Re: [boost] Newbie question: association graphs

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-18 18:47:50

Torsten Schindler wrote:
> 
> Hi Max,
> 
> thank you little lecture in recursive programming.
> To avoid misunderstandings I have still some question:
> 1) Your method turns an recursive algorithm into
>    a recursive state machine.
> 
>    Right [X] or Wrong [ ]

        I suppose that's right. It's more precise
to say that the machine stack is replaced by a manually
built one, so that the machine stack itself is
not used (except temporarily).

        However, since the transformation yields
a program with the _same_ semantics as the original
one, it's difficult to say that one is a state
machine and the other not: any description of one
applies to the other, since they're isomorphic
programs.

> 2) How would a visitor for the FIB class look like?

        What's a visitor? The original algorithm
is just a simple recursion. 'Visitor' applies to
scanning a tree data structure, as I understand it:
I've never bothered with 'Design Patterns' myself
(although I have it), it doesn't seem to say anything.
I don't do OO much, and I don't use classes as heavily
as other people -- indeed, at the moment, I don't
use C++ much. When I want to process a tree, I just
write recursive algorithms.

        To make them 'stackless' I write them in Felix,
and it does the work :-)

        In general, every procedure is just a class
with a resume() method. I think I called that fib()
in the Fibonacci example. In Felix, its always called
'resume()', and the class implementing the function
is always derived from 'continuation_t' which has
a pure virtual resume method.
 
> 3) How would a stack-based state machine of the Fibonacci
>    algorithm look like?

        I'm not sure what you mean: the original
algorithm

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

is how it looks in recursive form using the machine
stack. The code I posted is how it looks when control
inverted to replace the machine stack with a manual
one (using my particular transformation).
 
> 4) How would a stack-based state machine of the Bron/Kerbosch
>    algorithm look like? 

        I have no idea, since I don't know what that algorithm 
looks like.

>  Any simple recipe how I can convert it
>    to a stack-based state machine?

        Sure, I already gave it: replace
all functions with procedures. This means adding an extra
pointer argument, and storing the result where it points
intead of returning a value. Where the function is used,
you must decouple the expression into a list of
procedure calls which store the results in temporary
variables: this is what the C++ compiler does for when it
unravels an expression, but now you have to do it yourself.

        Having done that, you put a big switch around
the body of the resume() method, and write out the code
using GOTO, RETURN and CALL instead of every jump,
return, or procedure call, and then you replace that
psuedo code with appropriate C++ as indicated in
the example.

        There is a _mechanical_ way to do this,
that is, there is an actual tool which does it all
for you: that's what Felix does. 

> I read somewhere that good programmers are 'lazy'.

        :-)

> P.S.:
> Two year ago I was forced to convert F77 code with many goto statements
> to F90 code. During that work I sweared to my: No goto's in my
> programs!!!

        State machines use gotos. However, the use obeys
invariants: the jumps are always to a label
in a list of labels at one level of abstraction.

        Normally, you would NOT like to do this by hand.
That's one reason I am writing the Felix translator.

        Another example is regular expressions: the
implementation as a state machine does a lot of gotos,
but the regular expression analyser hides that, by allowing
you to write regexps.

        Felix actually provides a goto statement.
But it is there mainly to allow the client to build
user defined control structures: that is, it is meant
to be used in library components which are carefully
analysed and checked for correctness: it isn't meant to
be used in 'general' code.

        In C++, goto is sometimes useful, typically
when the existing control structures aren't strong enough.
An example is error handling, where you don't want to use EH.
Another is the ubiquitous 'search an array for an element'
problem, which is very hard to code without repeating
a test or using a goto. 

        Don't forget that 'break' and 'continue' 
are 'slightly better structured gotos', and the
most common 'goto' of all is 'return', which jumps
to the end of a routine. If you try to avoid all these
'goto' variants, and program strictly with proper
block structure, you'll find how weak the C/C++
control structures really are.

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