Talk:Denotational semantics

From Wikipedia, the free encyclopedia

Denotational semantics and functional programming reinforced each other's development. The design of functional programming languages was influenced by denotational semantics, the connection is certainly not only in one direction.

Contents

[edit] Questions about recent additions by CarlHewitt

I believe some of the remarks added to the article regarding denotation semantics and concurrency are incorrect. The article suggest atm that denotational semantics is inherently non-concurrent. However, this is not the case: Plotkin shows in his 1997 TCS paper "LCF Considered as a Programming Language" that PCF (the LCF programming language) can be extended with the parallel or and that a denotational model based on domains can be defined for this extended language. Hence, it can be argued that domains already allow for concurrency.

In fact, up until the 1990s it was an active topic of research on how to put extra restrictions onto domains such that only sequential functions are represented (see e.g. Ong's chapter Correspondence between Operational and Denotational Semantics: The Full Abstraction Problem for PCF, in Vol 4 of the Handbook of Logic in Computer Science) -- Koffieyahoo 10:05, 6 September 2005 (UTC)

The article also seems to have been retargeted with a focus on the Actor model, which seems completely unjustified given the wide spread use of denotational semantic through out computer science. -- Koffieyahoo 10:09, 6 September 2005 (UTC)

The article cites orginal sources. Can you cite any errors in the article?--Carl Hewitt 16:28, 6 September 2005 (UTC)

At least at two points:

  • "The Actor model provides an extension of denotational semantics to concurrent computation as demonstrated first by a theorem of Carl Hewitt and Henry Baker [1977]". I read here that denotational semantics up until 1977, and hence domain theory (it was invented before 1977) was basically non-concurrent. However, as Plotkin shows also 1977, domain theory is already capable of expression concurrent programs (see reference above). Moreover, it is self the Actor Model is a syntact construct and requires a such requires a denotational semantics. So, saying that the Actor model provides the extension is incorrect if you believe that syntaxt is something different from semantics.
  • "Sequential computations form an ω-complete subdomain": this assumes that we know in a denotational sense what sequential computations are. However, as explained in the chapter by Ong (cited above) a satisfactory definition is still lacking at least in the case of domain theory: the exisisting definitions work okay for first order functions, but in the higher-order case they don't (this e.g. spawned the field of game semantics).

Two other remarks regarding you additions:

  • Is the indented part in Unbounded nondeterminism section a quote? If it is, it is of such length that is highly likely violates a copyright.
  • In Sequential computations form an ω-complete subdomain section there is an informal proof: It's not only my opinion that proofs have not real place in encyclopedias. That's what the references are for.

-- Koffieyahoo 07:47, 7 September 2005 (UTC)

Thanks for your comments.

  • Ong is not an original source.
  • The indented part is a direct quote from Clinger's disseration. It is included in the Wikipedia by permission of the author.
  • The proof is short and informal. It is best thought as being an argument. The Wikipedia allows arguments.

--Carl Hewitt 17:03, 8 September 2005 (UTC)

Three remarks on this:

  • Ong gives on overview. Overviews are an integral part of science: Due to the way in which they present existing work they normally lead to new insights. Moreover, he cites the original sources.
Not to detract from Ong's work, it is not an original source.--Carl Hewitt 14:25, 9 September 2005 (UTC)
  • I've seen no proof that Clinger did so. If he did so, please provide that proof.
Clinger gave permission in a private message to me. I suggest that you contact him directly.--Carl Hewitt 14:25, 9 September 2005 (UTC)
  • Didn't respond wrt the errors I pointed out. Please do so (Learn to respond to all arguments. Do proceed to practice this selective responding. It's very annoying. Moreover, learn to respond to the point.).

-- Koffieyahoo 10:34, 9 September 2005 (UTC)

Sigh, I don't see why I'm not allowed to cite an overview articles. Particular one that provides you with all the relevant references. Ong cites at least 50 relevant references which I'm not going to repeat here. Moreover, overview or not, this is completely irrevant considering the remarks. So, can you now please answer my questions and remarks. -- Koffieyahoo 14:45, 12 September 2005 (UTC)

You can cite overview articles. I was simply pointing out that they are not original sources.--Carl Hewitt 16:45, 12 September 2005 (UTC)

Regrarding Clinger's thesis: looking at the front matter of the thesis I can't even tell if he's the rightful copyright owner. That might in fact be MIT. -- Koffieyahoo 14:45, 12 September 2005 (UTC)

Clinger is the copyright owner. MIT has the right to distribute.--Carl Hewitt 16:45, 12 September 2005 (UTC)
Do you have any particular questions at this point?--Carl Hewitt 16:49, 12 September 2005 (UTC)

Wikipedia is an encyclopedia. As such, there is a policy of Wikipedia:No original research. For starters, it states: "In fact, all articles on Wikipedia should be based on information collected from primary and secondary sources." Overview articles are important references for Wikipedia. --TuukkaH 16:23:54, 2005-09-12 (UTC)

I agree.--Carl Hewitt 16:45, 12 September 2005 (UTC)
Besides evading many of Koffieyahoo's points, I would also point out that the article completely ignores the contributions of J. de Bakker and his collaborators on the denotational semantics of concurrency.--CSTAR 06:44, 10 November 2005 (UTC)
Is any of de Bakker's work on denotational semantics?--Carl Hewitt 07:33, 10 November 2005 (UTC)

[edit] Reply to Hewitt

For starters, you can look at [1]. Please note the following:

  • Krzysztof R. Apt, J. W. de Bakker: Exercises in Denotational Semantics. MFCS 1976: 1-11
  • J. W. de Bakker: Least Fixed Points Revisited. Theor. Comput. Sci. 2(2): 155-181 (1976)

Not listed there is work by P. America, J. Zucker, de Bakker and others specifically on denotational semantics of concurrency.

  • P. America, J. de Bakker, J. N. Kok and J. Rutten: Denotational semantics of a parallel object-oriented language, Information and Computation, 83(2): 152 - 205 (1989)

(This paper actually appeared many years earlier in a technical report published by Centrum voor Wiskunde en Informatica

This is one of a series of papers that consider metric space denotational models. The idea in these papers can be described as finding fixed points of contractive functors on metric categories.

--CSTAR 17:06, 10 November 2005 (UTC)
Samson Abramsky has also done some work in this area.--Carl Hewitt 13:20, 11 November 2005 (UTC)
I wasn't aware of any work that Abramsky has done in this specific area (metric space domains), but maybe he has. Anyway the article is deficient in references, in coverage of the material and in clarity. In particular, I don't think you're use of extensive direct quotes is helpful. Moreover, citing original sources in science does not mean the same thing as it does in history, (including history of science) since most work in science builds heavily on previous work. I don't see how your response to KoffieYahoo's objections, in which you assert that you cite original sources is relevant.--CSTAR 17:33, 11 November 2005 (UTC)
I studied with Abramsky for a couple of years at Imperial in the early 1990s. The article has a slanted POV. Charles Matthews 18:57, 11 November 2005 (UTC)
This article is particularly important, since it is of a foundational nature in COmputer Science. Aside from the intro gives a completely distorted view of denotational semantics. It should at least begin with denotational models for the lambda calculus and relate this to work of Dana Scott and Chris Strachey. I am willing to do this myself, although I would be very appreciative if someone else did this; I would like to avoid another confrontation with Hewitt. Thanks.--CSTAR 21:24, 11 November 2005 (UTC)
Of course you realize that the lambda calculus models are submodels of Actor models in which the arrival ordering of messages sent to Actors is not visible. Nevertheless this is a useful special case that deserves treatment.--Carl Hewitt 10:54, 21 November 2005 (UTC)
Nobody is disputing the generality of the actor model of computation and its ability to model various things such as concurrency and indeterminism. However, your approach makes about as much sense as to claim that to address (a): provide a denotational semantics for the lamba calculus it would suffice to achieve (b) provide a denotational model for Turing machines (including a definition of what this means). The exercise (b), though quite interesting, would not adequately address (a).--CSTAR 17:35, 21 November 2005 (UTC)

[edit] Denotational semantics of functions

Is this section properly titled? Semantics is a function from a set of syntactic objects into a semantic domain. In what sense are you giving semantics of a function. I'm not against using imprecise language, but I think these examples should be presented carefully. I'm not sure how to rename the section, but its current title is confusing.--CSTAR 05:42, 12 November 2005 (UTC)

I concur. What do you think of "Denotational semantics of functional programs"?--Carl Hewitt 05:52, 12 November 2005 (UTC)
That probably is better. The example you give is a functional (i.e., non imperative) program.--CSTAR 06:02, 12 November 2005 (UTC)
I made the change. Thanks for noticing this.--Carl Hewitt 14:08, 12 November 2005 (UTC)
The example is still confusing; It defines the meaning of a recursive functional program.--CSTAR 18:21, 12 November 2005 (UTC)
I don't quite understand what you find confusing. Thanks,--Carl Hewitt 13:23, 13 November 2005 (UTC)

[edit] Reply to Hewitt on Fixed point semantics

(Least) fixed point semantics is a natural (and the most common) way to associate a denotation to a recursively defined program. Least fixed points can also be used to solve reflexive domain equations. But in your example, you seem to suggest that any functional program requires a fixed point definition. This is not true. For example, a language consisting of natural numbers and polynomial operations (without recursion) does not need "fixed point semantics."

One major defect of the article is this: It never mentions the basic point of denotational semantics, which is to associate meaning to expressions in a compositional way. Semantics for languages which allow recursion rely on fixed point semantics to assign meaning to definition by recursion.

There are other defects, which I will mention in due course. --CSTAR 16:35, 13 November 2005 (UTC)

I have written a section on compositonality that treats it from a modern point of view. See what you think. You should be aware that some of the classical treatments of compositonality in the text books have severe limitations, e.g., they do not handle delayed evaluation.--Carl Hewitt 10:13, 21 November 2005 (UTC)
Your new section is not an improvement. For example, it doesn't explain how denotations of variable binding operators work. Saying this treats this from a "modern point of view" is your opinion, which I doubt is widely shared.--CSTAR 16:50, 21 November 2005 (UTC)
I have explained how variable binding works. See what you think.
That the Actor model approach to compositionality is a modern point of view is not just my opinion. See the references in Actor model. The reason that the Actor approach has become the modern point of view is that other approaches have run into trouble, e.g. with delayed evaluation.
Regards,--Carl Hewitt 18:47, 21 November 2005 (UTC)
Baloney. See for example work of Mitch Wand and coworkers, such as:
Guttman, J. D., Ramsdell, J. D., and Wand, M. VLISP: a verified implementation of Scheme. Lisp and Symbolic Computation, 8 (1995), 5--32.
--CSTAR 19:03, 21 November 2005 (UTC)
The problem with classical approaches for compositional denotatonal sementics in dealing with expressions of form "delay <Expression>" has been how to formaize the semantics of the evaluation of <E>.
The Actor model provides a perfectly reasonable account:
The delay expression responds to an <Eval> message with environment E by creating a closure Actor C that has an address (called body) for <Expression> an address (called environment) for E.
When C receives a message M with Customer0, it creates a new Actor Customer1 and sends <Expression> an Eval message with environment E and the address of Customer1.
When Customer1 receives a value V, it sends V the message M with Customer0.
What is your account for the semantics of delayed evaluation?
Regards,--Carl Hewitt 19:31, 21 November 2005 (UTC)
See exercise 9-14 (p205) of
  • Kent Dybvig, The Scheme Programming Language, Prentice Hall, 1987.
Given that a denotational semantics for Scheme exists, including continuations (as per previous reference) this completes the proof.--CSTAR 20:15, 21 November 2005 (UTC)
I don't think that you quite understand the problem here. Denotational semantics is supposed to be a mathematical model theory. You can't just go off and call some particular program (e.g. eval) in the middle of your mathematical model. This is particularly true when eval is written in the programming language for which a model is to be defined!--Carl Hewitt 20:36, 21 November 2005 (UTC)
I don't think that you quite understand the problem here. Nice figure of speech.
In fact, my proof does not use eval . If you like, see Abelson and Sussman. p 264 for an implemementation of delayed evaluation within Scheme. Scheme itself has a denotational semantics. --CSTAR 21:05, 21 November 2005 (UTC)
Ah, but we are talking about mathematical models for denotational semantics here not implementation. I have provided the Actor compositional semantics above. (It's modular, relatively complete, quite short and understandable that it is correct.) What is your denotational semantics for delayed evaluation?--Carl Hewitt 21:41, 21 November 2005 (UTC)

[edit] Delayed evaluation within scheme

Ah, but implementation as used here means simply adding two definitions (not implementation at some low level): The mathematical semantics extends trivially to the extended language. Quoting Abelson and Sussman:

 (define (force delayed-object)
   (delayed-object))

On the other hand

 (delay <exp>)

is syntactic sugar for

 (lambda () <exp>)

I am relying on the existimng denotational semantics for Scheme, which I have show (by citing references) exists.

This is also modular, quite short and understandable that it is correct.QED--CSTAR 21:53, 21 November 2005 (UTC)

Sorry but it is not correct because (delay <exp>) is not necessarily a function of 0 arguments and therefore cannot possibly be syntactic sugar for (lambda () <exp>). For example (delay (plus 3 4)) is not a function of 0 arguments. In fact it is not even a function because it is in effect the number 7.
So now can say that you really didn't mean to attempt to provide a semantics for delayed evaluation because that would be too difficult. Instead you meant to provide a "hacked" (in the nonpejorative Sussman sense) version of delayed evaluation. The idea of the hacked version is that if a program suspects that a value V might be using delayed evaluation, it needs to call force with the argument V in order to obtain the real value of delayed evaluation. Of course if the suspicion is wrong then an error can result such as "Wrong number of arguments".
Regards--Carl Hewitt 01:32, 22 November 2005 (UTC)

[edit] Reply

What I am saying (directly citing H. Abelson and G. Sussman with J. Sussman, Structure and Interpretation of Computer Programs, MIT Press (1985) p 264) is that (delay <exp>) is an expression and that the meaning of this expression is the meaning of

(lambda () <expr>)

The meaning of this expression in turn is given by the denotational semantics of Scheme without delayed evaluation (as supplied by various papers in the literature)

Are you now saying that Abelson and Sussman made a mistake? --CSTAR 22:32, 21 November 2005 (UTC)

Steele and Sussman were (and are) "hackers" (in the nonpejorative sense). They were caught between a rock and hard place since they didn't understand Actors (according to the book you cited above). So they cut out on their own and attempted to "hack" (i.e. implement) their way forward. This approach had some strengths, but also some important limitations.
One of the limitations is that they ended up in some strange places. The attempt to patch delayed evaluation into Scheme is one of them. Patching the future construct (developed by Henry Baker and myself) into Scheme was another place where things got even stranger. Since then Steele is trying to do better in his Fortress language.
I suppose that you have realized by now that there is no good way using the old text books and papers to write down the denotational semantics of true delayed evaluation (i.e. the version without the strange hack in Scheme). This is one reason that modern treatments of compostional denotational semantics use the Actor model.
Regards,--Carl Hewitt 01:22, 22 November 2005 (UTC)
Re: I suppose that you have realized by now... I'm sorry I don't believe anything of what you've said. You dismiss both Steele and Sussman as hackers, suggesting their approach was strange. Presumptuous to say the least.--CSTAR 02:42, 22 November 2005 (UTC)
It seems that you are unaware of the honorable tradition of being a "hacker" at MIT. So I would never say as you did in the log that Sussman and Steele are "just" hackers. Also do I take from your remarks that you think the semantics of delayed evaluation in Scheme are fine just as you have described them?
Regards,--Carl Hewitt 03:06, 22 November 2005 (UTC)

[edit] Rewrite proposal

I hadn't looked at this article since before CH started editing, and was provoked to do so by CSTAR's comments at Wikipedia:Articles for deletion/Scientific Community Metaphor. Although CH started with an article that was not in very good shape, the article as it now stands is so imbalanced that I think WP is worse off than it was. In its defence, it was interesting for me to read some of the comments of Will Clinger from his PhD thesis (although I think the article was cobbled together with so little regard for readers that only experts will appreciate them) and there is some good content provided in the Early history of denotational semantics section. The main problems are:

  1. While Will Clinger's work has some recognition in the area, mostly, I think, through Kohei Honda's discussion of his work, he is not remotely a current authority on the subject (disclosure: I know Will, although not well, and like his work. This comment is not a reflection on his ability, only on what he has chosen to work on);
    While it is true that Clinger has not recently worked on denotational semantics, his dissertation is still a classic work on the subject and remains state of the art in terms of published literature. It is widely know by researchers in the field. Recent work builds on it and will be published soon.--Carl Hewitt 18:59, 21 November 2005 (UTC)
    • See the topic below What should this article be about? --- Charles Stewart 22:12, 22 November 2005 (UTC)
  2. I had never heard of unbounded nondeterminism as a particular problem in the semantics of concurrency: from what I can gather from this article and that, it seems to be an issue in the expressiveness of particular languages for concurrency, but present no special difficulties for models. That a semantics can be used to show presence or absence of this property is the kind of thing worth including, but it looks to me that a presence in this article beyond that is unjustified.
    It turns out that unbounded nondeterminism is a critical issue for the semantics of concurrency. Noted pioneers in the field, e.g. Dijkstra, got it wrong and influenced others. With the advent of massive concurrency (Web Services and many-core) computer architectures, unbounded nondeterminism is becoming even more critical.--Carl Hewitt 10:33, 21 November 2005 (UTC)
    • I've been in correspondence with Will Clinger on this point, and I'm persuaded that it is worth documenting. But note what I say in the topic What should this article be about? below --- Charles Stewart 22:12, 22 November 2005 (UTC)
  3. Relatively little in what CH wrote is about the denotational semantics of concurrency as a topic in its own right. The kind of things I would expect to see arise in such a section are: powerdomains, event structures, computational adequacy theorems, full abstraction theorems, game semantics, and nondeterministic operators in the lambda calculus. This list, no doubt, shows my biases, but the tiny overlap with the contents CH provides sounds an alarm bell: only the first item from my list, as far as I can see, actually appears. The bibliography is worse still.
    The article discusses power domains for Actor model diagrams which are the most modern published treatment of computational adequacy in terms event structures, nondeterminism, and indeterminacy. It turns out that full abstraction is still a controversial topic: whose treatment are you thinking of reporting? A section on game semantics would be a useful addition. There will be additional publications on denotational semantics this summer which will require the article to be revised in any case. What additions would you like to make to the bibliography?--Carl Hewitt 10:39, 21 November 2005 (UTC)
    • Full abstraction is not controversial is the sense that it is a widely recognised property of a denotational semantics that has an uncontroversial formulation and that is widely recognised to be hard to do in several cases. There is a controversy over whether fully abstract models are the best models for providing semantics of programming languages. By a treatment of a topic, I mean that the topic should be introduced in a manner that not only experts will grasp. Even the treatment of power domains does not really say what they are; with other topics, such as event structures, the reader is left completely in the dark. --- Charles Stewart 22:12, 22 November 2005 (UTC)
I generally agree with your sentiments. However, in this case the devil may be in the details. E.g., what would you say is an uncontroversial formulation of full abstraction?
With respect to event structures the article states:
The augmented Actor event diagrams [see Actor model theory] form a partially ordered set < Diagrams, ≤ > from which to construct the power domain P[Diagrams] (see the section on Power Domains below). The augmented diagrams are partial computation histories representing "snapshots" [relative to some frame of reference] of a computation on its way to being completed. For x,y∈Diagrams, x≤y means x is a stage the computation could go through on its way to y. The completed elements of Diagrams represent computations that have terminated and nonterminating computations that have become infinite. The completed elements may be characterized abstractly as the maximal elements of Diagrams [see William Wadge 1979]. Concretely, the completed elements are those having non pending events. Intuitively, Diagrams is not ω-complete because there exist increasing sequences of finite partial computations
x0 ≤ x1 ≤ x2 ≤ x3 ≤ ...
in which some pending event remains pending forever while the number of realized events grows without bound, contrary to the requirement of finite [arrival] delay. Such a sequence cannot have a limit, because any limit would represent a completed nonterminating computation in which an event is still pending.
How can we improve?
Regards,--Carl Hewitt 22:47, 22 November 2005 (UTC)

In defence of CH, he is not a semanticist, and is documenting what he knows about. But the defence is rather weak when seen in the context of CH's pattern of editing elsewhere: the article is being used inappropriately to push the actor model, at the expense of balanced coverage of the topic at hand.

It would not be an improvement in the article to replace modern treatments and results with old obsolete ones.--Carl Hewitt 18:59, 21 November 2005 (UTC)

It's probably best to start fresh: I propose we start a new article and userfy the current article (ie. move it into CH's user space). --- Charles Stewart 21:06, 17 November 2005 (UTC)

I've changed my mind about starting from scratch, though the article needs heavy surgery. --- Charles Stewart 22:12, 22 November 2005 (UTC)

[edit] What should this article be about?

I think that this article should be mainly about two things:

  • The development of mathematical structures that are rich enough to be used in denotational semantics. See a class outline by Alex Simpson for what kind of thing I mean here;
  • The cataloging of features of computation and programming languages that are problematic or significant for denotational semantics.

When I said above that the problem of unbounded nondeterminism present no special difficulties for models, I meant that it did not require subject-changing innovations in the kinds of mathematical structures used to give models. IMO, it's these kind of innovations that constitute the classic works of the topic. These works by no means exhaust good work in denotational semantics, but they do help you distinguish work on the core of denotational semantics, which is ultimately directed at achieving such progress, from applied work in denotational semantics that attempts to make use of these refined techniques. Furthermore they tend to get sigtnificant citations by both classes of work. Apart from the citation by Kohei Honda, I don't see any citations by anyone I recognise as a worker on the structures half of the subject. --- Charles Stewart 22:12, 22 November 2005 (UTC)

Thanks for your comments.
Robin Milner has favorably cited Clinger's work. Also I can tell you that most participants at the recent CONCUR conference have at least passing acquaintance with this material. Also the participants were generally of the opinion that programming languages that are not concurrent are rapidly becoming obsolete. Concurrency lies at the core of modern day denotational semantics.
Regards,--Carl Hewitt 22:37, 22 November 2005 (UTC)

[edit] "Example of factorial function" needs explanation

I think the first example is insufficiently explained. Is the "factorial" that appears in graph(factorial) and Fix_factorial the same quantity? What is the convention for representing partial functions as sets of pairs? (e.g. I think it would help to say that domain values for which the function is undefined are simply not included in the set, if this is the case) What is a fix point operator and why is Fix_factorial one? What does omega-complete mean? I think it's a good idea to have a simple example like this early on, but it should be fleshed out a bit (and I'm not qualified to do it). A5 21:56, 21 November 2005 (UTC)

Thanks for your comments and questions. I have rewritten the section to make it more readable. Please take a look and get back with more questions and comments. This is how we improve articles on the Wikipedia.
In answer to your first question, in mathematics the same name invariable means the same thing so that factorial is the same in graph(factorial) and Fixfactorial. Hopefully your other questions are answered in the rewritten section.
Regards,--Carl Hewitt 06:56, 22 November 2005 (UTC)

[edit] Apology to CSTAR

I would like to apologize to CSTAR for the tone of 2 of my remarks in our recent discussion above on delayed evaluation:

  1. I suppose that you have realized by now ...
  2. I don't think that you quite understand the problem here ...

These remarks were not collegial and I will strive to do better in the future.

Regards,--Carl Hewitt 06:46, 24 November 2005 (UTC)

[edit] Article is a mess

The article is a mess. Wikipedia is supposed to be a general-purpose encyclopedia. I don't think anyone who isn't already an expert in the field can hope to make head or tail of this.

The article needs to include:

  • a brief recap of computational semantics in general (operational, denotational, axiomatic approaches);
  • introduction the notion of a mathematical function representating a computer program with simple examples (non-recursive, non-looping, deterministic, non-parallel — could be imperative rather than functional);
  • motivation of the study of denotational semantics e.g. by proving equivalence relations between programs;
  • introduction of the method of structural induction for constructing denotations;
  • motivatation of domains by introducing looping and recursion, non-termination and fixed points.
  • relation of denotational semantics to operational semantics

There are several things that are odd about the article, in particular:

  • actor theory is given way too much prominence (if it's mentioned, it should be briefly as one of a set of models of non-deterministic computation);
  • the article slips from explaining denotational semantics to presenting actor semantics, which is not the same thing at all;
  • the explanation of "fully abstract" is quite wrong.

Maybe the right thing to do would be to move this article to actor semantics and start over? Gdr 06:51, 9 January 2006 (UTC)

[edit] Denotational semantics is a field under active development

Hello Gdr,

Welcome to our disucssions! You have arrived at an article on a field that is under active development by many researchers who have long since realized tha the older sequential view of computation is obsolete. That a concurrent system is not well represented by a mathematical function has been known for over three decades. Since the field is under development, negotiation of article content may prove to be more difficult than in fields have have stabilized.

Since denotatinal semantics is a field with a large publsished literature, We are going to end up with several articles on denotational semantics as it is a significant area of research. The questions is: How do we get there?"

With respect to your points (in italics)

  • a brief recap of computational semantics in general (operational, denotational, axiomatic approaches);
It would probably better to include a link to an article that provides an overview
  • introduction the notion of a mathematical function representating a computer program with simple examples (non-recursive, non-looping, deterministic, non-parallel — could be imperative rather than functional);
Mathematical functions are totally inadequate as denotations for computational systems. They are a special case that probably deserves its own article may titled something like Denotational semantics of functional programs. Models of the lambda calculus would go here
  • motivation of the study of denotational semantics e.g. by proving equivalence relations between programs;
Proving the equivlance of systems (induction, bi-simulation, model checking, etc.) deserves its own article.
  • introduction of the method of structural induction for constructing denotations;
Constructing denotations of sytems in computational domains by taking limits to fixed points is a central topic of denotatinal semantics. Do you have suggestions for how to improve the current treatment in the article?
  • motivatation of domains by introducing looping and recursion, non-termination and fixed points.
It is important to distinguish computational domains from programs that have looping and recursion. In due course we will need a separate article on comptatonal domains.
It is true that computational domains can be used to distinguish sequential computation from general concurrency. Do you have suggestions for how to improve the current treatment in the article?
  • relation of denotational semantics to operational semantics
The relationship between denonation semantics and operational semantics deserves its own article. E.g. We might try something creative like Denotational semantics and operational semantics ;-)

With respect to your other points (in italics)

  • actor theory is given way too much prominence (if it's mentioned, it should be briefly as one of a set of models of non-deterministic computation)
Denotational semantics is about mathematical denotations of computational systems. These days computational systems means concurent systems. So the denotational semantics of the process calculi and Actor model need to figure prominently in the article denotational semantics.
It is very important to distinguish the classical models of nondeterministic computation from concurrent computation. E.g. see the article unbounded nondeterminism.
  • the article slips from explaining denotational semantics to presenting actor semantics, which is not the same thing at all
Please see my comment above about the importance to the article of denotational models for Actors and process calculi.
  • the explanation of "fully abstract" is quite wrong
The explanation of fully abstract was inserted at the suggestion of another Wikipedia editor. Unfortunately it is now little more than a stub. Eventually we will probably end up with a separate article Full abstraction.
In the meantime, why do you think that is wrong? Also, how can it be improved?

Regards, --Carl Hewitt 21:00, 9 January 2006 (UTC)

I propose that we junk or move the actor theory stuff and give a traditional treatment of the field, starting with functional and imperative programs. Get the simple stuff right first. Gdr 21:16, 9 January 2006 (UTC)
The article already includes a section on the denotational semantics of a simple functional program: factorial. Please make suggestions how to improve this section.--Carl Hewitt 23:51, 9 January 2006 (UTC)
A quick survey on Google Scholar (admittedly an ad hoc test, but better than nothing) reveals ~264 hits involving denotational semantics and concurrency since 2000, and ~811 hits involving denotational semantics alone (with no reference to concurrency) since 2000 (a search for actor and denotational semantics gives ~38 hits since 2000 - not all related to the actual Actor model). This would seem to suggest that even modern research on denotational semantics is predominantly non-concurrent. Therefore, I think that Gdr's suggestion to give a more traditional treatment of the field is a good one.
It is probably reasonable to have a small section on the denotational semantics of concurrency near the end of the article (possibly with a pointer to a separate article on the denotational semantics of concurrency if there seems to be sufficient material). Regarding that section, it seems worthwhile to keep in mind that Google Scholar gives only ~16 hits for articles involving denotational semantics, concurrency, and actors (versus 211 for concurrency and denotational semantics in general). The equivalent numbers for the time period 1970 to 2006 are ~818 hits for concurrency and denotational semantics, of which ~74 hits include references to an "actor" of some kind, and ~2740 hits for denotational semantics articles that exclude concurrency and actors. This would tend to lend credence to Gdr's assertions about the excessive prominence given to the semantics of concurrency in general, and the semantics of the Actor model in particular. --Allan McInnes 23:27, 9 January 2006 (UTC)
Wikipedia science articles should reflect the current state of the art. There is no advantage to focusing on old science. I suggest that the current state of the art is reflected in the following references:
  • Will Clinger, Foundations of Actor Semantics. MIT Mathematics Doctoral Dissertation, June 1981. (Quoted by permission of author.)
  • He Jifeng and C.A.R. Hoare. Linking Theories of Concurrency United Nations University International Institute for Software Technology UNU-IIST Report No. 328. July, 2005.
  • Luca Aceto and Andrew D. Gordon (editors). Algebraic Process Calculi: The First Twenty Five Years and Beyond Process Algebra. Bertinoro, Forl`ı, Italy, August 1–5, 2005.
  • Bill Roscoe. The Theory and Practice of Concurrency Prentice-Hall. 2005.
The older special case stuff on denotational semantics of sequential and functional languages needs to go in its own specialized articles.
However, as I mentioned the field of denotational semantics is under active developmeent. This a fact which does not seem to be reflected in Google Scholar but Google will eventually figure out how to improve. There is a new denotational semantics for the Actor model this is in preprint. Google Scholar cannot be expected to know about it because it has not yet been published. But the article on denotational semantics will have to take it into account after it is published.
Regards, --Carl Hewitt 23:51, 9 January 2006 (UTC)
Carl,
You raise several different issues, which I will endeavour to address:
  1. A dissertation from 1981 hardly counts as the "current state of the art".
  2. Google Scholar provides a good survey of a wide variety of different archival publications. It is not perfect, but can be useful for providing an idea of general trends.
  3. The relative numbers of publications on denotational semantics since 2000 would seem to indicate that the "current state of the art" still leans heavily towards non-concurrent semantics. While I agree that concurrency semantics is important, and reflects a more general model than non-concurrent semantics, it is hardly the predominant portion of either denotational semantics research in general, or modern denotational semantics research.
  4. Neither Roscoe's work, or the work reported in the Algebraic Process Calculi reference, is really part of the mainstream of denotational semantics research.
  5. Please see my comments below regarding the treatment of "unstable" fields.
--Allan McInnes 00:27, 10 January 2006 (UTC)
Alan,
I have provided responses to your comments above:
  1. A dissertation from 1981 hardly counts as the "current state of the art".
Yes, amazing enough Clinger's dissertation is still "current state of the art". However, as I mentioned, there is an article in preprint that will considerably advance his work.
  1. Google Scholar provides a good survey of a wide variety of different archival publications. It is not perfect, but can be useful for providing an idea of general trends.
Google Scholar is probably not the best way to discern general trends. The generally accepted way to get an idea of current general trands is to ask the leaders in the field.
  1. The relative numbers of publications on denotational semantics since 2000 would seem to indicate that the "current state of the art" still leans heavily towards non-concurrent semantics. While I agree that concurrency semantics is important, and reflects a more general model than non-concurrent semantics, it is hardly the predominant portion of either denotational semantics research in general, or modern denotational semantics research.
The predominant portion of current research on denotational semantics is devoted to concurrency.
  1. Neither Roscoe's work, or the work reported in the Algebraic Process Calculi reference, is really part of the mainstream of denotational semantics research.
When I recently heard from Tony Hoare, he referred to Roscoe's work as mainstream. Also the following reference is as "mainstream" as it gets:
  • Luca Aceto and Andrew D. Gordon (editors). Algebraic Process Calculi: The First Twenty Five Years and Beyond Process Algebra. Bertinoro, Forl`ı, Italy, August 1–5, 2005.
Who are all these other "mainstream" researchers in denotational semantics?
  1. Please see my comments below regarding the treatment of "unstable" fields.
Please see my response to your comments below.
Regards, --Carl Hewitt 01:30, 10 January 2006 (UTC)
Carl,
  • Who do you consinder to be the "leaders" in the field of denotational semantics that we should be consulting?
  • You assert that the "predominant portion of current research on denotational semantics is devoted to concurrency". I disagree, and have provided statistical evidence based on Google Scholar searches to support my position. What evidence can you offer to support your assertion?
  • Roscoe's work (incidentally, he doesn't appear to have published much new on the denotational semantics of CSP since about 1998) and the Bertinoro conference are certainly mainstream in the process calculi community. Are they mainstream in the denotational semantics community?
  • "Mainstream" researchers in denotational semantics: a few examples might include Sam Abramsky, Andrew Pitts, Eugenio Moggi, Achim Jung, and Giuseppe Rosolini.
  • This survey paper on denotational semantics describes a number of open problems. As far as I am aware, many of them are still the subject of active research. Few of them seem to be specific to concurrency.
  • As I said before, I think concurrency semantics are important. But they are not the core or only concern of denotational semantics, and I think it is a mistake to represent them as such. There is a vast difference between denotational semantics in the general case, and concurrency semantics in the particular case. This article should not be focused on concurrency semantics. The current Cambridge syllabus for their denotational semantics course gives a pretty good overview of the sort of material I would expect this article to cover. Not surprisingly, it agrees well with the suggestions that Gdr made.
--Allan McInnes 08:39, 10 January 2006 (UTC)


Alan,
I have responded to your points below:
  • Who do you consinder to be the "leaders" in the field of denotational semantics that we should be consulting?
On questions of denotational semantics a list of very senior people to consult would include Abramsky, Clinger, Hoare, Milner, Montanari, Roscoe, and Winskel. Of course there are many others.
  • You assert that the "predominant portion of current research on denotational semantics is devoted to concurrency". I disagree, and have provided statistical evidence based on Google Scholar searches to support my position. What evidence can you offer to support your assertion?
All of the researcher that I have listed above have recently worked in concurrency.
  • Roscoe's work (incidentally, he doesn't appear to have published much new on the denotational semantics of CSP since about 1998) and the Bertinoro conference are certainly mainstream in the process calculi community. Are they mainstream in the denotational semantics community?
Roscoe has updated his book as recently as last year. Some of the Berinoro contributors reference more recent work on the denotational semantics of concurrent systems.
The above survey was published a decade ago.
  • As I said before, I think concurrency semantics are important. But they are not the core or only concern of denotational semantics, and I think it is a mistake to represent them as such. There is a vast difference between denotational semantics in the general case, and concurrency semantics in the particular case. This article should not be focused on concurrency semantics. The current Cambridge syllabus for their denotational semantics course gives a pretty good overview of the sort of material I would expect this article to cover. Not surprisingly, it agrees well with the suggestions that Gdr made.
Concurrent systems are the general case; both sequential and functional systems are special cases of concurent systems. Consequently denotational semantics in the general case is the denotational semantics of concurrent systems.
Winskel's syllabus begins with material that is completely general to concurrent systems:
  1. Introduction. Recursively defined objects as limits of successive approximations. Examples.
  2. Least fixed points. $\omega$-complete partial orders (cpos) and $\omega$-continuous functions. Least elements. Least fixed points of $\omega$-continuous functions.
  3. Constructions on domains. Products of domains. Function domains. Flat domains.
  4. Scott induction. Chain-closed and admissible subsets of cpos and domains. Scott's fixed point induction principle.
Winskel's syllabus then proceeds to the special case of the denotational semantics of the lambba calculus. Winskel may teach the denotational semantics of concurrent systems elsewhere in the curriculum (I haven't asked him).
Note that the general semantics of concurrent systems is a separate topic that deserves its own article. Perhaps we should try something creative like Concurrent computing semantics ;-)
Regards, --Carl Hewitt 19:35, 10 January 2006 (UTC)
Carl,
  • I don't intend to argue about who does or does not constitute a "leading" researcher in denotational semantics. But I will note that many of the people you list are researchers in concurrency, so of course their denotational semantics work will revolve around concurrency. That does not change the fact that there are other "leading" researchers not working on concurrency, or not focusing on it exclusively.
  • I am aware of Roscoe's recent update to his book. It does not contain any substantial changes to the denotational semantics, and only a few additions (involving infinite traces).
  • The survey paper is 15 years newer than Clinger's dissertation.
  • This is getting silly. We apparently both agree on what constitutes the core of denotational semantics (viz. the early parts of Winskel's syllabus), which is something that is general across both concurrent and sequential semantics. That core, and how it can be generally used to provide a semantics for some language, is what I think this article should be about. As I have said elsewhere, I would be happy to see discussions on specific applications (such as semantics for concurrent formalisms or functional languages) as well, but they should not be the focus of the article.
--Allan McInnes 20:03, 10 January 2006 (UTC)
Allan,
I still maintain that the current consensus is that concurrency is both the general case and the heart of the matter for denotational semantics.
Above, you pointed to survery paper to indicate what the current central issues are in denotational semantics. I pointed out in response that the paper was published a decade ago.
I propose that the following topics be included in a new article on Computational domains:
  1. Introduction. Recursively defined objects as limits of successive approximations. Examples.
  2. Least fixed points. $\omega$-complete partial orders (cpos) and $\omega$-continuous functions. Least elements. Least fixed points of $\omega$-continuous functions.
  3. Constructions on domains. Products of domains. Function domains. Flat domains.
  4. Scott induction. Chain-closed and admissible subsets of cpos and domains. Scott's fixed point induction principle.
In this way we could concentrate on the central topic of denotational semantics: mathematical meanings of concurrent systems with subarticles for special cases e.g. sequential, functional, and Petri nets.
Regards, --Carl Hewitt 20:27, 10 January 2006 (UTC)
Regarding the assertion that Since the field is under development, negotiation of article content may prove to be more difficult than in fields have have stabilized. : science in general is a field under development, as is mathematics. In those fields Wikipedia generally appears to provide coverage of those parts of the fields in question that are generally accepted and "stable". In some cases there may also be some mention of what the current directions in research are. There is a large body of established work on denotational semantics that can be readily described in this article. The courses, survey articles, and texts on denotational semantics that others have pointed to on this talk page give a good indication of what tat established body of knowledge is. It seems reasonable that this article should provide an encyclopaedic overview of that established material. A section on "current research thrusts" (or something similar) is probably reasonable too, but shouldn't be allowed to get too large or detailed, since the material in question is (as Carl has already pointed out) "unstable". --Allan McInnes 23:58, 9 January 2006 (UTC)
The general consensus of researchers in the field is that concurrency is the heart of the matter. In science whole bodies of publicatons can be made obsolete by new research. Research in concurrency is "stable" in the sense that there is a large body of published research and general agreement on many results and issues that have even been recognized by more than one Turing award of long duration. It is not to be diminished as "current research thrusts". However research on concurrency has not stabilized in that it is currently an area of vibrant development.
Note that I am not saying that the older research on functional and sequential programs should not be reported in the Wikipedia. These topics deserve their own specialized subsidiary articles.
Regards, --Carl Hewitt 00:22, 10 January 2006 (UTC)
What you refer to as "older research on functional and sequential programs" constitutes the core of denotational semantics, and remains the focus of much of the modern research on, and application of, denotational semantics. While those forms of semantics may not be as general as concurrency semantics, they are still very useful, and very heavily used (just as the λ-calculus is still useful and heavily used, despite the existence of the π-calculus). Given my background (which you are aware of, since you have raised it in other discussions), I am hardly one to diminish the importance of concurrency. But I think that the emphasis on concurrency is misplaced in this article. --Allan McInnes 01:18, 10 January 2006 (UTC)
In the Wikipedia, in the head article on a topic, we do not typically feature a special case of the topic to the neglect of the general case, e.g., General Relativity, Concurrent computing, etc.
Again, I am not saying that the older research on denotational semantics of functional and sequential programs should not be reported in the Wikipedia. These topics deserve their own specialized subsidiary articles. The older work is still of some interest although to be of real current value it needs to be reworked in the context of concurrent systems.
Also, who are all these researchers who are currently hacking away at the denotational semantics of sequential and functional programs?
I am indeed aware of your background and consequently find your comments here puzzling.
Regards, --Carl Hewitt 01:57, 10 January 2006 (UTC)
Wikipedia head articles should provide a general, encyclopaedic overview of a topic. Focussing on concurrency semantics to the exclusion of other aspects of denotational semantics would seem to be contrary to that goal. Those other aspects of denotational semantics are still extremely relevant, and continue to be the subject of active research. Examples of recent research in this area can be found in the publications lists of the researchers I identified in my comment above. Here are a few other examples of recent (post-2000) research involving non-concurrent denotational semantics for functional and imperative languages (including XSLT, Java, and C): [2], [3], [4], [5], [6], [7].
--Allan McInnes 08:53, 10 January 2006 (UTC)
I'm now going to try to short-circuit the above discussion (and I'll probably fail utterly): As far as I'm concerned both denotational semantics of models of programming languages and models of concurrency are important. That said, when you look at denotational semantics defined for both, generally the exact same tools from mathematics are used. Hence, as models of programming languages are generally considered to be 'simpler' than models of concurrency I think it's best to explain denotational semantics of models of programming lanhuages first and to then discuss models of concurrency.
  • I'll now suppose some people will freak out of the exact same part above. If so, please point me to references that show that really different tools are used.
  • As far as I know, the formulation of full abstraction in the context of concurrency is exactly the same as in the context of programming languages.
  • Just pointing out a text book on denotational semantics of concurrency and programming languages: De Bakker and De Vink, control flow semantics [8].
-- Koffieyahoo 10:35, 10 January 2006 (UTC)
That sounds reasonable to me. I think that's pretty much what Gdr was suggesting too. As I have mentioned several times now, I'm not trying to diminish the importance of denotational semantics for concurrency. I just think that the emphasis on that aspect of denotational semantics is wrong in this article. Ideally, I'd like to see this article rewritten such that it primarily describes what denotational semantics is in general, but also provides brief discussions of specific uses of denotational semantics (such as providing semantics for functional programming languages and for models of concurrency).
--Allan McInnes 18:39, 10 January 2006 (UTC)
Yes, it is true that the denotational semantics of concurrent systems and the denotational semantics of concurrent programming languages share mathematical foundations. The reason is that (as pointed out in the article) concurrent programs are concurrent systems. Consequently, general theory of concurrent systems covers programming languages.
Regards, --Carl Hewitt 05:04, 11 January 2006 (UTC)
The idea is that we want to write a readable article. Hence, we don't want to present every gory detail of concurrent systems in one blow. -- Koffieyahoo 07:51, 11 January 2006 (UTC)
I completely agree that we want a readable article.
So it important to concentrate on the big picture and general principles. The current article attempts to do this in the beginning. I am sure that it could be improved. I don't see how concentrating the article on spcecial cases is going to help, i.e., the the denotational semantics of functional, sequential, object-oriented, and logic programs.
Regards, --Carl Hewitt 17:25, 11 January 2006 (UTC)

There is really no need to shout. I see that consensus here rejects your proposal to place the standard theory arising from Dana Scott's work elsewhere. And quite rightly, in my view. As we know λ ≠ π, but is prior to it. Charles Matthews 20:44, 10 January 2006 (UTC)

Hi Charles,
Sorry for the shouting. We have problems in our technology trying to indicate what is the essential point when it seems to be being ignored. I have been attempting to use bold face for this purpose even though I would prefer a better tool. I am sorry that it annoyed you.
I am not proposing to relegate Dana Scott's work to elsewhere but rather to give it a proper respectful place of honor. I don't think that Dana would be offended by having his work referenced in an article on Computational domains.
It is true that the work on the lambda calculus was prior to the work on concurrent systems. But science continually moves on and the Wikipedia needs to be current. After all, it's one of our claimed advantages over older encyclopedias, e.g. Britannica ;-)
Regards, --Carl Hewitt 21:04, 10 January 2006 (UTC)
You could use double quotes instead of triple quotes... Moreover, if you think we need to explain every gory detail of comutational domains here, you're wrong, as there still is this article on Domain theory.-- Koffieyahoo 07:51, 11 January 2006 (UTC)
I did not propose to explain computational domains in the article denotational semantics. Instead I proposed the creation of a new article computational domains which would include the additional content that I listed which goes beyond what is found in the article domain theory.--Carl Hewitt 17:33, 11 January 2006 (UTC)

Carl, you are causing big problems here with this science continually moves on stuff. Denying that you are trying to sideline the work of major people in the field, in so doing, is only making matters harder to resolve. And WP only 'needs' to be current in the sense that bringing coverage up to date is a long-term objective. Where the foundations are not laid properly, in a mathematical area, we cannot claim to have proper coverage. So please decease and desist from your persistent argument, that you have insight here that others do not. There seem to be several other, well-informed folk editing this page. Your line of argument in no sense trumps what they are saying, as you appear to think. Charles Matthews 11:50, 11 January 2006 (UTC)

[edit] Response by Koffieyahoo

I totally agree. I'm also under the impression that anyone else who cares is waiting for this to blow over: Wikipedia:Requests for arbitration/Carl Hewitt. -- Koffieyahoo 07:51, 9 January 2006 (UTC)

The main point about the relationship of denotational to operational semantics is that they are different. This is an expression of the polarity extensional/intensional, if not the only one. Concurrency is not the same as denotational models of functional programming. Perfectly true. Not necessarily the main issue in a report on denotational semantics, though. Charles Matthews 20:47, 9 January 2006 (UTC)
Hello Charles,
It seems to me that denotational semantics is about mathematical denotations of computational systems. These days computational systems means concurent systems. Shouldn't the main article on denotation semantics treat the general case and provide links to articles on special cases?
That said, I do agree with your fundamental point that denotational and operational semantics are differenet.
Regards, --Carl Hewitt 21:12, 9 January 2006 (UTC)
Denotational semantics of functional programming languages is basic stuff. You shouldn't superimpose a current, 'research proposal' argument on that. You are muddying the waters by saying 'general case'. Properly-structured mathematical articles here do not start in the general case, but with classical material. We do access to the theory as primary, and surveys on current research only when the foundations have been laid. To put it another way, I spent quite some time studying this area, and it is clear to me that 'issues-led' is quite different from settled theory. The emphasis in Wikipedia should certainly be on getting the latter straight. Charles Matthews 09:19, 10 January 2006 (UTC)
I am not proposing that this Wikipedia article be based on an a 'research proposal' argument. Certainly the following publications present denotational semantic models that can be considered classic and are settled theory:
  • Will Clinger, Foundations of Actor Semantics. MIT Mathematics Doctoral Dissertation, June 1981.
  • Bill Roscoe. The Theory and Practice of Concurrency Prentice-Hall. 1997
Where do you suggest that the Wikipedia report on the denotational models in the above published research? It is not the case that the denotational semantics of concurrency is in any way flaky even though it is an active field of research.
The denotational semnantics of functional and sequential programs is basic stuff that is a special case of denotational semantics of concurrent programs. Because there is well established theory for denotational semantics of concurent programming languages, it is not muddying the waters to point this out.
Regards, --Carl Hewitt 17:40, 11 January 2006 (UTC)
Carl, as you yourself state, the references you provide present denotational semantic models. They are not denotational semantics, in the sense that they subsume and obsolete all previous work on denotational semantics. Roscoe alone presents at least four different denotational semantics for CSP (traces, stable failures, failures-divergence, and infinite traces). They are all different. But they all use the same underlying approach. That's what makes them denotational semantics instead of operational or axiomatic (or some other kind of) semantics. This article should be about that approach to defining a semantics. It is completely reasonable to also include some description of specific applications of that approach (such as defining denotational semantic models for concurrent systems), and describe some of the problems and solutions that arise in addressing those application areas. What everyone is objecting to is your attempts to make the entire article about one type of denotational semantic model, instead of about denotational semantics in general. --Allan McInnes 23:57, 11 January 2006 (UTC)
Alan,
I completely agree with you that the article should be about denotational semantics in general and not one particular denotational semantics. The article should report principles and methods that are common to all the approaches to denotational semantics.
Certainly the article Denotational semantics should not just report on Clinger's Actor denotational model. In fact the current treatment of Clinger's model should be abstracted into principles and methods in the article Denotational semantics and a new article Denotational semantics of Actors should be created for the details about Actors.
Similarly in Denotational semantics there should be some general reporting of the approaches of traces, etc. in CSP, the scenarios of the Actor model, testing regimes, etc. A new article should be created where the details of the different approaches are reported.
The article Denotational semantics needs to focus on denotational semantics in general and not try to cover all the special case denotational semantics of Petri nets, (functional, sequential, object-oriented, and logic) programs, process calculi, Actors, etc'. However, it is perfectly reasonable to have specialized subarticles for the denotational semantics of these special cases.
Regards, --Carl Hewitt 07:15, 12 January 2006 (UTC)

[edit] Question about full abstraction

I've always understood full abstraction of some denotational semantics as: two 'programs' are observationally equivalent (wrt some assumed operational semantics) iff they have the same denotation. Am I wrong to think this and is the definition something else in general, or is the current definition just plainly wrong? -- Koffieyahoo 12:23, 9 January 2006 (UTC)

Usually it's expressed in the stronger one-sided form: program A ≤ B iff [[A]] ⊆ [[B]]. (That is, B observationally improves on A just when [[B]] denotationally improves on [[A]].) Which implies the two-sided form you give.) Some authors use operational improvement instead of observational — if your setting is a pure functional language this choice doesn't make any difference.
That's how I always understood it, and it's the definition used by Milner, Pitt, Gordon, Winskel, Abramsky, etc. The article may be groping towards that idea in its "distinguishability" criterion, but it's expressed very oddly. The "constructivity" idea may be groping towards some idea of the kinds of objects we want to allow in our semantics. Certainly none of the three terms in the article is at all usual in the field. Gdr 13:33, 9 January 2006 (UTC)
Ah, okay then we agree and I now also understand the text in the article: This is just the discussion of what a 'good' fully-abstract model should look like (e.g. in the context of PCF). You usually what your fully-abstract model to satisfy certain additional properties. (See, e.g., the discussion in the context of PCF, where Milner showed that a fully-abstract model exists, and where they kept looking for fully-abstract models that satisfied certain additional properties, which eventually lead e.g. to game semantics for PCF.) -- Koffieyahoo 14:16, 9 January 2006 (UTC)
All of the above would be excellent matrial for a new article on Denotational semantics of functional programs!
In the meantime the reporting in the article is roughly in accord with recent published work on denotational semantics for concurrent systems. (See references in article.)
Regards, --Carl Hewitt 22:12, 9 January 2006 (UTC)
I could just as well claim that everthing on denotational semantics of concurrency should go in Denotational semantics of concurrency and that this article should be devoted to denotational semantics of functional programs. So, this attitude is getting us no where. -- Koffieyahoo 10:40, 10 January 2006 (UTC)
We have at least four special cases of denotatioal semantics for programming languages already: denotational of semantics of functional, sequential, object-oriented, and logic programs. Also we will eventually need to treat the denotational semantics of Petri nets. And none of the previous address the issues of denotational semantics for general systems. General systems are concurrent systems. --Carl Hewitt 04:59, 11 January 2006 (UTC)
Really, you understand the definition in the article? I certainly don't. I can see what it ought to be saying, but all the content has been abstracted away. Unless you already knew what full sbtraction was, I don't think you'd understand it. Gdr 14:30, 9 January 2006 (UTC)
Now that you have some insight, please make some suggestions for improvement. After all, this is the Wikipedia ;-)
Regards, --Carl Hewitt 21:34, 9 January 2006 (UTC)
Yup: rip the current stuff out and replace it by the definition Gdr gives above and possible add some text to the PCF atricle explaining why they kept looking for a fully abstract denotational semantics after one had already been found by Milner (if something like that isn't already there). -- Koffieyahoo 10:40, 10 January 2006 (UTC)
In the head article denotational semantics can we justifiy treating only the denotational semantics of the lambda calculus? What about the denotational semantics of sequential, object-oriented, and logic programs? Of course there are a few concurrent programming languages with denotational semantics of long standing as well, e.g., Communicating Sequential Processes ;-)
Regards, --Carl Hewitt 17:49, 11 January 2006 (UTC)

An important part of full abstraction is the "abstract" bit: you only have full abstraction if the mathematical structuress you are using on the denotational side are sufficiently abstract: in particular the structures must not be derived from or be an expression any operational semantics (else full abstraction would be trivial). The 'survey' article by Luke Ong in the handbook did important work in establishing the modern view on what is meant by abstractness for the purposes of PL semantics. --- Charles Stewart 11:16, 11 January 2006 (UTC)

Hi Charles,
You have a good point. It turns out that consideration of full abstraction for systems more general than the lambda calculus requires considerable subtlety. See the comment above by Allan McInnes on approaches to denotational semantics for Communicating Sequential Processes.
Regards, --Carl Hewitt 11:19, 12 January 2006 (UTC)
I agree with the need for the article to cover more than just the lambda calculus and similar formalisms, in particular when we talk about concurrency. However, from the point of view of keeping a core computer science article accessible, it would be nice if so far as is possible the article avoids assuming technical knowledge beyond a very basic grasp of lambda calculus and order theory: in particular as far as possible we should illustrate points about concurrency using nondeterministic operators. --- Charles Stewart 18:40, 12 January 2006 (UTC)

[edit] Development plan for this article

This article (Denotational semantics) needs a growth plan because we cannot reasonably report on the literature in one article. This article should be about denotational semantics in general (not one particular denotational semantics) reporting on principles and methods that are common to all the approaches to denotational semantics.

So I have some concrete suggestions for this article:

  1. The current treatment of Clinger's model should be abstracted into principles and methods in this article and a new article on the denotational semantics of Actors should be created for the details about Actors.
  2. In due course, new articles should be created for the specialized denotational semantics of Petri nets, (functional, sequential, object-oriented, and logic) programs, process calculi, etc.
  3. There should be some general reporting of the approaches of traces, etc. in CSP, the scenarios of the Actor model, testing regimes, etc.
  4. The relationship to model checking should be reported.

More suggestions are greatly appreciated.

What do you think?

Thanks, --Carl Hewitt 17:59, 12 January 2006 (UTC)

I think this sounds fairly reasonable, although I'd amend point 3 to include "general reporting" on approaches for things like functional programming too. I'd also like to suggest that instead of using functional programming or the Actors model as the source of examples for the essential principles of denotational semantics, we consider using something simple and less likely to cause conflicts (such as the arithmetic expressions used in the denotational semantics section of this article). This has the advantage of being more accessible to a general audience, and less likely to generate arguments like the current ones. Of course, such a simple system may not be sufficient to expose all of the issues in question. But that provides a nice gateway to describing the denotational semantics of more complex systems such as PCF or Actors, the problems they introduce, and the techniques used to resolve them. --Allan McInnes 18:15, 12 January 2006 (UTC)
You make a good point about including functional programs in 3.
I like the idea of beginning with an example on arithmetic expressions. However, I would like to see something simpler than the approach in the article "Introduction to Full Abstraction" by Alan Jeffrey and Julian Rathke which you linked to above. The Jeffrey and Rathke article has several complications for the purposes of this Wikipedia article including the following:
  • A simple kind of classical nondeterminism is built into the semantics so that the denotation of an identifier takes a whole set of possible values (presumably finite?).
  • The operational semantics used in the article is based on global states which is OK for simple sequential programs but problematical elsewhere.
  • The computational domain used in the article is OK for simple sequential programs but not general enough for other cases.
So it may be that we need an approach for our initial introduction that is both simpler and more general than what is in this article.
Regards, --Carl Hewitt 05:55, 13 January 2006 (UTC)
There being no objections, at the suggestion of another editor, I am going to proceed to begin to carry out the development plan. --Carl Hewitt 18:48, 16 January 2006 (UTC)
I agree that the nondeterminism of the Jeffrey/Rathke model is needlessly confusing. I think using a more general computational domain makes sense, so long as it is indeed simpler as well. The important thing to keep in mind (in my opinion) is that this article should be accessible even to people with a limited background in theoretical CS. Examples, should be simple, clear, and readily understood without requiring detailed knowledge of things that are not fairly well-known by the average reader. As a result, I would favour a less general computational domain (particularly for early examples) if it made the article more easily accessible to lay readers. --Allan McInnes 19:00, 16 January 2006 (UTC)
Allan, Thanks for your comments. I have started an initial series of edits to carry out the plan. Please make suggestions for improvement. --Carl Hewitt 20:42, 16 January 2006 (UTC)

[edit] Please cite sources!

Please cite sources for the material in this article! Anonymouser 11:36, 10 April 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../d/e/n/Talk%7EDenotational_semantics_075d.html"