Friday, August 9, 2013

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?

Wednesday, August 7, 2013

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).