Computers Aren’t Fast Anymore

Hello, doctor. I am only 22 years old, but I think computers used to be faster. Why do I feel this way? Can you help me?

Well, it couldn’t be CPUs. Everyone knows that chips were once getting twofold faster every couple of years. That is slowing down a bit now. But it couldn’t be GPUs, either. They’ve seen impressive leaps in speed too.

Hmm? Are we developers to blame? No, I don’t think so. We’re getting better and better at operating our newfangled machines, to take advantage of their futuristic capabilities. At the very least, the smart folks are writing languages and frameworks to bestow that power on the rest of us.

Of course, the extent that most developers see this innovation is in taking embarrassingly data-parallel problems and slapping them on a GPU. But that’s something, isn’t it, doctor? Memory’s faster, CPU caches are bigger, and hard disks are faster than they used to be. SSDs are even faster than that.

Tell you about my past? Okay…

At my high school, there were these run-of-the-mill Windows 2000 machines. We programmed on them in VB6. And let me tell you, for all its downsides, VB6 was screaming fast. These crappy amateur applications were downright speedy. Everything was.

When I use a computer now, I don’t feel that way. I don’t feel good about the speed or crisp responsiveness of applications. Not on a desktop, not on a high-end laptop, and especially not on a mobile device. And being that my job includes developing software for mobile devices, I have messed around with a great many of them.

I was deeply concerned by this. So I sat and I thought. Hmm. And it dawned on me: I don’t use real applications anymore.

I write this very psychiatric confessional blog post within a WYSIWYG editor running inside a web browser. (Sorry, doctor, but you’re just a figment of my overactive rhetorical imagination.) In the browser lies the problem. Almost all of the erstwhile proper applications that I use on a daily basis are now web applications.

Wait. Hold up. Give me a minute to breathe. We’re on to something.

All of the (user-facing–type) applications I use. They are running in a web browser. Which runs HTML and JavaScript. In case you haven’t heard, or you’re thinking of a different thing, we’re talking about HTML the document markup language. JavaScript the dynamically typed scripting language.

What. What. This is not okay. This is so beyond not okay that I have difficulty articulating the manner in which it is not okay because I feel like it should be obvious and why aren’t people freaking out? I’m freaking out.

Calm down? Okay, doc, I’ll try.

[Minutes pass, glacially.]

I guess the problem that I have with this is that programs aren’t…programs anymore. They’re not running on my hardware. They’re running umpteen layers removed from my hardware. They exist on this fundamentally different substrate, one that can’t be efficiently implemented on the real machines that we’ve spent so much effort making fast for real programs. It’s insane.

The things that are running natively are running on underpowered hardware, such as mobile games. And still a great number of them rely on internet services to function properly. Like a parasite, no, like an organ. Everything is part of this enormous whole, of which I am somehow not a part, and I wanted the brain and the muscle but you handed me a kidney.

Developers? No, I don’t fault them at all. You’ve got to have fun, and you’ve got to make money, and you’ve got to make programs. That’s just how it is. Everybody but me seems to have accepted a long time ago that it’s okay for an application to take this many milliseconds to display a character on the screen, or that many milliseconds to scroll. Or very many milliseconds stoned on TCP, roundtripping to a server for my data.

And my poor data. It wasn’t safe on the ground, so we sent it to live in the cloud with foster parents. Now I don’t know where it is, but it isn’t here. It’s holed up in my web applications, and it never comes to visit.

So do you think you can help, doctor? Is it just me? Should I adapt to this brave new world and wait for the award-winning silicon implementation of JavaScript running alongside an HTML coprocessor? Can I have my fast back then?

In the meantime, I guess I’ll continue to sacrifice a fraction of a second off my life here and there for the convenience of using a web program.

Rendering to a canvas.

Running in a browser.

Rendering to a screen.

So I write compilers for a living now.

I’m a regular visitor of Stack Overflow, and have a Stack Overflow Careers profile. A month ago, I saw a job listing for Spaceport.io, a YouWeb-funded company that makes a tool for converting Flash applications to run natively on several different platforms. A key component of their technology is a compiler, written in Haskell, from ActionScript 3 to the Spaceport runtime.

Since I enjoy working in Haskell, and compilers and games are two of my favourite things, I readily applied. After phone and Skype interviews, I flew out to California for a day of in-person interviews. Much as I like flying, it’s no fun to spend more time in the air than at your destination. Lesson learned.

Soon afterward I received an offer, accepted, and in a few short weeks found myself moving across the country from southern New Hampshire to the Bay Area. It’s been a great adventure so far, with plenty of good people, good food, and endless opportunities to practice my Chinese. :)

Stack Overflow Careers

When it launched, I believed Careers would soon become the go-to place to hire developers. Unfortunately, none of the job offers I actually received were the right thing for me. Most were a mediocre, uninteresting kind of bad, not the hilariously terribad stuff of great blog posts.

But it was well worth the wait. I got a job on the basis of reputation and merit, not just a résumé. And now I can happily say I make my living off compilers, which is what I want to be doing for the foreseeable future. The coolest part is that I can apply much of the theory I learned while doing language research in college—to solve practical problems.

From the company’s side, Careers is a win as well. You get many good developers looking at your job listing, for a downright minuscule fraction of the financial and time cost of a recruiter. When you get an application from a developer, all of the information you could possibly want to know about their skills and history is right there in their public profile.

So, fellow devs, if I’m ever in a position to hire you, it will probably be through Stack Overflow Careers.

Professional Haskell

Since I started using it professionally, my opinions on Haskell have definitely evolved. It’s a well designed language, to be sure, but till coming to Spaceport I hadn’t really had the opportunity to explore a large project. Here are some of the things I’ve learned while using Haskell in production.

Haskell is Scalable

I was skeptical that the language could scale, not only to a large project but to a complex one. It’s not that I was doubtful, exactly. It’s just that languages that perform well for small code don’t necessarily work well for big code, and vice versa. You can’t know unless you test.

After working with a roughly 10,000-line codebase for several weeks, I’m now convinced that Haskell is excellent for coding in the large. With good unit tests in place—we have about four times as much test code as application code—I was able to productively make changes and feature additions starting on day one.

A Haskell codebase seems to remain readily comprehensible well beyond the size where, say, a C++ codebase starts becoming unwieldy; it’s maybe a 2:1 ratio. Functional languages are good at factoring, too, which is basically the essence of abstraction and the key to managing complex code.

Still, you must be diligent about it. Using Haskell does not automatically make you a better programmer, athough the people who learn Haskell well do seem to be better programmers for it—if only because Haskell is pretty progressive as languages go.

Haskell is Productive

Proponents of any language often talk about increased productivity. I do feel more productive in Haskell—in terms of the amount of code I have to write in order to add and test a feature—than in most any other language. But I can’t exactly quantify that, so I invite you to try it for yourself.

LOC is funny in that it’s simultaneously an important metric and a completely useless one. Language designers tend to be in agreement, more or less, that syntax matters—that good syntax does wonders for the effectiveness of language as a tool of thought. Naturally, they disagree about what actually constitutes “good syntax”. There might be something more to it, or it may just be a matter of taste that Python looks good to Alice and APL looks good to Bob.

Regardless, Haskell looks good to Jon. It’s pleasant to read—succinct, but not so dense that reading it is a chore. As is the case for any language, tutorial code looks nothing like production code. In Haskell you also see many academic papers where the style is very mathy—one-letter names, excessive abbreviations—and that style doesn’t scale at all beyond 200 lines. You need good names, no matter what.

Static Typing? More. Gimme.

Haskell’s type system is powerful enough that type signatures can tell you a good amount of useful information as to what a polymorphic function does. The “polymorphic” part is important: specific types naturally have much broader interfaces than simple type variables. You can easily say that a function of type (a → [a] → [a]) has only a few possible sane definitions. (Well, okay, countably infinitely many, but still.)

1. f x xs = x : xs
2. f x xs = xs ++ [x]
3. f x xs = intersperse x xs

Whereas you know considerably less about what a function of type (Double → Double → Double) might do, because the set of floating-point numbers, and functions operating on them, is so large. The type system makes the trade-off explicit: the more domain-specific your functions are, the fewer guarantees you have about them.

In practice what this means is that, say, glancing at the type signature of a poorly-named function can give you a decent clue about what it ought to do. Or if you need a utility function, you can search Hoogle for a plausible type signature and usually find what you need. No other popular language’s API search comes close to matching that kind of utility. Thanks to Hackage, new libraries are very easy to discover and integrate into a project.

Haskell is Reliable

Where Haskell really does shine is in building reliable software. Static typing, unit testing with HUnit, and property testing with QuickCheck let you easily make a lot of guarantees that your code does what it’s supposed to. This is especially valuable for compilers, which are essentially (very large) pure functions, and thus very much amenable to such testing.

Testing definitely requires more up-front thought, but the end result is more reliable software—and that’s synonymous with better software, because good software is, for lack of a better term, obedient. Except maybe for AI.

Haskell lets us have a near-complete, robust AS3 compiler in under 10,000 non-blank lines of not-particularly-terse code. And that’s saying something: ActionScript is not what anyone would call a “pretty little thing”. And you don’t even know the half of it.

Conclusions

• Compilers are fun and I will write them forever.
• Haskell is good and I will use it for a good long time.
• The Bay Area is a cool place to be, and I’m glad I moved here.

For those interested in my language work, an update is coming soon. Till next time.

The Utopian University

Musician Tom Milsom recently wrote on his Tumblr:

I just wanna make shit

I don’t want money

I want to be able to live in a nice place and eat and fund US tours and stuff but apart from that

Nope

Pirate my music if you can’t afford it, cause it all comes round eventually in like goodwill and stuff, I don’t mind

I just want people to be able to enjoy what I do in the best possible environment

This really got me thinking. It’s a sentiment you often hear expressed among creative folks, and yet it never really seems to be addressed. I’ve been wishing for ages that there were some kind of patronage system for creative people—to do for makers what Y Combinator does for tech startups.

Creative people mostly just want the opportunity to create without being bothered by irrelevancies. Art colonies fill this need somewhat—you apply for a fellowship and get space and potentially funding for a summer to work on whatever you want. But this is, by nature, small-scale.

No matter how hard you wish oh wish for something, nobody is going to make it for you. But if you have a problem, and you fix it yourself, other people will come to you and say “Take my money!” or at least that’s the hope.

So what is my problem?

In order to create, I have to work on stuff not immediately related to my creations.

Even as a programmer, who can ostensibly create value out of just caffeine and time, most of my ideas are not easy to monetise. My hobby project right now is the compiler and tools for a new programming language. Whatever money I stand to make from that would be in book sales or donations.

So I, like many, cannot reasonably hope that my creative pursuits will ever be self-sustaining. And that’s fine, though I do envy Tom in that he is successful enough as a musician to continue being a musician.

Now, I could solve this problem by aggressively contacting investors to set up some kind of über-patronage venture fund thing for creators. That is, to my mind, the obvious solution.

But I don’t think it would scale. At all. In fact, I think it would be a spectacular failure.

Sure, the idea is straightforward. You apply with a portfolio. If accepted, you get a small amount of funding (say around $10,000) for a dozen-odd weeks to work on a particular project. That’s enough to ensure you have a place to live, food to eat, and the equipment and materials you need to work. Your patrons get a stake in anything you produce during that time.

But that’s not an attractive proposition for the people who would actually provide the funding. They have no way to force creators to stay on task. Worse, they won’t necessarily have the experience to know what to do with rights in widely varying projects.

And at the end of the season, they won’t have equity in a business. They’ll have rights in an album, or a game—a product with no business around it and no guarantee of growth unless somebody does some aggressive marketing. Which costs more money. That’s why specialised creative industries exist—record companies being the number one example. You make, we market.

Why would you, as an investor, buy a stake in something unless you expected it to be worth at least as much as you paid? This hypothetical patronage group would necessarily become a seed funding platform for creative startups, not just creative individuals in general. Even barring the other potential problems with that, it’s not what I want.

What I really want, quite frankly, is a Utopian University where creators can freely live and work and drink and mate and generally forget about the outside world. Creators create, the University helps market, the public buys, and the dollars come back to fund the whole shebang.

In order to keep everyone motivated, creators would be held accountable for their productivity—if you aren’t making progress on anything, you get the boot, or have to take a leave of absence. Call it an “artistic GPA” requirement.

That is something I think could work—with substantial initial funding, careful planning, and the right people behind it. I have no idea how to make it happen, but it will remain in the back of my mind as a long-term goal. And of course I’d love to hear a better idea.

C++ Functional Style Tips

To say that C++ is a complex language would be an understatement—I had to spend years using it before properly understanding all of its many gotchas. Because I have plumbed its depths, I cannot recommend it to anyone for any purpose. If you know how to use the language effectively, then by all means do use it—but if you do not already know it, then there are plenty of other, perfectly good languages out there. Personally, I’m a fan of C, Haskell, and Scheme.

However, the language is still undeniably useful, particularly in game development. So I must try to benefit from the power of C++ while avoiding its failings in every way that I can. Following, then, are some brief guidelines that I have found to work well for me to write C++ code in a more functional style. And functional style makes it easier to grasp a program by reducing the effort required to understand its possible states—so you can focus more on solving problems than fixing bugs.

For the sake of concision, I’ll assume that using namespace std; and using namespace std::placeholders; are in effect. Obviously in real code you ought to import only what’s necessary, and in as small a scope as possible.

♦ ♦ ♦

1. Use const Obsessively

C++ unfortunately has no reasonable way of enforcing referential transparency. You cannot readily make the compiler complain when a function has externally visible side effects. Indeed, I hope C++2x gets a pure keyword. But in the meantime, at least we have the ability to enforce immutability with our good friend const.

In general, everything should be const unless it truly needs to be modified—whether because an in-place algorithm is more efficient than its non-mutating equivalent, or because of failings in the type system and standard library. As an example of the latter, you cannot use standard algorithms to initialise an immutable container, resulting in objects that are unnecessarily non-const.

Declare member functions const if they are logically non-mutating, that is, you would expect that calling the function in and of itself will have no effect on the observable state of the object.  “Observable” means that you can deduce said state through the public interface alone.

struct Point {
    double distance(const Point&) const;
    double distance(double, double) const;
    double x, y;
};

When taking parameters by lvalue reference, use const when possible.

    double distance(const Point&) const;

When taking parameters by value, declare the function as usual.

    double distance(double, double) const;

Then make the parameters const in the definition, unless of course they are to be modified.

double Point::distance(const double x, const double y) const {
    …
}

Don’t bother returning by const value—all it does is arbitrarily prevent calling mutating member functions on temporaries—but do return const references where appropriate.

const vector<double>& TreeNode::get_children() const {
    return children;
}

Make local variables const when possible.

double Point::distance(const double x, const double y) const {
    const auto dx = this->x - x;
    const auto dy = this->y - y;
    return sqrt(dx * dx + dy * dy);
}

Be sure to use const qualification for pointers where appropriate.

T* x;             // Mutable pointer to mutable T.
const T* x;       // Mutable pointer to immutable T.
T* const x;       // Immutable pointer to mutable T.
const T* const x; // Immutable pointer to immutable T.

This also applies to smart pointers such as unique_ptr (which you should use a lot) and shared_ptr (which you probably don’t need).

shared_ptr<T> x;             // Mutable shared pointer to mutable T.
shared_ptr<const T> x;       // Mutable shared pointer to immutable T.
const shared_ptr<T> x;       // Immutable shared pointer to mutable T.
const shared_ptr<const T> x; // Immutable shared pointer to immutable T.

Related to const is constexpr, which allows you to ensure that if a function can be evaluated at compile time, then it will be. This has less to do with functional style and is more a matter of optimisation, so I mention it only for the sake of completeness.

♦ ♦ ♦

2. Use <functional>, <algorithm>, <numeric>, and <iterator>

The C++ standard library has a number of common algorithms abstracted into iterator-based functions. While iterators have some flaws, they can often help you write code that is more readable than the alternative using explicit loops.

bind() lets you perform partial application of function objects.

const auto succ = bind(plus<int>(), _1, 1);
cout << succ(3) << '\n';

Here, bind(plus<int>(), _1, 1) is equivalent to the section (+1) in Haskell.

There are two versions of transform() to be found in <algorithm>. The first is analogous to the familiar functional map, applying a unary function to each element in a range and sending the results to an output iterator.

const vector<int> a{1, 2, 3, 4, 5};
vector<int> b;
transform(a.begin(), a.end(), back_inserter(b),
    bind(plus<int>(), _1, 1));

The second version is analogous to zipWith, which takes two input ranges, applies a binary function to each pair of elements, and sends the results to an output iterator.

const vector<int> a{1, 2, 3, 4, 5};
const vector<int> b{5, 4, 3, 2, 1};
vector<int> c;
transform(a.begin(), a.end(), b.begin(),
    back_inserter(c), plus<int>());

accumulate(), from the <numeric> header, is by default a sum:

const vector<double> values{3.1, 4.1, 5.9, 2.6, 5.3, 5.8};
const auto sum = accumulate(values.begin(), values.end(), 0.0);

With a binary function, it becomes a left fold:

const auto product = accumulate(values.begin(), values.end(),
    1.0, multiplies<double>());

C++11 introduces lambdas to C++, which are largely syntactic sugar for anonymous classes—the members of the class are the (explicit) closure from the lambda’s lexical environment, and the operator() of the class is the lambda body. When you need to use a non-trivial function in a standard algorithm, it’s clearest to use a lambda rather than trying to compose function objects.

const auto paraboloid_product = accumulate(values.begin(), values.end(),
    2.0, [](double x, double y) { return (x - 1.0) * (y + 1.0); });

On the other hand, sometimes it’s better to use a simple for loop. Case in point: the for_each() algorithm, which conveys no more information than an ordinary range-based for, and can become unreadable when the types are non-trivial.

// Do this.
for (auto& p : symbols)
    p.second->method();

// Or this!
for (auto p = symbols.begin(); p != symbols.end(); ++p)
    p->second->method();

// Not this.
for_each(symbols.begin(), symbols.end(),
    [](pair<const string, shared_ptr<Value>>& p)
        { p.second->method(); });

♦ ♦ ♦

3. Use auto and decltype()

The C++11 auto keyword allows you to omit the manifest type of a variable, if a type can be deduced from the variable’s initialiser. Combined with const, this makes C++ variables look an awful lot like single static assignment registers.

const auto v = f(x, y);

Just as auto is used to deduce a declaration from an initialiser, decltype() is used to deduce a type from an expression:

decltype(v[0]) w;

Like sizeof(), decltype() does not evaluate its argument, so it’s safe to use side-effectful functions in a decltype() expression. Like const, you ought to use auto and decltype() wherever possible, specifying manifest types only when necessary. auto lets you avoid repetition at the type level, and decltype() lets you express types as contracts in terms of other types.

♦ ♦ ♦

4. Use Higher-Order Macros

One of the reasons I’m fond of functional and concatenative programming is an increased ability to reduce repetition through factoring. A functional style, and in particular a point-free style, is vastly more amenable to refactoring than imperative code. Unfortunately, C++ often makes it unwieldy to do such refactoring, even with functional style, because it is inherently an imperative language.

Despite its limitations and caveats, the C preprocessor is useful for eliminating repetition. Unlike, say, Lisp macros, which are Turing-complete, CPP is only equivalent in power to a pushdown automaton. Still, macros have one powerful feature that I use regularly: they can take other macros as arguments. Thus you can define a sequence like so:

#define FUNCTIONS(M) \
    M(add, +) \
    M(sub, -) \
    M(mul, *) \
    M(div, /)

And apply macros to every term in the sequence:

#define DECLARE(N, O) \
    int N(int, int);

#define DEFINE(N, O) \
    int N(int x, int y) { return x O y; }

FUNCTIONS(DECLARE)
FUNCTIONS(DEFINE)

#undef DEFINE
#undef DECLARE

When C++ fails to provide a mechanism of semantic abstraction for a particular problem, higher-order macros at least allow you to abstract syntactically repetitive code. Judicious use of macros to reduce repetition is a Good Thing, even if it might make you feel a bit dirty.

♦ ♦ ♦

I’m sure there’s more I’m forgetting, but that’s the meat of it. Functional style can help you out, and here are some ways to do it. These aren’t rules, just guidelines, and you should always evaluate each problem individually to determine if the usual patterns really fit. Programming is, after all, a very subtle magic. But if there’s any way to make that magic a little more fun, I’ll take it.

Frighteningly Ambitious Programming Language Ideas

Use versus Mention

The use–mention distinction—in addition to being one of the rare opportunities to use an en dash—is a distinction between application of a term for its inherent meaning (Brian is alive and has no letters) and examination of the term for its superficial representation (“Brian” has five letters and is not alive). In natural languages, we typically use quotation to differentiate between use and mention.

This distinction is one of those apparently mundane linguistic phenomena that turns out to have rather subtle and interesting philosophical implications. In particular, use without mention is the basis of pronouns and demonstratives—in “He picked up the book and studied it”, it refers to the same thing as the book, without repeated mention of the book. These structures in turn allow self-reference, as in the liar paradox (“This statement is false”) and Quine’s paradox:

“Yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.

Reference and self-reference are two things that come up quite often in programming. If you’re a language designer with a mind to fundamentally alter how programming is done, then the ideas that follow are yours for the taking. They are difficult, unattractive, dragonish ideas, and it will be many years before ordinary developers take them seriously.

But first, some background.

♦ ♦ ♦

Reference and Quotation

Every aspect of natural language has a parallel in artificial language. Concrete referential types such as pointers are also references in the abstract sense. Pointers are like pronouns in that they allow you to refer to a thing itself, rather than through its name. Take this C code:

T x;
T *y = &x;

Here, *y refers to the very thing that x does. In addition, it allows a form of lazy evaluation: we can pass around copies of y as much as we want, without creating copies of *y. Deferred evaluation thus has performance benefits, but more fundamentally, pointers allow us to create data structures of a wholly different shape than the memory in which they live—trees and graphs and so forth. More on that later.

So in C, taking the address of a variable is a form of quotation, preventing the evaluation (copying) of that variable until the pointer is dereferenced. In Lisp, the quote special form likewise denotes mention rather than use, but of any expression:

(f x y)         ; Use
(quote (f x y)) ; Mention
'(f x y)        ; (Shorthand for the above.)

Concatenative languages have this as well:

y x f     # Use
[ y x f ] # Mention

This is essentially a generalisation of pointers—deferring evaluation through quotation. Lisp programs can pass around code unevaluated as easily as C programs pass around data uncopied. This largely eliminates the distinction between data and code, and allows still more kinds of laziness. Anonymous functions are similar to quotations, but a bit heavier in that they also have a closure of variables from their (lexical or dynamic) environment.

♦ ♦ ♦

To Infinity

But as it turns out, it’s not even strictly necessary to make a distinction between use and mention. The most visible example of this in practice is probably Haskell, where evaluation is non-strict by default. Every expression is nominally a reference (thunk) to be evaluated only as needed. To support this, most types are implicitly referential (boxed). Non-referential (unboxed) types are available for internal use and low-level optimisations.

In a way, lazy evaluation is rather like garbage collection. GC simulates a machine with infinite memory; lazy evaluation simulates a machine capable of infinite computations. In Haskell, it’s normal practice to construct infinite lists and cull them as needed. That’s backward as far as most languages are concerned, but it also turns out to be a very intuitive way of modelling many kinds of problems.

So we can work with infinities of space and time on finite machines. But can we generalise further? Well, yes, but the results look pretty alien. Here be the aforementioned dragons.

♦ ♦ ♦

Dimensionality and Topology

Our computations are essentially two-dimensional, with one dimension of space (memory) and one of time. More time dimensions are possible, but I don’t see the use, considering our universe seems to have only one. I’d appreciate comments from anyone who can offer an application of such a thing.

You can very easily generalise to more memory dimensions, though. 2D memory allows you to construct, say, a matrix where each element is adjacent in memory to all of its neighbours. You just allocate memory in rectangular rather than linear regions. Unfortunately, you lose a sane ordering relation on pointers.

You can also play with the memory topology—cylindrical, spherical, or toroidal memory lets you construct fixed-size circular arrays, where each element is adjacent to the next, and the last is also adjacent to the first. Slightly stranger topologies allow variable-length circular arrays. And beyond familiar shapes and grids, any lattice graph can serve: in a 2D hexagonal topology, for instance, each memory location is adjacent to six others.

Our programming languages, too, tend to be one-dimensional, much like our natural languages; but this, too, is not a requirement. Indeed, two-dimensional languages and higher-dimensional languages have been made, but it’s probably more practical to add 2D features to a predominantly 1D language:

# Probably a good idea:

matrix = 1 2 3
         4 5 6
         7 8 9

# Maybe a good idea:

lispy_boxes = +-------------+
              | * +-------+ |
              |   | + 2 3 | |
              |   +-------+ |
              |   +-------+ |
              |   | + 4 5 | |
              |   +-------+ |
              +-------------+

# DEAR GOD WHY

         (   divisor  ) exponent    n
result = | ---------- |          * sum set(i)
         (  dividend  )            i=0

Furthermore, 1D languages require jumps for flow control, but since any graph can be embedded in three dimensions, languages of three or more dimensions can be written jump-free. An easy way to do this is to allow changing the direction of the instruction pointer rather than its position.

And for you CS theory types looking for something to do a Ph.D. on, it’s a fun problem to figure out whether a language with a strictly planar state diagram can be Turing-complete. Go nuts.

♦ ♦ ♦

Diffing, Visualisation, and Editing

As with memory, languages could be given any number of interesting topologies beyond the usual grid. Tool support, of course, becomes something of an issue. It’s relatively easy to see how a diff would work in a 2D or 3D Cartesian language, but more complex spaces are problematic.

In one dimension, diffing relies on the longest common subsequence problem (LCS). While this problem is NP-hard, it can be solved in polynomial time using dynamic programming for a constant number of sequences—usually two, the previous and current versions of a file.

In more complex spaces, you have to rely on the maximum common subgraph isomorphism problem (MCS), which too is NP-hard. Luckily, MCS is solvable in polynomial time when the circular ordering of edges around vertices in an embedding is constrained, as it would (almost?) certainly be. But you don’t need to add complexity when you generalise—hell, for some languages, you might only need simple graph difference.

No, the really problematic things are visualisation and editing. How do you display removals and insertions in multiple dimensions and unusual topologies? Even for 2D images there are many equally good ways to visualise differences. How do you let a programmer efficiently and reliably create, alter, and share programs outside the realm of 1D text?

♦ ♦ ♦

And Beyond

Programming is still a fairly new field. Our languages are hovering around a local maximum, but there’s little reason to think we couldn’t come up with something better, more fun, and more productive. We need to be willing to sacrifice some of the things that make existing languages great, because they might have no analogue in a better system.

In other words, we should not imagine aliens in terms of the creatures we know. A green dog with antennae is still a dog. We should instead imagine things that make us legitimately uncomfortable to think about. Things that are unattractive not because they’re peculiar or dangerous, but because they’re deeply unsettling. Think Marvin the Martian versus the blind idiot demon sultan Azathoth. If those aliens exist, then not only does it mean we’re not alone—it means we’ve been wrong this whole time. And that, unfortunately, is how progress works.