Copyright 2016 The Go Authors. All rights reserved.
Use of this source code is governed by a BSD-style
license that can be found in the LICENSE file.

Full talk text for https://talks.golang.org/2016/prototype-your-design.pdf.

Prototype your design!
Robert Griesemer
dotGo2016, Paris

[2]
Any professional software setting has some design process in place; and the goal is always the same: One wants to make sure a design is good before implementation starts. The reason is simple: The later mistakes are caught, the more costly they are.
The approaches are usually quite similar, at least when looking at the broad strokes: There’s some form of a design document, the “specification” of the software to be built. There is feedback from experts and design reviewers; and there is also some form of iteration of the design.
Often however the design process is a “dry” exercise: The design itself doesn’t involve much if any software being created.
After all, we are professionals, not hackers anymore (well some of us), and we don’t write code without having thought about the design first. And the bigger the project, the more there is to design first. Or isn’t it?

[3]
But no matter the approach, a crucial question remains:
How can we tell that our design is good?

[4]
Anywhere else, outside of software, designing and prototyping are closely intertwined. There’s virtually no design of anything, clothes, furniture, appliances, cars, even architecture, that is not prototyped before going into production.
This graphic, taken from the Design School of Stanford University, illustrates the design process in five steps. After learning and defining a problem --- at Google we call this “focus on the user and all else will follow” --- designing is a repeated sequence of idea creation, prototyping, and testing. A designer does not think his way to good design, she builds her way to the design. In other words, designers are doers; we might even call them “hackers”.

[5]
So let’s shift gears for a bit and look at language design. Specifically, designing Go language support for numerical applications. As some of you may know, there is a concrete proposal, asking for multi-dimensional slice support in Go. The proposal is currently in the design phase.
Concretely, multi-dimensional slices permit the declaration of say a 2d slice, for instance a matrix. Using make, the 2d slice can be dynamically sized at run-time, and there is indexed access to its elements. This is not currently possible in Go.
While we do have arrays and slices, and while arrays do allow the definition of a 2d data structure that is laid out contiguously in memory, they are also statically fixed in size. Slices are dynamically sized but inherently one-dimensional.

[6]
The high level goals of the proposal are simple enough: Improved readability through nice notation such as multi-dimensional indexing, and ideally good performance due to a native implementation.
But there are still many open questions. The current design doc answers them, but how do we know that they are the right answers?

[7]
However, we can make some observations: It turns out that we can implement many aspects of multi-dimensional slices in Go already. For instance, we can define slice descriptors for 2d, 3d, 4d slices or matrices - it’s just an abstract data type after all.
Furthermore, we can define and implement operations on those data types, which is to say define methods on them.
That is, it’s already possible to write numerical code and play with the design of our API. Which is what the gonum community has been doing for years.

[8]
Unfortunately, there is a key missing feature, and that is nice notation. For instance, there’s simply no way in existing Go to write 2d index expressions using index operators.
The current work-around is based on accessor methods, such as At and AtSet, to get and set an element of a matrix, for instance.
But accessors like these make numerical code look clunky, perhaps even unreadable.

[9]
So how can we get around this notation problem? There are a few solutions:
1) We can say it’s not a problem - and some people will be ok with this.
2) We can actually change the Go language for the experiment; but that is likely way too costly.
3) Or, we could rewrite the source: Whenever we see say a[i, j], we change it into a method call a.At(i, j). Basically what the gonum folks are doing now, except they don’t start with the nice notation.
Ideally we want to have a tool, a source-to-source rewriter that does this for us.

[10]
Given such a rewriter, which is going to be our prototype of a real implementation, we can explore the design space before making any hard decisions.

[11]
So let’s design our rewriter. Since we want to rewrite index expressions into methods, we are going to allow two special method names, made up of a sequence of index and assignment operators. I’m calling them indexed getters and indexed setters.
I have also added the binary operator + to this list. We don’t need it for our proposal, but it’s easier to explain the rewriting process using + down the road, which why it’s here.
We also going to allow more than one index in index expressions.
This doesn’t make sense for the basic indexable data structures (arrays, slices, maps) we have in Go, of course. But it does make sense for our extended indexing operations.
And finally, we need to give some new meaning to index expressions. The idea is simple: Whenever we see an index expression where the indexed expression, say x, has a respective getter or setter, then the index expression is interpreted as the respective method call.
This last part is crucial, it’s the core of the rewriter. We’re going to look at it in more detail.

[12]
Now that we know what our rewriter is supposed to do, we need to come up with a suitable implementation.
Remember the goal: Since existing Go doesn’t understand our extended language, we are going to rewrite our extended programs into programs that are understood by current Go.
It turns out that is pretty straight-forward. First of all, we are going to rewrite our new operator method names into valid Go identifiers. We choose slightly unusual names to avoid any accidental naming conflicts. But the actual names are unimportant.
Similarly, we are going to rewrite index expressions into method calls as shown.
Luckily, the Go std library provides all the tools we need: We use the parser to read our source. The parser produces a syntax tree. It’s that tree that we are going to modify. After that we use the go/printer to generate the new source from our modified tree.
Since we do want to accept new method names and more than one index, we have to modify the parser a bit. But it turns out that is rather trivial, perhaps 20 lines of code or so.

[13]
Let’s consider this simple example. It’s based on rewriting the + operator so we can concentrate on the essential. But everything we’re doing here applies to indexing operators just as well.
On the left we see the code that we would like to write in our extended language. There’s a + method defined on Point. We can then use binary addition to add two points, with the effect that the + method is called.
The right shows the rewritten source. This is now regular Go that will compile and run.

[14]
Because we need to understand the structure of the source to do the rewriting, and the syntax tree reflects that structure exactly, we rewrite the syntax tree, not the source. Again, for simplicity we’re looking at addition.
The rewrite of the method name is trivial and not show here: it’s just changing a string.
The rewrite of binary operations is a bit more tricky: We can’t just rewrite every binary + operation. We can only do it if the left operand’s type implements a + method. Or, after rewriting of the method names, if it implements an ADD__ method.

[15]
Luckily, the Go std library helps us out again. We can simply invoke go/type on our syntax tree to compute the types for all our operands.
In a 2nd step we can then rewrite all binary additions where the left operand implements the ADD__ method.
Again, the same approach works for also indexing operators.

[16]
Let’s see this in action: Here we have a syntax tree for x + y + z after parsing. We don’t have any types at this point.

[17]
Now we run the type checker. As expected, it determines the types for our operands x, y, and z. But we also have a couple of types missing.
This is of course because the type checker didn’t know about + for x and y. After all, this is still a Go type checker. We could change it, but we really don’t want to touch it - it’s a complex beast.
Instead we simply assume the errors are due to the fact that we haven’t rewritten x + y.

[18]
So let’s just do the rewrite where we can. In our example, we will end up with a method call instead of the first addition, and the modified syntax tree shown on the right.

[19]
Now we’re turning the crank again for a second round of type checking. At this point we have more success and only one type is missing.

[20]
Again, we assume the missing type is due to a missing rewrite, so let’s determine what there is to rewrite...

[21]
… and rewrite once more. This leaves us with a final tree with all additions replaced by method calls.

[22]
How do we know we’re done? Well, we type-check again. This time there’s no errors anymore, so we do have a valid Go program that will compile --- maybe not run, but compile. We are in fact done!

[23]
With a concrete prototype implementation at our disposal, we can actually use it to judge our design: We can play with it and see how it feels. And if we don’t like it we can modify it and thus refine our design.

[24]
For instance, using our rewriter, we can now define a Matrix type, effectively representing a 2d slice, together with nice indexing accessors.

[25]
Given this Matrix type, we can implement matrix multiplication. I’m showing the core of the multiplication here: On the left, we have the code that we wish to write, and which current Go doesn’t understand, and on the right we have the rewritten version which is valid Go code.

[26]
Finally, I want to briefly raise an important point which I haven’t talked about yet: During the implementation of a prototype, one will invariable encounter the unexpected. In other words, questions will come up that we didn’t even know we should be asking.
Without a prototype, these same questions will come up much later, when it’s perhaps too late.

[27]
In our example, there was one surprise, at least to me: I found that indexing operators were so effective --- and in fact so cheap, syntactic sugar really! --- in addressing the specific notational problem, that one might indeed be wondering if that’s perhaps all that’s needed.
But that’s food for thought for another time…

[28]
I like to conclude with a couple of observations:
First of all, it turns out, not unexpectedly of course, that Go is a fantastic prototyping language. This is really why people say that Go brought back the fun to programming.
Secondly, prototyping is really the way to get to a good design: Instead of thinking about it, we can build towards it.
And finally: If we can prototype even language changes we can prototype anything.

[29]
Frederick Brooks said it best in his 1975 classic:
Plan to throw one away --- the prototype --- ; you will (throw one away), anyhow.

[30]
Thank you.
For all of you who would like to dig into my prototype a bit more: It’s all on GitHub, and it’s small. Perhaps 200 lines of code or so, scattered across a dozen commits that are fairly easy to digest. Have fun!