Compiler Writing Interview
Recent Interview on my Compiler Writing
Matt, when did you start writing compilers?
I guess the first time I wrote any parsing and language semantics coding was at University with Peter Henderson in his “Lisp and Language Semantics” course. It was for the die-hard programmers. It kickstarted my fascination with being able to define and implement one’s own programming language. It was my first encounter with functional programming as well. I have always been interested in creating ways to make programming more efficient and effective. I’m sure it is a shared journey for many programmers. Once you adopt the abstraction of programming control flows, if-then-else, while-loops, etc., you lose interest in using goto’s to do the same thing. In one programming language, you encounter abstractions like modularity and being able to define abstract data types; you always want to use that technique, regardless of the language you are using. The ultimate path is being able to write your own language translator, either an interpreter or a compiler. It’s raw power.
So, that was in an academic setting. What about in industry?
It turned out to be a short time after that at Joyce Loebl, a then instrument manufacturer. I was writing systems software for bit-sliced embedded image processing machines. This was in the 1980s. They were being sold for various applications as programmable machines in automated analysis. We needed to create a programmable interface for users to automate the image analysis. We had an early Apple II E development environment with USDC Pascal, and I got to writing a rudimentary compiler-and-interpreter pair based on Lisp. It is pretty straightforward to write a Lisp recursive decent parser in Pascal. The Apple II E was an excellent machine, but we had to keep pressing the chips back into their sockets!
That sounds like quite a solo effort. What other experiences did you have? Any more extensive commercial efforts?
Later in the 1980s, I got to do a dedicated compiler construction gig at the Dr. Neher Laboratorium in Leidschendam, Holland. It certainly was a team effort. I got to write some of the boot-strap CHILL compiler in Pascal and then do it all again using CHILL as the source language. The ‘Lab was keen to have early experience using their language. CHILL was an excellent language then and has many more abstractions than Pascal, say. It is used sparingly now. Telecommunications organisations often lead in software engineering. They have the challenges and the resources to address them. After finishing the compiler, I worked on a symbolic debugger for CHILL.
Looks like you enjoyed that. Have you stayed with compiler writing ever since?
No, I have worked quite a lot in systems and as an architect since then, though I do get to do compiler writing from time to time. I travelled to Australia after Holland, and there was little of that type of work around then. There still needs to be. Eventually, I worked for a telco’ again, Ericsson, initially in technical architecture but later in their development centre in software engineering. This was around the year 2000. I prototyped some session initiation protocol (SIP) proxy, redirection, registration and presence servers. It was the early days of SIP, and the Ericsson Development Lab’ wanted to get experience with the technology. That’s a lot of language parsing and implementing the semantics. That was a solo project, but after that, I worked in a team implementing a production SIP protocol stack in C++ destined for Ericsson’s kit. In compiler work at the Lab’ where we had a Backus Naur Form (BNF) description, I used Lex, YACC and the GNU Flex and Bison, which had some features that YACC lacked. I first came across BNF at my University, which used Algol-W as the teaching language, and I remember everyone was encouraged to get the BNF description of that language. Funny how things come around.
Fascinating, but let’s wrap this up. What’s your most recent experience with compiler writing?
That’s a current project with Alive Drumming. Alive Drumming came about through a realisation that we needed a more convenient, efficient way to arrange play-along backing tracks based on the high-quality audio of top-session drummers.
Aren’t there lots of those types of programs around already? There are some top-rated play-along apps that musicians use.
Yes, there are. That’s true. But not ones that use high-quality audio from top session drummers. You are probably thinking of apps like iRealPro, which is excellent at what it does. But that’s a generator of audio from MIDI data. You give it a description of the chord chart, and the app generates sound based on that chart with a small group of instruments, say drums, bass, and piano. This is helpful when learning tunes, and the musical quality is good enough to use for that purpose. But, say you just selected the drums and turned bass and piano down to zero, then playing along to that track is less engaging than playing along to Alive Drumming’s Song Rhythm Tracks. There is a big difference in the musicianship of the drumming, the realism and the selection of styles. For just drumming, you would be unlikely to want to continue with the iRealPro for very long, but with Alive Drumming’s Song Rhythm Tracks, you get a much more enjoyable musical experience and a more extensive selection of rhythms to choose from. We are biased, of course, but the distinction is there.
But wouldn’t I want the whole band and not just drumming accompaniment?
It’s a case of horses for courses. There’s much diversity in play-along music: the MIDI generators, like iRealPro, and then the training play-alongs that include full lead sheets, like the Jamey Aebersold‘s, through to meant-for-performance ones like Bobby’s Backing Tracks and others. There is room for all of these and more in the market.
OK, fair enough. But what of the compiler?
Right, so back to efficiency and convenience. First, if it is a drumming track, you must avoid having to base it on a full chord chart. Drummers don’t play harmony. So, what could you use instead? Well, musicians sometimes refer to the form of a song. They say it is an AABA tune or a 16-bar blues or 32-bar A1A2, or whatever, so we should be able to provide a list of forms and have a user choose which form they want for their play-along track. That’s quicker than entering a complete chord chart.
OK
Next, why not let them describe the track’s arrangement by saying, “I’ll have four repeats of that form with an 8-bar introduction section”. Once we know the audio we will use, we can create the entire track based on this. That’s pretty efficient from the end-user perspective.
Sure. Is that the basis for the compiler, then?
Yes. Well, it started like that, and then it grew. We can convert the song form into a sequence of sections so that 32-bar AABA would be 8A, 8A, 8B, 8A. All our recordings of drummers have ‘A’ and ‘B’ style drumming. So, the previous arrangement could result in
2-bar count-in,
8A, // Using 'A' style for the intro section
8A, 8A, 8B, 8A, // Using 'B' for the bridge section, only
8B, 8B, 8B, 8B, // Middle choruses (repeats) using 'B's
8B, 8B, 8B, 8B,
8A, 8A, 8B, 8A, // Final chorus, returning to the 'head' feel
2-bar drummer's ending
The advantage here is that the user just had to specify the song form, the number of repeats and the size of the introduction section, and the tooling does the rest to create a play-along backing track using high-quality audio. You always get count-ins, middle chorus variations and drummer’s endings. Also, this type of description is the lingua franca amongst musicians for describing the form and arrangement. We try to avoid introducing any new language but adopt what is already used.
So, do you think you need a compiler for that?
Yes, it’s a pretty rudimentary one, initially, but what I just described isn’t enough in all circumstances. Not all songs use one of the standard forms. There is infinite variation possible in song form and arrangement. So, while still embracing the convenience I described, we also need to accommodate all song forms and all arrangements. This leads to a simple general-purpose algebra for describing these based on section lengths and A/B drumming style.
Consider the arrangement to be an infinite comma-separated sequence of –
<number repeats> <"*"> <section sequence>
where
<section sequence> :: = <section> | <section sequence> <section>
and
<section> ::= <number> | <divider> <number>
<divider> ::= "|" | "/"
So we can parse any of, say,
3 * 8|8/8|8 // 3 repeats of 32-bar AABA form
16|16 // A single chorus of 32-bar AABA
8 , 4 * 8|8/8|8 // An 8-bar intro section, 4 repeats of AABA
/8|4, 6 * 8|4|4|4, 2 * 8/8 // A more involved arrangement.
So, the compiler,
parses this user format language, creating the intermediary code described previously, e.g. 8A,8A,8A,8B,8A,8A,8A,8B,8A,8A,8A,8B,8A,8A,8A,8B,8A, emits executable code (not shown) from this intermediary code to build a track Finally, this code is executed, building the track. More compiler optimisation is also involved, including peep-hole optimisation of the executable code. The executable pseudo-randomly selects audio from a database to be combined into the arrangement. Whenever we do use the same audio, we don’t need to repeat the selection, so that code is peep-hole optimised.
I see. What tooling did you use to create this?
The creation of the backing track necessarily had to be server-based. The audio database is vast, so we could not consider deploying it on a mobile device. We wanted a rock-solid server infrastructure, and my experience with the mission-critical software stack developed by Ericsson, Open Telecom Platform (OTP), led me to consider Elixir OTP. I had some experience with Erlang at Ericsson, and Elixir is based on that with a much more advanced language spec. I enjoy Elixir. It’s a great language and is getting more and more adopted. I did a recursive decent parser, which is all that is required in such a small language where the programs are never going to get big. Everything was done in Elixir except the low-level audio splicing and dicing, where I used an external library.
Is it complete?
Yes, it is in production and working well. We are considering some enhancements to it, adding new arrangement features.
Thanks for sharing your experiences in compiler writing. Are you open to taking on new assignments, and if so, where should folks contact you?
Yes, I am. I love this type of work, and with telecommuting, I can deliver work anywhere in the world. I can contribute to compiler writing and other software toolchain developments. I also have experience in embedded real-time software and automation. I can be contacted via email at mattharg@itchy.studio. Thanks.