Lisp and stack overflow

This semester I am teaching a course which over the years has had many names (Computational algebra, Symbolic computation, Categories and automata, etc, etc) but which is really my thoughts about relations between algebra and computer science. For some years I used Maple as an illustrative programming language, but it is expensive, and the faculty in Como has withdrawn support, closing the laboratory which had Maple installed a couple of years ago. So this year at the last moment I thought of using Common Lisp (Clisp). To be honest I am not a programmer though I have written programs in a large number of different languages but not in Lisp.
Perhaps strangely for a category theorist I have always been rather negative towards functional style programming.
As a first example, I wrote the following informally described programs (in which o is just a symbol):

add(successor(x),y)=successor(add(x,y))
add(o, y)=y;


multiply(successor(x),y)=add(multiply(x,y),y)
multiply(o,y)= o;


factorial(successor(x))=multiply(successor(x),factorial(x))
factorial(o)=successor(o).

I was surprised that with these programs I could calculate at most factorial(7) without stack overflow (by 7 I mean of course successor(successor(...o)))))))).  I would have thought that a language based on recursion would support recursion to the limit of the memory of the machine. (My first effort with a language or a machine is to try to break it, but this was too easy.)

Reading further about Lisp I realised that you are supposed to write not general recusion but "tail recursion".
Tail recursion is really just "while". I would like to give an explanation of tail recursion in terms of the Elgot automata we introduced in the paper P. Katis, N. Sabadini, R.F.C. Walters, Bicategories of processes. Journal of Pure and Appled Algebra, 115:141-178, 1997.

An Elgot automaton is a function g : X + U → U + Y (where + means disjoint union). The partial function fun(g) : X → Y computed by g is defined as follows: given x in X apply g repeatedly until the result lies in Y. The result, if it exists is then fun(g)(x).
 Notice that g can be broken into two parts: g1 : X → U + Y and g2 : U →U + Y; g1 is an initialization step  and g2 is an iteration step.

Let us look at an example, namely calculating factorial given multiplication.
Take X=N the natural numbers. Take U=NxN, and take Y=N.
The initialization step g1: n → (n,1) in NxN.
The iteration step g2 : NxN → NxN + N is defined by (n,p) → (n-1, p*n) if n>0, else (0.p) → p.
Clearly the function fun(g) calculated by the Elgot automaton g is factorial; this is a usual imperative program for factorial.

Going back to the general Elgot automata, notice that g2 defines a partial function also, from U to Y, namely the result of iterating g2 on the whole of U. Calling this "auxiliary" partial function auxfun(g) it is clear that fun(g) = (auxfun(g) | 1Y) • g1. But also the auxiliary function satisfies a fixed point equation, namely that
auxfun(g)(u)=auxfun(g)(g2(u))
since in a computation of auxfun(g)(u) (iterating g2) all the values passed through arrive (if they arrive at all) in the same value auxfun(g)(u).

In the example above of the program for factorial the auxiliary function is easily seen (by iterating g2) to be
(n,p)  →  (0, factorial(n)*p).

This equation auxfun(g)(u)=auxfun(g)(g2(u)) may be taken to be a recursive program for auxfun, and then fun(g) is a composite. A recursive evaluation consists in the steps
auxfun(g)(u)=auxfun(g)(g2(u))=auxfun(g)(g2(g2(u))=auxfun(g)(g2(g2(g2(u)))= ... until a value which would land in Y arrives. This is tail recursion - it involves only one application of auxfun.

The idea then is this: to do tail recursion think of a calculation using iteration. This involves introducing new state (U), initializing (g1) and also an auxiliary function (g2). The function you wish to calculate then is a composition of the initialization and the tail recursion of the auxiliary function.

Let us write tail recursive programs for addition, multiplication and factorial.

Addition
For addition there is no need to introduce new state. The internal state is NxN, the same as the domain of addition. The iterative step is (m,n) → (m-1,n+1) with exit when the first variable is 0.
Hence the recursive definition of and is:

Add(o,y)=y
Add(successor(x),y)=Add(x,successor(y)).

Multiplication
For multiplication the iterative program introduces a new variable p.
The initialization is (x,y) → (x,y,o).
The iterative step is (x,y,p) → (x-1,y, p+y).
Exit is (o,y,p) → p.

The auxiliary function auxMultiply is (x,y,p) → x*y+p.

The recursive program for auxMuliply is:

auxMultiply(o,y,p)=p
auxMultiply(s(x),y,p)=auxMultiply(x,y,Add(p,y))

Then 
Multiply(x,y)=auxMultiply(x,y,o).

Factorial 
For calculating factorial(x) by iteration one introduces a new variable p.
The initialization is x → (x,1).
The iterative step is (x,p) → (x-1,x*p).
The exit is (o,p)  → p.

The auxiliary function auxFactorial is (x,p) → (factorial(x)*p).
The recursive program for auxFactorial is:

auxFactorial(o,p)=p
auxFactorial(s(x),p)=auxFactorial(x,s(x)*p).

Then 
Factorial(x)=auxFactorial(x,1).

Remark The Elgot automata form the arrows of a symmetric monoidal category with feedback with delay. In fact they are a case of a general construction for universally adding such feedback with delay to a symmetric monoidal category (see P. Katis, N. Sabadini, R.F.C. Walters, Feedback, trace and fixed-point semantics , Theoret. Informatics Appl. 36:181-194 (2002)). The product monoidal structure on Sets gives Mealy automata, variations of which are being studied for application to circuits by Miklos Bartha. There are close relations with the work of Joyal, Street and Verity on traced monoidal categories.


Remark The idea of McCarthy to form a language with a data type (s-expressions) so that programs become data, plus the idea that programs should be equational (recursive) definition of functions makes a very interesting language. However I remain convinced that the object of programming is not just to describe functions but instead systems and their composition.