Lambda expressions are used to create procedures in LISP. We can bind the created procedure to a name using define in order to subsequently call it with that name. Let’s see an example with a procedure binded to square:
(define square (lambda (x) (* x x)))
> (square 2) 4
However, we’re not forced to bind the lambda procedure. In that case, we will say the procedure is anonymous. Since the procedure isn’t binded to any name to call it, we’re forced to apply it as soon as we create it, as in:
> ((lambda (x) (* x x)) 2) 4
The matter of this post will be to see how to create anonymous recursive procedures using Scheme (a LISP dialect).
Recursion
Recursion takes place when a procedure calls itself. One of the most common examples is the recursion of the fibonnacci sequence, where the nth element of the sequence is:
fibo(n)= fibo(n-1) + fibo(n-2)
This sequence requires two initial feed values, which are usually 0 and 1. The resulting sequence is then:
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
With the exception of the first two elements, each value is the addition of the two values that come before it. We can implement this idea with:
(define (fib n)
(define (fibo v1 v2 c n)
(cond [(= n 1) v1]
[(= c n) v2]
[else (fibo v2 (+ v1 v2) (+ c 1) n)]))
(fibo 0 1 1 n))
> (fib 1) 0 > (fib 2) 1 > (fib 3) 2 > (fib 4) 3 > (fib 5) 5 > (fib 6) 8 > (fib 7) 13
The procedure fib is just a wrapper function for the recursive procedure fibo, which takes as parameters the two initial values of the sequence (0 and 1), a counter c that increments until the nth value of the sequence is reached and n itself.
Let’s see how to implement fib with anonymous recursive procedures.
Fibonnacci sequence using anonymous recursive procedures
The difficulty of using anonymous procedures to express recursion resides in the fact that a recursive procedure calls itself. With an anonymous procedure, we don’t have any name assigned to call the procedure with. We will remediate this fact by passing the recursive procedure as a parameter to itself. Finally, we will need a second anonymous procedure to start calling our main anonymous procedure. Let’s see how would this look like by parts.
Creating the main recursive lambda procedure
The recursive procedure we defined before was (fibo v1 v2 c n). The equivalent lambda procedure would be:
(lambda (v1 v2 c n)
(cond [(= n 1) v1]
[(= c n) v2]
[else (call-self v2 (+ v1 v2) (+ c 1) n)]))
Like we stated before, the issue is that we don’t have any name defined for this procedure to call itself as we intended to do in (call-self v2 (+ v1 v2) (+ c 1) n).
To remediate this, we will pass a procedure as an extra parameter:
(lambda (fibo v1 v2 c n)
(cond [(= n 1) v1]
[(= c n) v2]
[else (fibo fibo v2 (+ v1 v2) (+ c 1) n)]))
And this procedure will be applied at:
(fibo fibo v2 (+ v1 v2) (+ c 1) n)
Which is just applying the procedure fibo with the arguments: fibo, v2, (+ v1 v2), (+c 1) and n. With this mechanism, we’re effectively creating a recursive call because we apply the same procedure that is passed as an argument until we reach one of the base cases.
The next difficulty is that we need to pass as an argument the very procedure we’re creating. We could write the same procedure twice, once to create it and once as an argument:
(define (fib n)
([lambda (fibo v1 v2 c n)
(cond [(= n 1) v1]
[(= c n) v2]
[else (fibo fibo v2 (+ v1 v2) (+ c 1) n)])]
(lambda (fibo v1 v2 c n)
(cond [(= n 1) v1]
[(= c n) v2]
[else (fibo fibo v2 (+ v1 v2) (+ c 1) n)]))
0
1
1
n))
fib is just a wrapper function. The interesting part is that we’re applying a lambda procedure (the part in square brackets []) and passing a similar procedure as an argument (next to the other arguments v1 = 0, v2 = 1, c = 1 and n. This fib will yield the same results as the fib that was defined earlier!
Using a helper procedure to call the recursive procedure
However, we can do better. In order to avoid having to write the same procedure twice, we can use a helper function that will call the main procedure:
(lambda (fn v1 v2 c n) (fn fn v1 v2 c n))
See that if we pass a procedure fn to this procedure, it will apply fn to the rest of the arguments. Which is precisely how we applied fibo before.
Putting these two pieces together:
(define (fib n)
([lambda (fn v1 v2 c n) (fn fn v1 v2 c n)]
(lambda (fibo v1 v2 c n)
(cond [(= n 1) v1]
[(= c n) v2]
[else (fibo fibo v2 (+ v1 v2) (+ c 1) n)]))
0
1
1
n))
See that the helper lambda is the operator. We have enclosed it in square brackets []. This procedure is called with the main lambda procedure as an argument, together with 0, 1, 1 and n.
Which effectively defines the recursive lambda procedure that we intended!
In conclusion
We have seen how to create anonymous recursive procedures. In order to store the procedure and apply it recursively, it’s necessary to include it as a parameter. Finally, a second procedure can be used to call it with the rest of its parameters.