|
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
|
Re-writing abstractions
