Re: [boost] Newbie question: association graphs

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-14 17:19:23

Torsten Schindler wrote:
> 
> Hi Jeremy,
> 
> > To turn your detect clique algorithm into a state machine, you will need
> > to replace the recursive algorithm with a stack-based version of the
> > algorithm, i.e., use a stack and a loop to simulate the recursion. I've
> > started to think about how that would look, but it's a bit complicated...
> >
> Can you give me an short example. Maybe I'm able to convert the
> code myself. Another point I'm still interested is: How
> should a visitor for the DetectClique class look like, any hints?

I know exactly what it will look like.
That's because this is exactly what Felix does (for procedures).
Basically, you can do this in complete generality: eliminate
the stack from _any_ piece of code, by a mechanical transformation.

First: you write a driver loop:

        while(p) p= p->resume()

Now, you use a functoid that looks like this:

        struct continuation {
                int pc;
                continuation *caller;
                continuation(continuation *ret) : pc(0), caller(ret) {}
                virtual continuation *resume()=0;
        };

        struct X : continuation {
                X(continuation *ret, arguments ..) : 
                        continuation(ret), 
                        //init members . 
                {}

                continuation *resume()
                {
                        switch(pc)
                        {
                                case 0: case_0: ...
                                case 1: case_1: ...
                                case 2: case_2: ...
                                ...
                        }
                }		
        };

To return to the caller, you say:

        return caller;

Initially, the caller is NULL, which terminates the driver loop:

        continuation *p = new initial_proc(NULL, arguments);
        while (p) p = p->resume();
        assert(p==NULL);

You can also say:

        pc = 99;
        return this;

instead of

        goto case_99:

To call a subroutine 'fred'

        pc = 99;
        return new fred(this, arguments);
        case 99:

If you want to do a tail recursion, which is a loop:

        return new(this) X(ret,arguments)

which reinitialises the current frame (without bothering
to destroy the old object  .. you can fix that if it worries you)

If you extend the continuation object to have a pointer

        message_t *msg;

which is set to non-NULL when you want a message_t object
stored by the driver at address msg, and extend the driver
loop to read messages from a queue when that happens,
you have just done event driven programming using
cooperative multi-tasking -- without programming
any message handling callbacks (you use CALL,
RETURN and READ psuedo code shown above, and you keep
a hashtable of continuations, one for each thread,
and resume the one that the next message is for)

The code uses the machine stack _temporarily_, but the stack
is always empty at the point you yield to the driver,
non-the-less you have maintained a stack of objects
using a linked list of callers.

Finally, I didn't explain how to delete an object when
it returns to its caller (Felix uses a GC, since you can
actually return a pointer to value on the 'stack' in Felix,
but you probably don't need that).

For an actual state machine, there will only be a single object,
and you will change state entirely using gotos, so you don't
need the driver loop, nor the pc variable, just the switch.
If you have a non-tail recursive recursion <g>, then the
mechanism above will generate frames: it works even when
the recursion is indirect. [Felix also allows nested
procedures, and also passes a 'display' to allow
access to the environment]

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