[metapost] Re: recursion in MP/MF

[Larry 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/

"Hit.mp" 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.

Excellent suggestion; I am still mulling it over.

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.

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

But yes, given that MF/MP arrays are dynamic, 'tail
recursion' seems 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 [rather than n=29] ... 

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?

Failing that I ask

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

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

Indeed! How can one expect geometers to adopt MP, as an
intimate professional tool if their favorite mode of
reasoning is hobbled?

Cheers

Laurent S

 %%%%%%%%%%%%%%%%%%%%%%

TEXHNICAL 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 have 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/need 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.

Laurence Finston suggested use of an array.  It seems to
me that the use of a home-made stack (housed in an array
for lack of alternatives?) might be a slightly better
solution. Mostly on the hope that the program could
remain 'almost' unchanged (unmutilated!?) -- each
recursive intersection function call being replaced by a
by a 'push' of a time interval onto the stack. The
intersection function would 'pop' its time interval
as it launches.  Incidentally, in this scheme the maximum
stack depth might be far less than 100.

QUESTIONS. What is the RAM cost of an 'array' element of
type pair?  Is there some way of recycling useless
array elements -- maybe similar to TeX's \let
\macroxxx=\undefined? Is there a good example of 
the use of a stack in MF/MP programming.