In Scheme, how do you use lambda to create a recursive function?

Question

I'm in a Scheme class and I was curious about writing a recursive function without using define. The main problem, of course, is that you cannot call a function within itself if it doesn't have a name.

I did find this example: It's a factorial generator using only lambda.

((lambda (x) (x x))
 (lambda (fact-gen)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((fact-gen fact-gen) (sub1 n)))))))

But I can't even make sense of the first call, (lambda (x) (x x)): What exactly does that do? And where do you input the value you want to get the factorial of?

This is not for the class, this is just out of curiosity.

Answer 1

You define it like this:

(let ((fact #f)) 
  (set! fact 
        (lambda (n) (if (< n 2) 1 
                               (* n (fact (- n 1)))))) 
  (fact 5))

which is how letrec really works. See LiSP by Christian Queinnec.

---

In the example you're asking about, the self-application combinator is called "U combinator",

(let ((U  (lambda (x) (x x)))
      (h  (lambda (g)
            (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n))))))))
  ((U h) 5))

The subtlety here is that, because of let's scoping rules, the lambda expressions can not refer to the names being defined. h can not be referenced inside the lambda expression which is established by this let as its value.

When ((U h) 5) is called, it is reduced to ((h h) 5) application, inside the environment frame created by the let form.

Now the application of h to h creates new environment frame in which g points to h's value in the environment above it:

( (let ((g (lambda (g)
               (lambda (n)
                 (if (zero? n)
                     1
                     (* n ((g g) (sub1 n))))))))
      (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n)))))) 
    5 )

The (lambda (n) ...) expression here is returned from inside this new environment frame in which g points to h's value above it - as a closure object. I.e. a function of one argument, n, which also remembers this binding for g.

So when this closure is called, n gets assigned 5, and the if form is entered:

  (let ((g (lambda (g)
               (lambda (n)
                 (if (zero? n)
                     1
                     (* n ((g g) (sub1 n))))))))
      (let ((n 5))
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n))))))

All gs here have - or will have - the same value, the lambda expression (lambda (g) ... (g g) ...), because the same value is being passed as its own argument in all its invocations, however many there will be, depending on n. And thus the (g g) application always gets reduced to the same function of one argument n, serving as our recursive factorial function, which on the next iteration will be called with 4, then 3 etc. - because a function calling the same function as itself is the definition of it being recursive.

Whether it will be a new closure object or the same closure object will be reused, depends on a compiler. This can have an impact on performance, but not on the semantics of recursion.

Each call to (g g) recalculates and recreates the same function of one numeric argument n - the recursive factorial function. Thus the vicious circle is broken, for if we tried to actually include the definition of factorial inside itself by value upfront, that value would have to include the same value inside itself, and that inside itself, and so on without end, and we would have no value at all - since the inclusions would never stop.

But we do not try to put the whole value inside itself - only the promise to re-create it when actually needed. In the regular languages with recursion by name this is achieved by allowing to refer to the value, - which is the recursive function, - by its name. Either way the vicious circle is broken through some kind of an intermediary, some kind of a delaying step.

Answer 2

With a single lambda it's not possible. But using two or more lambda's it is possible. As, all other solutions are using three lambdas or let/letrec, I'm going to explain the method using two lambdas:

((lambda (f x)
   (f f x))
 (lambda (self n)
   (if (= n 0)
       1
       (* n (self self (- n 1)))))
 5)

And the output is 120.

Here,

1. (lambda (f x) (f f x)) is a lambda that takes two arguments, the first one is a lambda (let's call it f) and the second is the parameter (let's call it x). Notice, in its body it calls the provided lambda f with f and x as arguments – the same f.
2. Now, lambda f (from point 1) i.e. self is what we want to use to recurse. See, when calling self recursively, we also pass self as the first argument and (- n 1) as the second argument.
   Thus calling (self self ...) uses the same combination as initiated by (f f ...) – which is the meaning of recursion, i.e. calling self from self: self becomes bound to the second lambda (lambda (self ...) ...) and is passed to self as a value inside its body.
   This passed value being used both as a function in the new call and its argument overcomes the limitation of not being able to give global names to functions, in the lambda calculus, and only using nameless ("anonymous") lambdas.

Answer 3

I found this question because I needed a recursive helper function inside a macro, where one can't use define.

One wants to understand (lambda (x) (x x)) and the Y-combinator, but named let gets the job done without scaring off tourists:

 ((lambda (n)
   (let sub ((i n) (z 1))
     (if (zero? i)
         z
         (sub (- i 1) (* z i)) )))
 5 )

One can also put off understanding (lambda (x) (x x)) and the Y-combinator, if code like this suffices. Scheme, like Haskell and the Milky Way, harbors a massive black hole at its center. Many a formerly productive programmer gets entranced by the mathematical beauty of these black holes, and is never seen again.

Answer 4

Basically what you have is a form similar to the Y combinator. If you refactored out the factorial specific code so that any recursive function could be implemented, then the remaining code would be the Y combinator.

I have gone through these steps myself for better understanding.
https://gist.github.com/z5h/238891

If you don't like what I've written, just do some googleing for Y Combinator (the function).

Answer 5

I like this question. 'The scheme programming language' is a good book. My idea is from Chapter 2 of that book.

First, we know this:

(letrec ((fact (lambda (n) (if (= n 1) 1 (* (fact (- n 1)) n))))) (fact 5))

With letrec we can make functions recursively. And we see when we call (fact 5), fact is already bound to a function. If we have another function, we can call it this way (another fact 5), and now another is called binary function (my English is not good, sorry). We can define another as this:

(let ((another (lambda (f x) .... (f x) ...))) (another fact 5))

Why not we define fact this way?

(let ((fact (lambda (f n) (if (= n 1) 1 (* n (f f (- n 1))))))) (fact fact 5))

If fact is a binary function, then it can be called with a function f and integer n, in which case function f happens to be fact itself.

If you got all the above, you could write Y combinator now, making a substitution of let with lambda.

Answer 6

I was curious about writing a recursive function without using define. The main problem, of course, is that you cannot call a function within itself if it doesn't have a name.

A little off-topic here, but seeing the above statements I just wanted to let you know that "without using define" does not mean "doesn't have a name". It is possible to give something a name and use it recursively in Scheme without define.

(letrec
  ((fact
     (lambda (n)
       (if (zero? n)
         1
         (* n (fact (sub1 n)))))))
  (fact 5))

It would be more clear if your question specifically says "anonymous recursion".

Answer 7

(lambda (x) (x x)) is a function that calls an argument, x, on itself.

The whole block of code you posted results in a function of one argument. You could call it like this:

(((lambda (x) (x x))
  (lambda (fact-gen)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((fact-gen fact-gen) (sub1 n)))))))
 5)

That calls it with 5, and returns 120.

The easiest way to think about this at a high level is that the first function, (lambda (x) (x x)), is giving x a reference to itself so now x can refer to itself, and hence recurse.

Answer 8

(lambda (x) (x x)) takes a function object, then invokes that object using one argument, the function object itself.

This is then called with another function, which takes that function object under the parameter name fact-gen. It returns a lambda that takes the actual argument, n. This is how the ((fact-gen fact-gen) (sub1 n)) works.

You should read the sample chapter (Chapter 9) from The Little Schemer if you can follow it. It discusses how to build functions of this type, and ultimately extracting this pattern out into the Y combinator (which can be used to provide recursion in general).

Answer 9

The expression (lambda (x) (x x)) creates a function that, when evaluated with one argument (which must be a function), applies that function with itself as an argument.

Your given expression evaluates to a function that takes one numeric argument and returns the factorial of that argument. To try it:

(let ((factorial ((lambda (x) (x x))
                  (lambda (fact-gen)
                    (lambda (n)
                      (if (zero? n)
                          1
                          (* n ((fact-gen fact-gen) (sub1 n)))))))))
  (display (factorial 5)))

There are several layers in your example, it's worthwhile to work through step by step and carefully examine what each does.