Flat vs non-flat domains

Question

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.

Answer 1

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.

Answer 2

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.

I also found a historical introduction to it which I have not read. And there seem to be some significant literature that followed.