Compilation du filtrage (pattern-matching) ------------------------------------------ Le filtrage en ML: - dans les définitions de fonctions function pat1 -> expr1 | ... | patN -> exprN - dans les conditionnelles généralisées match expr with pat1 -> expr1 | ... | patN -> exprN - dans les handlers d'exceptions try expr with pat1 -> expr1 | ... | patN -> exprN Objectif: transformer ces constructions en séquences de tests élémentaires (du type if cond then expr1 else expr2). On se ramène à la forme de base du filtrage: match ident with pat1 -> expr1 | ... | patN -> exprN en ajoutant des lets s'il le faut. Le langage des motifs (patterns): pat ::= x | C(pat1, ..., patN) C est un constructeur, N est son arité. Exemples: - C est un constructeur d'un type concret type t = C1 of ... | C2 of ... | C3 (N est le nombre d'arguments du constructeur) - C est une constante: false, true, 0, 1, -1, ..., "hello", "world", ... (N=0) - C est [] (N=0) ou :: (N=2) - C est le constructeur de tuples (N >= 2) Remarque: certains types ont un nombre fini de constructeurs (types concrets, booléens), d'autres une infinité de constructeurs (entiers, chaînes). On se restreint aux motifs linéaires: pas de variable apparaissant plusieurs fois dans le motif. Exemple: (x, x) est non linéaire, mais (x, y) est linéaire. (On reviendra sur les motifs non linéaires plus tard.) On dit qu'une valeur v filtre un motif p s'il existe une substitution S (de variables par des valeurs) telle que v = S(p). Les valeurs sont ici v ::= C(v1, ..., vN) | \x.e Pour une valeur construite C(v1, ..., vN), il faut bien sûr N = arité(C). On considère aussi des valeurs "non construites" telles que les valeurs fonctionnelles notées \x.e ci-dessus. Remarque: si v = S(p), on peut supposer de plus que le domaine Dom(S) de la substitution S, c'est-à-dire l'ensemble des variables x telles que S(x) != x, est inclus dans l'ensemble des variables libres dans p. En effet, si x n'est pas libre dans p, on a v = S(p) quelle que soit l'image S(x) de x par S; on peut donc prendre S(x) = x et toujours avoir v = S(p). Exemples: - toute valeur filtre p = x - les valeurs qui filtrent p = C sont v = C - les valeurs qui filtrent p = (p1, p2, ..., pN) sont v = (v1, v2, ..., vN) telle que vi filtre pi pour i = 1...N. Remarque: ceci n'est vrai que si p est linéaire. Contre-exemple dans le cas p = (x,x) : 1 filtre x, 2 filtre x, mais (1,2) ne filtre pas (x,x). Preuve: * Soit v une valeur qui filtre p. On a donc v = S(p) pour une certaine substitution S. Comme S(p) = (S(p1), ..., S(pN)), il s'ensuit que v est de la forme (v1, ..., vN) avec vi = S(pi) pour tout i. Autrement dit, vi filtre pi pour tout i. * Réciproquement, supposons que les valeurs v1 ... vN filtrent respectivement p1 ... pN. Cela veut dire que pour tout i, il existe une substitution Si telle que vi = Si(pi), et de plus Dom(Si) est inclus dans Vars(pi). Comme p est linéaire, on a donc que les domaines Dom(Si) sont deux à deux disjoints. En particulier, Si(pj) = pj si i != j. Considérons S = S1 o S2 o ... o SN. Pour tout i, on a: S(pi) = S1(S2(...Si(...SN(pi))...)) = S1(S2(...Si(pi)) en raison de la linéarité de p = S1(S2(...vi)) par définition de Si = vi car vi ne contient pas de variables Donc, S(p) = (S(p1), ..., S(pN)) = (v1, ..., vN) = v. Ceci prouve bien que v filtre p. [] Extension à un pattern-matching a plusieurs cas: match id with p1 -> e1 | ... | pN -> eN Si V est la valeur de id, on dit qu'elle filtre le i-ème cas du filtrage si V filtre pi et pour tout j < i, V ne filtre pas pj (règle de priorité textuelle). Le résultat du matching est alors S(ei), où S est la substitution telle que S(pi) = V et Dom(S) inclus dans Vars(pi). Si V ne filtre aucun des p1 ... pN, le matching produit une erreur à l'exécution (exception Match_failure en Caml). Compilation d'un matching à une ligne: [match id with p -> act] = F(p, id, act) F(x, e, cont) = let x = e in cont F(C, e, cont) = if constr(e) = C then cont else error F(C(p), e, cont) = if constr(e) = C then F(p, #1(e), cont) else error F(C(p1, ..., pN), e, cont) = if constr(e) = C then F(p1, #1(e), F(p2, #2(e), .... F(pN, #N(e), cont))) else error Notations: constr(e) renvoie le constructeur de la valeur de e #N(e) renvoie la N-ième composante de la valeur de e Autrement dit, si e s'évalue en C(v1 ... vN), alors constr(e) s'évalue en C et #N(e) en vN. Exemple: match x with 1 :: y :: z -> y + length(z) devient if constr(x) = :: then if constr(#1(x)) = 1 then let y = #1(#2(x)) in let z = #2(#2(x)) in y + length(z) else error else error Exercice: introduire des "let" dans F pour éviter de recalculer #N(e). Preuve de correction: si e --> v, F(p, e, cont) --> S(cont) si il existe S tq v = S(p) et Dom(S) inclus dans Vars(p) --> error sinon Cas p = x: let x = e in cont --> cont[x <- v] Cas p = C: si v = C, F(C, e, cont) --> e. Sinon, F(C, e, cont) --> error. Cas p = C(p1, ..., pN): Si constr(v) != C, il n'existe pas de S tq v = S(p); d'autre part, F(C(p1, ..., pN), e, cont) --> error. Si constr(v) = C, écrivons v = C(v1, ..., vN). S telle que v = S(p) existe si et seulement si il existe S1...SN telles que vi = S(pi), et on a S = S1 o ... o SN. Si une des Si n'existe pas, l'appel F(pi, #i(e), ...) va se réduire en error, et donc F(C(p1, ..., pN), e, cont) aussi. Si toutes les Si existent, on obtient par hyp de réc F(p1, #1(e), F(p2, #2(e), .... F(pN, #N(e), cont))) --> F(p1, #1(e), F(p2, #2(e), .... SN(cont))) --> F(p1, #1(e), S2(...(SN(cont)))) --> S1(S2(...(SN(cont)))) = S(cont) [] Généralisation aux matchings à plusieurs lignes: filtrer ligne à ligne et au lieu de faire "error", passer à la ligne suivante. [match id with p1 -> act1 | ... | pN -> actN] = F(p1, id, act1, F(p2, id, act2, ...,F(pN, id, actN, error))) F(x, e, succès, échec) = let x = e in succès F(C, e, succès, échec) = if constr(e) = C then succès else échec F(C(p1, ..., pN), e, succès, échec) = if constr(e) = C then F(p1, #1(e), .... F(pN, #N(e), succès, échec) ..., échec) else échec Exemple: match x with [] -> 1 | 1 :: y -> 2 | z :: y -> z devient if constr(x) = [] then 1 else if constr(x) = :: then if constr(#1(x)) = 1 then let y = #2(x) in 2 else if constr(x) = :: then let z = #1(x) in let y = #2(x) in z Exercice: prouver que si e --> v F(p, e, succès, échec) --> S(cont) si il existe S tq v = S(p) --> échec sinon et en déduire la correction de la compilation. Problème: on effectue plusieurs fois les mêmes tests. on effectue des tests redondants car mutuellement exclusifs (constr(x) = [] et constr(x) = ::) Pour faire mieux, il faut considérer le matching dans sa globalité et non pas ligne à ligne. Pour pouvoir récurser, on utilise la forme généralisée suivante: | e1 e2 ... eM | | | | p11 p12 ... p1M -> act1 | | . . . . . | | . . . . . | | . . . . . | | pN1 pN2 ... pNM -> actN | Signfication: la même que match (e1, e2, ..., eM) with (p11, ..., p1M) -> act1 | ... | (pN1, ..., pNM) -> act2 Algorithme de compilation: F(matrice) Si N = 0: | e1 ... eM | F | | = error | | Si M = 0: | | | -> act1 | F | . | = act1 | -> actN | Si toute la colonne de gauche se compose de variables: | e1 e2 ... eM | | | M = | x1 p12 ... p1M -> act1 | | . | | xN1 pN2 ... pNM -> actN | On fait sauter les variables en introduisant des "let" dans les actions pour compenser: | e2 ... eM | | | MV = | p12 ... p1M -> let x1 = e1 in act1 | | . | | pN2 ... pNM -> let xN = e1 in actN | et on prend F(M) = F(MV) Si la colonne de gauche contient au moins un motif construit: (on suppose 3 constr C, D, E, d'arités 1, 0, 2 respectivement): | e1 e2 ... eM | | | | C(q) p12 ... p1M -> act1 | | D p22 p2M -> act2 | M = | x p32 p3M -> act3 | | E(r,s) p42 p4M -> act4 | | y p52 p5M -> act5 | | C(t) p62 ... p6M -> act6 | | E(u,v) p72 p7M -> act7 | On construit une sous-matrice pour chaque constructeur, qui regroupe les lignes commençant par ce constructeur, ainsi que les lignes commençant par une variable. Ce sont les seules lignes qui peuvent encore s'appliquer aux valeurs qui ont ce constructeur en tête. Dans les sous-matrice, la première colonne est remplacée par N colonnes correspondant aux N arguments du constructeur. | #1(e1) e2 ... eM | | | MC = | q p12 p1M -> act1 | | _ p32 p3M -> let x = e1 in act3 | | _ p52 p5M -> let y = e1 in act5 | | t p62 p6M -> act6 | | e2 ... eM | | | MD = | p22 p2M -> act2 | | p32 p3M -> let x = e1 in act3 | | p52 p5M -> let y = e1 in act5 | | #1(e1) #2(e1) e2 ... eM | ME = | _ _ p32 p3M -> let x = e1 in act3 | | | | r s p42 ... p4M -> act3 | | _ _ p52 p5M -> let y = e1 in act5 | | u v p72 ... p7M -> act7 | On considère aussi le reste (les lignes commençant par une variable), qui s'applique si la valeur à filtrer n'a pour constructeur ni C, ni D, ni E: | e2 ... eM | | | MR = | p32 p3M -> let x = e1 in act3 | | p52 p5M -> let y = e1 in act5 | On prend alors: F(M) = case constr(e1) in C -> F(MC) D -> F(MD) E -> F(ME) otherwise -> F(MR) Remarque: le "case" peut s'optimiser de nombreuses manières étant connu le type auquel appartiennent les constructeurs C, D, E: * si un seul constructeur C dans ce type (p.ex. la virgule): F(M) = F(MC) * si C, D, E sont les seuls constructeurs de ce type: pas de cas "otherwise". * si le type a 2 constructeurs: un simple if ... then ... else suffit. * si le type a un nombre fini de constructeurs: compilation par table de saut. * si nombre infini de constructeurs, mais ordre total entre les constructeurs (entiers, chaînes, mais pas flottants!): on organise les tests en arbres binaires. On lance la compilation sur F(M) avec M à une seule colonne: | id | | | M = | pat1 -> act1 | | ... | | patN -> actN | Exemple: match x with [] -> 1 | 1 :: y -> 2 | z :: y -> z devient case constr(x) in [] -> 1 :: -> case constr(#1(x)) in 1 -> let y = #2(x) in 2 otherwise -> let z = #1(x) in let y = #2(x) in z On remarque que ce code ne contient plus aucun test redondant. Une fois éliminé les calculs multiples de #1(x) et #2(x) par l'introduction de "let" supplémentaires, on obtient du code optimal. Avantages supplémentaires: * Détection des cas redondants: l'action correspondante n'apparaît pas dans le code produit. Exemple: match x with false -> 1 | true -> 2 | false -> 3 Le code généré est: case constr(x) in false -> 1 true -> 2 L'action "3" est éliminée. * Détection des filtrages non exhaustifs: "error" apparaît dans le code produit (après suppression des cas "otherwise" inutiles). Exemple: match x with 0 -> 0 | 1 -> 1 Le code généré est: case constr(x) in 0 -> 0 1 -> 1 otherwise -> error Exercice: est-ce que le filtrage suivant est exhaustif? match x with (true, true) -> true | (y, false) -> false | (false, y) -> false Mauvaise nouvelle: la détection des filtrages non exhaustifs est NP-dure. Preuve: par réduction du problème SAT: Est-ce que (!x1 | x2 | !x3 ...) ^ (x1 | x2 | ...) ^ ... est satisfiable? En prenant la négation: est-ce que (x1 ^ !x2 ^ x3 ...) | (!x1 ^ !x2 ^ ...) | ... est une tautologie? (toujours vraie pour toutes les valeurs des xi). C'est une tautologie si et seulement si | x1 x2 x3 ... | | | | true false true ... -> () | | false false _ ... -> () | | ... | est exhaustif. Conséquence (si P != NP): ce schéma de compilation est exponentiel. Exponentiel en la taille du code produit, en fait. Compilation plus rapide: avec partage du code. On introduit les constructions catch et throw: catch ... throw ... with ... "throw" se comporte en gros comme le déclenchement d'une exception, et "catch...with" comme l'interception d'une exception (construction "try...with"). La différence est que le "throw" a une portée statique: il se branche toujours à un "catch...with" qui est dans la même fonction. En conséquence, "throw" se compile très efficacement par un simple "goto" au code de la partie "with" du "catch...with" englobant le plus proche. Sémantique à réduction: catch throw with e --> e catch v with e --> v si v est une valeur throw + x --> throw x + throw --> throw et de même pour toutes les opérations strictes Même compilation qu'avant, mais la continuation d'échec est remplacée par la branche "with" du "catch" le plus proche, et activée par un simple "throw". Algorithme de compilation: F(matrice) Si N = 0: | e1 ... eM | F | | = throw | | Si M = 0: | -> act1 | F | . | = act1 | -> actN | Si le motif en haut à gauche est une variable: | e1 e2 ... eM | | | | x1 p12 ... p1M -> act1 | M = | . | | xK1 pK2 ... pKM -> actK | | pK+1 pN2 ... pNM -> actK+1| | . | | pN1 pN2 ... pNM -> actN | On divise au niveau de la derniere variable dans la colonne de gauche: | e2 ... eM | | | MV = | p12 ... p1M -> let x1 = e1 in act1 | | . | | pK2 ... pKM -> let x1 = e1 in actK | | e1 e2 ... eM | | | MC = | pK+1, pN2 ... pNM -> actK+1 | | . | | pN1 pN2 ... pNM -> actN | et on prend F(M) = catch F(MV) with F(MC) Si le motif en haut à gauche est construit: | e1 e2 ... eM | | | | C(q) p12 ... p1M -> act1 | | D p22 p2M -> act2 | M = | E(r,s) p32 p3M -> act3 | | E(u,v) p42 p4M -> act4 | | x p52 p5M -> act5 | | y p62 p6M -> act6 | | C(t) p72 ... p7M -> act7 | on regroupe constructeur par constructeur, mais seulement jusqu'au premier motif variable. Les lignes 5 et suivantes ne sont pas distribuées dans MC, MD, ME, on les laisse dans le reste MR. | #1(e1) e2 ... eM | | | MC = | q p12 p1M -> act1 | | e2 ... eM | | | MD = | p22 p2M -> act2 | | #1(e1) #2(e1) e2 ... eM | | | ME = | r s p32 ... p3M -> act3 | | u v p42 ... p4M -> act4 | On considère aussi le reste: | e1 e2 ... eM | | | MR = | x p52 p5M -> act5 | | y p62 p6M -> act6 | | C(t) p72 ... p7M -> act7 | On prend: F(M) = catch case constr(e1) in C -> F(MC) D -> F(MD) E -> F(ME) otherwise -> throw with F(MR) Appel initial: catch F(M) with error avec M comme précédemment: | id | | | M = | pat1 -> act1 | | ... | | patN -> actN | Code produit linéaire en la taille de l'entrée, car les lignes ne sont jamais dupliquées. Exemple: match x with (true, true) -> true | (y, false) -> false | (false, y) -> false Avec catch/throw: catch catch case constr(#1(x)) in true -> catch case constr(#2(x)) in true -> true otherwise -> throw with throw otherwise -> throw with catch case constr(#2(x)) in false -> let y = #1(x) in false otherwise -> throw with catch case constr(#1(x)) in false -> let y = #2(x) in false otherwise -> throw with throw with error Optimisation évidente: catch e with throw c'est la même chose que e. D'où après simplification: catch catch case constr(#1(x)) in true -> case constr(#2(x)) in true -> true otherwise -> throw otherwise -> throw with catch case constr(#2(x)) in false -> let y = #1(x) in false otherwise -> throw with case constr(#1(x)) in false -> let y = #2(x) in false otherwise -> throw with error Le code produit est moins efficace que dans le schéma précédent. En particulier, certains tests peuvent être exécutés plusieurs fois. Cependant, il factorise quand même pas mal de tests en pratique. Aussi, l'algorithme de compilation ne détecte plus les cas redondants ni les filtrages non exhaustifs. Extension aux motifs non linéaires et aux motifs avec gardes: match id with pat1 [when cond1] -> act1 | ... Le premier cas n'est sélectionné que si id filtre pat1, et de plus l'expression booléenne cond1 s'évalue à vrai. P.ex. match id with (x, x) -> ... s'écrit match id with (x, y) when x = y -> ... Implementation du when: on utilise throw pour reprendre le matching là où on l'a laissé. Dans le cas M = 0: si une seule ligne | | F | when cond1 -> act1 | = if cond1 then act1 else throw | | si plusieurs lignes (plusieurs actions possibles) | when cond1 -> act1 | | -> act2 | | -> act2 | F | . | = if cond1 then act1 else F | . | | -> actN | | -> actN | Problème de la direction du filtrage: dans les deux algorithmes, on peut choisir n'importe quelle colonne, pas forcément toujours la plus à gauche. Choisir une autre colonne peut donner un filtrage plus efficace.