Rediscovering Standard ML
Thursday, April 24, 2008 at 6:10PM Back when I was studying computer science in Edinburgh (1995-99), we all learned the ML programming language, specifically Standard ML, which was developed in my CS department in the 70s. Even though I think most people on my course quickly decided they didn't like it, it grew on me as I became more familiar with it (and it seemed pretty simple relative to Prolog, which we had to learn in our AI courses).
I hadn't used it since I left university, but given the recent resurgence of interest in higher-level programming languages, with features like type inference, such as with Scala and F#, I decided it was time to indulge in a bit of nostalgia, and refresh my memory.
At university we had a book called ML for the Working Programmer
I then downloaded Standard ML of New Jersey, a popular and powerful SML compiler/interpreter. I had previously considered Caml, an alternate dialect of ML to Standard ML, but I couldn't really get used to it, and I liked the fact that SML supports continuations, a feature useful for building highly concurrent applications. Furthermore, there is MLTon is an extremely powerful "whole-program" SML compiler that reputedly produces extremely efficient code.
So what does SML look like? Here is a simple recursive function to count the elements in a list:
fun count([]) = 0
| count(h::t) = 1 + count(t);
SML relies on pattern matching. The first line tells SML to return 0 for an empty list. The second line will only be reached if the first line doesn't match, and will only match if the list has at least one element. It splits the list into its first element, called 'h', and the remaining elements, called 't' using the '::' operator. It then returns 1 plus the number of elements in the tail.
After typing this into SML's interpreter, SML produces this:
val count = fn : 'a list -> int
This is the type inference at work. Without specifying a single type, SML has inferred that the function count takes a list of type 'a (pronounced "alpha") which can represent any type, and returns an integer. Note that SML has correctly inferred that the type of the elements in the list passed to count is irrelevant for the purpose of counting them.
Lets try something else, a sum function to add up the elements in a list:
fun sum([]) = 0
| sum(h::t) = h + sum(t);
The general structure is similar to count, but this time SML infers different types:
val sum = fn : int list -> int
As expected, it has inferred that the list must be a list of integers.
SML is a powerful language, and I'd recommend it for anyone keen to broaden their knowledge of programming languages.
Unlike Haskell it is "impure", meaning that functions can have side-effects. Some people seem really hung-up on this idea of purity, but so far as I can tell it is more of a fetish which makes life more complicated, and with few practical benefits (whenever I ask people to explain what is so desirable about purity, the response is generally rather theoretical or hand-wavy).
I also think its nicer than Scala in some ways, for example in ML you can do pattern matching on function definitions, rather than having to use match. And of course, its way more mature than Scala.
If you are going to try it, I suggest using Emacs together with sml-mode.
Reader Comments (11)
It's unfortunate that it infers the second example to int list -> int rather than something more generic. F# does the same thing, and it drives me nuts.
Kurt, note that it inferred it was an int list because I started it with '0', if I had started the recursion with '0.0' it would have assumed it was real.
Doh, I totally missed that. What if the function took both a list and a starting value, would you end up with a generic function restricted to things with the + operator defined?
Kurt, I tried it, and it didn't, it assumed it was an int. I think the issue is that SML isn't object orientated, it doesn't have a concept of inheritance. Otherwise, you could have a Number class that defined the + operator, and then Integer and Real would be subclasses of it.
Apparently Ocaml does support Object Orientated programming, so perhaps it does something better.
ian,
Haskell's type classes allow precisely that benefit -- there's a Numeric type class that common operators apply to.
OCaml unfortunately lacks this capability.
Andy, that is good to know, I'll definitely look at Haskell more closely (I always just assumed Haskell was due to the normal Glaswegian antipathy towards all things Edinburgh ;).
IMO the main reason to learn Standard ML is so you can read Appel's Modern Compiler Implementation in ML and the chapter in ML for the Working Programmer that discusses a simple tactical theorem prover.
Beyond that, Haskell has a much more active community, and F# has much better libraries.
I second the other recommendations to give Haskell a serious look. I had a very similar experience to yours with SML, and I still find it a remarkably elegant and lovely language, more so than Haskell in some respects. But Haskell is both much more sophisticated and much more active at this point, it's also a lovely language, and it has a very similar flavor to SML.
Incidentally, it looks like the forthcoming book Real-World Haskell is going to be quite good, going much farther than existing intro books and really getting into some practical benefits of Haskell's design.
> OCaml unfortunately lacks this capability.
On the other hand, OCaml does provide subtyping :
let rec sum zero = function
| [] -> zero
| hd::tl -> hd#add (sum zero tl)
The inferred type is :
val sum : 'a -> 'a; .. > list -> 'a =
'a; .. > means "any object with the method add and the right type"
I'm not saying this is equivalent to typeclasses (it is actually quite different, and typeclasses are nearer to the module system imho), but this is a possibility that should not be neglected.
Moreover, this precise example is quite moot actually, as those three languages all have a fold_left (foldl) operation that is strictly more generic, as you can give both the operation (+) and the identity element :
foldl :: (a -> b -> a) -> a -> [b] -> a
# List.fold_left (+) 0;;
- : int list -> int =
# List.fold_left (+.) 0.;;
- : float list -> float =
The overloading is actually a minor issue in that case, and i think this is a poor example of typeclass usefulness.
Definitely do take a second look at Haskell. It's full of brilliant ideas. For example, Haskell's monads let it manage side-effects such that it's not inconvenient to work in a pure functional language. They also capture a large number of other concepts: continuations are implemented in pure Haskell as a monad.
A sail veering about the blank bay waiting for a swollen designer sunglasses wholesale bundle to bob up, roll over to the sun a puffy replica sunglasses wholesale face, salt white. Here I am. They followed the winding path down to the creek. Buck Mulligan stood on a stone, in shirtsleeves, his wholesale cheap sunglasses unclipped tie rippling over his shoulder. A young man clinging to a spur of rock near him moved slowly frogwise his green sunglass wholesale legs in the deep jelly of the water. Buck Mulligan sat down to unlace his wholesale oakley sunglasses boots. An elderly man shot up near the spur of rock a blowing red sunglasses for wholesale face. He scrambled up by the stones, water glistening on his fashion sunglasses wholesale pate and on its garland of grey hair, water rilling over his chest and paunch and spilling jets out of his wholesale sunglasses china black sagging loincloth.