Skip to content

Instantly share code, notes, and snippets.

@lynus
Created March 10, 2021 08:27
Show Gist options
  • Save lynus/baa315d62831de9b07c409bcbfb4e747 to your computer and use it in GitHub Desktop.
Save lynus/baa315d62831de9b07c409bcbfb4e747 to your computer and use it in GitHub Desktop.
How to derive Y combinator
(define (add1 x) (+ 1 x))
(define l3 '(1 2 3))
(define length
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cd l)))))))
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cd l)))))))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cd l))))))))
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((length length)(cd l)))))))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((length length)(cd l))))))))
((lambda (mk-length)
(mk-length mk-length))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((length length) (cdr l))))))))
((lambda (mk-length)
(mk-length mk-length))
(lambda (fx)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((fx fx) (cdr l))))))))
(define y0
((lambda (mk-length)
(mk-length mk-length))
(lambda (fx)
((lambda (F)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (F (cdr l)))))))
(lambda (x)
((fx fx) x))))))
(define y1
(lambda (work)
((lambda (mk-length)
(mk-length mk-length))
(lambda (fx)
(work (lambda (x) ((fx fx) x)))))))
(define work
(lambda (F)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (F (cdr l))))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment