Tag Archives: haskell

The “Whole Program” Fallacy

This StackOverflow question has generated a buzz of zealous reactions in the Haskell community. Here are the important bits of the question:

I often find this pattern in Haskell code:

options :: MVar OptionRecord
options = unsafePerformIO $ newEmptyMVar

doSomething :: Foo -> Bar
doSomething = unsafePerformIO $ do
  opt <- readMVar options
  doSomething' where ...

Basically, one has a record of options or something similar, that is initially set at the programs beginning. As the programmer is lazy, he don’t wants to carry the options record all over the program. … Now each part of the program has to use unsafePerformIO again, just to extract the options.

In my opinion, such a variable is considered pragmatically pure (don’t beat me). …

In this post I will give my own zealous reaction.

To ask a question like this assumes something about the nature of software. The assumption is hiding in these phrases: all over the program, each part of the program. Here, the poster assumes that a program is a large, monolithic beast such that every part of it will need access to this variable, and yet the definition of this variable is not known to the programmer. That means that the program depends on this value. If we purely model the structure of the above example program, we see that every function depends on OptionRecord. So we have (taking the context of a compiler):

parse :: OptionRecord -> String -> AST
compile :: OptionRecord -> AST -> LinkerObject
simplify :: OptionRecord -> AST -> AST
freeVars :: OptionRecord -> AST -> Set Variable
safeName :: OptionRecord -> Set Variable -> Variable -> Variable

These are perhaps not the cleanest signatures for parse, compile, and simplify, but they are conceivable in the real world. There is some junk — surely not all three of those functions depend on every option of OptionRecord. It would be cleaner to declare that they depend on exactly the things they actually depend on.

But the problem becomes much more unsettling at freeVars. freeVars takes an OptionRecord — staying true to the original problem description, it must, because it or a function it calls may end up depending options. But what on earth could a global OptionRecord determine about a free variables function? Perhaps there are multiple ways to find free variables — do we count type variables, what scoping mechanism to use — but those are not global options. Different functions will require different behaviors out of that function depending on what they are doing.

We even get such pathologies as shortestPath :: OptionRecord -> Graph -> Node -> Node -> [Node] — a plain, simple, reusable graph algorithm which somehow depends on this global options record. We have no way of telling the compiler — or, more importantly, ourselves — that this algorithm really has nothing to do with the specific compiler we are implementing. Somewhere deep in shortestPath‘s call chain, there is a call to some function which calls an error function which depends on one of the options. Suddenly this beautiful, well-defined function is not reusable. To take it out and use it in another project means to include OptionsRecord in that project, and OptionsRecord has things about compiler and type system extensions, configuration files, who-knows-what, but certainly having nothing to do with graphs. Sure, we can go and dig out the OptionsRecord, replace it with a record that is more suited to the program we are reusing the code in. But you have to go read, understand, mutate code that you just want to work please so you can get on with your project. We have all suffered the head-throbbing pain of integration problems. This is their source.

When I think of software as thousands of lines of specification for something, my mind jumps to problems like the original question. How am I going to write something so huge purely without it being really inconvenient? I see the need for global options, often global state, things ending with Manager (often a global trying to convince you it is a good abstraction), big systems talking about big ideas which are only applicable to my project.

But I have begun to think about software another way. Consider 100 lines. That is potentially a lot of information. The only reason 100 lines is not very much in the code world is because we lack the vocabulary to say what we mean. We are caught up in the details of manipulating lists of identifiers, building sorting trees, defining what we mean by “first” in this or that context. Could you describe your project in 100 lines of English? Perhaps not, but you could get a lot closer than with 100 lines of code.

I’m beginning to think that my latest greatest software project should be as small as possible. I need to build up vocabulary so I can describe it in a small space, but that vocabulary is not a part of my project. That vocabulary belongs to everyone in the same-ish domain of software. And nobody else cares about the meaning of OptionsRecord.

When I think of software this way, the idea that I need to pass around an OptionsRecord as a parameter to every function in my project starts to make sense. Every part of my project depends on its options, but my project is just a little thing that is standing on the shoulders of the giants of vocabulary used to get it there. I don’t mind passing options around between a few functions after I load them.

This is an ideal. I hope to move software closer to this ideal with my CodeCatalog project. Your current project probably cannot be phrased in a few hundred lines right now. But think about what it would look like if you structured it as a small main program + a lot of supporting vocabulary. Think of the supporting vocabulary as something any project could use. What does that mean for the modularity, reusability, and adaptability of your code? What does it mean for the clarity of your specification? What does it mean about the concept of “architecture”?

Flattr this

Searchable Data Types

A few years ago, Martín Escardó wrote an article about a seemingly-impossible program that can exhaustively search the uncountably infinite "Cantor space" (infinite streams of bits). He then showed that spaces that can be thus searched form a monad (which I threw onto hackage), and wrote a paper about the mathematical foundations which is seemingly impossible to understand.

Anyway, I thought I would give a different perspective on what is going on here. This is a more operational account, however some of the underlying topology might peek out for a few seconds. I’m no topologist, so it will be brief and possibly incorrect.

Let’s start with a simpler infinite space to search. The lazy naturals, or the one-point compactification of the naturals:

data Nat = Zero | Succ Nat
    deriving (Eq,Ord,Show)
infinity = Succ infinity

Let’s partially instantiate Num just so we have something to play with.

instance Num Nat where
    Zero   + y = y
    Succ x + y = Succ (x + y)
    Zero   * y = Zero
    Succ x * y = y + (x * y)
    fromInteger 0 = Zero
    fromInteger n = Succ (fromInteger (n-1))

We wish to construct this function:

search :: (Nat -> Bool) -> Maybe Nat

Which returns a Nat satisfying the criterion if there is one, otherwise Nothing. We assume that the given criterion is total, that is, it always returns, even if it is given infinity. We’re not trying to solve the halting problem. :-)

Let’s try to write this in direct style:

search f | f Zero    = Just Zero
         | otherwise = Succ <$> search (f . Succ)

That is, if the predicate worked for Zero, then Zero is our guy. Otherwise, see if there is an x such that f (Succ x) matches the predicate, and if so, return Succ x. Make sense?

And it seems to work.

ghci> search (\x -> x + 1 == 2)
Just (Succ Zero)
ghci> search (\x -> x*x == 16)
Just (Succ (Succ (Succ (Succ Zero))))

Er, almost.

ghci> search (\x -> x*x == 15)
(infinite loop)

We want it to return Nothing in this last case. It’s no surprise that it didn’t — there is no condition under which search is capable of returning Nothing, that definition would pass if Maybe were defined data Maybe a = Just a.

It is not at all clear that it is even possible to get what we want. But one of Escardó’s insights showed that it is: make a variant of search that is allowed to lie.

-- lyingSearch f returns a Nat n such that f n, but if there is none, then
-- it returns a Nat anyway.
lyingSearch :: (Nat -> Bool) -> Nat
lyingSearch f | f Zero = Zero
              | otherwise = Succ (lyingSearch (f . Succ))

And then we can define our regular search in terms of it:

search' f | f possibleMatch = Just possibleMatch
          | otherwise       = Nothing
    where
    possibleMatch = lyingSearch f

Let’s try.

ghci> search' (\x -> x*x == 16)   -- as before
Just (Succ (Succ (Succ (Succ Zero))))
ghci> search' (\x -> x*x == 15)
Nothing

Woah! How the heck did it know that? Let’s see what happened.

let f = \x -> x*x == 15
lyingSearch f
0*0 /= 15
Succ (lyingSearch (f . Succ))
1*1 /= 15
Succ (Succ (lyingSearch (f . Succ . Succ)))
2*2 /= 15
...

That condition is never going to pass, so lyingSearch going to keep taking the Succ branch forever, thus returning infinity. Inspection of the definition of * reveals that infinity * infinity = infinity, and infinity differs from 15 once you peel off 15 Succs, thus f infinity = False.

With this example in mind, the correctness of search' is fairly apparent. Exercise for the readers who are smarter than me: prove it formally.

Since a proper Maybe-returning search is trivial to construct given one of these lying functions, the question becomes: for which data types can we implement a lying search function? It is a challenging but approachable exercise to show that it can be done for every recursive polynomial type, and I recommend it to anyone interested in the subject.

Hint: begin with a Search data type:

newtype Search a = S ((a -> Bool) -> a)

Implement its Functor instance, and then implement the following combinators:

searchUnit :: Search ()
searchEither :: Search a -> Search b -> Search (Either a b)
searchPair :: Search a -> Search b -> Search (a,b)
newtype Nu f = Roll { unroll :: f (Nu f) }
searchNu :: (forall a. Search a -> Search (f a)) -> Search (Nu f)

More Hint: is searchPair giving you trouble? To construct (a,b), first find a such that there exists a y that makes (a,y) match the predicate. Then construct b using your newly found a.

The aforementioned Cantor space is a recursive polynomial type, so we already have it’s search function.

type Cantor = Nu ((,) Bool)
searchCantor = searchNu (searchPair searchBool)

ghci> take 30 . show $ searchCantor (not . fst . unroll . snd . unroll)
"(True,(False,(True,(True,(True"

We can’t expect to construct a reasonable Search Integer. We could encode in the bits of an Integer the execution trace of a Turing machine, as in the proof of the undecidability of the Post correspondence problem. We could write a total function validTrace :: Integer -> Bool that returns True if and only if the given integer represents a valid trace that ends in a halting state. And we could also write a function initialState :: Integer -> MachineState that extracts the first state of the machine. Then the function \machine -> searchInteger (\x -> initialState x == machine && validTrace x) would solve the halting problem.

The reason this argument doesn’t work for Nat is because the validTrace function would loop on infinity, thus violating the precondition that our predicates must be total.

I hear the following question begging to be explored next: are there any searchable types that are not recursive polynomials?

Did you like this post? Flattr this

Programming for a culture approaching singularity

In 2001, Ray Kurzweil published his inspiring, controversial essay The Law of Accelerating Returns. I acknowledge that the essay sometimes seems far-fetched, and perhaps some details are overly (or underly) idealistic, but in essence I find it very convincing. I will take it as an assumption for this article, and I also assume my readers are familiar with the gist of the essay.

I read Kurzweil’s essay about six weeks ago, and it has set off a chain reaction in my consciousness, causing me to reconsider my perceptions of technology. At first, it seemed to murder my denotational idealism, destroy my hopes of Dana (my purely functional operating system). It filled me with an excited fear, as if I were being carried down the rapids of a great river, trying not to hit the next rock.

Now the ideas have settled and my idealism is born again with a new perspective. The spirit of Dana still has a place, and I will describe what I think that is.

We are at a unique inflection point in the process of technological acceleration. In the last 50-100 years, orders of magnitude of progress began to occur in a single human lifetime. Technology is folding upon itself, each new invention making use of more and more recent knowledge and tools.

Dana was originally envisaged to facilitate this growth by observing that the vast majority of software out there is not compositional, thus we are re-inventing many wheels. Dana’s goal was to provide a framework in which everything must be compositional. But my early execution of the idea was misguided. It may have had a noble goal, but I was pretending that I was at the beginning of an acceleration of software, not the middle. Dana’s implementation did not make use of modern technology, and thus its development was an order of magnitude or two slower than the rate of modern software’s development. Further, its despotic purism would never catch on: it was trying to change the direction of an avalanche by throwing a snowball.

A truly modern compositional environment must embrace the flow of knowledge. Those who try to reverse the paradigm will end up reinventing all the technology that the mainstream is already using, and by the time they are finished the mainstream will be lightyears ahead. The state of the art may be ugly, but it exists, which is more than the purists can say. One person — one team — cannot develop software anymore; to do something new, we must employ the labor of the entire world.

Currently, the most constraining property of software is that for it to be reusable, it must be designed for reuse. It is hard to reuse libraries in a way for which they were not intended. And in fact most of the coding that goes on is not in libraries at all — people aren’t intending their code to be reused by anyone. They just want to get their product out the door and get some cash flowing in. Below is a reified mental picture of this.

The state of progress in reusable software

The bulb on the bottom is the software designed for reuse. It grows slowly and uniformly, mostly occurring in the open-source world, created by people who like to write good software. The rays at the top are individual, result-oriented projects. This code is not typically designed to be reused. These projects grow quickly in a single direction, but if someone else wants to go in a similar direction, they have to start at the bottom. This is an economic phenomenon, and the economic goals of developers are not likely to change.

To accelerate progress, we must find a way to re-use those chutes, the goal being to transform the picture into something more like this:

In this picture, each results-oriented chute carries with it a net of all the support code that was written for it, upon which anyone can build. Of course only with the consent of the creator (people will find a way to protect their information), but if it is useful, then people will buy it.

I have thus become a supporter of Donald Knuth’s mantra:

I also must confess to a strong bias against the fashion for reusable code. To me, “re-editable code” is much, much better than an untouchable black box or toolkit.

Forking a project in order to use one of its features in another project is no simple task. Depending on the complexity of the feature, you might gain some time by doing things this way, but many competent software engineers prefer to simply rewrite from scratch. One reason is in order to understand the code, but another is simply economics. Saying that I rewrite features because it is fun is missing half of the equation. I rewrite features because it is more fun then spending a week fighting integration issues (very much not fun). I claim that to support this new picture, our primary goal should be to vastly reduce integration issues.

Here is where my purist ideals kick back in, having found a new purpose. Pure functions have no integration issues, at least semantically speaking (performance is always a bit more subtle). A pure function makes explicit all of its inputs and outputs, so to use it, you can just rip it out of its context, provide the inputs, and transform the outputs. While depending on the situation that may be a lot of work, compare it to finding all the places a singleton was modified in order to recreate its state at some point in the execution of the program. What if the singleton returned a reference to an object that was stored away and modified by an obscure corner of the program, upon which your feature later depended. This sounds like a terribly inflexible design, but most software is terribly designed, and we still want to reuse it.

However, just saying “use pure functions, voila!” is no solution. The trend of the world is gradually shifting toward more functional idioms, but asking everyday programmers (who we care about, because they are doing our work for us) to switch to purity is asking a lot. Retraining brains is too hard.

So that is my open research question. How do we introduce the immense advantage of purity from this perspective into programming pop culture? Perhaps it is a new virtual machine, that does dynamic dataflow analysis. Perhaps it is a static analysis tool. Perhaps it is a new language, which can interface with many popular existing languages. This would be slow to take off because it requires migration (thus risking never), but because of interop and the good reuse properties (with tool support) it might be faster to achieve critical mass. Clojure and Scala are doing kindof okay.

Once you have a way to track assumptions, the rest follows easily. It would be possible to assemble a database of every function ever written, with the ability to just drag and drop it into your program (ehem, Haskellers, why don’t we have this?). The natural version control system, another step in the direction of the DVCSes, tracks changes between individual objects, and how those changes induce changes in the objects that reference them (this is the part I have thought through the most, but I will forgo describing it for it is a small detail and this post is already very long).

A singularity-aware culture should keep its eye on a way to bring the next inevitable order of magnitude of progress. I believe the elimination of integration issues is one such way, and Haskell, for the most part, has already eliminated them. The first step is to bring this property to the popular languages in any way we can (this includes making a Haskell a popular language… LOL).

Did you enjoy reading this article? Let me know! :-) Flattr this

Haskell’s Big Three

As my regular readers know, I am a zealous Haskell advocate. After many years of programming in many different languages, Haskell has secured itself as my #1 language for almost every problem: using any other is like painting with a mop — like playing tetris without being able to rotate your pieces. Nonetheless, Haskell has some unsightly areas, especially when considering programming in the large. The more I use Haskell to tackle big problems, the more obnoxious they become. This post is my account of Haskell’s Big Three annoyances. Contrary to my usual shtick about cutting out features because fewer features means more properties, these are missing features. The order in which I list them is meaningless.

1. No Module Abstraction

Some of the code I am writing for Evo (purely functional RTS game), if stated in full generality, would look like this:

gameUI :: (RealFrac time, Image image, Causal causal) => UI time image causal () ()

The first three parameters are constant throughout my entire program. I can’t in my right mind make a data type with 5 type parameters, and I certainly refuse to write those same three constraints on every function involving UI. So, sacrificing generality, I have fixed those three parameters to the particular choices I need for Evo. But suppose this module were to be reused — by fixing my choice of, eg., image to Graphics.DrawingCombinators.Image, I have disallowed the reuse of this module by any program that uses another library for drawing. But I stand by my aesthetic choice, so that I don’t obscure my code’s inner beauty behind repulsive, indecipherable type signatures.

Haskell needs some form of abstraction over modules. ML functors, Agda modules (aka. awesome records), Coq sections — any way to abstract over more than one definition. This would allow module authors to make their code clean and reusable at the same time.

2. Module Naming Policy

Hackage is a mess. I cringe looking at vector-space, taking up 9 valuable top-level names (“Data.” doesn’t count, everybody uses that), preventing anyone else from naming a module or module suite named Data.Cross or Data.Derivative (the latter I actually have a candidate for). data-object for JSON objects, as if nothing else could concievably be called an object. transformers and mtl both have a module named Control.Monad.Trans, preventing both versions from being used from the same package (suppose this package depends on two other packages, each of which depending on a different monad library).

The quick fix, what every other language has done, is to institute a policy or culture of naming conventions that makes the probability of collision low. I feel like Hackage is nearing its limit — the ad-hoc Data.Blah naming conventions won’t last through another order of magnitude. If we encouraged people to name packages more conservatively, we may last through one or two more.

But a naming convention is just delaying the inevitable, giving us a false sense of security. What happens when a package is forked, two packages come to depend on two different branches of this package which forgot to rename itself, and a third package wants to depend on both of those? We need something innovative, and in Haskell’s spirit! Let’s allow the flexibility in package names that we allow in symbol names from imports now — if there is a name collision, just rename one of them for the scope of your package. No big deal. Let module authors name their modules whatever they think is clearest — go ahead, name your module Monad, we don’t care. Right now, a name like that would be a death sentence for that module due to impoliteness.

3. Unrefactorable Typeclasses

The Haskell prelude is a very nice place, in general (what, you haven’t read it? Go, it’s a nice read!). However there is one cesspool of which every experienced Haskeller is ashamed: the Num class. Let’s look:

class  (Eq a, Show a) => Num a  where
    (+), (-), (*)    :: a -> a -> a
    negate           :: a -> a
    abs, signum      :: a -> a
    fromInteger      :: Integer -> a

(+) and (-) almost surely belong, as does fromInteger (supposing you don’t allow more flexibility with numeric literals a la IsString). (*) might be considered reasonable, though we have just disallowed vectors as instances of Num. abs and signum… well I guess as long as you’re putting in (*) those make sense. But the superclasses Eq and Show, especially Show, what? What about being a number involves being convertible to a string? Eq and Show both disallow computable reals from being a bona fide instance of Num, they have to cheat. Same goes for notational extensions like f Int where f is any applicative functor.

The Num class is pretty bad, but I excuse the Haskell designers for making that mistake. Library design is hard, especially when you have never used the langauge you are designing the library for. The weakness in Haskell is much deeper: we are stuck with this cruft because any attempt to change it would break all sorts of code everywhere. Num isn’t the only class affected, it is just the most public example. Any module which defines a typeclass and allows users to instantiate it suffers from this problem. As soon as the typeclass is defined, it may no longer change. You are stuck with that decision forever, or else you break backwards compatibility.

Ultimately what we would like to do is split Num up into algebraic structures like Group (with (+), (-)), Ring (with (*)), etc. There is a simple, conservative proposal that could solve this problem, which essentially would allow us to say:

class alias Num a = (Eq a, Show a, Field a, IsInteger a)

Which would allow all four of those typeclasses to be instantiated in one go, thus treating the collection of four as one, and allowing us to introduce finer granularity in the Num typeclass without breaking everything. GHC has implemented all kinds of crazy extensions, and this seems tame in comparison. I wonder what is preventing it. (Maybe I should get into some GHC hacking?)

I have identified further typeclass modularity problems could be solved by a more radical suggestion: outlaw orphan instances. But that fight is for another day.

Conclusion

I consider Haskell to be by a wide margin the prettiest practical language in existence. Haskell code in the small is often perfect to my eyes, “from the book” as Erdös would say. Each of these suggestions is about improving Haskell code in the large. They allow the incremental creation of a perfect module, a perfect package, a perfect typeclass. We are closer than we think to a language in which an entire program could be considered perfect.

I wrote this article to emphasize these features, open them to active discussion and critique, and entice their implementation. What do you think, are they worth the effort?

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.

Haskell Antipattern: Existential Typeclass

I have observed pattern of design emerging in various Haskell libraries, for example vty-ui, GlomeTrace, and XMonad. Here is an excerpt from vty-ui’s interface. The snippet is long but simple, and I need all of it to demonstrate my point.

class Widget w where
    render :: DisplayRegion -> w -> Image
    growHorizontal :: w -> Bool
    growVertical :: w -> Bool
    primaryAttribute :: w -> Attr
    withAttribute :: w -> Attr -> w
mkImage :: Widget a => Vty -> a -> IO Image
data AnyWidget = forall w. Widget w => AnyWidget w
data Text
data Box
data Fill
instance Widget AnyWidget
instance Widget Text
instance Widget Box
instance Widget Fill
text :: Attr -> String -> Text
hBox :: (Widget a, Widget b) => a -> b -> Box
vBox :: (Widget a, Widget b) => a -> b -> Box
hFill :: Attr -> Char -> Int -> Fill
vFill :: Attr -> Char -> Fill

This module models the concept of a GUI widget. It defines a class with a basis of operations on Widgets, and then instantiates a few data types into the class. To facilitate passing around arbitrary widgets instead of specific instances, it provides an AnyWidget class. This Any* class is the tell-tale sign of this antipattern.

When I was using the above interface, I found myself immediately wrapping the results of text, hbox, and the other combinators in AnyWidget. By throwing away the information of exactly what instance of Widget it was I lost nothing, all the same operations were available to me. Astute readers might notice that withAttribute is an exception, because it has a w to the left and to the right of an arrow, so if I pass it a Box, I know I will get a Box back. But I cannot use that knowledge for anything else, so it doesn’t buy me anything.

There is a simpler and more direct way to encode the same thing. Here is the interface I would have written to this library:

data Widget = Widget {
    render :: DisplayRegion -> Image,
    growHorizontal :: Bool,
    growVertical :: Bool,
    primaryAttribute :: Attr,
    withAttribute :: Attr -> Widget
}
mkImage :: Vty -> Widget -> IO Image
text :: Attr -> String -> Widget
hBox :: Widget -> Widget -> Widget
vBox :: Widget -> Widget -> Box
hFill :: Attr -> Char -> Int -> Widget
vFill :: Attr -> Char -> Widget

I know just from looking at the types that all the code in the module could be converted to this style. Every operation has the exact same assumptions as in the old version, and all the extra guarantees that the old one provided were useless because they were never used as assumptions. Plus, you don’t have to wrap every call to a combinator with AnyWidget. By exposing the constructor for the Widget type, it gives users the same opportunity to make custom Widgets as the class interface gave.

You might be thinking, “but what if somebody else made a widget type which did use the additional assumptions that the separated data types provided, for example,

data Window
instance Widget Window
window :: Widget w => (Int,Int) -> w -> Window
windowSize :: Window -> (Int,Int)
adjustSize :: (Int,Int) -> Window -> Window

“Haven’t we just excluded this possibility from the interface?” Turns out that we have not; just replace the instance with a function:

toWidget :: Window -> Widget

See how this is going? Classes become data types, instances become functions. I’m just manually “expanding” what GHC does for you. Of course, the expansion is smaller than the original.

I advocate a direct programming style in Haskell. Advanced type system features have their place, but plain old functions go a long, long way. Functions are the masters of reuse: when you use an advanced feature, you need a yet more advanced feature to abstract over it (think: classes < existential types < universally quantified constraints < unknown). But all you need to abstract over a function is another function.

Beliefs and the Unimpossibility of Functional Reactive Programming

Behaviors must be first class — this is a belief I have held for almost my entire tenure as an FRP researcher. The belief originated about two weeks after I learned of FRP, when I wrote my first FRP Arrow and in it tried to write a small game. The process was awkward; not as clean and natural as what I had dreamt of for the paradigm. The awkwardness arose when trying to wrangle a time-varying list of time-varying enemies. I concluded that Arrowized FRP (AFRP) was terrible at managing dynamic collections of behaviors, and therefore that an FRP system needed dynamic collections to be powerful enough to do nontrivial things.

Only half of my conclusion was justified. AFRP is indeed terrible at managing dynamic collections of behaviors. But I never questioned the latter half. It epitomizes what Conal Elliott calls “proof by lack of imagination”: since I couldn’t devise a way to write my game without dynamic collections, there must not be a way.

Conal and the rest of the FRP gang has been discussing the semantic junk in classic FRP. Clearly there is more (or rather, less) to an interactive Behavior than an arbitrary function between two non-interactive ones. This identified, my mind immediately jumped to Arrows. That is what they are for: function-like things that can’t do quite as much as regular functions.

And for some reason — perhaps it is my increased functional maturity — I feel no need for first-class behaviors anymore, no awkwardness for their lack. Programming with them doesn’t feel like the rest of functional programming. It feels too open-ended; i.e. I can say too much in the code without saying it in the type. I feel now like Arrows are a perfect fit for FRP. And fortunately, we already have an efficient AFRP implementation. It’s not a great implementation — there are semantic and operational details that could be improved, but it is something to start from, which is more than I had before.

I don’t blame myself for temporarily believing that we needed first-class behaviors. But I am disappointed in myself for taking so long to question that belief. FRP was my world. I was determined to understand it and to make it a practical alternative to Haskell’s IO. But I ended up blatantly ignoring half of the ongoing research because I didn’t believe it would work. This is not acceptable for a serious researcher.

The perfect way is only difficult for those who pick and choose.
Do not like, do not dislike; all will then be clear.
Make a hairbreadth difference, and Heaven and Earth are set apart.
If you want the truth to stand clearly before you, never be for or against.
The struggle between for and against is the mind’s worst disease.
— Zen master Sent-ts’an

New Year’s Resolutions: Produce, Believe

I bring you two personal experimental hypotheses for 2010.

I am a Haskell module author. Constituting my released modules are those ideas which resisted the least when I opened the text editor. But two of them, data-memocombinators and graphics-drawingcombinators have gained some popularity, and I am feeling rewarded having written them.

Most of my ideas functionalize pieces of Haskell programming that are currently imperatively-minded, as you can see with the two aforementioned. But FRP, a particularly greedy such idea has been stealing my tuits away from the others. I have envisaged functional command lines, package management, event handling, persistence, testing, and probably more that presently slip my mind. This brings me to my first new year’s resolution for 2010: Produce! It’s time to start coding these up instead of letting one very hard problem block the solution of moderately hard ones. Kicking off the year, I rewrote graphics-drawingcombinators to have a stronger semantic foundation, becoming version 1.0.0 (thanks Peaker and sinelaw for egging me on!).

My second resolution addresses an irrational fear I noticed a few days ago. The story begins with Hubris Arts, the game studio my friend Max and I started in July. We released our first game in November. We are in development on our second (codename “R4″) and prototyping our third (codename “Evo”). All of our development so far has been in C# with XNA, for a familiar reason: it was the path of least resistance. But as I prototype Evo I see all my beloved functional design patterns leaping out at me from between the lines of imperative blasphemy. So far the implementation seems a great fit for Haskell, but I am uneasy. Some part of me doesn’t believe that Haskell can do it. Haskell’s role in my life so far has been that of a language for beautiful koans and interesting experiments, but not for Real Software. But why not? My only evidence is my own fear.

Thus the second resolution: Believe in Haskell! I have decided to do Evo in Haskell. It is only by tackling Real Software that a language matures — it may not be ready now, but by doing it anyway, we will make it ready. If we can do it, that will be a wonderful success for the language, perhaps permanently parting us from C# von Neumann’s clutches. If we can’t, at least we’ll have reasons why not — ideas for things to improve — instead of unsupported uneasiness and unconfidence.

IO-free splittable supply

I know it has been a while since I posted, and I’m sorry to say this isn’t a terribly deep or interesting one.

I like the value-supply package on hackage. It takes (essentially) an infinite list of things and arranges them into an infinite tree randomly… but a particularly useful kind of random. The first one you look at just happens to be the first element of the list, the second one you look at comes from the second element, etc.

This sort of magic isn’t useful for its magic, it’s just useful because you can use something like Int and not run out of bits too soon. All I ever use it for is unique labels in computations that would be made too strict by the state monad. As a contrived example of such a computation:

    allocateLabel :: State Label Label
    
    labelList :: State Label [Label]
    labelList = liftM2 (:) allocateLabel labelList

    bad :: State Label [(Label,Label)]
    bad = liftM2 zip labelList labelList

The problem is that we don’t know what label to start with on the second labelList in bad… we never finish using them up in the first one. But if all you care about is uniqueness of labels, rather than their order, this computation is easily definable as a function of a Supply from value-supply:

    labelList :: Supply Label -> [Label]
    labelList sup = let (a,b) = split2 sup in supplyValue a : labelList b

    good :: Supply Label -> [(Label,Label)]
    good sup = let (a,b) = split2 sup in zip (labelList a) (labelList b)

Great. Only problem is, we can only make Supplys from the IO monad. As it should be, since the supply uses a nasty form of nondeterminism to assign elements to its trees.

But, if all you care about is uniqueness, which is the case for me more often than not, you can squash IO out of the interface (not the implementation, unfortunately). Like this:

    runSupply :: (forall a. Eq a => Supply a -> b) -> b
    runSupply f = f (unsafePerformIO (newSupply 0 succ))

In my opinion, this is the best possible interface for such a thing. Value-supply is only to be used when all you care about is uniqueness, not ordering or the precise values. Well, this interface encodes that exactly. When you use this function, all you are allowed to care about is uniqueness, any other concern is hidden behind the type system. It is also impossible to confuse indices from different supplies.

And this is a perfectly well-behaved function. You could demonstrate that by giving a pure implementation of Supply [Bool] (which just traces the path to the given leaf from the root). The unsafe business is merely an optimization (and for some use cases, like labelList above, a very potent one).

Hooray. I get my favorite evil module, with all of its evil safely contained in a jar that they call a box for some reason.