Re: [stack] disallowing recursive definitions

John Cowan <[email protected]> wrote:
> William Tanksley, Jr scripsit:
>  > 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.

I don't know the term "lambda-lift", and Google knows of it mainly as
a bunch of source files (I did find a 1985 paper on the topic, but
it's a little dense to answer my questions easily). My question: does
that include code copying -- in other words, is it possible for a
single stretch of code-text in the original GOTO program to be present
in two places in the lambda-lifted code text?

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

Well, if you're really using GOTOs optimally (or pessimally) you don't
have ANY structures, so the language can't stop you.
http://catb.org/jargon/html/story-of-mel.html

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

Interesting. I have a very hard time picturing this.

I suppose that's why GOTOs are considered harmful.

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

Now, interestingly, a concatenative tail-call cannot do this. Does
this imply some superiority for concatenative optimizers? :-)

-Wm