Projet de Programmation en Scheme
created 10 may 2000, last edition 11 may 2000

On se propose de réaliser en Scheme un compilateur d'expressions algébriques telles que:

(A + (B * C))
((A + (B - C))
X
(X + (Y * X))
((X / X) * (A / (B + B)))
...

produisant du langage machine.

Les expressions

Leur syntaxe est donnée par la grammaire:

expression ::= <identifier>
| ( left_operand operator right_operand )

operator ::= + | - | * | /

left_operand ::= expression

right_operand ::= expression

Le terminal <identifier> correspond à l'ensemble des symboles Scheme.

Un environnement est une liste d'association entre des symboles et des nombres. Exemples:

((A . 12) (B . 24) (C . 36) (R2001 . 367))
((A . 12) (B . 24) (A . 36))

Dans le second environnement, A apparaît deux fois: on ne tient compte que de la première occurrence, donc A vaut 12.

On implantera un évaluateur purement fonctionnel d'expressions:

eval-expression: expression, environment -> number

Fichier à compléter: expressions.scm.

Return to top of page.

Le langage machine

On dispose d'une machine à registres, appelés R0, R1, ..., dont les instructions sont décrites par la grammaire:

        instruction ::=   (ld <register> <identifier>)
                   | (operation target source)
      operation ::=   add | sub | mult | div
         target ::= <register>
         source ::= <register>

La sémantique d'une instruction dépend de son type:

l'instruction ld charge le registre avec le contenu de la mémoire spécifiée par l'identificateur;
les autres instructions effectue l'opération spécifiée entre les contenus des registres target et source et place le résultat dans le registre target.

Un programme machine est une liste d'instructions machine:

program ::= ()
| ( instruction . program )

On implantera un évaluateur purement fonctionnel de programmes machine:

eval-program: program, environment -> environment

Exemple:

guile> (eval-program '((ld R0 A)
                       (ld R1 B)
                       (add R0 R1)
                       (ld R1 C))
                     '((A . 12) (B . 24) (C . 36)))
       ((R1 . 36) (R0 . 36) (R1 . 24) (R0 . 12)
        (A . 12) (B . 24) (C . 36))

Fichier à compléter: machine.scm.

Return to top of page.

Le compilateur

Il s'appelle compile et admet un seul paramètre appelé expression: l'expression à compiler. Le résultat de la compilation est une liste d'instructions machine, dont l'évaluation par eval-program produirait un environnement où R0 contiendrait la valeur de l'expression dans l'environnement de départ. Par exemple:

guile> (compile '((A + B) * (C - D)))
((ld R0 A)        ; A
(ld R1 B)        ; B
(add R0 R1)      ; (A + B)
(ld R1 C)        ; C
(ld R2 D)        ; D
(sub R1 R2)      ; (C - D)
(mult R0 R1))    ; ((A + B) * (C - D))

Ce compilateur (purement fonctionnel) utilise une fonction auxiliaire:

(compile-reg expression n):
compile l'expression en n'utilisant que des registres de rang supérieur ou égal à n, et engendre un programme qui place le résultat dans le registre de rang n.

Fichier à compléter: compiler.scm.

Return to top of page.

Version impérative de l'évaluateur de programmes

On réalisera une version impérative de l'évaluateur de programmes machines appelée exec pour laquelle l'environnement sera implicitement représenté par l'environnement global de Scheme: ld, add, sub,
mult, div seront implantés comme des macros de Scheme, de même que "exec".

Exemple:

guile> (macroexpand '(exec ((A . 12) (B . 24) (C . 36))
                           (ld R0 A)
                           (ld R1 B)
                           (add R0 R1)
                           (ld R1 C)))
(begin (define A 12)
       (define B 24)
       (define C 36)
       (define R0 ())
       (define R1 ())
       (ld R0 A)
       (ld R1 B)
       (add R0 R1)
       (ld R1 C))

Fichier à compléter: exec.scm.

Return to top of page.

A rendre

On remettra un petit rapport de 4 à 5 pages sur le projet, de préférence au format html (nommé index.html), et des fichiers Scheme complétés, dont au moins:

test.scm qui charge tout et lance des tests,
expressions.scm,
machine.scm,
compiler.scm,
exec.scm,

à partir du répertoire

~gloess/scheme/project/

Chaque document rendu devra indiquer en tête les noms des auteurs.

Critères d'évaluation

On évaluera la qualité du logiciel et en particulier son adéquation avec la spécification, sa fiabilité, sa modularité, la clarté des fonctions et macros définies, et des commentaires les accompagnant, le choix des noms des divers paramètres, le bon usage du style fonctionnel de l'implantation. Le rapport ne devra pas répéter le sujet ou le logiciel, mais mettre l'accent sur la conception, les points délicats, les difficultés éventuelles.

Return to top of page.

Suivi du projet

On pourra s'adresser à l'enseignant-chercheur de son groupe de TDs pour tout tout problème relatif au projet:

Les réponses, incluant vos messages, seront susceptibles d'être diffusées à l'ensemble de la promotion.

Return to top of page.