Planche 1
Cours 8
Objets - Classes - Méthodes
Jean-Jacques.Levy@inria.fr
http://jeanjacqueslevy.net

secrétariat de l'enseignement:
Catherine Bensoussan
cb@lix.polytechnique.fr
Laboratoire d'Informatique de l'X
Aile 00, LIX
tel: 34 67
http://w3.edu.polytechnique.fr/informatique

Planche 2
Références
Planche 3
Plan

  1. Un calcul des objets
  2. Exemples
  3. Objets modifiables
  4. Typage des objets ¹ sous-typage
  5. Les sujets non traités
  6. DEA + recherche
Planche 4
Les objets en PCF [Abadi-Cardelli 96]

Termes
M, N, P ::= ... voir cours précédents
  | {l1 = z x1. M1; l2 = z x2. M2; ... ln = z xn. Mn } objet (n ³ 0)
  | M.l valeur d'un champ
  | M.l Ü z x.N modification d'un champ
On écrira aussi {li = z xi. Mi iÎ1..n} pour un objet. (li distincts)
z x.M est une méthode.

Valeurs
V ::= ... comme avant
  |
{li = z xi. M
 iÎ1..n
 
i
}

Variables libres

z est un nouveau lieur. La variable liée parfois appelée self ou this.
FV(M.l) = FV(M)
FV({li = z xi. M
 iÎ1..n
 
i
}) =
n
È
i=1
FV (z xi.Mi)
FV(z x.M)= FV(M) - {x} FV(M.l Ü z x.N) = FV(M) È FV(z x.M)

Planche 5
Réductions

Soit o = {li = z xi. Mi iÎ1..n}
m_invocation o.li ® Mi [xi \ o]
m_update
o.li Ü z x.M ® { li = z x. M;  lj = z xj. M
 jÎ (1..n)-i
 
j
}

Abréviation pour les champs données

Si z x.M est une donnée (x ÏFV(M)), on pose
{...; l=M; ...} = {...; l=z x.M; ...}
o.l Ü M = o.l Ü z x.M

Alors on a bien (o.l Ü M).l ® M.

Exemples

Si P = { x = 3; y = 4 }
P.x ® 3 P.y ® 4
P.xÜ 5 ® { x = 5; y = 4 } P.xÜ 5. yÜ 6 ® { x = 5; y = 6 }

Planche 6


Exemples

Si P = { x = 3; y = 4;
move_x = z o.l d. o.x Ü o.x+d ;
move_y = z o.l d. o.y Ü o.y+d}
P.move_x  2
® (l d. P.x Ü P.x+d) 2
® P.x Ü P.x + 2
® P.x Ü 3 + 2
® P.x Ü 5
® { x = 5; y = 4;
move_x = z o.l d. o.x Ü o.x+d ;
move_y = z o.l d. o.y Ü o.y+d}

De même,
(P.move_x  2).move_y  3
®* { x = 5; y = 7;
move_x = z o.l d. o.x Ü o.x+d ;
move_y = z o.l d. o.y Ü o.y+d}

Planche 7
Exemple des cellules mémoires

let  c = {
contents =
 
0
;
get = z s.  s.contents;
set = z s.  l v. s.contents Ü v }

in ((c.set  3).set  (c.get + 1)).get
®* 4

Une cellule mémoire avec sauvegarde.

let  c = {
contents =
 
0
;
get = z s.  s.contents;
set = z s.  l v.  (s.backup Ü s.contents).contents Ü v ;
backup =
 
0
;
restore = z s.  s.contents Ü backup }

in ...

La même en utilisant deux lieurs self différents.

let  c = {
contents =
 
0
;
get = z s.  s.contents;
set = z s.  l v.   (s.restore Ü z t. t.contents Ü s.contents) .contents Ü v ;
restore = z s.  s.contents Ü
 
0
}

in ...

Planche 8
Calcul des objets purs

Exercice Soit
o1 = {l = z x.{ }}
o2 = { l = z x.  x.l }
o3 = { l = z x.  x }
o4 = { l = z y.  y.l Ü z x.x }

Montrer que o1.l ® { }, o2.l ® o2.l, o3.l ® o3, o4.l ®* o3

Récursion

Posons µ x.M = {mu = z x.  M[x \ x.mu] }.mu Alors on a
µ x.M ® M[x \ x.mu][x \ {mu = z x.  M[x \ x.mu] }]
  = M[x \ {mu = z x.  M[x \ x.mu] }.mu]
  = M[x \ µ x.M]

Exercice Montrer qu'on peut coder tout le lambda calcul avec les seuls objets.

Planche 9
Classes et sous-classes

On suppose donné un ensemble de fonctions l s.Mi, comment construire une classe à partir d'elles?

Une classe sera:
c = {
new = z z.  {li = z s. (z.li) (s)
 iÎ 1..n
 
};
li = l s. M
 iÎ 1..n
 
i
}

On crée un objet o par o = c.new ® {li = z xi. Mi iÎ 1..n}

Pour créer une sous-classe avec des fonctions supplémentaires l s.Mk, on écrit
c' = {
new = z z.  {li = z s. (z.li) (s)
 iÎ 1..n+m
 
};
lj = c.l
  jÎ 1..n
 
j
;
lk = l s. M
 iÎ n+1..n+m
 
k
}

Planche 10
Quelques remarques

Planche 11
Objets modifiables

Termes
M, N, P ::= ... comme avant
  | clone(M) clonage
Une location peut aussi être une valeur.

Règles de réduction
alloc
á {li = z xi. M
 iÎ1..n
 
i
},  sñ ® á ,  s + [={li = z xi. M
 iÎ1..n
 
i
} ]ñ
  (Ïdomaine(s))
m_clone á clone(),  sñ ® á ',  s + ['= s()]ñ ('Ïdomaine(s))
Si s() = {li = z xi. M
 iÎ1..n
 
i
}
m_invoc á .li,  sñ ® á Mi [xi \ ],  sñ   
m_upd
á .li Ü z x.M,  sñ ® á ,  s[ \ { li = z x. M;  lj = z xj. M
 jÎ (1..n)-i
 
j
}]ñ

En fait, clone est une opération dérivée.

Planche 12
Typage des objets



Si un objet o de type t a au moins tous les champs de o' de type t', il est logique de dire que t est un sous-type de t', noté t <: t'.

Par exemple, la cellule mémoire avec backup a un sous-type du type général des cellules (cf. exemples plus haut).

P :  t = {
x =
 
3
;   y =
 
4
;
move_x = z o.l d. o.x Ü o.x+d ;
move_y = z o.l d. o.y Ü o.y+d }

Pc  :  tc = P  with  { c = rouge } = {
x =
 
3
;   y =
 
4
;   c = rouge;
move_x = z o.l d. o.x Ü o.x+d ;
move_y = z o.l d. o.y Ü o.y+d }

Alors tc <: t
(Les points colorés forment un sous-ensemble des points).

Quel est le type de move_x? de move_y?

Planche 13
Le sous-typage ne suffit pas à typer les objets
[Cook, Hill, Canning 90]

La méthode z o.l d. o.x Ü o.x+d prend un point et un entier pour retourner un point.

move_x  :  t ® int ® t

Comme tc <: t, on peut aussi l'appliquer à un point coloré. On peut donc garantir que

Pc.move_x   3  :  t

Mais peut-on dire que Pc.move_x   3  :  tc ?

Si on répond oui, alors le code de move_x doit recopier tout les champs, couleur comprise, sinon il y a risque d'erreur à l'exécution. Donc son code ne dépend pas uniquement de son type!

Planche 14
Problème avec les types

Plus grave si on rajoute la méthode equals retournant 1 si les deux points sont égaux, et 0 sinon (en l'absence de booléens en PCF).

P :  t = {
x =
 
3
;   y =
 
4
;
equals = z o.l o'.  (o.x = o'.x) Ä (o.y = o'.y) }

Pc  :  tc
=
P   with  {
c = rouge ;
equals = z o.l o'.  (o.x = o'.x) Ä (o.y = o'.y) Ä (o.c = o'.c) }
=
{
x =
 
3
;   y =
 
4
;   c = rouge;
equals = z o.l o'.  (o.x = o'.x) Ä (o.y = o'.y) Ä (o.c = o'.c) }

Soient deux points P, P' et deux points colorés Pc, P'c.
P.equals   P' et Pc.equals   P'c sont bien typés.

Mais comme tc <: t, le terme Pc.equals   P' est aussi bien typé.
Or il provoque une erreur à l'exécution.

Typage des objets et sous-typage sont différents
Planche 15
Covariance / Contravariance

Le type d'une fonction est contravariant sur son argument et covariant dans son résultat. I.e

t <: t'    u <: u'   Þ   t' ® u <: t ® u'

Le type des objets et des méthodes doit en tenir compte.

Une autre solution est de ne pas autoriser de sous-typage ou plutôt de le rendre explicite, c'est la solution d'Ocaml. La relation <: apparait explicitement dans les programmes. L'avantage est de permettre l'inférence de types.

En Eiffel, on se sert d'informations dynamiques. En C++, Modula-3 et Java, le type des méthodes spécialisées ne peut changer.

Planche 16
Le typage des objets: problème difficile

Planche 17
Les problèmes non traités dans le cours

Pour en savoir plus Aller en DEA, en thèse.
cours de Leroy, Rémy, Castagna, Pottier au DEA SPP

Planche 18
La recherche

Planche 19
La recherche -- suite

Planche 20
2 exemples de DEA: DEA Algorithmique

1. Algorithmique et combinatoire des mots, [J. Berstel]
2. Géométrie computationnelle, [J.-D. Boissonnat]
3. Introduction au calcul parallèle et distribué, [M. Morvan]
4. Algorithmes probabilistes, [J.-M. Steyaert]
*. Pratique du calcul formel.

Filières, responsables et cours

1. Analyse d'algorithmes [J.-M. Steyaert]:
2. Automates et mots [J.-E. Pin]:
3. Calcul formel [D. Lazard]:
4. Combinatoire [R. Cori]:
5. Complexité, codage et cryptographie [J. Stern]:
6. Géométrie, images et robotique [O. Faugeras]:
7. Parallélisme et concurrence [A. Petit]:
*. Conception de circuits, [P. Bertin, J. Vuillemin].

http://w3.edu.polytechnique.fr/informatique/

Planche 21
DEA Sémantique, Preuves et Programmation

=6pt

1. Les termes en logique du premier ordre, [J.P. Jouannaud]
2. Lambda calcul, [T. Hardin]
3. Preuves constructives, [G. Dowek]
4. Sémantique dénotationnelle, [R. Di Cosmo]
5. Typage et programmation, [M. Mauny - D. Rémy - X. Leroy]

Filières, responsables et cours

=7pt 1. Langages, [G. Cousineau] Langages distribués, [C. Queinnec]; Sous-typage et langages à objets, [G. Castagna - F. Rouaix - D. Rémy] Compilation des langages fonctionnels et impératifs, [X. Leroy] Programmation logique avec contraintes et systèmes concurrents, [F. Fages - L.Fribourg]

2. Modèles Sémantiques, [P.-L. Curien] Types, catégories et domaines, [P.-L. Curien-G. Longo] Logique linéaire, [R. Di Cosmo] Concurrence et Communication, [G. Gonthier - J.-J. Lévy] Modèles algébriques des processus et méthodes de vérification, [ Ph. Schnoebelen]

3. Preuves et spécifications, [J.-P. Jouannaud] Calcul des constructions inductives, [C. Paulin - B. Werner] La méthode B, [V. Donzeau-Gouge, M. Simonot] Preuve par des techniques d'automates, [H. Comon] Réécriture et preuves, [J.-P. Jouannaud - C. Marche - M. Rusinowitch]

4. Sémantique et Interprétation abstraite, [R. Cousot] Fondements de l'interprétation abstraite, [P. Cousot] Interprétation abstraite: applications, [A. Deutsch - P. Granger - R. Cridlig] Langages objets, contraintes et typage, [F. Bourdoncle - B. Monsuez] Parallélisme : sémantique et preuve, [R. Cousot - E. Goubault - I. Mackie]

http://w3.edu.polytechnique.fr/informatique/

Planche 22
Laboratoires de recherche/Hitech

CNET Issy, Lannion Labri Bordeaux
CNRS Imag Grenoble
INRIA, 5 Unités de recherche Marseille Luminy
ENS Paris 6
ENS Cachan Paris 7, (Logique)
ENS Lyon Marne la Vallée
ENPC ORSAY
ENSMP Saint Denis
ENST CNAM
LIX  
 
 
Thomson LCR Lucent
Alcatel Marcoussis AT&T Bell labs
GENSET Bellcore
ILOG Compaq SRC, WRL
O2 Technology IBM Almaden, Yorktown
Chorus Systèmes Microsoft Research Cambridge
Xerox Grenoble Microsoft Research Redmond
Web Consortium Xerox PARC
Trusted Logic HPlabs
Cryo Networks SUN Microsystems
Intel

Planche 23
Domaines de recherche (exemple de l'INRIA)

=8pt Thèmes

1. Réseaux et systèmes
2. Génie logiciel et calcul symbolique
3. Interaction homme-machine, images, données, connaissances
4. Simulation et optimisation de systèmes complexes

Action de développements

DYADE : conception de systèmes d'information avancés
GÉNIE : science de l'information et ingénierie concourante
MÉDIACULTURE : système multimédia distribué pour la documentation culturelle
PRAXITELE : transport urbain public individuel
PRÉVISIA : interopérabilité des systèmes d'information
SYNCHRONE : environnement de développement de systèmes temps-réel
W3C : les services d'information sur Internet
WEBTOOLS : outils logiciels pour le World Wide Web

http://www.inria.fr/Recherche/activites-fra.html

Planche 24
Thème 1

=7pt

Parallélisme et architecture :

APACHE - Algorithmique parallèle et partage de charge
API - Architectures parallèles intégrées
CAPS - Compilation, architectures parallèles et systèmes
PAMPA - Environnement de programmation des architectures massivement parall èles
ReMaP - Régularité et parallélisme massif
SLOOP - Simulation, langages orientés objets et parallélisme

Réseaux, systèmes, évaluation de performances :

MÉVAL - Modélisation et évaluation des systèmes informatiques
MISTRAL - Modélisation en informatique et systèmes de télécommuni cation : recherche et applications logicielles
MODEL - Modélisation de systèmes aléatoires
RESEDAS - Outils logiciels pour les télécommunications et les systèmes d istribués
RODEO - Réseaux à haut débit, réseaux ouverts
SATURNE - Systèmes répartis tolérant les fautes et les intrusions
SIRAC - Systèmes informatiques répartis pour applications coopératives
SOLIDOR - Architectures et systèmes distribués extensibles, tolérance au x fautes, programmation objet
SOR - Systèmes d'objets répartis

Programmation distribuée et temps-réel :

ADP - Algorithmes répartis et protocoles
EPM-PATR - Environnement de programmation pour applications temps réel
MEIJE - Parallélisme, synchronisation et temps réel
PARA - Parallélisme, mobilité
REFLECS - Systèmes informatiques répartis temps réel tolérant les fautes
SPECTRE - Spécification et programmation des systèmes communicants et tem ps réel

Planche 25
Thème 2

=7pt

Sémantique et programmation :

CALLIGRAMME - Logique linéaire, réseaux de démonstration et grammaires cat égorielles
COQ - Spécifications et preuves de programmes
CRISTAL - Programmation typée, modularité et compilation
CROAP - Conception et réalisation d'outils d'aide a` la programmation
EURECA - Preuve, calcul symbolique et logique
LANDE - Langages déclaratifs
LOCO - Programmation logique avec contraintes
OSCAR - Outils syntaxiques pour la construction et l'analyse de programmes
PROTHEO - Contraintes, déduction automatique et preuves de propriétés de logiciels

Algorithmique et calcul formel :

ALGO - Algorithmes
CODES - Codes et protection de l'information
PRISME - Géométrie, algorithmes et robotique
SAFIR - Systèmes algébriques formels pour l'industrie et la recherche


Planche 26
Thème 3

=7pt

Bases de données, bases de connaissances, systèmes cognitifs :

ACACIA - Acquisition des connaissances pour l'assistance a` la conception par interaction entre agents
AIRELLE - Représentations et langages
ATOLL - Atelier d'outils logiciels pour le langage naturel
DIALOGUE - Dialogue homme-machine a` forte composante langagière
OPERA - Outils pour les documents électroniques : recherche et applications
ORION - Modélisation des connaissances pour l'automatisation des tâches
PSYCHO-ERGO - Psychologie ergonomique pour l'informatique
REPCO - Représentation des connaissances
RODIN - Systèmes de bases de données
SHERPA - Bases de connaissances a` objets
SHOOD - Méthodes et outils pour l'intégration de systèmes industriels
SYCO - Systèmes de compréhension et bases de connaissances
VERSO - Bases de données
Vision, analyse et synthèse d'images :

AIR - Traitement d'image et données satellites dynamiques
EPIDAURE - Imagerie et robotique médicale
iMAGIS - Modèles, algorithmes, géométrie pour le graphique et l'image de synthèse
ISA - Image, synthèse, analyse
MOVI - Modélisation, localisation, reconnaissance et interprétation en vis ion parordinateur
PASTIS - Analyse de scènes et traitement d'images symboliques
ROBOTVIS - Vision par ordinateur et robotique
SHARP - Programmation automatique et systèmes décisionnels en robotique
SIAMES - Synthèse d'image, animation, modélisation et simulation
SYNTIM - Analyse et synthèse d'images
TEMIS - Traitement, exploitation et modélisation d'images séquentielles

Planche 27
Thème 4

=7pt
Automatique, robotique, signal :

AS - Automatique et signal
ATGC - Action transversale génome et calcul
BIP - Conception et contrôle de robots marcheurs et applications
COMORE - Contrôle et modélisation de ressources renouvelables
CONGÉ - Contrôle géométrique des systèmes non linéaires
FRACTALES - Approche fractale pour l'analyse et la modélisation de signaux complexes
ICARE - Instrumentation, commande et architecture des robots évolués
MÉTA 2 - Méta automatique et méthodes de l'automatique
MIAOU - Mathématiques et informatique de l'automatique et de
l'optimisation pour l'utilisateur
PROMATH - Programmation mathématique
SAGEP - Simulation, analyse et gestion des systèmes de production
SOSSO - Applications et outils de l'automatique
SYSTOL - Modélisation statistique et applications biomédicales

Modélisation et calcul scientifique :

ALADIN - Algorithmes adaptés au calcul numérique intensif
CAIMAN - Calcul scientifique, modélisation et analyse numérique
ESTIME - Estimation de paramètres
IDOPT - Identification et optimisation de systèmes en physique et en environnement
M3N - Multi-modèles et méthodes numériques
MODULEF - Méthodes et outils pour le calcul scientifique
NUMATH - Analyse mathématique et traitement numérique de modèles non linéaires
OMEGA - Méthodes numériques probabilistes
ONDES - Modélisation, analyse, simulation des équations des ondes
SINUS - Simulation numérique dans les sciences de l'ingénieur
SYSDYS - Systèmes dynamiques stochastiques

Planche 28
En TD La prochaine fois

This document was translated from LATEX by HEVEA.