Reading 26: Little Languages I
|Safe from bugs||Easy to understand||Ready for change|
|Correct today and correct in the unknown future.||Communicating clearly with future programmers, including future you.||Designed to accommodate change without rewriting.|
In this reading we will begin to explore the design of a little language for constructing and manipulating music. Here’s the bottom line: when you need to solve a problem, instead of writing a program to solve just that one problem, build a language that can solve a range of related problems.
Formula data type from Recursive Data Types:
Formula = Variable(name:String) + Not(formula:Formula) + And(left:Formula, right:Formula) + Or(left:Formula, right:Formula)
In the parlance of grammars and parsers, formulas are a language, and
Formula is an abstract syntax tree.
But why did we define a
TypeScript already has a way to represent expressions of Boolean variables with logical and, or, and not.
For example, given
q, we can just write:
The answer is that the code expression
p && q is evaluated as soon as we encounter it in our running program.
And(...) is a first-class value that can be stored, passed and returned from one function to another, manipulated, and evaluated now or later (or more than once) as needed.
Formula type is an example of representing code as data, and we’ve seen others.
Here is a first-class function:
When we define an abstract data type, we’re extending the universe of built-in types provided by TypeScript to include a new type, with new operations, appropriate to our problem domain. This new type is like a new language: a new set of nouns (values) and verbs (operations) we can manipulate. Of course, those nouns and verbs are abstractions built on top of the existing nouns and verbs which were themselves already abstractions.
And it’s the difference between writing an integer addition function and devising a
IntegerExpressiontype to represent integer arithmetic expressions — and store them, manipulate them, rearrange them, evaluate them, and so on.
This kind of language is called a domain-specific language (DSL), because it solves problems in a narrower domain than a general-purpose programming language like TypeScript or Python. DSLs can be further classifed into external and internal. External DSLs have custom syntax and semantics, independent of any general-purpose programming language. Examples that we’ve already seen in this class include regular expressions, ParserLib grammars, and the language of problem set 3. By contrast, an internal DSL is embedded in a general-purpose programming language, using the syntax and abstraction mechanisms of the host language rather than inventing its own. First-class functions and functional objects enable us to create particularly powerful internal DSLs because we can capture patterns of computation as reusable abstractions. The music language that we’ll develop in this class and the next is an example of an internal DSL.
In class, we will design and implement a language for generating and playing music.
We’ll first see how to write a program to play music with the MIDI synthesizer.
Then we’ll begin to develop our music language by writing a recursive abstract data type for simple musical tunes.
We’ll choose a notation for writing music as a string of characters, and we’ll implement a parser to create instances of our
MidiSequencePlayer uses the Jazz MIDI API to play sequences of notes.
This code is somewhat involved, and you don’t need to understand how it works.
MidiSequencePlayer implements the
SequencePlayer interface, allowing clients to use it without depending on the particular MIDI implementation.
We do need to understand this interface and the types it depends on:
addNote : SequencePlayer × Instrument × Pitch × number × number → void (SequencePlayer.ts) is the workhorse of our music player.
Calling this method schedules a musical pitch to be played at some time during the piece of music.
start : SequencePlayer → Promise<void> (SequencePlayer.ts) actually plays the music.
Until we call this method, we’re just scheduling music that will, eventually, be played.
Instrument is an enumeration of all the available MIDI instruments.
Pitch is an abstract data type for musical pitches (think keys on the piano keyboard).
Read and understand the
If MIDI does not work on your machine in Node.js, you can try using a web browser instead.
npm run WebServer, browse to the
localhost URL it prints out, follow the ScaleSequence link, and click run main!
To start, we’ll define the
Music type with a few operations:
notes : String × Instrument → Music (MusicLanguage.ts) makes a new Music from a string of simplified abc notation, described below.
duration : Music → number (Music.ts) returns the duration, in beats, of the piece of music.
play : Music × SequencePlayer × number → void (Music.ts) plays the piece of music using the given sequence player.
notes will be a factory function; rather than put it in
Music (which we could do), we’ll put it in a separate file:
MusicLanguage will be our place for all the functions we write to operate on
ScaleSequence, the first concrete variant that might jump out at us is one to capture the information in each call to
addNote: a particular pitch on a particular instrument played for some amount of time. We’ll call this a
The other basic element of music is the silence between notes:
Finally, we need a way to glue these basic elements together into larger pieces of music. We’ll choose a tree-like structure:
secondare any music.
This tree structure turns out to be an elegant decision as we further develop our
Musictype later on. In a real design process, we might have had to iterate on the recursive structure of
Musicbefore we found the best implementation.
Music = Note(duration:number, pitch:Pitch, instrument:Instrument) + Rest(duration:number) + Concat(first:Music, second:Music)
Music is an example of the composite pattern, in which single objects (primitives, e.g.
Rest) and groups of objects (composites, e.g.
Concat) all belong to the same type, so they can be treated the same way.
The recursive data types we’ve been using, like
Formula, have been examples of the composite pattern.
HTML’s Document Object Model (DOM) relies heavily on the composite pattern: there are primitive elements like
<input>that don’t have children, and composite elements like
<span>that do contain other elements as children. All of them implement the common
The composite pattern gives rise to a tree data structure, with primitives at the leaves and composites at the internal nodes.
playoperation is also an instance method; we’ll discuss it below under implementing the player.
We’ll discuss the
notes operation, implemented as a static method in class
MusicLanguage under implementing the parser.
To avoid representation dependence, let’s add some additional factory functions for building
note : number × Pitch × Instrument → Music (MusicLanguage.ts)
rest : number → Music (MusicLanguage.ts)
concat : Music × Music → Music (MusicLanguage.ts) is our first producer operation.
We will write pieces of music using a simplified version of abc notation, a text-based music format.
We’ve already been representing pitches using their familiar letters. Our simplified abc notation represents sequences of notes and rests with syntax for indicating their duration, accidental (sharp or flat), and octave.
C D E F G A B C' B A G F E D C represents the one-octave ascending and descending C major scale we played in
C is middle C, and
C' is C one octave above middle C.
Each note is a quarter note.
Read and understand the specification of
If you’re not familiar with music theory — why is an octave 8 notes but only 12 semitones? — don’t worry. You might not be able to look at the abc strings and guess what they sound like, but you can understand the point of choosing a convenient textual syntax.
notes : String × Instrument → Music (MusicLanguage.ts) splits the input into individual symbols (e.g.
We start with the empty
rest(0), parse symbols individually, and build up the
parseSymbol : String × Instrument → Music (MusicLanguage.ts) returns a
Rest or a
Note for a single abc symbol (
symbol in the grammar).
It only parses the type (rest or note) and duration; it relies on
parsePitch to handle pitch letters, accidentals, and octaves.
parsePitch : String → Pitch (MusicLanguage.ts) returns a
Pitch by parsing a
pitch grammar production.
You should be able to understand the recursion — what’s the base case? What are the recursive cases?
play : Music × SequencePlayer × number → void (Music.ts) plays the piece of music using the given sequence player after the given number of beats delay.
If we define
play in that way, we won’t be able to play sequences of notes over time unless we actually wait during the
play operation, for example by setting a timer.
Our sequence player’s
addNote operation is already designed to schedule notes in the future — it handles the delay.
Just one more piece of utility code before we’re ready to jam:
MusicPlayer plays a
Music using the
Music doesn’t know about the concrete type of the sequence player, so we need a bit of code to bring them together.
Read and understand the
That’s not very exciting, so read
examples/RowYourBoatInitial and run it using
npm run RowYourBoatInitial.
You should hear Row, row, row your boat!
Can you follow the executation of the code from calling
notes(..), to returning an instance of
Music, to the recursive
play(..) call, and then individual
If you have trouble understanding the flow of the code, using a debugger to step through the code may help.
diagram updates paused: cannot parse Snapdown input
const r: Music = rest(1); const p: Pitch = Pitch.make('A').transpose(6); const n: Music = note(1, p, Instrument.GLOCKENSPIEL); const s: Array<Music> = [r, n];
Playing Row, row, row your boat is pretty exciting, but so far the most powerful thing we’ve done is not so much the music language as it is the very basic music parser.
Writing music using the simplified abc notation is clearly much more easy to understand, safe from bugs, and ready for change than writing page after page of