Boost logo

Boost :

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-04-13 09:02:25


Aleksey Gurtovoy wrote:
[...]
>I only wish I knew more about lambda-calculus to understand the details,
>and
>the semantics of the term notation itself. Perhaps if you could elaborate a
>little bit more on it,[...]

Lambda-calculus is basically a tiny programming language, or a formalization
of computation, suitable for mathematical analysis. You can find
introductions to the lambda-calculus on the net and there are several books
and articles that introduce the lambda-calculus. For example, the book Types
and Programming Languages by Benjamin C. Pierce contains an introduction to
the lambda-calculus. The following short introduction describes the
lambda-calculus using the notation used in the PP implementation of the
lambda-calculus.

There are only three kinds of terms (expressions) in the the basic
lambda-calculus:

  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 lambda-calculus, everything is a function. In other words, there
are no built-in operators or data-types. Booleans, arithmetic on natural
numbers, and even lists, are represented using functions. For example, the
Church-booleans 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 Church-booleans, 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 Church-booleans. 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 Church-booleans, the result will be another Church-boolean. For
example:

  ((AND,TRUE),FALSE) ==> LAMBDA(T,LAMBDA(F,F)) = FALSE

There are several different strategies for the evaluation, or reduction, of
lambda-calculus terms. Most programming languages, use the
call-by-value/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
call-by-name 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 lambda-abstractions are considered
values. (This holds in the call-by-value strategy - other strategies might
continue substitution in the body of the lambda-abstraction, 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* lambda-calculus, 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 2x-10x 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 non-trivial programs using the native C
preprocessor. Of course, whether or not it is really pragmatic to use the C
preprocessor for non-trivial preprocessing is debatable. It certainly is
fun, though.

[...]
>and may be provide a few other usage examples an average PP-library 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
non-performance 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