# Boost :

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-03 06:35:13

From: "Vesa Karvonen" <vesa.karvonen_at_[hidden]>
> From: "Vesa Karvonen" <vesa.karvonen_at_[hidden]>
> > Hi,
> >
> > A few hours ago, I invented a technique for implementing ADD(X,Y) and
> SUB(X,Y)
> > using linear amount of tokens.
> [snip]
> > It is highly likely that other interesting and useful operations could be
> > implemented in the future.
>
> I have now implemented also MUL(X,Y), MAX(X,Y) and MIN(X,Y).
>
> A pint of beer is promised to the first person to implement DIV(X,Y) and
> MOD(X,Y) using at most a linear amount of tokens (and the result must, of
> course, be a single token).

I implemented DIV and MOD about two hours ago (local time is currently 13:50),
so it seems like that I get the beer...

I'll probably post more details later, but I'll first present the primary
technique. Basically, it seems to be possible to simulate the WHILE statement
using the preprocessor:

// C = Condition
// F = Body / Function
// X = State (tuple)
#define WHILE(C,F,X) IF(C X,IF(C X,WHILE0,DUMMY)(C,F,F X),X)
#define WHILE0(C,F,X) IF(C X,IF(C X,WHILE1,DUMMY)(C,F,F X),X)
#define WHILE1(C,F,X) IF(C X,IF(C X,WHILE2,DUMMY)(C,F,F X),X)
#define WHILE3(C,F,X) IF(C X,IF(C X,WHILE3,DUMMY)(C,F,F X),X)
#define WHILE4(C,F,X) IF(C X,IF(C X,WHILE4,DUMMY)(C,F,F X),X)
// ...

If you look closely, you'll notice the funny looking "C X" and "F X"
expressions. They are tuple function calls. The state X, is a tuple. For
example, a 4-tuple could look like this:

(1, 2, 3, 4)

To make a function for manipulating a tuple, say increment the first and
decrement the second element of a 2-tuple, you could write it like this:

( INC(X)\
, DEC(Y)\
)

Another function on a 2-tuple could simply return the second element:

#define TUPLE2_E1(E0,E1) E1

With these you can implement ADD:

Well, not quite, you need to extract the first element from the resulting
tuple. It can be done with these helper primitives:

#define TUPLE2_E0(E0,E1) E0
#define ID(X) X

Integrating these to ADD we get: