From: pdm@daimi.aau.dk (Peter D. Mosses)
Subject: Re: Semantic definition style
Summary: OK, continuing
Keywords: structural operational semantics, denotational semantics, nondeterminism
Reply-To: pdm@daimi.aau.dk (Peter D. Mosses)
Organization: DAIMI: Computer Science Department, Aarhus University, Denmark
Date: Fri, 20 Nov 92 08:56:55 GMT

In article <piotr.722190155@sedalia>, piotr@cs (Piotr Rudnicki) writes:
>pdm@daimi.aau.dk (Peter D. Mosses) writes:
>>[Perhaps we should continue this by e-mail, as it probably doesn't
>>have sufficient general interest for comp.specification.]
>
>Continue here please.
>
>I am sure there are many people who want to see such discussions.
>I am one of them.
>
>PR
>--
>Piotr (Peter) Rudnicki

Many thanks for the encouragement!  I also received several e-mail
messages expressing similar views.  I'll be happy to continue the
discussion of semantics on comp.specification - and others should feel
free to join in, of course... with questions, as well as opinions.

Just let me add a bit of explanation, followed by a perhaps somewhat
provocative statement.

Some of you may be aware that I studied denotational semantics with
Strachey in Oxford, developed a Semantics Implementation System (SIS)
for denotational semantics, and more recently wrote a chapter on the
approach for the Handbook of Theoretical Computer Science (ed. Jan van
Leeuwen, Elsevier, 1990).  You may be puzzled that I've been pointing
out problems with the denotational approach, and advocating another,
more operational approach, namely action semantics (references
provided in an earlier message - mail me if you missed that one).

Actually, I still think that denotational semantics is useful - but
only for dealing with small-scale, unrealistic languages, of the kind
often used as examples in textbooks on semantics.  The main pragmatic
problem is it doesn't seem to *scale-up* smoothly - not even as far as
medium-scale languages like Standard Pascal.  It becomes very heavy,
rather like writing large (functional) programs without any
modularity.

I'd like to make a distinction: between the *concepts* underlying the
usual denotational semantics of programming languages, and the
*representation* of these concepts by higher-order functions on Scott
domains.  In my view, it's only the latter (together with the use of
lambda-notation) that causes the pragmatic problems of denotational
semantics.  The concepts themselves, developed primarily by Strachey,
Burstall, and Landin, are useful *whatever* semantic framework one
uses!  For example, the distinction between bindings and storage
(symbol tables and memories, environments and states) is crucial for
any sensible semantic description of passing parameters by reference.
Action semantics provides straightforward notation for such concepts,
rather than representing them all in terms of higher-order functions.

Finally, to be a bit provocative :-) let me claim that if one is
making a denotational semantics of a simple language, and wants to
make the semantic equations independent of whether the model is in the
direct or in the continuation-passing style (i.e., hiding
information), one is *forced* to introduce auxiliary notation akin to
action notation!  Just contemplate the semantic equation for statement
sequencing...

-- 
Peter D. Mosses | Computer Science Department | <pdmosses@daimi.aau.dk> 
~~~~~~~~~~~~~~~ | Aarhus University           | Phone: +45 86 12 71 88 
                | Ny Munkegade, Building 540  | Fax:   +45 86 13 57 25 
                | DK-8000 Aarhus C,  Denmark  | Telex: 64767 aausci dk
Newsgroups: comp.specification