cours-2-1

Foil - Jean-Pierre Jacquot

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

14 pages

Catalan

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

Sujets

informatique

Informations

Publié par	Foil
Nombre de lectures	67
Langue	Catalan

Extrait

Termes 1
Objectifs du cours
er1 Niveau :
– Fonctions : définition et application
– Types : définition, calcul de type, constructeurs
– Noms : environnements
– Récursivité : principe de récurrence et calculs
ème2 Niveau :
– Modularité et structures de données + Termes
– Langage informatique :
» Syntaxe et Grammaire
» Compilation
• syntaxe
• sémantique
» Exécution
DEUG 2 2000
Termes 2
Approche suivie
Travail centré sur un projet : la construction d’un
compilateur
“texte de analyseur générateur Résultats
exécuteur
programme” syntaxique de code du calcul
machinegrammaire sémantique
du langage du langage abstraite
Remarques importantes :
– c’est un gros travail : il faudra être présent tout le temps
– nous fournirons beaucoup des programmes : il faut savoir lire
et comprendre
– ce qui a été fait l’an passé est supposé connu
DEUG 2 2000
Page 1Termes 3
Détails pratiques
Organisation similaire à l’an passé :
– cours, TD, TD machine
Rappel : les machines sont en libre service !
Evaluation :
– un examen pratique
– un examen écrit
Bibliogaphie :
G. Cousineau, M. Mauny, Une approche fonctionelle de la
programmation, EdiScience
P. Weiss, X. Leroy, Le langage caml, InterEdition
DEUG 2 2000
Termes 4
Noms : rappels
Nommage : mécanisme liant un symbole (le nom) à une valeur
Environnement : mécanisme permettant de décider quelle
valeur est liée à un nom
syntaxe:
Déclaration globale
let <nom> = <valeur>;;
Déclaration locale
let <nom> = <valeur>
in <expression>;;
DEUG 2 2000
Page 2s
t
s
s
s
s
Termes 5
Types : rappels
Un type est défini par trois vues
– une expression de type (son nom)
Types simples : int, float, string, bool, char
Types construits : 1 -> 2, 1 * 2
Types nommés :
type <nomtype> = <expression de type>;;
– un ensemble de valeurs (entiers, décimaux, listes d'entiers)
avec une syntaxe spécifique pour les types prédéfinis
– un ensemble d'opérations associées
float : +., -,, int_of_float, sin, etc.
bool: or,&, etc.
listes: List.hd, List.for_all, @, etc.
DEUG 2 2000
Termes 6
Types : rappels
Typage : règles permettant de calculer le type d’une expression
en fonction de ses constituants
a + b est de type int si a et b sont de type int
(f x) est bien typée si
f est de type s -> t
x est de type
(f x) est alors de type
Le type de l'expression (function p -> <exp p>) est
l'expression la plus simple de la forme s -> t qui garantit que
<exp p> est bien typée
on calcule un type fonctionnel par unsystème d'équations dans
lesquelles les inconnue sont des noms de types
Expression polymorphe : expression dont le type contient des
variables de type
(function p -> p) : 'a -> 'a
Toute expression Caml doit être bien typée
DEUG 2 2000
Page 3Termes 7
Fonctions : rappels
Une fonction est une valeur :
Valeur d’une fonction : fermeture
On peut calculer une valeur fonctionnelle
On peut paramétrer une fonction par une autre
Une fonction permet de calculer :
Application : calcul d’une valeur en un point
Il est essentiel de ne pas confondre ces 2 points !
DEUG 2 2000
Termes 8
Fonctions : exemple
let derive =
function f ->
(function x ->
(f(x +. epsilon)-.f(x))/. epsilon);;
Valeur fonctionnellederive;;
type : (float -> float) -> float -> float
derive sin;; application en un point
type résultat : float -> float
double applicationderive sin 1.07;;
type : float
DEUG 2 2000
Page 4t
t
t
t
t
t
Termes 9
Fonctions : rappels
Interprétation du type fonctionnel :
-> -> 1 2 3
Soit une fonction à deux arguments
Soit une fonction à 1 argument dont le résultat est une fonction
Caml ne distingue pas entre les deux interprétations !
Toute fonction ayant le type -> -> peut être l’objet d’une 1 2 3
application partielle.
DEUG 2 2000
Termes 10
Récursivité : rappel
Expression de la notion de récurrence dans le domaine du
calcul
Ensemble inductif : ensemble (type) qui vérifie deux conditions
il possède un plus petit élément
il existe une (ou des) fonction qui transforme un élément en
son “suivant” qui est plus grand
Schéma standard :
let rec f =
function <arg_inductif> ->
if <arg_inductif> est le plus petit élement
then <valeur immédiate>
else <expression contenant
(f précédent de <arg_inductif>) >;;
DEUG 2 2000
Page 5Termes 11
Exemple
Déterminer si un nombre est premier
let est_premier =
function nombre ->
let rec cherche = function
0 -> false
| 1 -> true
| diviseur -> if nombre mod diviseur = 0
then false
else cherche (diviseur-1)

in if (nombre < 0)
then failwith "Erreur : nombre négatif"
else cherche (nombre-1);;
DEUG 2 2000
Termes 12
Listes : Rappel
Liste : structure de donnée inductive permettant de manipuler
un nombre indéterminé de valeurs
Typage : tous les éléments d'une liste doivent avoir le même
type
Notation :
[] liste vide, la plus petite liste
tete::reste ajout d'un élément (tete) à une liste (reste)
[v1; v2; v3] notation pour v1::(v2::(v3::[]))
Calculs : par leur nature inductive, les listes sont une des
structures calculatoires les plus importantes et les plus faciles
• soit la liste est vide
• soit la liste est constituée d'une tête et d'un reste !
DEUG 2 2000
Page 6Termes 13
Listes : Exemples
let rec nb_elem = function
[] -> 0
| t::r -> 1 + (nb_elem r);;
let rec est_dans =
function elt ->
function
[] -> false
| t::r -> (t = elt) or (est_dans elt r);;
DEUG 2 2000
Termes 14
Terme : définition
terme =
Valeur constituée d’une étiquette et d’une valeur Caml
L’étiquette est appelée constructeur
Les termes ont deux rôles en Caml
» Le rassemblement de plusieurs types en un seul
les types sommes
» La représentation de valeurs structurées complexes
les termes récursifs
DEUG 2 2000
Page 7t
t
t
t
Termes 15
Type somme
Problème : en Caml, une valeur possède un type unique. Dans
la réalité, il est souvent utile de considérer qu’une valeur peut
appartenir à différents ensembles.
Exemple : [1; 3.14; 44] est illégal en Caml, pourtant c’est une
liste de nombres.
Solution : étiqueter chaque valeur
créer un type qui soit l’union (la somme) des
valeurs étiquetées
[Entier 1; Reel 3.14; Entier 44] : nombres liste
Ceci devient du Caml correct
DEUG 2 2000
Termes 16
Termes : Notation
type nombre =
Entier of int
| Reel of float;;
Entier et Reel sont les constructeurs (étiquettes)
• Les étiquettes doivent commencer par une Majuscule !
On définit une valeur de terme par : (Etiquette valeur)
Typage :
soit le type t+ défini par
type t+ = Etiq of | Etiq of | .... 1 1 2 2
| Etiq of n n
Une expression de la forme (Etiq V ) est de type t+ si V est i i i
de type .i
DEUG 2 2000
Page 8*
Termes 17
Calcul avec les termes
Utilisation du mécanisme de filtrage
let rec somme_nombres = function
[] -> 0.0
| t:: r -> (val_nombre t) +. (somme_nombres r);;
let val_nombre = function
Entier n -> (float_of_int n)
| Reel r -> r;;
Règle : il faut qu’il y ait autant de filtres qu’il y a de
constructeurs dans le type somme.
DEUG 2 2000
Termes 18
Les valeurs structurées complexes
Problème : Comment représenter une valeur comme
2 + x + 4 * (y - 2)
de sorte qu’on puisse effectuer des traitements ?
Idée : pour calculer à la main, on structure la formule
+
+
2 x 4 -
y 2
Solution : on représente par un terme
DEUG 2 2000
Page 9Termes 19
Structure de terme
On observe qu’une formule est de la forme suivante
soit F + F, F*F, F-F
soit un entier
soit une inconnue
En Caml :
type formule =
Plus of formule*formule
| Moins of formule*formule
| Fois of formule*formule
| Coef of int
| Inc of string;;
Plus (Plus (Coef 2,Inc “x”),
Fois (Coef 4,(Moins (Inc “y”, Coef 2))));;
DEUG 2 2000
Termes 20
Structure de terme
A noter
Les termes sont définis récursivement
Il est possible de modéliser des objets très complexes
La structure du type (et des valeurs) rep