paralell assignment problem

paralell assignment problem

[skaller]

Does anyone know how to solve the parallel assignment problem?
Name invented by me to describe this problem:

x1,x2,x3..xn = e1,e2,e3 .. en

where ei might contain the variables xj. (Note = here is assignment).

The solution is a sequence of assignments involving
only xi, ei, and ti, where ti are temporaries introduced
to save the values of the expressions. For example,
a solution to

	x,y = y,x

is

	t = x; x = y; y = t

I seek a solution which minimises the number of assignments.
Note that the relation 

	i < j == ej doesn't depend on xi

is not transitive. This (a) confuses me enough I can't
see the solution, and (b) is precisely what allows
a temporary to remove a dependence.


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: paralell assignment problem

[Stefan Monnier]

> Does anyone know how to solve the parallel assignment problem?
> Name invented by me to describe this problem:

> x1,x2,x3..xn = e1,e2,e3 .. en

> where ei might contain the variables xj. (Note = here is assignment).

> The solution is a sequence of assignments involving
> only xi, ei, and ti, where ti are temporaries introduced
> to save the values of the expressions. For example,

Most ML compilers do this sort of thing to break big blocks of mutually
recursive functions into smaller such blocks.  The algorithm used is
generally to extract the "strongly connected components" of the graph.
Google for it and you'll surely find an algorithm.


        Stefan

Re: [Caml-list] Re: paralell assignment problem

[skaller]

On Wed, 2005-02-09 at 01:34, Stefan Monnier wrote:
> > Does anyone know how to solve the parallel assignment problem?
> > Name invented by me to describe this problem:
> 
> > x1,x2,x3..xn = e1,e2,e3 .. en
> 
> > where ei might contain the variables xj. (Note = here is assignment).
> 
> > The solution is a sequence of assignments involving
> > only xi, ei, and ti, where ti are temporaries introduced
> > to save the values of the expressions. For example,
> 
> Most ML compilers do this sort of thing to break big blocks of mutually
> recursive functions into smaller such blocks.  The algorithm used is
> generally to extract the "strongly connected components" of the graph.
> Google for it and you'll surely find an algorithm.

I'm not sure the problem is quite the same though.
Call graphs are transitive: if A calls B, and B calls C,
then A calls C.

However, 'depends on' is not transitive. Here

 x,y = y,x

x and y are mutually dependent, but in the solution:

  t = x; x = y; y = t

t depends on x, x depends on y, and y depends on t.
If the dependency were transitive, y would then 
depend on x, but it doesn't.

That is: the graph of the solution seems strongly connected:

  T -> X -> Y --+
  ^             |
  +-------------+

however, these are *sequential* and not parallel assignments.

A solution using digraph decomposition may well be the 
right answer, perhaps changing the relation to
'depends on the old value of'. This would break
the cycle above (since t has no old value, y now
doesn't depend on anything).

See another post for an algorithm..


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] paralell assignment problem

[Florian Hars]

skaller wrote:
> Does anyone know how to solve the parallel assignment problem
 > I seek a solution which minimises the number of assignments.

What, in polynomial time?

Most of the results seem to require paid subscriptions or a library at hand:
http://www.google.com/search?q=%22parallel+assignment+problem%22

But the comp.compilers link seems relevant and points further to

[3] Robert G Burger, Oscar Waddell, and R. Kent Dybvig.
           Register allocation using lazy saves, eager restores,
           and greedy shuffling. In 1995 ACM Conference on Programming
           Language Design and Implementation, June 1995, pages 130-138.
           Available online via
ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/Reg-Alloc-PLDI95.ps.gz

which claims NP-completeness for the problem.

Yours, Florian.

Re: [Caml-list] paralell assignment problem

[Marcin 'Qrczak' Kowalczyk]

skaller <skaller@users.sourceforge.net> writes:

> x1,x2,x3..xn = e1,e2,e3 .. en
>
> where ei might contain the variables xj. (Note = here is assignment).

If they contain calls to unknown functions, they might depend on these
variables indirectly. So I'm not convinced that it's worth to eliminate
temporaries in those rare cases when it's possible. After all, people
rarely assign the value of a variable to another variable.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Re: [Caml-list] Re: paralell assignment problem

[skaller]

On Wed, 2005-02-09 at 01:34, Stefan Monnier wrote:
> > Does anyone know how to solve the parallel assignment problem?
> > Name invented by me to describe this problem:
> 
> > x1,x2,x3..xn = e1,e2,e3 .. en
> 
> > where ei might contain the variables xj. (Note = here is assignment).
> 
> > The solution is a sequence of assignments involving
> > only xi, ei, and ti, where ti are temporaries introduced
> > to save the values of the expressions. For example,

Here's the algorithm I have implemented, I believe it works,
but I'm not sure it finds the minimal solution. The main
difficulty is in step 5.

1. Strip out equations of the form xi = xi since
   they don't do anything.

2. Create 3 lists: head, middle, and tail.

3. For each assignment in the working set:

  if the RHS does not depend on a variable in the working set, 
    prepend it to the tail
  else if no RHS in the working set depends on the LHS
    variable, prepend it to the head
  else add it to the middle

4. If we moved any assignment to the head or tail list,
   set the working set to the middle, and go back to step 3

5. The middle now has the property that for any assignment,
   there is at least one other assignent such that the RHS
   of one whch depends on the LHS variable of the other.

   So pick one assignment x = e out of the middle, 
   create a temporary variable t, prepend t = e
   to the head list and x = t to the tail list,
   set the working set to the remaining assignments
   of the middle. 

   If the working set is empty, the result is the reversed
   head list concatenated with the tail, otherwise
   go back to step 3


This algorithm (a) finds an equivalent set of serial assignments,
and (b) it is clearly locally minimal in the sense that
whenever it introduces a temporary in step 5,
there was no alternative but to do so.

However it isn't clear (to me) that just picking an arbitrary
assignment to split into two using a temporary
actually minimises the number of temporaries.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] paralell assignment problem

[skaller]

On Wed, 2005-02-09 at 03:03, Florian Hars wrote:
> skaller wrote:
> > Does anyone know how to solve the parallel assignment problem
>  > I seek a solution which minimises the number of assignments.
> 
> What, in polynomial time?

Actually total exhaustion may be quite feasible for
small numbers of assignments which is typical for many
tight loops presented as tail-recursive self calls.

In this case 'perfection' is desirable, whereas if 
there are 20 arguments, 'good enough' is probably good enough..

> But the comp.compilers link seems relevant and points further to
> 
> [3] Robert G Burger, Oscar Waddell, and R. Kent Dybvig.
>            Register allocation using lazy saves, eager restores,
>            and greedy shuffling. In 1995 ACM Conference on Programming
>            Language Design and Implementation, June 1995, pages 130-138.
>            Available online via
> ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/Reg-Alloc-PLDI95.ps.gz
> 
> which claims NP-completeness for the problem.

Ah, section 2.3 suggests 'Greedy Shuffling' is useful.
At present my algorithm is picking an arbitrary assignment,
but this paper suggests picking the which is depended
on most. They claim in only one program, their compiler,
did this yield non-optimal results, and in the compiler
only in 6 of 20,245 cases, in all of which only one
additional temporary was allocated.

So, thanks, this seems to be enough to finish of the
algorithm with some confidence the results will be good!


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] paralell assignment problem

[skaller]

On Wed, 2005-02-09 at 03:29, Marcin 'Qrczak' Kowalczyk wrote:
> skaller <skaller@users.sourceforge.net> writes:
> 
> > x1,x2,x3..xn = e1,e2,e3 .. en
> >
> > where ei might contain the variables xj. (Note = here is assignment).
> 
> If they contain calls to unknown functions, they might depend on these
> variables indirectly. 

This is true, and I need to ensure that this doesn't cause
a problem, which can be done, for example, by evaluating
the call to the unknown function first, and then using
that value. In this case, you'd be quite right that subsequent
optimisation would probably be worthless (calling a function
through a variable in Felix is quite expensive)

> So I'm not convinced that it's worth to eliminate
> temporaries in those rare cases when it's possible. After all, people
> rarely assign the value of a variable to another variable.

That may be so, however many function calls are direct,
that is, to known functions. In particular tail rec
calls typically involve passing 'old value - 1' or something
similar where no temporary is required. The actual example
which prompted this investigation is ackermann, which has two
tail-rec calls:

fun ack(x:int,y:int):int =>
  if x == 0 then y + 1
  elif y == 0 then ack(x-1, 1)
  else ack(x-1, ack(x, y-1))
  endif
;

No temporaries are needed in either tail call,
and either order of assignment will work.
But my actual code created 2 temporaries for each
tail call, unnecessarily.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] Re: paralell assignment problem

[Stefan Monnier]

>> Most ML compilers do this sort of thing to break big blocks of mutually
>> recursive functions into smaller such blocks.  The algorithm used is
>> generally to extract the "strongly connected components" of the graph.
>> Google for it and you'll surely find an algorithm.

> I'm not sure the problem is quite the same though.
> Call graphs are transitive: if A calls B, and B calls C,
> then A calls C.

Right, but the SCC will do the tail/head part of your algorithm in an
"optimal" way, and the strongly connected components can then be cracked
open by adding the t = ex ... x = t thingy.


        Stefan

Re: [Caml-list] paralell assignment problem

[Marcin 'Qrczak' Kowalczyk]

skaller <skaller@users.sourceforge.net> writes:

> fun ack(x:int,y:int):int =>
>   if x == 0 then y + 1
>   elif y == 0 then ack(x-1, 1)
>   else ack(x-1, ack(x, y-1))
>   endif
> ;
>
> No temporaries are needed in either tail call,
> and either order of assignment will work.
> But my actual code created 2 temporaries for each
> tail call, unnecessarily.

In the implementation of my language Kogut which targets C, on the
level I assign argument values to parameter slots (global variables),
expressions have already been processed into sequences of statements,
such that the remaining expressions contain only variables, constants,
and simple operations which don't call unknown code, don't have side
effects, don't depend on the time when they are evaluated, and can
actually be transformed into C expressions, not C statements. On this
level it's clear what expressions depend on which virtual registers.

I don't bother with finding the optimal assignment - I just make an
easy choice way which generates quite good result in most cases:

Positions are generally assigned in order. For each position, if the
target of the assignment is used among later source expressions, then
a C temporary is introduced and the temporary is assigned from the
source expression; otherwise the target is assigned directly (unless
it's the same as the source, in which case the assignment is skipped).
At the end all temporaries are assigned to their targets.

Sometimes this generates more temporaries than would be possible
with a different order, but I don't care. The C compiler must
still introduce a temporary register for moving between two global
variables, so maybe it would generate the same code even if all
values were passed through temporaries; I've heard gcc is pretty
good in propagating copies.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Re: [Caml-list] Re: paralell assignment problem

[Radu Grigore]

On Tue, 08 Feb 2005 09:12:32 -0800 (PST), skaller
<skaller@users.sourceforge.net> wrote:

> However it isn't clear (to me) that just picking an arbitrary
> assignment to split into two using a temporary
> actually minimises the number of temporaries.

I'm mildly convinced that it works.

Imagine a graph where an arrow is drawn from A to B only if A appears
in the expression to be assigned to B. You can imagine the process of
introducing temporaries as marking a few edges in this graph so that
you break all cycles. One marked edge = one temporary. But since no
identifier appears more than once on the left side, in this graph the
in-degree is at most 1 and each node is part of at most one cycle.
>From this it follows that each marked edge breaks at most one cycle.
Since all your temporaries break at least one cycle the algorithm
should work.

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Re: paralell assignment problem

[Radu Grigore]

On Tue, 8 Feb 2005 20:33:52 +0200, Radu Grigore <radugrigore@gmail.com> wrote:
> On Tue, 08 Feb 2005 09:12:32 -0800 (PST), skaller
> <skaller@users.sourceforge.net> wrote:
> 
> > However it isn't clear (to me) that just picking an arbitrary
> > assignment to split into two using a temporary
> > actually minimises the number of temporaries.
> 
> I'm mildly convinced that it works.

I was obviously too tired yesterday: there are lots of mistakes in my argument.

Actually here is an example on which your algorithm uses more
assignments than necessary:

a = b+c
b = c
c = a+b

The solution is
t = c
c = a+b
a = b+t
b = t

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Re: paralell assignment problem

[Radu Grigore]

On Tue, 8 Feb 2005 20:33:52 +0200, Radu Grigore <radugrigore@gmail.com> wrote:
> On Tue, 08 Feb 2005 09:12:32 -0800 (PST), skaller
> <skaller@users.sourceforge.net> wrote:
> 
> > However it isn't clear (to me) that just picking an arbitrary
> > assignment to split into two using a temporary
> > actually minimises the number of temporaries.
> 
> I'm mildly convinced that it works.

OK, I took 1h to think about this problem more carefully. Now I'm
almost convinced that it is NP :)

I'll use the example given in the previous mail:
a = b+c
b = c
c = a+b

We can read the first equation as "a must be computed before b and c".
So we can construct a graph whose edges mean "source should be
computed before target". In this case it is:

a -> b
a -> c
b -> c
c -> a
c -> b

If this graph has no cycles the problem is simple: just do a
topological sort and the problem is solved in O(V+E). If the graph has
cycles then we need to break them by introducing temporaries. Without
looking at the form of RHS expressions, that is without considering
computing an expression partially then we are left with two uses for
temporaries:

1. hold the original value of a variable
2. hold the result of an expression and write it later to the destination

Point (1) requires one extra assignment, while point (2) requires two
extra assignments. The effect is however the same: one of the
variable's value can be computed as soon as desired. Therefore we will
only use (1). [NOTE that your approach used (2) and hence is clearly
sub-optimal].

The effect of (1) (and (2)) on the constructed graph is that all
in-edges of a variable are removed. So we have reduced the problem to
this: "Given a graph mark as few nodes as possible such that the after
removing in-edges of marked nodes we obtain a tree". Now, that looks a
lot like SET-COVER. In the example above we have these cycles:

1: abc
2: bc
3: ac

The set is {1, 2, 3} and the subsets from which we have to choose are
a:{1, 3}, b:{2}, c:{1, 2, 3}. The minimum cover is clearly c:{1, 2, 3}
and hence the solution is to create a temporary for the original value
of c. After removing all in-edges of c and topologically sorting the
graph we get: c, a, b. So this is the order in which we should do the
other assignments. Yes -- we reached the correct solution.

Now, it looks like that starting from a SET-COVER problem one can
build a graph with the right relationship between nodes and cycles and
then an assignment problem. I can't give a  (semi-)formal argument but
I have tried on a few instances and the process of construction seems
to be fairly algorithmic (although hard to formalize -- at least in an
email -- since I used pictures). This is why I say your problem looks
NP.

An acceptable algorithm might be this one:
1. detect strongly connected components (optional)
2. within each SCC find all cycles and group them in subsets according
to the nodes they have in common
3. within each SCC solve SET-COVER (for cycle sets given by common nodes)
4. sort topologically the graph after removing the in-edges of nodes
marked at step 3

Step 2 is clearly exponential in the number of variables (consider a
complete graph).

For step 3 you probably want to use an approximation algorithm. It
looks like there are ones with good complexity (but I do not know them
so I can't tell anything about the constants). In any case, have a
look at: http://www.nada.kth.se/~viggo/wwwcompendium/node146.html
If you use the lg C algorithm (C = cycles) then the overall complexity
is something like O(2^V), where V is the number of variables.

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Re: paralell assignment problem

[skaller]

On Wed, 2005-02-09 at 18:48, Radu Grigore wrote:
> On Tue, 8 Feb 2005 20:33:52 +0200, Radu Grigore <radugrigore@gmail.com> wrote:
> > On Tue, 08 Feb 2005 09:12:32 -0800 (PST), skaller
> > <skaller@users.sourceforge.net> wrote:
> > 
> > > However it isn't clear (to me) that just picking an arbitrary
> > > assignment to split into two using a temporary
> > > actually minimises the number of temporaries.
> > 
> > I'm mildly convinced that it works.
> 
> I was obviously too tired yesterday: there are lots of mistakes in my argument.
> 
> Actually here is an example on which your algorithm uses more
> assignments than necessary:
> 
> a = b+c
> b = c
> c = a+b
> 
> The solution is
> t = c
> c = a+b
> a = b+t
> b = t

That's confirmed, my algorithm produces this:

ASG _tmp_a<2009> = (Int::add (f::b, f::c))
ASG _tmp_c<2010> = (Int::add (f::a, f::b))
ASG b<1764> = f::c
ASG c<1765> = index_2010
ASG a<1763> = index_2009

However, your solution, whilst correct, breaks one of
the rules: one of the RHS is refering to the old value
of 'c' using the name 't'. The original rules required
only assignments using the original LHS variables,
the original RHS expressions, and the temporaries,
that is, only permitted buffering the RHS expressions,
not old values of variables.

Allowing *both* RHS expressions (new values of variables)
and LHS variables (old values of variables) makes sense,
however, as your example demonstrates. And also seems
to make solving the problem harder :)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] Re: paralell assignment problem

[Radu Grigore]

On Wed, 9 Feb 2005 11:43:34 +0200, Radu Grigore <radugrigore@gmail.com> wrote:

> 1. hold the original value of a variable
> 2. hold the result of an expression and write it later to the destination
> 
> Point (1) requires one extra assignment, while point (2) requires two
> extra assignments. The effect is however the same: one of the
> variable's value can be computed as soon as desired. Therefore we will
> only use (1). [NOTE that your approach used (2) and hence is clearly
> sub-optimal].

One more mistake. Both approaches introduce _one_ extra assignment and
the algorithm described subsequently is independent on the choice of
(1) or (2).

For the problem:
a = b+c
b = c
c = a+b

The algorithm says: introduce a temporary for c, and the order is c, a, b.
With choice (1) the solution is the one I already wrote. With choice (2) it is:

// compute temporaries
t = a+b

// compute c, a, b (skip c because we have temporary, this is what I missed)
a = b+c
b = c

// use temporaries
c = t

... for a total of 4 assignments (same as with choice 1). This is
better than the 5 assignments given by your algorithm and it does NOT
depend on breaking the rule about using temporaries only to save
results of expressions (but not initial values).

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Re: paralell assignment problem

[Pascal Zimmer]

OK, I think I can add my stone now :)

Radu Grigore wrote:
> OK, I took 1h to think about this problem more carefully. Now I'm
> almost convinced that it is NP :)

It is. I will reuse your notations:

> I'll use the example given in the previous mail:
> a = b+c
> b = c
> c = a+b
> 
> We can read the first equation as "a must be computed before b and c".
> So we can construct a graph whose edges mean "source should be
> computed before target". In this case it is:
> 
> a -> b
> a -> c
> b -> c
> c -> a
> c -> b
> 
> If this graph has no cycles the problem is simple: just do a
> topological sort and the problem is solved in O(V+E). If the graph has
> cycles then we need to break them by introducing temporaries. Without
> looking at the form of RHS expressions, that is without considering
> computing an expression partially then we are left with two uses for
> temporaries:
> 
> 1. hold the original value of a variable
> 2. hold the result of an expression and write it later to the destination
> 
> Point (1) requires one extra assignment, while point (2) requires two
> extra assignments. The effect is however the same: one of the
> variable's value can be computed as soon as desired. Therefore we will
> only use (1). [NOTE that your approach used (2) and hence is clearly
> sub-optimal].

First, a remark here, case (2) can *always* be reduced to case (1). 
Suppose you are saving the expression for variable a into a temporary 
variable t, and assign a later when you don't need the old value anymore:

...
t <- some expression
... <-  ... a ...
... <-  ...
... <-  ... a ...
a <- t
...

This can be replaced by the assignments:

...
t <- a
a <- some expression
... <- ... t ...
... <- ...
... <- ... t ...
...

(Of course, you can also do the converse transformation.)

Thus, as you noticed, all you have to do is decide for which variables 
we should keep the old values, and then compute all the expressions with 
them (using a topological sort of what remains).

> The effect of (1) (and (2)) on the constructed graph is that all
> in-edges of a variable are removed. So we have reduced the problem to
> this: "Given a graph mark as few nodes as possible such that the after
> removing in-edges of marked nodes we obtain a tree".

That's true. But now, let's make a remark: since the marked nodes have 
only out-edges, they cannot participate in any cycle anymore. So, in 
fact, we can also remove their out-edges, which means remove the node 
completely from the graph.

The problem can now be rephrased as: "Given a directed graph, find a 
minimal set of vertices whose deletion leaves an acyclic graph". To put 
it another way, "given a directed graph G=(V,E), find a minimal subset 
of vertices V' such that every cycle of G has a vertex in V'".
This problem is known as the minimum feedback vertex set, and (sadly) it 
is NP-complete:
http://www.nada.kth.se/~viggo/wwwcompendium/node19.html#3336

Last, to comment Skaller's last post:

skaller wrote:
 > However, your solution, whilst correct, breaks one of
 > the rules: one of the RHS is refering to the old value
 > of 'c' using the name 't'. The original rules required
 > only assignments using the original LHS variables,
 > the original RHS expressions, and the temporaries,
 > that is, only permitted buffering the RHS expressions,
 > not old values of variables.
 >
 > Allowing *both* RHS expressions (new values of variables)
 > and LHS variables (old values of variables) makes sense,
 > however, as your example demonstrates. And also seems
 > to make solving the problem harder :)

Actually, they are fully equivalent. If you think about the graph 
defined above, you want to find the set of variables, for which you will 
compute their expressions, save them into temporary variables, compute 
the rest, and affect those variables. This now amounts to deleting 
*out-edges* for the elected variables in the graph. Now, use the same 
arguments and you get exactly the same graph problem.

To summarize:
- build the graph as described by Radu
- use an approximation algorithm for a minimum feedback vertex set
- compute expressions for variables in this set, and store results in 
temporary variables
- use topological sorting on the subgraph to find a correct ordering for 
the other variables
- assign temporary variables to their final destination

Hope this helps...

Pascal

PS: I am not sure this conversation is much OCaml-related anymore...

Re: [Caml-list] Re: paralell assignment problem

[skaller]

On Wed, 2005-02-09 at 22:34, Pascal Zimmer wrote:

> The problem can now be rephrased as: "Given a directed graph, find a 
> minimal set of vertices whose deletion leaves an acyclic graph". To put 
> it another way, "given a directed graph G=(V,E), find a minimal subset 
> of vertices V' such that every cycle of G has a vertex in V'".
> This problem is known as the minimum feedback vertex set, and (sadly) it 
> is NP-complete:
> http://www.nada.kth.se/~viggo/wwwcompendium/node19.html#3336

Ah, thanks, it reduces to a known problem.

> Last, to comment Skaller's last post:

[]

> Actually, they are fully equivalent.

Your argument is fully convincing, thanks (I'm relieved,
since I've already implemented the algorithm :)

> Hope this helps...

Indeed, thanks to everyone who contributed!

> PS: I am not sure this conversation is much OCaml-related anymore...

It probably wasn't in the first place, but this list has a lot
of friendly people with theoretical knowledge and analytical skills:
seemed like a good place to ask.

However, the algorithm could be applied in Ocaml in the circumstances
which lead me to the problem, namely tail rec-call optimisation.

Is Ocaml doing this already?

>From the ackermann tests I did it looks like stack
frame size is dominant in heavily recursive routines,
and the extra variables introduced by a non-optimal tail
call are only temporaries, so perhaps it isn't worthwhile,
as Marcin suggested, but then I don't know anything about 
how Ocaml works..

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net