Transformations d'expressions booléennes simples

Nous voudrions écrire la fonction ebs-simplifiee qui évalue partiellement une expression booléenne simple en éliminant, au maximum, les constantes booléennes.

Spécification
Ainsi cette fonction a comme donnée une expression booléenne simple (avec variables) et comme résultat une autre expression, simplifiée de l'expression donnée:

;;; ebs-simplifiee : ExprBoolSimple -> ExprBoolSimple ;;; ERREUR lorsque exp n'est pas une expression bien formée ;;; (ebs-simplifiee expr) rend une expression booléenne simple simplifiée ;;; équivalente à l'expression booléenne simple donnée.

Exemple :

(ebs-simplifiee '((@non a) @et (b @ou (@v @et a))))
-> ((@non a) @et (b @ou a))

(ebs-simplifiee '((@non @f) @et (b @ou (@v @et a))))
-> (b @ou a)

(ebs-simplifiee '((@non @f) @et (b @ou (@v @ou a))))
-> @v

Règles de simplification:

Encore faut-il préciser ce que nous entendons par « simplifiée ». Nous utiliserons les simplifications suivantes:

`a (@ou @v)`	devient	`@v`	`(a @et @v)`	devient	`a`	`(non @v)`	devient	`@f`
`(a @ou @f)`	devient	`a`	`(a @et @f)`	devient	`@f`	`(non @f)`	devient	`@v`
`(@v @ou a)`	devient	`@v`	`(@v @et a)`	devient	`a`
`(@f @ou a)`	devient	`a`	`(@f @et a)`	devient	`@f`

Remarques:

il s'agit bien d'une évaluation partielle, d'autant plus que les sous-expressions qui n'ont pas d'occurrences de variables sont évaluées;
nous pourrions donner d'autres règles de simplification (par exemple (@non (@non a)) devient a). Vous pouvez essayer d'implanter cette dernière règle de simplification -- et, éventuellement, d'autres. Nous nous en tiendrons là.

Implantation
Encore le même schéma:

(define (ebs-simplifiee exp) (cond ((ebs-atomique? exp) ((ebs-unaire? exp) ((ebs-binaire? exp) (else (erreur 'ebs-simplifiee "expression mal formée"))))

une formule atomique est simplifiée ; on la retourne donc telle quelle:

(define (ebs-simplifiee exp) (cond ((ebs-atomique? exp) exp) ((ebs-unaire? exp) ((ebs-binaire? exp) (else (erreur 'ebs-simplifiee "expression mal formée"))))

Pour les expressions unaires et binaires, cela semble plus compliqué: nous utilisons des fonctions ebs-unaire-simplifiee et ebs-binaire-simplifiee qui simplifient des expressions unaires et binaires, mais données par leurs décompositions:

(define (ebs-simplifiee exp) (cond ((ebs-atomique? exp) exp) ((ebs-unaire? exp) (ebs-unaire-simplifiee (ebs-unaire-operateur exp) (ebs-unaire-operande exp))) ((ebs-binaire? exp) (ebs-binaire-simplifiee (ebs-binaire-operateur exp) (ebs-binaire-operande-gauche exp) (ebs-binaire-operande-droit exp))) (else (erreur 'ebs-simplifiee "expression mal formée"))))

avec ces fonctions spécifiées par:

;;; ebs-unaire-simplifiee : Operateur1 * ExprBoolSimple -> ExprBoolSimple ;;; (ebs-unaire-simplifiee op exp) rend une expression booléenne simple ;;; simplifiée équivalente à l'expression booléenne (ebs-unaire op exp). ;;; ebs-binaire-simplifiee : Operateur2 * ExprBoolSimple * ExprBoolSimple -> ExprBoolSimple ;;; (ebs-binaire-simplifiee op expG expD) rend une expression booléenne ;;; simple simplifiée équivalente à l'expression booléenne ;;; (ebs-binaire expG op expD).

Implantation de ebs-unaire-simplifiee
Pour la simplification d'une expression unaire, on vérifie que l'opérateur est bien @non et, si c'est bien le cas, on fait appel à la fonction de simplification dédiée à la négation. En remarquant que la simplification d'une négation doit être calculée à partir de la simplification de sa sous-expression:

;;; ebs-unaire-simplifiee : Operateur1 * ExprBoolSimple -> ExprBoolSimple ;;; (ebs-unaire-simplifiee op exp) rend une expression booléenne simple ;;; simplifiée équivalente à l'expression booléenne (ebs-unaire op exp). (define (ebs-unaire-simplifiee op exp) (if (ebs-operateur1-non? op) (ebs-neg-simplifiee (ebs-simplifiee exp)) (erreur 'ebs-simplifiee op "n'est pas un opérateur unaire")))

en utilisant une fonction, ebs-neg-simplifiee qui doit avoir comme spécification:

;;; ebs-neg-simplifiee : ExprBoolSimple/simplifiee/ -> ExprBoolSimple/simplifiee/ ;;; (ebs-neg-simplifiee exp) rend une expession booléenne simple simplifiée ;;; équivalente à (non exp)

Implantation de ebs-binaire-simplifiee
De même, pour simplifier une expression binaire, on fait appel à une fonction de simplification dédiée à l'opérateur de l'expression:

(define (ebs-binaire-simplifiee op expG expD) (cond ((ebs-operateur2-et? op) (ebs-conj-simplifiee (ebs-simplifiee expG) (ebs-simplifiee expD))) ((ebs-operateur2-ou? op) (ebs-disj-simplifiee (ebs-simplifiee expG) (ebs-simplifiee expD))) (else (erreur 'ebs-simplifiee op "n'est pas un opérateur binaire"))))

ces fonctions ayant comme spécification:

;;; ebs-conj-simplifiee : ExprBoolSimple/simplifiee/ * ExprBoolSimple/simplifiee/ ;;; -> ExprBoolSimple/simplifiee/ ;;; (ebs-conj-simplifiee e1 e2) rend une expession booléenne simple simplifiée ;;; équivalente à (e1 et e2) ;;; ebs-disj-simplifiee : ExprBoolSimple/simplifiee/ * ExprBoolSimple/simplifiee/ ;;; -> ExprBoolSimple/simplifiee/ ;;; (ebs-disj-simplifiee e1 e2) rend une expession booléenne simple simplifiée ;;; équivalente à (e1 ou e2)

Implantation de ebs-neg-simplifiee
Règles de simplification (rappel):

Rappelons les règles de simplification pour la négation:

`(@non @v)`	devient	`@f`
`(@non @f)`	devient	`@v`

ce à quoi on pourrait ajouter, pour tenir compte des cas où il n'y a pas de simplification:

(@non a) devient (@non a)

Rappelons la spécification de la fonction ebs-neg-simplifiee:

;;; ebs-neg-simplifiee : ExprBoolSimple/simplifiee/ -> ExprBoolSimple/simplifiee/ ;;; (ebs-neg-simplifiee exp) rend une expession booléenne simple simplifiée ;;; équivalente à (non exp)

et notons que la donnée de cette fonction est une expression simplifiée et que c'est la sous-expression de la négation (c'est le a de la règle ci-dessus). L'implantation est alors facile (noter tout de même l'utilisation de la barrière syntaxique):

(define (ebs-neg-simplifiee exp) (cond ((ebs-constante-vrai? exp) (ebs-constante-faux)) ((ebs-constante-faux? exp) (ebs-constante-vrai)) (else (ebs-unaire (ebs-operateur1-non) exp))))

Implantation de ebs-conj-simplifiee
Règles de simplification (rappel):

Rappelons les règles de simplification pour la conjonction:

`(@f @et a)`	devient	`@f`	`(a @et @f)`	devient	`@f`
`(@v @et a)`	devient	`a`	`(a @et @v)`	devient	`a`

en se rappelant que la donnée de la fonction ebs-conj-simplifiee est constituée par les deux sous-expressions simplifiée d'une conjonction, l'implantation de cette fonction est:

;;; ebs-conj-simplifiee : ExprBoolSimple/simplifiee/ * ExprBoolSimple/simplifiee/ ;;; -> ExprBoolSimple/simplifiee/ ;;; (ebs-conj-simplifiee e1 e2) rend une expession booléenne simple simplifiée ;;; équivalente à (e1 et e2) (define (ebs-conj-simplifiee e1 e2) (cond ((ebs-constante-faux? e1) (ebs-constante-faux)) ((ebs-constante-faux? e2) (ebs-constante-faux)) ((ebs-constante-vrai? e1) e2) ((ebs-constante-vrai? e2) e1) (else (ebs-binaire e1 (ebs-operateur2-et) e2))))

Idem pour ebs-disj-simplifiee qui est laissée en exercice.