This is short story about a student finding something helpful
in class and making my day, preceded by a long-ish back story.
In my programming languages course yesterday, I did a session
on optimization. It's a topic of some importance, and students
are usually interested in what it means for an interpreter or
compiler to "optimize" code. I like to show students a
concrete example that demonstrates the value of an optimization.
Given where we are in the course and the curriculum, though, it
would be difficult to do that with a full-featured language
such as Python or Java, or even Racket. On the other end of
the spectrum, the little languages they have been implementing
and using all semester are too simple to benefit from meaningful
optimization.
I found a sweet spot in between these extremes with
BF.
(Language alert!) I suppose it is more accurate to say that
Eli Bendersky found the sweet spot, and I found Bendersky's
work. Back in 2017, he wrote a series of blog posts on how to
write just-in-time compilers, using BF as his playground.
The first article in that series
inspired me to implement something similar in Python and to
adapt it for use with my students.
BF is well-suited for my purposes. It is very simple language,
consisting of only eight low-level operators. It is possible
to write a small interpreter for BF that students with only a
background in data structures can understand. Even so, the
language is Turing complete, which means that we can write
interesting and arbitrarily complex programs.
The low-level simplicity of BF combines with its Turing
completeness to create programs that are horribly inefficient
if they are interpreted in a naive manner. There are many
simple ways to optimize BF programs, including creating a
jump table to speed up loops and parsing runs of identical
opcodes (moves, increments, and decrements) as more efficient
higher-level operators. Even better, the code to implement
these optimizations is also understandable to a student with
only data structures and a little background in programming
languages.
My session is built around a pair of interpreters, one written
in a naive fashion and the other implementing an optimization.
This semester, we preprocessed BF programs to compute a table
that makes jumping to the beginning or end of a loop an O(1)
operation just like BF's other six primitives. The speed-up
on big BF programs, such as factoring large numbers or
computing a Mandelbrot set, is impressive.
Now to the story.
At the end of class, I talk a bit about
esoteric languages
more broadly as a way for programmers to test the boundaries
of programming language design, or simply to have fun. I get
to tell students a story about a four-hour flight back from
OOPSLA one year during which I decided to roll a quick
interpreter for
Ook
in Scheme. (What can I say; programming is fun.)
To illustrate some of the fun and show that programmers can be
artists, too, I demo programs in the language
Piet,
which is named for the Dutch abstract painter
Piet Mondrian.
He created paintings that look like this:
That is not a Mondrian, but it is a legal program in the Piet
language. It prints 'Piet'. Here is another legal Piet
program:
It prints "Hello, World". Here's another:
That program reads an integer from standard input, determines
whether it is prime or not, and prints 'Y' or 'N'. Finally,
how about this:
If you are a certain age, you may notice something special about
this image: It is made up exclusively of Tetris pieces. The
program prints... "Tetris". Programming truly is an art!
One of my students was inspired. While reviewing the session
notes, he searched for more information about Piet online and
found
this interactive editor.
He then used it to create a Piet program in honor of a friend of
his who passed away earlier this semester. It prints the Xbox
gamertag of his late friend. In his email to me, he said that
writing this program was therapeutic.
I'm not sure one of my class sessions has ever had a more
important outcome. I'm also not sure that I have ever been
happier to receive email from a student.
This has been a tough year for most everyone, and especially
for students who are struggling with isolation and
countermeasures against a nasty virus. I'm so glad that
programming gave one student a little solace, at least for
an evening. I'm also glad he shared his story with me.