Advanced programming languages

As a researcher in programming languages, students frequently ask me what language they should learn next. If you're looking for a job in industry, learn whatever is hot right now: C++, Java, and C# and probably Python, Ruby and Perl too.

If, on the other hand, you're interested in enjoying personal enlightenment, doing academic research or in starting your own software company, the criterion by which you should choose your next language is not employability, but expressiveness. In academic research and in entrepreneurship, you need multiply your effectiveness as a programmer, and since you probably won't be working with an entrenched code base, you are free to use whatever language best suits the task at hand.

I'm slowly compiling descriptions of good, non-mainstream languages to learn here, with a list of favorite features for each, and pointers on where to learn more.

Jump to:

Haskell

Haskell excels as a language for writing a compiler, an interpreter or a static analyzer. I don't do a lot of artificial intelligence, natural-language processing or machine-learning work, but if I did, Haskell would be my first pick there too. (Scheme would be a strong second.) Haskell is the only widely deployed and used pure (or lazy) functional programming language.

Like Standard ML and OCaml, Haskell utilizes Hindley-Milner-style type inference, which means that the programmer doesn't have to write down (most) types, because the compiler can infer them. It has been my experience that it is difficult to get a bug passed the Hindley-Milner type system. In fact, experienced functional programmers become adept at encoding correctness constraints directly into the Haskell type system. A common remark after programming in Haskell (or ML) for the first time is that once the program compiles, it's almost certainly correct.

As a pure language, side effects (mutations of variables or data structures and I/O) are prohibited in the language proper. This has forced the language's designers to think seriously about how to provide such functionality through alternative means. Their answer, monads, enables one to perform side effects and I/O inside a safely constrained framework. Naturally, Haskell lets users define their own monads, and now the programmer has access to monads for continuations, transducers, exceptions, logic programming and more.

Being pure, Haskell could also be made lazy, and so it was. In other words, an expression in Haskell is not evaluated until (and unless) its result is required to make forward computational progress. Some have argued that the promised efficiency gains from laziness haven't materialized, but that's not of concern for me. I still appreciate laziness for the increase in expressiveness. In Haskell, it is trivial to describe data structures of infinite extent. Where other languages permit mutually recursive functions, Haskell permits mutually recursive values. I have also found laziness useful in cleanly encoding option types where utilizing the empty case should nuke the program. In Haskell, you can avoid creating an option type and instead use error to produce the empty value. Because of laziness, each type in Haskell has two additional elements: non-termination and error. This eliminates a surprising amount of tedious pattern matching from functional programming.

My favorite feature of Haskell is type classing. Haskell's type system literally allows the compiler to infer the correct code to run based on its type context. The example of type classes that really caught me by surprise was bounded lattices. A bounded lattice is a mathematical structure that has a least element (bot), a greatest element (top), a partially ordered less than relation (<:), a join operation (join) and a meet operation (meet).

In Haskell, one can define a bounded lattice as a type class: 

  class Lattice a where
   top  :: a
   bot  :: a
   (<:) :: a -> a -> Bool
   join :: a -> a -> a
   meet :: a -> a -> a
This says that if type a is a Lattice, then a supports the expected operations.

What I really love about Haskell is that it lets the programmer define conditional instances of a class; for example: 

  instance (Ord k, Lattice a) => Lattice (Map k a) where
   bot = Map.empty
   top = error $ "Cannot be represented."
   f <: g = Map.isSubmapOfBy (<:) f g
   f `join` g = Map.unionWith join f g
   f `meet` g = Map.intersectionWith meet f g
This rule says that if the kind/type k is an instance of an order (class Ord) and the kind/type a is an instance of a lattice, then a map from k to a is also an instance of a lattice.

As another example, you can easily turn the Cartesian product of two lattices into a lattice: 

  instance (Lattice a, Lattice b) => Lattice (a,b) where
   bot = (bot,bot)
   top = (top,top)
   (a1,b1) <: (a2,b2) = (a1 <: a2) ||
                      (a1 == a2 && b1 <: b2) 
   (a1,b1) `join` (a2,b2) = (a1 `join` a2, b1 `join` b2)
   (a1,b1) `meet` (a2,b2) = (a1 `meet` a2, b1 `meet` b2)

It's easy to make the "natural" lifting of the lattice operations, relations and elements to almost any data structure. The end result is that if you use the expression bot or the relation <: anywhere in your code, Haskell can infer their "appropriate" meaning based on the type of the expression (which it can also infer).

The ML languages have functors to play the role of type classes, but they lack the ad hoc polymorphism support of Haskell's type classes. Having spent a considerable amount of time programming in the MLs and in Haskell, the practical ramifications of inference on expressiveness cannot be understated.

Favorite features

Resources

Scala

Scala is a rugged, expressive, strictly superior replacement for Java. Scala is the programming language I would use for a task like writing a web server or an IRC client. In contrast to OCaml, which was a functional language with an object-oriented system grafted to it, Scala feels more like an true hybrid of object-oriented and functional programming. (That is, object-oriented programmers should be able to start using Scala immediately, picking up the functional parts only as they choose to.)

I'd learned about Scala at POPL 2006 when Martin Odersky gave an invited talk on it. I think that at the time I saw functional programming as strictly superior to object-oriented programming, so I didn't see a need for a language that fused functional and object-oriented programming. (That was probably because all I wrote back then were compilers, interpreters and static analyzers.)

The need for Scala didn't become apparent to me until I wrote a concurrent HTTPD from scratch to support long-polled AJAX for yaplet. In order to get good multicore support, I wrote the first version in Java. As a language, I don't think Java is all that bad, and I enjoy object-oriented programming. As a functional programmer, however, the lack of (or needlessly verbose) support of functional programming features (like higher-order functions) began restricting me. So, I gave Scala a chance.

Scala runs on the JVM, so I could gradually port my existing project into Scala. It also means that Scala, in addition to its own rather large library, has access to the entire Java library as well.

As I started using Scala, I became impressed by how cleverly the functional and object-oriented worlds blended together. In particular, Scala has a powerful case class/pattern-matching system that addressed pet peeves lingering from my experiences with Standard ML, OCaml and Haskell: the programmer can decide which fields of an object should be matchable (as opposed to being forced to match on all of them), and variable-arity arguments are permitted. I write a lot of functions that operate on abstract syntax nodes, and it's nice to be able to match on only the syntactic children, but still have fields for things such as annotations or lines in the original program. The case class system lets one split the definition of a sum type across multiple files or across multiple parts of the same file.

Scala also supports true multiple inheritance through class-like objects called traits. It cleanly circumvents Java's dogmatic ban on multiple inheritance.

Scala also allows a considerable degree of overloading; even function application and array update can be overloaded. This tends to make my Scala programs more intuitive and concise.

Favorite features

  • JVM support.
  • Intelligent operator overloading.
  • Extensive library.
  • Case classes/pattern matching.
  • Powerful multiple inheritance via traits.
  • Rich, flexible constructors.
  • Optionally lazy arguments.

Resources

Standard ML and OCaml

The ML family of languages represent a sweet spot in the design space: strict, side-effectable and Hindley-Milner type-inferred. This makes them practical and adaptable languages for real-world projects that need high performance and stronger guarantees on correctness. The ML family has gained traction with aerospace engineers (for its support of bug-free code) and with programmers in the finance and investment industry (for the same reason).

Standard ML was the first functional language I learned, so I still remember being shocked at how powerful it was. Today, OCaml seems to be the popular ML to learn, but there is at least one convincing argument in SML's favor: MLton. MLton really delivers on the thesis that functional languages offer the best opportunities at optimization. As a whole-program optimizing compiler, I've yet to see another compiler match its performance. I once created OpenGL bindings for MLton to toy around with 3D graphics, and the resulting program ran faster that the C++-based model I had used as a reference.

The functor system in SML, while more verbose than Haskell's type class system, is ultimately more flexible. Once you instantiate a type class T for a kind/type k in Haskell, you can't instantiate that type class again for that kind/type. With functors, each instance gets its own name, so you can have multiple instances of a given functor for the same type. It's rarely been the case that I needed such expressiveness, but it's nice to know it's there.

The other modern branch on the ML family tree, OCaml, is good to know because there is a large community invested in it, which means that there are a lot of existing libraries now. The OCaml tool-chain is also rich, with interpreters, optimizing compilers, byte-code compilers and more available to the developer.

Because the ML languages are more expressive than all the mainstream languages, but they still permit side effects, they make a nice stop on the way to learning Haskell. In Haskell, programmers not yet well versed in functional program design may find they repeatedly code themselves into a corner, where they don't have access to the monad that they need. The MLs keep the side effects escape hatch open to patch over incomplete design, which prevents projects from coming to a sudden, unexpected "refactor-or-abort" decision point. One useful measure of a language is how well it tolerates a bad or incomplete design for the software system, since design is something that almost inevitable changes as a program evolves. In this regard, the MLs still have the upper hand.

Favorite features

Resources

  • smlnj.org and mlton.org. Downloads, documentation, tutorials and more for SML.
  • caml.inria.fr. Downloads, documentation, tutorials and more for OCaml.
  • SML v. OCaml tabular comparison.
  • ML for the Working Programmer serves as both a good introductory and reference text for SML.
    It's the book I learned from, and it's a good introduction to the thought process of programming in the ML family of languages (including Haskell). It also covers how to implement the important functional data structures (trees and maps) not provided by the SML library.

Scheme

Scheme is a language with a pure theoretical core (λ-calculus and the theory of lists) and a design mandate to maximize freedom of expression. It's untyped, which makes it ideal for web-based programming and rapid prototyping. Scheme is also a great language for work in artificial intelligence.

Given its support for arbitrary-precision numerics, Scheme is also my first choice of programming language for implementing cryptographic algorithms. [See my short implementations of RSA and the Fermat and Solovay-Strassen primality tests in Scheme.]

The Turing-equivalent macro system in Scheme means that the language can be reconfigured to the programmer's desire. Combined with support for continuations, it is possible to embed alternate programming paradigms (like logic programming) inside Scheme with minimal effort.

For example, in the code: 

  (let ((x (amb 3 4 5))
        (y (amb 6 7 8 )))
    (assert (= (+ x y) 12))
    (display x)
    (display y))
it is possible to write an amb macro that "chooses" the right argument to make a subsequent assert statement be true, so that the program prints 4 and then 8.

A continuation represents the "rest" of the computation, and in Scheme, this is capturable first-class value. Programming with continuations feels like traveling back and forth in time and shifting between parallel universes.

Scheme is so minimal and extensible that there's not a whole lot to say about it, except that Scheme allows the programmer to extract from the language whatever the programmer is willing to put into it.

Favorite features

Resources

  • PLT Scheme is a complete scheme system, including a rich IDE, command-line based compilers and interpreters and a large library.
  • Chicken scheme is a pragmatic, hacker-friendly implementation of Scheme.
  • schemers.org. A community site for Scheme.
  • R6RS. The Scheme standard.
  • I recommend all Scheme programmers keep a copy of Guy Steele's Common LISP: The Language around. After Guy Steele invented Scheme, which is meant to be a pure, minimalist expression of the λ-calculus as a programming language, he designed Common Lisp, which is meant to be a maximalist expression of the λ-calculus as a programming language.
    Over the years, many of Common Lisp's features have been implemented as macros and libraries for Scheme. Whenever I find Scheme lacking, I look to see how Common Lisp did it, and then I roll a quick version of that for Scheme. Many still consider the powerful Common Lisp Object System to be the pinnacle of object-oriented programming language design as well.
  • Abelson and Sussman's Structure and Interpretation of Computer Programs is a classic. Until recently, when they decided Scheme was too advanced to use an introductory language, this was the textbook used for freshman computer science at MIT.