[Prev][Next][Index][Thread]
[matthias@rice.edu: denotational versus operational semantics]
Date: Tue, 31 May 88 10:14:59 CDT
From: Matthias Felleisen <matthias@rice.edu>
To: sieber@fb10vax.informatik.uni-saarland.dbp.de, meyer@theory.lcs.mit.edu
Cc: matthias@leto.rice.edu
In-Reply-To: Kurt Sieber's message of Mon, 30 May 88 18:31:07 CDT <<8805301815.AA25259@fb10vax.sbsvax.uucp>>
Subject: denotational versus operational semantics
I don't believe that denotational semantics tells you anything more
about the complexity of call-by-name vs call-by-value than calculus
semantics. The two appropriate calculi are based on
(\(n)x.M)N --> M[x/N] versus (\(v)x.M)V --> M[x/V]
where N ranges over terms, V over values. Similarly, in a pure setting
we only need to exchange the clauses for procedures in a denotational
specification:
E[\(n)x.M] == lambda r. lambda v. E[M]r[x/v]
versus
E[\(n)x.M] == lambda r. lambda v. v=BOTTOM --> BOTTOM, E[M]r[x/v]
Now, I can't see from either specification that call-by-value is
better or worse than call-by-name.
The truth is that call-by-name in a larger setting (assignment, goto)
generally needs much more elaborate rules than call-by-value. This
really asks for a measure for the orthogonality of constructs because
this is the issue involved.
I am currently writing up a first report on a formal
theory of expressiveness of languages (not Turing-machine
computability!) and this yields some insight into this issue. One of
the results seems to be that call-by-name is "less orthogonal" to ANY
imperative facilities than call-by-value. I hope to send you a draft
within this month.
Sorry, for pursuing a side-track that's not really central in
denotational vs operational semantics. That's also the reason for not
answering to the cc-list, but if you think it is appropriate, you may
forward this msg to a larger forum. -- Matthias