KR: Exercise 2

Answer Set Programming

A Canon Composer


The exercise will consist in programming an automated canon composer using Answer Set Programming. A canon is a technique for composing musical pieces with two or more simultaneous voices or melodies (polyphony). In a canon, an initial melody (called the leader or dux) is imitated by the other voices (called the followers or comes) that enter into play after a given duration or delay. For more details, see the wikipedia entry for canon (music).

For simplicity, our exercise will impose some important restrictions and assumptions:
  1. All pieces will be restricted to the well-known C major tonality (Spanish: do mayor).
  2. The range of pitches we will allow and the encoding we will use is shown below. Internally, notes will be numbered from 1 to 15, whereas the input files will allow the alphabetic representation shown below the notes:

  3. All notes will have the same duration: they will be quarter notes (Spanish: figuras negras).
  4. The whole piece will last a given number L>2 of quarter notes. We will refer to each quarter note beat as a time or instant.
  5. We will restrict the exercise to 2-voices simple canons. This means that there are only two voices, the leader and the follower, which follows the leader using exactly the same melody but with some given delay.
  6. The delay between the leader and the follower will also be specified as a given number D>0, D<n of quarter notes.

In principle, the composer must be capable of generating any possible melody, but we will apply the following harmonic restrictions.

  1. The notes being simultaneously played by the two voices cannot form a dissonance. In our context, this means avoiding that the two notes correspond to correlative letters, that is, combinations c-d, d-e, e-f, f-g, g-a, a-b, b-c are forbidden.
  2. We will not allow that the leader and the follower perform a sequence of two consecutive fifth intervals. A fifth interval is formed when the distance between the lower pitch and the higher pitch comprises 5 pitches. For instance, c-g forms a fifth (c-d-e-f-g) and a-e too (a-b-c-d-e).

Finally, the composer will also follow some melodic preferences. For instance, if possible, the following is preferred:

  1. Try to avoid unisons (both voices playing the same note)
  2. Try to avoid repeating the last note
  3. Smaller melodic jumps are preferred (better a raising jump from c to e than from c to b).
  4. Preferrably, the follower usually plays a note with lower pitch than the leader.

Degrees for preferences can be varied as parameters or random values to generate different solutions.


The input will be an ASCII file that contains a first line with a number L>2 (the total length measured in number of quarter notes) a second line with a number D (the delay or number of quarter notes that the follower will wait before starting) and then a partial description of each voice. This means that we will include some fixed notes at given instants or leave the note to be suggested by our composer (using symbol "-"). Blank spaces and intros are ignored. As a small example:

c' -  e' -  -  -  -  g'
-  -  -  -  -  -  -  c'

means that the total duration are 8 quarter note beats (instants) and that the follower will begin at instant 5. The leader voice has fixed the first, third and 8th note (c', e' and g' respectively) whereas the follower must play a c' at the 8th instant.


The output will be an ASCII file that completes the input satisfying all the constraints given before. For instance, a possible solution to the input example seen above would be:

c' d' e' c' e' f' g' g'
-  -  -  -  c' d' e' c'

Note that the first 4 beats of the leader voice must be "-" since the delay is 4. As an alternative output, we can also use the free software tool Lilypond to generate both a music score and a MIDI file. The solution above corresponds to the lilypond file canonex.txt and generates the score:

More instructions for using this choice will be uploaded here.

An example that does not satisfy the fifth-intervals rule would be, for instance:

c' d' e' c' g' a' g' g'
-  -  -  -  c' d' e' c'

which is not a valid solution since fifth c'-g' is followed by fifth d'-a'.

Assessment & delivery

The maximum grade for this exercise is 1,5 points. The deadline for delivery is May 2nd, 2014 using the lab work mailbox or buzón de prácticas.

Maintained by Pedro Cabalar. Last update March 18th 2014