-- Implementation.tioga
-- Last edited by: John Maxwell on: October 4, 1982 9:16 am

IMPLEMENTATION
Goals: a data structure for playing, editing, and displaying. Includes measure lines, etc.

The data structure is very important
Violations of structure:
In SMN, beams, measures break around lines and pages. Can't anticipate all violations.
pianoroll: really unstructured.
Simple invariants:
logical synchronisity. (Some violations in graphical display)
compare with voice biased data structure.
preservation of order (exception: justification).
linear vs. two dimensional. Factor out paging information.
Correlations:
position on page
beats from beginnings
seconds of playing time.
THE METAPHOR
linear structure with syncs
data structure for the page.
Separate data structure for beams, ties, and chords
ties notes together
Consequences of data structure:
Ease of programming algorithms
Ease of display on the screen
Ease of playing.
(what about text? lyrics? markings on notes? octava didn't fit well)
Extensions.



Why does the data structure matter?
 1) convenience of programming (playing editing, displaying)
 2) speed
 3) representational power

hierarchical vs. sequential data structure
 1) we want identical handling of mixtures of notation and pianorolls
 2) algorithms all have locality of reference
 3) we kept finding exceptions
 
description
 1) vertical cohesiveness
 2) handles all three domains (time, beats, and distance)
 

DATA STRUCTURE

This section describes the data structure that Mockingbird uses to represent a score. We felt that it was important to include this section because it took us a long time to get the data structure right. In this discussion we will describe our choice and explain why we think that it is the best design for our purposes.

The two designs that we considered were a structured, hierarchical data structure and an unstructured, sequential data structure. After much debate, we decided that the unstructured, sequential data structure was the better one. This decision surprised us, because at the beginning we thought that the hiearchical design was obviously better. However, experience has proven that the sequential design is vastly superior.

There are three considerations in designing a data structure: representational power, programming convenience, and speed.

Representational power is how much of the domain is covered by the data structure, and how easy it is to represent different aspects of the domain. We want to be able to represent as much of the different styles and forms of music notation as possible. However, just being able to represent things is not enough. It is also important that it be easy to represent things.

Programming convenience has to do with how easy it is to write algorithms that deal with the data structure. This depends a great deal on what the algorithms do. In Mockingbird we are mostly concerned with playing, editing, and displaying the score. (As opposed to structural analysis or automatic composition).

Speed also has to do with the algorithms chosen. Even if a data structure is convenient, it may not be efficient. Sometimes there is a trade-off between structural complexity, space usage, and speed. In Mockingbird, space wasn't very important but speed was. You can't support the illusion of editable music unless the display reacts crisply to edits the user makes.

There are many possible "hierarchical" data structures that might be used to represent music. I use the term loosely to describe a class of data structures which implicitly incorporate musical structure in the design. Thus you might imagine a data structure that had a separate part for each measure, or that had a separate data structure for each voice. A "sequential" data structure, on the other hand, is simply a sequence of undifferentiated entities. No attempt is made to incorporate musical structure into the design. Instead, it is up to the algorithms to infer the structure from the entities.

On the surface the hierarchical design is obviously better. If the musical structure is incorporated into the data structure, then you can guarantee a uniform interpretation over all of the algorithms. Not only that, but algorithms shouldn't have to do as much work, since the data structure handles some work for them.

This wasn't true in our case. The first problem we ran into is that we wanted a uniform representation for both common music notation and pianorolls. We wanted the user to be able to freely mix both types of music. We could envision him not only alternating sections of music notation with pianorolls, but even overlaying different sections. Although it is possible to keep a separate data structure for pianorolls, it would make the algorithms for editing, displaying and playing much more difficult.

The second problem was that it was hard to program algorithms that needed to know the proximity of things. This included all of our algorithms for playing, displaying, editing and justification. A simple example is redisplaying the score after a small edit has been made. For efficiency you would like to redisplay as little of the score as possible. But that depends on knowing what was near the entity that was edited. In the hierarchical design an entity that is close physically may be logically far away. It might be in another measure, or in another voice, or a in different chord, or on a different staff. Enumerating all of the possibilities is incovenient.

The last problem that we encountered was that we kept finding exceptions to the structure. Many of the rules of notation that we thought we inviolable turned out to have been violated by one composer or another as the need arose. A good example of this is the rule that says that all of the notes in a measure must add up to the time signature for that measure. Unfortunately, a musical phrase occasionally crosses a measure boundary. And if the phrase contains n-tuplets, it may temporarily violate the sanctity of the time signature (See figure xxx). A hierarchical design might make this example impossible.

(An important thought in designing a data structure for music is that we want a design that handles music as it is being edited, not just when it is finished. Throwing out the inconsistent music we found doesn't help, since a score may become inconsistent when the composer tries out new ideas. A good design should be tolerant of such inconsistencies.)

On the other hand, a sequential design doesn't have these problems. It allows pianorolls to be mixed with standard music notation because it doesn't know the difference. Both are just an ordered sequence of notes. Finding things that are nearby is easy, because things that are near one another on the screen are near one another in the data structure. And finally, since the data structure is so unstructured, it is flexible enough to handle a wide range of exceptions, perhaps some that we haven't even thought of.

A "sequential" data structure is simply a sequence of events ordered by time. An event might be a measure line, a collection of notes, a time signature, a clef switch, or a switch in the number of staffs per line. The events which contain notes are called "syncs" because they synchronize all of the notes in the event. (That is, all of the notes in the sync are played or displayed together.) The notes may belong to different voices or chords, but they all have the same "time".

Syncs are important because they keep simutaneous notes together while the score is being edited. Usually, if the composer plays a bunch of notes together, he wants them to stay together unless he explicitly says otherwise. If he inserts a new note at the beginning of a measure, he doesn't want the rest of the notes in that voice to move over. If any of the notes in a sync move, they should all move. (The justifier will occasionally move notes from one sync to another, but only under well defined circumstances.)

There are three meanings for the "time" of an event: time as seconds from the start of play, time as beats from the start of the score, and time as distance from the first measure line. Thus we might point to a particular note and say that it was two inches from the first measure line, or a second from the start of the sound, or four beats into the music.

Although these notions of time are very different, they co-exist nicely because they preserve order. If note A is played before note B, it is most likely drawn to the left of note B (modulo line breaks). Consequently, the same data structure can be used to display and play the music.

There are a few exceptions, however, which must be handled by the algorithms. Embellishments such as trills and rolled chords are played a little differently than they are drawn. Also, notes that are logically simultaneous may be separated slightly so the note heads can be distinguished. Generally, though, the correlation is good.

Beams and chords are handled separately from the rest of the data structure, since they are orthoganol to the structure of the score. That is, beams and chords are just horizontal and vertical parenthesis. Their only function is to group notes together. (If a beam or chord disappears from the score, it doesn't affect anything else.) Consequently, we can separate beams and chords from the main data structure. Each beam or chord knows what notes belong to it, and each note knows what beam or chord it belongs to. Beyond this, nobody needs to know that the beams and chords are there.

So far we have been assuming that a score was one long sequence of measures that appeared on one line. But since music is printed on a finite extent of paper, this long line must be broken up into shorter lines. Rather than make our data structure more complex, we decided to use a separate data structure to map between the linear data structure and the "two-dimensional" piece of paper. This data structure keeps track of how long each line is, how many lines fit on each page, how much of the line must be devoted to a key signature, and which section of the score goes on which line. Only the displayer and the justifier need to make use of this representation of the sheet; all of the other algorithms can manipulate the simpler data structure directly. Consequently, these algorithms are easier to program.

The meat of Mockingbird is the data structure used internally to represent music. All of the

The main data structure is an ordered sequence of elements called events. An event is a measure line, a time signature, a key signature, or a collection of notes that occur at the same "time".

When we first started to design the data structure, we were particularly concerned that it be flexible enough to handle music notation in many different states of editing. One could imagine a data structure that handled finished music well, but fell apart on a partially edited piece. For example, a poor data structure might lead to gaps in the sound of the music produced.

Looking at existing manuscripts made us realize that the rules of notation aren't sacred. Like users of natural languages, composers are happy to violate the conventions of notation if it means that their ideas will be expressed better. Notation is to serve the composer, not the other way around.

We also wanted to be able to freely mix pianorolls with standard music notation. Since these two are very different metaphors, our data structure would have to be very simple. What is the greatest common denominator between these two?

There are three different metrics by which the passage of music can be measured: seconds of playing time, number of beats, and inches along the score. These are all correlated, although not linearly. Generally, the music continues to move in the same direction for all three.

An important invariant across all three metrics is that events that occur together in one metric usually occur together in the other two. Violations are rare, and can usually be handled as special cases. (The rolled chord is one violation: it appears on the score as one event but is played as a number of separate events.)

Reflecting on the composition process, we decided that it was rare that the composer would want the editor to automatically separate events that he had placed together. For instance, if he played two notes simultaneously on the synthesizer, he probably wanted them displayed together. The notes can be manually separated, of course, but they shouldn't be implicitly separated by the system unless there is very good reason for it.

Notation can be thought of in three different ways; as a collections of marks that appear on a piece of paper, as symbols that represent music as the composer thinks of it, and as symbols that represent music as the composer hears it. The composer is concerned with all three aspects of notation.

The most important aspect of notation is its ability to represent music in symbolic terms. Many of the terms of notation such as "beats" and "voices" and "chords" only have meaning in the minds of the composer and listener. The sound waves that pass through the air only hint at there existence. Their reality is imposed by the listener.

Pianorolls capture just the raw events that is the basis for a piece. They don't have any structure; no chords, beats or beams. All of these must be added by the composer.

The composer is sometimes concerned with how the music notation appears on the sheet of paper, even though this will have no effect on how the piece is understood. This concern is both practical and aesthetic; practical because it will affect how easy the music is to read, and aesthetic because it will affect the beauty of the score.