In Scheme, how do you use lambda to create a recur

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.

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 in the environment above it:

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

The (lambda (n) ...) expression here is returned from inside that environment frame in which g points to h above it - as a closure object. I.e. a function of one argument, n, which also remembers the bindings for g, h, and U.

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

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

The (g g) application gets reduced into (h h) application because g points to h defined in the environment frame above the environment in which the closure object was created. Which is to say, up there, in the top let form. But we've already seen the reduction of (h h) call, which created the closure i.e. the function of one argument n, serving as our factorial function, which on the next iteration will be called with 4, then 3 etc.

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