From: Florian Frank <flori@...>
Date: 2004-01-23T09:52:47+09:00
Subject: Re: how to broadcast UDP packets

On Fri, 2004-01-23 at 00:37, Hal Fulton wrote:
> Would you explain your .sig? It makes my brain itch. :)

Not only your brain! ;)

It's the (applicate order) Y-Combinator that's used to implement
recursion in lambda calculus. It has the property Y(f) = f(Y(f)),
that means that it returns the fixed point of the given function
f.

If you define it like this

Y = lambda { |c| 
  lambda { |f| f[f] } [
    lambda { |f|
      c[lambda { |x| f[f][x] }]
    }
  ]
}

you can define arbitrary recursive functions with it like
the faculty function (here applied to 10)

Y[
  lambda { |fak| lambda { |n| n == 0 ? 1 : n * fak[n-1] } }
][10]

or Fibonacci numbers

Y[
  lambda { |fib| lambda { |n| n <= 1 ? 1 : fib[n - 2] + fib[n - 1]  } }
][10]


You don't have to assign this thingy to Y. You can use it
in a whole expression; here is the faculty function again:

lambda { |y, g| y[g] } [
  lambda { |c| 
    lambda { |f| f[f] } [
      lambda { |f|
        c[lambda { |x| f[f][x] }]
      }
    ]
  },
  lambda { |fak|
    lambda { |n| n == 0 ? 1 : n * fak[n-1] }
  }
][10]

To define Y is an important step, if you want to prove that the
lambda calculus and turing machine computability are equally
powerful. You can even eliminate the conditional statement,
the numbers (they can be translated to church numerals) and
arithmetic from the expression above and use lambda abstraction
and functional application instead. It's also possbible
to define pairs and lists that consist of pairs that way.

I hope this explanation helped a bit. If it didn't: I think
there are a lot of texts who derive this combinator in Scheme
or LISP to be found in the web, that can explain this better than
I can. BTW: Scheme would also make a good LOTY.

-- 
lambda {|c| lambda {|f| f[f] } [lambda {|f| c[lambda { |x| f[f][x] }]}]}