3

One of my favorite ways to test the power of a language I'm learning is to try and implement various fixed-point combinators. Since I'm learning Clojure (though I'm not new to lisps), I did the same for it.

First, a little "testable" code, factorial:

(def !' "un-fixed factorial function" (fn [f] (fn [n] (if (zero? n) 1 (* n (f (dec n))))))) (defn ! "factorial" [n] (if (zero? n) 1 (apply * (map inc (range n)))))

For any combinator c I implement, I want to verify that ((c !') n) is equal to (! n).

We start with the traditional Y:

(defn Y "pure lazy Y combinator => stack overflow" [f] (let [A (fn [x] (f (x x)))] (A A)))

But of course Clojure is not nearly so lazy as that, so we pivot to Z:

(defn Z "strict fixed-point combinator" [f] (let [A (fn [x] (f (fn [v] ((x x) v))))] (A A)))

And indeed, it holds that (= ((Z !') n) (! n)).

Now comes my issue: I cannot get either of U or the Turing combinator (theta-v) to work correctly. I suspect with U it's a language limit, while with theta-v I'm more inclined to believe it's a misread of Wikipedia's notation:

(defn U "the U combinator => broken???" [f] (f f)) (defn theta-v "Turing fixed-point combinator by-value" [f] (let [A (fn [x] (fn [y] (y (fn [z] ((x x) y) z))))] (A A)))

A sample REPL experience:

((U !') 5) ;=> Execution error (ClassCastException) at fix/!'$fn (fix.clj:55). ;=> fix$_BANG__SINGLEQUOTE_$fn__180 cannot be cast to java.lang.Number ((theta-v !') 5) ;=> Execution error (ClassCastException) at fix/theta-v$A$fn (fix.clj:36). ;=> java.lang.Long cannot be cast to clojure.lang.IFn

Can anyone explain

  1. Why these implementations of U and theta-v are not working; and
  2. How to fix them?
Improve this question
4
  • Please include a link to the code you are attempting to translate. Commented Jan 15, 2020 at 23:52
  • Er, @amalloy I'm translating math more than code, but if it helps, sure Commented Jan 15, 2020 at 23:53
  • FWIW a lot of math and code are the same thing. Certainly lambda calculus is both. Commented Jan 16, 2020 at 0:20
  • Small point: since (*) is 1, you don't need 1 as a special case in function !. (defn ! [n] (apply * (map inc (range n)))) works, as does (defn ! [n] (reduce * (range 1 (inc n)))), which I prefer. Commented Feb 19, 2020 at 13:57

1 Answer 1

Reset to default
1

Your definition of theta-v is wrong for two reasons. The first is pretty obvious: you accept f as a parameter and then ignore it. A more faithful translation would be to use def style, as you have for your other functions:

(def theta-v "Turing fixed-point combinator by-value" (let [A (fn [x] (fn [y] (y (fn [z] ((x x) y) z))))] (A A)))

The second reason is a bit sneakier: you translated λz.xxyz to (fn [z] ((x x) y) z), remembering that lisps need more parentheses to denote function calls that are implicit in lambda-calculus notation. However, you missed one set: just as x x y z would have meant "evaluate x twice, then y once, then finally return z", what you wrote means "evaluate ((x x) y), then throw away that result and return z". Adding the extra set of parentheses yields a working theta-v:

(def theta-v "Turing fixed-point combinator by-value" (let [A (fn [x] (fn [y] (y (fn [z] (((x x) y) z)))))] (A A)))

and we can demonstrate that it works by calculating some factorials:

user> (map (theta-v !') (range 10)) (1 1 2 6 24 120 720 5040 40320 362880)

As for U: to use the U combinator, functions being combined must change how they self-call, meaning you would need to rewrite !' as well:

(def U [f] (f f)) (def ! (U (fn [f] (fn [n] (if (zero? n) 1 (* n ((f f) (dec n))))))))

Note that I have changed (f (dec n)) to ((f f) (dec n)).

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

ack! I can't believe I missed that... theta starts with lambda.x, not lambda.f. Interesting that U requires this extra modification to its arguments. (PS agreed on the code/math thing, just wanted to clarify that i was translating from lambda calculus and not someone's python code or something)
Thanks for the article. Unfortunately, even with this correction to theta-v, I get (map (fix/theta-v fix/fib') (range 10)) ; (0 1 1 3 5 7 9 11 13 15) (map fix/fib (range 10)) ; (0 1 1 2 3 5 8 13 21 34) (map (fix/theta-v fix/!') (range 10)) ; (1 0 2 6 12 20 30 42 56 72) (map fix/! (range 10)) ; (1 1 2 6 24 120 720 5040 40320 362880) (hopefully the linebreaks are somewhat obvious)
Indeed, that certainly looks wrong. I don't have a good answer: it looks like your !' is right, and like the implementation of theta-v matches Wikipedia's. Since it's wrong even for a value as small as 1, you could try evaluating it by hand and see where it goes wrong (where on earth can a zero have come from?).
agreed, dont have time at the moment. Good tactic.
Ah, I see. You don't have enough parens in your theta-v. In Haskell, or lambda calculus, ((x x) y) z is the same as x x y z, or in long-hand, (((x x) y) z). However, in most lisps the former means "evaluate ((x x) y), then throw it away and return z.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.