#lang racket ;; Y combinator example ;; First, here is a definition of the factorial function using letrec, ;; and a sample call to compute 5 factorial. (letrec ((fact (lambda (n) (if (= 0 n) 1 (* n (fact (- n 1))))))) (fact 5)) ;; The Y combinator in Racket (applicative order evaluation version) (define Y (lambda (f) ((lambda (x) (f (lambda (v) ((x x) v)))) (lambda (x) (f (lambda (v) ((x x) v))))))) ;; A rewriting of the factorial function using the Y combinator (no recursion) ;; and a sample call. ;; Note that there are two different variables named 'fact', one bound by ;; the let and the other a parameter to the first lambda. (let ((fact (Y (lambda (fact) (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))))) (fact 4))