Langages De Programmation Et Compilation
École Normale SupérieureLangages de programmationet compilationJean-Christophe FilliâtreCours 1 / 23 septembre 2016Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 11
présentation du cours cours le vendredi, 8h30–10h30 en salle UV polycopié ensemble des transparents TD le jeudi/vendredi, 10h30–12h15 en salle Info 4 NIR avec Lélio Brun (lelio.brun@inria.fr) à partir d’aujourd’huitoutes les infos sur le site web du courshttp://www.lri.fr/ filliatr/ens/compil/questions Jean-Christophe.Filliatre@lri.frJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 12
évaluation un examen, en janvier anciens sujets corrigés sur le site un projet un mini compilateur réalisé en dehors des TD, seul ou en binôme rendu en deux fois (fin novembre, début janvier)note finale Jean-Christophe Filliâtreexamen projet2Langages de programmation et compilation2016–2017 / cours 13
objectif du coursmaı̂triser les mécanismes de la compilation,c’est-à-dire de la transformation d’un langage dans un autrecomprendre les différents aspects des langages de programmationpar le biais de la compilationJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 14
programmationici on programme en cours en TD pour réaliser le projet à l’examenon programme en OCamlJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 15
messageil n’y a pas de bon langage, il n’y a que de bons programmeursJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 16
suggestionlire La programmation en pratique de Brian Kernighan & Robert Pike(disponible à la bibliothèque)Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 17
aujourd’hui :Mise à niveau OCamlil y a un polycopié spécifique pour ce coursJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 18
présentationOCaml est un langage fonctionnel, fortement typé, généraliste,de la famille MLsuccesseur de Caml Light (lui-même successeur deCaml lourd )conçu et implémenté à l’INRIA Rocquencourt par Xavier Leroy et d’autresquelques applications : calcul symbolique et langages (IBM, Intel, DassaultSystèmes), analyse statique (Microsoft, ENS), manipulation de fichiers(Unison, MLDonkey), finance (LexiFi, Jane Street Capital), enseignementhttp://ocaml.org/Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 19
premiers pas en OCamlJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 110
un peu de maçonnerieon souhaite construire un mur avec des briques de longueur 2 () et de), dont on dispose en quantités respectives infinieslongueur 3 (voici par exemple un mur de longueur 12 et de hauteur 3 :Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 111
un peu de maçonnerie sérieusepour être solide, le mur ne doit jamais superposer deux jointuresJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 112
questioncombien y a-t-il de façons de construire un mur de longueur 32 et dehauteur 10 ?Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 113
première idéeon va calculer récursivement le nombre de façons C (r , h) de construireun mur de hauteur h, dont la rangée de briques la plus basse r est donnée cas de baseC (r , 1) 1 sinonC (r , h) XC (r 0 , h 1)r 0 compatible avec rJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 114
deuxième idéeon va représenter les rangées de briques par des entiers en base 2 dont leschiffres 1 correspondent à la présence de jointures00101010010ainsi cette rangée est représentée par l’entier 338 ( 001010100102 )Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 115
quel intérêt ?il est alors aisé de vérifier que deux rangées sont compatibles, par unesimple opération de ET logique (land en OCaml)ainsiland 001010100102010101001002000000000002 0land 010100101002001010100102000000100002 6 0maisJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 116
rangées de briquesécrivons une fonction add2 qui ajoute une brique de longueur 2droite d’une rangée de briques ràil suffit de décaler les bits 2 fois vers la gauche et d’ajouter 102de même on ajoute une briqueJean-Christophe Filliâtreavec une fonction add3Langages de programmation et compilation2016–2017 / cours 117
énumérer toutes les rangées de briqueson va construire la liste de toutes les rangées de briques possibles delongueur 32en OCaml, les listes sont construites à partir de la liste vide notée [] l’ajout d’un élément x au début d’une liste l noté x :: lJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 118
énumérer toutes les rangées de briqueson va écrire une fonction récursive qui parcourt cet arbre (conceptuel).jusqu’à trouver des rangées de la bonne longueurJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 119
somme sur une listepour écrire la fonction récursive C , on commence par écrire une fonctionsum qui calculeXsum f l f (x)x lc’est-à-diresum: (int - int) - int list - intJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 120
décompte récursifon écrit enfin la fonction récursive C de décompteet pour obtenir la solution du problème, il suffit de considérer toutes lesrangées de base possiblesJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 121
déceptionmalheureusement, c’est beaucoup, beaucoup, beaucoup trop long. . .Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 122
une troisième idéele problème est qu’on retrouve très souvent les mêmes couples (r , h) enargument de la fonction C , et donc qu’on calcule plusieurs fois la mêmechosed’où une troisième idée : stocker dans une table les résultats C (r , h) déjàcalculés c’est ce qu’on appelle la mémoı̈sationJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 123
quel genre de table ?il nous faut donc une table d’association qui associe à certaines clés (r , h)la valeur C (r , h)on va utiliser une table de hachageJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 124
table de hachagel’idée est très simple : on se donne une fonctionhash : clé intarbitraire à valeur dans 0.n 1 et un tableau de taille npour une clé k associée à une valeur v , on range le couple (k, v ) dans lacase du tableau hash(k)Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 125
collisionsplusieurs clés peuvent se retrouver dans la même case chaque case est une liste0123456Jean-Christophe Filliâtre(k1 , v1 ) [][](k2 , v2 )(k3 , v3 ) [][][](k4 , v4 ) [][]Langages de programmation et compilation2016–2017 / cours 126
mémoı̈sationon peut maintenant utiliser la table de hachage dans la fonction Con écrit deux fonctions count et memo count mutuellement récursives count effectue le calcul, en appelant memo count récursivement memo count consulte la table et la remplit avec count si besoinJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 127
c’est gagnéon obtient finalement le résultat% ocamlopt wall.ml -o wall% time ./wall806844323190414real 0m1.055sJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 128
si vous avez aimé ce problème.http ://projecteuler.net/Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 129
récapitulationJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 130
déclarationsprogramme suite de déclarations et d’expressions à évaluer interprétation, éventuellement interactive deux compilateurs (bytecode et natif)Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 131
variablevariable OCaml :1. nécessairement initialisée2. type pas déclaré mais inféré3. contenu non modifiableune variable modifiable s’appelle une référenceelle est introduite avec refJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 132
expressions et instructionspas de distinction expression/instruction dans la syntaxe : que desexpressionstoutes les expressions sont typéesles expressions sans réelle valeur (affectation, boucle, .) ont pour typeunit ; ce type a une unique valeur, notée ()Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 133
fonctions fonctions valeurs comme les autres : locales, anonymes, argumentsd’autres fonctions, etc. partiellement appliquées l’appel de fonction ne coûte pas cher polymorphesJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 134
polymorphismeOCaml infère toujours le type le plus général possibleexemple :val sum: (’a - int) - ’a list - intoù ’a représente une variable de typeJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 135
exempledans la bibliothèque standard, on trouveval List.fold left: (’a - ’b - ’a) - ’a - ’b list - ’a(** List.fold left f a [b1; .; bn]is f (. (f (f a b1) b2) .) bn *)applicationlet sum f l List.fold left (fun s x - s f x) 0 lJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 136
autre exemple : mémoı̈sationon peut écrire le principe de mémoı̈sation de façon génériquelet memo f let h Hashtbl.create 5003 infun x - try Hashtbl.find h xwith Not found - let y f x in Hashtbl.add h x y; yJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 137
autre exemple : mémoı̈sationval memo: (’a - ’b) - ’a - ’butilisationlet is prime n .let f memo is primeJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 138
autre exemple : mémoı̈sationne convient cependant pas à une fonction récursivelet rec f x .let g memo fn’aura pas l’efficacité espéréecar les appels récursifs dans f se font sur f, pas gJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 139
solutionil faut ajouter f en argument de la fonction qui calcule f xlet memo ff let h Hashtbl.create 5003 inlet rec f x try Hashtbl.find h xwith Not found - let y ff f x in Hashtbl.add h x y; yinfJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 140
autre exempleval memo: ((’a - ’b) - ’a - ’b) - ’a - ’bc’est un opérateur de point fixeutilisationlet count memo (fun count (r, h) - .)Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 141
allocation mémoireJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 142
GCallocation mémoire réalisée par un garbage collector (GC)Intérêts : récupération automatique allocation efficace perdre le réflexe allouer dynamiquement coûte cher. mais continuer à se soucier de complexité !Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 143
tableauxon a déjà vu les tableaux allocationlet a Array.make 10 0 accèsa.(1) affectationa.(1) - 5Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 144
enregistrementscomme dans beaucoup de langageson déclare le type enregistrementtype complexe { re: float; im: float }allocation et initialisation simultanées :let x { re 1.0; im -1.0 }accès avec la notation usuelle :x.imJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 145
champs modifiables en placetype personne { nom: string; mutable age: int }# let p { nom "Martin"; age 23 };;val p : personne {nom "Martin"; age 23}modification en place :# p.age - p.age 1;;- : unit ()# p.age;;- : int 24Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 146
retour sur les référencesréférence enregistrement du type suivanttype ’a ref { mutable contents : ’a }ref, ! et: ne sont que du sucre syntaxiqueles seules données modifiables en place sont les tableaux et les champsdéclarés mutableJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 147
listestype prédéfini de listes, α list, immuables et homogènesconstruites à partir de la liste vide [] et de l’ajout en tête ::# let l 1 :: 2 :: 3 :: [];;val l : int list [1; 2; 3]ou encore# let l [1; 2; 3];;Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 148
filtragefiltrage construction par cas sur la forme d’une liste# let rec somme l match l with []- 0 x :: r - x somme r;;val somme : int list - int fun notation plus compacte pour une fonction filtrant son argumentlet rec somme function []- 0 x :: r - x somme r;;Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 149
représentation mémoirelistes OCaml mêmes listes chaı̂nées qu’en C ou Javala liste [1; 2; 3] correspond à1Jean-Christophe Filliâtre23 []Langages de programmation et compilation2016–2017 / cours 150
types construitslistes cas particulier de types construitstype construit réunion de plusieurs constructeurstype formule Vrai Faux Conjonction of formule * formule# Vrai;;- : formule Vrai# Conjonction (Vrai, Faux);;- : formule Conjonction (Vrai, Faux)listes définies partype ’a list [] :: of ’a * ’a listJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 151
filtragele filtrage se généralise# let rec evalue functionVrai - trueFaux - falseConjonction (f1, f2) - evalue f1 && evalue f2;;val evalue : formule - bool fun Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 152
filtrageles motifs peuvent être imbriqués :let rec evalue functionVrai - trueFaux - falseConjonction (Faux, f2) - falseConjonction (f1, Faux) - falseConjonction (f1, f2) - evalue f1 && evalue f2;;Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 153
filtrageles motifs peuvent être omis ou regroupéslet rec evalue functionVrai - trueFaux - falseConjonction (Faux, ) Conjonction ( , Faux) - falseConjonction (f1, f2) - evalue f1 && evalue f2;;Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 154
filtragele filtrage n’est pas limité aux types construitslet rec mult function[]- 10 :: - 0x :: l - x * mult lon peut écrire let motif expression lorsqu’il y a un seul motif(comme dans let (a,b,c,d) v par exemple)Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 155
récapitulation allouer ne coûte pas cher libération automatique valeurs allouées nécessairement initialisées majorité des valeurs non modifiables en place (seuls tableaux etchamps d’enregistrements mutable) représentation mémoire efficace des valeurs construites filtrage examen par cas sur les valeurs construitesJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 156
exceptionsJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 157
exceptionsc’est la notion usuelleune exception peut être levée avec raiselet division n m if m 0 then raise Division by zero else .et rattrapée avec try withtry division x y with Division by zero - (0,0)on peut déclarer de nouvelles exceptionsexception Errorexception Unix error of stringJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 158
exceptions (exemple 1)exception utilisée pour un résultat exceptionneltry find table cléwith Not found - .Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 159
exceptions (exemple 2)exception utilisée pour modifier le flot de contrôletrywhile true dolet key read key () inif key ’q’ then raise Exit;.donewith Exit - close graph (); exit 0Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 160
modules et foncteursJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 161
génie logiciellorsque les programmes deviennent gros il faut découper en unités (modularité) occulter la représentation de certaines données (encapsulation) éviter au mieux la duplication de codeen OCaml : fonctionnalités apportées par les modulesJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 162
fichiers et moduleschaque fichier est un modulesi arith.ml contientlet pi 3.141592let round x floor (x . 0.5)alors on le compile avec% ocamlc -c arith.mlutilisation dans un autre module main.ml :let x float of string (read line ());;print float (Arith.round (x /. Arith.pi));;print newline ();;% ocamlc -c main.ml% ocamlc arith.cmo main.cmoJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 163
encapsulationon peut restreindre les valeurs exportées avec une interfacedans un fichier arith.mlival round: float - float% ocamlc -c arith.mli% ocamlc -c arith.ml% ocamlc -c main.mlFile "main.ml", line 2, characters 33-41:Unbound value Arith.piJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 164
encapsulation (suite)une interface peut restreindre la visibilité de la définition d’un typedans ensemble.mltype t int listlet vide []let ajoute x l x :: llet appartient List.memmais dans ensemble.mlitype tval vide: tval ajoute: int - t - tval appartient: int - t - boolle type t est un type abstraitJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 165
compilation séparéela compilation d’un fichier ne dépend que des interfaces des fichiersutilisés moins de recompilation quand un code change mais pas son interfaceJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 166
langage de modulesmodules non restreints aux fichiersmodule M structlet c 100let f x c * xendmodule A structlet a 2module B structlet b 3let f x a * b * xendlet f x B.f (x 1)endJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 167
langage de modulesde même pour les signaturesmodule type S sigval f: int - intendcontraintemodule M: S structlet a 2let f x a * xend# M.a;;Unbound value M.aJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 168
récapitulation modularité par découpage du code en unités appelées modules encapsulation de types et de valeurs, types abstraits vraie compilation séparée organisation de l’espace de nommageJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 169
foncteursfoncteur module paramétré par un ou plusieurs autres modulesexemple : table de hachage génériqueil faut paramétrer par rapport aux fonctions de hachage et d’égalitéJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 170
première solutionpasser les fonctions en argument :type (’a, ’b) tval create: int - (’a, ’b) tval add: (’a - int) - (’a, ’b) t - ’a - ’b - unitval find: (’a - int) - (’a - ’a - bool) - (’a, ’b) t - ’a - ’bproblème : il faut être cohérent dans l’utilisationJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 171
deuxième solutionpasser les fonctions à la création :type (’a, ’b) tval create: (’a - int) - (’a - ’a - bool) - int - (’a, ’b) tval add: (’a, ’b) t - ’a - ’b - unitval find: (’a, ’b) t - ’a - ’bJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 172
deuxième solutiontype (’a, ’b) t {hash: ’a - int;eq: ’a - ’a - bool;buckets: (’a * ’b) list array }let create hash eq n { hash hash; eq eq; buckets Array.make n [] }let add t k v let i (t.hash k) mod (Array.length t.buckets) int.buckets.(i) - (k, v) :: t.buckets.(i)let find t k let rec lookup function [] - raise Not found (k’, v) :: l - if t.eq k’ k then v else lookup linlookup t.buckets.((t.hash k) mod (Array.length t.buckets)Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 173
deuxième solutionproblèmes on ne peut plus comparer (avec ) ou stocker sur le disqueles tables de hachage on n’a pas toujours une structure pour y stocker les fonctionsJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 174
la bonne solution : un foncteurmodule HashTable(K: KEY) struct . endavecmodule type KEY sigtype keyval hash: key - intval eq: key - key - boolendJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 175
foncteur : le codemodule HashTable(K: KEY) structtype ’a t (K.key * ’a) list arraylet create n Array.make n []let add t k v let i (K.hash k) mod (Array.length t) int.(i) - (k, v) :: t.(i)let find t k let rec lookup function [] - raise Not found (k’, v) :: l - if K.eq k’ k then v else lookup linlookup t.((K.hash k) mod (Array.length t))endJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 176
foncteur : l’interfacemodule HashTable(K: KEY): sigtype ’a tval create: int - ’a tval add: ’a t - K.key - ’a - unitval find: ’a t - K.key - ’aendJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 177
foncteur : utilisationmodule Inttype keylet hashlet eq end struct int abs( )module Hint HashTable(Int)# let t Hint.create 17;;val t : ’ a Hint.t abstr (on ne connaı̂t pas encore le type des valeurs, d’où le ’ a)Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 178
foncteur : utilisation# Hint.add t 13 "foo";;- : unit ()# Hint.add t 173 "bar";;- : unit ()remarque : maintenant on connaı̂t le type des valeurs# t;;- : string Hint.t abstr Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 179
foncteur : utilisation# Hint.find t 13;;- : string "foo"# Hint.find t 14;;- : Exception: Not found.Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 180
foncteurs : applications1. structures de données paramétrées par d’autres structures dedonnées Hashtbl.Make : tables de hachage Set.Make : ensembles finis codés par des arbres équilibrés Map.Make : tables d’association codées par des arbres équilibrés2. algorithmes paramétrés par des structures de donnéesexemple : algorithme de recherche de plus court cheminJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 181
algorithme génériquemodule DijkstraShortestPath(G: sigtype graphtype nodeval successors: graph - node - (node * int) listend) :sigval shortest path:G.graph - G.node - G.node - G.node list * intendJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 182
exerciceécrire un foncteur pour calculer modulo mmodule Modular(M: sig val m: int end): sigtype tval of int: int - tval add: t - t - tval sub: t - t - tval mul: t - t - tval div: t - t - t(** divise x par y, en supposant y premier avec m *)val to int: t - intendJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 183
du bon usage des foncteursil faut résister à la tentation de tout généralisersuggestion : écrire un foncteur si il s’agit d’une bibliothèque générique(dont on ne connaı̂t pas les clients) on a soi-même au moins deux instances à en faireJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 184
persistanceJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 185
structures de données immuablesen OCaml, la majorité des structures de données sont immuables(seules exceptions : tableaux et enregistrements à champ mutable)dit autrement : une valeur n’est pas affectée par une opération, mais une nouvelle valeur est renvoyéevocabulaire : on parle de code purement applicatif ou encore simplementde code pur (parfois aussi de code purement fonctionnel)Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 186
exemple de structure immuable : les listeslet l [1; 2; 3]let l’ 0 :: ll’l0123 []pas de copie, mais partageJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 187
contrepartieun ajout en queue de liste n’est pas aussi simple :l1Jean-Christophe Filliâtre23Langages de programmation et compilation0 []2016–2017 / cours 188
concaténation de deux listeslet rec append l1 l2 match l1 with []- l2 x :: l - x :: append l l2let l [1; 2; 3]let l’ [4; 5]let l’’ append l l ’ll’123 []12345 []l’’blocs de l copiés, blocs de l’ partagésJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 189
listes chaı̂nées modifiables en placenote : on peut définir des listes chaı̂néespar exemple ainsitraditionnelles ,type ’a liste Vide Element of ’a elementand ’a element { valeur: ’a; mutable suivant: ’a liste }mais alors il faut faire attention au partage (aliasing )Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 190
autre exemple : les arbrestype tree Empty Node of int * tree * treeval add: int - tree - tree1212202042là encore, peu de copie et beaucoup de partageJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 191
intérêts pratiques de la persistance1. correction des programmes code plus simple raisonnement mathématique possible2. outil puissant pour le branchement algorithmes de recherche manipulations symboliques et portées rétablissement suite à une erreurJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 192
persistance et branchement (1)recherche de la sortie dans un labyrinthetype étatval sortie: état - booltype déplacementval déplacements: état - déplacement listval déplace: état - déplacement - étatlet rec cherche e sortie e essaye e (déplacements e)and essaye e function [] - false d :: r - cherche (déplace d e) essaye e rJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 193
sans persistanceavec un état global modifié en place :let rec cherche () sortie () essaye (déplacements ())and essaye function [] - false d :: r - (déplace d; cherche ()) (revient d; essaye r)i.e. il faut annuler l’effet de bord (undo)Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 194
persistance et branchement (2)programmes très simples, représentés partype instr Return of string Var of string * int If of string * string * instr list * instr listexemple :int x 1;int z 2;if (x z) {int y 2;if (y z) return y; else return z;} elsereturn x;Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 195
persistance et branchement (2)on veut vérifier que toute variable utilisée est auparavant déclarée(dans une liste d’instructions)val vérifie instr: string list - instr - boolval vérifie prog : string list - instr list - boolJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 196
persistance et branchement (2)let rec vérifie instr vars function Return x - List.mem x vars If (x, y, p1, p2) - List.mem x vars && List.mem y vars &&vérifie prog vars p1 && vérifie prog vars p2 Var - trueand vérifie prog vars function [] - true Var (x, ) :: p - vérifie prog (x :: vars) p i :: p - vérifie instr vars i && vérifie prog vars pJean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 197
persistance et branchement (3)programme manipulant une base de donnéesmise à jour complexe, nécessitant de nombreuses opérationsavec une structure modifiée en placetry. effectuer l’opération de mise à jour .with e - . rétablir la base dans un état cohérent . traiter ensuite l’erreur .Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 198
persistance et branchement (3)avec une structure persistantelet bd ref (. base initiale .).trybd : (. opération de mise à jour de !bd .)with e - . traiter l’erreur .Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 199
interface et persistancele caractère persistant d’un type abstrait n’est pas évidentla signature fournit l’information implicitementstructure modifiée en placetype tval create: unit - tval add: int - t - unitval remove: int - t - unit.structure persistantetype tval empty: tval add: int - t - tval remove: int - t - t.Jean-Christophe FilliâtreLangages de programmation et compilation2016–2017 / cours 1100
persistance et effets de bordspersistant ne signifie pas sans effet de bordpersistant observationnellement immuableon a seulement l’implication dans un sens :immuable persistantla réciproque est faussestructures persistantes structures non persistantesstructuresimmuablesJean
Langages de programmation et compilation Jean-Christophe Filli atre Cours 1 / 23 septembre 2016 Jean-Christophe Filli atre Langages de programmation et compilation 2016{2017 / cours 1 1. pr esentation du cours cours le vendredi, 8h30{10h30 en salle UV polycopi e ensemble des transparents TD le jeudi/vendredi, 10h30{12h15 en salle Info 4 NIR avec L elio Brun (lelio.brun@inria.fr) a partir d .
La programmation objets expliquée aux programmeurs Si vous êtes programmeur, mais habitué aux langages de programmation "procéduraux" (pascal, fortran, C, perl, etc.), ce chapitre est pour vous: il essaie d'expliquer comment on peut passer de la programmation procédurale à la programmation objet, via la programmation structurée.
4.1.3 Langages de programmation et construction des concepts. 92 4.1.4 Langages de programmation et développement cognitif et méta-cognitif. . 98 4.2 Caractéristiques souhaitables. 100. 4.2.1 Représentation et manipulation des objets. 100. 4.2.2 Graphisme 101 4.2.3 Editeur 101 4.2.4 Vocabulaire 102 4.2.5 Syntaxe 103 4.2.6 Styles de .
Ce chapitre présente l'atelier de programmation. Contenu de ce chapitre . Ce chapitre contient les sujets suivants : Présentation de l'atelier de programmation( § 1.1.1.1) Création ou modification de configuration d'une application( § 1.1.1.2) 1.1.1.1 Présentation de l'atelier de programmation . Langages utilisés
Cours c et programmation orientée objet Programmation orientée objet 3 UMMTO Apparu dans les années 60s au sein de MIT Offre une grande souplesse de travail maintenance aisée Objet en programmation objet dans le monde réel Objet propriétés (attributs ) actions (méthodes ) Objet en C Structure de données (objet simple ) Classe
Programmation pour la physique Ce cours est une introduction a plusieurs sujets importants pour la programmation scienti que : R evision de la programmation procedurale avec le langage Python Initiation aux principes el ementaires de la programmation orient ee objet Probl emes choisis de l'algorithmique : Algorithmes de tri Probl emes choisis de l'analyse num erique : Recherche des z eros .
Ce livre n'aborde pas des sujets comme la programmation web ou l'utilisation conjointe des langages Python et SQL. La description du langage couvre les be-soins qui sont ceux d'un ingénieur, c'est-à-dire une personne dont la programma-tion ne constitue pas l'essentiel de son travail. Chaque notion est illustrée par des
Ce guide de l'utilisateur vous apporte les renseignements dont vous aurez besoin pour utiliser les imprimantes iMZ320 et iMZ220. Ces imprimantes utilisent les langages de programmation CPCL et ZPL. Pour créer et imprimer des étiquettes à l'aide des langages CPCL et ZPL, veuillez vous référer au manuel de programmation CPCL et au guide
When recording archaeological finds using illustration, it is vital that you look very closely at the features visible on the objects. It is also important to look at colours, textures and materials. The ‘potato game’ is designed to get children looking at everyday objects that are usually taken for granted and spotting small features that make them unique. The game will also develop .
