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.
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).
http://picolisp.com/wiki/?recurinpicolisp
| 10apr21 | tj |