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

From: Alexander McLin (alex.mclin at gmail.com)
Date: Wed Aug 28 13:18:54 EDT 2013

Thank you for the correction. I will be more careful in the future.


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

>
> 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/91565f10/attachment-0001.html>

Posted on the users mailing list.