[metapost] Re: recursion in MP/MF

[Laurent SIEBENMANN]

Hi all,

Laurence Finston formulated the following caveat in
reaction to my program "Hit.mp" at

http://topo.math.u-psud.fr/~lcs/graphics/

It was designed to find all intersection points of
(almost) arbitrary composite bezier paths -- without the
preprocessing that B. Jackowski's program still required.

 > However, I think it would be worthwhile to consider whether you
 > couldn't just put the subpaths onto an array and loop 
 > over the array until some condition is met.

The ensuing discussion of "fullfledged recursion",  versus
"tail recursion" (as in loops) --- by Laurence Finston
Lars Engebretsen, Taco Hoekwater, Hans Hagen,
B_Jackowski, and others was particularly helpful to me. I
loath having to use syntax without its elucidation in
terms of physical or at least virtual machines.

I did not make any attempt to use 'tail recursion' first
off because that sort of code is considerably harder to
write AND to understand. If recursive reasoning were
purged from geometry and combinatorics only charred
treestumps would remain!

But yes, given that MF/MP arrays are dynamic 'tail
recursion' is a workable engineering solution to what
B.Jackowski considers to be a nasty bind in MP/MF

 > The ``true'' recursion, however, is still
 > discriminated in MP/MF -- the parameter stack is too
 > small to use recursive techniques in practice. In
 > 1994, during the (mentioned in one of my previous
 > letters) conference in Sobieszewo, Poland, Marek
 > Ry\'cko and I complained about it; then, a few years
 > later, I resumed the problem on the <metafont at ens.fr>
 > list, giving the following example: [...] Now is much
 > better: the program breaks for much larger n, i.e.,
 > n=31...

Taco, commented:

 > I also like recursion. It is unfortunate that precisely
 > this part of MP/MF cannot easily be changed. Knuth uses
 > the (compile-time) size of the param stack to
 > differentiate between the three parameter types, making
 > it hard to manage the stack dynamically. 

This suggests two questions:

(1) Could one not use just the insignificant byte of the
param stack sizes to differentiate between the three
parameter types and thus make dynamic stack admin
possible?

and failing that I ask

(2) Why have precompiled stack sizes not kept abreast of
available RAM in newer computers?

 > This is much more of a problem in MP than in TeX
 > because graphics often relate themselves well to
 > recursive algorithms.

In other words, how can one expect geometers to adopt MP,
as an intimate professional tool if their favorite mode
of reasoning is hobbled?

Cheers

Laurent S

PS. While it is hazardous to predict a tail recursion
solution before it is posted, I point out that the
quantity of extra 'array' data necessary  seems
acceptable:- If we are to find 100 intersection points
then the parameter interval of the first path pp is going
to be broken into about 100 time intervals. Think of
these as leaves on a binary tree. Unfortunately, we
perhaps also want to store the interior nodes. But we can
naturally associate to each intersection point the
interior node that is the interval in which it is first
discovered, and this counts all interior nodes.  Hence an
array of about 200 time intervals is (more than?)
adequate. At any rate, RAM storage for the 100
intersection points, their times on both curves and their
correspondence will be of the same order of magnitude.

Questions. What is the RAM cost of an 'array' element of
type pair?  Is there some way recycling a useless array 
elements similar to TeX's \let \macroxxx=\undefined?