Re: [stack] disallowing recursive definitions

William Tanksley, Jr scripsit:

> That feels questionable to me. GOTOs can be conditional,

True, but that doesn't matter: you translate the conditional GO into a
conditional invocation of the function corresponding to the labeled code.

> and tags can be inside conditions as well.

In a Lisp tagbody, tags are only recognized at the top level, so a label
within a conditional becomes a label at the top level of a nested tagbody
within the conditional.  GOs are allowed to go to a tag in any tagbody
they are lexically nested in.  In order to implement this using functions,
you have to lambda-lift the functions generated from any nested tagbody,
but that again is well-understood, local, and easily performed.

This actually allows rather more of a mess than even "normal" structured
programming languages with GO TO allow.  Most languages don't permit you
to GO TO into a construct from outside, though older versions allowed jumps
out-then-back-in (Fortran 66) and/or in-and-then-back-out (simple Basics
and others).  However, if you lambda-lift everything, you can actually
jump around however you please.

> In short and to be formal, it seems to me that tagbodies don't form
> properly nested trees, as functions must... I think they form digraphs.

A plausible way to think about tail recursion is to assume an infinite
return stack, and then postpone all the returns until the end of the
program (when they do not actually have to be performed).  So although the
call graph is a tree, the actually extant part of it is a random directed
graph, and all the retracing is simply banished from consideration.

This is essentially how Chicken implements Scheme, except that because
the control stack (the C stack) is not infinite, it is necessary to reset
it periodically, banishing any embedded data structures that are still
live to the C heap.  In effect, the C stack becomes the first generation
of the Scheme heap.

> An interesting point. A recursive tail call in an applicative language
> can do one thing that a simple GOTO cannot: it can, at one stroke,
> change the value of all the parameters of the function to something
> else. This would certainly be sufficient to make an applicative
> theorist blanch...

Absolutely.  LAMBDA = GOTO + argument passing; that's what makes it
"ultimate".

-- 
Cash registers don't really add and subtract;           John Cowan
        they only grind their gears.                    [email protected]
But then they don't really grind their gears, either;   
        they only obey the laws of physics.  --Unknown