Y oh Y oh Y

[sans-hubris]

"I heard a rumor that lambda calculus doesn't have recursion because it doesn't have named functions! It must be true because I can't think of a way to do anonymous recursion."

"It is a rumor, and nothing more! Trust me or go ask Alonzo Church or Alan Turing if you don't believe me. However, recursion may not be what you think it to be. In all reality, it's nothing more than syntactic sugar! This is why lambda calculus can get away with having anonymously recursive functions."

So, you're job is to write, in any language, a Y combinator. "What's a Y combinator?" some may ask, while others are trying to dig up their old LISP or Scheme source code. The Y combinator is exactly what is needed for anonymous recursion. Take the following pseudo-code, for example:

lambda length(l) //lambda declares a function
if empty_list(l) then //empty_list returns true iff l has no elements
return 0
else return 1+length(cdr(l)) //cdr returns the list of elements after the first element

What happens if we change the name of length?

lambda eternity(x)
eternity(x)

lambda length(l)
if empty_list(l) then
return 0
else return 1+eternity(cdr(l))

So now we can only get the size of a list with length zero. What about a list with one element? Hopefully you'll have some idea of what's coming next.

lambda eternity(x)
eternity(x)

lambda length0(l)
if empty_list(l) then
return 0
else return 1+eternity(cdr(l))

lambda length1(l)
if empty_list(l) then
return 0
else return 1+length0(l)

//if you don't like my naming scheme:
lambda length1b(l)
if empty_list(l) then
return 0
else return 1 + (lambda(n) //anonymous function taking one argument
if empty_list(n) then
return 0
else return 1+eternity(n))(l) //this is passing the list 'l' as an argument to our anonymous function

I'll let you do length2 however you wish. Consider the following function:

lambda eternity(x)
eternity(x)

lambda length_maker(length) //this function requires a function to be passed to it
lambda(l)
if empty_list(l) then
return 0
else return 1+length(cdr(l))

//the following defines a function that, when called, will first call lengt-maker with the argument eternity to get another function that takes a list, and returns the size of a list with zero elements in it
define length0a length-maker(eternity)

Hopefully you're getting the point that recursion is nothing more than a name problem. This is where the Y combinator comes in:

lambda Y(recfun)
(lambda(f)
(f f)) (lambda(fn)
recfun(lambda(x) (fn(fn))(x))

Ich! Sorry, that's a bit ugly. If you're familiar with how lambda calculus works:
(lambda (f) ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))
Or you can just try following the Scheme version:

(define Y
(lambda (recfun)
((lambda (f)
(f f))
(lambda (f)
(recfun (lambda (x) ((f f) x)))))))


Basically the challenge is to write the Y combinator in whatever language you would like. If this description isn't enough for you, you may try this (http://www.everything2.com/index.pl?node=Y%20operator) one or just go on google and look it up. It would be interesting to see this coded in non-functional programming languages.

To make sure it works, you must also code a function that uses the Y combinator. To get you started, here are some ideas: factorial function, Fibonacci, quicksort, etc.

[Strike]

I'm not sure I entirely understand what exactly the combinator is, and I even know a bit of Scheme and understand (vaguely) lambda calculus.

Y takes a function as an argument, but returns what? A function that takes an argument x and performs f on (x, x)?

[sans-hubris]

I knew this was going to happen. I'll provide an example of something that uses. The Y combinator is definitely something not very easy to understand.

This is the recursive factorial function using the Y combinator:

((Y (lambda (fact)
(lambda (n)
(cond
((= n 1) 1)
(else (* n (fact (- n 1)))))))) 5)

So, basically, the Y combinator takes a function that returns a function (which takes whatever arguments you want for your recursive algorithm) and returns yet another function.

If you were doing this in C, you would not actually have anonymous functions, but you could almost simulate it using function pointers.

In C++, you could possibly simulate anonymous functions by creating functors, which are basically objects that resemble normal functions (i.e. overload the '()' operator with the function you want to perform.)

[PrBacterio]

Strike: I think this following Scheme function which uses the Y combinator should really highlight what it's actually doing:

(define count-down
(Y
(lambda (me)
(lambda (arg)
(display arg) (newline)
(if (> arg 0)
(me (- arg 1)))))))

The only complicated thing about the Y combinator you have to 'get' is currying; a function that takes 2 arguments, x and y, can be written as taking a tuple:
(lambda (x y)
(do-something-with x y))

or in a curried fashion, as a function which takes the first argument, and returns a function, which takes the second argument, and returns the result:
(lambda (x)
(lambda (y)
(do-something-with x y)))

Now, what the Y combinator does is, it takes a function of two arguments: A function, and an argument; which assume, its FIRST argument is the function itself, so it can recurse; and this function takes those two arguments in a curried fashion. This is because in pure lambda calculus, there is no such thing as a tuple (at least, as a primitive type).

If you know a little bit of ML / OCaml, you should be familiar with the notion.

In OCaml, standard argument passing to function is done via currying. A function definition like
let foobar x y = x * y

really means a CURRIED function like:
let foobar = fun x -> fun y -> x * y

On the other hand, in SML the usual convention for functions which take several arguments is tupling-style, i.e. the function gets a tuple of arguments. Thats possible in OCaml too (and is, in fact, optimized by the compiler all the same):
let foobar (x,y) = x * y

Here's the Y combinator in OCaml for good measure:
let y = fun rf -> ((fun f -> (f f)) (fun f -> rf (fun x -> f f x)))

and here is QuickSort implemented in OCaml with this:
let qs =
y
(fun qs ->
function
| [] -> []
| h :: hs -> qs (List.filter (( >= ) h) hs) @ h :: (qs (List.filter (( < ) h) hs)))

This only works with truly recursive types in OCaml enabled, by the way (it's option -rectypes, so you have run ocaml as ocaml -rectypes).

[Strike]

Ah, okay, I get it now I think.

This link helped me - http://www.cs.oberlin.edu/classes/dragn/labs/combinators/combinators11.html

[Strike]

So, I wrote a currying function (assuming that's the same as a combinator, which I think it is) in Python:

def curry(func):
return (lambda x : (lambda y : func(x, y)))


And I checked it using the following code:
def curry(func):
return (lambda x : (lambda y : func(x, y)))

def times(x, y):
return x * y

def pow(x, y):
return x ** y
if __name__ == "__main__":
print (curry(times)(2))(3)
print (curry(pow)(4))(5)

Which uses the curried "times" function on 2, and then the function that returns on 3. Then it uses the curried "pow" function on 4 and then that function on 5.

The results:
[ddipaolo@Xena14 y-challenge]$ python y.py
6
1024


Do I win? ;)

[PrBacterio]

Do I win? ;)

Not quite :)

What you did was just write the currying combinator as a Python function. What was asked for in the original post was to write the y combinator in the language of your choice, i.e. Python.

The currying function you wrote, takes a function which expects two arguments, and returns it in its curried form - it returns a function, which expects one argument to give a function, which expects another argument to return the result, which is the result the original function would have given, if it were called with those two arguments.

Now, the Y combinator takes a function which is already in curried form. This function expects two arguments - a function, and its actual argument - so it can recurse over its argument. The function it expects is used inside the function definition for the recursion. It takes those two arguments in curried fashion.

Consider, for example, this Scheme function definition:
(define curry-factorial
(lambda (fact)
(lambda (n)
(cond
((< n 2) 1)
(else (* n (fact (- n 1))))))))

This function expects, as its first, curried argument, a factorial function which it can use for its second case recursion; this function, which curry-factorial expects as its first argument, is actually the factorial function it - curry-factorial itself - returns when called with this same factorial function.

And this is exactly what the Y combinator does: It calls this function, with the function it would return, if this same function were given to it - thus fullfilling the requirement for the recursion, that fact - the first argument to it - is the factorial function, which this function is used to define, itself.

Now, I dont know any Python but I *think* the Y operator in Python should look something like this: def y(func):
return (lambda f : func (lambda x : (f(f))(x)))
(lambda f : func (lambda x : (f(f))(x)))

[Strike]

Cool, I'll have to look into it. Things have been hectic here lately so I haven't had a chance to in a few days. Will put on my "to do" list for now though, for when things slow down.