Tag Archives: code

Information Economics















Announcing CodeCatalog

I’d like to share what I’ve been working on instead of homework for the past month: codecatalog.net. From the FAQ:







Designing with Interfaces

In this post I will share a personal discovery about object-oriented design. It is so simple and obvious that it may not be news to experienced OO programmers. However, it should be noted that before I became a Haskell nut, I was a dedicated OO programmer for 7 years. I occasionally empolyed the pattern in my designs without realizing its full generality. So it may yet be news to you vets.

I came across it when exploring the consequences of my recent post, Encapsulation Considered Harmful. I was trying to design a concept language around the idea, and realized that the language design I kept coming back to could be mostly encoded in existing languages.

Here’s the rule: never reference a class directly — always go through an interface. This includes creating new objects — go through a factory interface or take it as a parameter instead.

Obviously this rule cannot be followed 100% because you’ve got to give a concrete instantiation at some point. But push that as far “up” in your program as possible. Also, doing this 100% in contemporary languages would probably involve too much boilerplate. That’s okay, it can be done piecewise, and many of its advantages can still be reaped if it is done partially.

We have recently done this refactor on our game, and I have to say, it is gorgeous! I really like the clean, uniform way it separates concerns. More importantly, it is an abstraction instead of an encapsulation mechanism. That means that when code doesn’t depend on a particular detail, you can always substitute something else for that detail. Keep that property in mind, it will guide you in applying this pattern correctly.

Here is a simplified example from our game. We used to have a class FileSystem to access the filesystem. ProgressResult<T> was a class that monitored the progress of loading a file from disk and yielded a T when it was finished. Unit is the trivial type: struct Unit {}.

class FileSystem
    ProgressResult<List<string>> List();
    ProgressResult<byte[]> Load(string filename);
    ProgressResult<Unit> Save(string filename, byte[] bytes);

And in our World class, a class for the main game interface, we used it like so:

class World
    FileSystem filesystem;
    public World(...) {
        filesystem = new FileSystem();
    // using methods on filesystem here

After applying this pattern, it becomes:

interface IProgressResult<T>

interface IFileSystem
    IProgressResult<List<string>> List();
    IProgressResult<byte[]> Load(string filename);
    IProgressResult<Unit> Save(string filename);

class FileSystem : IFileSystem { /* as before */ }

class World
    IFileSystem filesystem;
    public World(IFileSystem filesystem) {
        this.filesystem = filesystem;

See how we avoided creating a filesystem in World, and instead took it as a parameter? World is now more flexible than it used to be: we can (and did!) instantiate it with a disk filesystem and an Amazon S3 filesystem. They have different sorts of ProgressResults too, thus that is also an interface.

Now, if you go to apply this pattern in your project, you might find that it breaks down for more complex designs. It’ll do that if you aren’t precise about your phrasing. For example, in another part of our project we had the following combinator library for our UI:

class UI 
    public static UI Over(UI over, UI under) { ... }
    public static UI VerticalGroup(params UI[] uis) { ... }
    public static UI Window(string title, UI contents) { ... }
    public static UI Button(string text, Action onClick) { ... }
    // some non-static members for inspection

To abstract over these implementations, we need to promote these static functions into methods on a factory-like interface. It may seem that this is the way forward:

interface IUI { /* the non-static members */ }
interface IUIModule 
    IUI Over(IUI over, IUI under);
    IUI VerticalGroup(params IUI[] uis);
    IUI Window(string title, IUI contents);
    IUI Button(string text, Action onClick);

But this is not the way. Imagine if you were to construct some IUIs with a SilverlightUIModule and then try to combine them (with, say, VerticalGroup) with a UnityUIModule. What is the unity module supposed to do with silverlight UIs? This design flaw will show its head much earlier than this predicament, however: you will find in UnityUIModule that you need to downcast the IUIs you get into a specific type. Downcasting is an indication that you are doing it wrong. The correct way is to make IUIModule parametric in the UI type:

interface IUIModule<TUI> where TUI : IUI 
    TUI Over(TUI over, TUI under);
    TUI VerticalGroup(params TUI[] uis);
    TUI Window(string title, TUI contents);
    TUI Button(string text, Action onClick);

Now UnityUIModule implements IUIModule<UnityUI> and SilverlightUIModule implements IUIModule<SilverlightUI>, so it is a compile-time type error to pass a silverlight UI to a unity combinator. In addition, you do not need to downcast: the UnityUIModule now knows statically that it will only be passed SilverlightUIs.

One thing remains… how are you supposed to use that damn module? Surely you don’t make every class that uses a IUIModule parametric in the TUI parameter like this:

class World<TUI> where TUI : IUI
    IUIModule<TUI> uiModule;
    public World(IUIModule<TUI> uiModule) {...}

Type parameters would accumulate in classes, and every time you used that class you would have to write all those fucking type parameters. That can’t be the way to go!

Well… actually… remember the rule? You never reference a class concretely, you only go through interfaces. And the interfaces don’t accumulate type parameters from usages in the implementation like classes do, they only accumulate type parameters from the cleaner and scarcer usage in interfaces. So the worry of unsightly verbose code is unfounded. It’s fine, let the type parameters accumulate, they are a way of stating your assumptions. They tell you exactly how a class may be reused. So to defeat this notational burden in this example, we must continue the pattern: create an IWorld!

As you do this, all your assumptions will bubble up to the top of your program. Each more complex thing is parametric in all the simpler things it is made of. When you go to write code that can actually be executed, you will find an ocean of flexibility: you basically have created a rich combinator library for your domain, allowing it to target multiple underlying frameworks easily, getting multiple different (reasonable, even desirable!) behaviors just by passing a different parameter to some object you are building at the top level. Mmmm, parametricity.

(For dynamically typed languages, duck typing will mostly take care of this pattern for you. But the design motivation remains, make your code parameteric: take parameters saying where it should get the objects it is creating and the functions it is calling rather than referencing them directly!)

Did you enjoy this article? Let me know and Flattr this. I appreciate it.

Encapsulation Considered Harmful

You heard me. Encapsulation is an obstacle to the reuse of code.

When I say encapsulation, I mean having a region of your program that knows or has access to some information about the implementation of something, and hiding that information from the rest of the program. If you have another definition of encapsulation, I’m not arguing against that.

Why do software engineers encapsulate? I claim it is for two major reasons: (1) to reserve the right to change the encapsulated code later without breaking anything, and (2) to minimize the propagation of assumptions through the program. To illustrate this, consider the following C code which uses a (supposedly) abstract List type:

int sum(List* list) {
    int i;
    int accum = 0;
    int length = List_length(list);
        accum += ((int*)list)[i];
    return accum;

This code breaks encapsulation. It assumes that List is represented as an array. So if we wanted to go back and change List to a linked list because it is more efficient in the majority of cases for which we are using it, sum would break. (In this example, it would break very badly — i.e. it might not even segfault but instead return some nonsense number)

Here is an example of code that correctly respects encapsulation.

int sum(List* list) {
    int i;
    int accum = 0;
    int length = List_length(list);
        accum += List_get_elem(list, i);
    return accum;

If you’re about to object that we should have exposed an iterator interface instead of a indexed get interface because we knew we wanted to change it to a linked list, I preemptively respond that we didn’t know that at the time — as in most code, when you are encapsulating, you don’t usually know what you’re going to come back to change — if you did, why didn’t you just write it like that in the first place?

The two reasons above are noble. They promote flexibility and simplicity, so that the minor decisions we make do not ripple their way through our architecture, making it impossible to change or understand. It takes the pressure off.

Although I agree with the goals, I believe this is the wrong solution. I think we should turn the barriers inside-out, and use only encapsulation’s dual: abstraction. When I say abstraction, I mean code that is defined polymorphically with respect to its assumptions. The above C code is abstract with respect to the list argument, since we can pass it any list we like. It is not, however, abstract with respect to the the List type and its operations — it fixes a single choice.

Encapsulation and abstraction are duals in the following sense: let’s say your program is defined in two parts A and B. A knows some information C, and B does not. There are two ways to look at this. A encapsulates C, or B is abstract with respect to C. That is, if you change C, you have only affected the specification of A, and B reacts polymorphically. So just divide your program at an information boundary — one side is encapsulating, the other side is abstracting.

While mathematically they are two sides of the same coin, there is a very real software engineering difference between them. Let’s say you are have three functions which use your abstract interface: sort, reverse, and frobnicate (some complicated business logic that can’t be written in 5 lines). With encapsulation, you might have this sort of usage graph:

And then, in one fell swoop, you can change it to:

That’s power, that’s flexibility. But… it’s lacking something. Now we have another part of our program which uses arrays, and I sure wish we could use that sort code we’ve already written. But we need that sort code for lists. Hmm, well we could copy and paste. But that sucks, maybe we could go back and make sort polymorphic in the list type. Yeah, that’s the right way to do it.

But, then why didn’t we just do that in the first place? Look what happens when we do:

Look at all those combinations. Those are the possibilities for code reuse without changing anything. Imagine if every encapsulation you made was an abstraction instead. Your usage graph would be basically black with arrows. But these aren’t bad dependency arrows, these are good reuse arrows. These are your possibilities for correctly using code that has already been written.

So I suggest: instead of advertising your guarantees and hiding details, advertise your assumptions and abstract over details. This has a pretty profound effect on the way your code is structured — like I said before, it turns all the encapsulation barriers inside-out.

My inspiration for this idea came from studying the form of mathematical theorems. They advertise their assumptions prolifically: “given a ring R with (+) and (*) as operations, …”, as opposed to “a real number has (+) and (*) and some implementation details”. This allows theorems to be maximally reusable, since although the mathematician was thinking about real numbers when he proved the theorem, he realized the same logic could work on any ring — including the integers, modular integers, matrices, and new things that were discovered later.

Object oriented programming seems to get close. One can consider a class (or an interface) as the specification of an assumption, and an instance the implementation of an assumption. Then you just take parameters that correspond to your assumptions, which are nicely bundled into classes so you don’t have to say “I use (+) and (*) and (-) and absolute value and …”. But this essential idea is muddied up by all sorts of crap, both in the language design and in popular usage.

I started to list the features we need to add/remove from OO languages to make them support this style, but it just got long and nitpicky. So I’ll just say this: I think we should be using objects differently. Objects as implementations of assumptions, not as “agents”. A natural number is not an object, The Natural Numbers is an object. As generics gurus are noticing, this:

interface Number {
    Number operator + (Number y);

has got to go. The assumptions are not specified properly — you are requiring that + take any kind of number whatsoever, when we probably mean the same kind of number as on the left side. What does it mean to add 2 (mod 4) to 7 (mod 13)? Instead we are learning to write:

interface Numeric<N> {
    N operator + (N x, N y);

That’s the right way. Notice that, although it is specified with different notation, N is just another abstract member of Numeric. We specify the set and its operations together, but the set is distinct from the interface. The interface is the name for the assumption of such a set. In some cases the interface and the set can be bundled into one, and it is these cases that provide most of the study material for OO design. But inside the soul of pop OO lies a form of modeling that is so much more powerful.

To reiterate, this is not breaking the guarantees of encapsulation — anybody who uses Numeric gets encapsulation for free. They are not allowed to see the details of N, just as if you had encapsulated it. It’s just that now you can swap out different N’s in the same code, where you couldn’t before.

I am pleased to see software engineering practice slowly converging on this already. I just thought I would point out the uniform rule behind it. Next time you write an encapsulation, ask yourself, what would it look like to make the users of this code abstract instead? Is it a small enough notational burden to do it that way? If not, what kind of language would allow it to be?

Did that give you something to ponder about? Flattr this

Searchable Data Types




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


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:



Let’s try to write this in direct style:

search f | f Zero    = Just Zero


And it seems to work.

Just (Succ Zero)

Er, almost.

(infinite loop)



-- it returns a Nat anyway.
lyingSearch :: (Nat -> Bool) -> Nat
lyingSearch f | f Zero = Zero
              | otherwise = Succ (lyingSearch (f . Succ))


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

Let’s try.



lyingSearch f
0*0 /= 15
Succ (lyingSearch (f . Succ))
1*1 /= 15
2*2 /= 15




Hint: begin with a Search data type:


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

searchUnit :: Search ()



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





Did you like this post? Flattr this


Photoshop, Premiere, Maya, AutoCAD, ProTools, Finale, Reason, InDesign. These are the state-of-the art tools for creators. They are all rich, powerful, versatile programs that strive to work at the artist’s level of thought.

And the people who write this amazing software get to use… Visual Studio? Eclipse? Emacs? At least I’ve heard IntelliJ IDEA is great, I’ve never used it. But when contrasting these to the tools above something seems missing. Like a library full of features that bring programs to the coder’s level of abstraction. Languages are attempting this now, but languages are written in text and IDEs are basically text editors with a few extra features. Photographers have clone (a tool that lets them erase sections of images replacing it with something that looks convincingly the background in that area), we have refactor-rename that doesn’t even respect alpha conversion (avoiding name conflicts with your new name).

Why do we even have to worry about alpha conversion? That’s like a composer worrying about MIDI patch numbers! We still denote identity with a string? Premiere wouldn’t have that — it would link directly to the clip in question. Who cares if you have named something else the same thing? My friends have no trouble distinguishing me from another Luke who walked in the room.

And files? We have libraries, namespaces, modules, classes, and functions to organize our code. Files are almost entirely orthogonal and not-almost entirely meaningless. Kudos to CodeBubbles for noticing and removing that tumor. But, that’s just a guy at a university, so naturally we won’t get to use that for real for quite some time.

What’s up with import statements? That’s just some junk that comes with representing programs as text. Eclipse has surpassed those… sortof… but we’re not all Java programmers. Why can’t I just type the class name and then pick the one I want from a list?

All the state-of-the-art creative programs have multiple views: more than one way to see your creation to get a better handle on it. Maya has isometric, wireframe, flat-shaded, full light…. We have the class hierarchy view. Oh boy. Why can’t I look at

    while (!queue.empty()) {
        Production p = queue.pop();
        if (p.star.is_terminal) { scan(p); }

click a little [+] next to predict(p) and see it right there inline, with its argument replaced by p? Oh, that’s how that works, cool, [-]. Instead we go to its definition, where we see it next to the functions we happened to define near it, about which we care nothing. Then we substitute the arguments in our heads, fathom loop invariants and fail to see how they are violated, and spend the next 5 minutes wondering if p is mutated in this call chain.

How come I can still have syntax errors? How come it is ever possible to have a syntax error in a program? Shouldn’t the IDE at least be helping me to have a valid program all the time? Finale doesn’t let you write a measure with the wrong number of beats and then complain when you push play. It just fixes it for you — “oh look, you need a rest there.”

“My indentation’s wrong. Oops, rename missed that one. Oh right, need to import Data.List. Ugh, namespace pollution. Fine, looks like I need to copy and paste again because abstracting will be a pain. I hate how you can only have one class per file and how it discourages small classes. Shit, that mFoo/foo accessor pattern again… weren’t get/set supposed to do away with the need for accessors? Fuck, looks like this virtual method needs another parameter — give me fifteen minutes.”

Do we not hear ourselves?! Software developers, the masters that create the masters’ tools, are touching up Avatar with mspaint. Shouldn’t we be sculpting effortlessly a masterpiece with a beautiful dynamic interface while robots bring us platters of Mountain Dew? We’re wasting our time with spelling errors while the 3D artist in the back is putting finishing touches on his city.

W. T. F.

If you were entertained, Flattr this. Thanks :-)

One true way

This post is a follow-up to my recent post programs are made of ideas. I received a lot of interesting comments and criticism on this philosophical exposition. But there is one in particular that caused me to deeply consider whether my argument made sense. It starts with this excerpt from the post:

Why constrain ourselves by forcing a fundamental idea? Must there really be a One True Way which forms a basis for everything else to be defined?

Surely the set of all the ideas we are capable of having forms a fundamental basis in which everything else can be defined. Or more concretely, it is presumptuous to think that our brains are so great as to not be constrained by some underlying system. We may not see the definitions of our ideas, but if our ideas can be said to exist at all, they have to have some expression in terms of something, right?

It is another thing entirely to wish to communicate that basis to a computer. Logicians will be quick to intuit that we would not be able to fully understand any system which forms the basis for our own thoughts (however, this intuition will be difficult to formalize unless our thoughts obey first order logic). And I’m pretty confident in saying that it isn’t first order logic, it isn’t lambda calculus, and it (still) isn’t actions on digital state machine1.

A perhaps clearer way of saying what I was trying to say is this: let the system in which we communicate our ideas be our slave, not our master. Think first, then decide which words will lead to the clearest explanation. We as software engineers, mathematicians, and even speakers of natural language have a tendency to give in to Sapir and Whorf. While we may not be capable of freeing our thoughts from our language2, we may be caving too easily. I felt a breath of fresh air when I noticed and cut the ropes tying me to lambda calculus and functional thinking.

It is a beautiful thing that most of these systems are Turing complete. I have never read the Church-Turing thesis as “C is Turing complete, so you might as well use C for all your programming tasks”. I read it almost the opposite way: “choose whatever language you want, because I can always write an interpreter for your language in my language”. Isn’t it great that we are able to choose between the uneasy handwaving of Perl and the frustrating precision of Agda?

I have always seen a programming language as a single core system for which ideas must be tailored. In other words, as a master. A current project of mine is to devise software development software that embraces the plurality of these systems: a way to tie together all these different methods of expression so that they can benefit each other. Let the language camps remain polarized, but let the computer do the arguing.

1 You might ask, “But what if we consider the brain to be a big digital state machine?” That is beside the point. By the time our consciousness gets hold of our thoughts, the mechanism used to implement them is long abstracted away. (Or perhaps not — maybe these thoughts are the result of a highly abstracted digital state machine, and with a different sort of brain we would have vastly different sorts of thoughts. That even seems likely. Hmm, food for… digital state machine operations.)

2 Nor may it be desirable — Bertrand Russell admired Giuseppe Peano for the clarity in which he could express thoughts using the then-novel idea of formal logic.

Did you like this post? Prove it! Flattr this

Programs are made of ideas

quietfanatic The fundamental unit of a computer program is not a function; it’s an action. CPUs don’t do lambda calculus; they follow procedures.

I saw this on twitter a couple days ago and responded with a jerk of my knee, only to commence a discussion1 in which I failed to accurately express my objection. So here is a full treatment.

First I would like to disclaim that I am not attacking quietfanatic in any way. His quote merely provides a convenient means to discuss a widespread pattern of thinking.

Before we start talking about fundamental units of X, it’s probably a good idea to get clear about what we mean by X (where X = computer program). Here are some of the possible definitions I can think of:

  1. A computer program is a pattern of memory intended to be read by a CPU — machine code.
  2. A computer program is an abstract specification for the behavior of the CPU when fed (to-be-determined) machine code.
  3. A computer program is the idea of its behavior. To illuminate what I mean by this, think of Firefox. What idea did you have just then? Was it of an abstract specification? A series of bits? I doubt it. You probably pictured a window browsing the internet or something like that. I’m talking about that kind of idea.
  4. A computer program is a state of a physical system. If it is not in a block of hard disk or ram somewhere, it cannot be considered to exist.

The difference between these is the level of abstraction at which they are defined. But importantly, they are all defined at some level of abstraction — which means that they are all just ideas. Perhaps (4) is not, depending on how concretely you see the world.

Here are some of the ways to think of how a program is run:

  1. The specification of the program is interpreted by some rules, resulting in some changes to physical things.
  2. The CPU deconstructs memory into a series of discrete instructions, which it then “performs” one after another.
  3. The computer is a system in which the states of some physical devices are coupled to a system of interacting voltages, some of which encode a program.

Again, they differ at the level of abstraction at which they are defined.

The way I read quietfanatic’s quote is talking about level (2) of the program and level (2) of the CPU. To me it says “CPUs perform instructions, so our abstract specifications of computer programs should be (ultimately) in terms of instructions”. With that phrasing there seems to be a wide logical gap between the two clauses. Why does the language we use for abstract specification have to correspond to one particular abstract conception of how a CPU works?

By permuting my list of interpretations, I can construct many plausible quotes that follow the same logic. “The fundamental unit of a computer program is a rule, since the program is ultimately interpreted as rules” or “the fundamental unit of a computer program is a voltage, since voltages are ultimately what drive the devices.”

But my objection is larger than this fallacy. To me, and I presume to most software developers, programs are made of ideas. When thinking about programming languages, we are looking for a way to express our ideas in a way that the computer can approximate them. Our ideas form the central theme, not the mechanisms that approximate them.

What is the fundamental unit of a number? How about of a web page? A shape? A set? A cursor?

All these things are ideas, each of which has many different lights under which it can be viewed, each of which may give a different answer about a “fundamental unit”. But ultimately ideas are not defined in terms of anything — we use definitions to grasp how our ideas connect to each other. Some might say that the fundamental unit of mathematics is the set, but when I think about a triangle, I’m sure not thinking about sets.

I am unable to see how computer programs are any different. Why constrain ourselves by forcing a fundamental idea? Must there really be a one true way which forms a basis for everything else to be defined? In the historical development of mathematics, our ideas have had a shifting fluid foundation, each generation bringing a new way to think about the same things. Currently the evolution of programming languages is serving as our shifting foundation. Let’s use our full vocabulary of ideas to express programs, and try not to limit our concepts’ true breadth and beauty by telescoping in on what they mean in terms of a fixed basis.

This article is reflecting a change in thought that I am going through right now. After a lot of time being committed to the lambda calculus, finding ways to construct the naturals out of some pretty-looking set of primitives, devising ways to abolish imperative thinking and embrace functional thinking, I realized that I was lost in a world of details. Everything I did and thought was coupled to the fundamental system I was creating.

It is dawning on me that the fundamental system is merely a means to express my ideas, and the true beauty is in the ideas themselves. My denotationalism fades as I perceive that most of my mental structures are intrinsic. They are not defined in terms of anything and they have no denotation other than themselves. There are ways to model those ideas, but I am suddenly being careful not to confuse the model with the idea itself.

1 To the extent that a series of tweets can be considered a discussion.

Did you like this post? Show, don’t tell Flattr this

Programming for a culture approaching singularity








The state of progress in reusable software




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









Haskell’s Big Three


1. No Module Abstraction





2. Module Naming Policy




3. Unrefactorable Typeclasses


    negate           :: a -> a
    abs, signum      :: a -> a
    fromInteger      :: Integer -> a








