flowchart TD A[*] --> A1[+] A --> A2[2] A1 --> A11[5] A1 --> A12[3] B[+] --> B1[+] B --> B2[2] B1 --> B11[5] B1 --> B12[3] C[+] --> C1[5] C --> C2[*] C2 --> C21[3] C2 --> C22[2]
1 Des calculs mathématiques aux programmes informatiques
Exercice 1.1 (Calculs mathématiques, programmes informatiques) Comment définir
- un calcul mathématique ?
- un programme informatique ?
La définition peut d’abord être informelle, mais la formalisation est nécessaire pour développer an aval des programmes et en amont des langages de programmation.
\[ \begin{array}{crcll} \textrm{terme} & t & ::= & x \mid y \ldots & \textrm{variable} \\ && \mid & c & \textrm{constante} \\ && \mid & t + t & \textrm{addition} \\ && \mid & t * t & \textrm{multiplication} \\ && \mid & -t & \textrm{opposition} \\ \textrm{constante} & c & ::= & 0 \mid -1 \mid 1 \mid -2 \mid 2 \mid \ldots & \textrm{entiers relatifs} \\ \end{array} \]
Exercice 1.2 (Typage) Lorsqu’on réalise des calculs, on applique des opérations ou des fonctions à des arguments. Est-ce toujours sensé ? Répondre par analogie avec l’analyse dimensionnelle en Physique. Proposer une discipline de typage pour les expressions d’un langage de programmation, avec l’idée qu’il doit être possible d’évaluer abstraitement un programme en utilisant un type, avant son évaluation réelle.
Exercice 1.3 (Type : le point de vue extérieur de la spécification) Comment spécifier un type pour pouvoir l’utiliser ? Quels services rend-il ? Pour répondre, on pourra s’appuyer sur la définition des structures mathématiques. Proposer la définition d’une interface, qui déclare les méthodes à l’interface entre le monde extérieur et les objets du type.
Développer l’exemple des entiers naturels en Java.
Justifier que l’interface minimale du type
Natpeut être définie ainsi, suivant la définition inductive des entiers naturels : \[ \begin{array}{crcll} \textrm{naturel} & n & ::= & 0 & \textrm{zéro} \\ && \mid & \mathtt{S}\ n & \textrm{successeur de } n.\\ \end{array} \]public interface Nat { // Accesseurs boolean estZero(); // teste si l'entier est nul. Nat predecesseur(); // renvoie le prédécesseur de cet objet. // Fabrique Nat zero(); // renvoie zéro. Nat successeur(); // renvoie le successeur de cet objet. }Pour vérifier que cette interface minimale suffit, définir une classe-module3 contenant les fonctions
somme,produitetegalite, calculant la somme et le produit et testant l’égalité de deux entiers. On utilisera la décomposition naturelle d’un entier naturel en soit zéro, soit le successeur du prédécesseur, et la récursion. Pour fabriquer de nouveaux entiers naturels, on utiliserazero()etsuccesseur().public class ModuleNat { public static Nat somme(Nat n, Nat p){ if(n.estZero()) return ...: return (... n.predecesseur() ...).successeur(); } public static Nat produit(Nat n, Nat p){ if(n.estZero()){ return n.zero(); } return ...; } public static boolean egalite(Nat n, Nat p){ if(n.estZero()) return ... if(p.estZero()) return ... return egalite(...); }
Exercice 1.4 (Type : le point de vue intérieur de l’implémentation) On appelle implémentation4 la réalisation d’un type, soit la définition des valeurs de ce type.
Comment implémenter un type ? Définir l’état d’un objet, avec ses attributs, ses constructeurs, dont le rôle est d’initialiser les attributs de l’état, et les méthodes déclarées dans l’interface, formées des accesseurs qui observent l’état, des fabriques, qui construisent des objets du type et des services, les opérations réalisées avec le type.
Développer en Java deux implémentations des entiers naturels, l’une inductive exploitant la définition par récurrence des entiers naturels, l’autre par restriction des entiers de type int (des entiers relatifs). Les tester en calculant la somme des dix premiers entiers par une itération et par une formule explicite (pour tester l’égalité, on pourra prendre le double de ces quantités car on ne dispose pas sur Nat de la division).
Définition inductive – Définir deux classes implémentant l’interface
Nat.class Zero implements Nat { public final static Nat singleton = new Zero(); // Aucun attribut ... } class Successeur implements Nat { // État : un attribut private Nat pred; // Constructeur public Successeur(Nat pred){ this.pred = pred; } ... }Restriction des entiers relatifs int – Définir une classe implémentant l’interface
Natpar restriction du type primitifint. Son état est formé d’un unique attribut de typeintvérifiant une propriété permanente, un invariant,class IntRestreint implements Nat { // État : un attribut vérifiant toujours this.val >= 0 private int val; // Constructeur public IntRestreint(int val){ this.val = val < 0 ? -val : val; } // Méthodes ... }
Exercice 1.5 (Objets ou modules : deux approches de l’interopérabilité à l’intra-opérabilité) AFFAIRE(sans doute leçon 2)
Exercice 1.6 (Fonctions pures ou impures - Des changements d’état) AFFAIRE(sans doute leçon 3)
Compilateur : traducteur dans le langage propre la machine, virtuelle ou réelle, qui va exécuter le code.↩︎
À l’extrême limite, certains langages théoriques utilisent un seul type : autrement dit ils ne sont pas véritablement typés. En pratique, ce n’est pas le cas : il existe au moins un système minimal de types. ↩︎
Une classe est qualifiée de classe-module si elle ne contient que des éléments statiques (qualifiés de
static) : elle ne sert donc pas de modèle pour des objets.↩︎C’est un anglicisme qui est adopté en français et doit être utilisé tant il décrit bien à la fois l’action et le son produit.↩︎