This blog has moved

I have not seriously updated the old Apocalisp blog for quite some time. Mostly this is due to the fact that I have been spending all of my creative time outside of work on writing a book. It’s also partly that putting a post up on WordPress is a chore. It’s like building a ship in a bottle.

So I have decided to make posting really easy for myself by hosting the blog on GitHub. I am using a dead-simple markdown-based framework called Octopress. With this setup I can very easily write a new post from my command line and publish by pushing to GitHub. This is already part of my normal coding workflow, so it feels more friction-free.

The new blog is simply titled “Higher Order”, and is available at blog.higher-order.com. Check back soon for posts that I’ve been sitting on but have been too lazy busy to post.

All of the old content and comments will still be available at the old address, and I’ll probably cross-post to both places for a little while.

 

Towards an Effect System in Scala, Part 2: IO Monad

In the previous post, we looked at the ST monad and how we can use it to encapsulate in-place mutation as first-class referentially transparent expressions. ST gives us mutable references and arrays, with the following guarantees:

  1. Mutations of an object are guaranteed to run in sequence.
  2. The holder of a mutable object is guaranteed to hold the only reference to it.
  3. Once a sequence of mutations of an object terminates, that object is never mutated again.

These invariants are enforced by the type system. I think that’s pretty cool, and sort of stands as a testament to the power of Scala’s type system.

This is much more than “delay side-effects until the last possible moment”. Remember, it is always safe to call runST on an ST action, anywhere in your program. As long as the call typechecks, it will have no observable side-effects with regard to STRefs and STArrays.

OK, so far we only have these guarantees for references and arrays, but that’s really not bad at all. We can eliminate an enormous class of bugs that have to do with shared mutable state, by guaranteeing that mutable state is never shared. Of course, you can still mutate other objects to your heart’s content (ones that are neither STRefs nor STArrays). But imagine for a second if Scala were modified in such a way that the var keyword actually constructed an STRef, and the only arrays provided by the library were of type STArray. Wouldn’t that be something? Wouldn’t that basically make Scala a purely functional language?

Well, no. There’s I/O. While ST gives us guarantees that mutable memory is never shared, it says nothing about reading/writing files, throwing exceptions, opening network sockets, database connections, etc.

The IO Data Type

We’re going to represent I/O actions as state transition functions, just like ST actions. Remember that ST is essentially a type like this:

type ST[S, A] = World[S] => (World[S], A)

The IO data type is very similar, except that we fix the world-state to be of a specific type:

type IO[A] = ST[RealWorld, A]

RealWorld is totally abstract. It’s an uninhabited type (there are no values of type RealWorld). And we will understand a value of type World[RealWorld] to represent the current state of the entire universe. Sequencing is guaranteed, just like with ST, since the IO monad has to pass the world state in order to execute the next action.

In Scalaz, it’s not possible (without cheating) to create a value of type World[RealWorld]. There are no values of this type. So how do you run an IO action? Well, the IO[A] data type has the following method defined:

def unsafePerformIO: A = this(null)

This is actually cheating a little bit, because we’re faking the value of type RealWorld by passing nothing at all. We’re about to potentially destroy the universe anyway, so this is OK just once. Besides, there’s a reason why this method has “unsafe” in the name. You only want to ever call this method once. The idea is that you construct your entire program with as much a purely functional core as possible, and an outer shell written in the IO monad. Then at the “end of the universe”, you call unsafePerformIO:

import scalaz._; import Scalaz._; import scalaz.effects._

def main(args: Array[String]): Unit =
myProgram(ImmutableArray.fromArray(args)).unsafePerformIO

def myProgram(args: ImmutableArray[String]): IO[Unit] =
error("Your IO program goes here.")

Again, imagine if Scala were modified in such a way that instead of looking for def main(args: Array[String]): Unit, it would look for def main(args: ImmutableArray[String]): IO[Unit].

Benefits and Weaknesses of the IO Monad

Because the World type argument is fixed in the definition of IO, we don’t have the same guarantees that we did with ST. Basically we can’t guarantee that the world state will never escape from unsafePerformIO. But we do have some other nice benefits.

For example, sequencing is still guaranteed, so no part of an action that depends on another will ever run before its dependency. This can be a problem if IO[A] is modeled as simply () => A. Also, IO actions are first-class objects, so they are freely composable and re-usable.

IO With the Scalaz Library

Scalaz includes a bunch of IO combinators for manipulating standard input and output, throwing/catching errors, mutating variables, etc. For example, here are some combinators for standard I/O:`

def getChar: IO[Char]
def putChar(c: Char): IO[Unit]
def putStr(s: String): IO[Unit]
def putStrLn(s: String): IO[Unit]
def readLn: IO[String]
def putOut[A](a: A): IO[Unit]

Composing these into programs is done monadically. So we can use for-comprehensions. Here’s a program that reads a line of input and prints it out again:

def program: IO[Unit] = for {
line <- readLn
_    <- putStrLn(line)
} yield ()

Or equivalently:

def program: IO[Unit] = readLn flatMap putStrLn

And if we wanted to write another program that re-uses our existing program, we can. Here’s a program that runs out previous program forever:

def program2: IO[Unit] = program |+| program2

IO[Unit] is an instance of Monoid, so we can re-use the monoid addition function |+|. Because everything is pure, we can concatenate programs just as easily as we concatenate Strings.

It’s also important to note that we’ve gained type safety. If you try to do this, you will get a type error:

scala> (readLn flatMap putStrLn) |+| System.exit(0)
<console>:17: error: type mismatch;
found   : Unit
required: scalaz.effects.IO[Unit]

Conclusion

We can gain a lot of static safety by separating values that produce I/O effects from values that have no effects, differentiating them via the type system. We also gain modularity by treating I/O actions as pure, compositional, first-class values that we can freely reuse in a completely deterministic way. Instead of running I/O effects everywhere in our code, we build programs through the IO DSL, compose them like ordinary values, and then run them with unsafePerformIO as part of our main.

 

Pascal’s Wager and the Problem of Computability

I was on a cable car yesterday morning and I was intellecually tickled by an advertisement posted on one of the walls in the car. It was an ad for a unitarian church, and in it they quoted Blaise Pascal:

It is incomprehensible that God should exist, and it is incomprehensible that He should not exist.

Pascal was a philosopher and mathematician, and he was trying to understand the question of whether or not one should believe in the existence of a God (specifically the Christian god, but that’s not important). He concluded that since the benefits of belief are supposedly enormous (or infinite), and one cannot actually know, one should wager in favor of there being a God, since then the benefit of being right is maximized and the cost of being wrong is minimized.

But Pascal made an error in his premises, which touches on computability theory. He sets out assuming that the statement “God exists” is either true or false. This is an unwarranted premise. Pascal was a rationalist, so he assumes the dichotomy of truth, that every statement is either true or false. But any programmer can tell you that this isn’t the case.

You see, Aristotle understood that not every statement is either true or false. The law of excluded middle says that a thing either is or is not. And truth or falsehood is an attribute only of statements that refer to things which are. For this reason, some statements are simply absurd, or arbitrary. Such statements cannot be examined for truth or falsehood. They can only be dismissed out of hand, as if nothing had been said. Because, in a very strict sense, nothing really has.

In computation, this is equivalent to the fact that not every program has an answer. Some programs simply bottom (crash or hang). There are types that are nonsensical and have no implementation except for programs whose answer is bottom. And there are questions that have no answer because they are nonsensical, and statements that are neither true nor false because they do not refer to any attributes or configurations of things which exist.

But it is absurd and impossible to suppose that the unknowable and indeterminate should contain and determine.

- Aristotle

Not only is it not right, it’s not even wrong!

- Wolfgang Pauli

On two occasions I have been asked,—”Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?” … I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.

- Charles Babbage