From: ogden@seal.cis.ohio-state.edu (William F Ogden)
Subject: Re: Semantic definition style
Keywords: structural operational semantics, denotational semantics
Organization: The Ohio State University Dept. of Computer and Info. Science
Date: Wed, 18 Nov 1992 01:04:21 GMT

In article <1992Nov13.084826.26088@daimi.aau.dk> pdm@daimi.aau.dk (Peter D. Mosses) writes:
   ...
>The style of `structural' operational semantics advocated by Plotkin
>et al. does *not* involve any translation!  The main point is
>precisely to avoid consideration of all the small, boring steps that
>low-level machines make, and to specify only the bigger transitions
>that are of interest at the programming language level.

Depending upon what you're willing to accept as operational semantics, I
suppose that the most austere forms might just reduce to denotational
semantics. I.e., the input/output pairs from sequential denotational
semantics (yes, pairs involving extended states which include auxillary
components such as environments) could be viewed as just very short
operational semantics history sequences which `specify only the bigger
transitions that are of interest at the programming language level.'

Moreover, it does seem likely that, whenever we finally discover
an appropriate set of language constructs to handle concurrency cleanly,
their denotational semantics will probably involve something comparable to
the state sequence notion which shows up in operational semantics.

   ...

>The use of minimal fixed points is neither more nor less difficult to
>explain than that of recursive (i.e., self-calling) procedures.
>Readers of semantic descriptions don't usually need to understand
>*why* things with certain desirable properties exist.  In fact in the
>mid '60s, Strachey was happily using minimal fixed point operators in
>denotational descriptions, long before the existence of a mathematical
>model for them was shown!

Minimal fixed point operators may be no more difficult to _explain_ than
recursive procedures, but when used with higher order functionals, they
do seem to be more difficult for most people to _understand_.

I never met Strachey, but from his writings at least, he doesn't strike me
as an example of the ordinary programmers who comprise one of the three
audiences for semantics whom we must consider.

>Another, more technical drawback of the use of Scott domains in
>denotational semantics is the following.  A semantics is usually
>intended to specify a *class* of implementations, not just one
>implementation.  I don't see any reason why a class of continuous
>functions should be representable by a single continuous function.
>E.g., consider a language where the value in an uninitialized variable
>is an arbitrary number (not necessarily the same one each time); to
>represent this denotationally involves unbounded nondeterminism, which
>conflicts with the usual continuity assumption.

Indeed. You don't get very far into object based programming before
you notice that functions just don't provide an adequate base for
the semantics of even sequential programming with objects. The
abstraction process that permits alternative realizations of operations
as well as information hiding inherently leads to what appears at the
abstract object level to be nondeterminism. The obvious denotational
semantics to cover this are relational and not functional.
-- 

/Bill

Newsgroups: comp.specification