5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Concerning adequacy at least, since you mention it, Schwichtenberg--Wainer have dealt with it in a non-flat setting, see here. (And thanks for making an answer out of your useful comments.) $\endgroup$ – Basil Nov 27 '14 at 12:09
  • $\begingroup$ That's interesting, thank you for the pointer! $\endgroup$ – Damiano Mazza Nov 27 '14 at 22:47
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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?... $\endgroup$ – Basil Nov 24 '14 at 15:08
  • 1
    $\begingroup$ @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. $\endgroup$ – babou Nov 24 '14 at 15:39
  • 1
    $\begingroup$ 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? $\endgroup$ – Basil Nov 24 '14 at 16:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Damiano Mazza Nov 25 '14 at 9:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Damiano Mazza Nov 26 '14 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.