Cours 4 : Modes d’appels, Portée lexicale/ Liaison dynamique

Modes d’appels

Par valeurs

Appel par valeurs :

l’argument est évalué, puis sa valeur est passée à la fonction

⟶ argument évalué 1 fois

Ex :

  • C
  • C++
  • Python
  • CamL
  • Java, …

f(arg) : calcule déjà arg, puis passe l’argument à f

Appel par nom :

évalue la fonction, son paramètre formel est remplacé par l’argument

⟶ argument évalué à chaque fois qu’il est appelé

Ex :

  • Préprocesseur C : CPP
  • Algol, …
    • par valeur ou par nom, selon qu’on le précise ou non
  • $𝜆$-calcul : langage fonctionnel, dans lequel on peut tout coder

Avantages : Si on appel f sur un argument arg qui ne termine pas : f(arg)

Quand est-on susceptible d’utiliser ça ?

  • Quand utilise des programmes écrits automatiquement
  • Programmation de plus haut niveau : Fonctions de callback :
    • Node.js
    • Interface homme-machine
  • Dans les langages paresseux : listes infinies, etc…
    • ex: en Haskell, liste des
    nats::[int]
nats = 0:map (+1) nats

    Comment ça marche ? Haskell alloue un thunk : zone de la mémoire de la forme

    |0 (flag)|Code| |-|-| ou | 1 | Valeur| |-|-|

Appel par nécessité :

évalue la fonction, son paramètre formel est remplacé par l’argument, mais n’est évalué qu’une fois (avec un système de flags)

⟶ argument évalué 1 fois, si il est appelé

Ex : Langages paresseux : Haskell

Haskell

Langage purement fonctionnel : sans effets de bords.

Si f(arg), avec un arg qui prend 3h à calculer :

Haskell se dit :

  • Si f utilise effectivement arg ⟶ le calcule pendant 3h et le stocke

  • Sinon : ne calcule pas arg

DONC : sans effets de bords, l’appel par nécessité est plus proche de l’appel par nom que de l’appel par valeur, car retourne toujours les mêmes choses (alors que si arg ne termine pas : l’appel par valeur ne va pas terminer).

Ex :

Machine virtuelle de la première version de CamL = la CaM

Était lente en appel par nécessité : lent à cause des thunks :

  • il faut une allocation mémoire, avec flags, pour stocker 1+1 (alors qu’on prendrait 2 sec à le calculer et l’empiler sur la pile)
  • Toute la logistique qui va avec : gestion des thunks, etc…

Pb avec Haskell :

Attention, comme est paresseux : il garde en mémoire des arguments qui peuvent être inutiles en cas de pattern matching

Gros point positif, avec Haskell :

Compilateurs : font des compilations de “code mort” : découvre les bouts de code qui ne seront jamais exécutés, et les élimine.

Mais, ne trouve pas tout : ne pourra pas simplifier

i=1
if i==0 :
...

Ce que fait Haskell, c’est qu’il utilise l’appel par valeurs dès qu’une fonction f termine dans tous les cas, même si arg ne termine pas (car appel par valeur = plus rapide).

digraph structs {
node [shape=record];
struct1 [shape=record,label="<f0> |<f1>"];

struct2 [shape=record,label="<f0> 0|<f1> ?"];

struct3 [shape=record,label="<f0> 0|<f1> map (1+) nats"];

struct1:f0 -> struct2:f0;
struct1:f1 -> struct3:f0;

 }

⇓

Quelle est la première valeur de “nat” ?

⇓

digraph structs {
node [shape=record];
struct1 [shape=record,label="<f0> |<f1>"];

struct2 [shape=record,label="<f0> 1|<f1> 0"];

struct3 [shape=record,label="<f0> 0|<f1> map (1+) nats"];

struct1:f0 -> struct2:f0;
struct1:f1 -> struct3:f0;

 }

⇓

Quelle est la deuxième valeur ?

⇓

digraph structs {
node [shape=record];
struct1 [shape=record,label="<f0> |<f1>"];

struct2 [shape=record,label="<f0> 1|<f1> 0"];

struct3 [shape=record,label="<f0> 1|<f1> "];

struct4 [shape=record,label="<f0> 1|<f1> 0+1 = 1"];

struct5 [shape=record,label="<f0> 0|<f1> map (1+) (map (1+) nats)"];

struct1:f0 -> struct2:f0;
struct1:f1 -> struct3:f0;


struct3:f1 -> struct4:f0;
struct3:f1 -> struct5:f1;

 }

Finite Model Finder :

On lui donne une formule de la logique du premier ordre, on veut savoir si elle est vraie (pb général = indécidable, mais ça peut marcher dans des cas particuliers).

Trouver des contre-exemples ⟸ trouver des modèles finis dans lesquels il y a ce contre-ex.

Il existe un FMF en Haskell extrêmement efficace.

Conditions ternaires :

(condition)?expr1:expr2

: si condition, alors expr1, sinon condition 2.

Pq ? C’est un if, then, else sur des expressions,

Mais attention : par pareil que if then else :

Contre-ex :

e & -e : la plus grande puissance de $2$ divisant e.

int lsb_mask (int n)
{
if (n==0)
return 0; /* false */
else return n & -n;
}

et

(e==0)?0:(e & -e) :

pour n=3, e=n++

lsb_mask(e) (=4) ≠ (e==0)?0:(e & -e) (=6)

NB :

Préprocesseur C : CCP : lit toutes les lignes commençant par #. Exs :

  • #include
    • ex: #include toto.h ⟶ ajoute le contenu de toto.h dans le fichier à cet endroit
  • #define
    • ex: #define chmol 3 : remplace toutes les occurrences de chmol par 3 dans le code
    • #define chmol : remplacé par rien
    • #define chmol IF def ... THEN ... ELSE : pour la portativité ⟶ chmod ne sera pas remplacé par la même chose selon la condition.
      • # define chmol IF def HP_UX THEN ... ELSE : pour contourner un bug qui ne s’observe que sur les ordis HP
    • #define NULL = &void *0 : pointeur NULL
      • attention : segments des processeurs Intel : adresses segmentées
    • #pragma : ne fait rien de compréhensible (le créateur de GNU (Richard Stallman) a râlé ⟶ quand GCC tombe dessus, lance emacs et joue aux tours d’Hanoï dessus) : commandes à sémantique non définie ⟶ spécifiques à chaque compilateur.
    • pour définir des macros : #define SCHMOLL 3 (convention: macros en majuscules)

Appel par nom

#define LSB_MASK(e) ((e)==0)?0:((e)&-(e))

Pq (e) et pas e ?

Pour que dans : LSB_MASK(n++), on ait n++ entre parenthèses.

Attention aux #define :

#define SET(x,e) x=e
SET(y,*p) // y=*p : pas du tout ce qu'on voulait !

#define MUL(x,y) x*y
MUL(2+2,3+3) // 2+2*3+3 : pas du tout ce qu'on voulait !

C’est pourquoi il faut toujours mettre les paramètres entre parenthèses :

#define SET(x,e) (x)=(e)


#define MUL(x,y) (x)*(y)

Appel par référence :

:

⟶ argument évalué à chaque fois qu’il est appelé

Ex :

  • Fortran
  • Pascal
  • C++
void inc(int n){
  n++;
}

int m = 4;
inc(m);
// m = 4 encore

Appel par valeurs :

Paramètre formel n a été incrémenté, mais quand on sort de la fonction, aucun impact sur m.

VS

Appel par référence :

On donne l’adresse de m, pas simplement sa valeur :

EX : en C++ :

void inc(int &n){
  n++;
}

int m = 4;
inc(m);
// m = 5 maintenant, car on a passé son adresse

C’est la fonction appelée qui décide quels sont ses paramètres par valeur/par référence.

ret pointeur vers m m=4
⇓    
ret pointeur vers m m=5

Si on voulait le faire en C quand même :

void inc(int *np){
  (*np)++;
}

int m = 4;
inc(&m);
// m = 5 maintenant, avec l'astuce

NB : Que se passe-t-il quand, en appel par référence, on ne passe pas une variable, mais une expression qu’on peut évaluer :

void inc(int &n){
  n++;
}

int m = 4;
inc(m+0);
// m = ?

ça dépend : en Fortran :

  • dans la théorie (sémantique) : est censé switché en appel par valeur
  • dans la pratique : calcule m+0=m, puis appel par référence : m sera modifié

Le cas de Prolog : aucun de ces modes d’appels !

Ex: concaténation de listes

append ([], L, L).

append ([X | L1], L2, [X | L3]) :-
append (L1, L2, L3)

⇓

append ([1,2], [3], [1,2,3]).
yes

Il résout aussi des équations :

? append ([1,2], [3], X).
yes
X = [1,2,3]

ou encore

? append ([1,2], Y, [1,2,3,4]).
yes
X = [3,4]

Si il y a plusieurs solution : en liste certaines quand à la suite quand on appuie sur “return”.

⟶ pour résoudre équations : utilise algorithme d’unification.

Portée lexicale / Liaison dynamique

Langage à portée lexicale = portée statique :

var = x ⟶ x est la dernière occurrence de x dans le code précédent.

Ex, en OCamL :

let x = 7
let rec f y = x+y;;

let x = 29 in f 3;;
(* retourne : 10*)

NB: les variables x (la locale et la globale) ne sont pas égales : mises sur la pile.

VS :

Langage à liaison dynamique :

var = x ⟶ x la valeur de x au moment on exécute cette instruction.

L’exemple précédent, en Emacs Lisp, retournerait 32, et pas 10 !

NB: la variable x locale écrase la variable globale localement.

“Emacs is all hooks” : toutes les fonctions peuvent être changées.

Ex :

  • surcharge de méthodes, en POO : forme de liaison dynamique “contrôlée” : on sait quelles méthodes a un objet, mais on ne peut connaître leur comportement qu’une fois qu’on a l’objet sous la main (les méthodes peuvent avoir été “surchargées”).

Variables statiques

En C :

static int i = 0;{.C} : grosso modo, une variable globale, mais on ne peut la voir que dans le block dans lequel elle a été définie.

Ex :

int fact(int n){
  if (n==0) return 1;
  return n*fact(n-1);
}

int fact_fast(int n){
  static int save_n = -1, save_fact;
  if (n==save_n)
    return save_fact
  save_n = n;
  return save_fact = fact(n);
}

Mini-mémoïsation (ne retient que la valeur précédente), protège la variable save_n pour que personne d’autre ne la modifie en dehors de notre programme.

NB : Remarquons qu’en C : stdin, stdout sont à liaison dynamique : pratique dans ce contexte.

Leave a comment