Rapport de stage

Une application de résolution de contraintes en harmonie tonale.

Jean-Louis GUENEGO

sous la direction de

Gérard ASSAYAG

DEA ATIAM

1997-1998

1. Introduction

La programmation par contraintes est une technique de programmation de plus en plus utilisée en informatique, et plus particulièrement en intelligence artificielle. Sa technique ne réside pas dans l'élaboration d'un algorithme de calcul de solutions construit à partir des données d'un problème, comme c'est souvent le cas dans la programmation classique, mais dans une déclaration de prédicats appelés contraintes qui sont fournis à un moteur de recherche censé explorer un domaine prédefini de possibilités pour extraire celles qui satisfont aux contraintes. Ces possibilités extraites sont les solutions du problème [Fro 94].

Ce type de programmation s'adapte bien dans le domaine de la composition assistée par ordinateur (CAO), car les problèmes que les compositeurs soumettent à la machine, souvent très intuitifs pour l'homme, sont en fait souvent difficiles et longs à traduire en algorithmes de calculs. De plus, le compositeur est amené très fréquemment à changer, de peu ou de beaucoup les problèmes posés, pour des raisons d'échecs où d'idées nouvelles. Or, modifier un problème, même très légèrement, peut amener le programmeur à revoir toute la nature du calcul menant à sa solution. En revanche, si la résolution du problème n'est pas faite fonctionnellement, mais par satisfactions de contraintes, il suffit alors de modifier légèrement les contraintes, éventuellement le domaine. Plus généralement, la programmation par contraintes bénéficie des quatres propriétes suivantes [Sar 95]:

- les contraintes spécifient l'information partiellement. Par exemple, la contrainte X=Y impose que la variable X et la variable Y soient égales, mais ne précise pas leur valeur.

- l'ordre de spécification des contraintes n'a pas d'importance,

- les contraintes sont rarement indépendantes. De plusieurs contraintes, on peut en déduire des prédicats qui rajoutent de l'information au système. Par exemple, les contraintes X+Y>=Z et X+Y<=Z donnent, sans pour autant que cela figure explicitement dans le programme X+Y=Z.

- les contraintes sont déclaratives, elles précisent les propriétés que doivent satisfaire les solutions d'un problème et non pas l'algorithme avec lequel les solutions doivent être trouvées.

C'est pour ces raisons que l'équipe Représentations Musicales de l'Ircam travaille depuis 1993 sur un moteur de satisfaction de contraintes, appelé Situation, adapté d'abord à PatchWork, et dernièrement mis à jour sur OpenMusic [Irc 98]. Ce moteur a été écrit par Camilo Rueda.

L'efficacité de la programmation par contraintes dépend de l'efficacité du moteur et de la façon dont sont programmées les contraintes que l'on y applique. Le moteur doit faire une exploration intelligente du domaine, ce qui nécessite une attention toute particulière à sa conception. L'exploration nécessite de nombreuses actions répétées. Lorsque le moteur parcourt le domaine, une même contrainte peut être appliquée un grand nombre de fois. Il faut par conséquent programmer celle-ci de façon à ce qu'elle soit évaluée le plus rapidemment possible. Ce sont ces exigences qui font que l'équipe Représentation Musicale travaille de façon continue à l'amélioration de Situation.

En outre, les méthodes visant à améliorer le moteur de satisfaction de contraintes sont souvent des compromis entre l'efficacité de la recherche dans le domaine et la variété de contraintes qui peuvent être supportées par le moteur. Les améliorations idéales sont bien sûr celles qui rendent la recherche plus efficace sans restreindre le type de contraintes acceptées.

Situation [Rue 98] étant un moteur de recherche conçu pour la CAO, il a été réalisé de manière à pouvoir s'appliquer principalement sur la génération de séquences harmoniques. Pour cela, il fallait trouver un modèle d'organisation du domaine permettant de représenter facilement des séquences harmoniques. Le modèle devait aussi permettre d'exprimer facilement les contraintes les plus diverses. Il est expliqué plus loin.

Une fois le modèle choisi, le moteur a été construit ainsi qu'une interface de programmation par contraintes permettant au programmeur de fabriquer des contraintes à partir de la codification des hauteurs Midi. Situation a déjà été utilisé dans la conception d'oeuvres musicales, notamment dans une pièce d'Antoine Bonnet intitulée " Epitaphe ".

Situation a jusqu'à présent été utilisé pour créer des séquences harmoniques de musique contemporaine, donc utilisé dans des systèmes propres à chaque compositeur. Dans le but d'améliorer et de valider universellement le moteur de Situation, on a pensé adopter la démarche qui consiste à tester le moteur sur des exemples appartenant à un domaine connu de tous et pour lequel il existe un corpus de règles bien définies.

Ainsi, on a cherché à générer des séquences d'harmonie tonale. En effet, les règles de l'harmonie tonale mettent en jeu des contraintes de type très divers. De plus, la structure tonale bénéficie d'une évolution musicale à travers plusieurs siècles ce qui en fait un exemple d'application des contraintes pertinent. La méthode généralement appliquée dans la recherche en informatique musicale jusqu'ici a généralement été de faire une modélisation mathématique de règles d'harmonie et de contrepoint. Certains chercheurs ont déjà mené des travaux dans ce sens, c'est le cas par exemple de Kamel Ebcioglu [Ebc 88] avec des simulations de choral dans le style de J.S BACH, de David Cope [Cop 91] avec un système de base de donnée permettant de générer des séquences musicales, de Hörnel [Lan 98] avec un système de réseaux neuronaux capable d'harmoniser dans le style baroque et enfin de P. Barbaud [Bar 68] avec des applications des automates finis en génération d'harmonie tonale.

Spécialement pour le cas de Situation, on se propose de recenser les méthodes de l'harmoniste professionnel pour harmoniser à vue, par exemple le fait de penser à harmoniser d'abord la basse d'un choral, et ensuite les autres parties. Ensuite, on essaie d'implémenter ces méthodes sous formes de contraintes dans Situation. Notons que l'harmoniste, consciemment ou pas, harmonise à vue avec un système de contraintes. De plus, on essaie de concilier simultanément l'aspect contrapuntique et harmonique, chose rarement fait auparavant car cela devient un problème de contraintes difficiles du fait de l'explosion combinatoire.

Situation étant en fait une librairie installée dans OpenMusic, ce dernier étant très lié à CLOS, on abordera ici l'étude de la programmation par contraintes en présentant successivement les outils employés :

- CLOS,

- OpenMusic,

- Situation.

On s'intéressera ensuite à des problèmes de complexités d'algorithme et enfin on donnera quelques perspectives de recherches.

2. CLOS

2.1. Historique

CLOS (Common Lisp Object System) est un langage objet directement issu de Common Lisp. Lisp (List Processing) a été développé dans les années 50 par John McCarthy [Sla 97]. La programmation en Lisp est différente d'autres langages tels que Fortran ou C, utilisé surtout pour du calcul numérique.

Lisp a été utilisé en particulier en Intelligence Artificielle, mais aussi dans des applications telles que de la simulation de langage naturel, de la démonstration de théorèmes mathématiques, de la reconnaissance de la parole, des jeux, des logiciels éducatifs,...

Depuis sa parution, Lisp présente plusieurs caractéristiques avantageuses :

- Une syntaxe simple. La syntaxe de Lisp est la même pour les données que les programmes.

- Une possibilité extension. On peut ajouter au système toute fonction programmée extérieurement.

- Une possibilité d'adaptation. Le programmeur peut non seulement ajouter toute sorte de fonction, mais aussi redéfinir celles déjà existantes.

- Une mémoire dynamique. Lisp est muni d'une gestion automatique de la mémoire ce qui libère le programmeur de toute préoccupation sur la mémoire.

- Une possibilité d'utiliser des arguments fonctionnels. On peut construire dynamiquement des fonctions à partir d'autres fonctions.

Common Lisp, en outre, permet au programmeur :

- d'avoir une facilité de déboguage,

- de manipuler des données abstraites,

- d'utiliser les ressources de la programmations par objets.

Lisp, au travers des années a été utilisé par beaucoup de monde, chacun l'étendant à sa guise, et plusieurs versions de Lisp sont apparues : Lisp 1.5, MacLisp, InterLisp, Franz Lisp, Portable Standard Lisp, Scheme, ... De ce fait, le code en Lisp devenait de moins en moins portable. La communauté " Lispienne " a alors décidé de créer Common Lisp, un Lisp commun à tous les programmeurs en Lisp, évoluant de façon graduelle.

Le manuel de référence de Common Lisp a été écrit par Guy Steele [Ste 90] et est utilisé par tout programmeur en Common Lisp, quelle que soit le type de machine utilisé. Ceci garantit la portabilité de tout programme en Lisp.

2.2. Mini-tutorial

2.2.1. Les bases

Lisp utilise un interpréteur, un peu comme un shell sous Unix. Une fois l'interprète lancé, on voit à l'écran un prompt, comme par exemple " ? ".

?

Pour faire une opération simple comme 2+3, on fait :

? (+ 2 3)

5

c'est à dire, on tape (+ 2 3) puis la touche " return " pour demander l'évaluation par l'interpréteur. Voici d'autre exemples (expt est une fonction calculant la puissance de deux nombres) :

- multiplication de 2 par 3 et par 5.

? (* 2 3 5)

30

- puissance de 3 par 4.

? (expt 3 4)

81

- puissance de 1234 par 345.

? (expt 1234 345)

3189555000809791039982160865301543096447702279358264375123302158564264838030773145551754688610210784694090772386893271533720207036491091405579400534911727788963046685018274148214101658075772345783520805176327377756926664169485734793985636194361712651171797215105385117862820362960611097841820462165690964591846094383945985782961798390819468331329413994521326691528359957740167766190764607542948363374191561257431682571975160164332417408034532103013074793331430417078523721635480570668309007965429587574130222054034442100803740223847566880666856391779621081895953855132005024048065068677625621904081064902832765470623371977067070180533201480408578833288673579336276774252534637172228766409378620376165964535219142293674590878675614765676755827112993603694218497848473332307722122685195076143293795456047605540293724327966629698080575311314124363415788641539737779863468850868344747754530158710031468239368331779085785337789727291551058792563812492441530406352654809159353570728413572606718791060220029360255670602237895688050127061923448987710944272500007638164045824

On peut remarquer que Lisp est à l'aise avec les grands nombres comme avec les petits. La syntaxe de Lisp est extrêmement générale. On ouvre une liste, on indique le nom de la fonction que l'on veut appliquer et ensuite les arguments, et on ferme la liste. Les listes peuvent s'imbriquer les unes dans les autres.

? (* (+ 2 4) (- 5 2))

18

On va maintenant définir des fonctions personnalisées. Pour cela, il suffit d'utiliser la fonction defun, qui prend en argument le nom de la fonction à créer, ses paramètres (on appelle la liste de paramètre la " lambda list ") et le corps de la fonction. Voici par exemple une fonction qui donne la multiplication par 2 d'un nombre qu'on lui donne :

? (defun fois2 (x) (* x 2))

fois2

La fonction defun renvoie le nom de la fonction qui vient d'être créée. Maintenant, utilisons la fonction fois2 :

? (fois2 7)

14

La fonction fois2 s'utilise exactement comme une fonction du système.

Lisp est bien sûr muni de beaucoup de fonction permettant de construire des programmes de haut niveau. Citons par exemple les fonctions permettant de faire des structures conditionnelles, des boucles, ...

? (defun signe (x) (if (< x 0) -1 (if (= x 0) 0 1)))

signe

? (signe 3)

1

? (signe -4.3)

-1

? (defun compte (depart arrivee) "compte depuis <depart> jusqu'à <arrivée>"

(loop for i from depart to arrivee do

(print i)))

compte

? (compte 3 8)

3
4
5
6
7
8

NIL

Dans la dernière fonction, une ligne de commentaire a été ajoutée. Celle ci doit être sous la forme d'un objet de type chaîne de caractère. Cette chaîne doit obligatoirement être placée après la lambda list et avant le corps de la fonction. Elle est ainsi reconnue par le système qui peut ensuite fournir de l'aide pour dire ce que fait une fonction lorsqu'elle est inconnue de l'utilisateur, ceci est particulièrement intéressant lorsque l'on essaie de lire du code lisp contenant des fonctions définis localement.

On peut aussi définir des fonctions de façon récursive :

? (defun factorielle (n) "calcule la factorielle de <n>"

(if (= n 0) 1 (* n (factorielle (- n 1)))))

factorielle

?(factorielle 5)

125

Une utilisation très courante dans Lisp est, comme " List Processing " l'indique, le traitement de liste. Les fonctions les plus rencontrées sont par exemple " car " et " cdr ". Le " car " d'une liste est son premier élément, le " cdr " est une liste contenant le reste de la liste. On a par exemple :

? (car '(1 2 3))

1

? (cdr '(1 2 3))

(2 3)

Une fonction évalue d'abord ses arguments avant d'être évaluée. Le signe ', appelé quote, devant la liste (1 2 3) signifie qu'avant d'exécuter la fonction " car " , il ne faut pas évaluer la liste (1 2 3). En effet, la liste (1 2 3) ne signifie rien pour l'interprète Lisp. Si on tente de l'évaluer, cela génère une erreur. Par exemple,

? (1 2 3)

ERREUR

En revanche,

? '(1 2 3)

(1 2 3)

On peut bien sûr définir des variables grâce à " setf ", " setf " renvoie alors la valeur de la nouvelle variable enregistrée dans le système :

? (setf xyz '(1 (3 4)))

(1 (3 4))

2.2.2. Variables locales, variables globales

Dans ce qui précède, on a vu deux types de variables. Celles qui sont définies par setf en dehors des fonctions, et celles qui sont définis temporairement dans la liste des paramètres d'une fonction. Les premières sont des variables globales, et les secondes des variables locales. Une fonction très utilisée en lisp est la fonction " let ". Elle permet de déclarer des variables locales autrement que dans une liste de paramètres avec " defun ". Voici un exemple d'utilisation de let dans une fonction :

? (setf y 0)

0

? y

0

? (defun foo (x)

(let ((y 2))

(print x)

(print y)

nil))

FOO

? (foo 3)

3

2

NIL

? y

0

? x

ERREUR (x non defini)

2.2.3. Closures

La fonction " let " permet de faire ce que l'on appelle en Lisp des closures. Notons que cela n'est pas directement possibles avec d'autres langages. Voici comment faire une closure :

? (let ((n 0))

(defun 1+n () (setf n (+ 1 n)))

(defun resetn () (setf n 0))

(defun printn () (print n)))

RESETN

? (setf n 45)

45

? n

45

? (printn)

0

? (1+n)

1

? (printn)

1

? n

45

On verra par la suite l'utilité d'une telle démarche dans la programmation.

Le lecteur désirant en savoir plus sur la description de CLOS pourra se référer aux ouvrages cités en bibliographie [Ste 90] [Sla 97].

2.3. Langage Objet

2.3.1. Introduction

Common Lisp est un langage étendu pour avoir aussi les caractéristiques d'un langage objet. On va décrire ici ce qu'est un langage objet en prenant l'exemple de Common Lisp.

Dans la partie précédente, on a utilisé plusieurs types d'objets :

- des nombres entiers

1 ; 3 ; 34563782384893 ; ...

- des nombres flottants

4.32 ; 3.14 ; 6.02e23 ; ...

- des chaînes de caractères

"le chat et la souris.", ...

- des listes

(1 2 3) ; ( "coucou" 2.45 78 (1 2) )

- des symboles

x ; dea ; defun ; ...

Il existe encore beaucoup d'autres types d'objets. Pour savoir de quel type est un objet, il existe une fonction type-of que l'on utilise comme ceci :

? (type-of 34)

FIXNUM

? (type-of '(1 2 3 4))

CONS

? (type-of "hello.")

(SIMPLE-BASE-STRING 5)

Dans un langage objet, le programmeur peut en fait créer soi-même ses propres types. Par exemple, on peut créer le type " note ", qui correspond à un triplet de trois entiers représentant respectivement la hauteur, la vélocité et la durée. L'avantage est que le programmeur peut exprimer avec ses propres termes des objets qui se ramènent le plus souvent à des listes d'objets de types primitifs (entiers, caractères, ...). Les programmes sont donc plus lisibles puisque les mots utilisés correspondent mieux avec ce qu'ils sont censés décrire. Mais la puissance du langages objets ne s'arrête pas là [Hab 96].

2.3.2. Classes et instances

Dans les langages objets, les types s'appellent des classes, et les objets sont dits des instances des classes. Créons maintenant une classe " note " ayant trois champs (slots) comme définis ci-dessus :

? (defclass note () (hauteur velocite duree))

#<STANDARD-CLASS NOTE>

La syntaxe de la fonction defclass ressemble un peu à la fonction defun, sauf qu'elle ne définie pas la même chose. La liste vide après le symbole note sera expliqué par la suite. Dans cette définition, on a uniquement déclaré à l'interprète que note était une classe ayant trois champs, on a par contre rien précisé sur la nature de ces champs. Est ce que le champ hauteur correspond à un entier, ou à une liste, ou encore à une chaîne de caractère ? On peut donner, moyennant quelques options de la fonction defclass des informations relatives aux champs. On pourrait déclarer de façon plus précise la classe note :

? (defclass note ()

((hauteur

:type integer

:initarg :hauteur

:initform 60

:reader lire-hauteur

:writer changer-hauteur

:documentation "hauteur codifiée midi")

(velocite

:type integer

:initarg :velocite

:initform 64

:reader lire-velocite

:writer changer-velocite

:documentation "velocite codifiée sur une échelle de 0 à 127")

(duree

:type integer

:initarg :duree

:initform 1000

:reader lire-duree

:writer changer-duree

:documentation "durée en milliseconde de la note")))

#<STANDARD-CLASS NOTE>

Ici, on a précisé la nature des trois champs. Ce sont des entiers. On a aussi précisé lors de chaque création d'instance de la classe note quelles seraient les valeurs par défaut associées à chaque champ. Et enfin pour chaque champ, on a indiqué une documentation précise les concernants. D'autres options ont aussi été indiquée (:reader, :writer...), leur utilité sera démontrée par la suite.

Maintenant, pour créer des instances de la classe note, il suffit de taper des instructions du style suivant :

? (setf *not1* (make-instance 'note))

#<NOTE #x1CA4066>

Dans la dernière instruction, on a rien précisé sur le contenu de note. Par conséquent, l'interpréteur a initialisé les champs par défaut. C'est à dire que le champ hauteur contient 60, le champ vélocité 64 et le champ duree 1000. En effet, examinons le contenu de la variable *not1* :

? (describe *not1*)

#<NOTE #x1CA4066>

Class: #<STANDARD-CLASS NOTE>

Instance slots

HAUTEUR: 60

VELOCITE: 64

DUREE: 1000

L'interpréteur envoie des informations relatives à la variable *not1*. Définissons une variable *not2*, cette fois-ci en précisant ses champs :

? (setf *not2* (make-instance 'note

:hauteur 67

:velocite 100

:duree 2000))

#<NOTE #x1CB3926>

? (describe *not2*)

#<NOTE #x1CB3926>

Class: #<STANDARD-CLASS NOTE>

Instance slots

HAUTEUR: 67

VELOCITE: 100

DUREE: 2000

On sait maintenant définir une classe et ses instances. On peut évidemment modifier les classes et les instances, mais toute fois en faisant attention de ne pas créer d'incohérence [Hab 97]. on a accès aux données comprises dans les champs d'une instance par des instructions de type suivant :

? (lire-hauteur *not1*)

60

? (lire-duree *not2*)

2000

Les noms des fonctions ci-dessus sont tout simplement ceux que l'on a déclaré lors de la définition de la classe " note ". Pour changer un champ d'une instance de la classe " note ", on tape par exemple :

? (changer-hauteur 72 *not1*)

72

? (lire-hauteur *not1*)

72

Le principal est dit à propos des classes et des instances. On va maintenant s'intéresser aux notions d'héritages.

2.3.3. Héritage

Dans les langages objets, on peut organiser les classes entre elles en leur donnant des relations. On peut par exemple définir des sous-classes. Définissons par exemple la classe " note-instrumentale " comme issue de la classe note, dans laquelle on rajoute un champ " timbre ", chaîne de caractère contenant le nom de l'instrument avec lequel la note est jouée.

? (defclass note-instrumentale (note)

((timbre

:initarg :timbre

:type string

:initform "piano"

:reader lire-timbre

:writer changer-timbre

:documentation "nom de l'instrument.")))

#<STANDARD-CLASS NOTE-INSTRUMENTALE>

? (setf *not3* (make-instance 'note-instrumentale))

#<NOTE-INSTRUMENTALE #x1CC926E>

? (describe *not3*)

#<NOTE-INSTRUMENTALE #x1CC926E>

Instance slots

HAUTEUR: 60

VELOCITE: 64

DUREE: 1000

TIMBRE: "piano"

Ainsi, on comprend mieux le sens de la liste se trouvant juste après le nom de la classe dans la fonction " defclass ". Elle indique que " note-instrumentale " est une sous-classe de " note ". Une classe peut être définie comme étant sous-classe de plusieurs classes. Cela s'appelle l'héritage multiple. Imaginons une classe A comportant deux champs a1 et a2, et une classe B comportant trois champs b1, b2 et b3. On peut alors construire la classe C comme étant une sous-classe de A et de B, l'instruction définissant C est de la forme :

? (defclass C (A B))

Une sous-classe hérite des champs de sa classe mère. Si on voulait en plus rajouter un champ c1 à la classe C, on donnerait alors l'instruction :

? (defclass C (A B)

(c1

:initarg :c1

......))

Quelques petites vérifications :

? (setf ccc (make-instance `C))

#<C #x1CCFA26>

? (describe ccc)

#<C #x1CCFA26>

Class: #<STANDARD-CLASS C>

Instance slots

B1: #<Unbound>

B2: #<Unbound>

B3: #<Unbound>

A1: #<Unbound>

A2: #<Unbound>

C1: #<Unbound>

2.3.4. Fonctions génériques, méthodes

Les fonctions génériques sont des fonctions dans lesquelles le type de donnée en entrée peut varier. Ces fonctions sont munis de méthodes dans lesquelles sont données les directives à suivre en fonction du type de donnée fourni en entrée. Montrons un exemple en définissant une fonction " plus " assez robuste pour additionner des nombres et pour concaténer deux chaînes de caractères.

La fonction " defgeneric " déclare la fonction générique plus à l'interpréteur. Cette fonction renvoie l'objet correspondant à la fonction générique créée.

? (defgeneric plus (chose1 chose2)

(:documentation "retourne l'addition ou la concaténation de <chose1> et <chose2>."))

#<STANDARD-GENERIC-FUNCTION PLUS #x1CD5B7E>

La fonction " defmethod " précise pour une combinaisons précise de types ce que la fonction générique doit faire. Ainsi, si le type de chose1 et de chose2 sont des nombres, on les additionne. Si le type de chose1 et de chose2 sont des chaînes de caractères, on les concatène.

? (defmethod plus ((chose1 number) (chose2 number))

"additionne deux nombres."

(+ chose1 chose2))

#<STANDARD-METHOD PLUS (NUMBER NUMBER)>

? (defmethod plus ((chose1 string) (chose1 string))

"concatène deux chaines de caractères."

(concatenate `string chose1 chose2))

#<STANDARD-METHOD PLUS (STRING STRING)>

Maintenant, testons la fonction " plus " :

? (plus 2.4 5.6)

8.0

? (plus "bonjour." "hello !")

"bonjour.hello !"

L'avantage de cette technique, appelée aussi polymorphisme, est qu'elle permet de considérer des entités fonctionnelles plus abstraites. Ici, " plus " est un opérateur binaire générique valant pour toute une famille d'opérateurs similaires.

2.3.5. Class Precedence List

En fait, on est souvent amené lors de la conception d'application à faire des arbres d'héritage de classe et de sous-classe assez grand et complexes. De plus, les objets de bases prédéfinis dans Common Lisp sont aussi structuré de façon complexe. Cela permet beaucoup de subtilité dans la programmation de fonction Lisp. Voici par exemple le graphe des relations d'héritages de CLOS :

float

integer

number rational

ratio

complex

function

symbol null

sequence list cons

array vector string

T character bit-vector

stream

pathname

readtable

package

random-state

hash-table

Quand on définit une fonction générique, il est rare de devoir lui ajouter des méthodes pour tout les types existant. De plus, ce serait assez fastidieux. Heureusement, lorsque l'on définit une méthode, celle-ci s'applique non seulement sur les objets du type indiqué, mais aussi sur tout ceux qui en découlent par héritage. Par exemple, dans la fonction générique plus, une méthode appliquée au type " number " suffit à décrire le comportement des " number " , mais aussi des " float ", des " rational ", des " ratio " ..., c'est à dire tout les types découlant du type " number ". Si on veut définir une méthode pour une des sous-classes de " number ", par exemple " rational ", celle ci s'appliquera aussi en priorité sur " integer " et " ratio ".

? (defmethod plus ((chose1 rational) (chose2 rational))

"additionne les deux rational, mais affiche aussi leur valeur."

(print chose1)

(print chose2)

(+ chose1 chose2))

#<STANDARD-METHOD PLUS (RATIONAL RATIONAL)>

? (plus 3/4 1/2)

3/4

1/2

5/4

? (plus 3.4 1.2)

4.6

Quand une fonction générique est évaluée, elle va examiner le type des données qu'elle a en entrée, puis elle va consulter la CPL (class precedence list) pour savoir quelle est la méthode la plus adaptée au type de donnée d'entrée. Si le type de donnée d'entrée n'est pas dans la liste de priorité, alors aucune méthode ne peut être appliquée et cela génère une erreur. Dans l'exemple de la fonction " plus ", on ne peut l'appliquer sur des tableaux.

? (plus #(1 3 4) #(3 4 5))

ERREUR

Pour plus d'information sur les langages objets, on peut se référer aux ouvrages cités en bibliographie [Hab 96], [Ste 90], [Sla 97].

3. OpenMusic

3.1. Introduction

L'équipe Représentation Musicale de l'Ircam a développé depuis 1993 un logiciel d'aide à la composition, appelé Patchwork. Ce logiciel est compté comme l'un des plus souples et plus puissants dans le domaine. Nombres compositeurs l'ont utilisé pour créer leurs oeuvres, parmi eux, citons Tristan Murail, Gérard Grisey, Claudy Malherbe, ...

L'expérience croissante des compositeurs en informatique accentue leur exigence face aux logiciels de CAO. De ce fait, Patchwork, pour rester à la pointe s'est muni progressivement de nombreuses fonctionnalités, subissant parfois de grosses modifications internes. Le désordre induit par ces modifications a rendu la maintenance du logiciels de plus en plus ardue. L'équipe Représentation Musicale a donc décidé de concevoir un nouveau logiciel, OpenMusic. Il est encore à l'état de gestation, mais le coeur du logiciel est sur pied.

3.2. Description générale

OpenMusic est entièrement écrit en CLOS et c'est un langage visuel. C'est à dire que l'on écrit les programmes non pas en écrivant des lignes de codes mais en assemblant des boites par des connexions. On trouve en fait beaucoup de similitude entre Lisp et le langage visuel d'OpenMusic. En effet, les deux sont des langages fonctionnels [Sja 93]. OpenMusic est un langage objet isomorphe à CLOS. Ceci en fait un langage extrêmement simple, cohérent et puissant. Peu de règles de bases sont nécessaires à connaître son fonctionnement global. De plus, développé pour Macintosh, son système de gestion des fichiers est très cohérent avec MacOS.

3.3. Utilisation

OpenMusic se lance comme toute application sous Macintosh. Une fois lancé, on voit apparaître deux fenêtres. La fenêtre du haut, appelée Workspace, est une fenêtre de gestion de fichier qui peut être personnalisée. La fenêtre du bas, plus petite, est simplement l' " écouteur " de MCL (Mac Common Lisp). Dans un Workspace, on peut créer des dossiers, des patches et des maquettes. Un dossier a la même fonction que dans MacOS, c'est équivalent à un répertoire dans lequel on peut mettre d'autres dossiers, patches et maquettes. Un patch est une boite dans laquelle on peut écrire des programmes en langage visuel. Il peut avoir des sorties et des entrées et contenir d'autres patches. Une maquette est comme un patch sauf qu'elle possède une abscisse représentant le temps. Pour pouvoir écrire des programmes visuels, on fait appel à des fonctions qui sont dans les packages d'OpenMusic. Ces packages sont les quatres boites se trouvant au bas du Workspace. On connecte ces fonctions entre elles dans un graphe acyclique orienté. Pour évaluer un programme, on évalue la dernière fonction de la cascade, qui appelle récursivement les autres pour pouvoir s'évaluer. Contrairement à certains autres logiciels de programmation visuelle comme par exemple Max, OpenMusic fait une évaluation en partant de la fin des programme. Cela ne permet pas de faire du temps réel, mais ouvre en revanche toute les techniques de programmation fonctionnelle. On montre par la suite quelques exemples d'utilisation d'OpenMusic.

Ouvrons le dossier new-folder pour voir ce qu'il contient. Pour cela, il suffit de faire un double-click avec la souris sur l'icône du dossier.

Le dossier New Folder contient deux patches, qui s'appellent factorielle et calcul. Ouvrons d'abord le patch calcul.

Le patch calcul contient deux boites reliée par une connexion. Visiblement, il doit calculer la factorielle de 6. Pour une boite donnée, les entrées se trouve au dessus de la boite, et les sorties en dessous. Le patch factorielle possède donc une entrée et une sortie. A l'entrée, on a branché la sortie de la boite qui contient le nombre 6. Pour évaluer la sortie du patch factorielle, on positionne la souris sur la petite boule bleue représentant la sortie et on fait option-click. Le Listener de MCL affiche le résultat.

Voyons maintenant comment est réalisé le patch factorielle. Ici, ce patch fonctionne comme une fonction. Il possède une entrée et une sortie. Ouvrons ce patch en faisant un double click sur l'icône du patch. Le contenu du patch apparaît. Il contient un programme visuel.

Pour comprendre comment fonctionne ce programme, il faut savoir que, lors de son évaluation, il y a une propagation d'appel de bas en haut, suivie d'une évaluation de haut en bas. C'est à dire, la sortie " output " veut savoir ce qu'elle contient. Pour cela, elle appelle la sortie de la fonction if, qui à son tour va évaluer ses entrées pour pouvoir s'évaluer elle-même et communiquer sa sortie. La fonction " if " appelle donc la fonction " égal " , la boite contenant 1 et la fonction " fois " à s'évaluer, et ainsi de suite. Ici, la fonction est programmée de manière récursive, la fonction " fois " appelle de nouveau le patch " factorielle " qui va s'évaluer, mais cette fois-ci avec son entrée décrémentée de 1. La récursivité s'emploie de la même façon qu'en Lisp. Plus généralement, la structure de programmation visuelle d'OpenMusic est en fait isomorphe à celle de Lisp et de tout les langages fonctionnels et c'est ce qui en fait un des principaux avantages.

On montre maintenant comment il est possible de programmer un patch où une fonction est passée en argument. On va écrire le programme visuel équivalent au code Lisp suivant :

?(sort '(1 4 2 5) #'<)

(1 2 4 5)

La fonction sort utilise une fonction prédicat pour classer une liste. Cette fonction prédicat est un argument de la fonction " sort ". Cette fonction est donc une donnée. Dans le langage visuel, il faut spécifier quand une fonction est considérée comme une donnée, afin que le système ne demande pas de l'évaluer. Ceci est réalisé à l'aide d'un marqueur " [[lambda]] ". Voici une traduction visuelle du code précédant. On retrouve bien le même résultat en évaluant la sortie de la fonction " sort ".

Pour faire des boucles, OpenMusic utilise une syntaxe visuelle très proche de la syntaxe de Lisp. Voici un patch illustrant la boucle " omloop ". Quasiment tout les styles de boucles réalisée avec Common Lisp sont réalisables de manière équivalente à l'aide de OpenMusic.

En double cliquant sur la boite " omloop ", on regarde son contenu.

Lors de l'évaluation de la boucle, l'interpréteur de MCL affiche successivement la valeur de la variable d'incrémentation. Puis pour finir, la boucle évalue ce qui se trouve connecté à " finally ". Ici, l'interpréteur affiche " hello " et le résultat de l'évaluation est aussi " hello ".

Montrons maintenant comment OpenMusic intègre les outils musicaux. Les outils musicaux sont en fait issus des techniques caractéristiques des langages objets, ils sont ainsi répartis en classe. A partir de la fenêtre du WorkSpace, on ouvre la boite des packages. Dans le répertoire " score ", on peut par exemple demander comment sont hiérarchisées les classes contenues dans ce répertoire. La figure ci-dessous montre le résultat.

On voit donc apparaître plusieurs classes : " note ", " rest ", ...

On va s'intéresser par exemple à la classe voice. Montrons une instance de cette classe dans un patch.

Une instance de la classe " voice " contient une suite d'accord avec un rythme associé. La syntaxe du rythme et des accords est assez explicite pour un musicien. On peut éditer le contenu de la boite correspondant à l'instance de la classe " voice ". Le résultat est dans la figure ci-dessous.

L'avantage de la programmation en langage visuel évite toute les fautes de type syntaxique, mais les erreurs de type sémantiques sont toujours possibles. De plus, on peut penser la conception d'un programme plus naturellement puisque l'ordre dans lequel on construit les boites n'est pas celui imposé par CLOS.

4. La programmation par contraintes en général

Voici un extrait de l'ouvrage d'Annick Fron [Fro 94], une synthèse en matière de programmation par contraintes.

La programmation par contrainte s'est répandue depuis les années 1990. Pourtant, beaucoup de travaux sur le sujet ont été mené bien avant, la plupart étant français. Citons les équipes d'Ilog avec l'outil Ilog Solver, de Prologia et de l'université d'Aix-Marseille avec Prolog III, sans oublier la société Cosytec et leur outil Chip, les travaux de Bull incarnés dans Charme, et bien d'autres encore. D'autres travaux, cette fois-ci à l'étranger ont aussi fait progresser ce style de programmation, parmi eux, ceux sur CAL à L'Icot, sur CLP(R) au laboratoire d'IBM aux Etats-Unis, pour ne citer que les plus fameux.

Application opérationnelles

La programmation par contraintes est d'ores et déjà utilisée quotidiennement par des industriels et professionnels, et les outils qui la mettent en oeuvre sont déjà commercialisés depuis plusieurs années. Parmi les domaines d'applications les plus classiques, on citera les banques pour les calculs financiers, les compagnies aériennes pour la planification de vols, les chemins de fers, les entreprises pour la gestion de production, la gestion de personnel.

La mise en forme des contraintes dans un contexte industriel peut se faire sous diverses formes : certaines applications utilisent des progiciels ou des environnements de développement du commerce, d'autres font seulement occasionnellement appel à des bibliothèques de gestion de contraintes, tout comme on pourrait envoyer une requête à une base de données, d'autres enfin restent à l'état de prototype et ne servent qu'à la modélisation du problème qui peut ensuite être codé de manière plus efficace dans un langage de programmation traditionnel, ou à l'aide de modules numériques.

Types d'applications

Les types d'application traitées par la programmation par contraintes sont très variés. Toutefois, on peut regrouper les types les plus usuels :

- Gestion du temps : gestion d'agenda, d'emploi du temps, planification d'équipes, de rotations d'équipes.

- Gestion et affectation de ressources : gestion de personnel, de moyens de transports, gestion de production.

- Planification et ordonnancement : planification de production, de livraison, de maintenance, d'interventions, d'itinéraires, ordonnancement d'ateliers.

- Optimisation de production, de moyens, d'investissements, de placements financiers, de coûts.

- Gestion de la cohérence d'information : interface graphiques, édition électronique, tableurs, bases de données.

- Modélisation : modèles mixtes numériques/symboliques, géométriques, économiques, financiers.

- Simulation comportementale de systèmes : on peut automatiquement déduire les sorties à partir des entrées. Le comportement du système à étudier est défini par des relations entre les variables, y compris les entrées et les sorties.

- Vérification de spécifications : le système de résolution de contraintes peut vérifier si le modèle de l'appareil ou du système est conforme à certaines propriétés, spécifiées par des contraintes.

- Diagnostic de pannes : étant donné un comportement anormal, une recherche du composant défectueux peut facilement être mise en oeuvre grâce à la programmation par contraintes en modélisant le comportement fonctionnel de l'appareil.

5. Notions Mathématiques de programmation par contraintes

5.1. Un exemple musical

Partons d'un exemple de problème musical simple. On voudrait générer de façon aléatoire un accord vérifiant les propriétés suivantes :

- il est parfait majeur de quatre notes à l'état fondamental,

- la basse est comprise entre le do2 et le do3,

- il ne contient pas d'unisson,

- l'intervalle entre le soprane et la basse ne dépasse pas deux octaves.

Cet accord ne peut donc avoir entre chacune de ses notes et sa fondamentale, que les intervalles de tierce, quinte et octave. On propose les deux algorithmes suivant où les hauteurs de notes sont traduites dans la norme Midi.

Approche constructive :

accord(0) := random(48, 60);

triplet := ordonne(sous-liste-ordonnee-random(3, (4, 7, 12, 16, 19, 24)));

de i := 1 à 3 faire

{accord(i) := accord(0) + triplet(i);}

Approche déclarative :

domaine := {48, ..., 84}^4

domaine-restant := domaine

faire

{accord := random(domaine-restant);

domaine-restant := enleve-element(domaine-restant, accord)}

jusqu'à

{verifie-proprietes(accord);}

Le prédicat verifie-proprietes() est écrit comme la disjonction de tous les prédicats traduisant les propriétés énoncées ci-dessus.

La première approche apparaît évidemment plus rapide d'exécution que la seconde, mais imaginons que l'on change un tout petit peu le problème. Par exemple, on voudrait un accord à l'état de premier renversement. Dans l'approche constructive, il suffit de changer la liste des intervalles (4, 7, 12, 16, 19, 24) en la liste (3, 8, 12, 15, 20, 24) et le tour est joué. Dans l' approche déclarative, on modifie l'un des prédicats contenu dans verifie-proprietes() et c'est gagné. Dans ce genre de modification du problème, il n'y a pas beaucoup de restructuration à propos des deux approches. Modifions le problème d'une autre façon. On voudrait cette fois-ci que les notes de l'accord soient toutes comprises entre do2 et do4. Dans l'approche déclarative, il suffit de réduire la taille du domaine. La recherche s'en retrouvera plus rapide. Par contre, au niveau de l'approche constructive, il faudra mener de grosse restructuration dans l'algorithme. On propose par exemple la correction suivante de l'approche constructive :

liste-intervalle := (3, 8, 12, 15, 20, 24);

auteur-max := 72 - liste-intervalle(3);

accord(0) := random(48, auteur-max);

fin := position-liste-ordonnee(liste-intervalle, 72 - accord(0));

liste-intervalle := sous-liste(liste-intervalle, 1, fin);

triplet := sous-liste-ordonnee-random(3, (4, 7, 12, 16, 19, 24));

de i := 1 à 3 faire

{accord(i) := accord(0) + triplet(i);}

Dans cet exemple, on s'en tire encore bien. Mais il existe des problèmes où l'approche constructive est impossible. C'est le cas du problème du voyageur de commerce, qui étant donné N villes à parcourir, doit trouver l'ordre optimal correspondant au trajet le plus court [Ste 90].

Dans le cas des applications musicales, les problèmes sont bien souvent plus complexes que la constructions d'accords. Et l'approche constructive est beaucoup plus fastidieuse à mettre en oeuvre que l'approche déclarative. C'est pourquoi cette dernière, appelée plus précisément programmation par contraintes (les prédicats sont appelés contraintes) est employée dans la composition assistée par ordinateur.

5.2. Modélisation

Dans cette partie, on se propose de développer les bases mathématiques concernant la programmation par contraintes [Rue 98].

Définition 1 : Un problème de satisfaction de contraintes (PSC) est un triplet

- est un ensemble fini ( ) appelé ensemble des variables.

- est un ensemble fini d'ensembles. Chaque ensemble ( ) correspondant au domaine de la variable .

- est un ensemble fini de contraintes binaires. Une contrainte binaire est un prédicat fonction de la valeur de la variable et de la variable . Donc, on peut dire que .

Définition 2 : Soit un PSC donné et noté . On dit que le n-uplet est une solution du PSC si et seulement si .

Définition 3 : Soit un PSC donné et noté . On dit que le p-uplet ( ) est une valuation du PSC si et seulement si .

La complexité liée à un problème de satisfaction de contrainte est exponentielle. En effet, pour résoudre ce problème, il faut prendre un à un tous les éléments du domaine et tester si ils satisfont aux contraintes. La taille du domaine à explorer varie de façon exponentielle. Imaginons un domaine de 8 variables pouvant prendre 15 valeurs différentes. La taille du domaine est alors de 158, soit 2562890625. Si on rajoute une variable du même type, on multiplie encore la taille du domaine par 15. Il faut donc à tout prix trouver des astuces qui vont accélérer le parcours du domaine. Les méthodes visant à améliorer la recherche se trouvent à deux niveaux. Il s'agit de réduire au maximum le domaine avant le parcours, et ensuite de faire un parcours judicieux.

5.3. Réduction du domaine

On considère l'exemple suivant. Soit un PSC avec

-

-

-

On peut représenter ce PSC à l'aide d'un graphe :

Essayons de réduire intuitivement ce graphe, mais de façon méthodique. Considérons en premier lieu la contrainte entre le premier et le deuxième domaine. En ce qui concerne le premier domaine, toutes ses valeurs figurent dans la contrainte. En revanche, la valeur c ne figure pas dans la contrainte. On peut donc l'enlever du domaine. Considérons ensuite la contrainte entre le premier et le troisième domaine. Une fois de plus, toute les valeurs du premier domaine sont présente, et aussi toute les valeurs du troisième. Il n'y a donc pas de réduction possible. Considérons enfin la dernière contrainte, celle entre le deuxième et le troisième domaine. La valeur c ne figure toujours pas dans les contraintes, et la valeur y non plus. On peut donc enlever la valeur y. Seulement, si y ne figure plus dans le deuxième domaine, on peut alors enlever la valeur 2 du premier domaine car elle était attachée seulement à la valeur de y. Après vérification de l'ensemble, on s'aperçoit que le domaine est réduit au maximum. Le graphe prend alors la configuration suivante :

A travers ce petit exemple, on se rend compte que il faut faire plusieurs passages sur les contraintes pour vraiment tout réduire. En fait, quand un domaine se trouve réduit, il faut réexaminer toutes les contraintes qui ont rapport avec ce domaine.

Définition 4 : Soit un PSC noté . Ce PSC est à domaine réduit si et seulement si .

Définition 5 : Deux PSC P et Q sont équivalents si et seulement si l'ensemble de leurs solutions coïncide. Cette relation est évidemment une relation d'équivalence.

Donnons maintenant un algorithme qui permet à un PSC donné et noté P, de déterminer un PSC P' réduit et équivalent. Notons que dans une classe d'équivalence, il existe bien entendu plusieurs PSC réduits et différents. Cet algorithme est connu sous le nom de " cohérence d'arc ".

Reduit-domaine (V,D,C)

pour tout (i,j) tels que C(i,j) existe

Queue=(i,j)

tant que Queue non vide

(i,j) :=retire-element(Queue)

E=ens. vide

test-cohérence(i,j,E)

si E non vide alors D(i)=D(i)-E fin

si D(i) vide alors "pas de solution"

sinon pour tout (w,i) tels que C(w,i) existe

Queue := Queue ++ (w,i)

fin pour tout

test-cohérence(i,j,E)

pour tout d dans D(i) faire

booleen := faux

pour tout v dans D(j)

si (d,v) dans C(i,j) alors booleen := vrai

sinon E := E ++ d

fin

Recherche de solutions

La réduction du domaine est déjà une bonne amélioration, mais elle n'est pas suffisante. Le domaine réduit peut encore être très vaste. Il est encore impossible de tenter d'examiner au cas par cas tous les éléments du domaine réduit. Plutôt que d'affecter à toutes les variables des valeurs et ensuite de vérifier que toutes les contraintes sont satisfaites, on va employer ce qui s'appelle en anglais le backtracking. Cette méthode est plus rapide et utilise moins de mémoire. Le principe consiste à construire une solution progressivement. On affecte la première variable parmi une des valeurs de son domaine, on fait de même pour la seconde, on vérifie que la contrainte correspondant à ces deux variables est satisfaites. Si c'est le cas, on affecte une troisième variable dans son propre domaine et on recommence; sinon on reaffecte la seconde variable. Si une variable a déjà parcouru l'ensemble de son domaine, alors on remonte d'un niveau de variable, et ainsi de suite. Si toute les variables ont réussi à être affectées, on a alors trouvé une solution. On donne l'algorithme suivant :

Procedure BackTracking(i)

pour tout v dans D(i)

S(i) := v;

si Verifie-coherence(i) alors

si i=n alors retourne s(1), s(2), ...s(n)

sinon Backtracking(i+1)

Procedure Verifie-coherence(i)

pour j dans 1, ..., i-1 faire

si (s(i), s(j)) non element de C(i,j) alors retourne faux

sinon retourne vrai

Toujours pour optimiser le système de recherche, on peut faire des réductions dynamiques des domaines. Supposons qu'une certaine partie des variables ait réussi à être affectée. Certaines contraintes opérant entre des variables affectées et des variables encore non affectées implique une réduction dynamique du domaines des variables non encore affectées. Réduire ce domaine s'appelle faire du Forward Cheking. Cette méthode permet dans la plupart des cas accélérer la recherche sans trop s'enfoncer dans l'arbre. On trouvera dans la bibliographie des algorithmes de Forward Checking, notamment dans l'article de Camilo Rueda [Rue 98], qui a proposé une amélioration (Evaluation paresseuse)[RuVa 97].

6. Situation

OpenMusic comprend plusieurs librairies dont l'une s'appelle Situation. Situation est une panoplie de fonctions supplémentaires utilisables sous OpenMusic. Il est donc nécessaire, avant chaque utilisation de patch utilisant des fonctionnalités propres à Situation, de charger la librairie. La librairies Situation comprend quatres répertoires qui sont montrés sur la figure ci-dessous à gauche :

Le premier répertoire contient la fonction c-solver qui est en fait le moteur de satisfaction de contrainte muni d'une interface utilisateur en cohérence avec les opérateurs rencontrés plus loin. Le répertoire standard constraints contient une panoplie de fonctions fabriquant des contraintes appliquées à la musique. Ces fonctions sont réparties dans les quatres sous-répertoires suivant :

- " vint control " contient les fonctions contrôlant des intervalles verticaux, c'est à dire les intervalles sur des accords.

- " hint control " contient les fonctions contrôlant des intervalles horizontaux, c'est à dire d'une même voix sur deux accords ou plus.

- " pitch control " contient les fonctions contrôlant les hauteurs des voix.

- " profile control " contient les fonctions contrôlant l'évolution des voix (montée, descentes, ...)

Le répertoire " user constraints " donne la possibilité à l'utilisateur de créer ses propres contraintes tout en se plaçant dans le cadre de l'interface du moteur. Il est muni des deux fonctions " user-cnstr " et " prev-instances " :

Le répertoire " generic problems " est le plus intéressant de tous, il permet de travailler directement avec les composantes du moteur de satisfaction de contrainte. Les fonctions qu'il contient seront largement employées par la suite, ces fonctions sont " variable-domains " et " generic-cnstr " :

Le dernier répertoire " utilities " permet à l'utilisateur employant l'interface de pouvoir transcrire les solutions trouvées par le moteur en notation musicale d'OpenMusic. Il s'agit des fonctions " ch-sol ", " part-sol ", " bpf-ambdef " et " default-fill ".

7. Situation mis à l'épreuve sur un exemple simple d'harmonie tonale

La première approche d'utilisation effectuée avec Situation est un cas particulier d'harmonisation en musique tonale. Il s'agit d'harmoniser un cantus firmus au soprane à deux voix. On se limitera aux règles suivantes :

- Pas de quintes, et pas d'octaves parallèles et directes.

- Pas plus de deux tierces ou deux sixtes consécutives.

- Pas de notes identiques répétées

- Mouvement le plus conjoint possible.

- Mouvement le plus contraire possible.

Pour construire les patches, on va se limiter à utiliser l'interface de Situation. Voici le premier patch, il est chargé de faire un contrepoint à deux voix à partir de celle du haut :

Le deuxième patch utilise le premier, et présente une petite interface pratique pour l'utilisateur :

Expliquons le premier patch, celui qui s'appelle " harmoniseur ". Il est muni de deux entrées, l'une par laquelle une liste correspondant au cantus firmus à la partie supérieure est connecté dans une notation simple (do3 = 1, re3 = 2, mi3 = 3 et ainsi de suite). Notons que l'on travaille uniquement dans la gamme de do majeur et que la mélodie ne comporte pas de modulation ni d'emprunt dans d'autres tonalités. D'une part, le patch calcule la longueur de cette liste, et d'autre part, il convertit la mélodie en notation compatible avec la fonction de la librairie Situation " pitch/ch-filt ". Cette dernière fonction construit une contrainte qui sera communiquée avec d'autres au moteur de recherche " c-solver ". Dans notre exemple, la fonction " pitch/ch-filt " prend la liste (1 2 3 4 3 4 5 4 3 2 1) et la convertie en la liste donnée ci-dessous :

(0 (AND (* 60)) 1 (AND (* 62)) 2 (AND (* 64)) 3 (AND (* 65)) 4 (AND (* 64)) 5 (AND (* 65)) 6 (AND (* 67)) 7 (AND (* 65)) 8 (AND (* 64)) 9 (AND (* 62)) 10 (AND (* 60)))

En effet, Situation permet que l'on impose une mélodie à une voix, mais moyennant cette notation. Dans 0 (AND (* 60)), le 0 signifie le premier accord (on compte toujours à partir de 0), le (AND (* 60)) signifie que les voix inférieures sont libres mais que le soprane est fixée à 60 (do3 en notation Midi). Les instructions suivantes dans la liste sont de même. On met en valeur ici un problème rencontrée souvent en CAO, c'est celui de la conversion de données. Il apparaît sans cesse. En effet, dans certains cas, une représentation est meilleurs qu'une autre pour faire un style précis d'opération. Dans d'autres cas elle s'avère moins bien adapté. Dans les problèmes résolu par programmation par contraintes, la notation employée est très importante. Dans certaines notations, les domaines de recherche sont des fois lourd à exprimer que l'on rentre finalement un domaine plus grand et on diminue donc l'efficacité de la recherche. C'est pourquoi il ne faut pas hésiter à faire des fonctions de conversion. De plus en Lisp, cela se fait aisément. Voici par exemple le code de la fonction " convertit-mélodie ".

(defun convertit-melodie (liste)

(let ((longueur (length liste))

(compteur 0)

(resultat nil)

(liste2 liste))

(loop (and (= compteur longueur) (return resultat))

(setf resultat (append resultat

(list compteur (list 'and (list '* ((lambda (x) (cadr (assoc x '((a 55)

(z 57)

(e 59)

(1 60)

(2 62)

(3 64)

(4 65)

(5 67)

(6 69)

(7 71)

(8 72)))))

(car liste2)))))))

(setf liste2 (cdr liste2))

(incf compteur))))

On a utilisé " loop " de façon très rudimentaire pour faire une boucle. " loop " effectue indéfiniment toutes les instructions qu'elle contient jusqu'à ce qu'elle rencontre la fonction " return ". Ici, on s'arrête quand la variable locale " compteur " est égale à la longueur de la liste passée en entrée. Pour programmer ce genre de fonction, d'autres types d'algorithme sont aussi utilisés.

Globalement, le patch " harmoniseur " est centré sur le moteur de recherche " c- solver " . " c-solver " prend en entrée les notes qu'il a le droit d'utiliser, c'est la liste ((48 50 52 53 55 57 59 60 62 64 65 67 69 71 72 )) . Les notes sont encore une fois codée en notation Midi. Ici, les deux mélodies doivent se trouver dans l'ambitus do2-do4. " c- solver " prend en entrée aussi une liste ( l (1 2 3 4 5 4 5 7 9)) indiquant les intervalles horizontaux permis. Un intervalle horizontale est un intervalle sur une voix. Un intervalle vertical est un intervalle entre deux voix d'un accord. Ici, on permet au moteur de trouver des séquences ou les intervalles horizontaux permis à la voix de basse sont inférieurs ou égal à la sixte majeure. Une autre entrée de " c-solver " est celle indiquant le nombre d'accord à trouver. Et enfin, toutes les contraintes listées sont fournis au moteur. Le moteur sort alors des séquences qu'il faut encore convertir pour qu'elles puissent être correctement interprétées par les objets d'OpenMusic.

Ainsi, le moteur prend en compte six contraintes. On a déjà vu que la contrainte utilisant " pitch/ch-filt " servait à imposer le cantus firmus. La contrainte utilisant " hint-filt " sert à faire des mouvement le plus conjoint possible. Ce genre de contrainte est difficile à exprimer car il s'agit ici ni d'une interdiction, ni d'une obligation. Ici, on a exprimer le fait que l'on désire des mouvements conjoints en précisant que sur une séquence de 6 notes (donc de 5 intervalles horizontaux), on ne permettait que seulement deux au plus intervalles horizontaux dépassant la tierce mineur. La contrainte est exprimée de manière très lourde comme l'illustre la grosse boite de données ci-dessus. Notons que l'on aurait pu écrire un programme construisant cette grosse boite, mais ce programme aurait servi une fois, et il aurait peut-être coûté autant de temps sinon plus pour sa conception. En tout cas, l'écriture de cette contrainte laisse à désirer.

La contrainte utilisant " v/v-prof " sert à favoriser les mouvements contraires. Elle interdit au moteur de construire plus d'un enchaînement consécutif et parallèle. En d'autre termes, si un enchaînement d'accord est à mouvement parallèle, le suivant sera forcément à mouvement contraire. Cette contrainte est, de même que la précédente, exprimée de façon assez relative, voire douteuse. Mais avec l'interface de Situation, on est obligé de pratiquer une telle écriture.

Les autres contraintes, en revanche s'expriment beaucoup mieux puisque ce sont des contraintes qui, interdisent ou obligent totalement certains faits. Par exemple, on interdit les quintes et octaves parallèles avec la fonction " vintsuc/pos-filt " . On interdit aussi par la même fonction trois sixtes ou trois tierces consécutives. Remarquons qu'il faut penser à dire au système, trois sixtes majeures, trois sixtes mineures, et de même pour les tierces. Cela fait une lourdeur d'écriture dûe à la notation imposée par le système d'interface de Situation. Une dernière contrainte interdit de faire deux notes consécutives identiques. Mais cette contrainte est superflue car la liste ( l (1 2 3 4 5 4 5 7 9)) l'interdit déjà.

Notons que l'on a utilisé une notation déclarative des propriétés mais pas de domaine de recherche explicite. En fait, le domaine de recherche est calculé au fur et à mesure que la recherche des solutions s'effectue. Le domaine est calculé par rapport aux notes précisées en ambitus ((48 50 52 53 55 57 59 60 62 64 65 67 69 71 72 )) et aux intervalles horizontaux précisés ( l (1 2 3 4 5 4 5 7 9)) .

Le deuxième patch utilise le premier pour harmoniser le cantus firmus. Il prend en compte le cantus firmus, calcule sa longueur, construit une liste de rythme en fonction de cette dernière et envoie l'information à l'objet " voice ". L'harmoniseur envoie aussi sa solution à l'objet " voice ".

On montre sur la figure ci-dessous un exemple de résultat :

Le temps de recherche et quasiment nul (quelques millisecondes à chaque essai) et les formules musicales trouvées sont toujours très différentes mais de qualité musicale à peu près constante. Ici, le moteur essaie de trouver une solution et la renvoie. Un processus aléatoire instancie les variables pour qu'à chaque lancement de la recherche, une solution différente soit renvoyée. La figure ci-dessous montre une autre solution :

Faisons un bilan des difficultés rencontrées :

- la notation de l'interface du moteur est inadaptée à la musique tonale, cela peut laisser penser qu'elle n'est peut-être pas efficace pour d'autre systèmes de musique contemporaine. En fait, on est amené à penser que avant de programmer par contrainte, il faudrait choisir un mode de notation le plus près possible de la façon de penser. Dans la musique tonale qui ne module pas, ou ne fait pas d'emprunt, l'harmoniste pense en degré d'accord car c'est la façon la plus cohérente d'organiser les accords.

- le système de fonction proposé par l'interface de Situation pour créer des contraintes n'est pas suffisant pour exprimer toute sorte de contrainte employé dans la musique tonale, notamment pour les contraintes qui, à la différence d'interdire ou d'obliger, pousse les solutions à satisfaire au mieux une propriété. A ce propos, on classifie les contraintes en quatre types :

- les contraintes positives (contraintes qui obligent)

- les contraintes négatives (contraintes qui interdisent)

- les contraintes d'optimisation (elles ne font pas de restrictions de solutions mais peuvent accélérer le moteur lors de la recherche).

- les contraintes douces (celles qui poussent le système à ce que les solutions satisfassent le plus possible une certaine propriété).

La fonction " c- solver " contient le moteur dans une grosse enveloppe (ce que l'on a appelé jusqu'ici l'interface). Mais, optionnellement, on peut utiliser " c-solver " en étant débarrassé de cette enveloppe, et accéder directement au moteur. Dans ce cas, il faut spécifier au moteur le nombre de variable, le domaine de chaque variable (donné à l'aide de la fonction " variable-domains ") et les contraintes (générées par la fonction " generic- cnstr "). Désormais, l'utilisation du moteur sera faite sans l'interface.

8. Séquences d'harmonie tonale à quatres voix

8.1. Introduction

Situation est maintenant utilisé sans son interface. Le patch correspondant à une telle utilisation est de la forme montrée ci-dessous :

Cette représentation montre mieux le parallélisme avec Situation et la modélisation mathématiques établies précédemment. Avec une telle configuration, Situation est paré à gérer des situations très diverses, et pas forcément en rapport avec la musique.

On va à présent utiliser cette configuration pour faire de l'harmonie à quatre voix et se rendre compte des avantages et inconvénients de Situation.

Pour cela, on va adopter un nouveau système de notation des hauteurs et des accords. On va coder chaque note blanche du clavier de 1 à 36 (do1 à do5). On considère toujours que les séquences harmoniques ne sont pas modulantes, et n'emprunte pas, même de façon passagère des notes étrangères à la gamme de do majeur. Un accord sera noté dans une liste contenant des entiers qui sont les intervalles entre une voix donnée et la basse. Ainsi, l'ensemble (8 (2 4 7)) représente l'accord à quatre voix (do3 mi3 sol3 do4).

Pourquoi cette notation ? Déja, elle privilégie la basse et chaque harmoniste le sait : la basse guide l'harmonie. Lors d'une harmonisation à vue, l'accompagnateur réfléchit surtout à la conduite de la basse et déduit ensuite les parties restantes. Ensuite, coder un accord sur une liste minimise le nombre de variable. Imaginons par exemple qu'un accord soit codé sur un nombre de variables égal au nombre de voix, le moteur s'en sortirait beaucoup moins facilement. Si on se limite dans l'harmonie aux accords à l'état fondamental et au premier renversement, cela fait une vingtaine d'accord à mémoriser. C'est très peu par rapport à ce que donnerait une codification par voix. Enfin, les contraintes de la musique tonale s'expriment de façon remarquable dans une telle notation.

Il faut remarquer que l'interface de Situation utilise une notation semblable, sauf que les hauteurs fixes des notes se calculaient par intervalles successifs. Par exemple, l'accord (do3 mi3 sol3 do4) est noté (48 (4 3 5)), 48 correspondant à la hauteur midi du do3, le mi3 étant do3 + 4, le sol3 étant mi3 + 3, et le do3 étant sol3 + 5.

Il reste maintenant à écrire le domaine et les contraintes. Commençons par le domaine.

8.2. Construction du domaine

Pour une séquence de n accords, il faut 2n variables car chaque accords est codé sur deux variables. Chaque basse est compris dans un certains ambitus, on choisit par exemple une basse de voix chanté (4 17) == (fa1 mi3). Les accords sont compris dans un répertoire d'accords possibles. On choisit simplement des accords parfait dans leur état fondamental et de premier renversement. On aboutit alors au patch suivant :

" liste-accord " est en fait une variable déclarée à l'interpréteur Lisp. Elle est défini de la façon qui suit :

(setf liste-accord '((4 5 6 7 8 9 10 11 12 13 14 15 16 17)

((function (lambda (x) (car (last x))))

(

(0 2 4) (2 2 4) (2 4 4)

(2 4 7) (2 4 9) (4 7 9)

(4 9 11) (7 9 11) (4 9 14)

(9 11 14) (7 11 16)

(0 2 5) (2 5 7) (2 5 9)

(5 7 9) (5 9 12) (7 9 12)

(5 9 14)))))

liste-accord contient une liste de deux domaines, celle correspondant à la basse, et une autre correspondant aux accords. Le domaine correspondant aux accords est muni d'une fonction (lambda (x) (car (last x))). Cette fonction appliquée à toute la liste d'accord suivant permet de structurer le domaine des accords comme étant un arbre à deux niveaux. La fonction donnée permet de calculer très vite le soprane.

Le patch duplique liste-accord n fois, n étant le nombre d'accords voulu. Il effectue ensuite une petite conversion pour être lu correctement par la fonction de Situation " variable- domains ". Le tout est envoyé en sortie.

8.3. Construction des contraintes

On construit les contraintes à l'aide de la fonction " generic-cnstr ". Décrivons sommairement cette fonction à l'aide d'une contrainte servant d'exemple. Il s'agit d'une contrainte positive. Son rôle est d'imposer l'état de renversement sur des accords précis. La fonction " generic-cnstr " est munie de quatre entrées.

- La première entrée est destinée à recevoir un prédicat. On rappelle qu'une contrainte est avant tout un prédicat sur des variables du domaine. On rentre donc une fonction prédicat en tant que donnée. Ceci est permis par OpenMusic au moyen de la marque " lambda " que l'on met sur l'icône de la fonction interprétée comme une donnée.

- La seconde entrée est la liste des variables sur lesquels la contraintes va être appliquée. Cela peut être une liste de la forme (1 3 5 7) si on veut ne prendre en compte que les variables d'intervalles.

- La troisième entrée est une liste servant à dire comment construire les contraintes à partir du prédicat et de la liste de variables. Dans cet exemple, (s i 1) signifie de faire des contraintes sur des variables successives " s ". Le " i " signifie que le prédicat a besoin pour être évaluer non seulement de la valeur instanciée des variables concernées, mais aussi de leur index. Le " 1 " donne l'incrémentation faite sur la liste passée dans la deuxième entrée. Le patch " renv " construit toutes les contraintes sur les variables concernées :

C(1) C(3) C(5)....

- La quatrième entrée spécifie à quelle niveau de l'arbre de la variable la contrainte se rapporte (il s'agit de l'arbre dont on parle lors de la construction du domaine).

Notons que Situation est capable d'interpréter non seulement des contraintes binaires, mais aussi des contraintes sur un nombre quelconque de variables. Les optimisations comme le forward checking, le backtracking sont appliqués uniquement sur les contraintes binaires. Dans certains cas, les contraintes n-aires peuvent être ramenées à des contraintes binaires et ces algorithmes sont alors appliqués. Il est possible mathématiquement de ramener des contraintes n-aires à des contraintes binaires, mais cela pose dans la plupart des cas des problèmes de complexité.

8.4. Assemblage

Une fois la construction du domaine fait et les contraintes réalisés, on peut assembler le tout. Le résultat montré est le patch suivant qui réalise des harmonies à quatres voix avec un soprano imposé. On retrouve évidemment la structure présentée schématiquement un peu plus haut. L'avantage de ce système est qu'il est très modulaire. On peut rajouter et enlever à sa guise des contraintes sans toucher à la structure du système. Certaines contraintes prennent des informations à l'extérieur du domaine. C'est le cas des contraintes conjoint, soprano, degré et renversement. La longueur du soprano est prise en compte par toute les contraintes car c'est elle qui fixe le nombre d'accord à construire.

La contrainte " renv " précise le renversement des accords. La liste passée dans la contrainte " renv " indique l'état de renversement des accords.

- * signifie que l'état de l'accord peut être quelconque,

- 0 signifie que l'état de l'accord doit être à l'état fondamental,

- 1 signifie que l'état de l'accord doit être au premier renversement,

- 2 signifie que l'état de l'accord doit être au second renversement.

La liste passée au patch " degré " indique le degré des accords. Le chiffre correspond au degré de l'accord (1 pour do majeur, 2 pour ré mineur, ...).

La contrainte " no7 " interdit au moteur de mettre un accord du septième degré à l'état fondamental où à l'état de second renversement.

La contrainte " oct+quint parallel " interdit les quintes et les octaves parallèles.

La contrainte " soprano " impose le soprano

La contrainte " basse " ne fait rien mais s'ajoute à la contrainte soprano pour accélérer de 20% environ le temps de recherche de solutions.

La contrainte " conjoint " pousse les solutions à être constituées de mouvements les plus conjoints possible, le plus contraire possible et les plus monotones possibles (c'est à dire que les changements de directions des voix sont minimisés). Cette contrainte sera détaillée plus loin.

On retrouve bien les quatres types de contraintes données précédemment. En effet, les contraintes " soprano ", " renv " et " degre " sont des contraintes positives. Ce sont les plus rapide car elles réduisent les domaines extrêmement vite. Ceci est compréhensible, puisque parmi toute les possibilités d'un domaine, elles n'en sélectionne que très peu. La technique du backtracking leur étant appliquée est très efficace. Les contraintes " no7 ", " no quint parallel " sont des contraintes négatives. Les prédicats sont beaucoup moins sélectifs que pour les contraintes positives et ne réduisent donc pas tellement le champ de recherche du moteur. La contraintes " basse " est une contrainte optimisante. La contrainte " conjoint " est une contrainte douce. Ce type de contrainte augmente le temps de recherche, mais elle n'est pas exprimable autrement que ce qui va être présenté plus bas.

Présentons tout de même les résultats harmoniques de ce patch :

On a évidemment réglé les coefficients de la contraintes " conjoint " de manière à ce que le nombre de solution ne soit pas nul, et ne soit pas non plus énorme (on demande au moteur d'afficher toute les solutions).

8.5. Contrainte " conjoint "

On va maintenant décrire le fonctionnement de la contrainte " conjoint ". Cette contrainte fait appel à une fonction croissante que l'on nomme la fonction seuil. Elle associe à chaque indice des accords un nombre arbitraire. Cette fonction est stockée sous forme de tableau dans l'interpréteur Lisp. Le principe de cette contrainte est qu'elle comptabilise au fur et à mesure de la construction d'une solution les erreurs dues au fait soit que le mouvement est disjoint, parallèle, non monotone. Les sanctions sont quantifiées par des coefficient donnés avant la recherche par l'utilisateur. Ce sont les trois coefficient apparaissant dans le patch. Plus ces coefficients sont forts, et plus la contrainte est restrictive. Notons que ce type de contraintes n'a jamais été appliqué dans Situation.

On montre le code correspondant au prédicat construisant la contraintes " conjoint " :

(setq *total-sanction* (make-array 40))

(setq *sens-parcours* (make-array 40))

(defun mouvement-conjoint-monotone-contraire (b1 i1 b2 i2 basse1 inter1 basse2 inter2

seuil-sanction conjoint parallele monotone)

"essaye de faire un mouvement conjoint et monotone.

attention, ce programme fait appel à setq, donc utilise des variables reservées.

*total-sanction* donne la sanction dûe à la mauvaise qualité du mouvement.

*sens-parcours* dit si ça monte ou ça descend."

(let* ((vect1 (coerce (mapcar #'(lambda (n) (+ basse1 n)) (push 0 inter1)) 'vector))

(vect2 (coerce (mapcar #'(lambda (n) (+ basse2 n)) (push 0 inter2)) 'vector))

(sanction 0)

(soprano (- (array-total-size vect1) 1)))

; mouvement-conjoint

(loop for i from 0 to (1- soprano) do

(incf sanction (* conjoint (nth (abs (- (svref vect2 i) (svref vect1 i)))

'(0 0 1 2 2 2 2 2 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10)))))

; mouvement-parallele

(and (<= 0 (* (- (svref vect2 soprano) (svref vect1 soprano))

(- (svref vect2 0) (svref vect1 0))))

(incf sanction parallele))

; basse-monotone

(and (> 0 (* (- (svref vect2 0) (svref vect1 0)) (svref *sens-parcours* b1)))

(incf sanction monotone))

; affectation

(setf (svref *sens-parcours* b2) (signum (- (svref vect2 0) (svref vect1 0))))

(setf (svref *total-sanction* b2) (+ (svref *total-sanction* b1) sanction))

;information ecran

; (format t "b2 : ~A~%" b2)

; (format t "sanction : ~A~%" sanction)

; (format t "sens-parcours : ~A~%" (svref *sens-parcours* b2))

; (format t "total-sanction : ~A~%" (svref *total-sanction* b2))

; (format t "seuil-sanction : ~A~%" (svref seuil-sanction b2))

; (format t "conjoint par monot : ~A ~A ~A ~%" conjoint parallele monotone)

; predicat

(and (> (svref seuil-sanction b1) (svref *total-sanction* b2)))

))

8.6. Contrainte " basse "

La contrainte " basse " est une contrainte d'optimisation. Elle est utile si et seulement si la contrainte " soprano " est utilisée. On peut alors se demander pourquoi l'optimisation n'aurait pas pu être rentrée dans la contrainte " soprano ". La raison est toute simple, si c'était le cas, alors il n'y aurait pas d'optimisation. On s'explique.

La fonction " soprano " génère des contraintes qui utilisent la basse et la liste d'intervalle d'un accord, soit en tout deux variables. Donc, pour vérifier si la contrainte est satisfaite, il faut instancier la basse et le reste de l'accord. En fait, on peut voir que de toute façon, certaines basses ne pourront pas convenir. Donc, il est judicieux de faire une sorte de précontrainte pour trouver le soprano ne portant que sur la basse. Cette contrainte ne sera pas suffisante pour imposer le soprano, mais empêchera l'instanciation de basse inutiles. Dans la pratique, cette contrainte améliore la recherche du moteur et dans tous les cas. en effet, quatre basses sur sept ne peuvent correspondre à un même soprano. En fait, cette optimisation tient compte que le moteur utilise la technique du backtracking. Ce genre de contraintes est tout à fait nouveau sur le moteur Situation. On montre le code des contraintes " soprano " et " basse " :

(defun soprane (b1 i1 basse inter soprano)

"impose un soprano."

(= (+ basse inter) (svref soprano b1)))

(defun impose-basse ( b1 basse soprano)

"impose la basse pour aller plus vite dans la recherche."

(member (- (svref soprano b1) basse) '(0 2 4 5 7 9 11 12 14)))

et les patches de contraintes dans lesquels ces fonctions s'insèrent :

8.7. Convergence des coefficients de la contrainte " conjoint "

Le problème rencontré avec la contrainte douce " conjoint " réside dans le fait qu'il faut choisir les coefficients avant de lancer la recherche. Si les coefficients choisis sont trop faibles, le moteur va fournir une quantité gigantesque de solutions si bien que l'utilisateur ne pourra jamais toutes les apprécier. Si les coefficients sont au contraire trop élevés, alors le moteur risquera de ne trouver aucune solution. On peut tâtonner à la main pour ajuster les coefficients, mais il est aussi possible d'ajuster automatiquement leur réglage. On fait en quelque sorte un asservissement des trois coefficients. Pour représenter le problème simplement et par la même, faciliter la compréhension, on imaginera que l'on a seulement deux coefficients au lieu de trois. De cette façon , on peut représenter les ensembles sur un espace à deux dimensions qu'est la feuille de papier. On s'intéresse à la figure ci-dessous.

La figure ci-dessous représente un quart d'espace à deux dimensions. Chaque coordonnées est celle d'un coefficient. Donc chaque point du plan représente, un couple de coefficients appliqués à la contrainte douce. A ce couple de coefficient est renvoyé par le moteur le nombre de solutions correspondant. On partage le quart de plan en trois zones :

- une zone A où les coefficients sont petits, et donc où le nombre de solutions renvoyées par le moteur dépasse une quantité raisonnable N.

- une zone B où les coefficients sont grands, et donc où le nombre de solutions renvoyée est nul car la contrainte conjoint est du coup très exigeante.

- une zone C où les coefficients sont ni trop faibles, ni trop forts et où le nombre de solutions est non nul et inférieur à N, c'est à dire raisonnable.

La figure fait penser à un bord de mer. Pour cette raison, on appellera la zone A la terre, la zone B la mer et la zone C la plage. La frontière entre la terre et la mer sera appelé la falaise. Le but, ici, est de trouver la plage. Le chemin 1 sur la figure est un chemin aboutissant à la falaise. Le chemin 2 aboutit à la plage.

Pour asservir les coefficients, on adopte la démarche suivante :

- on part de (0, 0), c'est à dire chaque coefficients est nul. On a de grande chance d'être dans la zone A, sinon, le problème ne comporte pas de solution.

- on incrémente les coefficients aux hasard jusqu'à arriver à une frontière. Si la frontière est une plage, c'est fini. Si c'est une falaise, alors il faut longer une falaise et espérer aller sur une plage. Cette façon a été implémenté dans un patch présenté dans la suite.

On peut modifier cette démarche en prenant le chemin sur l'un des axes. On incrémente pour cela un seul des coefficients jusqu'à arriver sur la frontière. Si c'est la plage, c'est fini, sinon, on longe toute la côte.

Les avantages de cette méthode est que l'on est sûr de trouver une plage s'il en existe une. Les inconvénients sont que cela coûte plus de temps de recherche en moyenne et que le côté aléatoire de la démarche précédente n'existe plus.

Montrons maintenant les patches faisant l'asservissement automatiques des coefficients :

La fonction " set-cpm " remet les trois coefficients à 0. La fonction " donne-cpm " affiche la valeur courante des trois coefficients. le mot " cpm " vient simplement des initiales des trois coefficients (c comme conjoint, p comme parallèle, m comme monotone). On retrouve la procédure habituelle d'affichage des solutions avec les objets d'OpenMusic requis (poly et voice). Enfin, on remarque que l'on connecte le soprane, les degrés, les renversements et le nombre N de solutions raisonnable maximum dans le " omloop ". La boucle enferme le patch de programmation par contraintes. La figure suivante montre l'intérieur de la boucle :

La boucle s'arrête si le nombre de solutions données par le moteur est compris strictement entre 0 et N. A chaque passage, la fonction " next-cpm " donne les valeurs suivantes pour les coefficients. La façon d'explorer dépend uniquement de ce que fait cette dernière fonction. Pour le test de la boucle, on fait appel au patch " mypatch " montré sur la figure suivante :

Les fonctions " donne-cpm ", " next-cpm " et " set-cpm " sont regroupée dans une closure. Ici, cette structure propre à la programmation Lispienne est tout à fait adaptée. Voici le code :

(let ((c 0) (p 0) (m 0)

(prev-c 0) (prev-p 0) (prev-m 0))

(defun set-cpm (val-c val-p val-m)

"remet c p m à val-c val-p et val-m."

(setf c val-c)

(setf p val-p)

(setf m val-m)

(setf prev-c val-c)

(setf prev-p val-p)

(setf prev-m val-m))

(defun next-cpm (long)

"donne les nouvelles valeurs de c p et m en fonction de long.

si long = 0 alors on prend prev-c, ...

sinon, une des valeurs parmi c p m va etre incrementee de 1."

(if (= long 0) (progn (setf c prev-c)

(setf p prev-p)

(setf m prev-m))

(let ((i (nth-random '(1 2 3))))

(setf prev-c c)

(setf prev-p p)

(setf prev-m m)

(cond ((= i 1) (incf c))

((= i 2) (incf p))

((= i 3) (incf m)))))

(print c)

(print p)

(print m)

(print prev-c)

(print prev-p)

(print prev-m)

nil)

(defun donne-cpm () (list c p m)))

8.8. Ordonnancement dynamique

La nouvelle structure présentée pour faire de l'harmonie à quatre voix est beaucoup plus performante que celle utilisant l'interface de Situation. Cela dit, on a pensé à une modification du moteur qui pourrait l'améliorer dans certains style de recherche utilisant le Backtracking. On appelle cette modification l'ordonnancement dynamique.

Quand le moteur de Situation instance une variable, il la prend au hasard parmi les éléments du domaine restant correspondant à cette variable. Au lieu de choisir les variables au hasard, il serait mieux qu'il prenne en premier celles qui auraient le plus de chance de marcher. Par exemple, dans notre cas où il faut faire une suite d'accord le plus conjoint possible, vaut mieux tester d'abord les accords qui sont le plus conjoint au dernier instancié. Le moteur mettrait un peu plus de temps pour trouver toute les solutions car il devrait calculer un ordonnancement à toute les variables. En revanche, il trouverait plus vite la première solution si c'est ce que le programmeur souhaite en premier lieu. Il faut savoir que dans les applications musicales, les domaines sont immenses, et les solutions peu nombreuses. La pratique nous montre que les solutions sont réparties en grappe dans le domaine, comme le montre schématiquement la figure ci-dessous :

8.9. Motifs

La dernière application que l'on va montrer avec Situation est celle concernant ce que l'on appelle les motifs. Un motif est une fonction où toutes les hauteurs sont relatives.

Sur une courbe donnée comme sur la figure ci-dessus, le motif correspondant ne contiendra uniquement les informations aux sens de la pente, et aux hauteurs relatives. Le motif contient aussi une mémoire à fenêtre finie, c'est à dire qu'une hauteur qui n'est pas apparue depuis un certain temps défini par la longueur de la fenêtre est oublié. La longueur de la fenêtre est un paramètre du motif. On construit alors la contrainte motif qui impose à une voix de suivre un motif donnée par une courbe. Ce type de contrainte s'insère mal avec la technique du backtracking car le moteur peut chercher longtemps des solutions dans des lieux où l'on est sûr qu'il n'y aura pas de solutions. Considérons par exemple le motif suivant :

Si le moteur n'instancie pas la deuxième variable beaucoup plus haut que la première, il ne pourra pas trouver de solution au vu de ce qu'impose le profile par la suite. Il va instancier des variables jusqu'à ce qu'il soit coincé. Seulement après, il reviendra en arrière.

Il faut donc que la contrainte soit telle qu'elle tienne compte de l'évolution de la suite du motif. Pour cela, on regarde plus loin dans le motif et on compte le nombre de hauteur qu'il faudra plus tard intercaler. Voici le code de la fonction fabriquant la contrainte motif :

(defun printn (&rest a) (loop for i in a do (print i)))

(defun printc (commentaire &rest a) (print commentaire) (true (loop for i in a do (print i))))

(defun affiche (commentaire a) (format t "~A : ~A ~%" commentaire a) a)

(defvar maximum (make-array '(4 40)))

(defvar minimum (make-array '(4 40)))

(defvar memoire (make-array '(4 40)))

(defun dp< (liste elem)

"donne la place d'un element dans une liste ordonnee."

(catch 'jl

(loop for i from 0 to (1- (length liste)) do

(and (< elem (elt liste i))

(throw 'jl i)))

(length liste)))

(defun dp<= (liste elem)

"donne la place d'un element dans une liste ordonnee."

(catch 'jl

(loop for i from 0 to (1- (length liste)) do

(and (<= elem (elt liste i))

(throw 'jl i)))

(length liste)))

(defun donne-place (aliste n)

"donne la place dans la a-liste de n."

(catch 'jl

(loop for i from 0 to (1- (length aliste)) do

(and (< n (car (elt aliste i)))

(throw 'jl i)))

(length aliste)))

(defun insere (liste a n)

"insere l'element dans liste a sa place."

(let ((nbis (cond ((< n 0) 0)

((> n (length liste)) (length liste))

(t n))))

(append (subseq liste 0 nbis) (list a) (subseq liste nbis))))

(defun impose-motif3 (b i basse inter voix fenetre motif ambitus)

"impose le motif d'une voix avec une fenetre de memoire donnée.

regarde en avant pour choisir judicieusement les variables afin de ne pas

s'enfoncer inutilement dans l'arbre de recherche."

(let* ((v (+ basse (nth voix (push 0 inter))))

(a (/ b 2))

(motif-courant (nth a motif))

(motif-restant (sort (remove motif-courant (remove-duplicates (subseq motif (1+ a)))) #'<))

(tampon-sup (length (subseq motif-restant (dp< motif-restant motif-courant))))

(tampon-inf (length (subseq motif-restant 0 (dp< motif-restant motif-courant)))))

;(print 'go)

;(printn voix v a motif-courant motif-restant tampon-sup tampon-inf)

(cond ((= a 0)

; (print 'a=0)

(setf (aref maximum voix a) (1+ (- (cadr ambitus) tampon-sup)))

(setf (aref minimum voix a) (1- (+ (car ambitus) tampon-inf)))

; (printn (aref maximum voix a) (aref minimum voix a))

(and (< v (aref maximum voix a))

(> v (aref minimum voix a))

(setf (aref memoire voix a) (list (list motif-courant v)))))

((< a fenetre)

; (print 'a<fen)

(if (assoc motif-courant (aref memoire voix (1- a)))

(and (= v (cadr (assoc motif-courant (aref memoire voix (1- a)))))

(true (setf (aref memoire voix a) (aref memoire voix (1- a)))))

; (true (printn motif-courant motif-restant )))

(let* ((place (donne-place (aref memoire voix (1- a)) motif-courant)))

; (affiche 'place place)

(cond ((= place 0)

(setf (aref maximum voix a) (- (cadr (nth place (aref memoire voix (1- a))))

(length (subseq motif-restant

(dp< motif-restant motif-courant)

(dp<= motif-restant (car (nth place (aref memoire voix (1- a)))))))))

(setf (aref minimum voix a) (1- (+ (car ambitus) tampon-inf))))

((= place (length (aref memoire voix (1- a))))

(setf (aref maximum voix a) (1+ (- (cadr ambitus) tampon-sup)))

(setf (aref minimum voix a) (+ (cadr (nth (1- place) (aref memoire voix (1- a))))

(length (subseq motif-restant

(dp< motif-restant (car (nth (1- place) (aref memoire voix (1- a)))))

(dp<= motif-restant motif-courant))))))

(t

(setf (aref maximum voix a) (- (cadr (nth place (aref memoire voix (1- a))))

(length (subseq motif-restant

(dp< motif-restant motif-courant)

(dp<= motif-restant (car (nth place (aref memoire voix (1- a)))))))))

(setf (aref minimum voix a) (+ (cadr (nth (1- place) (aref memoire voix (1- a))))

(length (subseq motif-restant

(dp< motif-restant (car (nth (1- place) (aref memoire voix (1- a)))))

(dp<= motif-restant motif-courant)))))))

; (affiche 'memoire (aref memoire voix (1- a)))

; (printc 'maxetmin (aref maximum voix a) (aref minimum voix a))

(and (< v (aref maximum voix a))

(> v (aref minimum voix a))

(setf (aref memoire voix a) (insere (aref memoire voix (1- a))

(list motif-courant v)

place))))))

(t

(if (assoc motif-courant (aref memoire voix (1- a)))

(and (= v (cadr (assoc motif-courant (aref memoire voix (1- a)))))

(setf (aref memoire voix a) (aref memoire voix (1- a))))

(let* ((place (donne-place (aref memoire voix (1- a)) motif-courant)))

(cond ((= place 0)

(setf (aref maximum voix a) (- (cadr (nth place (aref memoire voix (1- a))))

(length (subseq motif-restant

(dp< motif-restant motif-courant)

(dp<= motif-restant (car (nth place (aref memoire voix (1- a)))))))))

(setf (aref minimum voix a) (+ (car ambitus) tampon-inf)))

((= place (length (aref memoire voix (1- a))))

(setf (aref maximum voix a) (- (cadr ambitus) tampon-sup))

(setf (aref minimum voix a) (+ (cadr (nth (1- place) (aref memoire voix (1- a))))

(length (subseq motif-restant

(dp< motif-restant (car (nth (1- place) (aref memoire voix (1- a)))))

(dp<= motif-restant motif-courant))))))

(t

(setf (aref maximum voix a) (- (cadr (nth place (aref memoire voix (1- a))))

(length (subseq motif-restant

(dp< motif-restant motif-courant)

(dp<= motif-restant (car (nth place (aref memoire voix (1- a)))))))))

(setf (aref minimum voix a) (+ (cadr (nth (1- place) (aref memoire voix (1- a))))

(length (subseq motif-restant

(dp< motif-restant (car (nth (1- place) (aref memoire voix (1- a)))))

(dp<= motif-restant motif-courant)))))))

(and (< v (aref maximum voix a))

(> v (aref minimum voix a))

(setf (aref memoire voix a) (insere (aref memoire voix (1- a))

(list motif-courant v)

place))

(true (unless (member (nth (- a fenetre) motif) (subseq motif (- (1+ a) fenetre) (1+ a)))

(setf (aref memoire voix a)

(remove (assoc (nth (- a fenetre) motif) (aref memoire voix a))

(aref memoire voix a)))))

t)))))))

Montrons un exemple d'utilisation de la contrainte " motif " :

Dans ce patch, une contrainte motif est appliquée au soprane et une autre sur la basse.

La recherche de solution donne, au bout d'un temps raisonnable (quelques secondes) :

Dans cette configuration, longueur de la fenêtre étant nettement plus longue que le motif imposé, tout le début du motif reste imposé jusqu'à la fin. Une fois la première dent de scie construite, le moteur n'a plus aucun mal à trouver la suite.

Si la longueur de la fenêtre est réduit à 1, alors cela donne :

Cette fois-ci la recherche est plus longue, mais toujours effectuée dans des temps raisonnable car chaque dent de scie doit être recalculée puisque la mémoire des dents de scie précédentes sont effacées volontairement.

On peut à ces contraintes " motifs " rajouter d'autres contraintes vue précédemment. Cela accélérera la recherche car plus il y a de contraintes et plus le domaine est réduit, et par conséquent vite parcouru. Le cas où il y a deux contraintes motifs seulement est un cas parmi les plus défavorables au moteur, et l'on a vu qu'il s'en sortait bien.

9. Conclusion

L'utilisation de la programmation par contraintes à travers Situation dans le cadre de l'harmonie tonale paraît donner des résultats prometteur au vu du bon fonctionnement des modèles simplistes implémentés. On insiste sur le fait que l'harmonie tonale paraît comme l'un des meilleurs exemples de test d'épreuve du moteur de recherche de Situation. En effet, l'harmonie tonale est d'abord un exemple difficile à mettre en oeuvre, car elle met en valeur des problèmes mathématiques difficiles. Ensuite, elle est reconnue par l'ensemble de la communauté musicale. Enfin, si l'on arrive à montrer que Situation peut créer de bonnes séquences en musique tonale, alors on doutera moins de sa fiabilité vis à vis d'autres systèmes musicaux.

On insiste sur le fait que les améliorations que l'on envisage dans le cas de Situation ne visent en aucun cas à le spécialiser dans la musique tonale, mais à le rendre plus fiable dans la recherche de solutions face à des problèmes mathématiques complexes. Les essais sur la musique tonale ont donnés les idées d'améliorations, ou de compromis dont quelques uns sont donnés ici à titre d'exemple.

- Le système de notation du domaine étant très important pour une expression simple des contraintes et donc, une recherche efficace, Situation devrait permettre facilement au programmeur d'accepter toute les notations. En programmation par contrainte, la notation du domaine apporte déjà une information sur les propriétés. Dans le cadre de l'harmonie à 4 voix, le domaine apportait au système une connaissance de la structure des accords.

- L'ordonnancement dynamique devrait permettre de trouver plus rapidement une solution, même si le domaine est parcouru moins vite. Il faudrait donc inclure au moteur cette possibilité.

- Il faudrait que Situation permette facilement à l'utilisateur d'exprimer dans quel ordre il veut faire l'instanciation des accords lors du Backtracking, car une recherche rapide impose souvent d'instancier d'abord les variables qui ont un domaine très affectés par les contraintes. On sait que les harmonistes à vues prévoient toujours un peu en avance les cadences sur lesquelles ils vont aboutir lors de l'harmonisation de chorals.

Avant de modifier le moteur, les questions suivantes sont important à traiter :

- la modification ne va-t-elle pas engendrer une restructuration profonde du moteur ?

- la modification est elle vraiment une amélioration pour la majorité des contraintes rencontrées par le moteur de recherche ?

- la modification est elle bonne sur des points tels que l'efficacité et la modularité ?

Une autre idée, qui commence à être employée en intelligence artificielle consiste à construire les solutions étapes par étapes. On emploie non pas le moteur pour trouver d'un seul coup tout une séquence musicale (c'est une illusion de penser qu'un moteur de recherche va trouver en moins de deux secondes une séquence musicale telle qu'une fugue dans le style de BACH), mais pour trouver des séquences musicales partielles. C'est d'ailleurs ce que font les musiciens en écrivant une fugue : décomposer les étapes. On commence par trouver un contre-sujet, puis une réponse, une contre-réponse. On construit ensuite l'entrée de la fugue. On trouve après les marches d'harmonie qui s'inspirent le mieux du sujet. et ainsi de suite. On peut envisager ce style d'écriture par programmation par contraintes mais en divisant les étapes. Pour construire des séquences musicales, certains emploient des réseaux de neurones [Lan 98], mais toujours en divisant le travail. L'harmonie se construit successivement par des petits réseaux plus facilement contrôlables que un immense réseau qui ferait tout le travail. En fait, on arrive à l'idée qui consiste à mélanger la programmation fonctionnelle et la programmation par contrainte ou la programmation par réseaux de neurones.

En outre, on a vu au cours des exemples quatre sortes de contraintes différentes. Un des gros avantages de la programmation par contraintes est qu'elle permet de bien séparer l'information, et de pouvoir l'additionner exactement comme on le souhaite.

Mais le gros avantage de la programmation par contrainte est d'avoir la possibilité d'implémenter à la machine des instructions très semblables à celles que notre cerveau fait, consciemment ou pas, lorsque l'on essaie de faire de l'harmonie. C'est à dire de tâtonner, d'essayer et de changer quand cela ne va pas. Ce n'est surtout pas d'essayer de trouver un formalisme mathématiques résultant de propriétés, qui ici, sont quasiment inexistantes.

Je tiens vivement à remercier tout ceux qui m'ont aidé dans cette réalisation, spécialement Gérard ASSAYAG, mon maître de stage, Carlos AGON, qui ont été tout les deux toujours disponibles pour m'aider et surtout Camilo RUEDA pour ses explications concernant le moteur de Situation.

10. table des matières

11. Bibliographie

[Irc 98] Rapport Scientifique à quatre ans, Unité mixte de recherche Ircam-CNRS, Juin 1998.

[Gas 97] Gérard Assayag, Carlos Agon, Joshua Fineberg, Peter Hanappe. An Object Oriented Visual Environment For Musical Composition, Proceedings of the ICMC 97, Thessaloniki, 1997.

[Gas 93] Gérard Assayag, Camilo Rueda. Représentations musicales IRCAM. Revue Intermedia. Septembre 1993. Barcelone.

[Gas 96] Gérard Assayag,Carlos Agon. OpenMusic Architecture. Proceedings of the ICMC 96, Hong Kong, 1996.

[Sar 95] Vijay Saraswat. LFG qua concurrent constraint programming, 1995.

[Fro 94] Annick Fron. Programmation par contraintes, Addison-Wesley, Avril 1994.

[Sja 93] Emmanuel Saint-James. La programmation applicative, Hermes, 1993.

[Bal 98] Philippe Ballesta. Contraintes et Objets, clefs de voûte d'un outils d'aide à la composition ? Recherche et applications en informatique musicale, Paris 1998.

[Ebc 88] Kamel Ebcioglu. An expert System for Harmonizing Four-part Chorales, Computer Music Journal, vol 12 Ndeg.3, pp 43-51, Automne 1988.

[Rue 98] Camilo Rueda, Antoine Bonnet. Situation : Un Langage Visuel Basé sur les Contraintes pour la Composition Musicale, 1998.

[Lan 98] Joachim Langnickel, Werner Zorn. A System for the Automatic Harmonization of Chorales, 1998.

[Rue1 98]Camilo Rueda. Constraint Systems for Musical Applications, IRCAM, Technical Report, Juin 1998.

[Ste 90] Guy Steele. Common Lisp, the language. Second edition, Digital Press, 1990.

[Hab 96] Benoît Habert. Objectif : CLOS, Masson, Paris, 1996.

[Sla 97] Stephen Slade. Object-Oriented Common Lisp, Prentice Hall, 1997.

[Cop 91] David Cope. Computer and Musical Style, 1991.

[Ste 90] Jacques Stern. Fondements Mathématiques de l'informatique.

Mc Graw-Hill, 1990.

[RuVa97] Camilo Rueda, Frank Valencia. Improving forward checking

with delayed evaluation. In proceedings of CLEI'97, Santiago, Chile, 1997.

[Bar 68] Barbaud. La musique discipline scientifique, Dunod, Paris, 1968