Re: [boost] Newbie question: association graphs

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-15 17:03:47

Torsten Schindler wrote:
> 
> Hi Max,
> 
> thank you for your answer, but I have only reached an intermediate
> level of C++ programming, thus I need a more concret example.
> Can you explain me the whole thing with a simple routine
> for calculation of Fibonacci numbers for instance or can you tell me
> where I
> can find some literature which describes the solution in more detail?

        OK. For the function

        fib(n) = fib(n-1) + fib(n-2) n>1
        fib(1)=fib(0)=1

we could write

        int fib(int n) { 
                if(n<2) return 1; 
                else return fib(n-1) + fib(n-2); 
        }

To control invert it (make it stackless), 
we first need to change from a function
to a procedure, since my technique doesn't handle return values:

        void fib(int *p, int n) {
                if(n<2) *p=1;
                else {
                        int a,b;
                        fib(&a, n-1);
                        fib(&b, n-2);
                        *p = *a + *b;
                }
        }

Next, I'll simplify that:

        FIB::fib(int *p, int n) {
                switch(pc)
                {
                        case 0:
                                if(n>1) GOTO 2;
                        case 1:
                                *p = 1;
                                GOTO 5;
                        case 2:
                                CALL fib(&a, n-1);
                        case 3:
                                CALL fib(&b, n-2);
                        case 4:
                                *p = *a + *b;	
                        case 5:
                                RETURN
                }
        }

This is supposed to be a method in the class:

        struct FIB {
                int pc;
                FIB *caller;
                int *p;
                int n;
                int a;
                int b;

                FIB(FIB *caller_, int *p_, int n_)
                : caller(caller_), p(p_), n(n_), pc(0) {}
                FIB *fib();
        };

but I have to expand the GOTO, CALL, and RETURN psuedo
code to make it work (and a few other details).

        FIB * FIB::fib() {
                switch (pc) 
                {
                case 0:
                        if(n>1) { pc=2; return this; }
                case 1:
                        *p=1;
                        pc = 5; return this;
                case 2:
                        pc = 3;
                        return new FIB(this, &a, n-1);
                case 3:
                        pc = 4;
                        return new FIB(this, &b, n-2);
                case 4:
                        *p = *a + *b;
                case 5:
                        /* delete this; */
                        return caller;
                }
        }

Now, to drive it, I need:

        int *result;
        FIB *start = new FIB(0,&result,n);
        while(start) start=start->fib();
        cout << *result << endl;

I note that this code is inefficient in two ways.
FIRST: the algorithm is woeful, since it says:

        fib(n) = fib(n-1) + fib(n-2)

and that recomputes fib(n-2) twice. 
This isn't tail recursive! But I stuck to this algorithm
because it is simplest.

SECOND: the GOTO's can usually be replaced by

        goto case_n;
        ...
        case n: case_n:

that is, a direct jump to the case, instead of

        pc = n;
        return this;

You CANNOT do that for the CALL operation.

As to 'literature', all I can point to is the
sourceforge hosted documentation of the Felix programming
language, and I do NOT recommend that at the moment,
since I have not yet written up the details of the transformation.
[The actual implementation is given, but it's in Ocaml, and it
handles a LOT of other stuff than just control inversion]

I have also refrained here from 

        a) testing the example (because I'm lazy)

        b) showing the actual Felix generated code
                (because you're lazy, and you don't want
                to see the extra 'clutter' that Felix generates)

However, you can download Felix if you have a Linux box,
and try it out yourself, and you can probably make my
example code work with little effort.

BTW: the Felix for the above function is

        fun fib(n:int):int { return fib(n-1) + fib(n-2); }

and that does all the work I showed you by hand automatically.

-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net