Sommaire

Révision pour l’examen final

Voici une liste des notions qu’il est nécessaire de connaître en prévision de l’examen final du 27 avril.

Chapitres 1 à 6 : Programmation fonctionnelle et OCaml

L’examen portera surtout sur les notions vues après l’examen de mi-session (chapitres 7, 8 et 11), mais il sera quand même nécessaire de savoir lire et écrire du code OCaml. Une révision des chapitres 1 à 6 est recommandée.

Chapitre 7 : Programmation logique

1. Rappel mathématique: relations

Il est nécessaire de comprendre ce qu’est une relation et la différence avec une fonction.

Il faut comprendre comment Prolog utilise des relations, contrairement à OCaml qui utilise des fonctions.

2. Syntaxe de Prolog

2.1 littéraux

Nombres : entiers (ex. 123) et flottants (ex. 3.1416)

Atomes : Commencent par une minuscule ou entourés de guillemets simples.

Exemples: bonjour

'bonjour' (cet atome est la même chose que bonjour)

'bonjour tout le monde' (dans ce cas, les guillemets (') sont nécessaires pour inclure tous les mots dans un seul atome.)

Chaînes de caractères : "Bonjour tout le monde"

2.2 Variables logiques

Variables nommées : Commencent par une majuscule ou une barre de soulignement _.

Exemples:

X

_x

Foo

_Foo

Variables anonymes : on met une barre de soulignement _ au lieu d’un nom de variable lorsque la valeur d’une variable n’a pas d’importance dans la requête.

2.3 Structures

Exemples de structures:

aime(chat, croquettes)
addresse(numero(12), rue('Baker Street'), ville('Londres'))

2.4 Termes

Un terme est soit un littéral, une variable ou une structure.

2.5 Clauses

  • composées de termes
  • liées avec:

:- qui signifie “si”

, qui signifie “et”

; qui signifie “ou”

  • se terminent par un . (n’oubliez pas le . dans vos réponses à l’examen)
  • deux sortes de clauses:
  • un fait est une proposition qui est vraie sans condition.

Exemples:

length([1,2,3], 3).
length([], 0)
voyelle(a).
consonne(p).
  • une règle est une proposition qui est vraie sous certaines conditions.

Exemples:

sqrt(X, Y) :- X is Y * Y.
length([H|T], L) :- length(T, X), L is X + 1.
voyelle(X) :- X = a; X = e; X = i; X = o; X = u; X = y.

2.6 Relations

Une relation (ou prédicat) est définie par une suite de clauses

Pour l’examen final, on s’attend à ce que vous puissiez définir des relations en Prolog

Exemple de relation: fac/2 (à lire “relation binaire (d’arité 2) nommée fac”)

% Cas de base (c'est un fait)
fac(0, 1).

% Cas récursif (c'est une règle)
fac(N, M) :-
      N >= 1,
      N1 is N - 1,
      fac(N1, M1),
      M is N * M1.

2.7 Programmes

Un programme Prolog est simplement une suite de relations.

3. Requêtes

Une requête peut être effectuée dans SWIPL de la façon suivante:

?- fac(5, M).

(ne pas oublier le . à la fin de la requête)

Cette requête demande à Prolog de trouver toutes les valeurs de M qui rendent fac(5, M) vraie (toutes les valeurs de M telles que M est le factoriel de 5).

4. Unification

L’unification, c’est le fait de rendre deux expressions identiques en trouvant des valeurs pour leurs variables.

Autrement dit : on cherche une substitution des variables qui fait que les deux termes deviennent exactement les mêmes.

Par exemple:

• Unifier f(X, a) avec f(b, Y) donne

X = b et Y = a

Si c’est possible → succès Sinon → échec

On peut faire une requête d’unification dans SWIPL:

?- parent(X, f(Y), Y) = parent(g(Z), f(a), Z).

En analysant terme par terme, on trouve que ces deux expressions “unifient” si ces conditions sont respectées:

X = g(Z)
f(Y) = f(a)
Y = Z

On peut déduire de ces conditions que

Y = a donc Z = a donc X = g(a)

5. Résolution de requête

Par exemple, soit le programme suivant:

precede(a, b).  % la lettre `a` précède immédiatement `b`.
precede(b, c).
precede(c, d).

% pour déterminer si une lettre vient `avant` une autre dans l'ordre alphabétique:
avant(X, Z) :- precede(X, Z).
avant(I, K) :- precede(I, J), avant(J, K).

On veur résoudre la requête suivante pour connaître les lettres qui sont après b: ?- avant(b, L).

Prolog tentera alors d’unifier avant(b, L) avec toutes les définitions de avant, dans l’ordre de définition:

  1. avant(b, L) = avant(X, Z) si X=b et L=Z

On doit alors vérifier la requête ?- precede(b, L).

On tente alors d’unifier precede(b, L) avec les définitions de precede.

1.1. precede(b, L) = precede(a, b) est FAUX, car a est différent de b.

1.2. precede(b, L) = precede(b, c) est VRAI si L=c (on vient de trouver une première solution).

1.3. precede(b, L) = precede(c, d) est FAUX, car c est différent de b.

  1. avant(b, L) = avant(I, K) si I=b et L=K

On doit alors vérifier la requête ?- precede(b, J), precede(J, L). (Il s’agit d’une conjonction de deux requêtes. On les vérifie une à la fois:

2.1. precede(b, J) = precede(a, b) est FAUX, car a est différent de b.

2.2. precede(b, J) = precede(b, c) est VRAI si J=c.

Il reste à vérifier la 2e requête avec J=c:

2.2.1. precede(c, L) = precede(a, b) est FAUX, car a est différent de c.

2.2.2. precede(c, L) = precede(b, c) est FAUX, car b est différent de c.

2.2.3. precede(b, L) = precede(c, d) est VRAI si L=d (on vient de trouver une deuxième solution).

2.3. precede(b, L) = precede(c, d) est FAUX, car c est différent de b.

Une fois qu’on a tout vérifié, on trouve que les valeurs de L qui rendent avant(b, L) vraie sont:

L=c et L=d.

5.1 Arbres de résolution

En observant bien la résolution de la requête ?- avant(b, L), on constate qu’il est possible de construire un arbre de résolution. La solution de cet arbre sera donnée à la séance de révision du 20 avril.

Pour l’examen final, il faudra être en mesure de résoudre une requête comme celle-ci et de tracer l’arbre de résolution.

L’algorithme de construction d’un arbre de résolution se trouve à la page 42 du Chapitre 7.

6. Les listes

Une liste est soit une liste vide [], soit une liste qui contient au moins un élément:

[H|T]      où X est le premier élément de la liste et T est le reste de la liste.

Par exemple, si [H|T] = [1,2,3,4], on a alors que H=1 et T=[2,3,4].

Le constructeur | est l’équivalent du :: en OCaml.

7. Conversion de fonctions OCaml en relations Prolog

Pour l’examen final, si on vous donne une fonction OCaml, il est attendu que vous puissiez convertir celle-ci en relation Prolog.

Une fonction OCaml à n variables et retournant 1 valeur devra être transformée en une relation d’arité n+1, telle que le dernier argument correspond au retour de la fonction. Par exemple:

La fonction à une variable suivante:

let f (x : int) : int = x + 1

devra être transformée en une relation f/2:

f(X, Y) :- Y is X + 1.

L’application de fonction f 3 en OCaml sera alors remplacée par la requête ?- f(3, Y) et prolog se chargera de retourner toutes les valeurs possibles de Y.

Il est également possible qu’on vous demande de convertir une relation Prolog en une fonction OCaml.

8. Correction et complétude

Il est nécessaire de connaître la définition ce correction (soundness) et complétude (completeness), telles que définies vers la fin du Chapitre 7. Il faudrait également savoir où se situe Prolog.

Chapitre 8 : Interprétation d’un langage fonctionnel

8.1. Arbre syntaxique abstrait (AST: Abstract Syntax Tree)

Vous devez connaître la définition d’un arbre syntaxique abstrait et être capable de convertir une expression arithmétique sous forme d’AST. Par exemple:

(1 + (2 * 3)) + 4

            (+)
           /   \
        (+)     (4)
       /   \
    (1)     (*)
           /   \
        (2)     (3)

Type algébrique représentant la syntaxe d’un langage fonctionnel:

Les expressions possibles sont décrites par le type suivant:

type expr =
  | Int of int
  | Bool of bool
  | Plus of expr * expr
  | Times of expr * expr
  | Minus of expr * expr
  | Divide of expr * expr
  | IsZero of expr
  | If of expr * expr * expr
  | Var of string
  | Let of string * expr * expr
  | Function of string * expr 
  | Call of expr * expr

Cette définition du type expr vous sera fournie lors de l’examen.

À l’aide de ce type, l’expression arithmétique précédente devient:

Plus (Plus (Int 1, Times (Int 2, Int 3)), Int 4)

             Plus
            /    \
        Plus      Int 4
       /   \
  Int 1     Times
           /     \
      Int 2       Int 3

Autres exemples: L’expression

function x -> x + 1

devient

Function ("x", Plus (Var "x", Int 1))

                 Function
                /        \
             "x"          Plus
                         /    \
                  Var "x"      Int 1

L’expression

let x = 4 in x + 3

devient:

Let ("x", Int 4, Plus (Var "x", Int 3))

                   Let
           ________/|\________
          /         |         \ 
       "x"        Int 4        Plus
                              /    \
                       Var "x"      Int 3

Valeurs de retour et environnement

Dans notre langage d’évaluation d’expressions mathématiques, lors d’une évaluation, la valeur de retour aura le type suivant, défini conjointement avec le type env:

type value =
  | VInt of int
  | VBool of bool
  | VClosure of string * expr * env
and env = (string * value) list

Les définitions des types value et env vous seront fournies lors de l’examen

Le type value représente les valeurs possibles pour une expression qu’on évalue. VInt et VBool sont pour les entiers et les booléens. VClosure représente la valeur d’une fonction. Par exemple:

VClosure ("x", Plus (Var "x", Var "y"), [("y", VInt 3)])

Ceci représente la “valeur” d’une fonction à une seule variable x qui additionne x à la valeur de y. la variable y n’est pas un paramètre de la fonction; c’est une variable qui a été définie avant la définition de la fonction et qui fait partie de son environnement de définition, représenté ici par la liste associative [("y", VInt 3)]. La fonction sait alors que y vaut 3 lors du calcul x+y.

On fournira également la définition des deux fonctions suivantes:

(* Fonction qui permet d'extraire la valeur d'une variable 
   dans un environnement: *)
let lookup (env : env) (var : string) : value = List.assoc var env

(* Fonction qui permet d'ajouter une assignation de variable dans un environnement: *)
let extend (env : env) (var : string) (value : value) : env = 
    (var, value) :: env

Ces deux fonctions seront également fournies à l’examen.

Évaluation d’expressions

L’évaluation des expressions se fera avec l’interpréteur suivant, qui vous sera également fourni à l’examen:

let rec eval (env : env) (e : expr) : value =
  match e with
  | Int n -> VInt n
  | Bool b -> VBool b
  | Plus (e1, e2) ->
    begin match eval env e1, eval env e2 with
      | VInt x, VInt y -> VInt (x + y)
      | _ -> raise TypeError
    end
  | Times (e1, e2) ->
    begin match eval env e1, eval env e2 with
      | VInt x, VInt y -> VInt (x * y)
      | _ -> raise TypeError
    end
  | Minus (e1, e2) ->
    begin match eval env e1, eval env e2 with
      | VInt x, VInt y -> VInt (x - y)
      | _ -> raise TypeError
    end
  | Divide (e1, e2) ->
    begin match eval env e1, eval env e2 with
      | VInt x, VInt y -> VInt (x / y)
      | _ -> raise TypeError
    end
  | IsZero e1 ->
    begin match eval env e1 with
      | VInt 0 -> VBool true
      | VInt _ -> VBool false
      | _ -> raise TypeError
    end
  | If (condition, consequent, alternative) ->
    begin match eval env condition with
    | VBool true -> eval env consequent
    | VBool false -> eval env alternative
    | _ -> raise TypeError
    end
  | Var v -> lookup env v
  | Let (x, e1, e2) ->
    let v = eval env e1 in
    eval (extend env x v) e2
  | Function (param, body) ->
    VClosure (param, body, env)
  | Call (f, arg) ->
    begin match eval env f with
      | VClosure (param, body, def_env) ->
        let arg_value = eval env arg in
        let new_env = extend def_env param arg_value in
        eval new_env body
      | _ -> raise TypeError
    end

À l’aide de cette fonction d’évaluation, vous devez être en mesure d’évaluer des expressions et d’écrire la trace d’exécution des appels à la fonction eval en indiquant clairement les arguments de la fonction et les valeurs de retour. Par exemple:

let e = Times (Plus (Int 1, Int 2), Plus (Int 3, Int 4)) in

eval [] e

cette évaluation devrait retourner la valeur VInt 21, et la trace de son exécution est la suivante:

# eval [] (Times((Plus((Int 1), (Int 2))), (Plus((Int 3), (Int 4)))))
    # eval [] (Plus((Int 1), (Int 2)))
        # eval [] (Int 1)
        -> renvoie : VInt 1
        # eval [] (Int 2)
        -> renvoie : VInt 2
    -> renvoie : VInt 3
    # eval [] (Plus((Int 3), (Int 4)))
        # eval [] (Int 3)
        -> renvoie : VInt 3
        # eval [] (Int 4)
        -> renvoie : VInt 4
    -> renvoie : VInt 7
-> renvoie : VInt 21

Un autre exemple:

let e = Let ("x", Int 1, Let ("y", Plus (Var "x", Int 2), Plus (Var "y", Int 3))) in

eval [] e

La trace d’exécution est donc la suivante:

# eval [] (Let ("x", Int 1, Let ("y", Plus (Var "x", Int 2), Plus (Var "y", Int 3))))
    # eval [] (Int 1)
    -> renvoie : VInt 1
    # extend [] "x" = VInt 1
    # eval [x=VInt 1] (Let "y" = (Plus((Var "x"), (Int 2))) in (Plus((Var "y"), (Int 3))))
        # eval [x=VInt 1] (Plus((Var "x"), (Int 2)))
            # eval [x=VInt 1] (Var "x")
                # lookup [x=VInt 1] "x"
            -> renvoie : VInt 1
            # eval [x=VInt 1] (Int 2)
            -> renvoie : VInt 2
        -> renvoie : VInt 3
        # extend [x=VInt 1] "y" = VInt 3
        # eval [y=VInt 3, x=VInt 1] (Plus((Var "y"), (Int 3)))
            # eval [y=VInt 3, x=VInt 1] (Var "y")
                # lookup [y=VInt 3, x=VInt 1] "y"
            -> renvoie : VInt 3
            # eval [y=VInt 3, x=VInt 1] (Int 3)
            -> renvoie : VInt 3
        -> renvoie : VInt 6
    -> renvoie : VInt 6
-> renvoie : VInt 6

Remarquez que l’indentation de la trace d’exécution donne un bon indice quant à la forme de l’arbre syntaxique de l’expression à évaluer.

Vous pouvez expérimenter avec l’interpréteur dans la solution du laboratoire 10.

Notez que les notes de cours incluent aussi les fonctions récursives et les types algébriques dans la définition de l’interpréteur. Ceux-ci ne seront pas sujet à l’examen.

Chapitre 11 : programmation par contraintes

Le chapitre 11 était surtout nécessaire pour la résolution du TP2.

Voici une liste de sujets que je m’attends à ce que vous connaissiez:

  1. Qu’est-ce qu’un problème de satisfaisabilité
  2. Le solveur CLP(B)
:- use_module(library(clpb)).

Constraint Logic Programming over Boolean variables

Expressions:

0 : faux

1 : vrai

X : vraiable représentant une valeur inconnue

~X : négation de X (non X)

E1 + E2 : disjonction (ou)

E1 * E2 : conjonction (et)

E1 # E2 : ou exclusif

X ^ E : Il existe un X tel que E

E1 =:= E2 : égalité (E1 si et seulement si E2)

E1 =\= E2 : différence (E1 est différent de E2)

E1 =< E2 : implication (E1 implique E2)

En d’autres mots, si E1 est vrai (=1), alors E2 est vrai aussi (=1), d’où l’utilisation du symbol plus petit ou égal.

Pour résoudre des contraintes à l’aide de CLP(B), on utilise sat:

sat(A =:= B # C).

Ceci permet de connaître les valeurs de A, B et C telles que:

A est vrai si et seulement si (B et C sont différents)

  1. Le solveur CLP(FD)
:- use_module(library(clpfd)).

Il s’agit d’une version généralisée de CLP(B) qui ne se limite pas seulement à des valeurs booléennes, mais à tous les entiers. On peut émettre des contraintes sur des valeurs entières.

contraintes arithmétiques possibles:

E1 #= E2 : E1 est égal à E2

E1 #\= E2 : E1 est différent de E2

E1 #>= E2 : E1 est plus grand ou égal à E2

E1 #=< E2 : E1 est plus petit ou égal à E2

E1 #> E2 : E1 est plus grand que E2

E1 #< E2 : E1 est plus petit que E2

  1. Différence entre #= de CLP(FD) et le mot-clé is dans Prolog

Lorsqu’on effectue la requête

?- 3 #= Y+2.

le solveur CLP(FD) voit ceci comme une contrainte et sera capable de trouver que Y doit prendre la valeur 1 pour rendre cette requête vraie. Au contraire la requête suivante échoue:

?- 3 is Y+2.

Sans le sloveur CLP(FD), Prolog n’est pas suffisamment outillé pour résoudre cette requête. En utilisant le mot-clé is, Prolog s’attend à ce que ce qui se trouve à droite de is soit déjà connu. Or, dans cet exemple, Y n’a pas encore de valeur et ne peut donc pas être utilisé pour calculer Y+2, Y étant inconnu.