What is special about combinators in Joy

I am continuing my rendezvous with Joy, and this post is yet another rant about my perception of why combinators are real first class citizens in the paradigm of concatenative languages. Many of today's languages offer combinator libraries, but, with the possible exception of Haskell, none match the elegance that Joy offers.

Combinators help programming at a higher level of abstraction. In any functional language, using maps and folds definitely make your program more expressive than explicit recursion or iteration. Consider this snippet that uses map as a transformer over a list to convert every element of the list to upper case ..

upperCase xs = map toUpper xs


and here is the same using explicit recursion ..

upperCase (x:xs) = toUpper x : upperCase xs
upperCase []     = []


Apart from the former being more expressive, using the map combinator also helps you separate the strategy from the implementation of your program. map is a higher level abstraction and the implementation of map can be varied from recursive to iterative without any impact on the client code base. For example, without tail call optimization on the JVM, Scala implements List.map as an iterative method as opposed to the recursive implementation of Erlang map.

So, always use combinators to program at a higher level of abstraction.

In Joy, programming with combinators is the most natural way of doing things. In case you are just wondering, why is it not so with the programming language of your choice, the reason is in the architecture of the language. The combinators which I implemented in Scala, in my last post, did the stuff, but do we see such usages in real life ? Even with languages like Ruby, which do not have the noise of type annotations, combinators like divide_and_conquer, are not in common usage. The only possible exception to this today is Haskell, which allows point free programming, is referentially transparent and allows algebraic program transformations much like using formal methods through the medium of programming. And combinators are the most natural idioms in concatenative languages like Joy.

Why is that ?

Combinators are most effective when you compose them from atomic programs and evolve towards the bigger whole. And the closer you can get towards algebraic transformation with your combinators, the more elegant the process of composition looks. Today's mainstream languages are based on application of functions on parameters, leading to complex evaluation rules. Formal parameters add to the noise of composition and make the process less elegant. In statically typed languages, you also have the type annotations that add to the complexity of composition. On the other hand, in Joy, every combinator has the same form (Stack -> Stack) and gets all parameters including quoted programs from the stack itself. Hence you can write elegant compositions like 1 [*] fold to define the product function over the elements of an aggregate. Today Haskell allows such point free style of programming (product in Haskell will be foldl (*) 1), but none of the other mainstream languages come even close. It will be interesting to compare Joy with Haskell with respect to rewriting capabilites and application for formal methods.

Perhaps, the most important feature in Joy that makes non-invasive composition of combinators work like a charm is the datatype of quoted programs. A quoted program is just another list that happens to be on top of the stack when a combinator expects it. And the list can very well be generated as a result of other combinator operations. It is this generalization that unifies all combinator operations. In other languages, combinators work on different abstractions, while in Joy, it is always the same thing - combinators get lists on top of stack (which are incidentally quoted programs), execute them and return a stack with the result. Hence map is a higher order function in other languages, while in Joy, map is still a unary first order function from stacks to stacks.

At the same time, quoted programs in Joy, allow the normal evaluation order semantics to be imposed during program execution, in an otherwise applicative model.

Here is an example ..

0  [dup * +]  fold


This is an example of using the fold combinator. The quoted program [dup * +] will be on the stack in passive form, and will only be active when we have the fold combinator being applied. The result is the sum of squares of the input aggregate.

Recursion Combinators

As mentioned at the beginning of the post, if explicit recursion makes programs hard to understand, how do we hide 'em ? Inside recursive combinators. But can we remove explicit recursion from individual combinators ? Sure .. we can, by introducing the venerable y-combinator. So, only the y-combinator will contain explicit recursion, and all other erstwhile recursive combinators will be implemented in terms of Y.

Let us visit the factorial example and find out for ourselves, how the y-combinator can be used to remove explicit recursion and what trade-off does it imply ..

Here is the explicitly recursive version of factorial in Joy ..

recursive-fac  ==  [0 =] [succ] [dup pred recursive-fac *] ifte


Just for the uninitiated, ifte is the if-then-else combinator in Joy that takes 3 program parameters - quite intuitively, the if-part, the then-part and the else part. Note how effectively, quotation has been used here to impose normal order of evaluation, aka call-by-name. Otherwise it would not have been possible to implement it at all.

and here is the version that uses the y-combinator ..

[ [pop 0 =] [pop succ] [[dup pred] dip i *] ifte ] y


where y is implemented as simply as ..

[dup cons] swap concat dup cons


and .. and .. which version do you think is more readable ? Of course the one that uses explicit recursion. Huh!

This is the problem with the y-combinator. It is too generic, all-purpose, and hence not enough descriptive. And when combinators are not self-descriptive, the readability goes for a toss. And this is yet another area where Joy shines ..

Joy has special purpose combinators for recursion that are independent of data types and enough descriptive depending on the structure of the recursion. Here is an example with the factorial computation ..

fac  == [null] [succ] [dup pred] [*] linrec


linrec is a recursion combinator that takes four parameters in addition to the data that it needs.

• The first one is the if-part, where we specify a condition.


• If the condition evaluates to true, then the second part (the then-part) gets executed and the combinator terminates.


• Otherwise we look at the next 2 parameters - called the rec1-part and rec-2 part.


• The rec1-part is executed and then the 4 program parameters are once again bundled together and the quotation form is immediately executed.


• This is followed by the execution of the rec2-part.

The entire sequence models what we call a linear structural recursion.

For other variants of recursive problems, Joy offers a host of similar other combinators ..

• binrec is for binary recursion, that makes problems like fibonacci computation or quicksort a trivial one liner


• tailrec is for tail recursion, quite similar to linrec but without the rec2-part


• primrec is for primitive recursion which offers suitable defaults for the if-part and the rec1-part

Then there are a host of other recursive combinators for more advanced recursions like mutual recursion, nested recursion, generic recursion with n-ary branching etc.

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 +
        (x 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 :::
            (x 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 ..

enJOY

Programming for the sole purpose of having fun with it - How does this sound ? We have been talking about learning a different programming language every year, taking on the pill of polyglotism, learning languages that inhabit the common runtimes like the JVM or the CLR. But all this for the purpose of making ourselves a better programmer and raising our programmer value index in today's market. Really how many of us can afford to do so ? Most of us have a day job where we work on mainstream programming languages, strive hard to meet up to the expectations of the enterprise client and ensure that each of us remain billable to the client in the foreseeable future.

This post is not about polyglotism for today's market. If you enjoy programming, yet missing the fun part of it, this post is to tickle your programming instincts, and reminding you once again about the loads of fun that you can get out of hacking over a seemingly weird programming language. You may be doing Java / C# in your day job, feel guilty about not yet joining the bandwagon of functional programming, and try to dabble with Haskell, Erlang, Scala or F# over the weekend and during the evenings. Or you may already have joined the bandwagon privately, forked off a branch of your favorite project repository, basking in the sunshine of Lambda The Ultimate, and eagerly awaiting the day when your manager will approach you with a Haskell or Lisp assignment in hand.

If you thought you are having enough fun with lambdas, look out for more fun with functional programming without lambdas. Lambda calculus is about functions and applications of functions on arguments. I have been just been introduced to a functional programming language named Joy, which is NOT based on application of functions to arguments.

Holy crap ? No parameters .. what do functions do ?

They execute instructions on values that they find on the stack. And this post is about enjoying the beauty and savoring the fun that learning Joy has brought forth to me. And remember, you can have that too .. remove your day job hat for some time (maybe over a few weekends) and get immersed in the beauty of recursion and theory of computability.

Let us take an example ..

Suppose you want to write a function that computes the square of a number .. here is a Joy version for that ..

dup *


>> (dup)licate the element on top of the stack and apply multiplication operator (*) on the 2 top elements of the stack.

You can have a name for the function if you want to reuse it many times ..

square == dup *


and invoke it as

5 square


or without names

5 dup *


What about cubes ?

dup dup * *


Intuitive huh!

What does the following do ?

[dup dup * *] map


Ok .. possibly I have jumped too far ..

In Joy, programs evolve through 2 operations - quotation and concatenation.

Quotation can be thought of as a passive data structure and is indicated by surrounding the quoted program with square brackets. In the last example, [dup dup * *] is a quoted program. But it is also a list - in Joy lists are as well indicated within square brackets e.g. [1 2 4 6] is a list. So generically speaking lists are quoted programs in Joy. And a list can contain elements that are not literals and can be made to operate on values. And for that we need to activate the passive quotation.

Concatenation of two programs in Joy is effectively the composition of the functions denoted by the programs. Consider the example program ..

2 3 + dup *


which is effectively, the composition, denoted abstractly by *(dup(+(2, 3)))

In the above example that we left off without solving, the quoted program is activated by the combinator that follows it .. map. Combinator is another useful device that causes execution of the quoted program on top of the stack. There are a variety of combinators in Joy, the most trivial one being the i-combinator. i-combinator just dequotes the quoted program, i.e.

[dup dup * *] i


is equivalent to

dup dup * *


What about the map combinator ? Let us try to run the last example where we left off .. with some actual data ..

[4 6 8 9] [dup dup * *] map


Here is what happens ..

• Joy first pushes the list of integers on the stack


• Then the quoted program is pushed .. remember quoted programs are passive - hence nothing gets executed


• The map combinator then removes the list of integers and the quoted program and constructs a new list by applying the program to each element of the list. The usual stuff that map is so well-known to do ..

The result is a list that contains the cubes of the original elements.

I have only scratched the surface in order to tickle you towards a functional language that is not based on lambda calculus. I am sure you will also find Joy equally interesting, and loads of fun learning.

Tailpiece

Did you notice that we can have any element within a list ? Sounds familiar ? Yes, you got it right ! Program as data, as Joy would have it. A quoted program is data unless operated upon by a combinator. And, as this landmark paper suggests ..

"Since programs are data, it is possible to define a Y-combinator for recursion and several variants. It follows that there are self-reproducing and self-describing programs in Joy. Practical programs can be written without recursive definitions by using several general purpose recursion combinators which are more intuitive and more efficient than the classical ones."

Go read this paper .. it is an absolute joy (pun intended) if you want to learn more about recursion, combinators and computability. This paper was my starting inspiration in dabbling with Joy. You can also have it .. enJoy!