Skip to content

Instantly share code, notes, and snippets.

@valvallow

valvallow/ycombinator3.scm

Created February 10, 2010 11:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save valvallow/300244 to your computer and use it in GitHub Desktop.
Save valvallow/300244 to your computer and use it in GitHub Desktop.
Download ZIP
y combinator
Raw
ycombinator3.scm
((lambda (f)
(f f 10))
(lambda (f n)
(if (< 0 n)
(begin
(print n)
(f f (- n 1))))))
#|
10
9
8
7
6
5
4
3
2
1
#<undef>
|#
((lambda (x)
((lambda (f)
(f f x))
(lambda (f n)
(if (< 0 n)
(begin
(print n)
(f f (- n 1)))))))
10)
#|
10
9
8
7
6
5
4
3
2
1
#<undef>
|#
;; normal fact
(define fact
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1))))))
(fact 5)
;; 120
;; self calling self recursive fact
((lambda (f)
(f f 5))
(lambda (f n)
(if (zero? n)
1
(* n (f f (- n 1))))))
;; 120
;; (f f (- n 1)) -> ((h f)(- n 1))
((lambda (f)
(f f 5))
(lambda (f n)
(if (zero? n)
1
(* n (((lambda (g)
(lambda (m)(g g m)))
f)
(- n 1))))))
;; 120
;; parameterize (lambda (g)(lambda (m)(g g m))) -> h
((lambda (h)
((lambda (f)
((h f) 5))
(lambda (f n)
(if (zero? n)
1
(* n ((h f)
(- n 1)))))))
(lambda (g)
(lambda (m)(g g m))))
;; 120
;; reset
(define fact
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1))))))
(fact 5)
;; 120
;; to executable
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1))))))
;; error
;;(f (- n 1)) -> ((f f)(- n 1))
(((lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f) (- n 1))))))
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f) (- n 1))))))) 5)
;; 120
(((lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1))))))
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1))))))) 5)
;; 120
#|
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1))))))
|#
((lambda (g)
((g (lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1))))))) 5))
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1)))))))
;; 120
((lambda (g)
((g g) 5))
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1)))))))
;; 120
((lambda (h)
(h (lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1))))))))
((lambda (x)
(lambda (h)
((h h) x))) 5))
;; 120
((lambda (x)
((lambda (h)
(h (lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1))))))))
(lambda (h)
((h h) x))))
5)
;; 120
((lambda (x)
((lambda (h)
(h (lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1))))))))
(lambda (h)
((h h) x))))
5)
;; error
; reset
((lambda (g)
((g g) 5))
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1)))))))
;; 120
;; ((f f) (- n 1)) -> (f (- n 1))
((lambda (g)
((g g) 5))
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((lambda (m)
((f f) m))
(- n 1)))))))
;; 120
;; reset
(((lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1))))))
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1))))))) 5)
;;
(((lambda (g)
(g g))
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f)(- n 1))))))) 5)
;; ((f f)(- n 1)) -> (f (- n 1))
(
((lambda (g)
(g g))
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((lambda (m)
((f f) m))
(- n 1)))))))
5)
(
((lambda (g)
(g g))
(lambda (f)
((lambda (h)
(lambda (n)
(if (zero? n)
1
(* n (h (- n 1))))))
(lambda (x)
((f f) x)))))
5)
#|
(lambda (h)
(lambda (n)
(if (zero? n)
1
(* n (h (- n 1))))))
|#
(
((lambda (c)
((lambda (g)
(g g))
(lambda (f)
(c (lambda (x)
((f f) x))))))
(lambda (h)
(lambda (n)
(if (zero? n)
1
(* n (h (- n 1)))))))
5)
;; refactoring
(
((lambda (c) ;; c -> concrete
((lambda (r) ;; r -> recursion
(r r))
(lambda (m) ;; m -> maker
(c (lambda (p) ;; p -> param
((m m) p))))))
(lambda (f) ;; f -> function
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1)))))))
5)
;; y combinator
(define y
(lambda (c)
((lambda (r)
(r r))
(lambda (m)
(c (lambda (p)
((m m) p)))))))
(define fact
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1)))))))
((y fact) 5) ;; 120
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment