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.
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 (< 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)
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.