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

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2003-04-21 21:11:38

Vesa Karvonen wrote:
>>> [...] 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.

No it shouldn't overlap too much.  Chaos is, by definition, closer to the
preprocessor.  Order is an abstraction that, to a degree, hides the details of
the preprocessor.  Both are useful tools.

> 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.

They still do in order to protect them from macro expansions or they must be
unilaterally prohibited from being defined in any context--including local
context.  If you don't want prefixes for "identifiers" that aren't macros, you
can use a pp-numbers such as 0xLambda, 0xExpr, etc..  These are valid
preprocessing tokens, even though they aren't valid number "tokens," but you can
still use them to discriminate between various types of "instructions."  It is
also *not possible* to define them as macros, so they make for useful,
completely protected "flag identifiers."

> - 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).

The Chaos library provides significantly higher guarantees than the CVS pp-lib,
and can do the same type of lazy processing as the above.

> - Lambda-abstractions: The interpreter has full support for
> programming with higher-order functions. This significantly reduces
> the need for "top-level definitions".

Yes, and this is a great boon, but only up to a point.  The upside of lambda
expressions is that they can be easily "defined" on the spot; the downside is
that they cannot be easily reused.  For that, you turn to normal top-level
definition anyway.

> - Recursion: The interpreter makes the implementation of (recursive)
> algorithms very simple.

Yes, recursion is important.  Chaos abstracts recursion in a way that is closer
to the preprocessor.

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

It looks cool to me so far. ;)

>> 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?

For "full abstraction of recursion", I mean that macros can effectively invoke
themselves if design appropriately.  By "algorithmic," I mean implementing
recursive algorithms with only a few macros rather than hundreds.  The idea is
fundamentally simple:  It defers doing anything recursive until after rescanning
has finished: (warning names changed to protect the innocent--or, in the case of
Vesa and I, to protect the pathologically insane!)

#define EXPR_S(s) CAT(EXPR_, s)
#define EXPR_1(x) x
#define EXPR_2(x) x
#define EXPR_3(x) x
#define EXPR_4(x) x
#define EXPR_5(x) x

#define DEFER(macro) macro EMPTY()

#define COUNT_BACKWARDS_S(s, number) \
    number \
    DEFER(IF)( \
        number, \
        EXPR_S(INC(s)), \
        TUPLE_EAT(1) \
    )(DEFER(COUNT_BACKWARDS_ID)()( \
        INC(s), DEC(s) \
    )) \
    /**/
#define COUNT_BACKWARDS_ID() COUNT_BACKWARDS_S

A direct invocation of COUNT_BACKWARDS_S(1, 3) expands to this uninteresting
result:

3 IF( number, EXPR_2, EAT_1 )( COUNT_BACKWARDS_ID()(2, 2) )

This is not particularly great.  However, another scanning pass essentially
starts a controlled recursive chain-reaction:

EXPR_S(1)( COUNT_BACKWARDS_S(1, 3) )

...Which results in:

3 2 1 0

Automatic recursion is vastly simplified because it only has to work with the
expression macros.  Likewise, automatic recursion can make the above much
simpler:

EXPR(COUNT_BACKWARDS(3))

EXPR is an abstraction of an "entry point."  COUNT_BACKWARDS is an abstraction
of an algorithmic "step."  This can be simplified even further by a user-defined
entry point.

So, in essence, it abstracts recursion to a single set of macros.  This is
obviously closer to the preprocessor than a full-blown lambda calculus
interpreter, and it comes with serious drawbacks.  It *requires* a very strict
preprocessor because it is a direct and large-scale manipulation of expansion
order.  This prohibits its use of VC and Metrowerks.  It also requires (macro
names)/(specific identifier tokens) to be disabled only when they should be
disabled--during the first rescan of the replacement-list.  That prevents its
use on EDG-based preprocessors.  If however, EDG fixes that bug, it would be
quite fast, even on EDG--because 1) the "delays" that make EDG faster are
inherent, and 2) the data structures that EDG uses to "remember" which macros
aren't valid for expansion or massively simplified.  Likewise, the level of
detection that the library uses probibits its use on Borland, IBM, and Sun.
Which leaves, AFAICT, Wave and gcc as the only two preprocessors that can handle
the entire library.

The technique is extensible, BTW, and causes the "states" of various constructs
to be merged into a single library "state."  So, more advanced users can make
more algorithms that are implemented on top of the Chaos recursion backend.
Likewise, the algorithms that call user-defined macros, such as WHILE and
REPEAT, etc., can also generate "intermediate" expressions like the above,
effectively pulling their functionality out of themselves and into the
"expression" macros.  Thereby, allowing them to recurse on themselves.  For
instance, consider to good ol' LIST_CAT algorithm.  It is possible to create a
LIST_CAT algorithm that does a "deep" concatenation--i.e. lists of elements that
might be lists, etc..  So, effectively, library primitive A calls user-macro B
which calls library primitive A which calls user-macro B and so-on and so-forth.
The mechanism is *powerful*.  I.e. algorithms like WHILE, FOR, etc., used to be
implemented in terms of large sets of macros such as WHILE_1, WHILE_2, WHILE_3,
etc., the "strict" pp-lib does not do that kind of thing *ever*.

> 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.

The stack machine itself can be implemented with recursive abstraction like the
above.  Automatic recursion may not be relevent to the stack machine internally,
but it could be relevent if the stack machine was implemented using the
recursive abstraction above, and then subsequently used from other "normal"
Chaos-based code (or vice-versa).

> 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. ;)

It is not difficult for anything but division/modulus--which requires a degree
of "guessing-and-correction."  Otherwise, addition, substraction, and
multiplication are all easy to implement in "near-arbitrary precision" (meaning,
in theory, billions upon billions of digits).  However, fixed precision will
still be faster, because I can optimize based on a fixed number of digits.

> 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).

Chaos implements those macros in terms of an early-exiting exponential loop
(again implemented with about 3/4 macros) which is capable of billions upon
billions of iterations--i.e. longer than you want to wait.  So, it won't run out
of steam either. ;)

> However, it is definitely not necessary to base everything on the
> stack machine as other recursion techniques may be more efficient for
> special tasks.

I like the idea of a stack machine though.  I think that the stack machine
itself can be implemented in terms of lower-level recursive techniques like the
Chaos uses however.

Regards,
Paul Mensonides