2008-07-21

Top Down Operator Precedence - in Haskell

or How to write JavaScript in Haskell

While reading Top Down Operator Precedence by Douglas Crockford I was struck by the notion that here was a chance for me to convert my Haskell knowledge from read-only to something more read-write. The particular point was "... his technique is most effective when used in a dynamic, functional programming language". Well Haskell is certainly functional but what about dynamic? Here was a small working system which I could translate without having to consider design nor correctness issues. Of course for the comparison I'd have to keep the Haskell structure close to the JavaScript, which I think I've achieved in the majority.

I made several abortive attempts at coding the full parser starting with a bottom-up coding style, ie., write base functions first then functions which depend on them so on upwards, then a top-down style, ie., write then main function before functions it is dependant on. In total there were four incomplete versions:

  1. bottom-up and stateful
  2. bottom-up and stateful plus ST references
  3. bottom-up and stateful plus IO references
  4. top-down and purely functional

My final, fully working version was done in a top-down stateful way without references.

The main reason the bottom up versions failed was that testing them with all that state plus references was tricky. On the other hand the top down versions could have simple tests because the top-level interface is simple and I could avoid writing quite a bit of code and still compile by using error and type signatures for dependent functions I hadn't written yet. Any errors raised that way simply indicated the next function to write to get the tests running.

The switch to pure functional was prompted by the ugliness of the stateful code, especially a mix of state and references. The resulting environment passing tangle soon made the pure version less beautiful but it highlighted exactly where I could use state to clean the code and a crucial diversion from the JavaScript design which removed all of the reference-based horror. The last half of the parser coding work because almost mechanical transliteration.

The full side-by-side comparison is available.

My conclusion, having finished the comparison, is that the Simplified JavaScript and Stateful Simplified Haskell versions are very similar in complexity and structure. Because full mutable state is not 'native' to Haskell it's occasionally a little more verbose. On the other hand, pattern matching allows better separation of code in some parts and easy access to the internals of (non-stateful) parameters.

Whether the beauty of the Simplified JavaScript parser in Simplified JavaScript rubs off on the Simplified JavaScript parser in Stateful Simplified Haskell is debatable. Part may be due to keeping to a Simplified JavaScript coding style so that common Haskell idioms, especially the use of higher-order functions over simple recursion, are not used.

This is the 10,000m view!


No comments: