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

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