Lambda the Ultimate

inactiveTopic Re-writing abstractions
started 12/19/2001; 12:58:04 AM - last post 12/21/2001; 1:43:04 PM
Ehud Lamm - Re-writing abstractions  blueArrow
12/19/2001; 12:58:04 AM (reads: 770, responses: 3)
Re-writing abstractions
Oleg kindly wrote this summary of his article for LtU:

Normal-order (head-first) re-writing systems are notoriously difficult to program. Examples of such systems include R5RS (aka high-level or hygienic) Scheme macros, to some extent C macros, etc. The main difficulty is that such systems are anti-functional (anti-applicative): the fundamental principle of building complex expressions out of simpler ones by functional composition does not easily apply to such re-writing systems.

The article shows how to recover the functional composition and higher-order combinators. The solution is a continuation-passing-style (CPS) coupled with a macro-lambda. The solution makes it trivial to compose re-writing rules and to use higher-order rule combinators. We can code re-writing rules using traditional, well-understood applicative programming idioms. The solution relies on a first-class denotation for a future re-writing.

Examples include several non-trivial macros as well as a normal-order lambda calculator implemented as a R5RS macro. The article shows how to systematically build R5RS macros: write the corresponding code in Scheme, mechanically convert it into CPS and then introduce macro-lambdas. Coding of R5RS macros becomes no more complex than programming of regular Scheme functions.

Throughout the article you will see several kinds of lambdas -- a lambda of lambda calculus, a rewriting-rule lambda, and a lambda of Scheme. Each is handled by its own evaluator, yet they look similar. In fact, the former and the latter lambda forms are identical. In all the cases, the lambda forms play the same role: a denotation for a parameterized future evaluation. The evaluation occurs in different ways, yet the idea of delaying an action and passing its promise as a first-class object is universal.

Posted to functional by Ehud Lamm on 12/19/01; 1:01:19 AM

Frank Atanassow - Re: Re-writing abstractions  blueArrow
12/21/2001; 12:57:38 PM (reads: 625, responses: 0)
Oleg, I've been meaning to read your essay, but I haven't found the time. (I promise to do so within the week, though.)

But I've perused it, and it reminds me of a paper by Hilsdale and Friedman: Writing Macros in Continuation-Passing Style. I wonder if you're familiar with it...?

Ehud Lamm - Re: Re-writing abstractions  blueArrow
12/21/2001; 1:23:28 PM (reads: 609, responses: 0)
Oleg mentions this paper in the Related Work section of his essay, and compares it to the approach he describes.

Frank Atanassow - Re: Re-writing abstractions  blueArrow
12/21/2001; 1:43:04 PM (reads: 616, responses: 0)
Ah! Sorry, my fault.

I wanted to get some comment up quickly, since this discussion topic has remained empty despite its interesting subject matter.