Re: [stack] disallowing recursive definitions

> Recently, I mentioned that if you disallow recursive definitions, then
>  definitions can be thought of as macros or rewrite rules. In other
>  words, you can replace every occurrence of foo in a program with foo's
>  definition and then remove the definition without changing the meaning
>  of the program. It is therefore trivial to remove all definitions in a
>  program and be left with only a single function that only uses
>  primitives built in to the system.
>
>  This dual view of definitions as functions and definitions as rewrite
>  rules is, at least, aesthetically appealing. I began to think of what
>  some other benefits of disallowing recursive definitions might be:
>
>  1. It isn't necessary to do tail call optimization; an appropriate
>  combinator is used instead.
>  2. The type system and formalization of the language in general are
>  simplified. A restriction on recursive definitions may actually be a
>  requirement for a truly compositional type system.
>  3. WIth a small addition to the type system, it becomes possible to
>  prove that the stack will not overflow given the correct set of
>  recursive combinators. (Combinators like linrec would need to be
>  disallowed or specially handled.)
>  4. Similarly, it becomes possible compute the maximum number of items
>  that will ever be on the stack, and pre-allocate a stack of exactly
>  the right size upon program initialization.
>  5. It allows additional ways of presenting code, such as an editor
>  that can expand a definition inline to show what it does while still
>  displaying a program with the same meaning.
>  6. It becomes possible to prove termination when using recursive
>  combinators that always terminate given that their arguments always
>  terminate (such as primrec).
>
>  There are likely other benefits that I'm missing.
>
>  The question therefore is how critical recursive definitions actually
>  are. They're not necessary in an absolute sense; any recursive
>  function can be expressed using while. Essentially, it seems like
>  disallowing recursive definitions has the same sort of tradeoff as
>  disallowing multiple references to the same value (and therefore
>  enforcing linearity): Many nice properties emerge and things are
>  simplified, but it may simply be too much of a pain. I think it may be
>  worth a shot.
>
>  Thoughts?
>
>  - John

Strictly speaking, recursive functions aren't necessary. However, they
make code a lot more readable than directly using combinators which
take 4 or 5 quotations. Try expressing the Magic Five algorithm (see
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22)
to get the median of an array in linear time (for guaranteed O(n log
n) Quicksort) in terms of a recursive combinator. It'd be really hard,
and I'm not sure which combinator would be appropriate. So, maybe you
don't want recursive functions strictly in the minimal formalized
subset of your language, but, like lexically scoped variables, it
might be nice if the compiler did the appropriate transformations to
allow them in user code.

Also, about restricting the set of combinators so the stack doesn't
overflow: I'm not sure if that's worth it. If there's no explicit
recursion, you'd want the set of combinators included to be as general
as possible. (There is a combinator, condnestrec, which encodes
general recursion, and this would obviously not be included if you
want to prevent stack overflow.) Things like depth-first search are
much easier to express on the system stack (which could overflow from
certain graphs) than on an explicit stack, though strictly speaking
it's possible either way (and I guess in some cases you would actually
want to use an explicit stack).

Dan