Labos

1. Installation d’OCaml Installez OCaml sur votre ordinateur. Pour installer OCaml, il est recommandé d’installer opam le gestionnaire de paquet d’OCaml d’abord, qui vous permettra ensuite d’installer une version spécifique d’OCaml. 1.1 Installation d’OPAM Sur Linux Installez le paquet opam de votre distribution : apt-get install opam sur Ubuntu et Debian référez-vous à la documentation de votre distribution pour les autres Sur MacOS Installez le paquet opam avec Brew (brew install opam) ou MacPorts (port install opam), ou lancez la commande suivante :

Interprèteur minimal Soit l’interprèteur suivant, supportant les entiers, booléens, et fonctions, y compris les fonction récursives. type expr = | Int of int | Bool of bool | Plus of expr * expr | Minus of expr * expr | Times 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 | LetRec of string * string * expr * expr exception TypeError type value = | VInt of int | VBool of bool | VClosure of string option * string * expr * env and env = (string * value) list let lookup (env : env) (var : string) : value = List.

Résolution de programmes (Examen Été 2023) Soit le programme suivant : a(_). b(X, Y) :- a(X), c(X, Y). b(2, 5). c(X, Y) :- d(X), e(Y). d(1). d(2). e(3). e(4). Dans la suite de cette question, vous devrez dessiner des arbre de résolution. Pour cela, il est important : d’indiquer les buts à résoudre dans les nœuds de l’arbre d’indiquer les assignations aux variables logiques sur les arcs d’indiquer true comme feuille pour les requêtes qui réussissent, et false.

1. La fonction factorielle La factorielle \(n!\) d’un entier naturel \(n\) est le produit des nombres entiers strictement positifs inférieurs ou égaux à \(n\). Écrire la fonction fact à un paramètre entier n qui renvoie \(n!\). Le résultat attendu à l’utilisation est le suivant : # fact;; - : int -> int = <fun> # fact 0, fact 1, fact 2, fact 3, fact 4, fact 5;; - : int * int * int * int * int * int = (1, 1, 2, 6, 24, 120) Note : pour écrire une fonction récursive f, et donc d’avoir le droit d’appeler f dans la définition de f, le mot clé rec est à placer juste avant l’identificateur lors de la liaison globale :

Note : ce laboratoire est prévu pour être fait durant deux scéances. 1. Définition de type et filtrage par motif 1.1. Cartes Définir un type card qui représente les différentes cartes possibles pour un jeu de carte. Une carte peut soit être une valeur numérique, soit une figure parmi le valet, la dame, et le roi. Une carte a également une couleur (cœur, carreau, trèfle, ou pique). On souhaite comparer les cartes par valeur, où la valeur d’une carte numérique et égale à son nombre, et où le valet à une valeur inférieure à la dame, qui a une valeur inférieure au roi.

Les fonctions d’ordre supérieur sont des fonctions paramétrées par une ou plusieurs fonctions et/ou qui renvoient une fonction. Le but de ce TP est d’utiliser et d’écrire de telles fonctions et de se familiariser avec cette notion. Premières fonctions d’ordre supérieures et curryfication Dans cet exercice, on utilisera les deux définitions suivantes : let square (x : int) : int = x * x let my_list = [3; 12; 3; 40; 6; 4; 6; 0] Exprimer le type de la fonction f_sum paramétrée par une fonction f ainsi que deux entiers a et b et qui calcule f(a) + f(b).

Arbre binaire Rappel : un arbre binaire est un objet récursif défini comme étant soit une feuille; soit un nœud interne portant un élément et à partir duquel sont attachés deux arbres binaires. De manière équivalente, un arbre binaire est une structure de données qui peut se représenter sous la forme d’une hiérarchie dont chaque élément est appelé nœud. Dans un arbre binaire, chaque élément possède au plus deux éléments enfants au niveau supérieur, habituellement appelés gauche et droit.

Preuves de théorèmes Théorèmes sur append Définir la fonction append qui prend deux listes en argument et renvoie la concaténation de ces deux listes. Démontrer que la liste vide est l’élément neutre à gauche pour append, c’est-à-dire append [] xs = xs pour tout xs Démontrer que la liste vide est l’élément neutre à droite pour append, c’est-à-dire append xs [] = xs pour tout xs Définir la fonction rev qui inverse une liste.

Écrire une relation my_member/2 entre une liste et ses membres. ?- my_member(1, [1,2]). true . ?- my_member(1, [2,3]). false. ?- my_member(X, [1,2,3]). X = 1 ; X = 2 ; X = 3. ?- my_member(1, L). L = [1|_] ; L = [_, 1|_] ; L = [_, _, 1|_] . Écrire une relation nth/3 entre une liste et son nième élément. ?- nth(0, [a,b,c], X). X = a. ?

Les problèmes de ce labo sont inspirés de la suite de problème P-99 Arbres de résolutions Note: pour vérifier vos dessins d’arbre de résolutions, vous pouvez vous baser sur la bibliothèque sldnfdraw, dont vous pouvez consulter la documentation, ou bien utiliser interactivement en ligne sur cette page. Attention, cela ne marchera que pour les arbres finis. Nous avons également mis en place un fork qui dessine les arbres au format DOT, voir ici.