[boost] Re: PP: Beta-reducer for closed lambda-terms

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-04-21 19:34:22

Paul Mensonides:
>Vesa Karvonen:
>>[...] I think that Order and Chaos could benefit from and complement each
>>other. [...]
>
>Chaos *is* the pp-lib, but redesigned from the ground up to take advantage 
>of
>strictly conformant preprocessors.

Ok. Then I think that the overlap between Order and Chaos is not necessarily 
big.

The main advantages of the interpreter could be summarized as follows:
- Syntax: The readability of interpreted programs is better because long 
prefixes don't have to be used in programs.
- Controlled evaluation: For example, the 'if(cond,then,else)' special form 
is lazy unlike in Boost.PP. Only one of the 'then' and 'else' expressions is 
evaluated. This means that one never has to split a function because it has 
a conditional (like in the current PP-lib).
- Lambda-abstractions: The interpreter has full support for programming with 
higher-order functions. This significantly reduces the need for "top-level 
definitions".
- Recursion: The interpreter makes the implementation of (recursive) 
algorithms very simple.

These advantages make the Order-interpreter particularly interesting for 
implementing the logic and control of non-trivial program generators.

>The most fundamental differences between Chaos and the CVS pp-lib is a full
>abstraction of recursion.  It is *algorithmic*, which means implementing
>things like REPEAT, FOR, FOLD_LEFT, WHILE, and even FOR_EACH_PRODUCT all
>only require about three or four macros each.

What do you mean with "full abstraction of recursion" and that it is 
"algorithmic"?
Could you explain the idea in more detail?

Speaking of recursion, the Order-interpreter relies on the stack machine 
abstraction (sm.hpp - although I have made some changes to the 
implementation since last posting).

The stack machine essentially makes it relatively easy to write recursive 
algorithms. It is also straight-forward to decompose complex programs into 
modular "instructions" using the stack machine. For example, you can 
implement an "instruction" for computing the sum of two arbitrary precision 
numbers. The instruction can then be called from more complex instructions 
essentially as if were a subroutine or a function. To "call an instruction" 
one simply pushes the parameters on top of the value (or state) stack and 
pushes the instruction on top of the instruction (or program) stack.

All of this essentially boils into this: it is only necessary to implement 
one simple stack machine. Techniques such as automatic recursion are not 
needed. Of course, this means that one has to implement algorithms as 
stack-machine instructions. This is not as bad as it may sound, as 
individual "instructions" (or subroutines or functions) can be made 
arbitrarily powerful. For example, the complete Order-interpreter is 
basically just a single instruction of the stack machine (the EVAL 
instruction).

>I'm still debating whether to provide fixed, high-precision arithmetic, or
>arbitrary precision arithmetic.  I can do either, but fixed orecision would 
>be
>faster.  Maybe I'll do both....

High-precision arithmetic is probably more pragmatic.
Arbitrary precision arithmetic is probably more interesting. ;)

I have currently implemented simple arithmetic by implementing the simple 
addition, subtraction and multiplication algorithms as stack-machine 
instructions. This makes them more robust than the current Boost.PP 
implementations using WHILE (e.g. try BOOST_PP_MUL(200,200) and you'll get 
an error message - the stack machine does not run out of steam). However, it 
is definitely not necessary to base everything on the stack machine as other 
recursion techniques may be more efficient for special tasks.

-Vesa

_________________________________________________________________
MSN 8 with e-mail virus protection service: 2 months FREE* 
http://join.msn.com/?page=features/virus