Time to get cracking

"This business isn't for men of words," said Borja. "It's for men of action."

A. Perez-Reverte, The Club Dumas

I have some ideas for Effes that I haven't written about yet, but it's time to take a break from this exploratory spec work and get some concrete stuff done. I'm going to handle this in four stages:

1. Feature freeze: Done, as of... now. In order to make Effes what I want it to be, I will eventually features such as easy exec'ing to shell (hopefully as easy as it is in bash), easy parsing of inputs from shells, and other things. Eventually I'll probably need a multithreading model, too. But for now, I'm going to say that anything I haven't discussed so far isn't making it to this first pass.
2. Informally figuring out the syntax: In other words, me toying around in vim to figure out what I want programs to look like.
3. Coming up with a spec: Basically, stabilizing the doodles from the previous step and formalizing them.
4. Implementation: I have no idea how I'll do this. Hopefully I'll be brave enough to try and use Haskell until Effes can bootstrap itself. I'm going to have to read up on type inference, aren't I? Yikes.

Stage 2, which is the one I'm in right now, probably won't yield much interesting blog material. Stage 3 might, and I hope stage 4 will — though it'll probably more about me learning Haskell than about Effes, at that point. In the meanwhile, I've got some rants and mouth-foaming that might kill some time. Didn't I promise a rant about Guava's Optional<T> a few months ago?

Conjunction disjunction, what's your function?

It's time to turn my attention to functions. Like virtually any language, Effes has functions; like any language written in the last few years, those functions are data. (At what point does the term "functional programming language" start to lose its meaning, given that every language these days incorporates FP principles?)

Every function in Effes has a type, which is just its signature. For instance, doubler(i : Int) = i * 2.0 would have a type of Int -> Double. Subtyping basically follows the Liskov substitution principle: f : Vehicle -> Door is a subtype of g : Car -> Part because you can use f anywhere you'd be able to use g.

Like data types, function types can be composed into conjunctive and disjunctive types. Take the following:

data Cat, Person
countLegs : (Cat -> Int) = c -> 4
sayHi : (Person -> String) = p -> "Hi, I'm #{p.name}"

countHi = countLegs sayHi

countHi is a conjunction of countLegs and sayHi. Invoking this function doesn't chain or compose them; only one will get invoked. Think of it as a box that contains both functions: invoking this box means opening it, taking out one of the functions, and using it.

This follows the data trait analogy: a Cat Person type refers to an object that is both a feline and a human; it also can be thought of as two separate objects stuck together. When you have a Cat Person and ask for its fur type, you're looking at its cat-like nature; when you ask for its social security number, you're looking at its person-like nature. Similarly, countHi has both a countLegs-like nature and a sayHi-like nature.

(There's a slight difference here in that a conjunctive data type can be used in functions that look at both of its aspects; this doesn't apply to functions.)

This means that the input to countHi can either be a Cat (in which case countLegs is invoked) or a Person (in which case sayHi is invoked). In the first case, the result is an Int, and in the second case it's String. Putting that together, we get a type of (Cat | Person) -> (Int | String). More generally:

(Ia -> Ra) (Ib -> Rb) : (Ia | Ib) -> (Ra | Rb)

Disjunctions follow the same analogy; a Cat | Person type refers to a single object which is a feline or person, so functional disjunctions work the same way. Imagine a type that said "I'm either countLegs or sayHi". To pass an argument into it, you'd have to guarantee that the argument could be passed to either function; it would have to be both a Cat and a Person. Depending on which function got invoked, the result would be either an Int or a String.

(Cat -> Int) | (Person -> String)
 : (Cat Person) -> (Int | String)

(I0 -> R0) | (I1 -> R1) : (I0 I1) -> (R0 | R1)

Notice the symmetry here: The input to a conjunction of functions is the disjunction of their inputs, while the input to a disjunction of functions is the conjunction of their inputs. In both cases, the result is a disjunction of their results.

One edge case is when the input to a conjunction is composed of both input types. For instance, what happens if we break out the beakers and engineer a Cat Person? If we pass it to a conjunction countLegs sayHi, both functions in that composed function can process it. Which gets to? (This isn't a problem for a disjunctive type, since its object is just a single function.)

I'm not positive how to handle this case. One solution is to have both functions process it, and then compose the result. So, passing Cat Person to countHi = countLegs sayHi would result in a (4 "Hi, I'm Yuval") : (Int String).

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.