Monthly Archives: May 2008

OO is not the One True Paradigm, but Haskell still sucks at it

I just read osfameron’s Readable Perl talk. It’s a pretty typical language advocation talk, nothing special, but it reminded me of Perl. Those who have not been reading my blog since 2005 may not know that I used to be a Perl nut. I was even on the Perl 6 design team, attended several design mettings with Larry Wall (and a couple other notable geniuses), had the Perl 6 syntax memorized, …. Quite insane I was.

I have been pondering recently about the cognitive mismatch between OO and functional approaches. The two have been fused in languages, see O’Caml, but I argue that code in such a fused language will mostly end up looking like one or the other, not a beautiful balance as we would like.

My thesis is that the two support different models of the universe. The functional approach supports a “mathematical” view, where we know a lot about the structure of our data; the object approach supports an “empirical” view, where we know a lot about the data itself. Let’s use something I was playing with today as an example: the SK calculus.

The obvious functional approach is to define a data type representing the cases of the AST:

data AST = S | K | AST :@ AST

(The :@ is the name of an infix constructor; i.e. it is just a node with two subtrees)

Then to implement a function that, say, reduces the top level of a tree, we can analyze the data by pattern matching:

reduce (S :@ x :@ y :@ z) = Just $ x :@ z :@ (y :@ z)
reduce (K :@ x :@ y)      = Just $ x
reduce _                  = Nothing

Here we know a lot about what kind of argument reduce will get. Whatever it gets, we know that it will be either an S, a K, or an application. We then define what it means to reduce data of this form.

Now I could half-bake a standard OO retort showing how much incredibly better functional programming is by how awkward this would be in a typical OO language (and it would be). But that’s trying to apply the functional world-view, that we know a lot about the structure of our data, to an OO setting. I think a good OO design for this same problem would take quite a different form. I see it something like this:

interface Combinator {
    int arguments();
    AST apply(AST[] args);
}
class S implements Combinator {
    override int arguments() { return 3; }
    override AST apply(AST[] args) {
        return new Apply(new Apply(args[0], args[2]), new Apply(args[1], args[2]);
    }
}
class K implements Combinator {
    override int arguments() { return 2; }
    override AST apply(AST[] args) {
        return args[0];
    }
}
...

While I gave a working Haskell program above in four lines, my “good” OO solution (in whatever language this is… looks like C#) has much more than that and is not even complete. I have left out the definition of Apply and the function which actually does the reduction. But I’m not bashing OO here (but please do understand if I bash OO syntax, which as the years go by seems to get more and more verbose). Instead it’s just that this problem is very well-suited to functional programming.

But this program has very different properties from the Haskell version. In particular, it is easy to add a new combinator, a new object, that does something different. Whereas in the Haskell program, adding a new primitive combinator would change the assumptions of every function that worked with combinators. Conversely, adding data manipulation functions which depend on particulars, namely whether something is an S or a K (or whatever else), involves touching every object to add that method. Whereas in Haskell, we can just add a new function. Astute readers will recognize this as the famous “expression problem”.

This trade-off starts to affect the way we proceed. If we were to implement identical functionality in the two programs, our approaches will diverge greatly. For example, today I added a function to invert an application. In Haskell, I just enumerated by cases: this is how you invert an S-reduction, this is how you invert a K-reduction, etc.

In the OO program I wouldn’t add a visitor though, that would be stupid. Instead I would create a new node type for variables, apply the transformation to a number of variables equal to the number of expected arguments, and analyze the positions of the variables in the result. I would end up with a function that can invert any combinator. That is, the natural next step in the OO example is to write more generic code than in the functional example.

Anyway, there’s what I consider a nice side-by-side comparison of the two approaches. Maybe by analyzing these two examples and where they led, you can start to see what I’m saying about the two cognitive models.

And this brings me back to Perl. The slides I read mentioned Moose, an object model module for Perl. It is rich: supports inheritance, role composition, privacy, coersion, and many other tools. I think an OO system needs to have these tools: the OO world view counts on data having many facets, capabilities, constituents, and concerns itself with what is possible when you know about certain ones. An OO programmer must be an expert at creating data with many facets, capabilities, and constituents. This is contrasted to functional programming where everything is known about the data, and the focus is on manipulating it.

Haskell has no support for these tools. Its type system, although powerful, is too static. Haskell provides too many guarantees for OO to work; it wants to know too much about what’s going on. Similarly I don’t consider C++, Java, C# to be “powerful” OO languages. In fact, I might go so far as to say a language with static types and OO is not properly embracing the philosophy. You’re creating rich, smart data. If your superclass guaranteed that a particular method was const, i.e. does not change the object it was called on, how are you supposed to smartly cache the results of that function? Well, with the mutable hack. But that’s a hack, essentially telling the type system that it should go take a hike because you know what you’re doing.

Perl and Smalltalk “get it”, in my opinion. They have simple models, but provide tools for looking inside and changing data on the fly. They are about creating and manipulating smart data, leaving the guarantees up to the naming of the methods and their intended use, because trying to force guarantees would restrict their ability to be smart. If you want guarantees, use Haskell; it will almost prove your code is correct for you. But Haskell has no smart data, that’s the only way it can provide guarantees. You can’t have case analysis of data structures and objects that can reverse-engineer your function at the same time.

That’s it: when you’re in OO, don’t design functionally. Keep your guarantees wide open, and focus on making smart objects.

The Moment last Monday

Last Monday, “The Moment” (def: Nolan and whoever else) had a jam session at my house. I got my whole rig out, indicating this was a special occasion (first jam in more than a month).

  • 1 – Great funky track. It’s rough going now and then, but has some incredible passages, and is definitely listenable on the whole.
  • 2
  • 3
  • 4
  • 5
  • 6 – High energy rock/funk.
  • 7 – My favorite of the session. A trance track with nice vocals.
  • 8 – My “Charlie Hunter” moment (okay, that is an overstatement), playing a complex solo and bass at the same time :-)
  • 9
  • 10

The lineup:

  • Nolan McFadden – guitar, vocal
  • Willow – vocal, percussion
  • Will – drums
  • Luke – keyboard/bass

As the lineup implies, my left hand was on “bass” throughout the session. This was the first time I’ve had to cover the bass part, and I thoroughly enjoyed it (and it overloaded me, indication that I improved greatly that night).

How to play improv that doesn’t suck

Before we begin, a little shameless peddling: SNW was my band before it, er, disbanded. I consider that “improv that doesn’t suck”. If you think it sucks, then you probably won’t agree with my conclusion.

Two weeks ago I attended an open mic night at Cafe Babu, a fabulous musician-supporting cafe in Boulder. Interleaved between the scheduled acts were “open jam sessions”, where anybody who wanted to play could come up and play. Keyboardists being a rare commodity, I played in three of the four such sessions.

After more than a year of playing with excellent improvisers, it was extremely frustrating playing with these folks. Not because they weren’t good musicians—they were, they had good ears and a good sense of groove—but because nobody had musical control. The problem was that the music had the inertia of a freight train, and no matter how hard anyone pushed, it would not change direction. I will refine this statement to be more succinct by the end of the post, but in a good improv session, everyone needs to have control, simultaneously.

What I mean by this is that everyone needs to be looking at everyone else, watching and listening for ideas. Ideas are scarce in improv: because of the hypnotic nature of playing, music can continue on a good groove with no new content happening for many minutes. This makes it suck (ever heard the term “jam band” as derogatory? That’s what it’s referring to.). Music needs to change to make an impression, and if somebody wants to change it, you follow them. No matter if you like where it’s going or not, where it’s going is better than where it is.

Ears are more important than eyes. Especially when you’re around excellent musicians who often play with their eyes closed :-). So you listen for ideas and adapt to them. My personal philosophy as a musician assumes others are doing this: when I have an idea, I do it! No thinking, no testing the waters, no making sure that there is a nice transition or even that anybody is on board: just commit and go! If it doesn’t work out, well, you cross that bridge when you come to it.1 Other musicians take different tactics to success as well, this is just mine.

But if people aren’t listening, such riskiness will never work. That’s what I found at the open jam. I heard an idea (almost all my ideas come from hearing other people do things) and accentuated it, basically split off a new groove with whoever sparked the idea very coarsely, and nobody else did anything. Same ol’ thing. If I wanted it to stop sounding like noise, I had to shut up.

The best way to get the music to go somewhere new is to give someone control. You can force control on someone by making them solo. Not drum+bass+guitar solo, I mean guitar-only solo (or bass-only, or drum-only). As an extension to this rule, the more people playing, the less control anybody has. Or: the prowess of the musicians involved must increase quadratically with the number of musicians in order for the music to be coherent (each musician needs to be able to simultaneously listen and respond to each other). I explicitly restricted SNW never to grow beyond 4 members, since I didn’t believe that I had the prowess to handle 5.

But there is another way! If I can’t handle 5, there is an easy way to give the coherence of a session with 4. In the words of a favorite pop band, Cake: “Shut the fuck up!” Whaddya know, there are only 4 people playing again. The problem is that if you want it to be a 5 person jam session, one person can’t just refuse to play the whole time. Everyone needs to STFU, frequently. Listen to some Miles Davis fusion records, great improv. And then note the number of people listed on the album versus the number of people you can count playing at once. The ratio is around 3:1.

I am going to be organizing some jam sessions before I leave. And my preface will be just that: STFU. And ideally, you’ll get all numbers of musicians playing at once if you have a good distribution: 4,3,1,5, and (my favorite) 2. And if it’s really flowing for somebody, 6. :-)

But that’s it. Listen for ideas, give everyone control. If you don’t have enough control to introduce a new idea, shut the fuck up and endow your bandmates with more.

1 I have been working on incorporating such a mentality into my life outlook.

Making Twilight Imperium a bit less random

Twilight Imperium is a marvelous board game introduced to gamedev by Hagan Koopman (“King Koopman?”) some time ago. It is ridiculously complicated, has a 60 page dense rule book, and takes 15 hours to play if everybody already knows how to play. I used my roommates’ TI parties as an excuse to go on hikes with Jenn.

But after months of my roommates tirelessly raving about it, my interest was piqued and I played the next two games (you need one game to “get it”… quite a learning investment). And it is excellent. It’s plays as the strategy of every game you’ve ever played mixed into one: economics, politics, military, alliances, short-term deals, bidding, deception, pedantry. The complex social networks that emerge are something to behold.

But I have a problem with it: the combat sucks. You spend all this money and effort over many turns to build a massive army and decide to invade someone else’s space. And it comes down to dice rolls. Hundreds of dice rolls. There are some decisions to be made, but mostly they are trivial and can be described with an algorithm in half a page. You might as well be playing on a computer and say “resolve!” and it says “Luke wins!”. Combat! In a space warfare game!

Tonight at gamedev we did a tactical strategy game jam, and our group (Travis Offtermatt, Jude, and I) attempted to create an alternative that was more strategic. After some playtests, I think the game is quite a success. Fast-paced (by design, lest we yet lengthen this hideously long game), enjoyable, balanced, and quite in harmony with the outcomes of the dice if both players are playing at the same level (namely: noobs, since we just invented it).

It is played on a chess board, or any grid for that matter, with the TI combat pieces: Fighters, cruisers, destroyers, dreadnaughts, carriers, and war suns. Players begin on opposite sides of the board, and arbitrarily configure as many pieces as they like from their fleet in the two rows closest to them. Players take turns moving a single piece and then shooting with it if possible. After each turn a player may place more pieces from his fleet in the closest two rows.

Each piece has a “movement” attribute, which is the number of spaces that can be moved in a single turn. Movement is horizontal and vertical, not diagonal, not ever through a space that another piece is on, and backtracking is allowed. Furthermore, a piece is facing in the direction that it last moved; i.e. opposite the direction it came from. Pieces can only change orientation by moving, there is no in-place rotation.

Each weapon also has a range, which is the distance it can shoot. For range-1 weapons, the piece has to be directly horizontally or vertically adjacent, and also in the correct orientation. Things generalize naturally to more range: it has to be in the same line as the orientation of the weapon (which, for example for dreadnaughts, is not always the same as that of the ship). For example, fighters can only shoot in the direction they are facing, they can not move and then shoot in a different direction than they were moving.

Finally, war suns and dreadnaughts have an additional hit point. When you shoot one of these, it is turned on its side and continues to fight as normal. If you shoot one that is already on its side, then it dies. All the other pieces die immediately when shot. Shots can fire through friendly pieces without doing harm, but must stop and detonate at the first enemy piece on their path.

The characteristics of each of the pieces follow:

Unit Type Movement Weapons Hit Points
Fighter 2 Forward range 1 1
War Sun 1 3 shots, each to any space in the surrounding 5×5 square. 2
Cruiser 3 Forward range 1. Can shoot (once) at any time during motion, not just after motion 1
Destroyer 3 Forward range 1 or, once per battle (turn on side after this is done), an “anti-fighter barrage” that destroys all fighters in the 2×3 rectangle in front of the unit 1
Dreadnaught 2 Forward range 2 or on both left and right simultaneously with range 2 2
Carrier 1 Forward range 1 1

A few technical notes: since keeping units off the board can be a way to hide, if your unit gets to the other end of the board it may fire “off the edge” of the board to attack any of the pieces that are not yet in play. Further, it is only legal for any player to have 10 fighters on the board at a time, since that’s how many fighter pieces there are. The others must be kept off the board until some of the ones on the board die.

Enjoy your newly enhanced ludicrously long game!

Know any good GUI languages?

Recently an urge has been growing inside me. I have been wanting to play with graphical programming; I believe the age of textual programming is nearly over1, and I want to experiment with the next phase.

I’m asking for recommendations for languages or libraries in which to create this experiment. It’s purely an experiment, so experimental languages and environments are okay. Things along the lines of Squeak are okay (I don’t know smalltalk, but I was going to start researching it, until I realized that there might be something better I’ve never even heard of). Basically I want it to be a nice match for what I’m doing; I want it to be ridiculously easy to create a GUI (and I don’t care how it looks, so long as it does the right thing).

I’ll describe what I’m doing. My first experiment is a dependently-typed “environment”. I’m picturing bubbles floating around (could be boxes in a table, I don’t care) which are not organized in any linear fashion. These bubbles are tagged with a type and possibly a name, and they represent “I have an object of type t“. Arrow types are multi-parameter and look like this:

Visualization of an Arrow type

Where the things on the left are “important” parameters, the thing on the right is the return type, and the things on the bottom are “extra” or “implicit” parameters. And you can drag a bubble onto a parameter of an arrow to represent application, and to get a new curried composite bubble representing it. That’s basically the whole environment. What could I make that in?

1 The same way that C is an obsolete language today. :-)

Symphonic Poem no. 2

Here is the second in my series of symphonic poems. Still not happy with the ending, not because it’s not a good ending, but because it comes too soon. I want this piece to be about three minutes longer. I love it though, it is possibly my best work, so its length will probably push me over the edge on the 275th listen, and I will be forced to go back and add content.

When I finally arrange these poems into a “movement” structure, this will probably be the last one because of its high energy and strong, major key ending. I plan to write one more, which will be the first in the structure.

I began this piece about three weeks ago, and all in all it accounted for something like 35 hours of work. That is a rough estimate, I don’t keep track.

[score]

Isabelle you bitch!

I finally got Isabelle working. The installation instructions on the website make it seem simple. And it is. It’s just that many things can go wrong and they don’t account for them.

Here’s what I did: Got the source for polyml, built and installed it in /usr/local. Got the sources for Isabelle and Proof General (nothing prebuilt). Built Isabelle. But in Proof General’s makefile, it said:

EMACS=$(shell if [ -z "`which emacs`" ]; then echo xemacs; else echo emacs; fi)

I have both GNU Emacs and XEmacs installed, which means that EMACS got set to GNU Emacs. This was very confusing, since Isabelle started XEmacs anyway, but all the elc files were compiled by GNU Emacs.

I changed it to:

EMACS=xemacs

And all was well. Whew.

Now I get to see what all this Isabelle hype is about.

Session Types are cool

I just read a tutorial on Session Types. Session Types are a means for statically verifying a protocol between two (or with the new release, more) parties. It is what Erlang’s type system would be if Erlang had a type system.

The tutorial is very good, so I won’t belabor the point by reintroducing them here, but here’s a little teaser. Let’s say you have two processes, implemented like so:

process1 = do
    x <- recv
    y <- recv
    send (x + y)
process2 = do
    send 42
    x <- recv
    send (x + 1)

The session types library can verify at compile time that these two processes cannot talk to each other, since process1 is expecting to receive two integers but process2 only sends one before expecting to receive something.

Therefore, I conclude that Haskell is better than Erlang. Please ignore the fact that Haskell is missing the important things about Erlang (fault tolerance, hot swapping, total serialization). :-)

A quick glance at the automatically generated documentation for the session types library will cause you to go blind1. It is this kind of brilliant hackery which makes me really want a good dependently-typed language, since this kind of thing shouldn’t have to be brilliant hackery. It should be standard, everyday stuff.

1Oh, did you already click on it? I’m sorry, but I can deduce that you have since regained it.

Enumerating a context-free language

Here is a familiar context-free grammar for arithmetic expressions:

S      ::= add
add    ::= mul | add + mul
mul    ::= term | mul * term
term   ::= number | ( S )
number ::= digit | digit number
digit  ::= 0 | 1 | ... | 9

I have a challenge for you: write a program (in a language of your choice) which enumerates all strings accepted by this grammar. That is, your program runs forever, but if I have a string this grammar accepts, then your program should output it in a finite amount of time.

(This really is a fun challenge, so I encourage interested readers to try it themselves)

This is a tricky problem. Indeed it is sufficiently tricky that I cannot think of a clean imperative solution to it (which I’m sure is also related to being very out-of-practice in imperative programming). I’m interested to see any such solutions that people came up with. (And I’ll try it myself in the meantime)

But I’m going to present a functional solution using a neat little monad called Omega which I just uploaded to Hackage.

Let’s step back and consider a simpler motivating example. Consider the following list comprehension (and recall that list comprehensions are just the list monad behind a little bit of sugar):

pairs = [ (x,y) | x <- [0..], y <- [0..] ]

This looks like it generates all pairs of naturals, but it does not. It generates the list [(0,0), (0,1), (0,2), ...], so the first element of the pair will never get to 1. If Haskell allowed us to use ordinal numbers as indices then we could: pairs !! ω == (1,0). :-)

Conceptually what we have is a lattice of pairs that we’re “flattening” poorly:

(0,0)  (0,1)  (0,2)  (0,3)  ...
(1,0)  (1,1)  (1,2)  (1,3)  ...
(2,0)  (2,1)  (2,2)  (2,3)  ...
  .      .      .      .

We’re flattening it by taking the first row, then the second row, and so on. That’s what concat does. But anybody who’s had a brief introduction to set theory knows that that’s not how you enumerate lattices! You take the positive diagonals: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), .... That way you hit every element in a finite amount of time. This is the trick used to show that there are only countably many rational numbers.

Omega is the monad that comes from this concept. We define Omega‘s join to be this “diagonal” function. What we get back is a monad with a nice property:

If x occurs at a finite position in xs and y occurs at a finite position in f x, then y occurs at a finite position in f =<< xs

It’s hard to know what that means without knowing what =<< is supposed to mean. It means if you have a (possibly infinite) list of items, and to each one you apply a function which generates another (possibly infinite) list, and you merge them all together, you’ll be able to reach every result in a finite time.

More intuitively, it means if you write a multiple branching recursive function where each branch recurses infinitely (generating values), you will not get stuck in the first branch, but rather generate values from all branches.

And that is exactly what we need to write the context-free enumerator. Given a simple data structure representing a context-free grammar:

data Symbol a
    = Terminal a
    | Nonterminal [[Symbol a]] -- a disjunction of juxtapositions

Then we can write an enumerate function in a straightforward depth-first way:

enumerate (Terminal a) = return [a]
enumerate (Nonterminal alts) = do
    alt <- each alts          -- for each alternative
      -- (each is the Omega constructor :: [a] -> Omega a)
    rep <- mapM enumerate alt -- enumerate each symbol in the sequence
    return $ concat rep       -- and concatenate the results

But the Omega monad will do some heavy lifting and stagger those generators for us. Defining the grammar above:

arithGrammar = s
    where
    s      = Nonterminal [[add]]
    add    = Nonterminal [[mul], [add, Terminal '+', mul]]
    mul    = Nonterminal [[term], [mul, Terminal '*', term]]
    term   = Nonterminal [[number], [Terminal '(', s, Terminal ')']]
    digit  = Nonterminal $ map (map Terminal . show) [0..9]
    number = Nonterminal [[digit], [digit, number]]

And then running our enumerator:

runOmega $ enumerate arithGrammar

We get a very encouraging list of results:

0
1
0+0
0*0
0+1
(0)
1+0
0*1
0+0*0
00
...

Notice how each type of node is represented in that initial prefix. That’s a good sign that there won’t be degenerate repetitive behavior. But of course we know there won’t be by the guarantee Omega makes (unless I implemented it wrong).

Set Selectors

I am writing a poker game, and I got mildly annoyed when I went to write the hand classification functions. There was a disparity between the specification and implementation of poker hands; I had to come up with an algorithm to match each type. I didn’t like this, I want the code to match the specification more directly.

This is quite a geeky post. The types of poker hands are very unlikely to change, and the amount of time I’ve spent thinking about this problem already is many times that of solving it directly in the first place. I.e. it would be stupid for someone to pay me by the hour to solve it this way. Still, it gives rise to an interesting generalization that could be very useful.

I decided that the way I would like to specify these things is with “set selectors” over logical expressions. That is, given a finite set U, find a subset R of U such that some logical expression holds in R (i.e. all quantifiers are bounded on R).

This has a straightforward exponential time solution. I’m trying to do better.

I started by classifying logical expressions. In the following, let P(…) be quantifier-free.

  • \exists x P(x) is straightforward O(n).
  • More generally, \exists x_1 \exists x_2 \ldots \exists x_k P(x_1, x_2, \ldots x_k) is straightforward O(n^k).
  • \forall x P(x) is also O(n) to find the largest solution (because the empty set would satisfy it, but that’s not very interesting).
  • \exists x \forall y P(x,y) has an obvious solution, same as \exists x. P(x,x). There is no unique largest solution, but there is a unique largest for each x which can be found in O(n^2) time. It’s unclear what the library should do in this scenario.
  • \forall x \forall y P(x,y) is called the Clique problem and is NP-complete! Damn!

But the most interesting one so far is the case: \forall x \exists y P(x,y). It turns out that there is a unique largest solution for this, and here is an algorithm that finds it:

Given a finite set U, find the largest subset R such that \forall x \! \in \! R \, \exists y \! \in \! R \, P(x,y).

Let r_0 = U, r_{n+1} = \{ x \in r_n | \exists y\!\in\!r_n \, P(x,y) \}. That is, iteratively remove x’s from r that don’t have corresponding y’s. Then define the result R = \bigcap_i r_i.

Lemma. There is a natural number n_f such that r_{n_f} = R.

Proof. Follows from finite U and r_{n+1} \subseteq r_n.

Theorem. \forall x \! \in \! R \, \exists y \! \in \! R \, P(x,y).

Proof. Given x \in R = r_{n_f} = r_{n_f + 1}. Thus there exists y \in r_{n_f} = R such that P(x,y), by the definition of r_{n_f+1}.

Theorem. If R^\prime \subseteq U and \forall x \! \in \! R^\prime \, \exists y \! \in \! R^\prime \, P(x,y), then R^\prime \subseteq R.

Proof. Pick the least n such that R^\prime \not\subseteq r_n. There is an x \in R^\prime with x \not\in r_n. The only way that could have happened is if there were no y in rn-1 with P(x,y). But there is a y in R’ with P(x,y), so R^\prime \not\subseteq r_{n-1}, contradicting n’s minimality.

The time complexity of this algorithm can be made at least as good as O(n^2 \log n), maybe better.

While that was interesting, it doesn’t really help in solving the general problem (which, I remind myself, is related to poker, where all quantifiers will be existential anyway!). The above algorithm generalizes to statements of the form \exists w_1 \exists w_2 \ldots \exists w_j \forall x \exists y_1 \exists y_2 \ldots \exists y_k \, P(w_1,w_2,\ldots w_j,x,y_1,y_2, \ldots y_k). Each existential before the universal adds an order of magnitude, and I think each one after does too, but I haven’t thought it through.

In fact, I think that, because of the clique problem, any statement with two universal quantifiers will take exponential time, which means I’m “done” (in a disappointing sort of way).

Back to the real world, I don’t like that finding a flush in a hand will take O(n^5) time (16,807 checks for a 7-card hand, yikes), when my hand-written algorithm could do it in O(n). I’m still open to ideas for specifying poker hands without the use of set selectors. Any ideas?