As some of you may know, I’m working on a compiler infrastructure written in D. While the framework itself is rather high-level (it’s very close to actually being half of a compiler front end), an actual compiler implementation is needed to see if the whole thing will work out as well as I hope.
Thus, Tony and I set out to design a simplistic functional programming language. It is heavily inspired by Haskell and OCaml, and has many similarities, though it does not have much in the way of OOP. In short, it’s a language with first-class functions, generics, records/discriminated unions, and finally, treats everything as a value (much like most FP languages). We call it Cesura.
So far, nothing of what I’ve mentioned is particularly new or innovative. In fact, very few FP languages don’t have the features I mentioned. However, one interesting feature that we thought up (and which, to our knowledge, hasn’t been used in any other language) is what we call overloaded functional types. I’ll spare you from any category theory and jump straight to the problem.
You’re given this code:
sqr x : Int -> Int = x * x sqr x : Float -> Float = x * x f = sqr
The problem is immediately obvious: Which of the two functions does f refer to?
You could perhaps solve the problem by doing:
f : Float -> Float = sqr
This, however, completely defeats type inference and has lots of corner cases. If you passed sqr directly to a function, what would you do then?
We came to the conclusion that in order to maintain type inference and still have overloaded functions, we’d need to carry the overloads directly in the type system. This means:
f = sqr // The type of f is now: Int -> Int | Float -> Float
Here, we introduce the concept of an overload set. The type of f is a function that has an overload set consisting of Int -> Int and Float -> Float.
There are several advantages in this sort of type system. One of them is the fact that any function value is implicitly convertible to any function type whose overload set is a subset of the overload set of the function value’s function type.
But that’s not all. You might ask: What happens if I try to call f (from above)? How will the compiler know which function in the overload set I intend to call? The answer to this question is actually very simple:
x = f 2 y = f 4.0
Given this code, look at what’s passed to f in the first call. Clearly, it’s an integer. Thus, we know that a call to the Int -> Int overload was intended. In the second call, we’re passing a floating-point value, and therefore we’re calling the Float -> Float overload. So, x is of type Int and y is of type Float.
You might ask why we didn’t just choose to incorporate type classes, considering I claim that we’re heavily inspired by Haskell. The answer to this boils down to simplicity: Cesura needs to be a simple language utilizing as many features of the MCI framework as possible. We’re creating a simple, practical language, not a language utilizing extremely complex (but certainly beautiful) type system techniques.
Lastly, we’d really like some input on this approach. We’re still not entirely sure that it is the right way to go about this, though it does seem to be the most promising solution that isn’t overly complicated to implement. Also, if you know of some other language that uses this technique, please let us know!
