Wed May 6 18:16:37 CEST 2009

lazy partial evaluation

Interesting article here [1].  I'm getting a faint hint at what this
signifies.  It is related to reordering applications as mentioned
above.  I need to read a bit more about terminology.

"Evaluation under lambda" First comment in [2].  Reducing expressions
inside abstractions, instead of leftmost outermost.

First, let's go back to Felleisens comment about reduction strategies
vs. calculi.  It's better to define what a reducable expression is and
always reduce the leftmost outermost expression.

  "Normal order and applicative order are failed attempts to explain
   the nature of call-by-name programming languages and call-by-value
   programming languages as models of the lambda calculus. Each
   describes a so-called _reduction strategy_, which is an algorithm
   that picks the position of next redex BETA that should be
   reduced. By 1972, it was clear that instead you want different kind
   of calculi for different calling conventions and evaluation
   strategies (to the first outermost lambda, not inside).  That is,
   you always reduce at the leftmost-outermost point in a program but
   you use either BETA- NAME or BETA-VALUE." [3]

What is the equivalent of reduction inside abstractions for a
concatenative language?  Probably reduction of subprograms.  I wonder:
is there any difference between reducing from left to right and
reducing in arbitrary order?

Also, the Staapl macros behave as higher order abstract syntax: they
describe terms instead of being terms (machine code) [5].

[1] http://lukepalmer.wordpress.com/2009/05/04/lazy-partial-evaluation/
[2] http://lambda-the-ultimate.org/node/3217
[3] http://list.cs.brown.edu/pipermail/plt-scheme/2009-February/030354.html
[4] http://en.wikipedia.org/wiki/Supercombinator
[5] http://en.wikipedia.org/wiki/Higher-order_abstract_syntax