I've created several functional programming utility libraries in the past for JavaScript and CoffeeScript. Today they have become obsolete with the release of Mori. Mori is a simple bridge from vanilla JavaScript to ClojureScript's persistent data structures and the supporting API. Mori even includes Rich Hickey's new reducer work for allocation free operations on collections.

So maybe your boss won't let you use Lisp - well use Mori - it's just ~20k of gzipped JavaScript.

This benchmark is interesting. It shows that if your compile-to-JavaScript language needs to support some notion of interfaces (or protocols in the case of ClojureScript) there is nothing faster than a property lookup and a bitwise and operation to test membership. This is the approach that the ClojureScript compiler now takes.

Donald Knuth cleverly imprisoned the phrase "Literate Programming" - if you're not documenting your source with his particular methodology then you must be a proponent of "Illiterate Programming," which sounds truly awful.

I very much believe in documented code but I think no amount of pontification in English will ever make a piece of code clearer than the code itself (I'm not talking about project or API documentation). I'm also not talking about the superficial notions / arguments of "readability" that are bandied about these days (Python, CoffeeScript, etc).

Most languages have no deep notion of readability in their core. 

Take a look at this page of Smalltalk:

One of the most lovely ideas in Smalltalk was the ad-hoc categorization, "protocols" - here you see initialization, accessing, private. These were not reified in the language but instead were a level of documentation baked right into the software writing experience.

In a similar vein, one of my favorite features of Clojure and ClojureScript is protocols. Their least celebrated benefit is readability - here's how JavaScript primitive arrays are extended to participate in some core language concepts:

Smalltalk has so very few concepts - it's truly stunning. There's nothing more powerful in aiding readability than a small core set of concepts. In this sense I think Smalltalk continues to be one of the few languages to get anywhere near LISP. Most languages these days are just an abomination of features trapped inside of a compiler.

Yet I think Smalltalk still fundamentally failed (remember this is a programming language originally designed to scale from children to adults) because Objects are really hard and no-one really understands to this day how to do them right. This isn't to say they aren't incredibly useful but I think we've truly gone down the wrong path by putting then onstage. They should be backstage patiently waiting for those folks when they're ready to see how the pudding is made (Art of the MetaObject Protocol).

So I suggest repurposing "Illiterate Programming" to mean something very different. Programs, programming languages, and programming paradigms which strive for readability at a deeper level - the elegant self-evident architecture of very simple concepts. "Literate Programming" is admission of defeat.

I've started porting core.logic to ClojureScript. So far it feels good to rip out all of the JVM-centric optimization bits. However, I'd like core.logic to run at a decent clip in JavaScript - this means a different approach to optimization as well as staying truer to the Scheme miniKanren implementation (such as using lists for the substitution map). I think by the end I'll have amassed some interesting notes on how to write ClojureScript code that performs quite well in comparison to hand-written JavaScript.

I stumbled across this amazing blog series which is tackling computational linguistics by porting Prolog to core.logic. It reminds me a bit of my earlier attempt to implement Definite Clause Grammars. I got something experimental working but in order for core.logic to really scale for large parsing tasks we'll probably need to rethink how core.logic handles substitutions. That said, core.logic does have tabling so building packrat parsers shouldn't be too difficult.

All this brings me to the incredibly succinct program in Appendix II of the VPRI 2011 Report (Alan Kay et al). They start with a machine oriented lisp, define a grammar, implement Smalltalk, and finish with a non-trivial program.

Could we take similar approaches when writing software with Clojure?

UPDATE: Jeremy Ashkenas (CoffeeScript creator) has pointed out on HN a somewhat intentional flaw in the final gist. Hopefully you can spot it and see that this post is about solving that very problem. I'm being a bit old school here - I don't like to give everything away :)

I’ve been spending a lot of time recently hacking on the ClojureScript language. I can say without qualification that I haven’t had this much fun programming since I first taught myself JavaScript nearly seven years ago. So let’s put aside logic programming for a moment and let’s talk about code complexity and code expressivity.

Recently on StackOverflow someone asked how to idiomatically construct a type in ClojureScript. Before we get into that let’s consider how this is done in JavaScript:

CoffeeScript gets a lot of deserved attention for its brevity for common tasks. For example the same thing in CoffeeScript:

That requires nearly half the amount of characters. Of course on real code the code compression isn't nearly that great - perhaps 10-20% in my experience. Still I find that CoffeeScript tends to give the feeling of compression for many common tasks and how a language feels day in and day out is important for programmer happiness.

Let's take a look at the same thing in ClojureScript:

The ClojureScript without the strange protocol form would give even better compression than CoffeeScript! So what does this protocol form do and why do we need that cluttering up our type definition?

ClojureScript, unlike JavaScript or CoffeeScript, promotes defining reusable abstractions. Imagine if all the types in your favorite library were swappable with your own implementations? Hmm ... perhaps that's an abstraction too far for many users of JavaScript or CoffeeScript.

Well here's a use case I think more people will get - neither JavaScript nor CoffeeScript provide any kind of doesNotUnderstand: hook that is fantastic for providing default implementations.

We've extended all objects including numbers to respond to the bar function. We can provide more specific implementations at anytime, i.e. by using extend-type on string, array, Vector, even your custom types instead of default. It's important to note that this extension is safe and local to whatever namespace you defined your protocol.

Still not convinced? Let's demonstrate a very powerful form of extension that even Dart is getting behind.

In ClojureScript it's simple to construct types which act like functions. While this might sound esoteric consider very succinct operations like the following:

Wow. HashMaps in ClojureScript are functions! Now this may look like some special case provided by the language but that's not true. ClojureScript eats its own dog food - the language is defined on top of reusable abstractions.

How can we leverage this? An example - JavaScript and CoffeeScript both let you extract a range from strings and arrays. In JavaScript you have slice and CoffeeScript provides sugar via the [i..j] syntax. Neither provide you with a way to succinctly construct and manipulate the idea of a slice. For example:

IFn is one of the many reusable abstractions that ships with language. We define ISlice to illustrate that our type has dual functionality - as an object with fields that can be manipulated and as a function which can be applied to data!

Many people have the misconceived notion that Clojure/Script is only about functional programming - on the contrary Clojure/Script is very much "Object Oriented Programming: The Good Parts".

Yesterday I posted an incorrect solution to this puzzle because I did not read the problem description correctly. At first it seemed like the problem did not lend itself at all to constraint logic programming. After a whole day of pondering it- I'm no longer sure that's true.

To be clear I don't think I would have arrived at the following code had I not seen the answer - 1, 3, 9, 27. Before we dive into what is curious about these values lets first see that I retained my original inspiration:

We still want all the stone values to be all different - there's no benefit to representing zero on the scale with stones themselves. We also still want the first stone to weigh one pound. To limit the search space we still want to ensure the stones weights are in increasing order and they still have to add up n, which in this case is 40.

These constraints decrease the search space very quickly. We then pass whatever weight sets are left to checko:

checko is a recursive goal. It takes 4 important parameters - ws a list of weights in ascending order, sl a list of weights from ws that we've already considered in reverse order, r an accumulation list of weights we know we can represent in reverse sequential order, and finally n the maximum weight.

The base case is simple, we have no more weights to consider. If the head of the accumulation list is equal to 40 we are done - if not we failed.

If we have more weights to consider we pull apart the weight list ws into w and wr. We then call subchecko with the weight w, sl, the accumulation list of weights r, and a unbound logic variable nr to hold subchecko's result. If subchecko succeeds, we move w into sl and we recur with wr one element shorter, sl one element longer, nr with all the weights we can now represent and n.

subchecko does quite a bit of work. First let us consider the base case - sl is empty. If so we have no values with which we can modify w and get other representable weights. If the accumuluation list r has any weights in it we check that w is exactly one greater than the first element of r. If so we unify an extended r to o. If r is empty (as it might be on the first call) we just add the weight straightaway.

So much for the base case. Now let's consider if sl is not empty. This means we have some math we can do. sl holds previously examined stones in reverse order. We can pull these out and add and subtract to determine other weights we can represent. Note this is very tree like! First we consider w-a, then we consider w itself, then we consider w+a. Because we keep track of the previously considered stones from ws in sl, we can at each considered weight use the sl to compute further weights in a tree like fashion. It's a bit like an in order tree traversal - only 1, 3, 9, 27 can satisfy this behavior.

Again this code shows an understanding of the solution - but I hope it reveals how fascinating logic programming can be! We're combining search and global constraints to produce the answer very quickly - ~12ms on my machine under Racket.

UPDATE: This doesn't actually solve the puzzle! I wasn't considering putting stones on either side of a physical scale. I'm leaving the post as is since it does highlight the powerful declarative aspect of cKanren w/o sacrificing efficiency.

Cédric Beust wrote up a fairly interesting challenge. Petit Laurent notified me about it on Twitter saying that core.logic might be a good fit for the problem. As it turns out core.logic in its current form is not ideal, however I'm planning on integrating cKanren functionality to core.logic which would extend core.logic to Constraint Logic Programming.

For fun I spent a little bit of time coding up a solution in cKanren with Racket. Read the problem description before proceeding.

Take a look at the following bit of code:

This is constraint logic programming. I declare 4 logic variables a, b, c, d to hold the weights of the stones and two to hold intermediate sums s1, s2. I specify that these variables are allowed to range from 1 to 40. I constrain them to be all different.

We know that at least one stone must weigh 1 pound, so we go ahead and unify the first stone with 1. To limit the search space we also declare that the stones increase in weight. This means that the set of stones with the smallest weights that would add up to 40 would be 1, 2, 3, 34. Again to decrease the search space we say that stones a, b, c must be less than or equal to 34 pounds. We then sum the four stones together and declare that they must add up to 40.

This simple declarative function will generate the stone weights that satifisfy all the constraints. This is not brute force search - we arrive at the solution in ~85ms on my machine.

The entire solution and output:

I'm looking forward to adding this functionality to core.logic. I'm excited to hear William Byrd and Daniel Friedman describe the ideas behind cKanren at the Clojure/conj.

The ClojureScript compiler will need to communicate that we're looking at ClojureScript code to the match macro, but I got this working easily after a little fiddling. This is pretty amazing. JS.Next indeed.

Anyone that thinks that Google Closure was a bad idea should look at how concise the final output is:

Of course the above pattern is hardly interesting - consider checking red-black tree balance:

It's beautiful thing to be able to integrate object oriented principles with macros. In order to avoid overhead (no wrapper types) when pattern matching primitives you can derive the compilation mechanism and specify what type of code you want to generate. This means you're able to write beautiful patterns that have brutally fast performance.

As mentioned before this is all that it takes to make it work on bits:

Every other pattern matching implementation, read and weep :)

In case you're not familiar this is edge work happening on match. This library already supports map patterns, seq patterns, guards, or patterns, matching locals, and provides an interface so that you can pattern match Java objects.