Functional Programming @ MindSay

One of my recent job assignments is to understand "Latin Hypercube Sampling" (a variant of Monte Carlo sampling that needs fewer iterations to cover the full range of values), and in order to accomplish this, I'm writing some programs to let me play around with different techniques.  To do this, I'm using my favorite not-ready-for-prime-time programming language, SML.  SML/NJ to be precise.  I'm enjoying it so much that I feel compelled to write something about it.

SML is one of the more pragmatic members of the functional programming language (FPL) family, which includes Lisp, Haskell, Erlang and a few other languages you also never heard of.  (To be fair, lisp is only barely an FPL by modern standards and is really it's own family of languages - sort of like C++ is only sort of an object oriented language.  Yeah, you can code that way, but it's not your only or even necessarily primary option.)  SML has the same reliance on recursion, strong (but silent) type checking, automatic memory management and inability to re-bind variable values of more strict FPLs, but it includes some assignable variables and other concessions to "real world" programming that make it easier to hack around in, and don't require a doctorate in computer science to understand.

For example, here is a function that shuffles to lists of numbers together.  Think of it as shuffling a deck of cards:

fun shuffle ([], deckb) = deckb

  | shuffle (card :: decka, deckb) =

        card :: (shuffle (deckb, decka))

You could also write this as:

fun shuffle (decka, deckb) =

    if null decka then

       deckb

    else

       (hd decka) :: (shuffle (deckb, tl decka))

What this means is that the function "shuffle" has two cases:

If you're shuffling an empty deck with any thing, then the other deck is the result

Othewise, take a card from decka and put it at the front of a deck that is the shuffling of the rest of decka with deckb.  I swap the two decks in the call so that I can take cards from each deck in turn.

SML is a strongly typed language, but where are the type declarations?  Well, the compiler can figure them out from the code.  In this case, it knows that the first parameter to "shuffle" has to be a list, because one of the possible values is the empty list.  And because I call "shuffle" with "deckb" in the first parameter, it can tell that the other one has to be a list too.  (It could also tell that from the return values - the return value must be a list because I'm sticking "card" on the front of it, and that operation is only valid for lists.  Since "deckb" is a possible return value, it must also be a list.)

You can specify the types if you want to, and in some rare cases you *have* to specify them, but in general you get all the benefits of strong typechecking (compiler warnings, etc.) without having to spell things out for the compiler.  The only problem is that SML is WICKEDLY strongly typed, and doesn't do any automatic conversion of anything for you.  So if you want to say something like "1 + 2.0", you'd have to either cast 1 to a float or 2.0 back to an int, or it wouldn't compile.  Generally I'm in favor of this, but it does make some things harder to code than in C.

One of the really nice thing about SML's type system is that it automatically has the sort of generic programming thing C++ templates give you.  For example, the actual type of the function above is "'a list * 'a list -> 'a list", which means "takes a pair of lists of anything, and returns a list of the same sort of thing".  You can have functions like "'a * 'b -> 'c", which means "Takes two things that aren't necessarily the same type, and returns something that might not be related to the first two things".  It's very flexible, and lets you write nice generic functions like shuffle without having to worry.  If you call shuffle on a list of strings and a list of integers, it won't compile.  The compiler knows the two should be the same kind of list, and won't let you mess up.

Now SML isn't really ready for prime time, as I've mentioned, and although there are .NET compilers for it, it's really not very good for talking to the OS or writing windows programs with.  And because it's not OO, it can't really participate in .NET very well, since the whole system is designed to be used from an OO language.  The compiler I use is essentially a unix style command line compiler with an interactive environment that makes SML feel like an interpreted language.  It's very convenient to try things out in, which is why I like using it for a "lab" language.

(SML does have a sophisticated module system, the equivalent of C++ templates, exception handling, etc., but that stuff is a little beyond the scope of my little "SML Love" blog entry.)

I guess that's enough expounding on the virtues of an obscure language from a dying branch of computer science for now.  At least C# is starting to adopt some of the SML features so they won't be lost forever.