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.
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)))))))
 
;; head-recursive factorial
(define fac
  (Y
    (lambda (f)
      (lambda (x)
        (if (&lt; 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 (&lt; x 2)
            x
            (+ (f (- x 1)) (f (- x 2))))))))
 
(display (fac 6))
(newline)
 
(display (fib 6))
(newline)


output

720
8


Bonus answer:

When others want to learn more about Lambda Calculus the first reference I always give is "An Introduction to Functional Programming Through lambda Calculus"

Note: While the link is nice if you really do use the book often then please purchase the book.