Talk:Denotational semantics/Archive 2

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)

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.

• "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.

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): [1], [2], [3], [4], [5], [6].

--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 [7].

-- 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)

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)

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)