Dynamic Languages are Static August 20, 2014 | 04:06 pm

This article is a response to this blog post. The problem with this post is that it makes several mistakes around the behavior of sum types, which undrcut the argument the post is making. I want to explain why Bob Harper’s original (and admittedly some-what flaime-baity) post is correct.

But first, I need to actually state the argument Bob Harper was making. He was said that every dynamic language could be incoded as a sum type in a static language. As example of this, let me demonstrate exactly how to do this, by encoding lisp into a sum type in haskell:

    data Lisp =
        LInt Int
        | LString String
        | LSymbol String
        | LList [ Lisp ]

This says a Lisp value is either an Int (labelled with the tag LInt), a String (LString), a Symbol (LSymbol), or a list of Lisp values. You can, if you feel like, extend this with more data types- add floats, and doubles, and chars, and vectors, and maps, and sets, etc. I can then happily write functions that take and return my Lisp values.

At this point, the OP makes a critical error right about here- she assumes that the values 3 and LInt 3 are the same. They aren’t. No, you can’t add an integer and a string in Haskell- but you can write an add function (of type Lisp -> Lisp -> Lisp) which can add an LInt 3 to an LString "foo".

This is interesting because it demonstrates another point the OP missed. So let’s consider the add function, to add two lisp function together. As there are two arguments, and each argument can be one of four different types (variants), you might think I need to write 16 different case statements down. You’d be wrong. The code looks like:

    add :: Lisp -> Lisp -> Lisp
    add (LInt x) (LInt y) = Lint (x + y)
    add _ _ = error "add called with a non-integer argument"

The _ is a discard matcher- it matches anything. And since matching precedes in order, and the first pattern to fit is the one that is evaluated, if both arguments are ints, the first expression is evaluated, and we get an int. If any of the other 15 different situations occurs, then the second expression is evaluate, and we throw an error at run time. Just like Lisp. In this way, the _ acts as a sort of escape hatch from having to deal with all the different cases, which all get handled the same way anyways. Indeed, the whole Lisp type itself acts as a sort of escape hatch.

From one angle, all Bob Harper has done here is restate Greenspun’s tenth law. But here’s the difference, and the point Harper was making: we can choose not to use the Lisp type. By taking a value of type Lisp, we are expressly stating that this function takes any value that can be encoded as an s-expression. If that’s what we mean, all right. But we have the choice of using a more restrictive type, we express something of the assumptions the function is making.

This is what Bob Harper meant by more expressive. Everything we can express in language X was can also expression in language Y- but there are things we can express in language Y that we can not in language X. For example, that a given function doesn’t handle every possible case.