Why isn’t Crux a pure functional language?

Nicolas Hery asked on Twitter: “[Why isn’t Crux] pure like Haskell/Elm/etc.?” Good question, and one worth writing about.

First of all, the term “pure functional language” isn’t terribly enlightening. It’s certainly not useful for communication, because everyone has or invents their own definition on the fly.

There are a few independent ideas here: mutable vs. immutable data structures, mutable vs. immutable names/variables, and whether effects are tracked.

Regarding mutable vs. immutable data structures: in reality, mutable data structures are simply unavoidable. At some point you need to update your in-memory representation. There are ways to encode that with immutable data structures, but they get awkward fast. In addition, constantly producing new immutable values places a great deal of pressure on the garbage collector – often it’s fastest just to update your data in-place. Immutable data is a fantastic tool, used appropriately, but it sucks when it’s a straitjacket.

Regarding mutable vs. immutable local variables: imagine you want to sum up the elements in an array. If Crux were pure-functional, that
could be written something like:

fun sum_(list, index) {
  if index >= len(list) {
    0
  } else {
    list[index] + sum_(list, index + 1)
  }
}
fun sum(list) {
  sum_(list, 0)
}

Oh wait, that’s not tail-recursive, so it’ll blow up the stack with a long enough list. Let’s rewrite it:

fun sum_(list, index, total) {
  if index >= len(list) {
    total
  } else {
    sum_(list, index + 1, total + list[index])
  }
}
fun sum(list) {
  sum_(list, 0, 0)
}

OK, now we’re tail recursive. For efficiency, however, the compiler needs to turn that into a tight loop of instructions, storing the accumulators in registers. Wait, so you’re saying the language forced me to translate a simple imperative function (sum the elements in a list) into a tail-recursive loop, which the compiler then has to convert back into imperative code for efficiency? Why can’t the compiler just turn my natural imperative loop into a tail-recursive implementation, if that’s what it really wants? (It definitely could.) And it gets even worse the larger your functions become, especially if they have early exits and multiple “mutable variables”. In short, tail calls are great, when appropriate, but always programming with tail recursion is like someone rejecting all your commits with “Nope, you must contort your code for my pleasure.” And I shudder to think of what a tail-recursive implementation of a huge interpreter loop with lots of mutable variables would look like.

Tail calls are great, but being forced to write tail-recursive loops is dumb and one of my biggest annoyances with Haskell. Instead, why not just write:

fun sum(list) {
  let mutable total = 0
  for i in list {
      total += i
  }
  return total
}

Crux makes that natural.

However! Everything I said above is independent of what the defaults are. Crux variables and values are immutable by default, since that’s the common case. Sum types are always immutable. The only things that can be mutable are record fields and locals, but, again, you must opt into that functionality. It’s not annoying in practice; since everything’s an expression in Crux, there’s less need to mutate locals.

Okay, so instead let’s presume that most people consider pure functional to mean “has restricted side effects”, like Haskell.

Personally, I’m a huge fan of monads in Haskell, and the amazing
things they enable.

However, they come at a large cost: since nearly everything is a Monad, the error messages get really complicated, especially when the compiler thinks you meant the Maybe monad or a function monad. (Isn’t it crazy how, in Haskell, Integers aren’t a Monoid by default, but all functions are Monads?)

Eventually I’d love Crux to have an effect tracking system. Different syntax between pure code and effectful code is unacceptable, so the Haskell approach is a no-go. I am excited, however, about row-typed effect systems like Koka. (Notably, it should be okay for pure functions to use mutable locals, like the sum function above.) Future work!

To summarize, I think we can achieve most of the benefits of “pure functional programming” while retaining accessible syntax and allowing mutability as desired and convenient.

1 thought on “Why isn’t Crux a pure functional language?”

  1. There are some more effective methods for encoding mutability in a functionally pure way.

    In Mercury for example, which is statically moded, you can use uniqueness and treat variables as state representation to do it. For instance:

    :- pred increment(int::di, int::uo) is det.
    incremenet(A, A + 1).

    Now, you can use `increment(!Iterator)`, and the compiler is smart enough to recognize this an in-place modification, even though the function is functionally pure, all data is immutably represented, and there are no side effects.

Leave a Reply

Your email address will not be published. Required fields are marked *