Types are shapes — a graphical programming exploration

Type theory is notoriously difficult to understand. To make it easier for beginners, MIT’s Scratch programming language uses shapes as a metaphor to explain types.

For example, in Scratch booleans (values that can be either true or false, yes or no) are hexagonal. Anything that takes a boolean as its input, like an if-statement or logical-and, has a hexagonal hole.

This is amazing because without understanding anything about booleans or type theory, it’s abundantly clear that the hexagonal blocks fit inside the hexagonal holes.

Shapes are valuable hints

Recently one of my new students was trying to make her character jump when the space bar is pressed. First she found the key space pressed? boolean block.

From there, she used the shapes to guide her to an if-statement.

But now she had a bug. If she tapped the space bar, her character jumped. But if she held it down, her character would fly. Upon reflecting, she realized that her character should only go up if the space bar is pressed and the character is on the ground.

It was amazing to watch her figure this all out, mostly on her own. She didn’t have to take a class on propositional logic or introductory programming. The shapes gave her everything she needed to express her ideas in code.

Some type theory

Let’s take a step back. What are types?

Types are the way computer scientists categorize different pieces of code. Some basic types:

• number
• text
• list

It’s important to make these categorizations because they describe the kind of operations you can do to each type of thing.

For example, you can add, subtract and multiply numbers. You can’t do the same to text or lists.

You can shorten, lengthen, or capitalize text. You can’t do the same to numbers or lists.

You can add things, remove things, or filter things in lists. You can’t do the same with numbers or text.

While writing code, if you mistakenly thought you could add a piece of text and a list together, the computer would use types to warn you against it. In a programming language like Haskell, it’d warn you in a way that’s almost impossible to understand:

Couldn't match expected type `(Int, Int) -> Point'
            with actual type `[(Int, Int) -> Point]'
The function `map' is applied to three arguments,
but its type `(Point -> (Int, Int) -> Point)
              -> [Point] -> [(Int, Int) -> Point]'

Scratch makes even greater use of types by encoding their information into shapes. This makes it physically impossible to put anything other than a boolean inside of a logical and. It prevents you from making type mistakes before you make them.

Even better, Scratch’s shapes hint at the way blocks are supposed to be used. The shapes push you from a type error and closer to what you’re looking for, as it did for my student.

Shapes in the real world

The types-as-shapes metaphor works so well because this is how shapes work in the real world. Shapes help us discover how things are used and what we can do to them.

For example, the type of water is liquid. One thing that the shape of liquid conveys is that it can’t be held in your hands.

So if you want to hold liquid, you need something with a shape that can contain it. It turns out that non-porous curved solids do the job. By looking at any cup, it’s clear from its shape that it’s of type “transporter of liquid.”

Polymorphism in the real world

So what the type of a plate? Its shape conveys that it holds solids and that it must also rest on a flat solid.

Clearly, cups and plates have different shapes for different uses. In other words, they have different types.

And yet, when I order a set of cups and a set of plates from Amazon, they are both delivered in the same cardboard box.

So what’s the type of a cardboard box? Its shape tells us that it can transport solids. So we realize that there are types within types. Cups and plates are both members of the solid type.

In computer science, we call this “polymorphism.” Two types are polymorphic when they are both members of the same super-type.

Polymorphic shapes for programming

Let’s bring this insight about polymorphism in the real world back to computer programming.

A list is a number of things of the same type. For example, 1, 2, 3, 4, 5 is a list. So is “once”, “upon”, “a”, “time”. However, 1, 2, “oops”, 4, 5 is not a list because you can’t have numbers and text in the same list.

How can we communicate this type-information with shapes?

Let’s start with the anything type. I choose to represent it with a wiggly border to convey its generic-ness. What is it? It could be anything!

The number type is a circle.

Now, let’s add in the list type, which will be represented by three sequential humps.

As you can see, each of the humps is anything-shaped to represent that anything can go into this list.

But if we have a list of numbers, each hump is number-shaped.

We see can see that only numbers can be added to a number list, because circles are the only shape that’d fit.

Filter

We can use polymorphic shapes can help explain the types of higher-order functions, like filter.

Filter takes a list and a boolean operation and gives you back a new list with only the elements that passed the operation. For example, if I filter even? over 1, 2, 3, 4, 5, I’d get back 2, 4.

In shapes, filter could look like this:

We can see from its shapes that filter inputs a list of any type and a boolean operation.

If we add a number list to filter, it’s shape would update.

This shape-change shows that filter outputs the same kind of list that it inputs.

We can fill in the boolean hole with an operation that checks if the item is even.

Map

Let’s do one more example: map takes a list and an operation, and gives you back a new list of each item after putting it through the operation. For example, if I map +1 over 1, 2, 3, 4, 5, I’ll get 2, 3, 4, 5, 6, because I add one to 1, add one to 2, add one to 3, add one to 4, and add one to 5.

In shapes, map could look like this:

As you can see, map takes a list of any type and an operation of any type, and returns a list of any type.

However, the moment I add addition to map, it’s shape changes. Now we can see that map will output a list of numbers.

Let’s add in a number list and finish it up.

Types are for beginners

The way they are currently implemented in programming languages, types are seen as an advanced feature for pro-users. Even worse, they’re considered by some to be a dead weight that slows programmers down as they code.

That’s entirely backwards.

When properly implemented as shapes, types are like bowling lane bumpers. They help beginners get up and running faster because they prevent gutter balls.

Even better, types-as-shapes effectively gives brand new programmers the intuition of veteran programmers. I can imagine a day where a 10-year-old girl who’s never coded in her life, makes effective use of a higher-order functions like map and filter within her first hour of coding.

Update 11/29/16

Brent Yorgey, my Haskell professor from college, responded to this post:

…what you are describing is not a general system of shapes for
higher-order types, but specific shapes/layout for a few specific
combinators like map, which works OK. I challenge you to come up with
a similar way to encode foldr though.

So I slapped it together: