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

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Wed Aug 28 13:08:56 EDT 2013

No problem. 

While we are on names. We use
 -- "Matt" for Matthew Might, a Utah researcher who also uses Racket; 
 -- "Matthew" for Matthew Flatt, the CEO of PLT Design, Inc, creator of Racket, and ruler of the kingdom 
 -- "Matthias" for me, which yes, is a form of Matthew (used in Germanic and Hispanic contexts with various spellings). 






On Aug 28, 2013, at 1:02 PM, Alexander McLin wrote:

> 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/ed151015/attachment.html>

Posted on the users mailing list.