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

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-04-22 04:57:06

Paul Mensonides:
>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."

That is an interesting idea! Here is how the expression of a factorial 
function would look in Order currently:

  fn_rec(F,N,
         if(is_0(N),
            1,
            times(N,ap(F,pred(N)))))

This is how the code would look like when all operators (or keywords) are 
prefixed with 8:

  8fn_rec(8F,8N,
          8if(8is_0(8N),
              1,
              8times(8N,8ap(8F,8pred(8N)))))

Here is how the code would look with the prefix '8x' and the first character 
after the prefix in upper case:

  8xFn_rec(8xF,8xN,
            8xIf(8xIs_0(8xN),
                 1,
                 8xTimes(8xN,8xAp(8xF,8xPred(8xN)))))

In [X]Emacs, for example, it would be possible to use a special symbol lock 
mode to essentially hide the '8x' prefixes. (It would also be possible to 
provide special modes for pp-programming. E.g. a mode that allows you to 
edit macro definitions without having to think about backslashes at all, 
because the mode would insert backslashes (almost) completely 
automatically.)

At any rate, this technique does not seem to make the code completely 
unreadable, but it does make it more bullet proof.

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

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

-Vesa

_________________________________________________________________
The new MSN 8: advanced junk mail protection and 2 months FREE* 
http://join.msn.com/?page=features/junkmail