Langages de programmation
Sémantiques opérationnelles
Interprètes
Le langage pseudo-pascal.
Postscript, PDF Didier Rémy Polytechnique, INRIA
Cours (super, self) Exercises
  1. Langages, sémantiqes
  2. Sémantiqes S.O.S.
  3. Fermetures
  4. Évaluation paresseuse
  5. Affectation
  6. Le langage Pseudo Pascal
  1. Évaluation (*)
  2. Interprète de pp (*)
  3. Travaux dirigés
  4. Projets de compilation


La chaîne de compilation




Langages de programmation


Langages généraux

Ils doivent être complets, ie. permettre d'exprimer tous les algorithmes calculables. Au minimum, il faut une mémoire infinie (ou grande) et la possibilité d'exprimer la récursion (construction primitive ou boucle while). Ex: Fortran, Pascal, C, Ocaml, etc.

Langages spécialisés (DSL pour Domain Specific Languages)

Langages pour le graphisme, pour commander des robots, pour faire des annimations graphiques; la calculette. Ils peuvent ne pas être complets.

Expressivité

Les langages généraux ne sont pas tous équivalents. L'expressivité est la capacité d'exprimer des algorithmes succinctement (et directement).

Exemples de constructions expressives


Les fonctions
    ·Est-ce que les fonctions peuvent être locales?

    ·Est-ce que les fonctions sont des valeurs?



Les structures de données (et filtrage)

Les modules, les objets

Le typage restreint l'expressivité au profit de la sécurité. (Comparer Scheme et ML).

L'expressivité du système de typage est donc aussi importante (comparer ML et Pascal ou Java).

Note: Pour comparer l'expressivité formellement, il faut en général le faire point à point en exhibant un codage d'un langage dans un autre qui respecte certaines règles (compositionalité, localité, etc.)

Syntaxe concrète -- syntaxe abstraite


La syntaxe concrète décrit les mots du langage et la façon d'assembler les mots en phrases pour constituer des programmes.

Elle ne donne aucun sens aux phrases:

    ·Plusieurs notations sont possibles pour une même construction. Exemple: les caractères 'a' et '\097' ou en la boucle for qui s'exprime en fonction de la boucle while

    ·La syntaxe concrète est linéaire et utilise des parenthèses.



La syntaxe abstraite est une représentation arborescente qui fait abstraction de la notation (on parle d'arbre de syntaxe abstraite). Elle définit les constructions du langage.

L'analyse lexicale traduit une suite de caractères en suite de mots. L'analyse grammaticale lit une suite de mots, reconnaît les phrases du langages et retourne un arbre de syntaxe abstraite.

Exemple simple: La calculette


Syntaxe concrète (dans le style BNF)
    expression ::= ENTIER
                 | IDENTIFICATEUR
                 | expression binop expression
                 | '(' expression ')'
    binop      ::= '+' | '-' | '*' | '/'


Syntaxe abstraite
    type expression =
      | Const of int
      | Variable of string
      | Bin of opérateur * expression * expression
    and opérateur = Plus | Moins | Mult | Div;;


Exemple l'expression (1 - x) * 3 a pour représentation
   Bin (Mult, Bin (Moins, Const 1, Variable "x"), Const 3);;


Sémantique des programmes


Il s'agit de donner un sens aux programmes.

Sémantique dénotationnelle

On associe un objet mathématique (abstrait) à chaque expression. Par exemple, on construit un modèle mathématique des entiers, muni des opérations sur les entiers.

C'est beaucoup plus dur pour les fonctions (calculables).

Sémantique opérationnelle

On définit un ensemble de valeurs (ou résultats) puis une relation d'évaluation qui relie des programmes avec des résultats.

Cette sémantique est plus proche de la syntaxe (moins abstraite), mais elle est plus facile à manipuler.

C'est aussi celle qui nous intéresse le plus souvent (pour calculer).

Sémantique opérationnelle de la calculette


Les valeurs sont les entiers.
    type valeur = int
On peut définir l'évaluation par un programme Ocaml qui prend un environnement initial associant des valeurs à certaines variables, une expression à évaluer et retourne un entier:
    let cherche x env = List.assoc x env
    let rec évalue env = function
      | Const n -> n
      | Variable x -> cherche x env
      | Bin (op, e1, e2) ->
          let v1 = évalue env e1 and v2 = évalue env e2 in
          begin match op with
           | Plus -> v1 + v2 | Moins -> v1 - v2
           | Mult -> v1 * v2 | Div -> v1 / v2
          end ;;


Une présentation plus neutre (S.O.S.)


(Sémantique Opérationnelle Structurelle)


Une autre présentation équivalente, mais plus mathématique et plus modulaire modulaire consiste à définir une relation r |- e Þ v qui se lit ``Dans l'environnement r, l'expression e s'évalue en la valeur v'' par des règles d'inférence, c'est-à-dire comme le plus petit ensemble vérifiant une certains nombre de règles (implications).

Une règle d'inférence est une implication P1 Ù ... Pk Þ C présentée sous la forme
P1 Ù ... Ù Pk
C
que l'on peut lire pour réaliser (évaluer) C il faut réaliser à la fois P1 et ... Pk.

Sémantique des expressions arithmétiques


Les jugements de la forme r |- e Þ v
    ·r lie des variables x à des valeurs v, i.e. c'est un ensemble de paires notées x |® v.

    ·e Î expressions et v Î IN. On note á nñ l'entier naturel associé à sa représentation n.
r |- Const n Þ n   
x Î dom (r)
r |- Variable x Þ r(x)
r |- e1 Þ v1    r |- e2 Þ v2
r |- Bin (Plus , e1, e2) Þ v1 + v2
  
r |- e1 Þ v1    r |- e2 Þ v2
r |- Bin (Times , e1, e2) Þ v1 * v2


Une construction de liaison


On étend la calculette avec des liaisons. On ajoute un noeud de syntaxe abstraite
    | Let of string * expression * expression
avec, par exemple, la syntaxe concrète
    "let" IDENTIFICATEUR "=" expression "in" expression
L'expression Let (x, e1, e2) lie la variable x à l'expression e1 dans l'évaluation de l'expression e2.

Formellement:
r |- e1 Þ v1   r, x1|® v1 |- e2 Þ v2
r |- Let (x, e1, e2) Þ v2
où r, x |® v ajoute la liaison de x à v dans l'environnement r en cachant une ancienne liaison éventuelle de x.

Modification de l'interprète


    let ajoute x v env = (x,v)::env
Noter le codage de r, x |® v par (x, v):: r
    let rec évalue env =
      ...
    | Let (x, e1, e2) ->
        let v1 = évalue env e1 in
        évalue (ajoute x v1 env) e2 ;;


Exercice 1  
Pour l'expression let x = 1 in (let x = 2 in x) + x, donner:
    ·Sa syntaxe abstraitre,
    ·Le résultat de son évaluation,
    ·La dérivation de l'évaluation de l'expression la plus interne.


Arbre de dérivation


L'ensemble des réponses (de l'exercice précédent) est contenu dans l'arbre de dérivation, qui constitue une preuve de l'évaluation de l'expression en la valeur 3
Ø |- Const 1 Þ 1   
x |® 1 |- Const 2 Þ 2    x |® 1, x |® 2 |- x Þ 2
x |® 1 |- Let (x, Const 2, x) Þ 2
   x |® 1 |- x Þ 1
x |® 1 |- Bin (Plus , Let (x, 2, x), x) Þ 3
Ø |- Let (x, Const 1, Bin (Plus , Let (x, 2, x),x)) Þ 3


Formalisation des erreurs


L'évaluation peut mal se passer, même dans la calculette, par exemple, lors d'une division par 0 ou de l'accès à une variable non liée.

La sémantique opérationnelle doit aussi formaliser les erreurs.

On remplace la relation r |- e Þ v par une relation r |- e Þ r où r est une réponse. Les réponses sont l'union des valeurs v ou des erreurs z.
r |- e1 Þ v1          r |- e2 Þ v2    v2 ¹ 0
r |- Bin (Div , e1, e2) Þ v1 / v2

r |- e2 Þ 0
r |- Bin (Div , e1, e2) Þ Division 
Le type des erreurs (par exemple):
type erreur = Division_par_zéro | Variable_libre of string


Implémentation des erreurs


Formellement, on utilise un type somme
type résultat = Valeur of valeur | Erreur of erreur


En pratique, on utilise les exceptions du langage hôte
exception Erreur of erreur
let erreur x = raise (Erreur x)
let cherche x l =
  try List.assoc x l
  with Not_found -> erreur (Variable_libre x)
let rec évalue environnement = function 
    ...
  | Bin (Div, e1, e2) ->
      let v1 = évalue env e1 and v2 = évalue env e2 in
      if v2 = 0 then erreur (Division_par_zéro)
      else v1 / v2 ;;


Terminaison


L'évaluation peut ne pas terminer.

La S.O.S (à grands pas) ne permet ne modélise pas la terminaison. En effet, elle met directement en relation un programme avec la réponse finale. Aussi, un programme qui ne termine pas ne peut pas être mis en relation avec une réponse.

Sémantique à réduction à petits pas

Dans le cours Langage et programmation on définit une sémantique opérationnelle à réduction ``à petits pas'' qui permet quand même de décrire le calcul des programmes qui ne terminent pas: le calcul est modélisé par une relation de réduction interne, i.e. les programmes se réduisent sur eux mêmes (chaque étape élémentaire du calcul est modélisé par un petit pas de réduction) jusqu'à l'obtention d'une valeur ou d'un programme bloqué (erreur).

La calculette fonctionnelle


Ajout des fonctions
    ·Fun (x,e) désigne une fonction qui à x associe l'expression e.
    ·App (e1,e2) désigne l'application d'une expression fonctionnelle e1 à une expression e2.


Difficultés engendrées
  1. Les fonctions sont définies dans un environnement r mais elles sont appelées dans un environnement r' en général différent;

    La liaison statique exige que la valeur des variables soit prise au moment de la définition.
  2. Si les fonctions sont des valeurs (retournées en résultat), alors leur durée de vie peut excéder leur portée lexicale.


Exemple


Liaison statique
let x = 3             (* env1 : x est lié à une valeur v  *)
let rec mem =         (* la valeur de x est celle de env1 *)
  function [ ] -> false | h::t -> x = h && mem t
let x = w             (* env2 : x est lié à la valeur w   *)
mem l                 (* doit être évalue; dans env1      *)


Valeur fonctionnelles
let incr x = fun y -> x + y  
                    (* incr x retourne une fonction       *)
let f = incr 3      (* f doit mémoriser la valeur 3 de x  *)
f 4                 (* pour la restaurer lors de l'appel  *)


Fermetures


Une solution générale consiste à évaluer les fonctions en des fermetures.

Une fermeture est une paire á Fun (x, e),rñ formée d'une expression fonctionnelle Fun (x, e) et d'un environnement r.
r |- Fun (x, e) Þ á Fun (x, e),rñ
On peut éventuellement restreindre r à l'ensemble des variables libres dans Fun (x, e). Elle permet d'enfermer une expression avec son environnement statique. Une fermeture est une valeur qui peut être passée en argument.

L'application restore l'environnement statique.
r |- e1 Þ á Fun (x, e0),r0ñ    r |- e2 Þ v2    r0, x |® v2 |- e0 Þ v
r |- App (e1, e2) Þ v


Variables libres


Un variables libre d'une expression est une variable utilisée dans cette expression dans un contexte où elles ne sont pas liée:
vl (Const n) = Ø     vl (App (e1, e2)) = vl e1 È vl e2
vl (Variable x) = { x }     vl (Plus (e1, e2) = vl e1 È vl e2
vl (Fun (x, e)) = vl e1 \ { x }     ...


Exemple La seul variable libre de (fun y -> x + (fun x x) y) est x. En effet y apparaît dans une contexte dans lequel elle est liée. Par contre, x apparaît au moins une fois dans un contexte dans lequel elle n'est pas liée.

Fermetures

Il suffit de mettre dans une fermeture les variables libres. On peut remplacer á e,rñ par á e,r / vl (e)ñ car r ne sera utilisé que pour évaluer l'expression e.

Évaluation paresseuse


La sémantique précédente est dite en appel par valeur parce que les arguments sont évalués avant d'être passés aux fonctions.

Pour donner une sémantique en appel par nom (utilisée dans les langages Algol, Miranda, Haskell, Gaml), on gèle les arguments des fonctions, jusqu'à ce que leur évaluation devienne indispensable.

Comme pour les fonctions, il faut sauver le contexte d'évaluation dans des fermetures, aussi appelées glaçons (expressions gelées).
r |- e1 Þ á Fun (x, e0),r0ñ      r0, x |® á e2,rñ |- e0 Þ v
r |- App (e1, e2) Þ v
r' |- e Þ v
r, x |® á e,r'ñ |- x Þ v


Évaluation paresseuse


L'appel par nom conduit à réévaluer plusieurs fois la même expression (chaque fois qu'un glaçon est dégelé).

L'évaluation paresseuse est une évaluation en appel par nom, avec en plus la propriété qu'un glaçon n'est évalué qu'un seule fois. On utilise l'affectation (voir plus loin) pour transformer un glaçon en une valeur après sa première évaluation.

L'évaluation paresseuse parce qu'elle ne force pas l'évaluation des arguments à de meilleures propriétés (App (Fun (x, e1), e2)) est équivalent à e1 {x ¬ e2}, ie. e1 où x est remplacé par e2.

En pratique toutefois:
    + L'évaluation paresseuse ne se combine pas bien avec des effets de bords (affectation, exception).
    - L'évaluation paresseuse peut être simulée (manuellement) en appel par valeur en codant les glaçons comme des fonctions.
La conditionnelle


La construction Ifz (e1, e2, e3) est toujours une construction paresseuse (l'un des deux derniers arguments seulement est évalué).
r |- e1 Þ 0    r |- e2 Þ v
r |- Ifz (e1, e2, e3) Þ v
  
r |- e1 Þ n    n ¹ 0    r |- e3 Þ v
r |- Ifz (e1, e2, e3) Þ v


Le AND et le OR

En Pascal ces opérateurs sont stricts: ils évaluent leurs arguments. En C et dans la plupart des langages, ils sont paresseux comme la construction ``ifz''. Le plus simple est de lire e1  and  e2 comme if e1  then  e2  else  false .

Fonctions globales non retournées


(en appel par valeur)


Les fermetures peuvent être évitées lorsque les fonctions sont globales et jamais retournées en résultat.

Les seules variables libres d'une fonction sont alors les variables globales. L'environnement de définition est l'environnement global, que l'on peut réinstaller à toute application.

Pour cela, on sépare l'environnement global r0 de l'environnement local r et on écrit: r0; r |- e Þ v.
r0; Ø |- Fun (x, e) Þ Fun (x, e)
r0; r |- e1 Þ Fun (x, e0)    r0; r |- e2 Þ v2    r0; x |® v2 |- e0 Þ v
r0; r |- App (e1, e2) Þ v


Fonctions locales non retournées


Les fonctions locales non retournées sont un cas intermédiaire.

On peut éviter les fermetures par remontée des variables.

Principe: une fonction f =def Fun (x, e) avec une variable libre y locale à une fonction globale g peut être transformée en une fonction globale f' =def Fun ((x, y), e). Les appels à f de la forme App (f, e) sont transformés en App (f, e, y).

Il faut si besoin renommer d'autres liaisons locale de la variable y qui cacheraient la liaison globale y.

Note: Comme les deux programmes ont la même sémantique, on peut utiliser la transformation inverse si le langage le permet, et écrire des programmes où les variables sont ``descendues''.

Exemple
Deux styles de programmation différents.

Variables remontées
let member x l =
  let rec mem = function
    | [] -> false
    | h::t -> 
        x = h || mem t
  in mem l
  Variables descendues
let rec member x = 
  function
  | [] -> false
  | h::t ->
     x = h || member x t
En pratique les deux écritures sont utiles (selon le contexte, et le nombre d'arguments).

Un compilateur peut effectuer la transformation de gauche à droite pour éliminer des fonctions locales, ou dans le sens inverse pour sortir des invariants de boucles, par exemple s'il y avait un calcul (sans effet de bord) avant l'appel à la fonction interne.

L'affectation des variables


On peut affecter les variables en Pascal ou C.

Il faut introduire une notion de mémoire s qui lie des adresses-mémoire l à des valeurs. L'environnement lie maintenant les variables modifiables (ou les références) à des positions mémoire (left-value) dont la vraie valeur (right-value) est définie dans s.

On écrit r / s |- e Þ v / s' qui se lit dans l'état-mémoire s et l'environnement r, l'évaluation de l'expression e produit une valeur v et un nouvel état mémoire s'.
r / s |- e1 Þ v1 / s1    l Ï s1    r, x1|® l / s1, l |® v |- e2 Þ v2 / s2
r / s |- Let (x,e1, e2) Þ v2 / s2
Lecture et écriture
x Î dom r    r (x) Î dom s
r / s |- x Þ s(r (x)) / s
  
x Î dom r    r / s |- e Þ v / s'
r / s |- Affecte (x, e) Þ v / s', r(x) |® v


Implémentation

On peut profiter des strutures mutables du langage hôte et se contenter d'un environnement qui lie les variables à des valeurs mutables (cela revient à utiliser la propre mémoire du langage hôte pour représenter s).
    type environnement = (string * valeur ref) list
    ...
    let rec évalue env = function
        ...
      | Variable x -> !(chercher x env)
      | Affecte (x, e) ->
          let v = évalue env e in (trouve x env) := v
(Pour simplifier, on a considérer toutes les variables mutables ici.)

Tableaux


Les tableaux alloués dynamiquement sont des structures de données mutables un peu comme les variables. Mais, à la différences des variables, les tableaux peuvent être passés à d'autres fonctions. L'accès à un tableau est explicite (il est implicite pour une variable).

On ajoute trois constructions
    ·Tableau (e1, e2) alloue un nouveau tableau de taille la valeur de e1 initialisé avec la valeur de e2.
    ·Lire (e1, e2) lit la case (correspondant à la valeur de) e2 du tableaux (la valeur de) e1.
    ·Ecrire (e1, e2, e3) écrit la case e2 du tableaux e1 avec la valeur de e3.
(Les références de Ocaml sont des tableaux à une seule case.)

Sémantiqe des tableaux


On introduit de nouvelles valeurs t qui sont des fonctions d'un ensemble d'indices [0, k -1] vers des adresses-mémoire.

Création
r / s |- e1 Þ k / s1    r / s1 |- e2 Þ v / s2    li Ï dom (s2)iÎ [0, k-1]
r / s |- Tableau (e1, e2) Þ (i |® li)i Î[0,k-1] / s, (li |® v)i Î [0, k-1]


Lecture
r / s |- e1 Þ t / s1    r / s1 |- e2 Þ k / s2    k Î dom (t)    t(k) Î dom s2
r / s |- Lire (e1, e2) Þ s2 (t(k)) / s2


Écriture similaire

Interprétation des tableaux


    ·On profite des tableaux mutables du langage hôte.
    ·Il y a plusieurs formes de valeurs qu'il faut distinguer par un type somme.
    ·L'accès à une valeur du mauvais type produit une erreur (que le typage devra empêcher).
    ·L'accès en dehors des bornes produit également une erreur (que le typage ne détecte pas en général).


Distinguer les valeurs (par un type somme)
(* les différents types de valeur *)
type valeur = Entier of int | Tableau of valeur array
type erreur = ... | Type | Indice 
(* pour retirer une valeur de la bonne forme *)
let entier = function Entier n -> n | _ -> erreur Type
let tableau = function Tableau t -> t | _ -> erreur Type


Tableaux (suite)
  let rec évalue env =
      ... 
    | Tableau (e_1, e_2) ->
        let k = entier (évalue env e_1) in
        let v = entier (évalue env e_2) in
        Tableau (Array.create k v)
    | Lire (e_1, e_2) -> 
        let t = tableau (évalue env e_1) in
        let k = entier (évalue env e_2) in
        if 0 <= k && k < Array.length t
        then Tableau (Array.create k v)
        else erreur Indice
    | Ecrire (e_1, e_2) -> 
        ...


Variables et tableaux non initialisées


En Pascal ou en C, les variables et les tableaux ne sont pas toujours initialisés.

Formellement, on introduit une valeur indéfinie et l'accès à une variable ou à une case non définie produit une erreur.

Ordre d'évaluation


La présence d'effets de bords (affectation) fixe l'ordre d'évaluation!
r / s |- e1 Þ á Fun (x,e0),r0ñ / s1
r / s1 |- e2 Þ v2 / s2      r0, x |® v2 / s2 |- e0 Þ v / s'
r / s |- App (e1, e2) Þ v / s'

Le langage Pseudo-Pascal (PP)


C'est un pascal simplifié, pour limiter le nombre de constructions.

Description informelle
    ·Syntaxe Pascal.
    ·Valeur entières et booléens; ni chaînes ni flottants
    ·Des tableaux dynamiques (durée de vie infinie). Pas d'enregistrements.
    ·Les fonctions sont globales, mutuellement récursives et jamais retournées.

Le résultat d'une fonction est passé en affectant la variable de même nom.
    ·Le passage d'argument est toujours en appel par valeur.
    ·Les variables sont toutes mutables.
Arbre de syntaxe abstraite


On conserve les informations de types (pour permettre une analyse de type ultérieure)
  type type_expr = Integer | Boolean | Array of type_expr;;
Un programme est composé d'un ensemble de déclarations de variables et de fonctions et d'un corps (une instruction).
type var_list = (string * type_expr) list
type program = {
   global_vars : var_list; 
    definitions : (string * definition) list;
    main : instruction;   (* corps du programme *) } 
and definition = {
    arguments : var_list; result : type_expr option;
    local_vars : var_list;
    body : instruction;   (* corps de la fonction *) }
Suite (expressions)
and expression =
    (* constantes *)
  | Int of int | Bool of bool
    (* opérations binaires *)
  | Bin of binop * expression * expression
    (* accès à une variable *)
  | Get of string
    (* appel de fonction *)
  | Function_call of string * expression list
    (* accès dans un tableau à une position *)
  | Geti of expression * expression
    (* Création d'un tableau d'une certaine taille *)
  | Alloc of expression * type_expr
and binop = Plus | Minus | Times | Div
  | Lt | Le | Gt | Ge | Eq | Ne
Suite (expressions)
  and instruction = 
      (* Affectation d'une variable *)
    | Set of string * expression
      (* Suite d'instructions *)
    | Sequence of instruction list
    | If of expression * instruction * instruction
    | While of expression * instruction
      (* Appel de procédure *)
    | Procedure_call of string * expression list
      (* Ecriture d'un entier *)
    | Write_int of expression
      (* Lecture d'un entier dans une variable *)
    | Read_int of string
      (* Affectation dans un tableau *)
    | Seti of expression * expression * expression


Exercices


Interprète pour le langage PP

La syntaxe abstraite est donnée par pp.mli.

Les interfaces sont imposées interpret.mli

Quelques programmes tests: fact.ml, fib.ml, et memo_fib.ml

Écrivez-en quelques autres.

Extensions du langage langage PP

Considérer un langage PP+ plus évolué et le traduire dans le langage PP. On pourra
    ·Autoriser une construction de liaison locale Let (x, e1, en) et la tradiore en des déclarations de variables au niveau la définition de fonction ou au niveau global.
    ·Autoriser les fonctions locales et les traduire en fonctions globales par remontée des variables.


Projets de compilation


But:
    ·Mieux maîtriser l'ensemble de la chaîne d'un compilateur.
    ·Apporter votre solution personnelle à un problème concret.


Points communs (pour de nombreux projets):
    ·Modification légère de l'ensemble.
    ·Écriture, ré-écriture, ou modification importante d'un maillon.
    ·Quelques sujets plus indépendants demande d'écrire une autre chaîne de compilation.


Choisissez
    ·Un sujet qui vous plaît
    ·À votre mesure (les difficultés sont très variées).
Pleins de sujets


  1. Implémenter (un mini) Lex.
  2. Implémenter (un mini) Yacc.
  3. Transformer les fonctions locales en fonctions globales au niveau du langage source.
  4. Ajouter des enregistrements, des chaînes de caractères, des caractères (alloués dans le tas ou en pile).
  5. Compiler un Pseudo Pascal Fonctionnel ou un mini ML (fonctions locales retournés avec fermetures ou environnements chaînés en pile)
  6. Optimisations du code source (évaluation partielle, ...)
  7. Remplacer une solution approchée d'un des maillons par une solution plus efficace (produisant un meilleur résultat).
  8. Écrire un vérificateur de types pour Pseudo Pascal.
  9. Gestionnaire de mémoire (par compteur de référence ou stop and copy)
  10. Compiler vers une autre architecture, ou vers une machine réelle (par exemple x86)
  11. Proposez votre projet.


This document was translated from LATEX by HEVEA and HACHA.