Atypical: A Differently-Optimized Type System

What are programming languages for? This might be a silly question, but bear with me for a moment.

Most programming languages try to be at least partially general-purpose, but the languages that tend to grow popular are the ones that work well in an area where existing languages do not. C’s popularity persists because it’s still one of the few languages that lets you—forces you, in fact—to drop down to a low level and root around in the guts of the computer’s memory yourself. C++ carried that forward from C, but added more complexity, allowing people to create structure in larger software systems. Java took that object-oriented large-system-structure approach even further, but divorced it from the low-level programming of C and C++, running programs on a virtual machine that acts the same on a wide variety of hardware, at the expense of some performance. And then you even have environments like Node.JS, whose selling point was web development, where asynchronous programming is important and allowing people to use a single programming language in both the front end and the back end was desirable.

Many of these decisions stemmed from the kind of things each language was optimizing for: low-level programming, hardware agnosticism, easy transition by web developers, and so on.

But if you go further, into the less-widely-used languages, you find some interesting cases where people are optimizing for other things. Rust optimizes for safety while trying to retain as much performance as possible. Haskell and its powerful type system tries to make sure your program does exactly what you want it to do and nothing else. Prolog is an attempt at making you tell the computer precisely what you want, and letting the computer go and figure out how to do it for you.

So here’s a question: how would you design a feature for a language meant for live presentations?

I wouldn’t even call this a programming language, per se. After all, programming languages are meant to create an artifact—a program—that you later distribute or run. A presentation-based language, on the other hand, should be okay with being ephemeral, since the point isn’t the artifacts that you create, but the information being communicated. This language also has to allow for improvisation, and has to allow the presenter to drive it in the way they feel is best.

Over the course of the last year of my Masters degree, I worked to answer that question. I want to tell you a bit about the project I was working on, the motivation behind the feature I implemented, and how that feature came together.

Chalktalk

This language for live presentations isn’t hypothetical. It’s a real system being actively developed by Professor Ken Perlin and the other researchers at NYU’s Future Reality Lab, called Chalktalk.

Chalktalk is best described as a magic chalkboard. You can draw in it, same as a regular chalkboard, but when you draw certain objects and then click on them, they come to life and let you interact with them.

These objects, which we call “sketches”, can do a lot of different things. They can show animation…

They can play audio…

They can be used to demonstrate simple concepts…

Or they can be combined together to show more complicated concepts.

The concept behind Chalktalk is twofold.

In the present, it’s a presentation tool meant for talks and demos. Prof. Perlin actively uses this project to teach his computer graphics class, which is why Chalktalk has such a rich library of sketches based around this topic.

But its ultimate destiny is as a prototype to answer an important question about the future: if or when AR technology becomes mainstream, how will it impact human language and communication?

If this kind of technology ever becomes commonplace, computer graphics and interaction won’t just be limited to a screen. We’ll effectively have the ability to place computer graphics all around us. If we’re describing a concept or idea, we won’t be limited to describing it with words or static images. We’d be able to play with the ideas by interacting with simple simulations live.

I first saw this project demoed in a recording of a talk given by Prof. Perlin near the end of 2014, when I was applying to grad schools. It single-handedly inspired me to add NYU to the list of universities I was applying to for grad school, and that decision shaped my life from that point on. I was accepted, started getting involved with the project during the end of my first year, and in my second year Prof. Perlin was kind enough to allow me to do a formal thesis related to it.

Focusing on a narrower sub-problem

While I was working with Chalktalk before my thesis, we’d occasionally get new interested users playing around with the interface. In fact, for a while, I was one of those new and interested users, being a novice to the system and its interface. These experiences revealed a couple of stumbling blocks for new users, and for my thesis I decided to focus on reducing one of those stumbling blocks.

As you can see in the animations above, Chalktalk has a feature that allows users to connect sketches together to send data from one to the other. This feature is crucial when you’re using Chalktalk to explain any sort of complex system, since it lets sketches be a small part of a much larger whole. But it had a problem.

See, Chalktalk is built on Javascript via WebGL. The objects that were being sent over the links were regular old Javascript data types: numbers, functions, objects, arrays, and so on. But Javascript is dynamically typed, so there was no guarantee that the kind of object your sketch was receiving was the kind of object you were expecting.

What this meant from the user’s perspective was that you could connect basically any sketch to any other sketch, regardless of whether the connection made any sense.

At best, this would do nothing when the two objects were connected. At worst, the receiving sketch would incorrectly interpret the data coming from the sending sketch, and things would break. Avoiding problems like this required some major defensive coding when creating sketches, and required the user to know exactly which sketches worked with each other.

The obvious answer to this, at least for computer programmers, is to implement a stronger type system.

The problem is, Chalktalk is optimized for flexibility and improvisation, because it’s meant for performances, presentations, and conversation. Creating a system that would artificially limit compatibility between sketches would have interfered with that improvisational feel, even if it did prevent problems from connecting incompatible sketches.

So the question that remained was this:

1. We wanted sketches to be able to have some assurances as to what kind of data they would receive, so that we could make sure things were compatible, and subtly inform the user when they were not.

2. But we also wanted to preserve flexibility and compatibility. In other words, if you connect any sketch to any other sketch, so long as there’s some reasonable interpretation for that connection, the connection should be allowed.

This differs from the requirements on the kind of type systems you see in most statically-typed modern programming languages. In those, the types are meant to help you prevent errors. In languages with strong static type systems, like Haskell, people often complain about “fighting the type checker”, but also say that once it compiles, and the types are all sorted out, it’s almost sure to run correctly.

These kinds of properties are desirable in a programming language, but we’re not working in one of those. How do we make a type system that gives us the kind of flexibility and compatibility you want in a presentation language?

An Atypical solution

The solution I came up with looks something like this. Imagine you’re connecting two different sketches together.

1. We’ll require each sketch to declare the kinds of types it can take in as input, and the kind of type it outputs. That way you know exactly what types you’re dealing with across that connection. The receiving sketch will always be guaranteed to receive an object of the type it specifies as input.

2. If the output type on the sending sketch and the input type on the receiving sketch are exactly the same, then you’re good! Send the data across.

3. If they’re not, try to see if you can do a conversion of the data from the output type to the input type. Be generous with conversions, because we’re optimizing for compatibility over safety. More on this soon.

4. If they’re not the same, and no conversion is available, warn the user with a little “X” on the end of their arrow, telling them that what they’re trying to do doesn’t make sense.

Of course, this raises the million-dollar question: how do you determine which types can be converted, and how are those conversions implemented?

Conversions

The first and most obvious way you can define conversions is by making an explicit conversion function. For example, you might define a conversion between Bool and Float by using 1.0 for true and 0.0 for false.

AT.defineConversion(AT.Bool, AT.Float, function(b) {
   return new AT.Float(b.value ? 1 : 0);
});

The obvious problem with this is that if you force developers to define this kind of function for every pair of types, then it blows up in your face, as you end up having to specify O(n²) conversion functions manually. This obviously doesn’t scale once you get past a certain number of types.

So the type system tries to make it as easy as possible to define conversions, even in many cases defining the conversion functions for you.

Intermediary conversions

Some conversions to have to be specified manually, and there’s not much of a way around that.

However, once you have a small number of conversions specified, you can start writing intermediary conversions: conversions that go from type A to B by converting from A to C and then C to B, assuming that conversions from A to C and C to B exist.

To give a more concrete example, if you have the above conversion from Bool to Float, and another conversion from Float to Int, then you can easily specify a conversion from Bool to Int like this:

AT.defineConversionsViaIntermediary(AT.Bool, AT.Float, AT.Int);

This doesn’t save you much code in this case, but it can be very useful in more complex types.

And although it’s somewhat dangerous, you can even specify wildcard intermediary conversions by replacing the first or last argument with null:

AT.defineConversionsViaIntermediary(AT.Bool, AT.Float, null);

What this means is “if you have a conversion function between Float and anything else, you can convert Bool to that other type by first converting to Float”.

You have to be careful and disciplined using these wildcards, because it loses you a lot of type safety. In fact, if you do it in all directions it effectively makes two types equivalent. But it still can be useful if you have two types that are similar enough that you can make these kinds of conversions with confidence, and it allows you to treat some types, like Float, as “hubs” through which many other conversions flow.

Generic type conversions

This type system supports generic types, as any good static type system should. Generic types have a lot of machinery to help them implement as many conversions as possible automatically. As the type system currently stands, if you have a generic type such as Generic(T, U, V), you can do any or all of the following each with a single function definition:

• Define all conversions from Generic(T, U, V) to T, U, or V, regardless of what those types actually are,

• Define all conversion from any of T, U, or V, to Generic(T, U, V), again for any values of T, U, or V, or

• Define conversions from Generic(A, B, C) to Generic(T, U, V) regardless of what the type parameters are.

Each of these three functions can be optionally paired with another function that determines whether a conversion like that would be valid, but overall they’re meant to be very broad and allow as much free-form conversion as possible. For example, when defining the latter function, for converting between different instances of the same generic type, by default it applies whenever the type parameters are convertible to their equivalent parameter in the new generic type. For example, using our previous example, Generic(A, B, C) would be convertible to Generic(T, U, V) whenever A is convertible to T, B to U, and C to V.

What it all adds up to

What this ends up giving you is something of a type graph. Rather than defining a hierarchy of types that allows safe conversion in only one direction, as many conventional languages and some unconventional languages tend to do, the topology of the type system ends up being a lot more flexible.

If you look at this from a programming language perspective, it seems like madness: why on earth would you ever want to convert a number into a 3D model? Why would you allow for such lossy conversions? Wouldn’t that cause bugs in your program? It borders on absurdity, and Javascript is rightfully maligned for implementing even just a subset of this kind of behaviour, where "2" + 2 == "22" but "2" * 2 = 4.

But we’re not making a programming language. We’re making a language where you can play. And in that kind of a space, a bit of absurdity is totally fine. This is why I called the type system Atypical.

You are what you optimize for

In the end, the core lesson from this actually ended up being reminiscent of some of the things I learned back in my engineering degree at the University of Toronto. In my engineering design classes, we had the idea drilled into our heads that you have to define your requirements first, and your requirements should shape the structure of the design. Your requirements define what you should and should not care about, what you optimize for, and what decisions you’ll be making.

And it can be interesting to revisit those requirements and optimizations, to work in a world where you have to optimize for something else. It’s an underappreciated tactic in today’s technology environment, and it can lead to some interesting new approaches to well-known topics.

More info

If you want to play with this yourself, Chalktalk is now open source. You’ll find this experimental type system in the type-system branch, at least for now.

And if you want a quick three-and-a-half-minute overview of the project and the things this article talked about, here’s a video. Feel free to share it with anyone who’s interested.