[racket] applicative order -- topic was: Re: Help with exception raising and testing

Thank you for the illuminating primer, Matt. I hadn't realized that it was
such a questionable term.




On Wed, Aug 28, 2013 at 12:54 PM, Matthias Felleisen
<matthias at ccs.neu.edu>wrote:

>
> On Aug 28, 2013, at 12:33 PM, Grant Rettke wrote:
>
> > On Wed, Aug 28, 2013 at 11:04 PM, Matthias Felleisen
> > <matthias at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130828/e0edb595/attachment-0001.html>