/prog/ Confessions Thread

I've never really understood the Y combinator.

Basically, Y is a function that applies a function F (which expects some recursive function as it's first argument), to itself.

(define (y f) (f (y f)))

this only works in lazy languages though, otherwise Y will continually be called recursively until the stack blows up.

To make it work in strict languages you have to add another layer of indirection. Rather than passing (Y f) to the function, you pass a function (called Z) that when called will again call the original function
with a newly created version of Z, which again will pass a new version of itself into F, ad infinitum, but the infinite recursion only recurs stepwise as necessary this time, as it is delayed behind a lambda indirection.

(define (y f)
;; always pass a copy of this function to itself
(let ((make-wrapped-func (lambda (wrapper-maker)
(lambda (arg) ;; original function's argument

;; next-wrapped-func is equivalent to the function we're current evaluationg
(let ((next-wrapped-func (wrapper-maker wrapper-maker)))
;; call original func with wrapped func (which will in turn call it again with a wrapped func, if necessary)
;; then pass in the argument
((f next-wrapped-func) arg))))))
(make-wrapped-func make-wrapped-func)))