Monthly Archives: February 2010

Life and Projects

I just lost my job. This happening was unexpected except to the deep knowledge of my subconscious, who, for the last week, has been practicing what to say when it happened. The reason is that my “level of productivity is not sufficiently high to justify [my] contract rate”. I agree with this, and although the whole thing has got me feeling a tad worthless, I am not beating myself up about it. The project was less familiar territory than I had expected, being of primarily object-oriented design (rather than functional — and yes “functional design” is a real thing). I have done a lot of OO programming in my day, but since I have started functional programming, my OO code never seems good enough. I now spend a good proportion of my time searching for cleaner, smaller, more obviously correct solutions, when the code that I am criticizing would have been just dandy 5 years ago.

Anyway I won’t blather on anymore justifying why I am still a good programmer nonetheless. This post is about the future.

In any case, I feel like the event woke me up. I was spending my 25 hours working on a project I didn’t really care about (despite it being fun and working with good people), a few hours a week on my own projects, and the rest of the time on who-knows-what. Chilling out, wasting time on the internet, watching netflix, getting high and playing the piano. It’s all a fine, relaxing lifestyle, but I am disappointed that I was spending so little time on my projects. So, I resolve to spend no less time working than I was before — at least 30 hours per week, all for my own goals.

For my own clarity, and for the interested, here is what I’m working on:

  • Evo (codename), a “serious” real-time strategy game written in Haskell, with my friend Max. The purpose of this game is twofold: (1) to be a ridiculously fun real-time strategy game (nothing good has come out of that genre for a few years) and (2) to prepare and exposit Haskell as a game development platform. Perhaps it is yet another attempt to solve my 6 year old thesis Game Programming is Too Hard.
  • Vatican, a lazy specializing interpreter, taking after the work of Michael Jonathan Thyer’s dissertation. This is largely a research project, in which I would be happy to get 1% of the performance of GHCi — just something to start from. Here is the repository.
  • An experimental programming language with a unique view of types: types are just properties (eg. “f :: Int -> Int” is another way of saying “for all x, if x is an Int then f x is an Int”). The language is essentially an untyped lambda calculus, but comes with a proof language in which the usual types and many more sorts of properties can be expressed and verified. There is some (mechanism as-yet undecided) macro facility that allows traditional type inference to be encoded as a macro in the language. There are a lot more ideas for this language floating around, but I am trying to stick to the principle “everything it does, it does perfectly”, so I’m holding off on new features until I know exactly where in the picture they appear.
  • I will consider blogging as officially one of my projects, to continue improving my writing. I am converging on a functional design methodology, my antipattern post hinting at its direction. But the feedback I’ve received on that post makes me realize that the argument and the details are not yet clear. I’d like to keep writing about it and exploring this methodology in order to one day pin it to rigorous principles.

30 hours a week of the above, or projects that the above evolve into. I don’t need to be a pedant: I know when I am and am not being productive.

Get up in the morning, work all day. –Philip Glass

Associative Alpha Blending

I recently revamped my graphics-drawingcombinators module to have a handsome denotational semantics. I may write a post going into full detail later, but the executive summary is that Image a = R2 → (Color, a). Due to TCM, I get semantics for Image’s Functor instance from this, and if Color is a monoid I get the semantics for the Applicative and Monoid instances as well. OpenGL combines colors by alpha blending, so I happily defined my monoid instance as alpha blending:

 mempty = Color 0 0 0 0
 mappend c@(Color _ _ _ a) c' = a*c + (1-a)*c'

It doesn’t take a genius to see that this violates two of the three monoid laws (the only one it satisfies is left unit: mempty `mappend` x = x). This is embarrassing. My new rigorous denotational semantics has a pretty awesome flaw.

To make this right, let’s redefine Color not as something which is drawn, but as a transformation on alpha-free colors. I do this because functions make great monoids: composition is always associative and identity is always a unit. But it’s not just any function, it’s an alpha blending function. So we say that f is a “Color” if there exists constants a and x such that f(c) = a x + (1-a) c, which I will write as f = [a; x]. Here a is a scalar and x is another alpha-free color like c. We would really like it if the composition of two Colors were also a Color. Let’s try:

f(g(c)) = [fa;fx]([ga;gx](c))
        = fa fx + (1 - fa) ([ga;gx](c))
        = fa fx + (1 - fa) (ga gx + (1 - ga) c)
        = fa fx + (1 - fa) ga gx + (1 - fa) (1 - ga) c
        = fa fx + (1 - fa) ga gx + (1 - fa - ga + fa ga) c
        = (fa fx + (1 - fa) ga gx) + (1 - (fa + ga - fa ga)) c

It looks like the “alpha” of our composition is (fa + ga – fa ga). Let’s call this a’. Now we have to get the left side of the addition into the form a’ r for some r. Let’s just hack it: multiply and divide1 by a’.

        = a' (fa fx + (1 - fa) ga gx) / a' + (1 - a') c

And then we can read off the answer:

[fa;fx] . [ga;gx] = [a' ; (fa fx + (1 - fa) ga gx) / a']
   where a' = fa + ga - fa ga

For the identity, we need:

a x + (1 - a) c = c

Which is satisfied for a = 0 with x = anything, so we can use [0,0].

Because we derived this from composition and identity, the laws must hold. The mathematically untrusting may wish to check this.

And there you have it: my new Color monoid which actually satisfies the laws. This is the way to compose alpha-blended colors — it reflects what happens if you draw one after the other, blending as you go. This is the math that pre-blends any segment of that sequence.

I should have known that OpenGL’s colors were transformations all along, since the color of an object that you see can depend on the color you used to clear the screen.

1 But what if (fa + ga – fa ga) = 0? Fortunately, the only place this happens when these variables are between 0 and 1 is fa = ga = 0, which means both f and g are the identity color.