Next Language?

Recently I’ve been thinking, “I’ve done the Lisp thing. Also, SML and OCaml. What’s the next language I could learn that will change the way I think about programming?”

Erlang seems pretty cool. Really inexpensive parallelism and built-in capability for distributed process on a bunch of machines. Pattern matching. Built-in tuples. All good things… but it’s dynamically typed. The benefit of strong typing (every expression has a type, inferred or declared, at compile-time; and types are checked) is well known. I have taken this to heart, and programmer friends of mine know I get very testy when someone threatens my Hindley and Milner.

Haskell, on the other hand, has a magnificently expressive type system. It has dependent types, generalised algebraic data types, and type classes, all which make for a fruitful compilation step and contribute to code confidence. Type classes in particular provide operator overloading⁰ in a type-safe way. But if languages are schoolteachers, Haskell is a pushover: it has non-strict semantics. This property is less-accurately¹, but more commonly known as laziness.

I don’t like this aspect of Haskell. It seems to make it hard to reason about the complexity of an algorithm. “Am I accumulating stack?” While it might be quick to code something correctly, coding correctly and efficiently is a less obvious process for me.

Ignoring these options, however: who’s to say I’ve really understood Lisp, SML, or OCaml? Some would have it that it takes longer than a few years to really become an expert in any reasonably general-purpose language. I like this, and so my current plan is to stick it out for a while with OCaml (education permitting).

Currently I’m exercising my OCaml-fu by implementing a parallel Sudoku solver in Jocaml. Jocaml is an extension of OCaml that implements the join calculus, a formal language for asynchronous communicating processes. Basically, instead of just wrapping some system threads library, Jocaml provides orthogonal primitives to describe fundamental building-blocks of processes and how they communicate. As a bonus, the whole thing is formal, so you could conceivably prove theorems about a program written in Jocaml, because there is a mathematical theory underlying all the asynchronous bits.

^[0]Also called ad-hoc polymorphism, though I’ve yet to discover why.

^[1]In my vocabulary, strict semantics is a language property meaning that evaluating an expression involves first completely evaluating its subexpressions. It follows, then, that a language has non-strict semantics when it does not have strict semantics.

One consequence of non-strict semantics is the possibility of embedding non-terminating expressions in a terminating program. For example, suppose use-first-argument is a binary function that does exactly what it says, namely does something with its first argument only, ignoring its second. In a strict language (e.g. everything, mostly), where stands for an expression whose evaluation never terminates, the function call use-first-argument (X, ) will never terminate. In a non-strict language (Haskell), that code fragment will return whatever use-first-argument returns. If the expression’s value is never needed, it is never computed, and hence the infinite recursion is never triggered.

To return to the point, laziness is the property of a program or data structure — a value can be lazily computed by saving intermediate results until the final result is manually requested, at which point evaluation occurs. Laziness can be written into Java, or OCaml, or any language. One example is a common pattern in OO system implementation: set the values of member variables the first time they are accessed, rather than upon initialisation of the class.

Lexing & Parsing (With Makefile) in Objective Caml

I’m learning Objective Caml in order to write a compiler. I’ve written one compiler before, and that in SML/NJ. I must say: the ML family of languages is really nice for writing data-structure intensive code. The strong typing can save you significant amounts of time and hair.

Anyway, the following is a hacker’s experience getting lexing & parsing to work using ocamllex and ocamlyacc. I hope this proves useful for someone. It would have been useful for me.

1. Go to the the documentation & copy the calculator example into appropriate files.
2. Scoff at the advice:

   To compile everything, execute:
           camllex lexer.mll       # generates lexer.ml
           ocamlyacc parser.mly     # generates parser.ml & parser.mli
           ocamlc -c parser.mli
           ocamlc -c lexer.ml
           ocamlc -c parser.ml
           ocamlc -c calc.ml
           ocamlc -o calc lexer.cmo parser.cmo calc.cmo"

   Think: “Surely there’s a compilation manager. Makefiles are so nearly-thirty-years-ago.

   “A compilation manager would run from within the OCaml environment. A compilation manager would keep track of source code changes & recompile only what’s needed. I should just be able to list the OCaml code I write, & it should take care of the rest.”

3. Search for an OCaml compilation manager.
4. Find something similar, but which is really just a front-end for generating a configure script and Makefile. Figure it out later.
5. Create Makefile:

   ########## Makefile for OCaml Calculator Example
   ########## http://caml.inria.fr/pub/docs/manual-ocaml/manual026.html
   ########## Created by Denis Bueno
   
   all: calc
   
   # main program executable
   calc: calc.cmo
   	ocamlc -o calc lexer.cmo parser.cmo calc.cmo
   
   calc.cmo: lexer.cmo parser.cmo calc.ml
   	ocamlc -c calc.ml
   
   ##### Compile the lexer & parser sources
   parser.cmo: parser.ml parser.cmi
   	ocamlc -c parser.ml
   lexer.cmo: lexer.ml parser.cmi parser.ml
   	ocamlc -c lexer.ml
   parser.cmi: parser.mli
   	ocamlc -c parser.mli
   
   ##### Make the lexer & parser sources
   lexer.ml: lexer.mll
   	ocamllex lexer.mll
   parser.ml parser.mli: parser.mly
   	ocamlyacc parser.mly
   
   clean:	rm -f lexer.ml parser.mli parser.ml *.cmo *.cmi calc

6. Grumble indecorously because you’re so used to CM.
7. make

   ocamllex lexer.mll
   11 states, 267 transitions, table size 1134 bytes
   ocamlyacc parser.mly
   ocamlc -c parser.mli
   ocamlyacc parser.mly
   ocamlc -c lexer.ml
   ocamlc -c parser.ml
   ocamlc -c calc.ml
   ocamlc -o calc lexer.cmo parser.cmo calc.cmo

8. ./calc Now do some arthmetic.

this site brought to you by the letter p and the number e.