On Aug 28, 2013, at 12:33 PM, Grant Rettke wrote:
> On Wed, Aug 28, 2013 at 11:04 PM, Matthias Felleisen
> <matth...@ccs.neu.edu> wrote:
>> For the record, there is no such thing as 'applicative order.' There is
>> call-by-value and there is a humongous misunderstanding
>> called 'applicative order'
>
> When authors use this term what do they cite as being the
> authoritative source? How did people come up with using the term?
A short history of PL and LC and evaluation order:
* 1960ish: people discover the lc as a model of pl. But the lc by itself is not
a pl, and they know that. For example, you can encode arithmetic in lc but
that's bad. They also understand that lc per se does not nail down an
evaluation function. For pragmatic reasons, it is clearly wrong to define
eval[[ e ]] = the normal form of e according to beta
Otherwise you get infinite loops when the programs that you
* over the he following decade: people make two different compromises:
[1] they stop evaluating when they find a lambda but otherwise use beta
[2] they evaluate the argument before they evaluate a function application
Algol 60 introduces the by-value variant as
A(int x) value x; as short for A(int x); x := x;
with the understanding that := is strict on the rhs.
* in parallel: mathematicians think that this is about a strategy for
evaluation lambda terms and explore a whole range of evaluation strategy. An ES
is a function from a lambda term with at least one beta redex to a specific
beta redex. Applicative order is one of these.
* 1970ish: People begin to understand that 'applicative' does not address the
termination issue. Confusion reigns.
* 1973: Plotkin writes the definitive paper on the issue of relating LC to
notions of CBName and CBValue. It appears in TCS:
Call-by-name, call-by-value, and the lambda calculus.
It shows how the idea of evaluation order and the idea of a calculus relate to
each other and sets out general criteria. Then it shows that two different
calculi relate to the specified evaluation function according to these
criteria.
* I later showed in my dissertation that these criteria also apply to
extensions of the model with assignment and control.
* Crank and I followed up with a paper that shows how Plotkin's criteria scale
to call-by-reference/pass-by-worth, call-by-copy-in/out, etc. So Plotkin's
criteria are neither whimsical nor a fluke. It is possible to work out this
connection for any combination.
* In a nutshell, however, the idea of evaluation strategy for LC relates to the
idea of evaluation order in PLs only in a highly superficial manner.
* Sadly SICP continues to propagate this misunderstanding and people keep for
falling for it because the book is intriguing in other ways.
So if you wish to connect LC and PL and speak about order, please study the
above citations. The whole discussion is summarized in the first part of the
REDEX book (see redex.racket-lang.org).
-- Matthias
____________________
Racket Users list:
http://lists.racket-lang.org/users
