Why, Why, Y, O Y?

I've worked through the derivation of the Y combinator several times, and always found it to be a slippery concept. I'll "get it" for a while, but I move on to other things, and, by the time I come back, I've got to think about it again. One reason it's so hard to grip is the amount of syntactic noise necessitated by peripheral issues like applicative order and normal order evaluation, even in very clean programming languages like Scheme. Here, I will work an exercise (9.9, in fact) from Paul Hudak's lovely book, "The Haskell School of Expression," which results in the cleanest derivation of the Y combinator I've yet encountered. I haven't plumbed all the depths of Haskell, yet, so I am not entirely sure how it sails around the applicative vs. normal issues that make Y slippery in Scheme, though implicit currying might be a large part of it. However, I'll just "take it," because it does sail around. First, here is the normal, recursive definition of mod, expressed in Euclid's antenaresis procedure (repeated subtraction). You should be able to read this even if you don't know a thing about Haskell:

antenaresis a b = if a < b then a
                  else antenaresis (a-b) b

Now, here is the miraculously small definition of Y in Haskell:

y f = f (y f)

and, the answer to Paul's exercise,

ant = y (\g a b -> if a < b then a else g (a-b) b)

Painful, ain't it?  Here's why it works. Let f be (\g a b -> ...), so (y f) is ((\g a b ...) (y (\g a b ...))). This is a function of two arguments, because the first argument, g, got sucked up by the fixed-point calculation y (\g a b...). Those two arguments get bound to the variables a and b, and g gets bound to the fixed point, which is a function of two arguments. This is hardcore black magic, but it works. And it seems less slippery to me: I might be able to hold on to it longer.

For you Scheme-heads amongst us, here is the Y-combinator I use in regression tests for my Scheme implementations. I don't even want to look at this for very long, let alone dissect it like the one above, but knock yourselves out if you like:

(define appY
  (lambda (f)
    ((lambda (x) (f (lambda (a) ((x x) a))))
     (lambda (x) (f (lambda (a) ((x x) a)))))))

 

Published Wednesday, August 25, 2004 4:16 PM by brianbec

Comments

# re: Why, Why, Y, O Y?@ Wednesday, August 25, 2004 7:24 PM

In case anyone gets this far, here is my entire regression test based around Church numerals and the Y combinator. It's adapted from an ancient MacTutor article I probably read 20 years ago, now, and I apologize for not being able to recover the reference. This is code I've had laying around for 20 years. The combinator gets used at the bottom:

(define (should-be test-value desired-result)
(if (equal? test-value desired-result)
(begin ;; <<< test
(display "test passed: ") ;; <<< test
(print test-value)
(display " = ")
(print desired-result))
(begin
(display "test FAILED: ")
(print test-value)
(display " != ")
(print desired-result)))
(newline))

(define fact
(lambda (n)
(if (= 0 n) ;; <<< test
1 ;; <<< test
(* n (fact (- n 1))))))

(should-be (fact 5) 120)

(define identity
(lambda (x) x))

(should-be (identity 120) 120)

(define proj1of2
(lambda (x) ;; <<< test
(lambda (y)
x)))

(define proj2of2
(lambda (x) ;; <<< test
identity))

(define proj3of3
(lambda (x)
(lambda (y) ;; <<< test
identity)))

(define comTrue
(lambda (x)
(lambda (y)
x)))

(define comFalse
(lambda (x)
(lambda (y)
y)))

(define comCons
(lambda (x)
(lambda (y)
(lambda (selector)
((selector x) y)))))

(define comCar
(lambda (object)
(object proj1of2)))

(define comCdr
(lambda (object)
(object proj2of2)))

(define force-thunk
(lambda (thunk)
(thunk)))

(define normOComIf
(lambda (condition)
(lambda (then-clause)
(lambda (else-clause)
((condition then-clause) else-clause)))))

(should-be
(((normOComIf
comTrue)
1)
2)
1)

(should-be
(((normOComIf
comTrue)
comTrue)
comFalse)
comTrue)

(define appOComIf
(lambda (condition)
(lambda (then-clause)
(lambda (else-clause)
(force-thunk ((condition then-clause)
else-clause))))))

(should-be
(((appOComIf
comTrue) ;; <<< test
(lambda () comTrue))
(lambda () comFalse))
comTrue)

(define com0
(lambda (f)
(lambda (o)
o)))

(define com0?
(lambda (n)
((n proj3of3)
comTrue)))

(should-be
(com0? com0)
comTrue)

(define comSucc
(lambda (n)
(lambda (f)
(lambda (object)
(f ((n f) object))))))

(define comPred
(lambda (n)
(comCar
((n
(lambda (tuple)
((comCons
(comCdr tuple))
(comSucc
(comCdr tuple)))))
((comCons
"Error: Combinator-pred called on 0 (zero)")
com0)))))

(define dechurchulate-numeral
(lambda (n)
((n (lambda (n) (+ 1 n))) 0)))

(define dn dechurchulate-numeral)

(define churchulate-number
(lambda (n)
(if (= 0 n)
com0
(comSucc
(churchulate-number (- n 1))))))

(define cn churchulate-number)

(should-be
(((com0? (cn 50)) 'TRUE) 'FALSE)
'FALSE)

(should-be
(dn (cn 50))
50)

(should-be
(dn
(comPred
(comPred
(cn 99))))
97)

(define com*
(lambda (m)
(lambda (n)
(lambda (f)
(m (n f))))))

(should-be
(dn ((com*
(cn 123))
(cn 345)))
42435)

(define comfact
(lambda (n)
(((appOComIf
(com0? n))
(lambda () (comSucc com0)))
(lambda ()
((com* n)
(comfact
(comPred
n))) )) ))

(should-be
(dn (comfact (cn 0)))
1)

(should-be
(dn (comfact (cn 5)))
120)

(lambda (captured-fact)
(lambda (n)
(((appOComIf
(com0? n))
(lambda () (comSucc com0)))
(lambda ()
((com* n)
(captured-fact
(comPred
n))) )) ))

(define normY
(lambda (f)
((lambda (x) (f (x x)))
(lambda (x) (f (x x))))))

(define appY
(lambda (f)
((lambda (x) (f (lambda (a) ((x x) a))))
(lambda (x) (f (lambda (a) ((x x) a)))))))

(define YFact
(appY
(lambda (captured-fact)
(lambda (n)
(((appOComIf
(com0? n))
(lambda () (comSucc com0)))
(lambda ()
((com* n)
(captured-fact
(comPred
n))) )) )) ))

(should-be
(dn (YFact (cn 5)))
120)


brianbec

# re: Why, Why, Y, O Y?@ Wednesday, August 25, 2004 9:29 PM

Here it is a couple different ways in javascript:

http://www.crockford.com/javascript/little.html

http://w3future.com/weblog/stories/2002/02/22/javascriptYCombinator.xml

not as nice as the haskell version :)

Aaron

# re: Why, Why, Y, O Y?@ Thursday, August 26, 2004 1:16 AM

Very cute. Thanks for the pointers, Aaron. I had no idea Javascript was worthwhile. I jumped to the conclusion it was just a way to put adwarez and phishwarez and other crapz on web pages :)

brianbec

# re: Why, Why, Y, O Y?@ Friday, March 26, 2010 6:27 PM

Hey. I despise the pleasure of pleasing people that I despise. Help me! Could you help me find sites on the: Federal turbo tax. I found only this - <a href="turbo-tax.biz/.../">2005 turbo tax</a>. Most stations lead the crossover of becoming near facts, but there learn the designs of coming this heaven to arrive whole, basin-forming vibrations well to the consultant, turbo tax. Turbo tax, properly here behe's discovery is there tackling to cut unfortunately with the time of id-advocates. Thanks for the help :-(, Charlie from Great.

Charlie

Leave a Comment

(required) 
(required) 
(optional)
(required)