11
$\begingroup$

Scott domains are often presented as having been introduced in 1969. However, the first (but numerous!) papers are from the 1970s, so it is not easy to know what the pertinent references are. My two criteria are:

  • historical significance (where was it published first?),
  • clarity (where was the theory first given a “stable” presentation?).

I have a list of suggestions I'll add below as a community wiki and which I'm already quite satisfied with, but I remember I struggled a bit with this a few years ago so maybe it will help somebody else in the future.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Can you be a bit more exact about what you mean by "Scott domain"? Nowadays this means a countably-based algebraic directed-complete bounded-complete poset, but in the late 1960's and early 1970's Dana Scott worked with complete lattices (continuous, algebraic), which I think were called domains also. What precisely are you looking for? $\endgroup$
    – Andrej Bauer
    Commented Dec 31, 2023 at 15:15
  • 3
    $\begingroup$ And are you aware of github.com/CMU-HoTT/scott ? $\endgroup$
    – Andrej Bauer
    Commented Dec 31, 2023 at 15:22
  • 2
    $\begingroup$ I assume you are asking about references where the concepts were originally introduced? Because otherwise Amadio and Curien's Domains and Lambda-Calculi, published in 1998, is a very comprehensive reference, good for citing in any technical paper not concerned with historical questions. $\endgroup$
    – Damiano Mazza
    Commented Dec 31, 2023 at 20:03
  • $\begingroup$ @Andrej: my second point was precisely related to the notion having evolved through time, so I had nothing special in mind. I wasn't aware of this repo, thanks a lot! $\endgroup$
    – sparusaurata
    Commented Jan 2 at 14:13
  • 1
    $\begingroup$ And thanks @Damiano too, maybe I should reorganise my answer with some textbook references like this. $\endgroup$
    – sparusaurata
    Commented Jan 2 at 14:14

2 Answers 2

Reset to default
12
$\begingroup$

I asked Dana Scott who kindly responded. I am relaying his answer:

I think the paper “A type-theoretical alternative to ISWIM, CUCH, OWHY” answers the questions and gives the context of the discovery. In mid-fall 1969 I was thinking of continuous functions and higher-type function spaces. And one afternoon lying on the guest-room bed I thought: “What about infinite types?” The rest is history, as they say.

I was supposed to be in Princeton for a new job, but had asked for the fall term off to work with Strachey. But then having to move and start a new job, I was too slow in publishing. Just another one of my many, many sins I have to keep paying for.

And do please weigh in for me at the Stack Exchange. Plotkin’s paper in the same collection is also very relevant as he discovered the use of enumeration operators.

Dana Scott (December 31st, 2023)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for this first-hand answer! $\endgroup$
    – sparusaurata
    Commented Jan 2 at 14:33
8
$\begingroup$

First papers

Scott (1993), A type-theoretical alternative to ISWIM, CUCH, OWHY.
This 1969 manuscript was later published in TCS. The title is a bit odd but it seems to hide the very first written reference.

Scott (1969, unpublished), Lattice-theoretic models for the λ-calculus.
This manuscript is cited by Wadsworth but I could find no copy of it.

Scott (1970), Outline of a mathematical theory of computation.
An introductory account of domain semantics is given in this one.

Scott (1972), Continuous lattices.
This is the first published paper on the topic. It was first released as a technical report in 1971.

Scott (1976), Data Types as Lattices.
This is also a standard reference.

“Textbook” references

Amadio and Curien (1998), Domains and Lambda-Calculi.
This “is a very comprehensive reference, good for citing in any technical paper not concerned with historical questions” (DM).

Comments

Scott writes:

Historically my first model for the λ-calculus was discovered in 1969 and details were provided in Scott (1972).

Tennent writes:

Scott [1970] is an outline of the axiomatic basis of his theory and its applications; the theory is developed in detail in Scott [1971a, 1971b, 1972b, 1972c, 1972d]. A fairly complete and systematic exposition is given in Reynolds [1972b].

Improve this answer
$\endgroup$
4
  • $\begingroup$ ISWIM stands for "if you know what I mean" and OWHY for "or what have you". I've forgotten what CUCH meant. $\endgroup$
    – Martin Berger
    Commented Dec 31, 2023 at 16:16
  • $\begingroup$ *ISWIM stands for "if you see what I mean", and CUCH stands for "Curry–Church". $\endgroup$
    – varkor
    Commented Dec 31, 2023 at 19:53
  • $\begingroup$ Scott explains this in the 1993 reprint: “The strange title of this paper ought perhaps to be explained. In 1966, Landin published an influential paper which introduced [a language] he called ISWIM, standing for “If you See What I Mean”. Also Böhm in 1966 named a language CUCH, standing for “Curry-Church”. There seemed to be a worrisome trend in funny acronyms starting here. The author hoped to stop some proliferation and deter the creation of programming languages of doubtful foundation called (as a group) OWHY, standing for “Or What Have You.” No one really understood the joke.” $\endgroup$
    – sparusaurata
    Commented Jan 2 at 14:19
  • 1
    $\begingroup$ Worldcat lists one copy of Lattice-theoretic models for the λ-calculus in the Centrum Wiskunde & Informatica. $\endgroup$
    – Jiak Kantang
    Commented Jan 2 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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