Recursion in PicoLisp

Introduction to Recursion

As a reminder, here is a quote from Wikipedia about the general concept of recursion:


Recursion in computer programming is exemplified when a function is defined in
terms of simpler, often smaller versions of itself. The solution to the
problem is then devised by combining the solutions obtained from the simpler
versions of the problem. One example application of recursion is in parsers
for programming languages. The great advantage of recursion is that an
infinite set of possible sentences, designs or other data can be defined,
parsed or produced by a finite computer program.



Sometimes a picture says more than 1000 words, so here are two links to illustrations of recursion at work: Cathy's Recursion, and Recursive Function Calls.



Examples of Recursion in PicoLisp

Without Language Extension

Here is an example taken from PicoLisp by Example, demonstrating the special case of a pair of functions that are mutually recursive:


Mutual recursion

Two functions are said to be mutually recursive if the first calls the
second,and in turn the second calls the first.


(de f (N)
  (if (=0 N)
    1
    (- N (m (f (dec N)))) ) )

(de m (N)
  (if (=0 N)
    0
    (- N (f (m (dec N)))) ) )


Here is another example, again taken from PicoLisp by Example, implementing the famous Towers of Hanoi problem with recursive function move (calling itself in the function body):

Towers of Hanoi

In this task, the goal is to solve the 'Towers of Hanoi' problem with
recursion.

(de move (N A B C) # Use: (move 3 ’left ’center ’right)
  (unless (=0 N)
    (move (dec N) A C B)
    (println ’Move ’disk ’from A ’to B)
    (move (dec N) C B A) ) )


With Language Extension

In PicoLisp, as a member of the Lisp family, its easy to extend the language with new control structures (quoted from PicoLisp by Example):


Some programming languages allow you to extend the language. While this can be
done to a certain degree in most languages (e.g. by using macros), other
languages go much further. Most notably in the Forth and Lisp families,
programming per se is done by extending the language without any formal
distinction between built-in and user-defined elements.



Taking advantage of PicoLisp's shallow dynamic binding, Alexander Burger implemented anonymous recursion by extending the language with two functions, as described in the FAQ:


In PicoLisp, function definitions are normal symbol values. They can be
dynamically rebound like other variables. As a useful real-world example, take
this little gem:

(de recur recurse
   (run (cdr recurse)) )

It implements anonymous recursion, by defining recur statically and recurse
dynamically. Usually it is very cumbersome to think up a name for a function
(like the following one) which is used only in a single place. But with recur
and recurse you can simply write:

: (mapcar
   '((N)
      (recur (N)
         (if (=0 N)
            1
            (* N (recurse (- N 1))) ) ) )
   (1 2 3 4 5 6 7 8) )
-> (1 2 6 24 120 720 5040 40320)

Needless to say, the call to recurse does not have to reside in the same
function as the corresponding recur.



recur and recurse in detail

Definition

Lets repeat and investigate the definition of recur and recurse:


(de recur recurse
   (run (cdr recurse)) )



To understand this (exceptionally short) definition, we should have a look at the documentation of run first:


(run 'any ['cnt ['lst]]) -> any

    If any is an atom, run behaves like eval. Otherwise any is a list, which
    is evaluated in sequence. The last result is returned. If a binding
    environment offset cnt is given, that evaluation takes place in the
    corresponding environment, and an optional lst of excluded symbols can be
    supplied. See also up.

    : (run '((println (+ 1 2 3)) (println 'OK)))
    6
    OK
    -> OK



Thus, the definition of recur assumes that function argument recurse is a list, and run evaluates the CDR of this list in sequence, returning the last result. But how does this minimal two-line definition manage to define recur statically and recurse dynamically at the same time, thus enabling anonymous recursion? The answer to this question can be found investigating how PicoLisp handles the function argument recurse. Here is a quote from the PicoLisp Tutorial:


Normally, PicoLisp evaluates the arguments before it passes them to a function
[...] In some cases you don't want that. For some functions (setq for example)
it is better if the function gets all arguments unevaluated, and can decide
for itself what to do with them.

For such cases you do not define the function with a list of parameters, but
give it a single atomic parameter instead. PicoLisp will then bind all
(unevaluated) arguments as a list to that parameter.


: (de foo X
   (list (car X) (cadr X)) )        # 'foo' lists the first two arguments

: (foo A B)                         # Now call it again
-> (A B)                            # -> We don't get '(1 2)', but '(A B)'

: (de foo X
   (list (car X) (eval (cadr X))) ) # Now evaluate only the second argument

: (foo A B)
-> (A 2)                            # -> We get '(A 2)'



So recurse is a single atomic parameter, and all (unevaluated) arguments given to recur are bound as a list to that parameter. When the definition of recur is read, two global symbols are created: recur, with its function definition as value, and recurse, with the initial value NIL. recur is just another statically defined function that can be called everywhere in a PicoLisp program. When it is called, the actual value of symbol recurse (which might be NIL or something else) is saved, and recurse is dynamically bound to a list containing all (unevaluated) arguments given to recur. This dynamic binding holds as long as the call to recur did not finish. After the call finished, recurse is set back to its initial (saved) value, e.g. NIL. This is similar to binding symbols with the let function inside of function definitions.

Documentation

Here is the official documentation of recur and recurse:


(recur fun) -> any
(recurse ..) -> any
    Implements anonymous recursion, by defining the function recurse on the
    fly. During the execution of fun, the symbol recurse is bound to the
    function definition fun. See also let and lambda.



With the preparation of the last sections, we should be able to understand how 'defining recurse on the fly' works. The symbol recurse is already created in the definiton of recur, but is bound dynamically to the (unevaluated) function given as argument to recur everytime recur is called. The following examples will illustrate how this works.

Walk Through some Examples

Example 1
This is the example given earlier in this article.


: (mapcar
   '((N)
      (recur (N)
         (if (=0 N)
            1
            (* N (recurse (- N 1))) ) ) )
   (1 2 3 4 5 6 7 8)  )
-> (1 2 6 24 120 720 5040 40320)




In this example, recur is called with the following args:


(N) (if (=0 N) 1 (* N (recurse (- N 1))))



These args are bound unevaluated as a list to recurse, thus the CAR of this list is (N), the CDR is the (if ...) expression. In other words, what happened could be written like this


(de recurse (N)
  (if (=0 N)
    1
    (* N (recurse (- N 1))) ) )



but this is a statically defined named function, in contrast to the dynamically defined anonymous function defined on the fly above.

The function body of recur looks like this


(run (cdr recurse))



thus


(if (=0 N) 1 (* N (recurse (- N 1))))



is recursively evaluated until the conditon (=0 N) is true. The mapcar calls recur 8 times, each time assigning a different value from the list (1 2 3 4 5 6 7 8) to N.

Example 2
This is the example that comes with the official documentation of the recur function:


    : (de fibonacci (N)
       (when (lt0 N)
          (quit "Bad fibonacci" N) )
       (recur (N)
          (if (> 2 N)
             1
             (+
                (recurse (dec N))
                (recurse (- N 2)) ) ) ) )
    -> fibonacci
    : (fibonacci 22)
    -> 28657
    : (fibonacci -7)
    -7 -- Bad fibonacci



Here, the call to recur defines recurse as the following anonymous function (remember there is no lambda function in PicoLisp, see this FAQ):


'((N) (if (> 2 N) 1 (+ (recurse (dec N)) (recurse (- N 2)))))



thus by calling run on the list's CDR the body of the if expression is repeatedly evaluated until (> 2 N) is true.

Performance Issues

Speed Comparison 'Recursion vs Iteration'

The following quote from the Emacs Lisp Manual is just one of many warnings about the unsufficient speed of recursion found in programming language books:


Use iteration rather than recursion whenever possible. Function calls are slow
in Emacs Lisp even when a compiled function is calling another compiled
function.



How does recursion perform in PicoLisp? Alexander Burger made a little comparison between recursion and iteration. Running


# Recursive
(bench
  (do 1000000
     (let (N 100)
        (recur (N)
           (if (=0 N)
              1
              (* N (recurse (dec N))) ) ) ) ) )

# Iterative
(bench
  (do 1000000
     (let N 1
        (for I 100
           (setq N (* I N)) )
        N ) ) )

# Simple
(bench
  (do 1000000
     (apply * (range 1 100)) ) )


results in


   13.161 sec
   7.331 sec
   7.413 sec
   -> 9332621544394415268169923885626670049071596826438162146859296389521
      7599993229915608941463976156518286253697920827223758251185210916864
      000000000000000000000000



So the recursive version takes about twice as long as the other two.

What about Tail-Recursion?

The following (lengthy) quote from Wikipedia explains the term tail-recursion that inevitably shows up when recursion is discussed:


In computer science, a tail call is a subroutine call that happens inside
another procedure as its final action; it may produce a return value which is
then immediately returned by the calling procedure. The call site is then said
to be in tail position, i.e. at the end of the calling procedure. If any call
that a subroutine performs, such that it might eventually lead to this same
subroutine being called again down the call chain, is in tail position, such a
subroutine is said to be tail-recursive, which is a special case of recursion.
Tail calls need not be recursive – the call can be to another function – but
tail recursion is particularly useful, and often easier to handle in
implementations.

Tail calls are significant because they can be implemented without adding a
new stack frame to the call stack. Most of the frame of the current procedure
is not needed any more, and it can be replaced by the frame of the tail call,
modified as appropriate (similar to overlay for processes, but for function
calls). The program can then jump to the called subroutine. Producing such
code instead of a standard call sequence is called tail call elimination, or
tail call optimization. Tail call elimination allows procedure calls in tail
position to be implemented as efficiently as goto statements, thus allowing
efficient structured programming. In the words of Guy L. Steele "in general
procedure calls may be usefully thought of as GOTO statements which also pass
parameters, and can be uniformly coded as [machine code] JUMP instructions"
[...].



Does tail-recursion play a role in an interpreted language like PicoLisp? Here is the answer of Alexander Burger to a (not so frequently asked) question by me on the PicoLisp Mailing list:


Q: The notion of 'tail-recursion' does not have any meaning in an
interpreted language like PicoLisp, since its only for compiler
optimizations -right?


A: Yes, because you cannot do TCE (Tail Call Elimination) while interpreting
List structures. You have to do it in the compiler, as it requires some
analysis of the code structure.

In general, I think recursion is overvalued. It used to excite computer
scientists in the dark ages of computing, causing awe and wonder when a
subroutine was able to call itself.

In a languge like PicoLisp, recursion is only necessary when you have
recursive data structures (like trees), and those cases are typically
not tail recursive.

For most common cases you directly write a loop with 'do', 'loop',
'while', 'until', 'for' etc., which let you express more clearly what
the code is supposed to do.

To my feeling, TCE would be very inappropriate for PicoLisp, as it is
rather against the "spirit": It makes things complicated, does something
behind the screen which is not controlled by the programmer, and does
inefficient things where there is a better, straight-forward and faster
solution (i.e. explicitly write a loop statement, where you want to
loop).

https://picolisp.com/wiki/?recurinpicolisp

09apr17   tj