Skip to content

Instantly share code, notes, and snippets.

Created February 3, 2015 16:17
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save hypirion/51db306caf49810d3d2f to your computer and use it in GitHub Desktop.
What's wrong with my Y Combinator?
;; I'm hitting my head against a wall trying to implement the Y Combinator in SKI in Clojure
;; Anyone with experience implementing it, or is able to detect what's wrong here?
(defn I [x] x)
#_=> #'user/I
(def K (fn [x] (fn [y] x)))
#_=> #'user/K
(def S (fn [x] (fn [y] (fn [z] ((x z)(y z))))))
#_=> #'user/S
;; The culprit:
(def Y ((S (K ((S I) I))) ((S ((S (K S)) K)) (K ((S I) I)))))
#_=> #'user/Y
;; fac work fine with a straight port of the Y combinator in Clojure,
;; so this one is probably not the issue.
(def fac (fn [f] (fn [n] (if (zero? n) 1 (* n (f (dec n)))))))
#_=> #'user/fac
((Y fac) 10)
;; StackOverflowError user/S/fn--844/fn--845 (NO_SOURCE_FILE:1)
((Y fac) 1)
;; StackOverflowError user/S/fn--844/fn--845 (NO_SOURCE_FILE:1)
((Y fac) 0)
;; StackOverflowError user/S/fn--844/fn--845 (NO_SOURCE_FILE:1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment