ProCoGraM - generating music by evaluating of probabilistic context-free grammars - similar to those used for natural language parsing. 

Program Description: 

1. A single grammar is used to generate a piece of music -- a single melodic line or such. 
2, The program works on iteration principle. At every step the working grammar generates derivatives which are evaluated by the user. 
3. Rating is based on the generated track after being listened for their votes. 
4. The initial grammar is completely random. The user selects the direction of music.
5. At any time the status of the program can be saved to a file and then resumed at the user's own discretion. 
6. History is also supported  -- you can move backwards and forwards. 
7. You can listen to the selected grammar continuously. You can also save a sound sample file. 

Semantics of the grammars: 

1. There is a finite set of terminal symbols. Each of them sets a tone (or rest) with its length of duration, etc. 
2. A grammar includes a starting symbol S. 
3. For each non-terminal symbol E there is a group of context-free production of the form E -> W *, where W * is a sequence of zero or more symbols (terminal or non-terminal). Each production is decorated with a probability, and they all add up to 1 (for each symbol E). 
4. Fresh non-terminal symbols may be placed on each grammar, if necessary, through mutation. 

5. For the grammar to be correct, for each non-terminal symbol there should be a nonzero probability of generating a terminal symbol. Otherwise, the machine will generate an endless music loop. 

6. For each symbol, either: 
6.1. The expected position of the first terminal symbol generated from it after a full expansion is finite. 
6.2. The symbol goes to the empty string. 

7. This condition is unfortunately not sufficient. For example: {S -> St} 

Generating the music: 
8. Music is generated by evaluating the state of the machine. 
9. Initial state is an infinite sequence of start symbols: SSSSS .... 
10. At every step of evaluation we remove the first symbol of the state machine. If it is a terminal, then  we send it to be played. Otherwise (nonterminals) we choose randomly the production of which we have used and place the result of production at the beginning of the recording.

To listen to the music you need to have fluidsynth installed (or timidity but you'll need to edit Song.hs to enable it).
The music files are generated in /tmp.

------
Original (Polish):

ProCoGraM - generowanie muzyki poprzez ewaluację drzew gramatyk probabilistycznych - podobnych do tych, które służą do parsowania języka naturalnego.

Opis programu:

1. Pojedyncza gramatyka służy do generowania utworu muzycznego - lub pojedynczej linii melodycznej takowego.
2. Program działa na zasadzie iteracji. Na każdym kroku z gramatyki wyjściowej generowane są gramatyki pochodne, które oceniane są przez użytkownika.
3. Ocena polega na odsłuchaniu wygenerowanego utworu i oddaniu głosu.
4. Gramatyki w pierwszym kroku są zupełnie losowe. Użytkownik wybiera kierunek rozwoju muzyki
5. W dowolnym momencie stan programu można zapisać do pliku i później wznowić wedle uznania.
6. Obsługiwana jest też historia - można się cofać i przechodzić do przodu.
7. Wybraną gramatykę można odsłuchać w sposób ciągły. Można też zapisać próbkę dźwiękową do pliku.

Semantyka gramatyk:

1. Istnieje skończony zbiór symboli terminalnych. Każdy z nich określa pewien dźwięk (lub pauzę) wraz z jego długością trwania itp.
2. Gramatyka zawiera symbol startowy S.
3. Dla każdego symbolu nieterminalnego E istnieje grupa produkcji bezkontekstowych postaci E -> W*, gdzie W* jest ciągiem zera lub więcej symboli (terminalnych lub nieterminalnych). Każda z produkcji ma przypisane prawdopodobieństwo wystąpienia, a wszystkie one sumują się do 1 (dla każdego symbolu E).
4. Świeże symbole nieterminalne mogą być wprowadzane go gramatyki w razie potrzeby na drodze mutacji.

5. Aby gramatyka była poprawna, dla każdego symbolu nieterminalnego powinno istnieć niezerowe prawdopodobieństwo wygenerowania symbolu terminalnego. W przeciwnym wypadku maszyna generująca muzykę zapętli się.

5. Dla każdego symbolu albo:
5.1. Oczekiwana pozycja pierwszego symbolu terminalnego wygenerowanego z niego po pełnym rozwinięciu jest skończona.
5.2. Symbol przechodzi w ciąg pusty.

6. Powyższy warunek nie jest niestety wystarczający. Przykład: { S -> St }

Generowanie muzyki:
5. Muzyka generowana jest przez ewaluację stanu maszyny.
6. Stanem początkowym jest nieskończony ciąg symboli startowych: SSSSS....
7. Na każdym kroku ewaluacji usuwamy pierwszy symbol ze stanu maszyny. Jeżeli jest to terminal, to przesyłamy go do odegrania. W przeciwnym wypadku (nieterminal) wybieramy losowo produkcję którą mamy zastosować i umieszczamy wynik produkcji na początku zapisu.