> Next Lambda functions
< Previous Lists

5.8.2.2 Tail recursion

The first subtlety of the language of Guile is the one big hurdle to understanding it. Take a deep breath and go slowly here.

Guile and other lisp-derived languages have a feature unique to them: a procedure can call itself infinitely without consuming all the memory or other resources of the laptop. More precisely, when a procedure calls itself as its last action, it is executed as a jump back to the top of the procedure, rather than as an actual procedure call.

The following adds up the numbers from one to ten, inclusive (you can get the same answer as (+ 1 2 3 4 5 6 7 8 9 10), but that would not be very illuminating).

      (let loop 
           ((x 1) (y 0))
           (if (<= x 10) 
               (loop (1+ x) (+ x y)) 
               y))

We will take this very slowly. At the beginning is a call to a procedure bound to the symbol ‘let’. This takes a symbol to refer to a new procedure, a list of arguments the new procedure takes (in this case two, bound to the symbols ‘x’ and ‘y’) and which gives initial values to the arguments (in this case 1 and 0, respectively), and then there are a list of procedure calls which define the new procedure. ’Let’ not only defines a new procedure, but simultaneously binds it to the symbol given as first argument (here, ‘loop’), and calls it immediately with the default arguments ‘x’ = 1 and ‘y’ = 0.

The arguments to our new procedure are taken to be a counter from 1 to 10 (‘x’), and the result of adding x’s together, called ‘y’.

Now to the procedure body. We don’t actually want infinite recursion, but want to stop somewhere, which we do by comparing ‘x’ with 10. The procedure bound to the symbol ‘if’ takes three arguments. Depending on the value of the first argument, either the second or third arguments are executed. In our case the first argument compares ‘x’ with 10, and if it is less the second argument to ‘if’ is executed. This is the fantastic recursion I was telling you about: the new procedure calls itself! Note that the procedure will do nothing else after the recursive call, hence this is true tail recursion and the call is genuinely infinitely recursive. We call the new procedure with an ‘x’ value incremented by 1 (the effect of the procedure bound to the symbol ‘1+’), and with a ‘y’ value being the sum of the current ‘x’ and ‘y’ values.

If our comparison of ‘x’ with 10 indicated that ‘x’ was in fact greater than 10, then the last part of the ‘if’ procedure would be executed. This is nothing but the symbol ‘y’, and the effect is to exit the procedure (and all its recursions) with the value that is associated with the symbol ‘y’ at this time (executing a symbol simply returns whatever the symbol was bound to, in this case a number), and this is the sum of the numbers from one to ten! Try it!

I’m sure this all seemed very complicated, both if you’ve never come across computer programming before, or if you are familiar with other procedural-style programming languages (as opposed to ‘functional’ style, which Guile is). However, this kind of reasoning suffuses all Guile programs, and in fact becomes very simple once you get used to the basic idea. Where most languages have a slew of looping constructs with names like ‘do’, ‘for’, ‘while’, ‘goto’ (ha ha), (and Guile has these as well), the fact is that Guile manages with just this form of ‘let’, and this single form is capable of far more sophisticated looping constructs than any of the others.

> Next Lambda functions
< Previous Lists
Copyright © 2010, 2012 DM Bespoke Computer Solutions Ltd
All rights reserved