Another blow against strict immutability

I know I've talked about mutability before, but I realized the other day yet another argument against taking immutability too far: it complicates logging.

I'll take Haskell as my usual favorite example, but this time I won't put it in a favorable light. Because it treats all I/O as non-pure, mutable behavior, any logging you do has to be within the IO monad. This means you have to change your application's structure to support logging. You have to do so within a monad, and, if that monad doesn't happen to be IO, it needs to be a transformer monad. If it's not, and you want logging — find a new monad.

(Full disclosure: I haven't written any real apps in Haskell, so I haven't needed logging past what the repl shell gives me. Maybe all of this is not a problem in practice.)

You can cheat a bit: there's a debug module that lets you log from pure code, but it's not meant for production. For the most part, pure code just can't be logged.

To me, logging is critical. It's important both for "interactive" debugging (as I'm writing new code) and for figuring out what went wrong when a bug crops up in the field. At the same time, it's orthogonal to the logic of the application, and so should dictate as little as possible about how the application is set up. If I have to turn a pure function into an impure one just so I can log some values, that seems like the tail wagging the dog.

Even though Effes is restrictive about mutable types, it considers loggers immutable because their actions (namely, printing bytes to a file) can't directly change the behavior of Effes objects. This means you can use a logger anywhere you like, which is good.

Polymorphic upcasting?

In my last post, I summarized Effes' polymorphism by observing that you can't know exactly how an object will behave unless you create it. That's actually not so weird — it's how all OO code works. I know exactly how an ArrayList works in Java; I have pretty much no clue how a List I get from a function will work (unless I look at that function's code, of course). The twist that Effes brings is that the binding is done based off of an object's specific composition, not based off its class. It's much more fluid.

That last post had various examples, but here's an interesting one: you can actually upcast an object's function resolution! Here's how:

data Loud; Animal; Cat
Cat is Animal

speak(c:Loud Animal) : String = "Stomp!"
speak(c:Loud Cat) : String = "Meow!"

getAnimal() : Animal = Loud Cat
animal = getAnimal() // 1
loudAnimal = Loud animal // 2

speak(animal)
speak(loudAnimal)

At line // 1, we get some sort of Animal. We don't know what kind, but we don't need to because of polymorphism. As it happens, it's a Loud Cat, which means it'll meow at us when we ask it to speak.

At line // 2, we take our animal and make it loud. The interesting thing to note here is that the animal already was loud, though the compiler doesn't know it: specifically, it was a Loud Cat. But, since the compiler doesn't know that, it creates a new object, with new bindings. At that point, the only thing the compiler knows is that it's a Loud Animal, so it binds it to the stomping version of speak.

This behavior is a bit counterintuitive at first. By doing what most systems would call a no-op (I even said it would be, last month!), an object's behavior changes. Specifically, adding the Loud trait to an object that already had it ended up changing its function binding.

This may seem weird, but I'd like to give it a try. My hypothesis hope is that the tradeoff of more deterministic object creation is worth it.

Incidentally, this rebinding would not happen if the operation was known to be a no-op at compile time:

getLoudAnimal() : Loud Animal = Loud Cat
animal = getLoudAnimal()
loudAnimal = Loud animal

Here, animal is already Loud, so adding Loud to it becomes a compile-time no-op, with no rebinding. While this particular example is silly, this use case is actually useful if the redundant trait has parameters that you'd like to change:

data Microchipped(id : Int)
data Cat

getAnimal() : Microchipped Animal =
  Microchipped(123) Cat

animal1 = getAnimal()
animal2 = Microchipped(456) animal1

Here, we're changing the animal's microchip id without having to worry about upcasting its function resolution.

Subtyping and function resolution (at last!)

I've been putting off for too long my ideas for subtyping and function resolution, because I've wanted to get things juuust right. Instead, I'm going to just outline my ideas and move on, because I want to start coming up with a grammar and writing some actual Effes. I've been dragging my feet for too long!

So, subtypes first, then function resolution.

Type hierarchy in Effes

• A is a subtype of B if there is a "class-based" implementation that says B is A. For instance, if we declare that Stack[A] is Sizeable where..., then Stack[A] is a subtype of Sizeable
• A is a subtype of B if A is a conjunction type whose parts include B. For instance, FourWheeled Vehicle is a subtype of FourWheeled and Vehicle.
• Union types act as a single unit and don't establish any subtype relationships with their components. So:
  
  • Cat | Mouse isn't a subtype of Cat or Mouse.
  • Neither Cat nor Mouse are a subtype of Cat | Mouse.
  • However, since Cat | Mouse is a single unit, Cute ( Cat | Mouse) is one of its subtypes.
• Any type is of course a subtype of itself.
• Without getting into too much details, subtypes work with the components of conjunction types, not just the full conjunction. For instance, if Box is a subtype of Container, then Big Box is a subtype of Big Container.
  

I think for generic types, I'll say that Box[Gum] is a subtype of Container[Candy] if Box is a subtype of Container and Gum is a subtype of Candy. This is extremely up for grabs; it can wreak havoc on collections, but that's because they're mutable. Effes has a much stricter set of restrictions on mutability, which I think eliminate the problem.

Function resolution

In a nutshell: functions are bound to an object according to the most specific type information known about it at compile time. (That last bit is important!) For each function f, find the most specific subtype that defines f, and bind that version of f to that object.

-- Define some types
data Animal; Ascii; Cat; Dog
Dog is Animal
Cat is Animal

-- Define some methods
speak(a:Animal) : String = "Zzzz" -- all animals sleep
speak(c:Cat) : String = "Purr"
speak(c:Ascii Cat) : String = ">^-^<"

-- Invoke them
speak(Cat) -- Purr
speak(Dog) -- Zzzz
speak(Ascii Cat) -- >^-^< 
peak(Dog Cat) -- compile-time error
speak(Ascii Animal Cat) -- >^-^<

The first three of the function invocations should be pretty straightforward. The fourth case is a compile-time error because Dog Cat is "equally subtype-y" to both Dog and Cat, so the compiler doesn't know which method to use. (Maybe I'll provide some overriding behavior in the future, but for now I'm just going to disallow it altogether.) The last one is an edge case — hey, every language has to have 'em! The reason is that type conjunctions are commutative and associative: (A B) C is the same as B (C A). So, even though Ascii Animal Cat doesn't look like anything meaningful, it can also be expressed as (Ascii Cat) Animal, which is a subtype of both Ascii Cat and Animal (as well as of Ascii and Cat, but that's not important for this example). Since Ascii Cat is itself a subtype of Animal, it is the most specific subtype and thus supplies the function. One last thing, which is the bit about binding at compile time. Let's tweak the menagerie a bit:

data Ascii; Hungry; Cat

speak(c:Ascii Cat) : String = ">^-^<"
speak(c:Hungry Cat) : String = "Meow!!" -- at 5am...
speak(c:Hungry Ascii Cat) : "4d 65 6f 77 21 2`"

getKitty() : Cat = Ascii Cat
c1 = getKitty() c2 = Hungry c1

In this example, c1 has a compile-time type of Cat and a runtime type of Ascii Cat. However, where the object was created (namely, the only expression in the body of getKitty), it had a compile-time type of Ascii Cat, so speak(c1) is bound to speak(c:Ascii Cat) and would result in ">^-^<". The last line is where things get potentially unfamiliar. Even though c1 has a runtime type of Ascii Cat, it has a compile-time type of just Cat, so Hungry c1 has a compile-time type of Hungry Cat, not Hungry Ascii Cat. This means speak(c2) would result in "Meow!!".

This feels a bit weird at first blush: it's a blend of polymorphism and... something that feels un-polymorphic. I may change my mind, but the reason I like it is that you can know, easily and deterministically, how functions will be bound just by looking at where an object is created. That is, you don't have to reason about where the object came from and what its runtime type might be; you just look at what it is, and there you go.

The basic rule is that you can't know exactly how an object will behave unless you create it.

The path to function resolution is a winding one

Eek, it's been a while since I've written here. I've been putting off a few posts on subtypes and function resolution, because my ideas aren't fully fleshed out. But here's an update, which is mostly some insight into how my thought process is changing.

I originally had a fairly complicated subtyping scheme in mind, because I wanted to support various ways of composing types. A lot of that had to do with the fact that I wanted to be able to write code like:

data Foo(foo : String)
data Bar(bar : String)
data Buzz -- no args

a = Foo("something")
b : Foo = a Bar("another")
c : Foo Buzz = b

The first two assignments are simple, but the third is... weird.

• a is a Foo
• a Bar("another") is a Foo Bar, which is a subtype of Foo and can thus be assigned to a Foo-typed reference — in this case, b
• c : Foo Buz would be neat if it worked, but it'd require jumping through hoops with the subtyping

The reason I want that last line to work is that Buzz may have some neat behavior, including an override of default behavior. Here's a more concrete example:

getNames() : Stack[String] = ...
useNames(names : QuickSize Stack[String]) = ...
useNames( getNames() )

I'm using the definitions of Stack[A] and QuickSize from a while back. Basically, Stack[A] is Sizeable but has O(N) performance for getting a stack's size, while QuickSize can override a Sizeable object's size method to provide O(1) performance.

The problem is that useNames wants that O(1) performance, while getNames doesn't provide it. My original idea was to allow this with some weird, complicated subtyping rules; that's a bad idea, and I'm abandoning it. My next thought was to allow type declarations to implicitly create composite objects, such that this:

c : Foo Bar = Foo(789)

...would be sugar for this:

fTmp : Foo = Foo(789)
bTmp : Bar = Bar()
c : Foo Bar = fTmp bTmp

I think I'm going to abandon this as well, because it's still complicated and doesn't buy much. In fact, given that I want type inference to eliminate most explicit typing, putting so much semantic importance on declared types is actually a pretty counterproductive plan.

So here's my new idea: do nothing!

Here's how it works. Let's say you have getNames() and useNames as above. In that case, the call site just has to add the QuickSize itself:

useNames( QuickSize getNames() )

That's not so hard. It works because QuickSize (getNames()) creates a new object, the composition of the getNames() : Stack[String] and QuickSize. ("Creates" in the conceptual sense; it may be optimized to just a runtime check).

Better yet, the useNames method can get rid of the QuickSize requirement altogether, since it's just an optimization that polymorphism can handle within the method:

useNames(names : Stack[String]) =
  names = QuickSize names
  ...

So, that's where I am right now. This simplifies the subtyping system a lot, though I still have to figure out what to do with generics and covariance (Stack[Int] vs Stack[Num]). And those simplifications in turn simplify function resolution, which is where all this is really headed in the end.

CoffeeScript should handle callbacks better

I want to add a quick addendum to yesterday's post about best practices. I mentioned the staircase problem caused by Node's reliance on callbacks: if one action is a prerequisite for other actions in a method (for instance, you query a database and then act on those results), the rest of that method ends up indented.

Node has another big problem, which is that its target language, JavaScript, is awful. Luckily, one of Node's third-party modules, CoffeeScript, provides a decent language that compiles down into JavaScript. We get all the Node goodness without the CoffeeScript badness!

Since CoffeeScript is a new language that can evolve quickly, and since one of its main use cases is Node, and since Node relies heavily on callbacks... why not add some sugar to make callbacks a bit nicer? I propose a way to bind callback arguments to left-hand variables. This is actually pretty similar to what Haskell does with its do notation, and for pretty similar reasons.

Let's take a simple, imperative-with-exceptions snippet of code:

try
  res1 = func1 arg1
  [res2a, res2b] = func2 res1
  if res2a is "foo"
    doFoo()
  else
    res3 = func3 res2b
    doBar res3
catch err
  handle err

That's pretty simple. Watch how gross it turns when we use callbacks instead of just returning back the results:

func1 arg1, (err, res1) ->
  if err?
    handle err
  else
    func2 res1, (err, res2a, res2b) ->
      if err?
        handle err
      else if res2a is "foo"
        doFoo()
      else
        func3 res2b (err, res3) ->
          if err?
            handle err
          else
            doBar res3

My suggestion is to create some sugar for that. It would look something like this:

do and throw err...
  (err, res1) <- func1 arg1
  (err, res2a, res2b) <- func2 res1
  if res2a is "foo"
    doFoo()
  else do...
    (err, res3) <- func3 res2b
    doBar res3
  catch err
    handle err

Notice how similar this is to the original, easy-to-read, imperative style. The general idea is simple: the new do... syntax introduces a block of code in which callback variables can be bound on the left-hand side. Every time that happens, it starts a new callback nested in the previous one. If you provide the and throw varname syntax, then it treats left-hand bound variables of this name as errors, and if one ends up being non-null, its callback will run the code in the catch block and nothing else.

I won't pretend this is a small bit of sugar; it probably has some interesting edge cases, and the concept might be a bit weird to grok for someone who's new to it. But it's an elegant solution to a real problem that's pretty significant for a major part of CoffeeScript's target audience.

Tutorials need a section on best practices

I took a bit of a break from Effes over the Fourth of July weekend to relax with friends, watch some TV and teach myself node.js by jumping into a small project. The process reminded me of a problem I've hit a few times in various self-learning exercises: docs for languages and frameworks tend to focus almost exclusively on syntax, APIs and other hard facts, but they don't talk much about best practices.

With Node, my question was how to get around the "staircase problem," where indentations march the code off the right side of the screen. Node is non-blocking and uses callbacks for just about anything that goes to the outside world. For instance, its mysql module puts its result set into a callback. That has some neat benefits, it leads to indentation hell. Here's an example in CoffeeScript:

m = mysqlPool()
m.query getFizzes, (err, fizzes) ->
  if err?
    console.log "Error: #{err}
  else
    foos = [fizz.foo for fizz in fizzes]
    for foo in foos
      do (foo) ->
        m.query selectBars, [foo], (err, bars) ->
          if err?
            console.log "Error 2: #{err}
          else
            console.log("Found a bar!", b) for b in bars

That barely even fit in this blog layout; I had to change bar to b in the last line. And while it's true that blog layouts aren't where most coding happens, the staircase problem is annoying and makes code hard to read.

Now, this is not the biggest problem in the world, but it does make code a bit hard to read if the sequence of actions gets much longer (it's only two above). I solved it in one kinda-hairy section (4-long sequence with a conditional, oh man!) with a bit of refactoring, but the resulting code was actually a bit harder to follow because it broke up the logic's natural flow.

There are other ways I could have solved the problem, and there's at least one third-party module that may help, but here's the real point: the Node docs don't help me out. They don't even acknowledge the problem. If the best thing to do is to use async with CoffeeScript, Node should tell me so.

Maybe it's unfair to pick on Node's docs, since there's barely anything as far as a tutorial. You've got a "hello world" example on the front page, a link to the built-in library's APIs, and that's about it. But it's not just Node.

For instance, the intro guide for Ruby on Rails promises to teach the reader "the basic principles of MVC," but it never mentions MVC again, and doesn't give much guidance for when to put logic in a controller vs a model. Github doesn't talk about the benefits of forking vs branching — the first three hits for "git fork or branch" on google are all on Stack Overflow. Guice's tutorial doesn't tell us where to put our injector. And so on.

I'll give the RoR guide some slack, because MVC has been around for a while; maybe they just assumed that most of their readers would already know it. But in general, the more newfangled a technology is, the more its project should tell newbies not just how to use it, but how to use it well.

Immutability and randomness

In my last post, I proposed a working definition for mutability: in short, an object mutable if code can directly affect its state. I mentioned one odd implication of this rule: certain OS calls like getCurrentTime are considered immutable even though their results are different each time. An even trickier problem is that of randomness and pseudo-randomness.

Let's take a random number generator first. There are various ways to produce truly random (or very close to it) number sequences: using the weather, relying on hardware inputs, or even leaning on quantum mechanics. A language can't affect any of these, so random number generators that use them fall within the realm of immutable objects by my definition.

On the other hand, a pseudo-random number generator's sequence is completely based on code, once its initial state is set. The PRNG has some seed, and when asked it does some math to determine a new seed and a result for the random. This means that PRNGs are "normal" objects that have to participate in a language's mutability rules.

For languages that have immutable objects, this makes PRNGs awkward to work with; rather than just asking for the next random number, you have to ask for a pair (randomNumber, nextPrng). If you forget to do this, your pseudo-random sequence will be boringly predictable. Here's an example from Haskell (using ghci):

> prng <- getStdGen > next prng (750537749,750578441 40692) > next prng (750537749,750578441 40692) > next prng (750537749,750578441 40692)

As you can see, this is quite boring; the reason is that the second element of the returned pair (shown here as "750578441 40692") is the crucial next-immutable-PRNG, which we're not using. Here's that code done right:

> prng0 <- getStdGen > let (r1, prng1) = next prng0 :: (Int, StdGen) > let (r2, prng2) = next prng1 :: (Int, StdGen) > let (r3, prng3) = next prng2 :: (Int, StdGen) > r1 750537749 > r2 1579754317 > r3 1580611703

This is the behavior we want, but look how much more code it took! Even ignoring the ":: (Int, StdGen)" bits (that's Haskell needing some help with its type inference), it took twice the lines of code and required littering the block with one-time-use prngN variables.

This is a case where I think Effes' semi-mutability really shines. Once you get the PRNG object, you can use it all you want, and it'll mutate its internal state to update its seed as it goes. If you pass it to a function, that invalidates (at compile time) your copy; you have to get a different one if you want to continue generating random numbers. This is a tad more cumbersome, but not much (there are ways to alleviate it, such as "forking" the PRNG before passing it to the function).

Immutability isn't an exact science with these clowns

The last few posts have read like a reference manual more than a blog, so I'm going to switch things up a bit and write about immutability at a high level. This post will have an Effes-based perspective, but it won't tie in directly to the language.

The question of the day is: what makes an object immutable? The easiest and (almost) most restrictive definition is that nothing about the object can change — its bytes are determined at construction time and never altered afterwards.

Well, what about an object that lazily caches the result to some method — a lazy-evaluated asString field for the object's toString representation? The first invocation of toString will modify the object's bytes, but I would argue that it's still immutable because its observable behavior has not. This is my version of the equivalence principle: if you can't tell from your rocket ship that the universe has changed, then it hasn't in any real sense.

Let me take it a step further: is stdout mutable? Let's assume that a write to stdout never fails, that the stream is never closed, and that the stdout object doesn't contain state such as "how many bytes have been written so far." In this case, from the language's perspective, the stdout object has no state, which is just about the most immutable a thing can be.

On the other hand, most output streams are mutable, because they can be closed. Streams can also fail due to things like a full disk or dropped connection, but I see those as two different scenarios: in one, the behavior of the object changed due directly to an action the code took, whereas in the other, the behavior changed due to an external event.

This is an important distinction, because otherwise even the original, "most restrictive" definition above is not enough. Let's say we want to define immutability strictly as "the object's behavior never changes," so that an uncloseable output stream is mutable (because it may fail, thus altering its behavior). Now consider an object with no pre-calculated string representation; its toString method generates a new string each time. This requires allocating memory, which itself may fail — so with our super-strict definition of immutability, even this object isn't immutable. With this definition, the only immutable objects are one with immutable, public fields and nothing else: even a getter could fail due to a stack overflow.

And so, I submit this as a working definition of mutability, at least for Effes: an object is immutable if its behavior can't change in a deterministic way as a direct result of actions expressible in the language.

This definition has an interesting implication: a method that gets the current date/time from the OS is immutable, even though it gives a different result each time! (Let's assume the language doesn't have features built into it that set the system clock.) As weird as this sounds, it actually makes sense, given the problems that I think immutability solves — specifically, no scope can change the date/time for another scope. You won't ever invoke getCurrentTime expecting it to have been set by another scope even though it wasn't; and you won't ever invoke getCurrentTime from one scope expecting it not to have been changed, even though somebody else changed it.