Talk:Denotational semantics/Archive 3

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)

I have made some more changes along the lines proposed above. I hope I have not upset anybody. I think this article now describes denotational semantics in a general setting, with links to follow if the reader wants to know more about specific styles.

Please comment here if my changes were unwelcome, and we can discuss any reverts.

The article still needs some work. The section on concurrency is currently particularly bad. There is plenty of work on denotational semantics for concurrency that doesn't use process algebra or actors. For instance, there are recent game semantic treatments of concurrency, and Glynn Winskel has been progressing on a 'Domain theory for concurrency' programme for some time now. I don't have time to fix this now. Sam Staton 19:28, 4 July 2007 (UTC)

Sam, thanks for your contributions. It might be better to move Derivation of Scott Continuity from Actor Semantics back into the main article for reasons of generality and continuity because it is on the main path of the evolution of the fundamental concepts of denotational semantics.--71.198.217.123 15:15, 5 July 2007 (UTC)

Hello, I don't understand your reason for moving this back. This section is nothing more than an aside. Advanced readers might value this observation, but this section is in no way crucial to the understanding of denotational semantics. I don't understand why you say it is on the main path: people understood the meaning of continuity long before 1977. I have read several standard textbooks on the subject and I have never seen this observation before.

I know very little about actor semantics (but I know quite a lot about denotational semantics in general) so perhaps I am missing the crucial point of the section. If so, I apologise. It is likely that many others are in the same boat, and it would be very good if you could rewrite the section without the actor-specific terminology.

Please remember that this article is an article about denotational semantics in general. It is not an article about actor semantics or the relationship between actor semantics and Scott domains. Many books and articles have been written about denotational semantics without reference to actors, and the present article should surely serve as a reference for readers of such things. Sam Staton 16:37, 17 July 2007 (UTC)

Sam, thanks for your question. Continuity is the fundamental assumption behind Scott's development of denotational semantics. Consequently, it is important that this fundamental assumption can be derived from principles that are even more fundamental. Therefore, the derivation of the continuity criterion belongs in the mainline thread of the history of the subject. Unfortunately, many researchers were unaware of concurrent computation (the general case) and consequently only studied special kinds of computation, e.g., sequential and parallel computation. However, concurrency has now become mainstream and consequently many articles are being published about the Actor model.--71.198.219.183 17:07, 17 July 2007 (UTC)

Thank you for your explanation. I agree that continuity is fundamental. As to which principles are even more fundamental, surely this is a matter of debate, and dependent on personal opinion and point of view.

Historically, in models of concurrency, Actors were based on physics whereas the process calculi were based on algebra.--71.198.219.183 20:46, 17 July 2007 (UTC)

I am sure that you would not assert that one cannot understand denotational semantics without understanding actors. For this reason I maintain that the reader should be able to read the whole article without knowing anything about actors. I think this is true of the article EXCEPT for the section we are discussing.

It's probable that One cannot understand general denotation semantics without any understanding of concurrency. However, it is a good idea to understand process calculi as well as Actors.--71.198.219.183 20:46, 17 July 2007 (UTC)

I still do not understand the section at all, though I would like to. eg. what is immediate-descendents?

It seems to me that there are two ways forward. One is to expand the section by explaining it in a self-contained way, without assuming familiarity with actors. This would probably lead to a disproportionately long section, and so should be an article in its own right, referenced from the main page of course.

I have tried to make the article more self-contained. Please make suggestions for improvement.--71.198.219.183 20:46, 17 July 2007 (UTC)

The other possibility is that these remarks can only make sense to someone familiar with the actor model, in which case they should surely be included on a separate, actor-specific page.

What do you think? Sam Staton 19:06, 17 July 2007 (UTC)

Thank you, that is better and a little less biased. (By the way, I take it you are Carl Hewitt? why not sign in?)

In the list of properties of domains, I have taken out the definition of finite element and included a link to the article about them instead. One does not need to know precisely what finite elements are in order to understand the essence of denotational semantics.

Can anyone explain what is meant by the sentence "domains should be downwards closed"? If not I will remove it. I'm not quite sure what this list is for anyway, when there is a special page on domain theory. Sam Staton 16:04, 18 July 2007 (UTC)

Good point. Why don't you try integrating the list into the article on domain theory. The terminology that you quote is defined in Clinger's thesis.--71.198.220.87 02:22, 21 July 2007 (UTC)

Hi. I think all these properties do already appear in the domain theory article. Shall we just delete them from here, and leave a reference, or a sentence "A domain is typically a complete partial order, possibly subject to additional properties." Sam Staton 15:52, 23 July 2007 (UTC)

PS. wrt "downwards closed", it's not in the defn of domain on page 62 of Clinger's thesis (which, by the way, I have just started reading, and am enjoying). I know what is meant by a downclosed subset of a partial order, but these "domains" are not subsets of any particular universe. Sam Staton 15:52, 23 July 2007 (UTC)

One other little thing. I'm not sure that the average reader needs to know about a bug in the Hewitt-Baker paper. I am thinking of removing the parenthetical remark and instead including (see e.g. Hewitt and Baker [1977], Clinger [1981]) in the introductory sentence. Do you think this would be appropriate?

A reader reader following the Wikipedia reference to the paper should be warned because they probably won't think to look in Clinger's thesis for the correction. Maybe put it in a footnote?--71.198.220.87 02:22, 21 July 2007 (UTC)

I am also thinking of moving the section on "Fixed point semantics" to lower down the page, because certain other notions, e.g. full abstraction and compositionality, are arguably more central to denotational semantics in general. Would this be sensible?

Fixed points semantics is arguably the heart of denotational semantics since it leads directly to the the Representation Theorem and its applications. Full abstraction is a rather vague notion that is badly in need of further development, especially for concurrency. Compositionality is ambiguous and controversial. However compositionality of programming language semantics seems clear enough.--71.198.220.87 02:22, 21 July 2007 (UTC)

Sam Staton 18:34, 19 July 2007 (UTC)

Please cite sources!

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

Reworked article

I have now reworked the article in the hope that it is now quite informative to the unfamiliar reader. I have tried to incorporate the ideas of other contributors, even if I have edited the original text. I have tried to keep the article short and to the point. My intention was to give a broad overview of denotational semantics, and an overview of Scott-style semantics. The article now roughly outlines a typical undergraduate course on the topic, with plenty of extra links and references to related articles.

I hope no-one objects to my reworking. My intention was to make the article clearer. I did not mean to offend anyone. If you are upset, please can we discuss here rather than undo-warring? I will check often. Sam Staton 19:36, 24 September 2007 (UTC)

It certainly is in a much better state than a year and a half ago when I last looked at it.--CSTAR 19:51, 24 September 2007 (UTC)

I agree with CSTAR. I hadn't looked at this article in a long while, and have been pleasantly surprised at the improvement. Nice work, Sam! --Allan McInnes (talk) 03:46, 12 November 2007 (UTC)

Thank you! I have now added a section about other language features. Please add a paragraph to that if there is a language feature missing. My intension was that each paragraph should be kept brief. If an editor feels like writing more about a topic, I recommend starting a new article for that purpose.

The bibliography is now very long. I have put a separate list of four basic texts so that the interested novice will not be too bewildered to read further.

PS to 67.188.207.19 (=CH?): I deleted the comment about concurrency being really important from the first paragraph. All the language features that are listed are important for modern computing, and I don't think this is the place to explain why. We can discuss here if you like. Sam Staton 18:52, 25 September 2007 (UTC)

Unfortunately, you seem to have an outmoded perspective. Concurrency is the general case. Why do you think that all of the leaders in the field turned their attention to concurrency beginning in the early 1970s? Every aspect of programming languages now has to be considered in the light of concurrency.67.180.231.39 21:01, 27 September 2007 (UTC)

An anonymous editor (=Carl Hewitt?) has reverted some of my changes and made the article more point-of-view. I have taken actions against this.

In accordance with Wikipedia traditions, you would have been better advised to work with the contributions of the other editors rather than revert them since the changes that you have imposed are quite retrogressive.67.180.231.39 21:01, 27 September 2007 (UTC)

My reasons are as follows.

1. The anonymous editor seems to think that domain theoretic models only work for functional languages. This is completely untrue, as any textbook will tell. One can give a fairly conventional domain-theoretic denotational semantics to Java-like languages; see for instance the recent work of Bernhard Reus.

Please provide a reference to the work of Reus. Of course you are aware that Java is a concurrent programming language. Consequently, for Java, a denotational semantics based on computations as mathematical functions, as in the original work of Scott and Strachey, is entirely inadequate.67.180.231.39 21:01, 27 September 2007 (UTC)

2. I think the editor believes that concurrent computation is the most interesting and important subject to study.

It's a generally accepted scientific fact that concurrency is the general case and this needs to be clearly stated in the article. As I mentioned above, every aspect of programming languages now has to be considered in the light of concurrency.67.180.231.39 21:01, 27 September 2007 (UTC)

Hang on there. The 'general case' doesn't have such standing in an article devoted to a particular topic. In mathematics, a field is a a special case, a ring is a more general case. That doesn't mean that 'rings are more general' has any need to be stated in some article relating to the theory of fields. Anyway, the argument is not well formed. Concurrent computation is not more general than computation using a Turing machine, in a strictly limited sense. It just happens to be useful, which a Turing machine isn't. So engineers will ignore Turing machines, rightly. On the other hand, denotational semantics isn't engineering, either. It is a distinctive way of setting up mathematical, computational models. So please can we have regard to the needs of the encyclopedia? Charles Matthews 18:15, 29 September 2007 (UTC)

Concurrent programs are strictly more general than both sequential programs and functional programs. For example a concurrent program can have the property of unbounded nondeterminism which is not possible for sequential and functional programs. In particular a nondeterministic Turing machine has the property of bounded nondeterminism [Plotkin 1976].

Consequently, the general subject matter of denotational semantics is concurrent computation.--67.180.231.39 04:57, 30 September 2007 (UTC)

See my comments below.Sam Staton 09:43, 30 September 2007 (UTC)

This is a point of view. Many people have devoted significant amounts of time to denotational semantics of other aspects of programming languages. Many people continue to devote time to difficult questions in these other areas. In my revision, I have included yet more examples of different research directions in denotational semantics. These deserve equal mention.

I have removed sentences from the introduction such as In this way, domain theory has been made to apply to the general case of concurrent computation. because they are pushing a point of view.

It may be that the history of denotational semantics illustrates the "unreasonable effectiveness of mathematical abstraction." Scott and Strachey set out model computations as mathematical functions. Then Scott developed domain theory to model these functions. However, it turned out that because of concurrency, computation cannot be adequately modeled as mathematical functions. Nevertheless, researchers were able to adapt domain theory to model general concurrency by considering more general domains. Thus although the first part of what Scott and Strachey were attempting was limited for technical reasons, the second part was an enormous success even though Scott never took any interest in concurrency!67.180.231.39 21:01, 27 September 2007 (UTC)

I was also concerned by sentences such as However, this approach [to state] doesn't work very well for concurrency since because of issues of unbounded nondeterminism.

There is a whole history of the field of denotational semantics of which you do not seem to be aware. In fact, much of this history is told in the "Other references" section of the article where you will find that the issue of unbounded nondeterminism played a crucial role in the development of modern denotational semantics. And indeed, the nondeterministic global state approach ran into trouble because of the issue of unbounded nondeterminism.67.180.231.39 21:01, 27 September 2007 (UTC)

Firstly, this was placed in a section that is not about concurrency. Secondly, the sentence is a negative, very critical assertion, doesn't explain the problem. Thirdly, it is not necessary to detail all the little pros-and-cons of all the little parts of this article. The article would become ridiculously long if we included balanced arguments for all the little fors-and-againsts. I assert that they thus should be omitted, or moved to separate pages.

Please do not revert my changes without explaining or discussing here first. That is rude.

It was also rude of you to retrogressively revert the constructive contributions of the other editors. My suggestion is for you to restore their work, try to understand it in consultation with experts such as Robin Milner and Tony Hoare, and then try to proceed constructively.67.180.231.39 21:01, 27 September 2007 (UTC)

A respected academic (such as Carl Hewitt) has a right to a point of view, and has a responsibility to share it. I would love to know more about your opinions and predictions. Maybe you would like to visit Cambridge (UK) some time. Wikipedia is not a forum for this; we must find somewhere else. Sam Staton 19:22, 27 September 2007 (UTC)

Dear Carl (?), thank you for your response to my message.

I was sorry to read that you think I have ignored your previous constructive contributions. My intention was simply to clarify the article and remove the bias that it had. To this end I was acting largely based on the "action plan" that you proposed above. After my initial edits, I explained this on the discussion page. I understand from CSTAR that he found my changes helpful.

I was also worried by your suggestion that I was skewed. I have tried to address this point in the section below.

I would like to move forward, and see the article further improved. Following your comments and our disagreemets I think it is best if we agree changes here before making them. Here are some changes I am proposing to make.

• There should be a short subsection on the "denotational semantics of sequentiality" in the second section of the article. This would point the reader to game semantics models.

• The section on semantics of concurrency should be extended to include a few short examples of how language constructs are denoted in some of the models.

Please let me know whether you think these changes are appropriate. Sam Staton 16:44, 28 September 2007 (UTC)

Neutral point of view in this article

I was very concerned to read that an anonymous editor thought my view might be skewed in my understanding of denotational semantics. My intention was (and is) to remove bias from the article. To investigate this, and reassure myself, I wanted to know what the average computer science graduate knows about denotational semantics. I searched, using Google, using the term "denotational semantics course". This led me to syllabuses of various courses from the following universities, around the world.

Yale, US; Cornell, US; Rhode Island, US; Dallas, US; Iowa State, US; CMU, US; Grinnell, US; Walden, US; Queen's, Ontario, Canada; Liverpool, UK; Cambridge, UK; Edinburgh, UK; Midlands, UK; Nottingham, UK; Munich, Germany; Aachen, Germany; Linz, Austria; Nijmegen, Netherlands; Uppsala, Sweden; KTH, Sweden; Porto, Portugal; Victoria, New Zealand; Tohoku, Japan; Bombay, India

(I can provide urls if you are interested.) I was shocked, as you may be, to find that not one of these syllabuses mentioned denotational semantics for concurrent programs. From this I deduce that the average graduate would understand the phrase "denotational semantics" as primarily referring to the Scott-Stratchey denotational semantics of sequential programs, and would regard other extensions and programming features (including concurrency) as rather advanced subject matter.

Hopefully graduate students are not in general as naive as you suppose ;-) A typical graduate should know that the approach that you have described above is entirely inadequate. Instead they should have sense enough to ask their professors and to consult the scientific literature. (Have your read the references that are cited in the article?)207.47.11.2 23:56, 28 September 2007 (UTC)

In conclusion, I am not skewed. My view represents the view of the general population.

Admittedly, we still have a large education job ahead of us ;-)207.47.11.2 23:56, 28 September 2007 (UTC)

You write "It's a generally accepted scientific fact that concurrency is the general case". It is not clear what you mean by "concurrency is the general case".

The statement means among other things that concurrency is a framework of computation that encompasses the special cases like functional and sequential computation.207.47.11.2 23:56, 28 September 2007 (UTC)

Could you clarify, and perhaps find some evidence? I strongly believe that concurrency is an interesting and important topic for research.

You seem not to have heard that there has been a revolution to massive concurrency that has been going on for some time now. This revolution has been extensively reported and discussed in both the general press and the scientific literature. See the one below and many subsequent examples:

http://hewitt-seminars.blogspot.com/2006/06/ultraconcurrency-revolution-in.html207.47.11.2 23:56, 28 September 2007 (UTC)

But statements like this devalue the current work of many active researchers. I give some examples.

• If the world is only interested in concurrency

Of course the world in interested in other things besides concurrency ;-) But you missed the point that concurrent computation is the general case.207.47.11.2 23:56, 28 September 2007 (UTC)

, then why did Abramsky, Hyland, Ong, and others carry out a detailed study of sequentiality, through the 1990s? I think you would write-off their work as pointless. This is a valid opinion, but it is clearly not an opinion that is generally held, and certainly not held by the authors of that work, so cannot be reported in wikipedia.

Sequential computation remains a suitable subject for research. However, in this day and age, sequential computation needs to be studied in the context of concurrent computation.207.47.11.2 23:56, 28 September 2007 (UTC)

• You remark that "Scott never took any interest in concurrency". We can't have the wikipedia article denouncing the work of one of the greatest computer scientists!

The statement that "Scott never took any interest in concurrency" is not an insult. Any single researcher cannot work on everything ;-) So Dana pursued his interests in other areas where he did excellent work.207.47.11.2 23:56, 28 September 2007 (UTC)

• For another example: the work of Reus (see main page for a reference, by the way) is based on domains. You believe, I think, that this approach is ridiculous, because concurrency won't be modelled right there.

The work that you deleted from the article on denotational semantics of concurrency is also based on domains (all be it more sophisticated domains than those required for functional programs). So concurrency can certainly be modeled correctly using domains.207.47.11.2 23:56, 28 September 2007 (UTC)

(Incidentally, sequentiality won't be modeled quite right either.) In this case, why are Reus and Streicher, two acclaimed denotational semantics researchers, wasting their time with it? Why did the referees and editors of world-class journals accept their articles?

"How science works in practice" is a fundamental area of research in its own right with a large literature by notable researchers including Michel Callon, Paul Feyerabend, Elihu M. Gerson, Mark Johnson, Thomas Kuhn, George Lakoff, Imre Lakatos, Bruno Latour, John Law, Susan Leigh Star, Anselm Strauss, Lucy Suchman, Ludwig Wittgenstein, etc. You might begin by reading the following:

Bruno Latour (1987) Science in Action: How to Follow Scientists and Engineers through Society Harvard University Press.207.47.11.2 23:56, 28 September 2007 (UTC)

In summary: the wikipedia page cannot assert that "semantics of concurrent languages is the most important area".

I agree that a Wikipedia article should not make personal value judgments of the kind that you quote above. It should stick to generally accepted facts such as "Concurrent computation is the general case." Do you see the difference?207.47.11.2 23:56, 28 September 2007 (UTC)

This is not a universal view, and it devalues the current work of many active researchers.

Since you evidently are in Cambridge, you would do well to consult Robin Milner and Tony Hoare about the issue of the fundamental nature of concurrency. 207.47.11.2 23:56, 28 September 2007 (UTC)

Look, please note well that dropping on people from a great height is not an acceptable way of arguing in Wikipedia. If you have references to quote, please bring them forward. Name-dropping is not going to move the discussion forward. Charles Matthews 18:19, 29 September 2007 (UTC)

The suggestion to consult with Robin and Tony was meant as a constructive suggestion and has been taken in that spirit. (See below).--67.180.231.39 21:51, 29 September 2007 (UTC)

Whoever is right or wrong, I don't think this should be causing major problems. One editor wants to include statements that other editors claim introduce a particular point-of-view to the article. The only solution is to omit such statements unless all editors can be convinced that the statements are factual. Sam Staton 16:44, 28 September 2007 (UTC)

The issue on point-of-view seems to be your limited perspective. Again, I would recommend reading the literature and consulting with Robin and Tony.207.47.11.2 23:56, 28 September 2007 (UTC)

Dear Carl, thank you for your response to my comments. I was pleased to see that your views are less extreme than I had first thought. Thank you also for the references to Latour's book and to your own seminar. I will look for the book in the library this week. And I think I would have enjoyed your seminar.

I want you to know that I am very interested in concurrency, and it is my opinion that concurrency is a fascinating and important field. I am also of the opinion that researchers and students of denotational semantics should take more notice of concurrency phenomena. I know Robin and Tony, yes; I expect that they both sympathize with these views. I would not be surprised if the computer science community, as a whole, held these views, as a criticism of the denotational semantics community (although I have no evidence for this).

But this article is about "denotational semantics". It has to reflect what the general population understands by that term.

Most importantly, the article should reflect the best current generally accepted scientific understanding of Denotational Semantics. Surveys of the opinion of the general population should be left to social scientists who are competent in these matters.67.180.231.39 17:00, 29 September 2007 (UTC)

For this, my survey of university syllabuses is the best evidence we have.

Unfortunately, your survey of university syllabuses is deeply flawed as the basis for judging the current generally accepted scientific understanding of Denotational Semantics.67.180.231.39 17:00, 29 September 2007 (UTC)

The focus that denotational semantics should ought to have is a different matter, even if it comes from opinions of world leaders.

I agree that the article should not delve into what Denotational Semantics ought to be. Instead it should focus on what is the generally accepted scientific understanding. Do you see the difference?--67.180.231.39 17:00, 29 September 2007 (UTC)

The article becomes biased if it singles-out one particular research direction as "most important".

I agree that personal value judgments as to which research direction is "most important" should not be part of the body the article. However, it is a mathematical theorem of the denotational semantics of the Actor model that functional programs, sequential programs, etc. are special cases of concurrent programs. Consequently, concurrency is the general case.67.180.231.39 17:00, 29 September 2007 (UTC)

(In any case, the report of Milner and Hoare at http://www.ukcrc.org.uk/gcresearch.pdf suggests that there are other important issues for the modern world, such as trust, that people need to start investigating from a semantic perspective.)

Good point. There is more to the semantics of computational systems than denotational semantics.67.180.231.39 17:00, 29 September 2007 (UTC)

(As another aside: There are many people working on the subject of concurrency theory. But only a small proportion of those people are explictly and actively working on denotational semantics.)

Moving forward, I suggest the following changes. My intention is to transform the article to a state where neither of us finds it biased.

• The section on semantics of concurrency should begin with a statement like

Concurrency has increased in importance, motivated in part by the massive concurrency in Web services and Multi-core computer architectures. Concurrency is regarded by many as a general situation within which functional and sequential programming languages can be studied.

Rather than state a matter of opinion, it would be better to refer to the facts of the matter: Functional and sequential programs are special cases of concurrent programs.67.180.231.39 17:00, 29 September 2007 (UTC)

(Vague phrases such as "concurrency is the general case" are best avoided in favor of more precise ones, surely. To me, that phrase indicates that "concurrency subsumes polymorphic data types", a sentence that does not make sense.)

Actually, polymorphic data types are an important area of study for concurrent programming. In particular there are some subtle issues in avoiding timing errors when using polymorphic data types in libraries.67.180.231.39 17:00, 29 September 2007 (UTC)

• The third introductory paragraph of the article could contain the (something like) following statements.

The first section of this article is primarily concerned with the traditional approach to denotational semantics for recursive programs. This approach needs considerable revision to deal with some important aspects of modern programming languages such as concurrency, sequentiality, and local state. These issues are treated briefly in the second section of this article.

Unfortunately, the above proposal is still somewhat muddled. We need a forthright statement that concurrency is fundamental.67.180.231.39 17:00, 29 September 2007 (UTC)

• You said above that I removed something factual from the section on semantics of concurrency. I apologize: My intention was only to remove bias from the article. I have looked through the history, and I cannot find what you are talking about. Please could you be more specific? because this should probably be remedied.

You deleted the following paragraphs:

The first denotational model of true concurrency was developed for the Actor model based on a power domain of an incomplete domain actor event diagrams [Clinger 1981]. Subsequently a simpler model was developed based on a power domain of the complete domain of timed event diagrams [Hewitt 2006].

The first denotational semantics developed for CSP in [Francez, Hoare, Lehmann, and de Roever 1979] was given in terms of traces: a program is denoted by the set of traces that it is capable. However this model had the property of bounded nondeterminism and consequently did not have the property of true concurrency as pointed out in [Clinger 1981]. However, the subsequent model of CSP does embody true concurrency [Roscoe 2005].--67.180.231.39 17:00, 29 September 2007 (UTC)

• I would also like to know whether you think my other two change-proposals, in the previous section, are appropriate.

With best regards, Sam Staton 11:30, 29 September 2007 (UTC)

Carl, I am glad we are agreeing on some things now.

I have some responses to your responses to my change proposals, though.

1. You want to include the statement "Functional and sequential programs are special cases of concurrent programs." in the section on semantics of concurrency.

Yes, it is a theorem of the denotational semantics of the Actor model that functional and sequential programs are strict special cases of concurrent programs.--98.207.43.10 01:36, 1 October 2007 (UTC)

This statement might be appropriate in the article on Programming Languages.

Actually, since it is about denotational semantics, the statement is more appropriate for this article.--98.207.43.10 01:36, 1 October 2007 (UTC)

Well, it is a statement about your particular semantics in the actor model. (It cannot be a fully abstract semantics, so some would argue it is not very interesting.) Sam Staton 11:00, 1 October 2007 (UTC)

You may not be aware that currently there are two major frameworks for concurrency centered around the Actor model and process calculi. Of course, it turns out that Functional and sequential programs are special cases of concurrent programs. in the process calculi as well.

Let's be clear: those two frameworks are not the only current frameworks for concurrency.

The statement to which you refer did not say that the Actor model and process calculi are the only current frameworks for concurrency. However, they currently are by far major ones.--171.66.50.31 22:47, 2 October 2007 (UTC)

I'm not sure what "by far major" means. Just in case you meant "by far the most major": I know plenty of people using event structures, petri nets, and then there are Robin Milner's bigraphs... Sam Staton 09:21, 3 October 2007 (UTC)

It seems that development of denotational semantics for the Actor model and process calculi is much further along than for Petri nets and bigraphs.--171.66.51.82 22:53, 3 October 2007 (UTC)

Yes: Functional and sequential programs are special cases of concurrent programs in the pi-calculus when "special cases" means "can be encoded into while retaining some properties". Sam Staton 09:53, 2 October 2007 (UTC)

It would be more accurate to say that functional and sequential programs can be straightforwardly encoded in the pi-calculus retaining essentially all important properties.--171.66.50.31 22:47, 2 October 2007 (UTC)

I'm happy with "functional and sequential programs can be encoded in the pi-calculus retaining essentially all important properties." (But how straightforward it is is a matter of opinion.)

Also, you may not be aware the the concept of being "fully abstract" is currently not very well defined and therefore the subject of controversy.--98.207.43.10 16:12, 1 October 2007 (UTC)

I'm not aware of any controversy about the concept of full abstraction for sequential languages. Sam Staton 09:53, 2 October 2007 (UTC)

Of course, the statement to which you refer means that The concept of full abstraction is controversial for concurrent systems including programming languages.--171.66.50.31 22:47, 2 October 2007 (UTC)

With respect to denotational semantics, it is too imprecise: what is meant by "are special cases of"? In many interpretations, the statement is wrong.

Most readers of the article are not that naive.--98.207.43.10 01:36, 1 October 2007 (UTC)

I honestly don't understand what the non-naive interpretation is. I first understood it as the (wrong) meanings below. Sam Staton 11:00, 1 October 2007 (UTC)

Again, I recommend reading the literature in the references to the the article. It's not so difficult to understand.--98.207.43.10 16:12, 1 October 2007 (UTC)

It is not the case that "denotational semantics of sequential programs is a special case of denotational semantics of concurrent systems".

Sorry, it is the case that the denotational semantics for sequential programs is a special case of denotational semantics for concurrent systems.--98.207.43.10 01:36, 1 October 2007 (UTC)

Then I don't know what you mean by "special case".

Since you are at Cambridge, I suggest that you consult with Glynn, Robin, and Tony to get some perspective on these matters.--98.207.43.10 16:12, 1 October 2007 (UTC)

It is not the case that "denotational semantics of parametric polymorphism is a special case of denotational semantics of concurrent languages".

You're right. The above sentence is nonsense.--98.207.43.10 01:36, 1 October 2007 (UTC)

It may be the case that "denotational semantics of parametric polymorphism is a special case of denotational semantics of parametric polymorphism in concurrent languages". But one can study polymorphism without studying concurrency, and vice versa.

Yes, but in this day and age, it only makes sense to study polymorphism in the context of concurrency for the reasons mentioned earlier.--98.207.43.10 01:36, 1 October 2007 (UTC)

Now you are saying that other people's current work does not make sense. That can only be opinion.Sam Staton 11:00, 1 October 2007 (UTC)

These days, who is working on polymorphism outside the context of concurrency? Researchers working on polymorphism for functional languages have to be concerned that the functional programs will execute in a larger concurrent environment.--98.207.43.10 16:12, 1 October 2007 (UTC)

One example: Rasmus Ejlers Møgelberg, Alex Simpson: Relational Parametricity for Computational Effects. LICS 2007: 346-355.

It is not the case that "given a denotational semantics for a sequential language L1, there is a concurrent language L2 whose syntax contains that of L1, and a denotational semantics for L2, such that denotational equality for L1 coincides with denotational equality for L2". This is an important point: contextual equivalence for PCF is different from contextual equivalence for PCF + parallel or. So, you see, one has to be careful.

Parallel or does indeed add computational power. See

• Mike Paterson and Carl Hewitt (1970) Comparative Schematology MIT AI Memo 201. August 1970.--98.207.43.10 01:36, 1 October 2007 (UTC)

It might be the case that "there is a functional programming language L1 that can be given a denotational semantics in the actor model, and there is a concurrent language L2, that contains the syntax of L1, and that also has denotational semantics in the actor model such that denotational semantics from L1 is preserved".

If you can think of a more careful wording that takes into account the above, please let me know. I can't think of anything better than my proposal above, right now.

Unfortunately, you have tied yourself in a bit of knot. It's best to simply state that the denotational semantics for sequential and functional programs is a special case of denotational semantics for concurrent systems.--98.207.43.10 01:36, 1 October 2007 (UTC)

I have ended up in a knot because I don't understand what you mean by "special case". As it stands I don't agree with the sentence. Sam Staton 11:00, 1 October 2007 (UTC)

What I have in mind are results like those in Sequential computations form an ω-complete subdomain of the domain of Actor computations. Of course the same kind of results can be be obtained in process calculi.--98.207.43.10 16:12, 1 October 2007 (UTC)

OK. I understand what you mean by "special case" in this context. So how about In the standard denotational semantics in the actor model, the semantics of sequential programs is a special case of the semantics of concurrent programs (with appropriate linking).

Unfortunately, this is far too narrow a statement. For example, in the reference below, it is shown how to embed functions in the process calculi:

• Davide Sangiorgi and David Walker. The Pi-Calculus: A Theory of Mobile Processes Cambridge University Press. 2001.--98.207.43.10 22:27, 1 October 2007 (UTC)

Right, how about In many studies of denotational semantics, the semantics of sequential programs is a special case of the semantics of concurrent programs. (NB my PhD thesis was on models of process calculi, and I was recently employed on a project called "domain theory for concurrency", so perhaps I know more than you think about that.) Sam Staton 09:53, 2 October 2007 (UTC)

More accurate would be In the Actor model and process calculi, the semantics sequential and functional programs are special cases of the semantics of concurrent programs.--171.66.50.31 22:47, 2 October 2007 (UTC)

How about "In many studies of denotational semantics, including those in the Actor model and pi-calculus, the semantics of sequential and functional programs are special cases of the semantics of concurrent programs".Sam Staton 09:21, 3 October 2007 (UTC)

Slightly better would be "In many studies of denotational semantics, including those in the Actor model and process calculi, the semantics of sequential and functional programs are special cases of the semantics of concurrent programs".--171.66.51.82 22:53, 3 October 2007 (UTC)

OK, I see, since one can probably do a similar thing for ambient calculus etc etc. How about "...and some process calculi". I'm not sure how sensible or elegant it is to encode a functional language into something like Milner's CCS. Or alternatively, "...and many ..." or "and most modern...". I don't mind. Sam Staton 17:02, 5 October 2007 (UTC)

2. You want to include the statement that "concurrency is fundamental" in the introductory paragraphs. Again, this sentence is too vague and by interpreting the sentence in different ways I can derive both facts, and erroneous statements, and also opinions.

It is not the case that "concurrency is fundamental in denotational semantics". In the current state of the subject, as it is taught in many universities, as it is researched by various people, as it is explained in textbooks on the subject, concurrency does not necessarily take a fundamental role.

Unfortunately, you have a very skewed perspective on the current state of the art. Your little survey is fundamentally defective in many ways. I suggest that you consult an expert in the sociology and anthropology of science about such matters. As usual, the textbooks are decades out date. Today, it would be very strange to teach a seminar course on denotational semantics at Berkeley, Cambridge, Carnegie, Edinburgh, MIT, Stanford, Oxford, etc. without covering concurrency.--98.207.43.10 04:35, 1 October 2007 (UTC)

Perhaps I am strange. I help to teach the course entitled "denotational semantics" at Cambridge (UK). Concurrency is not mentioned in that course.Sam Staton 11:00, 1 October 2007 (UTC)

What I had in mind by my comment was a full blown graduate level seminar course, which would be expected to be close to the state of the art. This is different from CST05 "Denotational Semantics" which is part of the Computer Science Tripos. One thing to note is that in this framework there are only 8 lectures. Another thing is that in this framework, it is important to have textbooks, which is a severe constraint that dramatically limits what can be covered.--98.207.43.10 16:12, 1 October 2007 (UTC)

OK. And of course Cambridge is only one example.

Perhaps I'm not sure what you mean by "fundamental". You haven't challenged my arguments below, so perhaps you agree with them. To recap: It is evidently possible to teach and research denotational semantics without studying denotational semantics of concurrency.

Certainly at the graduate level and above, it is currently a big mistake to teach and research denotational semantics without studying the denotational semantics of concurrency.--98.207.43.10 22:27, 1 October 2007 (UTC)

This is a statement of opinion. It classifiers a group of active researchers as making "a big mistake". But see [[1]].Sam Staton 09:53, 2 October 2007 (UTC)

The course to which you refer is an undergraduate course.

I see. Sorry, I'd followed a link from Theory Postgraduate Courses. Sam Staton 09:21, 3 October 2007 (UTC)

However, academia can sometimes move amazing slowly.--171.66.50.31 22:47, 2 October 2007 (UTC)

Perhaps, but unfortunately wikipedia has to reflect this. Academia is where denotational semantics is. Sam Staton 09:21, 3 October 2007 (UTC)

Even though some academics can lag far behind, this doesn't mean that the Wikipedia should be an extreme laggard. The Wikipedia needs to report on the full course of published work from the oldest to newest. Also, we need to recognize that more recent publications often supersede older ones which affects the current state of denotational semantics.--171.66.51.82 22:53, 3 October 2007 (UTC)

I agree. I think/hope the introductory paragraph that you proposed makes it clear that the first section is about the traditional and first work (that are often taught in courses, etc) and the second section is about more current topics. Sam Staton 17:02, 5 October 2007 (UTC)

So concurrency is not necessarily at the foundation of denotational semantics. Yes, concurrency is sometimes fundamental in denotational semantics. But that's probably too weak to be included. My other point was that it's biased to imply concurrency is more fundamental than other language features. Sam Staton 17:16, 1 October 2007 (UTC)

It's probably a mistake to think of concurrency as a language feature. After all, there are many language features having to do with concurrency, e.g., futures, message passing, etc. It's better to think of concurrency as the way that things are done now.--98.207.43.10 22:27, 1 October 2007 (UTC)

Perhaps concurrency refers to a class of language features.

Concurrency is more than just a class of features because the denotational semantics of concurrency impacts the denotational semantics of all features of a programming language.--171.66.50.31 22:47, 2 October 2007 (UTC)

I'm not sure that this argument is valid. Nobody ever said that combining features is easy. Sam Staton 09:21, 3 October 2007 (UTC)

The issue is not so much the combining of features as the use of more sophisticated underlying denotational domains.--171.66.51.82 22:53, 3 October 2007 (UTC)

I am happy to instead use the phrase aspect of programming language if you find it more neutral.Sam Staton 09:53, 2 October 2007 (UTC)

Unfortunately, "aspect" already has a technical meaning in programming languages.--171.66.50.31 22:47, 2 October 2007 (UTC)

I don't think the meanings of "aspect" will be confused in the following paragraph. I hope you find it palatable:

The first section of this article is primarily concerned with the traditional approach to denotational semantics for recursive programs. This approach needs considerable revision to deal with some important and fundamental aspects of modern programming languages such as sequentiality, local state, and the various features introduced for concurrency. These issues are treated briefly in the second section of this article. Sam Staton 09:21, 3 October 2007 (UTC)

How about Denotational semantics was first developed as a framework for functional and sequential programs modeled as mathematical functions mapping input to output. The first section of this article describes denotational semantics developed within this framework. Later sections deal with issues of polymorphism, concurrency, etc.--171.66.51.82 22:53, 3 October 2007 (UTC)

Yes, I'm happy with that. I'll change this in the article in a second. Sam Staton 17:02, 5 October 2007 (UTC)

One can study denotational semantics without studying concurrency; therefore concurrency is not fundamental.

(You may disagree with my argument here. If so, then, since you think one thing, and I think another, it is a matter of opinion and can't be included in the article.)

It may be the case that "concurrency is fundamental in modern computer science". I don't want to enter a debate about this, but note the "grand challenge" report that I quoted before suggests that there are other concepts that are perhaps even more fundamental in modern computer science. Anyway, I concede that the statement might be appropriate on a more general page about computer science, within a discussion about directions for computer science etc.

If we include this statement on this page, though, outside the context of a general debate, it gives the impression that concurrency is more fundamental than other issues, such as local state, polymorphic data types, etc., that many have been working on, and issues such as trust that people are only just starting to work on. I suggest, as a compromise, the following statement.

The first section of this article is primarily concerned with the traditional approach to denotational semantics for recursive programs. This approach needs considerable revision to deal with some important and fundamental aspects of modern programming languages such as concurrency, sequentiality, and local state. These issues are treated briefly in the second section of this article.

3. I didn't delete those paragraphs, I reformulated them in a way that was more neutral.

The paragraphs have been moved to the history article which is an more appropriate place.--98.207.43.10 01:36, 1 October 2007 (UTC)

I see that I inadvertently omitted the mention of power domains, which was perhaps wrong of me.

The history article will need to address the history of the development of power domains.--98.207.43.10 01:36, 1 October 2007 (UTC)

Could you propose a way to reinsert it in a balanced way? and preferably a way that makes sense to someone who has not already read your article?

The elements of bias that I removed from the paragraph include the following.

• There was an assertion that actor semantics was the "first denotational semantics of true concurrency". This statement is entirely unnecessary, irrelevant, unverifiable, and imprecise (since "true concurrency" is not defined here). Nowhere else in the article is it written which bits of work were "world firsts".

I agree that this discussion belongs in the history article where it is pointed out that denotational semantics originated first in the work of Scott and Strachey.--98.207.43.10 01:36, 1 October 2007 (UTC)

Also, Winskel's work (now cited) of around the same time was presumably fairly independent of Clinger's, so it is inappropriate to make precise temporal comparison.

Presumably this issue will be addressed by the editors of the history article.--98.207.43.10 01:36, 1 October 2007 (UTC)

• The paragraphs criticized the work of Clinger and Francez et. al. with one-sentence statements that used terminology that is not defined here.

The paragraph has been moved to the history article where it is more appropriate.--67.180.231.39 19:45, 30 September 2007 (UTC)

For instance: Why is your recent work "simpler" than Clinger's?

The work in [Hewitt 2006] is much easier to understand and technically much simpler than [Clinger 1981].

BTW, it is not a criticism of Clinger that long subsequent to his work that a simpler model was developed. Clinger did pioneering work in developing the first denotational model of concurrency. Nor is it a criticism of [Francez, Hoare, Lehmann, and de Roever 1979] that their model had bounded nondeterminism--they did it deliberately under the influence of Dijkstra who maintained that including unbounded nondeterminism would make it impossible to implement.--67.180.231.39 19:45, 30 September 2007 (UTC)

It is not appropriate for an encyclopedia to authoritatively state negative points about other people's work without a proper discussion and debate.

I agree that the detailed history should appear in a separate article history of denotational semantics where it can be properly discussed.--67.180.231.39 19:45, 30 September 2007 (UTC)

I argue that there is no space for a proper debate here, and moreover it's not really necessary to include the criticism, so let's omit it.

Yes, the material should be in the history article.--67.180.231.39 19:45, 30 September 2007 (UTC)

Instead, I included a remark that "these lines of enquiry remain under investigation", which implies that none of these approaches were perfect and that the interested reader will find more information in the suggested references.

These developments should be recounted in the history article.--98.207.43.10 01:36, 1 October 2007 (UTC)

If you liked, you could include a proper debate in an article on concurrency theory, and link to it from here. There is already a link to unbounded non-determinism; we can include another if you like.

The discussion probably belongs in the history article.--98.207.43.10 01:36, 1 October 2007 (UTC)

I hope you can understand my reasons, and I hope you can see that I have done my best to retain the (non-biased) content of your original contribution.

I hope we can continue to move forward to get an accurate, unbiased article. Best regards, Sam Staton 09:43, 30 September 2007 (UTC)

Since as you have pointed out there is no room in the article and the detailed history is not appropriate for this article, a new article on the history of denotational semantics is being developed. The new article needs further development.--67.180.231.39 19:45, 30 September 2007 (UTC)

Carl, I'm in vague agreement about the history article, though I have some concerns (see that article). When/if that article is better developed then it could be linked to from the introductory paragraphs of this article.

The remaining problem is the following. There are two sentences that you want to include in this article. I do not agree with those sentences; I think they are false and misleading. You think I am mistaken, and I wonder if you are mistaken. So we are stuck in a loop. I don't want to keep going round in circles. Since the sentences are not universally held facts, they (by definition) are opinions.

There are three ways out. The first is to clarify the sentences to the extent that we both happy with them. The second is to omit them because, as opinions, they are not scientific fact. The third is to include them as they are, and mark them are opinions.

Best regards. Sam Staton 11:00, 1 October 2007 (UTC)

Carl, a few comments about my changes to your recent edits.

It is not necessary to say that the standard semantics of state doesn't work properly in the case of concurrency. It doesn't work for sequentiality either. It is clear to anyone reading the article that for concurrency, one needs to be very careful.

I don't know why you keep writing about "functional" data types. The techniques for data types are just as relevant for imperative languages as for functional ones. We have talked about this before. I wonder whether, while you are an expert on the actor semantics, you don't know very much about denotational semantics in general. I recommend reading the textbooks that are listed in the article.

I notice that you have included two quotes about semantics. As far as I can tell, these have nothing particular to do with denotational semantics and would be more relevant on the page about formal semantics of programming languages. I would move them there, only I am a bit apprehensive about lengthy quotes (see Wikipedia:Don't_include_copies_of_primary_sources), especially the Clinger one, since Clinger is not considered by many to be a world expert in this field. It's a bit odd to include a quote from Scott and then one from Clinger. Sam Staton 17:06, 9 October 2007 (UTC)

Systems or Expressions

The intro refers to "denotation of a system" and earlier it also provides examples of systems. I usually thought of a denotation as being defined on a syntactic object; such an enity I would have called an "expression." Now admittedly, it may be desirable to have a general way of referring to the kinds of things which require denotations. But it seems very strange to explicitly avoid the use of "expression", i.e. "3+4" is an expression not a system.

We could enter into a discussion about whether it is "computer systems" which have denotations or rather "syntactic expressions which denote computer systems" which in turn have denotations in some domainspace, but I would rather stay away from that.--CSTAR 18:31, 9 October 2007 (UTC)

CSTAR, that is a good point. I had been planning for a while to change "semantics of computer systems" to "semantics of programming languages". Since you have also noticed this, I will make the change. After all, this subject stems from semantics. I have a computer system on my desk, and it makes no sense to talk about the "meaning" of it! I don't even know what "semantics of computer systems" means. Perhaps, as you suggest, it means "semantics of languages for describing computer systems".

If someone objects we can discuss here. Sam Staton 19:21, 9 October 2007 (UTC)

Probably "semantics of computational systems" since hardware systems have denotational semantics as well as software systems.--206.223.225.227 03:45, 11 October 2007 (UTC)

I think you're talking about the people who find mathematical models for chips etc.. I think this is most often called "modelling", and I can't think of anyone who calls it "denotational semantics". (It's more about "modelling" a chip than finding the "meaning" of a chip.) We could say "semantics of computer languages" rather than "of programming languages", if you prefer that. Or, if there are genuine examples from the literature of people talking about the meanings of chips, etc, we could use "semantics of programming languages (or more generally computational systems)". Sam Staton 14:13, 11 October 2007 (UTC)

The following reference treated denotations of concurrent systems uniformly regardless of whether implemented in software or hardware:

• Carl Hewitt (2006) What is Commitment? Physical, Organizational, and Social COIN@AAMAS. 2006.

These days it's not so clear how you tell the difference between hardware and software. The denotational semantics of hardware is closely related to model checking.--206.223.225.227 16:39, 11 October 2007 (UTC)

Dear Carl, I am very happy to talk about semantics of languages for software programming, of languages for hardware design and specification, languages for protocol specification, etc etc.. My dictionary says that 2semantics2 is about meaning of languages, or sentences of languages, and that's why I find it strange to say "semantics of systems" per se. In your article, in Section 4, as I understand it, you are thinking of the Actor model as a language, and the "Actor systems" as well-formed sentences in that language. The purpose of Chapter 4 is to define the meaning of those sentences, and this makes it semantics. On the other hand, if one wants to talk about mathematical representations of what a pre-existing (perhaps physical) system can do, then that is the subject of modelling, and not semantics, for you are no longer talking about the meaning of things but rather about what things do. I've never heard a physicist speak of "semantics of gravity"!

Try focusing on the denotations. It's clear that a hardware concurrent system has a denotation. Also the software won't run without the hardware ;-) --206.223.225.227 18:21, 11 October 2007 (UTC)

I hope I've understood that part of your article correctly and I hope you can understand what I am trying to say. (I see we are now straying into the debate that CSTAR wanted to avoid...) All the best, Sam Staton 17:45, 11 October 2007 (UTC)

Sorry, it doesn't make sense to say that a physical entity denotes a mathematical object. Yes, a physical thing can be modelled by a mathematical object. But not denoted. (Check the dictionary!) Sam Staton 10:59, 12 October 2007 (UTC)

Researchers are continually extending language. For better or worse, Denote_S as the denotation for a system S is already deeply embedded in the literature.--206.223.225.227 16:19, 12 October 2007 (UTC)

Please can you give some references? I know plenty of people who look at models of chips, etc, and they don't call it denotational semantics. As I said above, the systems in your paper are nothing but phrases of a language (the language of the actor model). If you're right, and people really talk about "denotations of physical entities", we should also write to the dictionaries to tell them that "denotation" doesn't just mean "That which a word denotes" (OED), but also "that which models a physical system". I find this quite obscure. (No need to keep shouting, by the way.) Sam Staton 17:04, 12 October 2007 (UTC)

The references are sprinkled and there are lots more in print. In order to persuade people to change, you are going to have to come up with better notation than Denote_S.--206.223.225.227 17:54, 12 October 2007 (UTC)

That may be true, but I'd still like to see some of these references, to understand what you are talking about. In the meantime, if you want to talk about models of physical systems ... why not write Model(S) ? Sam Staton 18:56, 12 October 2007 (UTC)

Your proposal stands to cause confusion with established usage in model checking.--206.223.225.227 20:28, 12 October 2007 (UTC)

You can see why I wanted to avoid this discussion. There is no doubt here (I don't think) that "denotation" is a function on some class of objects; usually these objects are thought of as syntactic objects. Now clearly we can try to relate two objects which are not (at least not in any obviously recognizable way) syntatic objects. But to attempt to call that a denotation as Carl wants us to do, is a risky business. For example, bisimulations can relate non-syntactic objects and I suppose one could use bisimulation to offer a kind of semantics of hardware. But that I think is too idiosyncratically Carl. --CSTAR 19:09, 12 October 2007 (UTC)

Of course the hardware engineers have gigabytes of syntactic objects for their machines ;-) --206.223.225.227 19:35, 12 October 2007 (UTC)

Re hardware engineers have gigabytes of syntactic objects for their machines ...whatever that means ...and regardless of what it means, (if anything) what is the relation to my comment above--CSTAR 00:46, 14 October 2007 (UTC)

It should be possible to map from the syntactic objects of hardware engineers to denotations.--71.204.128.92 18:53, 14 October 2007 (UTC)

Then you are talking about denotational semantics of hardware description languages, which is very reasonable. Both CSTAR and I made this point in our first postings above. I really don't understand what you are arguing about. Sam Staton 08:44, 15 October 2007 (UTC)

The gigabytes of syntactic objects document machines (i.e. systems).--98.207.43.23 21:44, 15 October 2007 (UTC)

It's no use pretending that concurrency does not exist

It's no use pretending that concurrency does not exist. The mythical dream of computation being limited to functions as originally conceived by Strachey and Scott has dissolved in the reality of massive concurrency. So get over it ;-)

If you are talking to me, I remind you that I do believe in concurrency. We've been over this in the discussion above, and I thought we had reached agreement about the balance in the current state of the article. If not, we'll have to discuss here further.

One further point. Many (if not most) studies of denotational semantics, even of concurrent programs, consider denotations of programs as morphisms between the type of the environment and the type of the program. These morphisms may be more elaborate than functions, eg relations for non-deterministic programs, or profunctors or morphisms of petri nets in Winksel's work. But the connection with functions is not so far away. Sam Staton 09:25, 11 October 2007 (UTC)

You may not be aware that there are recursive programs (e.g. in Java and C#) that are not functional ;-)

Yes I am aware of this! Sam Staton 09:25, 11 October 2007 (UTC)

Semantics of functional recursive programs

In this section we review the semantics of functional recursive programs which were the initial subject matter of denotational semantics. (These programs are called "functional" because the objects which are denoted do not change, unlike in conventional programming languages.)

Although the section uses the example of a functional language, and that I think is clear from the first sentence, the techniques are just as applicable to all (sequential) languages. A while ago I thought of rewriting the first section using "while" programs instead of a functional language. This is in keeping with many of the textbooks and would perhaps make the page more accessible to newcomers. Perhaps you would prefer it too. I'll have a go at that in a sandbox and let you when it's done. Sam Staton 09:25, 11 October 2007 (UTC)

You may not be aware that there are data structures (e.g. in Java and C#) that are not functional ;-)

It's not that the data types, ie data structure definitions, are "not functional". It is the imperative use of them that is important. If one gives semantics to imperative languages in the straightforward way (as above) then solving domain equations is just as relevant for imperative languages (with mutable data structures) as it is for functional ones (with immutable data structures). I have already pointed you to the standard textbooks and the Reus and Streicher paper. Sam Staton 09:25, 11 October 2007 (UTC)

I can believe that in the actor model you do something different, and that this is better for concurrent programs. That's great, and should be mentioned on the pages about the actor model and briefly in the section on concurrency on this page. Sam Staton 09:25, 11 October 2007 (UTC)

Denotations of functional data types

Many programming languages allow users to define recursive data types. For example, the type of lists of numbers can be specified by

datatype list = Cons of (Nat, list) | Empty.

This section deals only with functional data structures that cannot change. Conventional programming languages would typically allow the elements of such a recursive list to be changed.

Just because Sam Staton is blind to this reality doesn't mean that the Wikipedia has to follow suit.--206.223.225.227 04:27, 11 October 2007 (UTC)

Ouch! I think you may have misunderstood a few things. Sam Staton 09:25, 11 October 2007 (UTC)

This talk page uses continuation semantics. We will continue at a point where we left off this conversation (timewise about two years ago.)--CSTAR 16:40, 11 October 2007 (UTC)