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

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2003-04-22 08:20:20

Vesa Karvonen wrote:
>   8xFn_rec(8xF,8xN,
>             8xIf(8xIs_0(8xN),
>                  1,
>                  8xTimes(8xN,8xAp(8xF,8xPred(8xN)))))
...
> At any rate, this technique does not seem to make the code completely
> unreadable, but it does make it more bullet proof.

Note that you don't need to use 'x'.  You can even use underscore if you want:

8_fn_rec...

>> [Chaos recursion] is a direct and large-scale manipulation of
>> expansion order
>
> The technique is very interesting! I can see now why only two
> preprocessors can handle it.
>
> Do you have a name for the technique? I think that a term like
> "rescanning recursion technique", might be more understandable than
> describing it as "full algorithmic abstraction of recursion".

Well, I was calling it a "lambda recursion," because it generates an expression
without evaluating it--and then evaluates it, but then you actually went and
designed a *real* lambda calculus interpreter, so I had to change it!  I'd
prefer the name "scan recursion."

>> I think that the stack machine itself can be implemented in terms of
>> lower-level recursive techniques like the Chaos uses however.
>
> If the rescanning recursion technique makes the stack machine more
> robust
> and does not negatively affect performance, then it would definitely
> make sense to use the rescanning recursion technique to implement the
> stack machine.
>
> It might also be possible to implement the Order-interpreter more
> directly (without a separate stack machine) using similar techniques.
> I have actually been playing around with the idea of a sort of a
> direct recursive "expression evaluating" mechanism. The rescanning
> recursion technique might actually make it possible.

I implemented a miniature parser for the parameteric lambda expressions that
Chaos uses, e.g. something like CAT_(class T, (0)) where (0) is the placeholder,
with this mechanism.  That parser is actually implementing a grammar!  So, I
guarantee that the above is possible, it just takes some "getting used to." :)

Regards,
Paul Mensonides