Y operator

In lambda calculus, the Y operator (also known as the Y combinator) computes the fixed point of a function. As a bit of background, note that everything in the lambda calculus is a function.

Given a function F, Y F is the function g such that g = F g. Autrement dit, Y F = F Y F.

A quick example (using pseudo-Lisp syntax as mjs did above):

nextfact = (lambda (f x) (if (<= x 1) 1 (* x (f (- x 1)))))

fact = (Y nextfact)

(fact 7) => 5040

Here's a definition of Y that works (in Scheme):

(define (Y f) ((lambda (x)
                  (lambda (z) (f (lambda (y)
                                    ((x x) y))
                               z)))
               (lambda (x)
                  (lambda (z) (f (lambda (y)
                                    ((x x) y))
                                 z)))))

In Common Lisp, it would be:

(defun Y (f) ((lambda (x)
                 (lambda (z) (funcall f (lambda (y)
                                           (funcall (funcall x x) y))
                                        z)))
              (lambda (x)
                 (lambda (z) (funcall f (lambda (y)
                                           (funcall (funcall x x) y))
                                        z)))))

This assumes you have a decent enough CL implementation to have the lambda macro. gcl, for one, doesn't have one, so you would need to insert #' in a few places above. In both of these, it only works with procedures of two arguments (including the f argument), and produces a procedure of one argument. In other languages, such as ML and Haskell, partial evaluation and currying allow any function to be written to take a single argument, so arity is not a problem.