# Prolog’s Makin’ Music – Part 3

This time we’ll have a look at some techniques for automatically generating music — or rather, to be more accurate, melodies. Since we’ve deduced that a musical scale is a mathematical structure in which it’s possible to perform all the standard operations, we have quite a lot of freedom when it comes to the choice of a suitable formalism. We’ll also make some simplifications to make the job easier: namely that our melodies consists of a single list of notes where all notes are assumed to be of equal importance, e.g. played in the same timbre and tempo. This means that the resulting melodies won’t be that pleasing to the ear, but there’s of course nothing that stops us from using one of these melodies as a building block in a larger musical composition. I suppose that we still need musicians for something!

### Lindenmayer systems

A Lindermayer system, or an L-system, is a formal grammar quite similar to a context-free grammar. The goal is to rewrite a starting string, the axiom, by applying as many rules as possible. A rule is simply an if-then statement of the form: if the token is $X$ then replace it by $Y$. Formally speaking this information can be summarized as a tuple: $L = (V, \omega, P)$

Where $V$ is a set of variables, $\omega$ the starting axiom and $P$ the set of production rules, i.e. functions from $V$ to the language. The symbols that don’t appear in $V$, the constants, are always left untouched. The first example on Wikipedia is an Algae system. It has two variables, $A$ and $B$, $A$ as starting axiom and the two rules: $A \rightarrow AB$ $B \rightarrow A$

So the strings that will be produced are: $A$, $AB$, $ABA$, $ABAAB$, and so on. It shouldn’t be hard to see how the rules were applied. First the axiom was used. Then, the rule for $A$ was used which produced $AB$. Then the rules for both $A$ and $B$ were used which produced $AB$ and $A$, i.e. $ABA$.

We are free to interpret the structure in an L-system in any way we see fit. For example, we could interpret $A$ in the Algae system as “play the first note in the scale” and $B$ as “play the second note in the scale”. I shall however use something a bit closer to the Logo notation that is commonly used to visualize L-systems. It consists of the following commands:

• $f$ — draw forward.
• $+$ — turn right.
• $-$  — turn left.
• $s$ — push the current point on the stack.
• $r$ — pop an entry from the stack.

But since we’re working with scales, and not images, we have to reinterpret these commands. I propose the following:

• $f$ — play the current note.
• $+$ — increase the current note.
• $-$ — decrease the current note.
• $s$ — push the current note on the stack.
• $r$ — pop an entry from the stack.

Hence we’re going to use L-systems that produce strings in this format. From such a string it’s then possible to extract a melody. For example, the string $"f+f-f"$ could be interpreted as the notes $0,1,0$.

We’ll return to this later. For now, let’s concentrate on implementing L-systems in Logtalk. This can be done in a large number of ways, but once we’ve chosen a suitable representation everything else will more or less follow automatically. Every L-system will be represented by an axiom and a set of production rules for both variables and constants. Since the production rules take symbols as argument and produces strings/lists, DCG’s are a fine choice. For the moment we can ignore everything else and just stipulate what an L-system is.

:- protocol(l_system).

:- public(rule//1).
:- public(axiom/1).

:- end_protocol.

:- object(algae,
implements(l_system)).

axiom([a]).

rule(a) --> [a,b].
rule(b) --> [a].

:- end_object.


Then we’ll need a predicate that takes a string as input and applies all applicable production rules. Since the rules themselves are written in DCG notation, it’s easiest to continue with this trend. The predicate will take a string and an L-system as input, and iteratively apply the rules for the elements in the string.


next([], _) --> [].
next([X|Xs], L) -->
L::rule(X),
next(Xs, L).


And all that remains is a predicate that calls $next//2$ for a predetermined number of generations. It’s more or less a standard loop: if $N$ is $1$, then the resulting string is the axiom of the L-system. Otherwise, recursively run the L-system for $N - 1$ generations and then run it once more.

generation(1, L, X) :-
L::axiom(X).
generation(N, L, X) :-
N > 1,
N1 is N - 1,
generation(N1, L, Y),
phrase(next(Y, L), X, []).


This is almost too easy! For reference, let’s also implement an L-system that makes use of the Logo commands previously discussed.

:- object(koch_curve,
implements(l_system)).

axiom([f]).

rule(-) --> [-].
rule(+) --> [+].
rule(f) --> [f,+,f,-,f,-,f,+,f].
:- end_object.


This structure is known as a Koch curve, and when interpreted as drawing commands it looks like: Now we’ll need a predicate that transforms a list of commands into a list of notes. It’ll need 4 input arguments:

• $Xs$ — the list of commands.
• $Scale$ — the scale that the notes shall be generated according to.
• $N$ — the starting/current note.
• $S$ — the stack.

And one single output argument:

• $Ns$ — the resulting list of notes.

It’s not that hard to implement since it  only consists of a case-analysis of the command list. For example, if the command list is empty then the list of notes is empty. If the command is $f$, then we add the current note $N$ to $Ns$, and so on for all the other commands.

    transform([], _, _, _, []).
transform([f|Cs], Scale, N, S, [N|Ns]) :-
transform(Cs, Scale, N, S, Ns).
transform([-|Cs], Scale, N, S, Ns) :-
Scale::lower(N, N1),
transform(Cs, Scale, N1, S, Ns).
transform([+|Cs], Scale, N, S, Ns) :-
Scale::raise(N, N1),
transform(Cs, Scale, N1, S, Ns).
transform([s|Cs], Scale, N, S, Ns) :-
transform(Cs, Scale, N, [N|S], Ns).
transform([r|Cs], Scale, _, [N|S], Ns) :-
transform(Cs, Scale, N, S, Ns).


### Putting everything together

We can now generate command strings from L-systems and convert these into notes in a given scale. What remains is to convert the notes into frequencies with a specific duration. These can then be converted into samples and be written to a WAV file.

    generate_notes(L, I, Scale, Notes, Number_Of_Samples) :-
l_systems::generation(I, L, X),
Scale::nth(0, Tonic),
l_systems::transform(X, Scale, Tonic, [], Notes0),
findall(F-0.2,
(list::member(Note, Notes0),
Scale::frequency(Note, F)),
Notes),
length(Notes, Length),
synthesizer::sample_rate(SR),
Number_Of_Samples is Length*(SR/5).


The value $0.2$, the duration of each note, is of course just an example and can be changed at whim. This is all we need in order to crank out some simple tunes. Luckily, I’ve already prepared some samples for your auditory pleasure.

Koch curve in C major

This is the curve depicted earlier. To be frank it sounds kind of dreadful, but fortunately the other samples are somewhat more interesting. Next up is the dragon curve! Dragon curve in C major

Dragon curve in C minor

I think it sounds much better than the Koch curve, but that might be due to the fact that I view my creations with rose-tinted eyes; unable to see the unholy abomination that is their true form. Let’s have a look at the Hilbert curve. Hilbert curve in C major

Hilbert curve in C minor

Catchy! The last L-system is a fractal plant. Fractal plant in C major

Fractal plant in C minor

I think the results are quite interesting, and this is only the tip of the iceberg since it’s possible to create any kind of L-system and interpret it as a melody. The whole set is available at Soundcloud.

I initially intended to include a section in which I created a Prolog interpreter that for each refutation also produced a melody, but the time is already running out. It’s not impossible that I’ll return to the subject at a later date however!

### Source code

The source code is available at https://gist.github.com/1034067.

1. 