Tuesday, December 16, 2008

Combinators for fun and profit

Wikipedia says ..

"A combinator is a higher-order function which, for defining a result from its arguments, solely uses function application and earlier defined combinators."

Primitive functions that do not contain any free variables. The functions take some arguments and produce a result solely based on those arguments only. No side-effects, nothing. In concatenative languages like Joy and Factor, combinators are formed from the primitive elements by quotation and concatenation, using nothing but function composition, transforming your system into a rich algebra of programs. As I mentioned in my last post, there are no variables in Joy. Data is manipulated through a stack. Along with data, Joy pushes programs themselves onto the stack and manipulates just like data through combinators.

I am an enterprise programmer - what do combinators buy me ?

Nothing, except maybe a good evening over a weekend. Seriously! This is a continuation of my last post dedicated fully towards pure joy of writing programs. And this post is about some possibly wasted efforts that I have been plunging into, quite off and on. Dear prudent reader, you may not find anything useful out of it .. it is just a truthful and honest account of self indulgence into something I found enjoyable.

OK .. so you have been warned ..

Consider the simple function that finds the arithmatic mean of a list of numbers .. using a language that's quite not-so-elegant for combinator programming .. Scala ..

def arith_mean(list: List[Int]) = {
  list.foldLeft(0)(+ _) / list.size
}


The method is purely functional, has no side-effects, but really not a manifestation of being produced as a composition of primitive functions. The parameters get in the way, the type annotations are a noise. Joy makes combinator programming more concise, concatenative and reveals the intention purely as a composition of combinators .. Shout out the following aloud, and that is exactly what the program does, as every function works through the available stack .. Here is the program for arithmatic mean in Joy ..

dup  0  [+]  fold  swap  size  /


and here is the commentary of how the operators and combinators above compose ..

  1. Duplicates the list on top of the stack

  2. Does a fold to add elements of the list, which is on top of the stack. So the top of the stack contains the sum of all elements of the list. And the next element of the stack contains a copy of the original list

  3. Swaps the top 2 elements of the stack - the top now contains the list

  4. Replace the top list with its size

  5. Apply division on the top 2 elements of the stack to get the result



A more idiomatic version of the above will use the cleave combinator that does compact the above program and even parallelizes the computation of the sum of the elements and the size of the input list ..

[0 [+] fold]   [size]   cleave   /


Meanwhile, Reginald Braithwaite is having a party with combinators in his specialty un-blog homoiconic. He is exploring ways to write more enjoyable programs in Ruby using Krestel, Thrush and the other combinator birds that Raymond Smullyan has immortalized in his creation To Mock a MockingBird, as a tribute to the bird watching passion of Haskell Curry. Twenty years since the book came out, it is still a joy to read.

In his series on refactoring code with combinators, Reginald presents how to refactor a sum_of_squares method using a divide_and_conquer combinator. The method computes the sum of squares of a tree of integers represented as a nested list. The idea is to model the divide_and_conquer paradigm as a combinator and have the sum_of_squares method as an implementation of that combinator.

Here is my sum_of_squares method in Scala for integers .. functional and recursive ..

def sum_of_squares(list: Iterable[Any]): Int = {
  list.foldLeft(0) {
    (s, x) =>
      s +
        (match {
          case l: Iterable[_] => sum_of_squares(l)
          case e: Int => e * e
        })
  }
}


And now a divide_and_conquer combinator in Scala that defines the strategy ..

def divide_and_conquer(value: Iterable[Any],
                       conquer: Any=>Any,
                       divide: Iterable[Any]=>Iterable[Any],
                       recombine: Iterable[Any]=>Any): Any = {
  recombine(
    divide(value).map { (x: Any) =>
      x match {
        case l: Iterable[_] =>
          divide_and_conquer(l, conquer, divide, recombine)
        case e =>
          conquer(e)
      }
    }
  )
}


where ..

  • divide is the step that divides the main problem into subproblems

  • conquer is the trivial case for the smallest part

  • recombine is the step that pieces solutions to all subproblems together


And here is the implementation of sum_of_squares using the combinator ..

def sum_of_squares(l: List[Any]): Any = {
  divide_and_conquer(l,
    (x) => x.asInstanceOf[Int] * x.asInstanceOf[Int],
    (x) => x,
    (x) => x.asInstanceOf[List[Int]].foldLeft(0){+ _}
  )
}


Quite a bit of noise compared to an implementation using a concatenative language, with all parameters and type annotations sticking around. But it's not too ugly compared to what other mainstream languages can offer .. and anyway it's fun .. I am sure someone more conversant with Scala will be able to make it a bit more succinct and idiomatic.

Here is another implementation of the divide_and_conquer strategy using the combinator above .. flattening a list ..

def flatten(list: List[Any]): Any = {
  divide_and_conquer(list,
    (x) => x,
    (x: Iterable[Any]) => x,
    (x: Iterable[Any]) =>
      x.foldLeft[List[Any]](Nil){
        (s, x) =>
          s :::
            (match {
              case l: List[_] => l
              case e => List(e)
            })
      }
  )
}


Quite ugly .. huh ? Looks like Scala is not an ideal language for combinator based programming. Though we have some very good implementations of combinators in Scala, the parser combinator library, the pickler combinator library etc. But if you are serious about combinators and combinator based programs, jump into the concatenative languages. Joy gives us the following implementation of flatten ..

flatten  ==  [null]  []  [uncons]  [concat] linrec


Here goes the commentary ..

  1. If the parameter list is empty, nothing to flatten, leave the empty list

  2. Otherwise, uncons to get the first and its rest

  3. Flatten rest through anonymous recursion on it

  4. Concatenate the saved first to the result


Quite intuitive, and implemented using function composition only. Just one trick - what is the linrec doing out there ?

linrec is one of the most widely used recursion combinators in Joy which can be used to avoid recursive definitions in your program. It encapsulates the recursion part within its implementation, much like what we have done with the recursion in our divide-and-conquer combinator. Joy also offers a host of other recursion combinators like genrec, binrec, tailrec etc. Using them you can write non-recursive definitions of recursive tasks through simple composition and quotation. But that is the subject another rant .. some other day ..

13 comments:

Anonymous said...

while this was interesting, the code was unreadable and additionally, I like to generally avoid recursion as I consider this to be the "goto" of the new millenium.

Tony Morris said...

Hello Anonymous. The code was completely readable. I read it fine. See how that works? It's quite a pointless claim until you can provide an objective definition for "readable" (which is possible by the way).

Your "belief" about recursion is quite amateurish - I recommend you learn what "proof by induction" means to get started.

GM said...

The for loop of the new millenium, maybe. Certainly it's good practise not to use explicit recursion where you can avoid it, but I'm not convinced you can _always_ avoid it like you can with goto. Mind you, once upon a time people weren't sure about goto.

Unknown said...

Greg -

Re: "Certainly it's good practise not to use explicit recursion where you can avoid it" .. That is precisely what recursion combinators do. They give a recursive definition of the combinators that does make it possible to eliminate all other recursive definitions from your program. See the section "Recursion and its elimination" in this paper.

Cheers.

Eric said...

Hi Debashish,

Very nice article, thanks. I believe that there's a lot to gain by understanding that there are higher possible levels of abstraction in our programs.

But that also hurts the mind of the casual reader! I also wonder how maintaining and debugging goes with concatenative languages. It looks a lot like mathematical proofs at that point.

One (very) small Scala point also:

You can rewrite:

list.foldLeft(0) { _ + _ }

with

list.reduceLeft(_ + _)

Cheers,

Eric.

GM said...

I don't know what your toolbox of recursive combinators looks like, but mine isn't expressive enough to eliminate all explicit recursion without at times making the code more complex and hence less clear - and the linked paper only lists a coarse subset of mine.

I conjecture that any toolbox which _was_ expressive enough would be prohibitively large and complex. But I would love to be proven wrong about that!

James Iry said...

Eric, those mean two slightly different things. lst.foldLeft(0){_ + _} yields 0 on an empty list. lst.reduceLeft{_ + _} yields an exception on an empty list.

Unknown said...

Eric -

Re: "But that also hurts the mind of the casual reader! I also wonder how maintaining and debugging goes with concatenative languages. It looks a lot like mathematical proofs at that point."

I think you missed the fun part of it :-). Indulge in concatenative languages like Joy to get more fun out of programming. It's quite difficult to imagine people programming in Joy / Factor as a day job. As a prelude you may want to go through the first post in this series - enJOY.

Cheers.

Stacy Curl said...

You might find interest in the following articles which examines recursion patterns:

http://hamletdarcy.blogspot.com/2008/07/morphisms-for-masses.html

'A tutorial on the universality and expressiveness of fold' (www.cs.nott.ac.uk/~gmh/fold.pdf) to figure out the function needed.

A fold can be defined for much more than lists, so one can defined one for a tree. It would be nice if Scala has foldLeft & foldRight defined on an interface (Foldable[T] ?) which would allow you to do: def sum_squares(foldable: Foldable[Int]) = { foldable.foldRight(0) (_^2 + _) }. You would need to use an explicit Tree[Int] type too instead of List[Any].

Unknown said...

Stacy -

Thanks for the links. I am currently reading the "universality and expressiveness of fold" document.

Cheers.

James Iry said...

Scala isn't particularly good at points free programming, but in Haskell

flatten = foldl (:) []

I remain unconvinced that concatenative languages are really buying much over applicative languages, as interesting as they are.

Also, most concatenative languages use the stack as a giant ball of shared mutable state. IIRC Joy is an exception in that the stack is a functional, persistent structure so that code can't modify the stack so much as pass a new version of it to the next bit.

Unknown said...

Hi James -

re: "Scala isn't particularly good at points free programming"
+1 on your thoughts .. and that is what I have indicated in the post. Haskell is the closest in this regard. I plan to discuss more in an upcoming post. Apart from point free programming, Joy also has "quotations" and combinators that dequote for execution that add to the power of combinator programming.

re: "I remain unconvinced that concatenative languages are really buying much over applicative languages, as interesting as they are."
Sure. If you have followed my earlier post, I am trying to get into Joy for enjoying the fun part of it. After all it gives a much more broader and fuller perspective to your programming acumen and instincts :-).

Cheers.

James Iry said...

Oops, Haskell is
flatten = foldl (++) []

I copied the wrong thing out of my session. :-)