
Boost : 
From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 20030413 09:02:25
Aleksey Gurtovoy wrote:
[...]
>I only wish I knew more about lambdacalculus to understand the details,
>and
>the semantics of the term notation itself. Perhaps if you could elaborate a
>little bit more on it,[...]
Lambdacalculus is basically a tiny programming language, or a formalization
of computation, suitable for mathematical analysis. You can find
introductions to the lambdacalculus on the net and there are several books
and articles that introduce the lambdacalculus. For example, the book Types
and Programming Languages by Benjamin C. Pierce contains an introduction to
the lambdacalculus. The following short introduction describes the
lambdacalculus using the notation used in the PP implementation of the
lambdacalculus.
There are only three kinds of terms (expressions) in the the basic
lambdacalculus:
abstraction: LAMBDA(<symbol>,<term>)
application: (<term>,<term>)
variable: <symbol>
In plain english, LAMBDA(X,...) is a function of one parameter and (F,X)
applies X to the function F.
In the pure lambdacalculus, everything is a function. In other words, there
are no builtin operators or datatypes. Booleans, arithmetic on natural
numbers, and even lists, are represented using functions. For example, the
Churchbooleans are represented as functions:
#define TRUE LAMBDA(T,LAMBDA(F,T))
#define FALSE LAMBDA(T,LAMBDA(F,F))
Basically, TRUE is a function that takes two parameters (one by one) and
returns the first parameter. To compute with Churchbooleans, you apply them
to functions. For example, logical conjunction can be defined as:
#define AND LAMBDA(L,LAMBDA(R,((L,R),FALSE)))
Basically, AND is a function that takes two parameters, L and R, which are
assumed to be Churchbooleans. It first applies L to R, i.e. (L,R), and then
applies the result to FALSE, i.e. ((L,R),FALSE). Assuming the parameters L
and R were Churchbooleans, the result will be another Churchboolean. For
example:
((AND,TRUE),FALSE) ==> LAMBDA(T,LAMBDA(F,F)) = FALSE
There are several different strategies for the evaluation, or reduction, of
lambdacalculus terms. Most programming languages, use the
callbyvalue/applicative order/strict evaluation strategy, which basically
means that parameters are reduced before application and that no reduction
happens inside abstractions (functional values). Another strategy is the
callbyname strategy, which is one form of lazy evaluation.
The evaluation technique used in the implementation in the previous post
uses a very inefficient technique which basically works by using direct
substitution of terms for variables. Basically, a function application is
evaluated by substituting the evaluated (actual) parameter in the place of
each free occurrence of the function's variable (formal parameter) in the
function's body (term). For example, suppose that we evaluate the term
( LAMBDA( X, (LAMBDA(X,X),X) ) , LAMBDA(Y,Y) ) .
^ ^^^^^^^^^^^^^^^ ^^^^^^^^^^^
variable term parameter
The outer application yields, after replacing each free occurrence of the
variable X by the term LAMBDA(Y,Y) in the term (LAMBDA(X,X),X),
( LAMBDA(X,X), LAMBDA(Y,Y) ) .
Likewise, the inner application yields, after replacing each free occurrence
of the variable X by the term LAMBDA(Y,Y) in the term X,
LAMBDA(Y,Y) .
At this point, evaluation stops, because lambdaabstractions are considered
values. (This holds in the callbyvalue strategy  other strategies might
continue substitution in the body of the lambdaabstraction, but in this
case there is nothing to evaluate in the body. Note that we didn't
explicitly consider evaluating the parameter LAMBDA(Y,Y), which is also
already a value.)
Evaluation by substitution repeatedly takes apart the terms and puts them
back together, in a recursive fashion, which makes it very inefficient. I
have already implemented another toy evaluator, which works by using
environments. On evaluating the term (FACT,ONE), the evaluator using
environments is over 40 times faster than the evaluator using substitution
(on GNU CPP 2.95). (Note that numerical computations are quite intensive in
the *pure* lambdacalculus, which represents numbers as functions.) The toy
evaluator based on environments is not efficient enough to be of practical
use. You can find both evaluators in the small attachment.
The estimate that a nearly optimal interpreter might be just 2x10x slower
than the language in which the interpreter is implemented is based on the
simple observation that such numbers hold for modern interpreters. For
example, it would not be difficult to provide native operators for
arithmetic in the interpreter. The cost of arithmetic would then be the
overhead of the interpreter plus the cost of native arithmetic. As native
arithmetic, on the preprocessor, is already quite computationally intensive,
interpreted arithmetic on the preprocessor might be just 2x slower than
native arithmetic.
What is the significance of all this?
The point is that it is possible to implement an interpreter for a fairly
expressive and easy to use programming language using the C preprocessor.
Programming, using such an interpreted language, could be an order of
magnitude easier than programming the native preprocessor. Unfortunately,
the interpreter will be slower than the native preprocessor, which can and
does limit its practical usefulness. If we had a nearly optimal C
preprocessor and a nearly optimal interpreter, it could be that we would no
longer have to implement nontrivial programs using the native C
preprocessor. Of course, whether or not it is really pragmatic to use the C
preprocessor for nontrivial preprocessing is debatable. It certainly is
fun, though.
[...]
>and may be provide a few other usage examples an average PPlibrary user
>can
>associate herself with more easily, some of us would be able to provide you
>with a more than just "WOW" feedback  which this work more than certainly
>deserves anyway :).
Well, at this point, the evaluator is really just a toy implemented
primarily for fun. With the addition of some native operators and values to
the environment based evaluator, one might be able to use it for some
nonperformance sensitive PP programming.
Vesa
_________________________________________________________________
Help STOP SPAM with the new MSN 8 and get 2 months FREE*
http://join.msn.com/?page=features/junkmail
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk