# A lab activity for the Y-Combinator

We are about to study the y-combinator as a culmination of lambda calculus, and I would like a shortish lab activity that is related to this idea. We are currently working in Scheme, though I don't consider that to be important at this stage. What I want (and what I lack) is something interesting that students can do with the concept of a lambda expression that takes itself and then acts recursively.

• An example that seems to work is here: viksit.com/tags/clojure/… Dec 4, 2017 at 21:34
• Does this help: RosettaCode Y-Combinator Scheme ? If so I can make it an answer. Dec 14, 2017 at 20:48
• @GuyCoder It certainly helps.
– Ben I.
Dec 16, 2017 at 21:06
• @Buffy The memoization example there is amazing. I'm still trying to make sense of it.
– Ben I.
Dec 16, 2017 at 21:11

One site that I find helpful for basic examples of coding task written in a multitude of programming languages is RosettaCode. While it is not always a win when going there, I still keep it high on the list of sites to check when looking for teaching examples or code that demonstrates something.

In this case the combination of the programming language Scheme, an example simple enough to use in a classroom and the Lambda Calculus Y-combinator are satisfied by this example:

Define the stateless Y combinator and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions.

(define Y
(lambda (h)
((lambda (x) (x x))
(lambda (g)
(h (lambda args (apply (g g) args)))))))

(define fac
(Y
(lambda (f)
(lambda (x)
(if (< x 2)
1
(* x (f (- x 1))))))))

;; tail-recursive factorial
(define (fac2 n)
(letrec ((tail-fac
(Y (lambda (f)
(lambda (n acc)
(if (zero? n)
acc
(f (- n 1) (* n acc))))))))
(tail-fac n 1)))

(define fib
(Y
(lambda (f)
(lambda (x)
(if (< x 2)
x
(+ (f (- x 1)) (f (- x 2))))))))

(display (fac 6))
(newline)

(display (fib 6))
(newline)


output

720
8


• Now that I've seen your writeup, are you saying that the lab activity is, itself, to create fib and fac?
• Yes. The activity would be first to create the Y combinator, then to verify that it works one could write fib and/or fac. I also find that reading the book noted is a gentler way to learning what is going on and why. While I don't know your end goal with Lambda Calculus. If I were teaching a class on it I would keep one of the goals being to understand System F which is the basis for a lot of functional languages and language research. Dec 17, 2017 at 17:57