Functional Groovy: Y-Combinator. Learning Groovy from Haskell ;)

Intro

I guess that, Y-Combinator (maybe together with Monad) is now on the Geek-Should-Know concept list.  Also YCombinator is a name of a venture capital firm so even managers may know about it!

I intend this to be a very simple intro to Y-Combinator using Groovy Closures.  There are other blogs about Y-Combinator in Groovy:

 http://hamletdarcy.blogspot.com/2009/09/y-combinator-in-groovy.html

My goal is to explain/derive Y-combinator, not to just show how to use it. 

An excellent post with code examples in Scheme can be found here:
 http://mvanier.livejournal.com/2897.html

Combinators and Things: The History

"Computer Scientists do not know their history"  Eric Meijer
My background (education) is mathematics, not CS.  As a mathematician, I was never much into logic.  I am learning this stuff now.  I believe CS (maybe this is changing) education does not typically include topics like Combinatory Logic,  Lambda Calculus or Category/Functor Theory.
Universities produce an army of excellent engineers which think in only imperative terms.
(Correct me if I am wrong, I am sure this is very much school dependent.)

SKI Calculus and combinators (1920-ties, Moses Schönfinkel, Haskell Curry) are older than Turing Machines (1930-ties).  Lambda Calculus (1930-ties Alonzo Church) is concurrent to Turing work. Lots of this is very cool stuff and includes work of many other mathematicians, most notably, David Hilbert.

SKI calculus motivation was logic, not computing, but, in fact, Church's work was largely motivated by the idea of a computer (same as Turing work was).  You can think that lambda calculus was `software oriented` thinking, why Turning machines have been `hardware oriented`.  
That last statement is somewhat questionable: since two base combinators S, K (I can be derived) can express complete mathematical logic, it maybe possible to build CPU with S, K, I  as the instruction set.  That idea has been worked on a lot (however, it is hard to google for it:  "SKI hardware", "SKI instructions set"  ;).
The is some learning involved.  Here are some 'quick' guides I have recently found:

  http://www.youtube.com/watch?v=FC6kl_kLFEo

  http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf

Enough of this into. (I am not sure it even belongs in this post).

Recursion as Fix-point

Functions are often defined using recursion. In this post, I will use Fibonacci sequence with its (super-slow) recursive definition which may look like this in Groovy:

 Closure fib
 fib = {int n -> n < 2 ? n: fib(n-1) + fib(n-2)}

but everything discussed here will generalize to other recursive function definitions.

Here is a different (and interesting) way to look at this.  We can create a functional FIB (a function that takes functions are argument and returns a new function) like so:

Closure FIB = {Closure f ->
  {int n -> n<2 ? n: f(n-1) + f(n-2)} //returns new closure
}

With Fpiglet you could alternatively define FIB like this (implicit currying):

 Closure FIB = FpigBase.f {Closure f, int n -> 
    n<2 ? n: f(n-1) + f(n-2)
 }

Our FIB functional maps functions into functions. The fix-point (if exists and here it does) is a function f0 such that:

 FIB(f0) == f0

It should be obvious that this f0 fix-point must be the same as the fib function defined above and this type of argument can be easily generalized to other recursive definitions.

So the name of the game here is: to find a way to 'solve' functionals like the FIB functional defined above for fix-points.

Fix function:

Would it be cool if we had a 'magic' function called fix which could calculate f0 like so:

 f0 = fix FIB

Obviously, Haskell has one ;) and it is defined like this:

fix :: (a -> a) -> a
fix f = f (fix f)

This is exactly what we need, if you blindly plugin 'FIB' for 'f' and 'f0' for 'fix FIB' the function implementation line becomes:

 f0 = FIB f0

so if fix returns anything it will he a fix-point!

With the above we can define Fibonacci sequence like this (note fib' is the same as FIB functional, we just do not want to use upper case function names in Haskell):

fib' :: (Integer -> Integer) -> Integer -> Integer
fib' f 0 = 0
fib' f 1 = 1
fib' f n = f (n-1) + f (n-2)

f0 :: Integer -> Integer
f0 = fix fib'

numbs = map f0 [0..6] --numbs equals to [0,1,1,2,3,5,8] 

Let us do that in Groovy!  There is a little glitch. Haskell is lazy language so the above implementation of fix does not have to stack overflow,  this simple Groovy equivalent will always stack overflow:

def fix
fix = {Closure f ->
    {x -> (f << fix(f)) x} 
}

but not if you do it like this:

def fix
fix = {Closure f ->
    f({x -> (fix(f))(x)}) 
}

you can run the following to convince yourself that it works:

def f0 = fix(FIB)
assert [0,1,1,2,3,5,8] == (0..6).collect(f0)
assert 8 == f0(6)

The trick is that fix function passes closure {x -> (fix(f))(x)} to the next iteration of FIB and that closure does not need to be invoked if n < 2. 
This is cool but the definition of `fix` itself is recursive.  So we are swapping one recursion for another.  I would be better if we could do recursion without ANY recursion! 

Y-Combinator

Y combinator is, well is a combinator (whatever that means) invented by Haskell Curry.

It it is typically represented by the following lambda expression (whatever that means):

  λf.(λx.f (x x)) (λx.f (x x))

Instead of explaining its meaning, let me try to derive it (using Groovy) and the meaning may become clear. Forget about fix function. I would really like to do something like this:

FIB(FIB)(6) //or FIB(FIB, 6)

This will not work with current definition of FIB but will work if you define it like so:

Closure FIB = {Closure f, int n ->
    n < 2 ? n: f(f, n-1) + f(f, n-2)
}

FIB(FIB, 6) //returns 8

or using curried versions:

Closure FIB = {Closure f ->
  {int n -> n < 2 ? n: f(f)(n-1) + f(f)(n-2) }
}

assert 8 == FIB(FIB)(6)

This is it, this is the main trick behind Y-Combinator.  The rest is simply bunch of refactoring steps.

This trick may look like cheating and to some extent it is.  Instead of being able to call function from itself (which would be recursion), we pass a copy of that function to itself so that function can call it. On one hand this seems like a recursion in disguise,  on the other hand it is function composition.  On some deep level, composing function with itself and recursion are similar concepts.

I like to think that function composition is a stronger concept than recursion.   Y verifies that claim.

I can refactor my code so it looks like this:

Closure c2 = {f ->
   return {x -> f(f)(x)}
}

Closure FIB= {Closure f2 ->
  return {int n -> n < 2 ? n: f2(n-1) + f2(n-2)}
}

c2({Closure f ->
  return FIB(c2(f))
}) (6)  //returns 8

and now I can re-write my code like so:

Closure c2 = {f ->
   {x -> f(f)(x)}
}

Closure FIB = {Closure f ->
  {int n -> n < 2 ? n: f(n-1) + f(n-2) }
}

def Y = {Closure fx -> c2({Closure f ->
   fx(c2(f))
})}  //fx represents functional, f function

def f0 = Y(FIB)
assert [0,1,1,2,3,5,8] == (0..6).collect(f0)

and this is it, we have Y Combinator in Groovy.  And if you look long enough you will see the original lamba expression!

Actually what we got is this (Groovy is strict/eager evaluation language):

 λf.(λx.f (λv.((x x) v))) (λx.f (λv.((x x) v)))

Formal Mathematical Proof

It is actually not very hard.   This PDF: http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf
has a good introduction to lambda calculus, but the proof that Y acts as fix-point finder requires more explanation:

Y g = (λf . (λx . f (x x)) (λx . f (x x))) g   //1. definition
= (λx . g (x x)) (λx . g (x x))                //2. β-reduction of λf: applied to g
= g ((λx . g (x x)) (λx . g (x x)))            //3. β-reduction of λx done on x x
= g (Y g)                                      //4. definition again

The only thing that needs explanation is how do we get from 2 to 3.  We basically are substituting 

 (λx . g (x x)) into x x expression on the left!

Useless or useful?

If you visited Hamlet D'Arcy's post on Y-combinator you may have noted that he has classified Y-combinator as cool but useless.

I think, the main applicability of Y-combinator is that it lets you keep your closures as anonymous functions.   You can define recursive closure without giving it a name like this:

Y {Closure f ->
    { ... }
}

I think that could make some of your code more expressive.  Also if pointless programming is important to you, then you should love Y!  Now, pointless and useless are not exactly the same ;).

There is also the thing about recursion being logically dangerous.  You can lookup 'Curry Paradox' and read on that.  But hopefully compilers will catch all of that for us, and I do not think this is related to Groovy programming anyway.

So is this just cool theoretical CS?  My take on this is that, for working programmers, it maybe more important to know what combinators are in general and try to learn to 'think in combinators'. In that Y-combinator probably will not help much.  'Thinking in combinators' will involve higher level combinators like function sets defining Monad, Arrows, Lenses, etc.

Curlies 10: recursion, why language matters

This is 10th installment about Curly braces: my arguing that curlies are the reason for all the evil in programming ;)  And my team has introduced mustache to my current project :D.

I wrote about for loops and how they compare to functional alternatives before. Today's topic is a bit different but is still relevant to the imperative for loops.  The point is that recursion can be a very expressive alternative to the for loop.

Lets look at some code examples.  Groovy collections have a method called collect which applies a given closure to each collection element like so:

assert [10,20,30] == [1,2,3].collect { it * 10 }

If Groovy did not have collect method and we wanted to write our own, how would we do that?
Probably with a for loop!  In fact this is how the underlying implementation of Groovy method looks like:

   public static Collection collect(Object self, Collection collection, 
                            Closure closure) {
       for (Iterator iter = InvokerHelper.asIterator(self); iter.hasNext();) {
            collection.add(closure.call(iter.next()));
       }
       return collection;
   }

Let's compare this with functional language equivalent (let's do that in Haskell!)  So if Haskel did not have a built in Map function, here is how we would write one:

    map :: (a->b) -> [a] -> [b]
    map _ [] = []
    map f (head : tail) = f head : map f tail

We are done!  I do not want to say we 'implemented' or 'coded' map function.  This would imply that we told the computer what to do and we did not!  We told the computer what map is.
Haskell to English:  (1st line) is declaration,  in Haskell all functions are curried so to define function c = f(a, b) you write f :: a -> b -> c.   So, this declaration says that map accepts both a function: a->b and a list [a]as parameters and returns a list [b].  
(2nd line) Says that map of empty list is an empty list no matter what the function is.  
(3rd line)  Says that to map a non-empty list you apply the function on the first element of that list and apply the map with this function to the remaining elements of the list (recursive induction).  
Side Note: a very cool pattern matching is happening.  If list [1,2,3] is defined as x:xs, that means that:  x==1 and xs==[2,3].  The parentheses (head : tail) are here only to disambiguate the order of things.  In Haskell to call function f on x you just type: f x
I find Haskell version much much readable!

Next lets look at something a bit more complex. Haskell alternative to Groovy's collection findAll method which works like so:

 assert [3] == [1,2,3].findAll { it > 2 }

Can you imagine how it is implemented?  Obviously with a for loop! I will spare you the details.  Here is how you could do that in Haskell (Haskell calls the same operation  filter):

 filter :: (a->Bool) -> [a] -> [b]
 filter _ [] = []
 filter p (head : tail)
     | p head      = tail : filter p tail
     | otherwise   = filter p tail

Haskell to English:  This bar ( | ) things are called guards and are somewhat reminiscent of our old switch statement.
(1st line) is declaration.
(2nd line) filter applied to empty list results in empty list no matter what the predicate function is.
(3rd line and on) for predicate function p and list with first element called head and the remaining elements called tail, if the predicate is satisfied for the head element then the head element is included otherwise it is not.
That is all there is to it!

You can see the expressiveness of Haskell!  Recursion allows us to almost translate the definition from English directly to the program!  Readability!   Imperative programs tell the computer what to do,  declarative programs tell the computer what things are.

So why languages matter?  Many programmers (I was one of them) tend to think that the multiplicity of new languages today comes from some form of developer vanity.  Hey why not create one more language?   Why do we assume that all advancements in computer science can be expressed in, say, Java?   Obviously they can't!  New work in type systems, in compilers, ... the point is clear but we still do look down on all these new languages!

The recursion is another little reason why new languages are needed.  You could try to use recursion in Java but with big collections prepare yourself for stack overflow errors. You need some serious language help for that!
Now I am NOT saying that there are no stack overflow problems in Haskell or SCALA.  In fact, knowledge of how to avoid stack overflow errors is part of language learning.  However, functional language compilers are armed with bunch of tricks such as tail-call optimization, trampoline...  These tools allow language compiler to resolve recursion into a for loop!
Added Note:  As I have learned recently Groovy is catching up and you can trampoline your closures (that is not a compiler function and requires explicit coding).   Also there is some tail-call optimization support for methods (not closures) in both Groovy and Java.  I may write more about it in the future.

Final little point  (and I tried to make this point before):  I hope I have shown some very expressive code examples.  However the terseness and expressiveness was not the goal, rather is was a consequence. Declarative programming yields terse and expressive code, but not all terse and expressive code is declarative or functional.  So what is more important expressive or declarative, expressive or functional?  But this maybe a good topic for another post some day, maybe.