Skip to content

Instantly share code, notes, and snippets.

@hypirion hypirion/ski.clj
Created Feb 3, 2015

Embed
What would you like to do?
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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.