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

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-04-21 12:44:44

David Abrahams:
>Vesa Karvonen:
>>It is definitely possible to get reasonable performance from
>>the interpreter. This is especially true when using built-in operators
>>of the language.
>
>Do you mean +, *, etc?  How can you use those?  I know you know they
>don't produce tokens!

By operators, I mean special syntactic constructs recognized by the 
interpreter. Normal function application currently uses the syntax 'ap(f,p)' 
('ap' is short for 'apply' #0 #1 #2). Operators, like 'times', which is used 
for multiplication, uses the syntax 'times(l,r)'. If 'times' were a regular 
function, it would currently be called like 'ap(ap(times,l),r)'.

#0) Technically, you could say that 'ap' is the operator for function 
application.

#1) I like to keep the syntax of the most fundamental constructs of the 
language short. The reason is pragmatic. Once you have learned the basics of 
the language, these fundamental constructs become entirely obvious to you - 
every program you write uses them many many times. If the syntax is verbose, 
it may help someone who looks at the language for the first time. If the 
syntax is short, it helps to keep more complex programs readable. hmm... It 
would also be possible to support both long and concise syntax at the same 
time.

#2) The syntax 'ap(f,p)' is currently chosen over '(f,p)', because 'ap(f,p)' 
seems to be easier and faster to destructure - but I'll have to test this 
further.

>>For example, arithmetic is basically just as fast in the interpreter
>>as in the Boost.PP library (using BOOST_PP_[ADD|SUB|MUL]).
>
>Unsurprising, I guess.

Basically, yes. For the interpretation of built-in operators, the 
interpreter basically has a certain fixed overhead, which is the time it 
takes to analyze the expressions. After the analysis is done, the operators 
execute at full speed. As long as the interpreter offers a well chosen set 
of built-in operators, which match the computational needs of the users, 
performance can be kept at reasonable levels. If the operator 'times' were 
implemented as a recursive function, using primitive operations such as 
'succ(x)', it would be much much slower.

Relatively, the slowest operators are the simplest operators. In Boost.PP, 
BOOST_PP_INC(x) is very fast. In the interpreter, the corresponding 
'succ(x)' operator is significantly slower, because the overhead of the 
interpreter dominates. This means that it is important to have built-in 
operators for basic computational processes such as mapping, folding, etc...

>OK.  Not that I do all that much arithmetic...

It could potentially be more important. I could imagine building much more 
complex program generators. For example, remember the lexer and parser 
generators we discussed earlier. With fast built-in operators for maps and 
sets (like maps and sets in STL), it just might be possible to write a 
practical lexical analyzer generator. Arithmetic could be more useful in 
other kind of program generators.

>What do you mean by "embedded interpreter"?

The term is probably not very good. I was thinking about embedded languages. 
An embedded, or scripting, language is something that you can use to extend 
(or program) a system basically without modifying the system itself (like 
elisp in Emacs). I'll get back to this later.

>>, which makes the manipulation of algebraic or inductive data types,
>>such as syntax trees, relatively easy.
>
>This I've gotta see.

The basic technique is very simple. First of all, syntax trees can be 
directly encoded in the same form that they are written externally. For 
example, the preprocessing token sequence 'if(or(C,D),plus(X,Y),minus(X,Y))' 
is the representation for the following syntax tree:

             if
           /  |  \
         /    |    \
       or   plus  minus
      / |    / \    | \
     C  D   X   Y   X  Y

In order to destructure such syntax trees, one can define two macros for 
each operator (if, or, plus, minus, C, D, X, Y,...). The first of these 
macros simply extracts the operator tag or type:

#define STX_TAG_if(c,t,e)  if     // if is ternary
#define STX_TAG_or(l,r)    or     // or is binary
#define STX_TAG_plus(l,r)  plus
#define STX_TAG_minus(l,r) minus
#define STX_TAG_C          sym    // Symbols are nullary
#define STX_TAG_false      val    // Values are nullary
// ... and so on for other operators ...

The second macro extracts the children (or "opens" the node):

#define STX_OPEN_if(c,t,e)  c,t,e
#define STX_OPEN_or(l,r)    l,r
#define STX_OPEN_plus(l,r)  l,r
#define STX_OPEN_minus(l,r) l,r
#define STX_OPEN_C          C
#define STX_OPEN_false      false
// ...  and so on for other operators ...

It is now possible to destructure the top node of a syntax tree quite easily 
by using the token pasting operator:

#define FOO(syntax_tree) \
  APPLY(CAT(FOO_,STX_TAG_##syntax_tree),(STX_OPEN_##syntax_tree))
  ^^^^^          ^^^^^^^^^^^^^^^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^
    #4                    #1                       #2
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                      #3

#define FOO_if(c,t,e) It's an if with children c, t and e
#define FOO_or(l,r) It's an or with children l and r
// ... and so on for all operators ...

Consider now what happens when we expand the C preprocessor expression 
'FOO(if(true,0,1))':
1. The underlined part expands to 'if'
2. The underlined part expands to 'true,0,1'
3. The underlined part expands to 'FOO_if'
4. The macro apply is simply defined as:

#define APPLY(m,p) m p

The idea is that it applies a computed function-like macro to a computed 
parameter list. The use of APPLY (or some similar macro that essentially 
ensures the correct order of macro expansion) is necessary, due to C 
preprocessor technicalities.

5. The entire expression then expands into: 'FOO_if (true,0,1)'...
6. ...which then expands into: 'It's an if with children true, 0 and 1'

As I was hopefully able to show, this is really quite simple.

Ok, as you can see, there are some macro identifiers with lower-case 
characters, but I think that the technique is still quite safe, because the 
prefix of the macro identifier (e.g. 'BOOST_ORDER_STX_TAG_') can be made 
long and it will be highly unlikely that it would cause accidental macro 
replacement. If the lower-case characters do cause trouble, it is possible 
to get rid of them, but I think that the lower-case identifiers, like 'if', 
make the code significantly more readable.

>>[tail-recursive,lexical binding,exit,eval,...] The interpreter also
>>directly supports continuations with the special form 'call_cc(f)'
>
>OK, stop right there.  Somebody get this man into quarantine!  You are
>one sick dude, Vesa!

;) Honestly, these features aren't nearly as difficult as they may sound. I 
was quite surprised to see how easy they were to implement. The simplicity 
of the interpreter makes all these features practically trivial.

>>[special support for exceptions]
>
>Once you have continuations, that stuff is easy.

True, exceptions could basically be directly implemented in terms of 
continuations. However, continuations, in the interpreter (not in general) 
are much less efficient in terms of space than direct support for 
exceptions. I haven't really profiled/benchmarked these features, but the 
continuation technique uses signficantly much more space and the exception 
technique uses more macro expansions.

>Don't all programs use continuations?  I thought that was the most
>fundamental control structure...

Yes, you can implement other control structures in terms of continuations. 
You could say that all programs use continuations. However, not all 
languages make it possible to manipulate continuations as first class 
values. A continuation basically represents the remainder of computation 
(waiting for a value). To simplify a bit, but not much, you could think that 
in a running C++ program, a continuation would be represented by the program 
stack and all cpu-registers. To capture a continuation, you could take a 
snapshot of the state of the program stack (or stack of activation records) 
and cpu-registers (including instruction pointer register). This is 
basically how it works in the interpreter: the call_cc(x) special form 
simply captures the current program state. It is very simple (and takes 
relatively lot of space). (In real interpreters and compilers there are many 
ways to optimize the capturing of continuations so that it is not necessary 
to copy all activation records.)

>[...] When are you going to submit this sick piece of work for
>review?  Can you put it in the sandbox?

Faisal Vali:
>	I was just wondering if or when you were planning on posting the code
>for this PP-evaluator for your extended lambda calculus?
>
>I look forward to tinkering around with it if u do ;-)

Yes, I plan to publish the code at some point. The evaluators for the pure 
lambda-calculus are now basically done. It is still probably possible to 
optimize them, but not unless the structure of the evaluators is changed 
significantly (i.e. the stack machine would probably have to be replaced 
with something even better suited to the task of interpretation).

The interpreter for the extended lambda-calculus, which I have named Order, 
because it makes it easy to program with higher-order functions, is not yet 
complete enough to be published - and probably won't be totally complete in 
the near future. I'll try to get something complete enough for public 
scrutiny in the next week or so.

I'm also very interested in seeing the Chaos library from Paul. I do not 
really know the philosophy of Chaos to be sure, but I think that Order and 
Chaos could benefit from and complement each other. The Order-interpreter 
has been made possible by several discoveries in PP-metaprogramming by Paul 
and me.

Order should be handy for expressing complex functions or the logic of 
complex generators, but it isn't really designed for tasks such as 
repetition of tokens or the construction of comma separated lists. Such 
repetition constructs need to be provided outside of the Order-interpreter. 
A variation of something like the BOOST_PP_FOR() macro could be designed, 
that would directly support using Order-programs for the predicate and 
operation. In this setting, you could think that the Order-interpreter is 
embedded into the repetition construct.

Also, Paul has mentioned that Chaos implements efficient high precision 
arithmetic. The high precision arithmetic of Chaos could probably be used 
from the Order-interpreter, which could, for some parts, basically act as a 
convenient high-level front-end to the efficient low-level facilities of 
Chaos. But like I said, I don't know enough about Chaos to be sure.

-Vesa

_________________________________________________________________
Protect your PC - get McAfee.com VirusScan Online 
http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963