Static Typing and Functional Languages

With a title like that, it’s not really clear where I intend to go with this post, but bear with me for a moment.

A couple of years ago, I got into functional programming, initially with Common Lisp (only a tiny bit), and then Scheme and Scala, a pinch of OCaml, and finally Clojure.  One thing I noticed about all the Lisps was that they weren’t statically typed in the way I was used to in Java.  Then I noticed that all the functional languages that were statically typed (OCaml, Scala) were also more modern than the Lisps.

Anyway, I continued working in functional languages for months, growing more accustomed to the power they offered, and changing how I thought about solving problems as I went.  Design patterns seemed much less useful, and languages that didn’t support higher order functions, TCO, and the basic map, reduce, and lambda functionality started to feel increasingly awkward.

So, as I worked in Java for much of my professional work, I was naturally drawn to investigate Functional Java, a set of libraries that offered at least a partial veneer of functional programming on top of the Java language.  Part of that library was a testing framework inspired by QuickCheck called Reductio Test.  Reductio was cool, and the examples looked simple and powerful.  Then I tried to write my own generator for Reductio.

The code was awful.  It was an explosion of objects attempting to replicate higher order functions, but constrained by Java’s type system.  As such, the types of the higher order functions were generified on types of lower-arity higher order functions, and so on, until finally all the parameters had been consumed.  I thought I must be doing it wrong, so I browsed the Functional Java source tree over on the Google code site where it is hosted.  In Function.java, I saw the same problem emerge:

 /**
   * Curry a function of arity-5.
   *
   * @param f The function to curry.
   * @return A curried form of the given function.
   */
  public static <A, B, C, D, E, F$> F<A, F<B, F<C, F<D, F<E, F$>>>>> curry(final F5<A, B, C, D, E, F$> f) {
    return new F<A, F<B, F<C, F<D, F<E, F$>>>>>() {
      public F<B, F<C, F<D, F<E, F$>>>> f(final A a) {
        return new F<B, F<C, F<D, F<E, F$>>>>() {
          public F<C, F<D, F<E, F$>>> f(final B b) {
            return new F<C, F<D, F<E, F$>>>() {
              public F<D, F<E, F$>> f(final C c) {
                return new F<D, F<E, F$>>() {
                  public F<E, F$> f(final D d) {
                    return new F<E, F$>() {
                      public F$ f(final E e) {
                        return f.f(a, b, c, d, e);
                      }
                    };
                  }
                };
              }
            };
          }
        };
      }
    };
  }

I was stunned.  What had gone wrong?  After a few minutes or hours, I realized the reason Lisp had used dynamic typing: having to explicity specify all the types for each of the higher order functions destroys the readability of the code!  So, languages like Javascript, Lisps, Python and Ruby get too avoid all that.  So how do OCaml and Scala work?

Well, a lot of work had to be done to support static typing with functional programming, and it required the development of a type inferencer to make code readable.  The end result is a sophisticated compiler that has the ability to determine the types in the code without the programmer specifying them exhaustively.  This functionality is advanced, however, and it took a long time to develop.  That is why OCaml and Scala are much newer that Lisp, for example (though it is true that OCaml and Python are about the same age).

So, suddenly it all came together for me.  I finally had a glimpse as to how the type systems interacted with the programming paradigms, and why languages made the decisions they did.  Type inferencers can be tricky to write well, so there is a trade space language designers have to navigate to get the result they’re looking for.  Dynamic typing offers simplicity, but also comes at the cost of rigor and the ability to catch entire classes of bugs at compile time, rather than runtime.  Sometimes that cost is worth it, sometimes not.  That is why, even today, there is room for dynamic languages like Python and Ruby alongside static languages like Scala and OCaml.