• Environnements
• Fonctionnalité
• Application de fonction
• Récursivité
• Traits impératifs
  • Mémoire, références
  • Exceptions
  
  
• Correction de programmes

1

Renaud.Rioboo@lip6.fr

• true -_E-> true,
• 1 -_E-> 1,
• (if true then 1 else 2) -_E-> 1

2

que l'on utilise souvent dans une fonction ou pour pour éviter des re-calculs

• En portée dynamique la valeur d'un identificateur se trouve dans l'environnement global (interprétation, langages de shell)
  
  

  let x = 1	E=ë(x=1)<|Eû
  let f =
  function y -> x + y	E=ë(f=F)<|Eû
  f 1	2
  let x = 2	E=ë(x=2)<|Eû
  f 1	3

• En portée statique (ou lexicale) la valeur d'un identificateur se trouve dans l'environnement de définition (compilation)
  
  

  let x = 1	E1=ë(x=1)<|E0û
  let f =
  function y -> x + y	E2=ë(f=F)<|E1û
  f 1	2
  let x = `a`	E3=ë(x=`a`)<|E2û
  f 1	2

• E_u, session utilisateur en cours,
• E_m, les modules ouverts
• E_b, la base.

• un fichier .zo de code et
• un fichier .zi d'interface obtenu à partir d'un fichier de description d'interface .mli.

• une fonction load (: string -> unit) qui permet de charger un module source (.ml) en mémoire.
• une fonction load_object (: string -> unit) qui permet de charger un module source (.zo) en mémoire.

• un nom de variable, c'est le paramètre formel (nom),
• une expression définissant la valeur de la fonction en tout point que l'on nomme le corps de la fonction (corps),
• un environnement de définition de la fonction (Env) :

• les expressions en lettres calligraphiques ( E) ou sous forme de pseudo code (expr)
• les valeurs ou les environnements en notation mathématique (V ou E)

let deux = (print_string "1+1" ; 1 + 1) in
  deux + deux ;;

1. liaison de deux à
   (print_string "1+1" ; 1 + 1)
   puis évaluation de deux + deux
2. substitution de deux à sa ``valeur'' soit :

   (print_string "1+1" ; 1 + 1) +
   (print_string "1+1" ; 1 + 1)
   

3. affichage de "1+1" calcul de 1 + 1 = 2
4. affichage de "1+1" calcul de 1 + 1 = 2
5. calcul de 2 + 2 = 4

let deux = (print_string "1+1" ; 1 + 1) in
  deux + deux ;;

1. calcul de la valeur de
   (print_string "1+1" ; 1 + 1)
2. affichage de "1+1" retour de 2
3. liaison de deux à sa valeur 2
4. calcul de deux + deux soit 2+2
5. retour de 4

• Définitive : on modifie l'environnement global
  let x = 1 ;;
  1. évaluation de 1.
  2. enrichissement de l'environnement global de la liaison de x à 1
     E=ë(x=1)<|Eû
  
  
• Temporaire : on créée un nouvel environnement pour évaluer une expression (portée lexicale) :
  let x = 1 in x+1;;
  1. évaluation de 1.
  2. création d'un nouvel environnement contenant la liaison de x à 1
     E₁=ë(x=1)<|Eû
  3. évaluation de x+1 dans E₁
  L'environnement global n'est pas modifié !

type fonctions_booleennes = Fbool of bool -> bool ;;

let vrai = Fbool (function x -> true)
and faux = Fbool (function x -> false);;

let ou = function f1 -> function f2 ->
  match (f1,f2) with
   ((Fbool f1), (Fbool f2)) -> 
      Fbool (function x -> (f1 x) || (f2 x)) ;;

let applique = function f1 -> 
  match f1 with 
    Fbool f1 -> function x -> f1 x ;;

let est_vrai = ou vrai vrai ;;

applique est_vrai true = applique vrai true ;;
applique est_vrai false = applique vrai false;;

est_vrai = vrai;;

type point = {abs : int ; ord : int} ;;
let ({abs = x ; ord = y} as un_point) = 
  {abs = 10 ; ord = 20 } ;;

• x : int = 10,
• y : int = 20 et
• un_point : point = {abs = 10 ; ord = 20}

let (a,b) = (1,2,3) in a+b ;;
let (a,1) = (1,2) in a+1 ;;

let projection_verticale = function a_point -> 
  match a_point with
    {abs = x ; ord = y} ->
      if (y = 0) then a_point
      else {abs = x ; ord = 0};;

let abscisse = function un_point ->
  match un_point 
    with {abs = x ; ord = _} -> x ;;

• évaluer l'expression en position fonctionnelle,
• évaluer l'expression en position d'argument,
• augmenter l'environnement de définition de la fermeture de la liaison entre le paramètre formel et le paramètre effectif pour évaluer le corps de la fermeture.

• let foo = function (x,y) -> E(x,y)
  
  L'expression n'a qu'un seul argument qui est le couple (x,y) et foo a pour type s_x*s_y ® s _E
  
  Sa valeur est une fermeture F₁=«x,y:-> E(x,y),E»
  
  
• let foo = function x -> function y -> E(x,y)
  
  L'expression est une fonction curryfiée et foo a pour type s_x®s_y ® s _E.
  
  Sa valeur est une fermeture F₂=«x:-> E_x,E»
  
  où E_x est l'expression function y -> E(x,y).

• F₁ et F₂ n'ont pas le même type,
• On évalue F₂ en liant x et y en même temps,
• F₁ et F₂ ne sont pas équivalentes.

let incremente_compteur = let compteur = ref(0) in
    function n -> 
      begin
      compteur := !compteur + n ;
      !compteur
      end ;;

• Les F_i sont des motifs lexicaux qui introduisent de nouveau noms. Ils permettent de produire un environnement d'exécution de la clause.
• Les E_i sont des expressions qui constituent le corps de la clause, elles sont évaluées dans l'environnement de définition de la fonction augmenté des liaisons produites pendant le filtrage.
• Chaque clause de filtrage |  F_i ® E_i va :
  • permettre de sélectionner un sous-ensemble de valeurs du type s_v
    que doit avoir V.
  • permettre de produire un environnement dans lequel va s'évaluer l'expression E_i qui définit le corps de la clause comme dans :
    
    let F_i = V in E_i exécuté dans un environnement E tel que ( V -_E-> V).
    On notera E_i les liaisons produites pendant ce filtrage E_i Å E l'environnement obtenu après avoir augmenté E de ces liaisons.

let rec fib = function n -> match n with
  | 0 -> 0
  | 1 -> 1
  | _ -> fib(n-1) + fib(n-2) ;;

• Soit E_fib l'environnement de définition de fib et E l'environnement courant.
• Évaluation de fib(3) dans E :
  F_fib(3) puisque fib -_E-> F_fib et 3 -_E-> 3. On évalue E₃ =fib(n-1) + fib(n-2) dans E₃ =ë(n=3)<|E_fibû, évaluation de fib(2) dans E₃ en suspens et :
  • évaluation de fib(1) dans E₃ soit l'évaluation de F_fib(1) qui vaut 1. Donc fib(1) -_E3-> 1
  • reprise de l'évaluation de fib(2) dans E₃ :
    évaluation de F_fib(2) puisque fib -_E3-> F_fib et 2 -_E3-> 2
    On doit évaluer E₂ = fib(n-1) + fib(n-2)
    dans E₂ = ë(n=2)<|E_fibû :
    • évaluation de fib(0) dans E₂ soit 0
    • évaluation de fib(1) dans E₂ soit 1
  • Donc E₂ -_E2-> 1
  
  
• et enfin E₃ -_E3-> 2

• constructeurs de valeurs du type foo :
  • une constante C : foo
  • deux fonctions
    • C1 : t1 -> foo
    • C2 : t2 -> foo
      qui allouent de nouvelles valeurs du type foo
• motifs lexicaux de filtrage des valeurs de type foo :
  • un motif C qui filtre cette valeur,
  • deux motifs C1 _ et C2 _ qui filtrent les autres.
    qui n'allouent pas mais introduisent des noms

type somme_formelle =
 | Variable
 | Entier of int
 | Somme of somme_formelle * somme_formelle ;;

let rec eval = function (expr, valeur) -> 
  | (Variable , _ ) -> valeur
  | (Entier n , _ ) -> n
  | (Somme (e1,e2) , _ ) -> 
      eval(e1,valeur) + eval(e2,valeur) ;;

let rec somme = function l -> match l with
  | [] -> 0
  | h::r -> h + (somme r) ;;

let rec somme_abs =
  function zero -> function plus -> function l ->
    match l with
      | [] -> zero
      | h::r -> 
        (plus h (somme_abs zero plus r)) ;;

let somme = function l -> somme_abs 0 (prefix +) l;;

let somme = somme_abs 0 (prefix +) ;;
let mult = somme_abs 1 (prefix *) ;;

let rec foo = function n -> match n with
  | 0 -> 2
  | _ -> foo(n-1) + n;;

let rec foo_bis = 
  function n -> function res -> match n with
    | 0 -> res
    | _ -> foo_bis (n-1) (res + n);;

let rec foo = function arg ->
  if (arg = arg_0)
  then val_0
  else op(foo(g(arg)), f(arg));;

let rec foo = function (arg,accu)
  if (arg = arg_0)
  then op(accu,val_0)
  else foo(g(arg) , op(accu, f(arg)));;

let rec pow = function a -> function n ->
  if ((n mod 2) = 0) 
  then
    if (n = 0) 
      then 1 
      else
        let res = pow a (n / 2) in res * res
  else
    if (n = 1) 
    then a 
    else
      let res = pow a (n / 2) in a * res * res ;;

let rec dich = fun zero un op a n ->
  if ((n mod 2) = 0) then
    if (n = 0) 
    then zero 
    else
      let res = dich zero un op a (n/2) in 
        op res res
  else
    if (n = 1) 
    then un 
    else
      let res = dich zero un op a (n/2) in 
        op a (op res res) ;;

• 4 si l'ordre d'évaluation est foo puis E₁ puis E₂ ou bien
• 2 l'ordre d'évaluation est si E₂ puis E₁ puis foo

exception Foo ;; 
exception Bar of int;;

let to_foo = function an_exn -> match an_exn with
  | Bar _ -> Foo
  | an_exn -> an_exn ;;

let v = 1 in
  try (let v = 2 in raise Foo) 
  with
   | Foo -> v 
;;

• Si l'évaluation de E dans E ne déclenche pas d'exception c'est une valeur V (de type s_v) qui est le résultat.
• Sinon, soit I l'exception déclenchée, le résultat de l'évaluation est alors le même que celui de
  match I with | F ® E_I
  
  dans l'environnement E.

let foo = function x -> 
  try (x+1) with 
    | Foo -> -1
;;
foo (raise Foo);;

• rajoute une nouvelle référence dans l'environnement,
• crée une entrée associée à cette valeur dans la mémoire.

• un nouvel environnement E' =ë(r=v_r)<|Eû
  où v_r est une nouvelle valeur telle que r -_E'-> v_r
• un nouvel état mémoire M'=é(v_r¬v)<|Mù.

• on consulte le contenu de v_r par !r et on note M|>v_r
• l'instruction r := v' ne modifie pas l'environnement courant E mais affecte la mémoire courante M : é(M|>v_r)¬v'ù où v' -_E-> v'

let foo = 
  let c = ref 0 in
    function () -> 
      begin c := !c + 1 ; !c end ;;

let foo = function () ->
  let c = ref 0 in 
  begin c := !c + 1 ; !c end ;;

let i = "i" ;;
for i = 1 to 9 
do 
  begin 
    print_int i ;
    print_newline() ; 
    i 
  end 
done ;;
i;;

let fact = function n ->
  let res = ref 1 in
    begin
    for i = 1 to n do
      res := !res * i
    done ; 
    !res
    end;;

let rec fact = function
  | 0 -> 1
  | n -> n * (fact (n-1));;

let fact = 
  let rec f_r = fun r n ->
    match n with
      | 0 -> r
      | _ -> f_r (n*r) (n-1)
  in 
   function n -> f_r 1 n;;

let fib = function n ->
  let f_0 = ref(0) 
  and f_1 = ref(1) 
  and temp = ref(0) in
    begin
    for i = 1 to n do
      temp := !f_0;
      f_0 := !f_1;
      f_1 := !temp + !f_1
    done;
    !f_0
    end ;;

let fib =
  let rec f_r = function
    | 0 -> (0, 1)
    | n -> 
      let (f_0,f_1) = 
          f_r(n - 1)
      in (f_1, f_0 + f_1)
  in fun n -> fst(f_r n) ;;

• Terminaison de fonctions récursives

  let rec ack = function n -> function m ->
    if (n = 0) 
    then 
      m + 1 
    else
      if (m = 0)
      then 
        ack (n - 1) 1
      else 
        ack (n - 1) (ack n (m - 1)) ;;
  

• Démonstration de propriétés

  let min_list = function l -> match l with
    | [] -> failwith "Liste vide"
    | h::t -> it_list min h t ;;
  

  Équivalent à

  let min_list = 
    let rec aux = function m -> function
      | [] -> m
      | h::t ->
        if (h < m)
        then aux h t
        else aux m t
    in 
      function l -> match l with 
        | [] -> failwith "Liste vide"
        | h::t -> aux h t ;;
  

type arbre_bin = 
  | Feuille of int
  | Noeud of (arbre_bin * arbre_bin) ;;

let rec it_arbre = fun op -> function arbre -> 
  match arbre with
    | Feuille n -> n
    | Noeud (fg,fd) -> 
      op (it_arbre op fg) (it_arbre op fd) ;;

• l'arbre est une feuille et
  it_arbre(F, Feuillen) vaut n
• on suppose que A₁ et A₂ sont des arbre_bin tels que :
  • it_arbre(F , A₁) = a₁
  • it_arbre(F,A₂) = a₂
  La valeur de it_arbre(F,Noeud(A₁,A₂)) est alors F(a₁,a₂).

let rec append = function l ->
  match l with
    | [] -> function l -> l
    | h::t -> function l -> h::(append t l) ;;

• si l₁ est vide, appendl₁(appendl₂l₃) = appendl₂l₃ et append(appendl₁l₂)l₃ = appendl₂l₃
  
  
• sinon l₁ = h₁::l₁' et

  appendl1(appendl2l3)	=	h1::(appendl1'(appendl2l3))
  append(appendl1l2)l3	=	append(h1::(appendl1'l2))l3
  	=	h1::(append(appendl1'l2)l3)

let rec gcd = function n -> function m ->
  if (m = 0)
  then n
  else gcd m (n mod m) ;;

• supposons m < n.
  • Si m=0 le résultat est correct.
  • Sinon on a 0 £ (nmodm) < m et nmodm < m
    et le couple (n,m) décroît strictement pour l'ordre produit.
  
  
• si m ³ n alors m < (nmodm)³ et on utilise le point précédent.

3

sauf si m=n=0 mais le résultat reste correct

Ce document a été traduit de L^AT_EX par H^EV^EA.