<p>For what concerns the use of non-flat domains, babou already gave examples.  I can add that sometimes it may even be useful to see integers as streams: there's ⊥, above which there are 0 and S⊥, above the latter there are S0 and SS⊥, and so on.  I know that in the early 90s Loïc Colson worked on models using the above interpretation of integers, although I don't know exactly for what purpose.</p>

<p>So the usefulness of non-flat domains may be taken as understood and I will add some motivation as to why flat domains tend to be the "default choice" for interpreting base types.</p>

<p>In languages like PCF, the normal forms of every base type plus the equivalence class of all diverging terms of that type form a flat cpo with respect to the observational preorder. Therefore, if one is interested in full completeness (or even just adequacy) for PCF, interpreting base types as flat domains is a natural choice.  It works too: in all fully abstract models of which I am aware of (Milner's syntactic model and both Abramsky-Jagadeesan-Malacaria and Hyland-Ong-Nickau games models) base types are flat.</p>

<p>In fact, the difficulty in achieving full abstraction is to capture the sequential behavior of PCF (and, more generally, the operational behavior of its extensions, such as non-deterministic, probabilistic, quantum or whatever) and this has nothing to do with the flatness/non-flatness of base types (in fact, as I said above, from the syntactic point of view base types are flat).</p>

<p>So, in the context of adequacy/full abstraction, which is very important (and historically fundamental), there is no need to go beyond flatness, or at least we have not yet found a compelling reason to do so.</p>

CC BY-SA 3.0
2014-11-27T12:09:21.427Z
Concerning adequacy at least, since you mention it, Schwichtenberg--Wainer have dealt with it in a non-flat setting, see [here](http://books.google.it/books?id=C0avFThF2SgC&pg=PA287&lpg=PA287&dq=schwichtenberg+wainer+6.2.8+adequacy&source=bl&ots=1a1Fd7mr2c&sig=D_V4olBQNRteFCaA4aZSt3rRwRA&hl=en&sa=X&ei=jBN3VNvVCI3uat_dgbAP&ved=0CCMQ6AEwAA#v=onepage&q=schwichtenberg%20wainer%206.2.8%20adequacy&f=false). (And thanks for making an answer out of your useful comments.)
Basil
CC BY-SA 3.0
2014-11-27T22:47:20.457Z
That's interesting, thank you for the pointer!
Damiano Mazza
CC BY-SA 3.0
2014-11-26T17:02:03.867Z
2014-11-26T17:02:03.867Z
Damiano Mazza
<p>With only flat domains, you cannot define limits to construct
"infinite" structures, such as looping structures, for data or for
programs. Fixpoint constructions in denotational semantics (since you used that tag) use non flat domains.
Maybe you should give examples of domains that are taken as flat,
while it would be better to do differently.</p>

<p>Many problems we deal with are expressed with data from flat domains.
But non-flat domains are used when necessary or convenient. Infinite,
or indefinite structure such as stream are not flat. Some domains used
for program analysis, for example with abstract interpretation, are not
flat. But is pretty much because non-flat domains are more
appropriate, as information that can be obtained is expected to have
different degrees of precision.</p>

<p>One good example to look at (but I have no expertise) is the case of
real numbers. They are often considered in a flat domain, but they are
really limits in a non-flat domain. How much is that used, explicitly
or implicitly?</p>

<p><strong>Edit after the question was restricted to base types</strong></p>

<p>The nature of the question changes somewhat if you restrict it to base
types.</p>

<p>In many case, it would be interesting to see whether there are
alternatives to using flat domain, and what is the usefulness of such
alternatives. Is there a choice between flat and
non-flat for booleans? Is there one for integers? for characters? etc. What are the
pros and the cons.</p>

<p>But, to begin with, you may have to define what is a base type. This
is why I suggested looking at the real numbers. Should the domain be
considered flat or not.  Even in classical mathematics, reals can be
defined as limits. So you could ask the question whether reals are a
base type.</p>

<p>I have not looked at these issues for a long time, but I think the
following paper may be relevant: <a href="http://homepages.inf.ed.ac.uk/gdp/publications/Concrete.pdf" rel="nofollow">"Concrete Domains" by Gilles Kahn and
Gordon Plotkin</a>.</p>

<p>I also found a <a href="http://www.cs.cmu.edu/~brookes/papers/HistoricalIntroduction.pdf" rel="nofollow">historical introduction</a> to it which I have not
read. And there seem to be some significant literature that followed.</p>

CC BY-SA 3.0
2014-11-24T15:08:31.790Z
But fixpoints don't necessitate the use of non-flat domains; there's a fixpoint functional associated to every Scott domain, regardless if it's flat or not (indeed, as I say in the original post, the mainstream approach is to actually use flat ones, as far as I've seen). Am I misreading something?...
Basil
CC BY-SA 3.0
2014-11-24T15:39:22.503Z
@Basil Maybe I misread your question. You may indeed start with flat domains,
but the semantics you attach to functional operates in a non-flat
domain so that, iterating the functional gives you better and better
approximations of the fixpoint. And many non-flat domains can be
derived from flat ones.
babou
CC BY-SA 3.0
2014-11-24T16:24:54.923Z
I see what you mean, fixpoint functionals live at higher types, and of course, flatness is not preserved at higher types. I guess you can say that my questions concern exactly the choice of the base type model (and then, its implications for the higher types). You say "many non-flat domains can be derived from flat ones"; I take it you have domain equations in mind?
Basil
CC BY-SA 3.0
2014-11-25T09:07:48.263Z
I think you answered your own question: the subcategory of flat domains is not Cartesian closed (it is not even just Cartesian) so it makes no sense to restrict to flat domains in general and the real question is why use flat or non-flat domains to interpret base types.  @babou answered that: it depends on the way you see the data type.  In most cases integers can be taken as atomic entities (either you have nothing or an integer) but sometimes it is useful to see them as streams: there's $\bot$, above which there are 0 and S$\bot$, above the latter there are S0 and SS$\bot$, and so on.
Damiano Mazza
CC BY-SA 3.0
2014-11-25T10:44:16.920Z
@DamianoMazza I agree, and I should have put it clearer in the OP: the question is why flat or non-flat *base* types. Ah, but that's what edits are for, I guess... :-)
Basil
CC BY-SA 3.0
2014-11-25T11:03:34.587Z
@DamianoMazza The example of streams would be one answer to the question "why non-flat?" Are there answers for "why flat" as well, other than simplicity? (By the way, I've edited the original post, I hope it's clearer now.)
Basil
CC BY-SA 3.0
2014-11-25T11:29:56.450Z
@Basil I edited (actually complemented) my answer accordingly.
babou
CC BY-SA 3.0
2014-11-26T11:00:50.290Z
In languages like PCF, the normal forms of every base type plus the equivalence class of all diverging terms of that type form a flat cpo with respect to the observational preorder.  Therefore, if you are interested in full completeness results for PCF, interpreting base types as flat domains is a natural choice.  It works too: we know fully abstract models in which base types are flat (Milner's syntactic model and both AJM and HO games model).  So, in this (fairly important) context, there is no need to go beyond flatness, or at least we have not yet found a compelling reason to do so.
Damiano Mazza
CC BY-SA 3.0
2014-11-26T13:09:22.203Z
@DamianoMazza Well, I have not looked into the work of AJM or HO. Just to be certain: would you say that the issue of full abstraction for PCF via AJM-HO game-theoretic models should *not* be considered settled if we built on non-flat types (had we reasons to want to do so)?
Basil
CC BY-SA 3.0
2014-11-26T13:18:19.067Z
@babou Thanks for your time, and for the reminder of the Kahn--Plotkin work!... Concerning the reals, I actually know of different approaches, both interpreting them as higher-type objects over N (Cauchy sequences of rationals, etc), and as base type objects. In fact, on the latter, I happen to know of the recent work of [Kenji Miyamoto](http://www.math.lmu.de/~miyamoto) on the reals; there, he certainly uses a non-flat model. I'm not an expert in real arithmetic though, I would need some time to take your suggestion properly.
Basil
CC BY-SA 3.0
2014-11-26T13:18:55.320Z
No, I would say quite the contrary: if AJM or HO games semantics had achieved full abstraction by using a non-flat arena to interpret base types, I would have taken that as a good reason to use non-flat domains.  And if someone came up with some "really cool" fully abstract model in which base types are not flat, I would say the same thing.  However, for the moment I am not aware of any reason to prefer non-flat interpretations of base types over the simpler flat ones in the context of full abstraction for PCF and any of its extensions (non-deterministic, probabilistic or even quantum).
Damiano Mazza
CC BY-SA 3.0
2014-11-26T13:21:26.937Z
@DamianoMazza Ok, so you are indeed saying that we have full abstraction building on flat base types, but *not* building on non-flat base types, right?
Basil
CC BY-SA 3.0
2014-11-26T13:30:04.847Z
Yes, that's what I'm saying.
Damiano Mazza
CC BY-SA 3.0
2014-11-26T13:53:41.913Z
@DamianoMazza Okay, that's a nice crucial point, albeit realistic. By the way, and off-topic: wouldn't you say that your comments might very well be an official "answer"? I don't really mind, I get my answers alright, I'm just saying. (I don't know the etiquette of the site well yet.)
Basil
CC BY-SA 3.0
2014-11-26T14:40:38.503Z
@DamianoMazza Is it the case that we do not have full abstraction building on non-flat base types because it is much harder to do, Or is it simply the case that no one bothered.
babou
CC BY-SA 3.0
2014-11-26T16:26:11.443Z
@babou, I don't know for sure but I can give you my guess.  Building fully abstract models is already extremely hard and people knew very early on that the problem was capturing sequentiality, which has nothing to do with the flat/non-flat question.  So one might as well go with flat and I think that no-one really bothered to do otherwise.  I know that in the early 90s there was some work by Loïc Colson using "streamlike" integers (as described in my comment above) but I couldn't tell you exactly where and for what purpose (the best is to look into his papers from that time).
Damiano Mazza
CC BY-SA 3.0
2014-11-26T16:28:06.200Z
@Basil, if you are satisfied with my remarks and you think they give you an answer (additional to what babou already wrote), I will make it "official" of course.  I am going to do it as soon as I can.
Damiano Mazza
CC BY-SA 3.0
2014-11-24T14:27:45.167Z
2014-11-25T11:27:51.030Z
2014-11-25T11:27:51.030Z
babou
<p>My understanding is that, more often than not, when people use domain theory for higher-type computability or the denotational semantics of functional programming languages, they tend to prefer <em>flat domains</em> to interpret base types.</p>

<p>These are obviously simpler to handle than non-flat ones, a fact that is reflected both on theoretical issues, since reasoning about properties of the model can become quite a combinatorial task, as well as on issues phrased in a more applied parlance, like, say, strictness analysis. My understanding is also that there are things that one can pull out in non-flat domains that are simply not doable in the flat ones, perhaps the most trivial example being the injectivity of constructors.</p>

<p>But, I feel that my understanding is still quite uninformed and shallow.</p>

<p><strong>My questions</strong>: Why prefer flat domains? Why prefer non-flat domains? What are examples of things (theoretical or practical) that can be done in one setting but not, or <em>not yet</em>, in the other? Is there a reference with an account on such a comparison?</p>

<hr>

<p><strong><em>EDIT</strong> (25/11/14): I added explicit mention of the base types, after the discussion with babou and Damiano Mazza <a href="https://cstheory.stackexchange.com/a/27560/10146">below</a>.</em></p>

<reference-request><denotational-semantics><domain-theory>
Flat vs non-flat domains
Basil
# Flat vs non-flat domains

(Asked by: username_0 on 2014-11-24)

My understanding is that, more often than not, when people use domain theory for higher-type computability or the denotational semantics of functional programming languages, they tend to prefer *flat domains* to interpret base types.

These are obviously simpler to handle than non-flat ones, a fact that is reflected both on theoretical issues, since reasoning about properties of the model can become quite a combinatorial task, as well as on issues phrased in a more applied parlance, like, say, strictness analysis. My understanding is also that there are things that one can pull out in non-flat domains that are simply not doable in the flat ones, perhaps the most trivial example being the injectivity of constructors.

But, I feel that my understanding is still quite uninformed and shallow.

**My questions**: Why prefer flat domains? Why prefer non-flat domains? What are examples of things (theoretical or practical) that can be done in one setting but not, or *not yet*, in the other? Is there a reference with an account on such a comparison?

---

***EDIT*** (25/11/14): I added explicit mention of the base types, after the discussion with babou and Damiano Mazza [below](https://cstheory.stackexchange.com/a/27560/10146).

**Tags:** reference-request, denotational-semantics, domain-theory

---

## 2 answers

### Answer by username_1 on 2014-11-26. Score: 3 | Accepted answer

For what concerns the use of non-flat domains, babou already gave examples. I can add that sometimes it may even be useful to see integers as streams: there's ⊥, above which there are 0 and S⊥, above the latter there are S0 and SS⊥, and so on. I know that in the early 90s Loïc Colson worked on models using the above interpretation of integers, although I don't know exactly for what purpose.

So the usefulness of non-flat domains may be taken as understood and I will add some motivation as to why flat domains tend to be the "default choice" for interpreting base types.

In languages like PCF, the normal forms of every base type plus the equivalence class of all diverging terms of that type form a flat cpo with respect to the observational preorder. Therefore, if one is interested in full completeness (or even just adequacy) for PCF, interpreting base types as flat domains is a natural choice. It works too: in all fully abstract models of which I am aware of (Milner's syntactic model and both Abramsky-Jagadeesan-Malacaria and Hyland-Ong-Nickau games models) base types are flat.

In fact, the difficulty in achieving full abstraction is to capture the sequential behavior of PCF (and, more generally, the operational behavior of its extensions, such as non-deterministic, probabilistic, quantum or whatever) and this has nothing to do with the flatness/non-flatness of base types (in fact, as I said above, from the syntactic point of view base types are flat).

So, in the context of adequacy/full abstraction, which is very important (and historically fundamental), there is no need to go beyond flatness, or at least we have not yet found a compelling reason to do so.

> **Comments:**
> **username_0**: Concerning adequacy at least, since you mention it, Schwichtenberg--Wainer have dealt with it in a non-flat setting, see [here](http://books.google.it/books?id=C0avFThF2SgC&pg=PA287&lpg=PA287&dq=schwichtenberg+wainer+6.2.8+adequacy&source=bl&ots=1a1Fd7mr2c&sig=D_V4olBQNRteFCaA4aZSt3rRwRA&hl=en&sa=X&ei=jBN3VNvVCI3uat_dgbAP&ved=0CCMQ6AEwAA#v=onepage&q=schwichtenberg%20wainer%206.2.8%20adequacy&f=false). (And thanks for making an answer out of your useful comments.)  
> **username_1**: That's interesting, thank you for the pointer!  

---

### Answer by username_2 on 2014-11-24. Score: 4

With only flat domains, you cannot define limits to construct
"infinite" structures, such as looping structures, for data or for
programs. Fixpoint constructions in denotational semantics (since you used that tag) use non flat domains.
Maybe you should give examples of domains that are taken as flat,
while it would be better to do differently.

Many problems we deal with are expressed with data from flat domains.
But non-flat domains are used when necessary or convenient. Infinite,
or indefinite structure such as stream are not flat. Some domains used
for program analysis, for example with abstract interpretation, are not
flat. But is pretty much because non-flat domains are more
appropriate, as information that can be obtained is expected to have
different degrees of precision.

One good example to look at (but I have no expertise) is the case of
real numbers. They are often considered in a flat domain, but they are
really limits in a non-flat domain. How much is that used, explicitly
or implicitly?

**Edit after the question was restricted to base types**

The nature of the question changes somewhat if you restrict it to base
types.

In many case, it would be interesting to see whether there are
alternatives to using flat domain, and what is the usefulness of such
alternatives. Is there a choice between flat and
non-flat for booleans? Is there one for integers? for characters? etc. What are the
pros and the cons.

But, to begin with, you may have to define what is a base type. This
is why I suggested looking at the real numbers. Should the domain be
considered flat or not. Even in classical mathematics, reals can be
defined as limits. So you could ask the question whether reals are a
base type.

I have not looked at these issues for a long time, but I think the
following paper may be relevant: ["Concrete Domains" by Gilles Kahn and
Gordon Plotkin](http://homepages.inf.ed.ac.uk/gdp/publications/Concrete.pdf).

I also found a [historical introduction](http://www.cs.cmu.edu/~brookes/papers/HistoricalIntroduction.pdf) to it which I have not
read. And there seem to be some significant literature that followed.

> **Comments:**
> **username_0**: But fixpoints don't necessitate the use of non-flat domains; there's a fixpoint functional associated to every Scott domain, regardless if it's flat or not (indeed, as I say in the original post, the mainstream approach is to actually use flat ones, as far as I've seen). Am I misreading something?...  
> **username_2**: @Basil Maybe I misread your question. You may indeed start with flat domains, but the semantics you attach to functional operates in a non-flat domain so that, iterating the functional gives you better and better approximations of the fixpoint. And many non-flat domains can be derived from flat ones.  
> **username_0**: I see what you mean, fixpoint functionals live at higher types, and of course, flatness is not preserved at higher types. I guess you can say that my questions concern exactly the choice of the base type model (and then, its implications for the higher types). You say "many non-flat domains can be derived from flat ones"; I take it you have domain equations in mind?  
> **username_1**: I think you answered your own question: the subcategory of flat domains is not Cartesian closed (it is not even just Cartesian) so it makes no sense to restrict to flat domains in general and the real question is why use flat or non-flat domains to interpret base types.  @babou answered that: it depends on the way you see the data type.  In most cases integers can be taken as atomic entities (either you have nothing or an integer) but sometimes it is useful to see them as streams: there's $\bot$, above which there are 0 and S$\bot$, above the latter there are S0 and SS$\bot$, and so on.  
> **username_0**: @DamianoMazza I agree, and I should have put it clearer in the OP: the question is why flat or non-flat *base* types. Ah, but that's what edits are for, I guess... :-)  
> **username_0**: @DamianoMazza The example of streams would be one answer to the question "why non-flat?" Are there answers for "why flat" as well, other than simplicity? (By the way, I've edited the original post, I hope it's clearer now.)  
> **username_2**: @Basil I edited (actually complemented) my answer accordingly.  
> **username_1**: In languages like PCF, the normal forms of every base type plus the equivalence class of all diverging terms of that type form a flat cpo with respect to the observational preorder.  Therefore, if you are interested in full completeness results for PCF, interpreting base types as flat domains is a natural choice.  It works too: we know fully abstract models in which base types are flat (Milner's syntactic model and both AJM and HO games model).  So, in this (fairly important) context, there is no need to go beyond flatness, or at least we have not yet found a compelling reason to do so.  
> **username_0**: @DamianoMazza Well, I have not looked into the work of AJM or HO. Just to be certain: would you say that the issue of full abstraction for PCF via AJM-HO game-theoretic models should *not* be considered settled if we built on non-flat types (had we reasons to want to do so)?  
> **username_0**: @babou Thanks for your time, and for the reminder of the Kahn--Plotkin work!... Concerning the reals, I actually know of different approaches, both interpreting them as higher-type objects over N (Cauchy sequences of rationals, etc), and as base type objects. In fact, on the latter, I happen to know of the recent work of [Kenji Miyamoto](http://www.math.lmu.de/~miyamoto) on the reals; there, he certainly uses a non-flat model. I'm not an expert in real arithmetic though, I would need some time to take your suggestion properly.  
> **username_1**: No, I would say quite the contrary: if AJM or HO games semantics had achieved full abstraction by using a non-flat arena to interpret base types, I would have taken that as a good reason to use non-flat domains.  And if someone came up with some "really cool" fully abstract model in which base types are not flat, I would say the same thing.  However, for the moment I am not aware of any reason to prefer non-flat interpretations of base types over the simpler flat ones in the context of full abstraction for PCF and any of its extensions (non-deterministic, probabilistic or even quantum).  
> **username_0**: @DamianoMazza Ok, so you are indeed saying that we have full abstraction building on flat base types, but *not* building on non-flat base types, right?  
> **username_1**: Yes, that's what I'm saying.  
> **username_0**: @DamianoMazza Okay, that's a nice crucial point, albeit realistic. By the way, and off-topic: wouldn't you say that your comments might very well be an official "answer"? I don't really mind, I get my answers alright, I'm just saying. (I don't know the etiquette of the site well yet.)  
> **username_2**: @DamianoMazza Is it the case that we do not have full abstraction building on non-flat base types because it is much harder to do, Or is it simply the case that no one bothered.  
> **username_1**: @babou, I don't know for sure but I can give you my guess.  Building fully abstract models is already extremely hard and people knew very early on that the problem was capturing sequentiality, which has nothing to do with the flat/non-flat question.  So one might as well go with flat and I think that no-one really bothered to do otherwise.  I know that in the early 90s there was some work by Loïc Colson using "streamlike" integers (as described in my comment above) but I couldn't tell you exactly where and for what purpose (the best is to look into his papers from that time).  
> **username_1**: @Basil, if you are satisfied with my remarks and you think they give you an answer (additional to what babou already wrote), I will make it "official" of course.  I am going to do it as soon as I can.  

---

