A simpler approach to functional programming

I’ve spent a lot of time thinking about purely functional programming lately.  There’s a lot of exciting stuff going on in the domain lately, mostly thanks to Haskell, which is the only purely functional programming language anyone cares about nowadays.  There’s not necessarily anything wrong with this in and of itself but there’s a disturbing trend that naturally comes about as a result: tending to view Haskell as a “baseline” for type systems and programming language features.  /u/tactics describes this well:

The issue is that any type system will simultaneously be too weak to express some constraints and strong enough to keep you from getting your job done.
There’s a fallacy in presuming that because Haskell (or more generally, any language) has some feature, it should be considered the baseline.
Haskell is littered with good examples of its own limitations (as is any language). Need a version of liftM which will work with two parameters? No problem, we have liftM2. Need one that will work with 6? No can do. Pretty much any library that works with arbitrary tuple types suffers from the same problem that you can’t write code generically over n-tuples.
Similarly, Haskell has no straightforward, culturally-standardized way to prevent users from entering negative numbers into a function, and many basic functions (length, foldl) are partial, with no indication at the type level (and frankly, at the documentation level) that their inputs should not be infinite.

That’s one person’s words, with some specific examples.  I agree with the spirit of that comment which I would summarize simply as “Haskell hasn’t necessarily done everything right”.  Sometimes, people default to thinking that Haskell’s approach is “the right one” for purely functional programming languages, first of all because it’s the only purely functional programming language that is remotely mainstream, and secondly because there is so much that Haskell did right, but make no mistake: the conversation isn’t over because Haskell had a say.  (See the conversation about typeclasses vs. ML-style modules, lazy vs. eager evaluation, first-class records vs. whatever it is that Haskell has, etc.)  This fallacy isn’t good for functional programming in general, and it doesn’t only affect people who are already functional programmers.  I’ve heard people insist they dislike functional programming when, in fact, what they dislike is some particular choice that Haskell made which perplexed or frustrated them.  In this post I’m going to describe one of those choices and I’m going to describe an alternative which I, personally, think is undisputably better.  Here it is:

IO

Somewhat predictably, I’m writing about IO here.  IO and functional programming have somewhat of a contentious relationship because, in a way, they’re sort of diametrically opposed: functional programming isn’t functional programming if it doesn’t make an effort to control and greatly limit side effects.  So figuring out how to make IO “work” with Haskell back in the 90’s was awfully confusing until someone proposed the IO type.  This has been explained to death in other posts so just google “monad burrito” if you don’t already know this, but here’s a quick summary: Haskell’s IO type describes IO actions in an opaque, abstract fashion.  You can string IO actions together by sequencing them.  The result of a Haskell program is a big IO action which is sort of like an abstract syntax tree which the Haskell runtime then interprets for you, thereby preserving referential transparency.  There’s an important advantage of this model in that it makes an essentially valuable distinction between things that have side effects and things that don’t.  As any Haskell programmer will tell you, C’s type system isn’t so amazing because (among many other reasons) every type signature tells you nothing:

int foo(int a, int b);

Who knows what this function does?  I don’t know.  It could do a “pure” computation on the two integers and return a new integer, but it could also do literally anything else, including looping forever, halting the program, dropping all the tables in your database, emailing embarrassing pictures to your mom, launching the missiles, nasal demons, etc.  The equivalent Haskell type signature

foo :: Int -> Int -> Int

severely limits the scope of what foo is allowed to do.  Otherwise, it’s

foo :: Int -> Int -> IO Int

… which reflects all the infinite power of computers.  However, there are also some important drawbacks to this design choice.  Here are a couple:

  • IO is Haskell’s so-called “sin bin”.  There’s one type in Haskell which is allowed to “do stuff”: IO.  Crucially, the language gives you no built-in way to distinguish between different kinds of side effects.  You’re either in pure, side effect-less code or you’re in IO land where anything is possible.  So the type IO () gives you no increased ability to reason about what the IO action does than the corresponding C function signature, which is unfortunate because that’s what purely functional programming is supposed to do for you, right?  Of course you can define your own types which have a more limited scope but this is always ad-hoc, and those eventually have to be hoisted up into IO which leads to nasty stuff like monad transformers and the like.
  • The interface to Haskell’s IO type is monadic.  Let’s not say much about this except that monads aren’t awfully intuitive, and for some reason you see a lot of head-bashing online with people trying to wrap their heads around IO in Haskell.  I refuse to believe that functional programming is itself unintuitive, so there must be some better approach from this respect.

None of this is to say that IO in Haskell is broken, or a disaster, but Haskell doesn’t have the final say.

Starting from scratch

Let’s start from scratch.  If we redesigned IO in a purely functional language from the ground up, how would we do it? Let’s take a basic principle of functional programming: you don’t change data, you perform transformations to make new data.  In Haskell, we have our putStrLn function as follows:

putStrLn :: String -> IO ()

Translating this along the core principle of functional programming, that functions should have no hidden inputs and outputs, we come up with something like this:

putStrLn :: (World, String) -> World

In this case, World is an abstract parameter which abstractly represents the “state of the world”: this function takes a world and a string and returns a new world where the string is printed to the screen. This is an abstraction which doesn’t match up to how things work in the “real world” but it matches up with how other data structures work in purely functional programming languages: nothing changes, but you get new, changed versions of old things. The corresponding getLine:

getLine :: IO String

becomes:

getLine :: World -> (World, String)

The program that reads a line from stdin in Haskell and writes it out? Well, we’re in monad mode, so we need `>>=`:

getLine >>= putStrLn :: IO ()

However, this is just a function composition, isn’t it? In my opinion this is much more clearly expressed in that way:

putStrLn . getLine :: World -> World

This matches up to a more intuitive understanding of how these functions should work and resembles other languages more closely. Here’s another little code sample: let’s open a file and write a string to it.

writeMessage :: File -> File
writeMessage f = fPutStrLn (f, "Hi buddy!")

main :: World -> World
main world = let
(world', f) = open (world, "~/out.txt", ReadMode)
f' = writeMessage f
world'' = close (world', f')in world''

The type signatures here are

open :: (World, String, FileMode) -> File
close :: (World, File) -> World
fPutStrLn :: (File, String) -> File

In Haskell, the type signature of writeMessage would be

writeMessage :: Handle -> IO ()

The superiority of the File -> File type signature in the other model should be obvious for the simple reason that it’s limited; the type Handle -> IO () is unlimited in scope, while the type File -> File can only perform file operations on the input file, because changing any other state requires access to the World (which isn’t an input to the function!). Reasoning about programs suddenly becomes much easier because the types inform our reasoning about what a function is allowed to do, in a way that is enforced by the type system, and which is not necessarily any more complicated than Haskell’s type system already is.

This isn’t the whole story

This isn’t the whole story.  This proposed system isn’t sound as-is; in order to make this a sensible model, you need to supplement it with something called “uniqueness” or “linear types” (see the Wikipedia article), which Haskell doesn’t have.  Haskell doesn’t have those and it doesn’t plan to have those in the future as far as I know; I don’t have time to discuss that in-depth but linear types are really nifty in and of themselves, even outside the context of IO.  I can write about that later.

This isn’t a new, original idea.  There are other languages that have this type system feature already, most notably Clean, a research language which is pretty much dead in the water nowadays.  (Rust deserves a shout-out here for also having affine/uniqueness types, though it isn’t pure or functional.)  I don’t mean to insinuate that I came up with this myself, but it is another way to think about IO in pure functional languages.  I think it’s better.  Maybe you do too.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: