Stuff about programming, programming style, maintainability, testability. Dedicated to my coworkers and friends. Everyone is welcome to leave comments or disagree with me. This blog does not represent views or opinions of my employer.

Wednesday, October 9, 2013

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:

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:

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.

Saturday, August 10, 2013

Monadic Comprehensions in Groovy and Fpiglet

This post is continuing my last 2 posts about monads.   In this post we will look at Groovy DSL syntax (as implemented in Fpiglet) for monadic comprehensions.

Legend:
  f([1,2,3]) - converts list [1,2,3] to functional list with the same elements
  f(myClosure) - converts closure to curried function
  << - is functions composition and passing param to function in Groovy,
         it also has been DSL-ed to do other things in comprehensions.

What are comprehensions:
If monads are about putting things in a 'box', then monadic comprehensions are magically removing the box. Only there is no magic.  Comprehension is a polymorphic (works across all monads) syntax which lets you operate on monads using 'unboxed' values.
Here is a simple example using Fpiglet Maybe type:
  
  def res = comprehend {
    x << from{ just(3) }
    y << from{ just(2) }
    output{ just(x+y) }
  }

  assert just(5) == res

One thing that Maybe and Either are famous for is that they are a great alternative to handling exceptions and nulls.  Let us see a bit of that in action:

 Closure maybeDivide = f { Maybe num, Maybe den ->
     comprehend {
       x << from { num }
       y << from { den }
       restrict { y != 0}
       output{ just(x/y) }
     }
 }

 def sixDividedBy = maybeDivide(just(6))
 assert just(2) == sixDividedBy(just(3))
 assert nothing() == sixDividedBy(just(0))

I think this is very cool and much more elegant than using if statements or throwing exceptions!
Fpiglet supports another syntax (somewhat LINQ inspired) which is also quite readable:

 Closure maybeDivide = f { Maybe num, Maybe den ->
   select{just(x/y)}.from {
      x << { num }
      y << { den }
      where { y != 0}
   }    
 }

Both versions are equivalent.  I will use select syntax moving forward.   

I hope you have enjoyed my Learn You a Haskell book inspired knight examples in previous posts. 
Here is a definition of knightMove function expressed using comprehension (please recall that positions are modeled as 2D Groovy lists [x,y] where x,y are in 0..7 range, but the list of all outcomes is a functional list):

 def knightMove = {pos ->
   def (x,y) = pos 
   select{ f([newPos]) }.from{ 
     newPos << {f([[x+2,y+1],[x+2,y-1],
                   [x-2,y+1],[x-2,y-1], 
                   [x+1,y+2],[x+1,y-2], 
                   [x-1,y+2],[x-1,y-2]]) }
     where {def (newX, newY) = newPos; newX in 0..7 && newY in 0..7}  
   }
 }

 assert [[2, 1], [1, 2]] == funlistOut << knightMove([0,0])

I am very much interested in code readability, so let me read the above code:

The result of knight move is select list (select {f[..]}) of new positions (newPos) from (.froma list of spelled out positions ({f[...]}), where (where) the new position coordinates are in 0..7 range (newX in 0..7).

One of the reasons for having comprehensions is that they read very nice!

And here are all possible positions after 3 moves:

 def in3Moves = select { f([third]) }.from{
   first  << { knightMove([0,0]) }
   second << { knightMove(first) }
   third  << { knightMove(second) }
 }

I think it reads even better!

Summary:
In previous posts we did go beyond simple 3 time knightMove to solving problems like the shortest number of moves needed to move from A to B.  Stuff like this still requires folds.    
However comprehensions are a very powerful and very readable syntax.  

Please check out Fpiglet website in a few weeks for more information about Fpiglet monadic comprehensions.

Thursday, August 1, 2013

Groovy, Monads, Knight, Chess. Making Groovy more functional with Fpiglet

In this post we will have some more fun with Groovy, chess, knights and monads using Fpiglet open source project.

This is continuation of my last post and will get a bit more advanced.  Please review my previous post first.

Legend:  Please remember that << in Groovy is function composition as well as parameter application:
 f(g(x)) //same as  f << g << x

and since we are using Fpiglet curried functions, we can be a bit more lenient with how we compose (curried functions are partially applied if invoked with fewer parameters).  Nothing was meta-programmed, Fpiglat monads are implemented purely using curried functions (it would be silly to use imparative code to implement monads!).  b is monadic bind (curried function) and m.pure is monad function which wraps object in monadic context.  Since we are talking about non-deterministic computing
  m.pure(x) //same as f([x]) (Fpiglet functional list with one element x)

Knights on Chessboard: This post is simply a more verbose version of unit tests that can be found in Fpiglet. The knight examples are inspired by Learn you a Haskell book. We have already seen how to use computational non-determinism to examine where knight can go on the chessboard. Here is somewhat improved version of knightMove which, now, includes chessboard boundary check:

Closure getKnightMove() {
 FunList possiblePositions = 
f([[1,2],[2,1],[-1,2],[2,-1],[1,-2],[-2,1],[-1,-2],[-2,-1]])
 Closure vplus = f {v, w -> [v[0] + w[0], v[1] + w[1]]}
 def onBoard  = {v ->
def (x,y) = v;  x in 0..7 && y in 0..7 }

 return {v -> filter(onBoard) << map(vplus(v)) << possiblePositions}
}
 assert [[1,2], [2,1]] == funlistOut << knightMove([0,0])

Let me explain:  Positions on chess board are represented as [x,y] 2 element Groovy lists where x,y are in 0..7 range.  f (first line) if Fpiglet function, which maps Groovy List into functional Fpiglet FunList. This f is overloaded so f on second line converts closure to a curried function. (In general, f maps OO things to functional things.)  The result of knightMove([0,0]) will be a list (FunList) containing all positions  [x,y] where the knight can move from staring point [0,0]. 
That is why we call it non-deterministic computing.

So where can I go in 'n' moves?  We have seen this in previous post, but here is this code again:
 FunListMonad m = FunListMonad.instance

 def composeNtimes = f {n, Closure c -> reduceR(COMPOSE) << take(n) << repeat(c)}
 def knightNMoves = f {n, initVal-> composeNtimes(n, b(knightMove)) << m.pure(initVal)} 
 def allPositionsAfter3From0_0 = knightNMoves(3) << [0,0]

Short explanation: composeNtimes really does this:
  c << c << ... << c // n times

Now we simply use composeNtimes with b(knightMove) to accomplish monadic chain:
 b(knightMove) << b(knightMove) << .... << b(knightMove) // n times

Simple stuff!  Sorry if I bored you by repeating parts of my last post.
So here is another, more interesting, way to do the same thing using monadic left fold:       
 BaseM mf = BaseM.getInstance(FunListMonad.instance) //gets monadic functions

def knightNMoves =
       f {n, initVal-> mf.foldLM(apply,initVal)<< take(n)<< repeat(knightMove)}

that may require a bit of explanation.  First what is apply I need to answer this question with a question:  Is 5 a function?  
If f(5) is f applied with 5 why not think about it as 5 applied with f?  apply is Fpiglet function which does just this. Takes argument and applies function to it (all of these return the same value):
 apply(5, {it + 1})
 apply(5, PLUS(1))
 apply(5) << PLUS(1)
 PLUS(1)(5)
 PLUS(1,5) 
 {it + 1)(5)

The knightNMoves definition is equivalent to the following chain of fold operations (think of inject in Groovy, which is effectively left fold,  with monadic blows and whistles applied):
  acc0 = m.pure(initVal) =>
       acc1 = apply(acc0, b(knightMove)) => 
             acc2 = apply(acc1, b(knightMove))  =>...

which is the same as
  acc0 = m.pure(initVal) => 
       acc1 = b(knightMove)(acc0) => 
             acc2 = b(knightMove)(acc1) => ....

which in turn is equivalent to this:
      b(knightMove) << ... <<  b(knightMove) << m.pure(initVal)

and that is exactly what we wanted.

That is all very cool but, the code above gives us final positions of knight only. What if I wanted to see the full path, a list of moves that lead to the final position?
 Closure knightPath=  {path ->
     if(isEmpty(path)) {
        f [empty()] //list with empty list as element
     } else {
        FunList nextPos = knightMove(head(path))
        map(prepend(_, path), nextPos) //map partially applied on second position
     }
 }

Again somewhat straightforward stuff.  knightMove accepts single path, applies single knightMove to it to return a new list of possible paths. Last move is prepended in front.

Now we can do stuff like this:
  def initialPath = m.pure( m.pure([0,0])) //list of lists of positions
  def inNmovesAllPaths = f {n -> composeNtimes(n,  b(knightPath)) <
initialPath} 

To do something meaningful we need to be able to check if a path ends where we want:
  Closure pathLeadsTo  =  f {v, path-> isEmpty(path)? false: v == head(path) }

so pathLeadsTo([x,y]) << path will check if path leads to [x,y]

How about, we check if we can get to [6,3] from [0,0] in 3 moves:
  assert  0 < length << filter(pathLeadsTo([6,3])) << inNmovesAllPaths(3)

So let me raise a bar a bit and ask this question:  what is the shortest sequence of moves that goes from [1,1] to [6,5]?

def initialPath = m.pure([1,1])
def destination = [6,5]
def stoppingRule = {paths-> !(isEmpty<< filter(pathLeadsTo(destination)) << paths)}
def shortestPaths =  filter(pathLeadsTo(destination)) << 
       mf.foldLMUntil(stoppingRule, apply, initialPath) << repeat(knightPath)

assert  ! isEmpty(shortestPaths)
println funlistOut << head << shortestPaths

Here is explanation:  We have used another Fpiglet function: a monadic fold with a stopping rule.    knightPath is placed in infinite sequence and we are folding this sequence with a stopping rule, which checks that we arrived at [6,5] Otherwise the folding logic is the same foldLM logic we have seen already, one using function application.
So that code is no big deal!
I hope I have shown some power of monadic computing.  If it looks interesting check out Fpiglet.

Sunday, July 21, 2013

Coding with Monads in Groovy, making Groovy more functional with Fpiglet

Monad is a quite simple concept yet is is perceived as a scary and complex thing that developers will never understand.  Fpiglet brings monadic computing to Groovy and the task should not be daunting at all.

History:  Monad concept came from Math, fortunately you do not need to understand much (or any) of Mathematics to understand and use monads.  In the nutshell, monads (in math, and in functional programming) are abstraction of 'container' concept.  Monad is simply a sophisticated term for a box.    If you know some Haskell you can read more about how math monads relate to monads used in programming: Haskell Understanding Monads (look at the end of that document).

What is it about:  It seems to me that functional programming is a simple concept that is made very confusing by all the attempts to express it using OO terms.  To any software engineer, Input-Output concept should be like bread and butter.  Functional programming is about transforming input to output.   The only trick is that these transformations are required to be pure (or safe) and are referred to as functions.
Pure/safe means that they do not change any state and do nothing else other than creating the output.

   data1 => function1 => data2 => function2 => data3 => ...

There is only one thing needed for that chain to work:  the result from function1 needs to match the input for function2...   This can be done by using bunch of tricks. One of them is the concept of curried functions (see my previous posts), another one is, yes, the monad.

In software we have a lot of boxes - we often put data into something that has additional context. Examples could be all the 'holder' classes which hold an object and some extra information.
One cool example is functional Either type which stores object or an error information why the object could not be created.  In this post, I will focus on one example that is very comprehensive and maybe one of the hardest to understand:  List as a Monad.

List as a Monad:
So putting a into a list [a] we are placing into a box. It even looks like a box ;)
This allows as to think about 'a' in a wider context of non-deterministic computations.  Typically when you perform an operation you just expect one result.  But if you define an operation like this
  Closure eitherAddOrSubtract1 = {a ->  [a-1, a+1]}

you are defining a function which says that there is more than one possible outcome.

So let us play some chess.  If position of my knight on the chess board is [0,0] (Groovy 2-element List) I can write the possible set of next positions as this:
[[1,2],[2,1],[-1,2],[2,-1],[1,-2],[-2,1],[-1,-2],[-2,-1]]

(for simplicity I assume that chess board has no boundaries so I can move around in any direction).

We can define a knightMove function like so:
  FunList knightPositions= funlistIn << 
     [[1,2],[2,1],[-1,2],[2,-1],[1,-2],[-2,1],[-1,-2],[-2,-1]]
  
  //vector plus
  Closure vplus = f {a, b -> [a[0] + b[0], a[1] + b[1]]}
  def knightMove = {pos -> map(vplus(pos)) << possiblePositions}

(we are using Fpiglet here a bit, we are transforming Groovy list into a Functional List and use curried closures (see f in front of the closure) which can be applied with just one parameter even if they need 2. Please remember that << in Groovy is both closure composition as well as a way to pass argument to a closure)

It would be interesting to see where can I get in 3 moves.  So I would like to chain (compose) the calls to knightMove like so:
     knightMove << knightMove << knightMove << [0,0]

This will not work because knightMove output is a List of positions but input is a SINGLE position.
That seems more like artificial obstacle than anything else.  

This is what monad is about.  If you have a function (in a very pseudo code)
  fn: a  -> box a  //maps a to boxed a

then monad knows how to chain or compose it.  It does it by implementing a 'bind' function.
The following code in Fpiglet calculates a list of all possible knight positions after 3 moves

  Closure move3x= b(knightMove) << b(knightMove) << b(knightMove)
 FunList in3moves = move3x << [[0,0]] 

Bind function my look like magic, but it simply does what it says. It takes a function fn which accepts non-monadic type and returns a new function which accepts monadic type!  No rocket science (in very pseudo code):
  fn: a  -> box a  //or fn: T -> FunList<T>
  b(fn): box a  -> box a  //or b(fn):FunList<T-> FunList<T>

To do that 'binding' monad implementation needs to figure out how the 'boxing' works. For lists this ends up being concatenating all possible results.  Now, these functions will compose just fine. 

And you can chain as much as you want:
  def composeNtimes = f {n, Closure c -> 
       reduceR(COMPOSE) << take(n) << repeat(c)
  }
  def inNmoves = f {n, initVal -> 
     composeNtimes(n,b(knightMove)) << [initVal]
  }

  def in4Moves = inNmoves(4,[0,0])

Notice that the above example uses right fold.  The same can be accomplished using monadic fold (which is left fold).  I will add a test case to Fpilget source demonstrating monadic fold solution in a few days.

Comprehensions: 
There is a more sophisticated idiomatic use of monads which I like to refer to as monadic comprehension.  You can do comprehensions with Fpiglet today, but most functional languages will give you some nice syntax sugar to make the code more readable.  
More info can be found on Fpiglet wiki pages, and I will write more at the time Fpiglet implements some syntax sugar for comprehensions.

-EDITED Aug 4, 2013- Fpiglet now implements simple monadic comprehension DSL!

You will find more examples of how to program with Monads in Fpiglet source code test folder.
I will be adding test code examples in the next few weeks.


  
   

Friday, July 5, 2013

How to fold Infinite List in Groovy - Functional Groovy with Fpiglet

Folding on infinite list. (To be exact, right-folding infinite list.)  That does sound impossible and is a frequently discussed puzzle that Haskell programmers enjoy.  How can you start at infinity and iterate backwards to the result?  Can it be done in Groovy as well?

We will use Fpiglet. The solution I am going to explain here is not as elegant as Haskell's but I think should be still quite interesting.  First some intro for all readers who are not familiar with functional terminology.

Introduction:  Fold and reduce functions are functional programming equivalent of 'iterator'.  Functional programs do not want to mutate anything so the fold functions provide a way to 'accumulate' new data from the list without mutating any state.  There are 2 ways to iterate over a list:  
  • scan it from the beginning to the end (left fold/left reduce)
  • scan if from the end to the beginning (right fold/right reduce)
Folding accepts initial value of accumulator, reducing takes first element of the list as accumulator. 
 foldL   (foldClosure, initAcc, list) -> finalAcc
 reduceL (foldClosure, list) -> finalAcc

where
  foldClosure(acc, element) -> newAcc

So the folding functions scan the list and for each element execute foldClosure passing it current accumulator and current element. The job of foldClosure is to create new version of accumulator so nothing is mutated.  I am sure you recognize similarity to Groovy Collection.inject(Object, Closure) and Collection.inject(Closure) because these are OO equivalents of foldL and reduceL.

Here is an example from Fpiglet, we use foldL to calculate smallest element in the list:
  assert 2 == reduceL({acc,b -> (b<acc)?b:acc}) << [4,10,2,7]

this does not look much better than Groovy code would so here is more of Fpiglet style:
 assert 2 == reduceL(MIN)<<[4,10,2,7]

This will scan the list (4,) 10, 2, 7.  If we wanted to scan the list (7,) 2,10,4 we would write this:
 assert 2 == reduceR(MIN)<<[4,10,2,7]

One difference is that with right-folds the folding function has parameters flipped:
  foldClosure(element, acc) -> newAcc

Infinity (and beyond?):   Fpiglet implements functional programming version of list which is lazy. That means that what is on the tail of that list is not evaluated until needed. This allows for creation of recursive lists (also called streams) which never end like all natural numbers:
  def naturalNums = naturalNumbers() 

Fipglet has special version of right-folds which work with infinite lists: foldXR and reduceXR.  

So lets go starting at infinity all the way back to 1 ;),  FRIST is one of predefined funcitons returning first argument :
  assert 1 == reduceXR(FRIST) << naturalNums

Lets find first natural number larger than 50 which can be divided by 7: 
 def foldClosure= f {b, acc -> (b>50 && b%7==0)? b: acc()}
 assert 56 == reduceXR(foldClosure) << naturalNums

It works!  But wait, I was not writing about curried functions for nothing in last 3 posts, this is better code example:
 def finder = f {predicate, b, acc -> 
         predicate(b) ? b: acc()
 }
 def res= reduceXR(finder{it%7==0 && it>50}) << naturalNums
 assert 56 == res

We have folded natural numbers all the way from infinity back into 56!

How it is done:
Functional lists are immutable and are created by prepending elements one in front of the other.
So a list like [4,10,2,7] can be written in Fpiglet like so:
  e(4) << e(10) << e(2) << e(7) << empty()

It is even more intuitive to see it using Haskell notation:
   4 : 10 : 2 : 7 : []  

or, to be more explicit
    4 : (10 : (2 : (7 : [])))
now I want to right-fold this list using folding closure, let us take something simple, we tried MIN, MODULO, let us try PLUS (+).   
Right folding the above list with + is equivalent to this:
      4 + (10 + (2 + (7 + [])))

Did you notice that I just replaced ': 'with '+' ? 
So for generic folding closure fc,  if I could only write  
     x 'fc' y  //instead of fc(x,y) 

we would get this:
    4 'fc' (10 'fc' (2 'fc' (7 'fc' [])))

Now imagine, what happens if for some values of x in fc(x,y), the result does not depend on y.  Like in our situation where predicate(b)is satisfied!  Then we get this:
    4 'fc' (10 'fc' (2 'fc' (...who cares...)))

The only issue is how do I know that fc does not care about second parameter?  reduceXR and foldXR pass second parameter (acc) as a closure!  To use accumulator, the closure needs to resolve it first.  It returns the new accumulated value of course, not a closure.  The logical signature for folding closure would look like this

  fc :: el -> (_->acc) -> acc //el -list element, acc -accumulator

Case solved!

It is not so good:
FoldXR and reduceXR implementation are prone to stack overflows.  This is true even for Haskell!   And it follows from the fact that we really are creating a long chain of composed functions!
There are other functional methods which work well on infinite lists, like map or filter

Here is a simple chain of Fpiglet code, which is stack overflow safe:
 def res= filter{it%7==0} << filter(LARGER(50)) << naturalNums
 assert [56] == funlistOutTake(1) << res

I hope you enjoyed this post and I invite you to check out Figlet.






Sunday, June 30, 2013

Groovy more functional with fpiglet - Curried Functions vs. Groovy Closure.curry

Fpiglet add support for the powerful concept of curried functions. This post compares this new functionality against simply using Closure.curry() methods in Groovy.
Originally I have 3 posts on this topic. Two of them have been moved and are now part of Fpiglet documentation.

Let us consider these Groovy closures:
 def c1 = {a,b,c,d -> a + b + c + d} 
 def c2 = {a->{b->{c->{d-> a + b + c + d}}}}
 def c3 = {a,b -> {c,d-> a + b + c + d}}

In Groovy you need to call them like this:
  c1(1,2,3,4);  c2(1)(2)(3)(4);  c3(1,2)(3,4)

and not in any other way unless you start using verbose .curry() method. By contrast with Fpiglet you can call them any way you like:
 def fc = f c1 //could be c2 or c3 with the same results 
 assert fc(1)(2)(3)(4) == 10 
 assert fc(1,2)(3,4)   == 10 
 assert fc(1)(2,3,4)   == 10 
 assert fc(1,2,3,4)    == 10

So why is that so important?

How Groovy curry chains work:
The following code example describes how Groovy curry method works:
 //see top of this post for c1 definition
 assert 10 == c1(1,2,3,4) //as expected
 assert c1.curry(1).curry(2).curry(3).curry(4) instanceof Closure
 assert c1.curry(1).curry(2).curry(3).curry(4)() == 10

So even if we were to magically get rid of explicit curry() calls Groovy curry() would result in something like this:
 //Groovy curried equivalent of c1(1,2,3,4)
 //(x) represents curry(x) and () represents .call()
 c1(1)(2)(3)(4)() == 10 //UGLY!

and the following code in Groovy language means nothing no matter how you curry it!
 c1(1,2)(3,4) //makes no sense

Arbitrary number of parameters closures with Groovy chains:
Part of the ugliness of the previous example can be explained by Groovy's need to support Closures with arbitrary number of parameters. Here is a textbook example using the flexible Object[] arg type:
  //GROOVY code
 def sumAll={Integer[] args-> 
      args.inject(0){acc, a -> acc + a}}

 assert 4 == sumAll(1,1,1,1) //works great!
 assert sumAll.curry(1).curry(1).curry(1).curry(1) instanceof Closure
 assert sumAll.curry(1).curry(1).curry(1).curry(1)() == 4

So curring works the same way for Groovy Closures with arbitrary lists of parameters as for fix parameter sets. And that is different from what we need.  Arbitrary parameter lists can be convenient, but the benefits of curried functions outweigh that by several factors.

Fpiglet version of sumAll:
  Closure sumAll = reduceL(PLUS)   
  assert 11 == sumAll ([5,5,1])

That does look much better than Groovy's version!
Fpiglet functional equivalents of Groovy's collection inject method are reduceL and foldL curried functions. Both are implemented on FunLists (which is Fpiglet functional list implementation).  But as you can see the above code uses them directly on Groovy lists!

Standard functions like reduceL are mapped over to Groovy Lists. This mapping over is possible because FunList -> List   defined by Fpiglet is a Functor.   In fact, the above code is syntax sugar version of:
   Closure fmap = FunListToListFunctor.statics.fmap
   Closure sumAll = fmap(reduceL(PLUS))

Functors are truly very powerful tool!  But code like that relies heavily on curried functions.
Just notice that fmap needs 2 parameters but it is given 1, reduceL needs 2 parameters but it is given 1 and, yet, everything works.
(I wrote more about Functors in this post  Better Polymorphism Post)

There is one more important point here:  in standard Groovy code: list.inject, the method inject is owned by the list.   In Fpiglet code: reduceL, PlUS, and reduceL(PLUS) are first class citizens, not owned by anything!  Data and data manipulation are decoupled.

Conclusions:
As we have seen Fpiglet Haskell style curried functions improve over Groovy's curry in more than just terseness   In Groovy language program using Closure needs to know if it needs to invoke 'c.curry(x)' or 'c.call(x)' or (as we have seen) both.

What makes curried functions powerful is freeing programs from needing to know that.  The program simply 'applies x' by using simple syntax: '(x)' or if it needs to apply x and y then will do either '(x)(y)'  or '(x,y)'.  The result is a terse and beautiful code like the sumAll example shown above.  The additional benefit is that data manipulating logic becomes first class citizen and the data is effectively decoupled from manipulation.


Thursday, June 27, 2013

Making Groovy more functional - Fpiglet open source

I started a new project on google code it is called Fpiglet:  http://code.google.com/p/fpiglet/
It stands for FUNctional Programming in Groovy and the 'let' is from a syntax I will try to DSL at one point.

My main motivation is to have fun with it.  I am spending my work hours dealing with very imperative code in Groovy and Grails and I often have a feeling that lots of that could be made more readable, maintainable and beautiful it it was just less OO and more FUN.

The other motivation is my perception that most (almost all developers) today miss out on one very useful concept:  function composition.  For that reason I started with supporting the concept of curried functions.

I am starting with basics:  Lazy Lists, Streams, but I also DSL-ed some syntax like if-elseif-else.
I am trying to use function composition whenever I can so my DSL is drawing heavily on curried function composition.

With DSL my goal is not to meta-program Groovy into something else.   Rather be 'gentle' and not intrusive with DSL.  My goal it so 'eat my own dog food' approach.  I also do not believe in writing super-complex hard to maintain imperative code just to expose nice interface to the outside world even if it that interface looked like Haskell.

Why the name?  I considered groovyz  but then that is just being a copy-cat and I am more motivated by Haskell these days.  GroovyH?

Saturday, May 25, 2013

Better Polymorphism. Polymorphism where apples are not oranges.

Subtitles:   - Polymorphism without curly braces.  - Lifting == next polymorphism.   - How to program your bike tube.  - Grandparent of Functional Programming.


I have finished my last year posting by writing about polymorphism, I want to start on the same subject and do a better job.  This is the longest post I ever wrote and I hope the longest I ever will.  I hope you will find it interesting and Thank You for reading!

POST INTRO:
- 'Doctor, each time I see a code like that in Groovy
  def listX = listY.collect{ ... }

 I see a torus and want to ride my bike.' 
- 'Oh no! you have a case of Polymorphism'

This post is not about what polymorphism is.  It is about what polymorphism can be.

POST BODY:
Definition: For an OO programmer polymorphism means a more sophisticated version of a cookie-cutter.  Typically this term is associated with the idea of applying the same 'thing' across many different 'things'.  I want to define it as Apply concept A to a set of concepts X. Most often A will be an operation/method (or a set of these) and will describe some type of a behavior, so a developer can say that A can be polymorphically applied to set X.

Classic OO imperative polymorphism suffers a bit from weak semantics where 'A' does not really mean 'A'. To achieve a 'Better Polymorphism' we will need to work on stronger semantics. Most interesting stuff happens when X contains bunch of different things and A provides a 'viewpoint' on all the things in X, but the essence of 'A' stays intact in some way. These are the cases which go beyond interesting and become an eye opening intellectual experience.

Classic Examples of OO Polymorphism: As I said, OO polymorphism is typically semantically weak:  apples become oranges so we can make ourselves a polymorphic screwdriver.
One set of such examples is when X=everything. If you can say something about everything then it is either obvious or incorrect.  Still, many programming examples do exactly that:
In obvious category:
Java Object.toString(): A='describe yourself', X=anything
In incorrect category:
Java Object.equals(Object o): A='concept of being equal', X=anything
(Why do I think that is incorrect?  Why would you think a meaningful equals comparison is always possible computationally or even logically? But that is a longer story well beyond this post ...)  
In Java, 'equals' becomes something less than what the 'real equals' should be.
More interesting example: C++ or Groovy overloading of +:   A='+ operation', X includes numbers, strings, collections, maybe a timestamp and duration, whatever else programmer decides makes sense with '+'.
This is all very imperative, programmer 'implements' and decides what '+' means.  So often '+' becomes just a neat syntax and any deeper 'essence' of '+' is lost. 

Polymorphism in Other Sciences?  Can software engineering learn something new about polymorphism from other sciences?  My examples will have a heavy bias on math, because math was my strong interest in the past and I still remember a little bit about it. I challenge you to come up with your own examples.

Partial Differential Equations (PDEs) offer many examples fitting well into my definition of polymorphism.
PDE Example 1: Often the same family of equations is used to model a range of totally different concepts. It maybe no surprise that the same set of equations models gas flow and traffic congestion. It is much harder to grasp that the famed Black–Scholes formula for pricing stock options (in Finance) is really a time-reversed (or backward) heat equation (in Physics)!
So: A=single PDE, X=parts of Physics, Finance and maybe other parts of science.
The essence of that PDE is described by the PDE itself, it is the same equation, yet it can be polymorphically applied to a large set of examples.  This is 'semantically strong' and often eye opening!
PDE Example 2: Once upon a time, I wrote a paper studying convergence of numerical solutions to a system of PDEs called Broadwell Model. I studied these using ... fractals.
So A=fractals, X=a PDE model in gass dynamics.
To do that I had to, of course, do more than just to start using fractal lingo when talking about PDEs (that would be nonsense).
PDE Example 3: Compensated Compactness Theory studies convergence of solutions to PDEs using ... measure theory.

Let us move on to something else than PDEs (or is it something else only because we have not found a polymorphic enough way to look at it yet? ;) ).
Grandparent of Functional Programming: There is this super cool part of math called Algebraic Topology.  This branch of math is just one big polymorphism and is one of the most intellectually stimulating pieces of science I have ever seen.
Algebraic Topology transforms manifolds (geometrical and topological concepts) into groups (algebraic concepts). I remember using phrases like 'thinking in CAPS' or 'functorial thinking' to describe the overall idea of such high level transforming.  I was not much into programming at that time so the term polymorphism did not cross my mind.
Still, the definition of polymorphism is matched perfectly (A=Algebra Groups, X=Manifolds). 
Many things that have been extremely hard to prove for an orthodox topologist became almost trivial to do in algebra.  This polymorphic approach offered by Algebraic Topology was a game changer in understanding of manifolds and lead to discovery of a lot of very cool math.

Algebraic Topology does its transforming in several different ways. These include concepts like homology, cohomology, homotopy .... All of these are a way to map a manifold into an algebra group preserving the 'essence' of that manifold in some way.

Side Note to get some intuition about what Algebraic Topology is about: 2-D sphere is totally different than 2-D torus (think of surface of a tube in your bike).  Both are hollow but in a very different way! 
On the sphere, all closed loops can be shrinked to a point so H1 (single dimension homology) is trivial.  On the 2-D torus you can draw loop around each of the 2 perimeters and you can start adding these loops (groups are about adding things) by rotating around one perimeter n-times and around the other k-times.  You can stretch and shrink these loops all you like, they will still rotate around torus perimeters the same number of times. So H1 of 2-D torus is the same as product of all Integers (understood as a group with + operation) with itself!

There are many other examples where concepts in one branch of math are used to solve problems in another branch...  but I need to stop, this post is not about math.

Another Side Note: I hope I did not lie too much. This post brought some very fond memories, but I have not done math, and Algebraic Topology in particular, for so long.

Functor:  We need something which is good at 'transforming concepts preserving essence of things'.  The name I am thinking about here is 'Functor' and all the transformation used in Algebraic Topology (homology, cohomology,  ...) are, in fact, functors.  (Not to be confused with C++ concept using the same name).

Functors have been studied on their own by a branch of math called Category Theory (I never embedded myself much in it).  Category Theory is arguably the parent of Functional Programming.  If that is so, Algebraic Topology is the grandparent. And that is the coolest grandma any science can have!

Before we move on, I would like to assert one observation, science seems to have no use for semantically weak polymorphism, it cares that A is still A in some deep way and that it is not just a name universally applied to different concepts.

Functor Definition:  So what is a functor?  Here is a wikipedia link for you: http://en.wikipedia.org/wiki/Functor  The most intuitive way to think about it: functors are for mapping things over. It must map identity into identity and preserve morphism composition (think for now that morphism==function and 'o'is function composition). The covariant functor definition rules are copied here:

  F(id) = id
  F(f o g) = F(f) o F(g)

Functor in Programming!: Can you think of a functor in programming?  There are actually a few of them but I will just explain one:  Think of transforming which works on a very high level (remember this is a high level thinking, thinking in CAPS).  Think of transforming types, one type into another. One such transform is  
  T -> List < T >
I like the [] notation so I will call this transform (or mapping):
   []: T -> [T]
but Java hardcores should read this as List: T -> List < T >
(which with Java type erasure means nothing, but well, still makes some sense, right?).

There is a method in Groovy working on collections called 'collect' and it's equivalent is typically called 'map' in other languages. Here is an example usage:
  assert [1,4,9] == [1,2,3].collect {it*it}

I am sure you agree that: 
Closure id = {it}
assert anyList.collect(id) == anyList == id(anyList)

and that is the first rule for being a functor. Let test the other one using an example:
assert [1,5,3].collect(it-2).collect(it * it) ==
       [1,5,3].collect((it-2) * (it-2))

Yes, Groovy's collect makes [] into a covariant functor!

Better Polymorphism (using Functor): Now since the [] operation preserves 'essence' of things, I should be able to use it.  Suppose I want to lowercase all elements from a list of strings.
You could write this:
   def lowerCaseList = ['HELLO', 'THERE'].collect {it.toLowerCase()}

but that is just missing the point altogether (and it uses evil curly braces). I want to be able to write something closer to the following (because functors preserve essence of things):
   def lowerCaseList = ['HELLO', 'THERE'].toLowerCase() 

the idea is that the function is magically lifted or mapped over by the [] functor so it can operate on functor values.  After all, compiler should know that [] is a functor!
Maybe in the future... for now, at least in Haskell, you could do something like this
   lowerCaseList = (fmap toLowerCase) ['HELLO', 'THERE']
  
That is some polymorphism for you!!!  Think of different functors ([] is just one example) and ability to write a cookie-cutter code across all of them.  Examples are Maybe (a concept replacing handling of null values) and Either (concept of handling error conditions without ugly try-catch).  You code might even end up working on the tube in your bike!  (think of a changeMe function ;).  

Even Better than Functor! (== Better than Better Polymorphism):  Functor is not the end of the story for 'preserving the essence of things' as far as programming goes, it is the begining.
There are 2 stronger super-concepts:  Applicative Functors improve upon Functors and  Monads improve upon Applicative Functors.

The idea is that I do NOT want to implement '+' operation on lists! I want the language just to know what to do!  If I know what 1+4 is and 1+5 is, etc I should automatically know what [1,2,5] + [4,5] is!  There is a little issue with using plain functors because they do not understand interactions between elements.  This is where Applicative Functor solves the problem!

It turns out that there are two natural ways to make [] an Applicative Functor (and I wrote a bit about both in my previous post).  Here is the recap: one way is so that:
  [1,2,5] '+' [4, 5]=[1+4, 1+5, 2+4, 2+5, 5+4, 5+5]

(this is called non-deterministic computing)
and the other works so that:
  [1,2,5] '+' [4, 5] = [1+4, 2+5] 

(these are zip lists).  Haskell has decided to make [] into non-deterministic computing and created a separate type called ZipList to handle the other case.
Now we could 'lift' any two or more argument operations automatically!  There is some extra typing involved in Haskell (you cannot just say [1,2,5] + [4,5]) but the work is really done for you and this extra typing is minimal.

I need to stop somewhere so I am not even going to try to define Applicative Functor. 
We have done a full loop, from OO imperative '+' example to the '+' example preserving the 'essence' of '+'.  

POST SUMMARY:  So all this transforming can lead to a very interesting polymorphism.  List is polymorphic with a tube in your bike!  So how is that useful?  I think some points are worth reiterating:

(1) The fact that mathematical concepts like homology are polymorphic with several programming concepts (like homogeneous lists, handling of nulls (Maybe) or handling of error conditions (Either)) is very much an eye opener.   That means that, in particular, we could write code that works across all these concepts!   In fact, Functor is a class type (kinda like interface) in Haskell.   OK, there is probably not that much that can be coded at such high level of abstraction, but more coding is possible (and done) against Applicative Functor (also a class type in Haskell) and even more against Monad (again a class type).  This is a true high level coding in CAPS!

(2) And these concepts are not apples and oranges polymorphic, they are 'better polymorphism' because they preserve the essence of things is some way.  That means we can 'lift' functionality.  If you wrote a library that does interesting things with type T, a lot of your work could be just 'lifted' to [T] (or any other Functors mapping T)  ... and even more of your code will 'lift' for free to any Applicative Functor.

(3) Let me emphasize the 'lifting' point.  'Lifting' is the next level of polymorphism.  This concept is equivalent to some of smartest parts of math ever,  Algebraic Topology lifts algebra into topology.  Other math examples lifted Measure Theory  or Fractals into PDEs.
But wait, examples with PDEs did not use functors!  What I am trying to say is that functor is not the only way to lift.  It is however the only way to lift I know in computing.

I hope you enjoyed this post.  It has been written by a newbe Functional Programming enthusiast, but  it covered some less than trivial stuff (maybe this is a risky combination).  It also was opinionated like my other posts, but I hope opinionated in a good way :).  And I hope it offered a unique perspective even to some Functional savvy developers.

By the way, did you notice that my post is visually organized into 3 sections making it polymorphic with other writings using this important presentation guideline.   You think that is cool,  NO, it is not cool!   That is just a contract-based, imperative, old style polymorphism, Gotcha! ;)