Y combinator

[Mats Kindahl]

Miki Tebeka <mtebeka at iil.intel.com> writes:

> Hello All,
> 
> I'm trying to write a the Y combinator in Python.
> Since Python has no closures I'm using classes.
> 
> I've tried:
> class Y:
>     def __init__(self, func):
>         self.__func = func
> 
>     def __call__(self, f):
>         return (self.__func (f (f))) (self.__func (f (f)))

The Y combinator is normally defined as (using Haskell notation, where
\ denotes lambda):

	Y = \f -> (\x -> f x x) (\x -> f x x)

which in rightmost outermost evaluation produce the correct
result. Observe that 'f x x' should be evaluated as '(f x) x', i.e.,
(f x) should return a function that can be further applied. Your code
does not do that, it rather does something along the lines of '(f (x
x)) (f (x x))', where you have named 'x' as 'f' (!!!) and are using
'__func' (bound inside the Y instance) to denote 'f'. 

> def y_fact(f, n):
>     if (n == 0):
>         return 1
>     else:
>         return n * f(n -1)

Giving the (slightly rewritten) definition (in Haskell notation) of
the *functor* 'y_fact'

    y_fact = \f -> \n -> if n == 0 then 1 else n * f (n - 1)
 
> fact = Y(y_fact)

Should (according to Y above) give the definition 

    fact = (\x -> y_fact x x) (\x -> y_fact x x)

> fact(3)

If you rewrite the expression manually in _almost_ rightmost outermost
evaluation (really a good idea when you have these kind of problems):

    (\x -> y_fact x x) (\x -> y_fact x x) 3

      { by application of Y }

    y_fact (\x -> y_fact x x) 3

      { by application of y_fact }

    (\f -> \n -> if n == 0 then 1 else n * f (n - 1)) (\x -> y_fact x x) 3

      { by application of lambda }

    (\n -> if n == 0 then 1 else n * (\x -> y_fact x x) (n - 1)) 3

      { ...and again }

    if 3 == 0 then 1 else 3 * (\x -> y_fact x x) (3 - 1)

      { by application of if }

    3 * (\x -> y_fact x x) (3 - 1)

      { by application of lambda }

    3 * (y_fact (3 - 1) (3 - 1))

      { by arithmetic simplification }

    3 * (y_fact 2 2)

      { by application of y_fact }

    3 * (if 2 == 0 then 1 else 2 * 2 (2 - 1))
                                   ^^^^^^^^^
                                   
which is hardly a function application. The first argument to 'y_fact'
should be a function---even in the recursion---and 'f' inside 'y_fact'
is the factored out version of 'y_fact'.
   
> and I get
> Traceback (innermost last):
>   File "c:\miki\python\y.py", line 15, in ?
>     fact(3)
>   File "c:\miki\python\y.py", line 6, in __call__
>     return (self.__func (f (f))) (self.__func (f (f)))
> TypeError: call of non-function (type int)
> 
> Any help?

Try this instead.

class Y:
    # Will bind the 'f' in the definition of Y above.
    def __init__(self, func):
        self.__func = func
 
    # Will give __func good starting arguments, and let __func do the
    # rest of the job itself.
    def __call__(self, x):
        return self.__func(self.__func, x)

def y_fact(f, n):
    if (n == 0):
       return 1
    else:
       return n * f(f, n - 1)

fact = Y(y_fact)

Hope this is of some help.

Regards,
-- 
Mats Kindahl, IAR Systems, Sweden

Any opinions expressed are my own, not my company's.