Trevor Oakes

Programming Languages and Sheet Music

If the juxtaposition seems strange to you, I agree with you that at first glance there doesn’t seem to be much in common between the two. If you’ve chalked it up the strangeness of the author and moved on to something else I wouldn’t blame you, but I still think you’re wrong.

Programming languages and sheet music share some interesting historical similarities besides their importantance as mathematically grounded tools for capturing and spreading ideas. Very different ideas.

A Very Shory History of Musical Notation and Programming Languages

Music is old. Really old. It shouldn’t be surprising then that written methods of describing music are also old. The oldest surviving example of musical notation, a mesopotamian cuneiform tablet (i.e. modern day Iraq), is about three thousand years old. Other examples of early musical notations also survive from Greece, the Byzantine Empire, India, China, Russia, Japan, Persia and Indonesia among many other countries.

The musical notation that we all know, however, comes from Western Europe, developed by monks in the abbeys and monastaries of the middle ages. Although originating to notate religious music, the modern staff notation became codified and spread with the rise and spread of classical music, and this is the musical notation system we have with us today.

Programming languages as we think of them did not arrive until much later, but that doesn’t mean that the history of programming languages started in the 1940’s with the first electronic computer.

No, that date probably belongs at least as far back as 1801 due to the creation of the Jacquard Loom. Besides the mechanical machine there was a language of sorts. Instead of code as bits or text files there where cards with holes punched in them. Instead of computing information it creates you a rug or some fabric. This invention, and its method of programs “written” on cards with punched holes, inspired Charles Babbage in his design of his computing machines: the Difference Engine and the Analytical Engine.

Neither of these was actually completed in his lifetime. A fully built Difference Engine wasn’t completed until 1991 and work only began very recently on a 10 year multi-million dollar project to build a working version of the Analytical Engine. The Analytical Engine as designed is the first instance of a Turing complete machine, making Ada Lovelace’s program to compute a sequence of Bernoulli numbers the first program written in a Turing-complete language. (For further reading I submit to you: A humorous and fictional account of Babbage and Lovelace.)

Unfortunately for Babbage, failing to get your brilliant ideas working in the real world doesn’t help you much to convince people that they actually are brilliant. Hence the idea of a general purpose computing machine (and the languages needed to program them) had to wait for more than 50 years to be realized. That doesn’t mean that different programming languages and computing machines didn’t arise in the meantime.

For example the autopiano, invented in 1876, had a sort of language for describing how to play music, while Herman Hollerith used punch cards to encode the 1890 census and then quickly tabulate the results. A steady progression of mechanical calculating machines eventually led to the creation of the “modern,” electrically powered computer in the 1940’s and with it various assembly languages, and then the explosion of general purpose languages that happened after the creation of Fortran, Lisp and Algol.

Wait a second! Back up a bit. A language, albeit a very limited one, that tells a piano how to play music? We’re back to musical notation again. This time, a sort of hybrid between the two: a human illegible notation for music and a very, very limited language for programming an autopiano. Some may contend that this is not programming, but it is an encoding of a series of steps to “compute” a song.

At this point it might be helpful to describe what a programming language is. A programming language allows you to compute the values of functions, or the results of algorithms, a series of well-defined steps. The duality of functions, mathematical functions, and series of steps is not a coincidence. Computation, and therefore programming languages, are intertwined with math. In a bit, we’ll see how exactly.

But first let’s see what math has to do with sheet music.

The Mathematical Basis of Musical Notation

The most obvious example is that there are numbers written on every piece of music giving the timing: 4/4 or 3/4 or 6/8. Music implies repetition of sound, but it only sounds good when it forms some sort of regular pattern. Sheet music breaks that up into wholes, or measures, and describes them using meter. The sheet music also usually has a recommeded timing, or length of certain kind of note. A 3/4 time means that there are three major beats in a measure, and 1 whole beat is marked as a quarter note. Why not as a whole note? I don’t know.

The notion and therfore the notation of rythym is inextricably connected with regular repetitions, and those sound good when they come at regular intervals and they form some relation to each other. In fact the notes are a form of binary fractions. You could represent the length of notes in binary:

Note Name “Binary”
Double Whole Note 1000000000
Whole Note 0100000000
Half Note 0010000000
Quarter Note 0001000000
Eigth Note 0000100000
Sixteenth Note 0000010000
Thirty-second Note 0000001000
Sixty-fourth Note 0000000100
Hundred Twenty-Eighth Note 0000000010

Rests can also be encoded in the same manner. (Wikipedia has a table of these notes, the rests and what they look like for those who are fascinated by music but not familiar with its notation. Nice to meet you too, nobody.)

Then you can think of a dotted note as adding a version of itself right-shifted by one bit: dotted_note = undotted_value + (undotted_value >> 1). A quarter note 0001000000, when dotted,becomes 0001100000. Two tied notes can be added together: a whole note 0100000000 tied with a quarter note 0001000000 becomes 0101000000.

This system is made more complicated when tuplets are introduced but the ratios and the math remain. These are only the easiest to see. Because music is based on sound, the mathematics of sound also affect the notation of music, a topic way out of my comfort zone. Besides the application to musical notation, branches of mathematics, such as set theory and abstract algebra, are also related to music theory, at least, according to wikipedia.

The Mathematical Basis of Programming Languages

The Church-Turing Thesis

Early in history of computing, mathematicians wanted to figure out what exactly computation means. They proposed different ways of modelling computations. Alan Turing developed a machine that provides the canonical definition of algorithms. If it runs on a Turing machine it is an algorithm or “an effective method to calculate a function, expressed as a finite list of well-defined instructions.” An effective method means that the method always: gives an answer-the correct answer, can complete the calculation in a finite number of steps, and works for all instances of a class of problems.

Other mathematicians came up with ideas rooted in recursive mathematical functions. For example Alonzo Church created the lambda calculus, the repeated application of functions. Other models for computability were also created, but it was shown that these are equivalent. This thesis, the Church-Turing Thesis, expresses the idea that the idea of computable functions, embodied in Church’s lambda calculus, is exactly equivalent to the idea of algorithms, embodied in the Universal Turing machine. Both rely on the idea that given infinite time and space, they can solve (and not solve) the same functions. Lambda calculus relies on infinity through recursion, while the Turing Machine invokes infinity by requiring an infinite tape.

There are other theories (recursion, reckonable in the system S1, canonical systems, register machine, combinatory logic, pointer machine, cellular automata) are also considered by the Church-Turing thesis to be equivalent to each other. (Sidenote: Since the idea of an algorithm is the intuitive definition of mechanical computation and not a formal idea, the Church-Turing thesis cannot be proven. i.e. a proof cannot show that a formal system, a Turing machine, is equivalent to an intuitive idea, mechanical computation.)

Since programming languages encode programs, whether they are thought of as algorithms as in imperative languages, or as functions in functional languages, or logical contraint resolution in logical languages, or any other way of computing a function, they are computing and manipulating mathematical objects.

The Curry-Howard Correspondence

This is another way that programming languages, like musical notation, are steeped in math: type systems.

Simply put, a typed computer program is exactly equivalent to a logical proof. Programs are proofs and types are logical propositions. This allows you to think about the problem in whatever way is most helpful at a time, and switch back and forth as needed. This probably seems very unexpected, but it can be very useful.

This means that proofs can be written in a language like Coq, checked by computer and run. In addition, types can be used to prove different properties of programs - for example that your kernel is free of implementation bugs such as deadlocks, livelocks, buffer overflows, arithmetic exceptions or use of uninitialised variables.

So, unless you are programming in assembly or the untyped lambda calculus, the Curry-Howard correspondence grounds your programming language in mathematical theory, just as musical notation is.

“Thought Stuff”

Why is programming fun? What delights may it’s practitioner expect as his reward?

[T]here is the delight in working in such a tractable medium. The programmer, like the poet, works only slightly removed from pure thought-stuff. He creates his castles in the air, from air, creating by exertion of the imagination. Few media of creation are so flexible, so easy to polish and rework, so readily capable of realizing grand conceptual structures…

Fred Brooks The Mythical Man-Month

As the English language was to Shakespeare so is the programming language to a programmer or musical notation to the composer, a means to capture and describe thought stuff.

These three things have something in common, a series of abstract symbols and associated meanings. Instead of pictograms for things, actions and descriptions we have words made up of abstract symbols called letters. Then we combine these groups of abstract symbols into groups of groups of symbols called sentences. With just 26 symbols we have created 250,000 words. And with all these words we can create an infinite number of syntactically and grammatically valid sentences. With only 26 symbols we can still create an infinite number of words, although I’m not sure what “sinfalderogalteblishanieraphtholology” or “qqqqqqqqqqqqqqqqqqqqqqqqqqqqqq” should mean.

It is strange and fascinating that a few simple rules, a finite grammar, can create infinite possibilities. In the same way that we can create an infinite number of sentences or even words for the english languages, there are an infinite number of programs for any programming language, or songs that can be captured by a musical notation. Our job is to capture these ideas, explore the space of interesting and beatiful english, songs and programs.

There’s a reason though that programming fascinates me more than others and I think the Fred Brooks captures pretty well the reason why. I’ll let Fred explain.

Yet, the program construct, unlike the poet’s words, is real in the sense that it moves and works, producing visible outputs separately from the contruct itself. It prints results, draws pictures, produces sounds, moves arms. The magic of myth and legend has come true in our time. One types the correct incantation at the keyboard, and a display screen comes to life showing things that never were nor could be.

Programming then is fun because it gratifies creative longings built deep within us and delights sensibilities we have in common with all men.

Fred Brooks The Mythical Man-Month