Denotational Semantics

The field of DenotationalSemantics was founded by DanaScott and ChristopherStrachey.

This discipline is alluded to on HoareTriple.

See the FreeOnLineDictionaryOfComputing at http://www.foldoc.org/foldoc/foldoc.cgi?denotational+semantics for a more precise explanation.

As far as I understand, DenotationalSemantics works as this: a function is defined that maps a valid expression onto some mathematical object. For example, if I have the expression 2+2, then the denotational semantics of this expression might be the natural number 4. (At least, that would be the case in any conventional programming language.) The construct fun x -> x + 2 might be mapped to the function from N to N that adds 2. This works most naturally for FunctionalProgrammingLanguages, but you can also do this for languages with assignment. (Although no-one ever wrote a DenotationalSemantics for CeePlusPlus.) -- StephanHouben

In denotational semantics, jumps are modeled using continuations (see ContinuationExplanation). Also see "Continuations: A mathematical semantics for handling full jumps" (1974) by ChristopherStrachey and Christopher P. Wadsworth (reprinted in Higher-Order and Symbolic Computation, 13(1/2):135-152, April 2000).

Denotational Semantics : The Scott-Strachey Approach to Programming Language Theory by Joseph E. Stoy

ISBN 0262690764 Review from Amazon: "You can read this for pleasure or personal edification. It's probably quite hard to get hold of now. It's a classic, and it's completely out of date. A bit like Plutarch."

He was my undergraduate college tutor. Seems to know what he's talking about. LambdaCalculus is very big in Oxford University's computing department, if that helps your websearches.

-- MattBiddulph

ChristianQueinnec's "LispInSmallPieces" has a chapter that lays out DenotationalSemantics for SchemeLanguage. Queinnec also wrote a conversion program, LiSP2TeX, that allows you to describe a denotational interpreter in Lisp syntax, execute it in Scheme, and convert the description to the Greek-heavy format that LambdaCalculus junkies prefer. -- SethGordon

Gadzooks! Seth, you are a star. Thanks for the hint. Google reveals that LiSP2TeX lives at http://youpou.lip6.fr/queinnec/WWW/l2t.html -- KeithBraithwaite

Now at: http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/l2t.html -- VolkerStolz?

DavidHarland? wrote a couple of books in 1984 and 1986 respectively in which I first read about DenotationalSemantics - highly underrated or overlooked books in the history of program language design I would say, from my highly limited experience of the genre:

Polymorphic Programming Languages ISBN 0470200294 (Out of Print)
Concurrency and Programming Languages ISBN 0470203625 (Out of Print)

-- RichardDrake

Linguists also use DenotationalSemantics for natural languages such as english for example http://cl.snu.ac.kr/nam/papers/abstract.PDF

DenotationalSemantics is similar to "{}" in Bison for example in a definition of expressions:

  exp:    NUM                { $$ = $1;         }
        | exp '+' exp        { $$ = $1 + $3;    }
        | exp '-' exp        { $$ = $1 - $3;    }
        | exp '*' exp        { $$ = $1 * $3;    }
        | exp '/' exp        { $$ = $1 / $3;    }
        | '-' exp  %prec NEG { $$ = -$2;        }
        | exp '^' exp        { $$ = pow ($1, $3); }
        | '(' exp ')'        { $$ = $2;         }
  ;

before each set of curly brackets is the synax and in the curly brackets is the semantics. Usually grammars only give syntax semantics specifies meaning. In formal DenotationalSemantics double square brackets are used for "semantic functions" so "+" above might be

  [[A + B]] = plus([[A]], [[B]])

Where plus() is known in the meta (specifying) language. Can also be sub or superscripted with other meta variables such as environments, continuations etc. Ie for a simple programming language statement1;statement2;... may become

 C[[S1;S2]]rho = C[[S1]]rho.C[[S2]]rho

Where C is "Command", rho the environment, "." means composition. DenotationalSemantics allows you to completely reduce and manipulate languages and their instances (programs or utterances) to mathematics and logic.

This doesn't look like a notation for "semantics", but rather an alternative algorithm for implementing interpreters/compilers, or at least a syntactic pre-digester, similar to an intermediate meta-language for a CommonLanguageRuntime engine . And/or perhaps a system to verify an interpreter/compiler is doing its job, somewhat similar to DesignByContract. I question that this and similar notations are directly "semantics". -t

{It isn't semantics; it's a notation for expressing semantics, and the above example is rather poor. See http://en.wikipedia.org/wiki/Denotational_semantics for a better description, and in particular, a reasonable set of references.}

How do we know it's expressing semantics and not algorithms or algorithm verification techniques?
{Why would denotational semantics (or other formal expressions of semantics) be describing "algorithms or algorithm verification techniques" when informal descriptions of semantics -- such as language reference manuals -- do not?}
- Such manuals may indeed be at least partly describing algorithms. Without a clear-cut definition or scientific test for "semantics", I have no fricken way to really know. To me, "semantics" is nearly synonymous with "ideas" in human minds. It's not directly about words in manuals, but rather what the mind does with such words (and different minds probably process such words/concepts differently).
[In addition, it doesn't meet the definitions for those things. In the example above, it's not an algorithm verification technique that is expressed since there's no algorithm to be verified, nor any place to supply such. It's also clearly not an algorithm since no instructions on how to evaluate the expressions are given, just what the expressions must evaluate to.]
Maybe it's incomplete then. It could be describing an aspect of syntax that nobody cares about, being neither algorithms nor semantics.
[Maybe? Since it does describe what language means, it's clearly describing semantics. There is no maybe about it.]
Algorithms can't describe "meaning"? How does one objectively measure the existence or absence of "meaning"? Or more specifically, that a given notation is or denotes ONLY meaning, and not partly meaning and partly algorithms and/or something else? AKA, purity test.

{What's wrong with using a formal notation for semantics to automate creating compilers and interpreters, in exactly the same manner that a formal notation for syntax -- EBNF -- allows us to automate creation of parsers?}

My issue is in calling it "semantics" or "only semantics", and has nothing to do with its suitability as a compiler tool.

{If it's used to formally describe the semantics of a programming language, why would it be describing anything but semantics?}

Just because one claims it describes semantics does not by itself make it so. If I get a letter from an alleged Nigerian Prince (with a special money-making deal), that by itself does not mean it's really from a Nigerian Prince. That should go without saying. And if one is misusing the output, then they are misusing the output (Re: "If it's used to formally describe..."). That should go without saying also.

For example, suppose the inventor of Prolog first introduced Prolog as a "semantics encoding technique" in 1972 or whatnot, and claimed Prolog "denotes semantics" and writes an interpreter for Algol in it claiming that the result "denotes the semantics of Algol". How does one objectively know if the inventor is full of it?

[Between this and your response to me above, you sound pretty desperate. In both cases, you aren't actually pointing out a problem or issue with it describing semantics. Maybe learning about the subjects you pontificate on before speaking would help.]

Projection; you are having difficulty answering basic questions. Your approach seems to be, "I know semantics when I see it because I'm more knowledgeable than you." This kind of thing is a fake get-out-of-rigor card.

{Why question whether DenotationalSemantics represents semantics or not? It's as odd a question as asking how we know that the Python language reference manual makes reference to Python and not assembly language. DenotationalSemantics either makes reference to syntactic constructs of a language in a coherent fashion and provides a description consistent with run-time language behaviour -- in which case it describes semantics -- or it does not. This is rather like being asked how we know that a blueprint represents a floor-plan and not a circuit diagram. The best response is probably, "Huh?!??"}

A description of an algorithm or a restatement of syntax structures in a meta-programming-language (similar to what Microsoft CLR may do under the hood) may fit those characteristics, but are not "pure semantics" by most accounts. If a notation represents semantics and only semantics, one should be able to describe characteristics of such similar to how one would look for characteristics of a circuit diagram. Circuit diagrams typically don't have bathroom sinks, for example. There are patterns and patterns can be identified by examining specimens. As far as I can tell, DenotationalSemantics fits the pattern of a meta-programming-language. But, there are no agreed-upon specimens of "pure semantics" to compare that side. And that's because semantics are ideas in human minds and so far the human mind remains mostly unencodable.

{I don't know why you think DenotationalSemantics "fits the pattern of a meta-programming-language". I don't know what a "meta-programming-language" is, nor how it's "similar to what Microsoft CLR may do under the hood". DenotationalSemantics maps language statements to mathematical objects so that we can reason about them formally and logically. That's it. It provides a way of unambiguously stating that, for example, whenever we have a language statement of the form "x + y" it shall be interpreted as (i.e., it shall mean) numerical addition of 'x' and 'y'.}

That transformation by itself doesn't make it "only semantics".

{Sorry, I don't know what that has to do with what I wrote.}

Does address it to me. I don't see whats wrong my statement, to be frank. "That transformation" refers to "maps language statements to mathematical objects". Mapping language statements to mathematical objects does not make those "mathematical objects" be only semantics.
{Equivalently, a Python language reference manual could, conceivably, actually be about French poetry. Have you asked Guido van Rossum to prove that the Python reference manual is actually about Python and not about French poetry?}
Your analogy is silly. Semantics and algorithms are easily confused, and the first one is poorly defined. (Note it is possible for a Python manual to be BOTH poetry AND a language manual in a similar to way that the Head First book series is both entertainment and education, quality of each aside.)
{Semantics and algorithms should not be easily confused. What statement in C means the B+Tree insert? What statement in Java means the Edmonds-Karp algorithm? A given statement, say "a = b;" in a typical programming language, has a meaning -- for example, "variable assignment". This is the semantics of the statement. Algorithms are used in the interpreter or compiler to implement semantics, but "a = b;" means "variable assignment", not "1. pushvar('b'); 2. retrieve('a'); 3. assign(pop());" Similarly, B+Trees may be used to implement indexing in a DBMS. That does not mean an index is a B+Tree -- a B+Tree is just one possible implementation strategy -- but an index may use a B+Tree.}
People often use implementation models in their head to think and reason about things. Nobody stops anybody from thinking of database indexes in terms of B+Tree's, for example. To them, the "meaning" and implementation either are the same, or heavily overlap. Similarly, one can imagine stacks when evaluating expressions. If one is heavily used to the old-style HP calculators, a stack mental model may become quite natural to them: habitual even. And one can envision "assignment" as a clerical robot taking the right side of the assignment statment, handing it to the expression evaluator robot, and when the expression evaluator robot is done, the original robot takes the results, and sticks them in the cubby-hole (slot) labelled with that variable name (as found on left side of statement). That's what "assignment" may "mean" to such a person. The meaning is an algorithm involving robots who follow pre-set rules. -t
{Treating meaning and implementation as equivalent is erroneous. How individuals (mis)interpret things is irrelevant.}
Why exactly is it "erroneous"? You are dictating how people "should" think and reason about their tools now?
{It's erroneous because meaning and implementation are not the same thing. In a typical programming language, "a = b;" means "assign b to a", it doesn't mean some sequence of machine language instructions or some series of steps, even though the compiler or interpreter author may have chosen them to implement "assign b to a".}
Bull. Implementation and meaning CAN be the same thing, of one chooses. People can think about languages any damned way they please. Babbage or his disciples are perfectly free to imagine and mentally process arithmetic computations in mechanical terms as long as they get work done right, for example. How they envision "assign" in their head is up to them, NOT you. You again appear to be mistaking your mental preferences for universal truths. We can define certain syntax patterns to be objectively (or at least consistently) called "assignment", but that doesn't limit HOW people think about such statements in their heads to do useful mental work.
{How people think about such statements is immaterial and irrelevant. Semantics are defined by a language designer to be exactly what the language designer wants them to be. Semantics are described in terms of the parts of the language -- e.g., values, variables, types, expressions, parameters, arguments, functions, procedures, flow-control constructs, expressions, etc. -- and how the parts interact. How someone might (mis)interpret language semantics is irrelevant -- including if someone, for whatever reason, understands semantics purely in terms of how they're implemented. All that matters in terms of human interpretation of semantics is that hopefully they're interpreted sufficiently accurately by the compiler/interpreter authors that the semantics described by the language designer are reflected in the actual run-time behaviour of the language implementations.}
People are allowed to use any semantics/model they want (as long as they get work done). Nobody can dictate that, not even the language inventor. What are you, the Thought Police? Plus, it's difficult to read language creator minds, and the writing on dynamic types is often poor in my honest opinion. -t
{People are allowed to maintain whatever misconceptions they like, but remember that semantics are not a matter of interpretation, but of definition. Regardless how well (or not) they're described, they are defined by language designers, and language implementers follow those definitions, not their own suppositions, interpretations or models.}
You have not proven such are MISconceptions. The language implementator may use multiple different communication techniques to determine what the language author(s) had in mind, such as similarities to similar existing languages, and Hello-World-style examples that show I/O for a given snippet. Brand new languages that are very different from existing languages are generally built by the language author him/herself, at least as a proof of concept. However, outside of such, existing languages are often used as reference source being that most new languages are heavily influenced by one or more existing language. Or perhaps the language author builds a "toy" version of the language him/herself as reference example, and then the professional implementors create a hardware-friendly version. These implementors can then use something akin to IoProfile against the "lab version" to determine expected behavior. Professional language implementors generally use hardware-friendly models in their heads because that's what they are used to (and I suspect distorts your view of the human thought world). For example, they may "think of" expression evaluation in terms of stacks because stacks are usually used to implement expression evaluators, at least for dynamic languages. That is NOT wrong, per se, but it is an implementation-specific viewpoint/mental-model. There is no canonical, unique single "right" way to think about such. There is no "pure" way/form for a language author to communicate his/her ideas. It's a combination of communication techniques that are used in practice, a majority of it similar to the IoProfile way to ascertain behavioral patterns of lab versions, and to using existing implementations of similar languages as a reference. (Disclaimer, I have not observed any actual "implementation parties", and this is merely personal speculation based in part on author and tech writer descriptions of the birth of certain languages. Either way, the idea transmission approaches are poorly documented such that ANYBODY's description is only an estimate based on limited clues.) -t
{Whether an individual's perception of semantics is correct or incorrect does not matter. All that matters is whether a compiler or interpreter for language <x> successfully matches the description of semantics for language <x>. With imperative programming languages, there is so much commonality that even with poor descriptions of language semantics, they can generally be correctly inferred based on knowledge of imperative programming languages in general.}
I disagree about matching the description. Few production programmers will likely read more than about 10% of the manual. Manuals are a tool, not a Bible. All that really matters is that the externally observable behavior of the language (interpreter) acts as expected. And you are right that expectations are often shaped by exposure to prior similar languages. It's mostly experience gained over time. Further, the best training manuals for languages are usually those with lots of small examples to illustrate behavior and gotcha's, which is closer to IoProfile than manual text study. Granted, different people learn different ways, but examples are still the favorite in my observation. Most just don't rely that much on text-centric descriptions of languages. And many authors are pretty crappy, especially when writing about dynamic types.
{Whether an individual "production programmer" reads "more than about 10% of the manual" is irrelevant. What matters is whether the intended semantics of the language matches the implementation. In that sense, only the interpreter/compiler developer needs to read the manual.}
Intended by who or what? (Make sure you think through your answer carefully, because I am going to hold you to it.)
{By the language designer.}
Users of languages generally do not care what language designers intended; they care how an interpreter actually behaves (IoProfile). I see no reason to define a language around what the designer intended unless it's a convenient shortcut to "know" the interpreter. We've been over this already. I consider the final arbiter criteria of an existing language to be the IoProfile, and this is consistent with usual field usage concerns.
{How is IoProfile relevant here? Isn't that a set of examples and their output used to determine whether one compiler/interpreter implementation behaves the same as another? As for "I see no reason to define a language around what the designer intended unless it's a convenient shortcut to 'know' the interpreter", wouldn't it be rather strange to create a language that wasn't what the designer intended, even if (perhaps, especially if) the designer and the interpreter author are the same person?}
No, the IoProfile is NOT a "set of examples". It is a technique to compare behavior. It is not limited to a "set of examples" nor does it label any "set of examples" in particular. And we are generally talking about language users, not language implementers. Of course the language implementer needs to work with the language designer to know what he/she wanted using various techniques. But a language user will likely never talk to the language designer. A language designer's manual may help the user know how a language works/behaves, but it's actual behavior (discovered using IoProfile-like techniques) is usually the final arbiter in the language user's world.
{I don't know any programmer that learns a language by "using IOProfile-like techniques". Instead, they read language documentation and/or take a course on the language, apply their knowledge of using similar languages, and write their own programs using the language. I don't know anyone who learns a language by using "a technique to compare behavior".}
I admit that maybe I'm not describing it quite right. I'm not a perfect writer. But most programmers I know learn mostly by examples, not so much descriptive manuals/books. Thus, it's the behavior of the language in terms of inputs (source and input data) and output (write statements) that they use. The descriptive part mostly just sets the stage in a general sense, and the examples supply the concrete details. The text becomes short-hand for code patterns. We see "nested block" and we know that "means" (predicts) that one code block is indented in another by studying some examples. It's a handy alias for a code pattern. I thought "nest" was an odd word for the situation when I first saw it, but learned that it implies a certain code structure pattern. Whether it "means" something is perhaps moot; it's an alias for a certain pattern and doesn't have to "mean" to do its job. -t
{I include examples among the useful references that a programmer may use, but examples without explanation are unhelpful, so description is valuable whether it's general discourse or the comments above lines of code. By the way, "means" and "predicts" are not the same thing. "Nested block" means a particular structure, it does not "predict" a particular structure. A "certain pattern" only has resonance because it means something, not because it predicts something.}
I didn't say descriptions were useless. And as far as if/how/when "means" is different from "prediction", that depends on what "means" means. That's a WetWare issue and is difficult to dissect with current resources. Any statements about it is merely conjecture.

And original code can also "reasoned about formally and logically". True, it may not be the most easiest notation for such work, but it's a matter of degree rather than a Boolean condition.

{Imperative code is unusually difficult to reason about.}

But "difficult" is a continuous scale. I don't dispute that the transformation may simplify the ability to analyze a language, but ease is not the issue at hand. Determining if it represents semantics and only semantics is the issue, not whether it's "easy to analyze'.

{A (programming) language is composed of syntax and semantics. If we're not talking about its syntax, we must be talking about its semantics. Of course, it's possible not to be talking about the language at all, but that's trivial to determine: We're either making reference to the language, or we aren't.}

But we are talking about the classification of what DS produces, not the language by itself. Again, describing what languages are composed of does not necessarily limit what DS output is composed of. The human using DS appears to be injecting algorithm artifacts into at least part of what DS produces as output.

{I don't know what you mean by "DS produces". DenotationalSemantics doesn't "produce". It's as odd as asking, "What does English produce?"}

Doesn't one use DS techniques to create a notation that (allegedly) represents semantics of a given computer language?
{No, one uses DenotationalSemantics to map language statements to mathematical objects. The mathematical objects represent the semantics of the computer language.}
How do we know those objects represent "semantics" and not "algorithms" or something else? (Didn't I ask that befow?)
{The same way we know the Python reference manual is talking about the Python language and not French poetry.}
Most don't really know how they do it in their gray matter. However, usually one can find lots of clues and explain why they are clues instead of "just trust me because I'm smart".
{Simpler than that: There's no French vocabulary (well, not enough to matter) in the Python language reference manual. Similarly, there are no algorithms in DenotationalSemantics.}
Lack of algorithms doesn't mean it's semantics. There could be third option(s), such as whatever Prolog denotes.
{As a language, Prolog is defined in terms of syntax and semantics. See, for example, http://en.wikipedia.org/wiki/Prolog_syntax_and_semantics }
But we are not talking about Prolog itself. See SemanticsDiscussion for discussions on what DS's output is.
{I'm afraid, then, that I don't follow your point.}

{What does "injecting algorithm artifacts" mean?}

Human interpretation of the syntax is turned into an algorithm or part of an algorithm in one's mind, and that algorithm is then written down as DS notation.

{I don't know why anyone would do that. It wouldn't be DenotationalSemantics, and I don't know how one would represent an algorithm in DenotationalSemantics.}

How do you know that's not the mistake being done with DS?

{How would we make that mistake with DenonationalSemantics?, when DenotationalSemantics doesn't let us represent algorithms?}

How do you know it's not presenting algorithms?

{Because it can't.}

Where's the stopper-fier?

{DenotationalSemantics defines mappings from language statements to mathematical objects, in which the mathematical objects represent the semantics of the language. Mathematical objects aren't algorithms.}

Those mathematical objects may be representing implementation (or perhaps implementation "hints"). See SemanticsDiscussion for discussions on what DS's output is.

{No, those mathematical objects are representing semantics. We use mathematical objects as a substitute for informal human-language descriptions of semantics.}

To me they just look like a re-statement of syntax patterns with implementation-oriented "hints". That does not make them semantics. They may be influenced by semantics, but that's not the same as being semantics. Anyhow, without a rigorous and widely-accepted way to classify a given notation as being "semantics" versus implementation versus "observations" etc., we will probably never settle this. I consider "semantics" to be human ideas in human minds. Notation that reflects such ideas is usually considered "implementation". DS generates partial implementation information in that it provides implementation hints, but is incomplete. And these "hints" may indeed be structured in a way that makes analysis of program behavior easier. But implementation information can be used for such also, similar to how a security expert may analyze machine code to figure out what a virus is doing. Being analyzable for clues about behavior characteristics does not (by itself) make it "semantics".

{How the DenotationalSemantics "look" to you, and the fact that you "consider 'semantics' to be human ideas in human minds", is irrelevant. You're free to be wrong all you like. That doesn't affect ComputerScience.}

It's not "science" if you cannot give decent evidence you are measuring semantics and not something else. Why should someone just take your word for it? Science is not ArgumentFromAuthority.

A DenotationalSemantics of (a small part of) XSLT: http://homepages.inf.ed.ac.uk/wadler/papers/xsl-semantics/xsl-semantics.pdf

A FormalSemantics? of PrologLanguage is given using PiCalculus in http://scholar.google.com/scholar?cluster=6035347962773538537.

DenotationalSemantics: A Methodology for Language Development by DavidSchmidt?.

Been out of print several years, now available online at: http://www.cis.ksu.edu/~schmidt/text/densem.html

ISBN 0697068498 (no image available)

http://4.bp.blogspot.com/-HpwWEkmsczQ/TsyAJ-yh4aI/AAAAAAAAIvI/dDXY_JSUfw0/s400/DSC_0134.JPG

Slots in this kind of shelf is what I mean when I say "cubby hole". Maybe there's a better term. (For some reason, the image is not directly displaying in the page; one has to click on it. Wiki bug?) -t

So, what does "operational equivalence coincides with denotational equality" imply for Perl?