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

1

Renaud.Rioboo@lip6.fr

2

que l'on utilise souvent dans une fonction ou pour pour éviter des recalculs

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

  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

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

• 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) :

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. modification de l'env global
     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
     E₁ = ë (x=1) <| E û
  3. évaluation de x+1 dans E₁
  L'environnement global n'est pas modifié !

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

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

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

let abscisse = function {abs = x} -> x ;;

type fonctions_booleenes = 
  Fbool of bool -> bool ;;

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

let ou = 
  function (Fbool f1) -> 
    function (Fbool f2) ->
      Fbool (function x -> (f1 x) || (f2 x))

let applique = 
  function 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;;

• 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
  
  
• 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 ~> «y ~>  E(x,y) , E₁ » , E₂ »
  On peut l'appliquer à une valeur x₀. C'est une application partielle, le résultat est une fonction :
  
  F_x0=  «y ~>  E(x,y) , ë (x=x₀) <| E₂ û » qui a pour type s_y ® s_E

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

• Les F_i sont des motifs lexicaux.
• Les E_i sont des expressions qui 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 l'argument 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

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

• Soit E_fib l'environnement de définition de fib.
• fib(3) Þ évaluation de
  E₃ = fib(n-1) + fib(n-2)
  dans E₃ =  ë (n=3) <| E_fib û,
  calcul de fib(2) en suspens et :
  1. calcul de fib(1) soit 1
  2. reprise du calcul de fib(2)Þ
     E₂ =  fib(n-1) + fib(n-2)
     dans E₂ =  ë (n=2) <| E_fib û Þ
     1. calcul de fib(0) soit 0
     2. puis de fib(1) soit 1
  3. La valeur de E₂ dans E₂ est donc 1,
• on en déduit la valeur de E₃ dans E₃ soit 2.

• constructeurs de valeurs du type foo :
  • une constante C : foo
  • deux fonctions
    • C1 : t1 -> foo et
    • C2 : t2 -> 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.
  
  On peut ensuite travailler par filtrage :

  let foo = function
    | C -> 0
    | C1 0 -> 1
    | C1 x -> x
    | C2 _ -> 2
  

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

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

eval(Somme(Variable,Entier 2) , 4)

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

let rec somme_abs = 
  function zero -> function plus -> 
    function
      | [] -> 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
  | 0 -> 0
  | n -> foo(n-1) + n

let rec foo_bis = function
  | (0,res) -> res
  | (n,r_p) -> foo((n-1) , r_p + 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)

let foo = fun x y -> !x + !y ;;

let essai = ref 0 in 
  foo 
    (essai := 1 ; essai) 
    (essai := 2 ; essai);;

exception Foo ;; exception Bar of int;;

let to_foo = function
  | Bar _ -> Foo
  | x -> x
;;

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.

• on consulte le contenu de r par !r : M |> v_r
• l'instruction r := v' ne modifie pas l'environnement courant mais affecte la mémoire : é (M|> v_r)¬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 print_int i 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 fact_a = 
    function r -> function
      | 0 -> r
      | n -> fac_a (n*r) (n-1)
  in function n -> fact_a 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 fib_aux = function
    | 0 -> (0, 1)
    | n -> 
      let (f_0,f_1) = 
          fib_aux(n - 1)
      in (f_1, f_0 + f_1)
  in function n -> fst(fib_aux n)       

• Terminaison de fonctions récursives

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

• Correction de programmes

  let min_list = function
    | [] -> 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
      | [] -> 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
  | Feuille n -> n
  | Noeud (fg,fd) -> 
     op (it_arbre op fg) (it_arbre op fd)

• l'arbre est une feuille et
  it_arbre(F,Feuille n) vaut n
• on suppose que it_arbre(F , A₁) et it_arbre(F,A₂) valent a₁ et a₂. La valeur de it_arbre(F,Noeud (A₁,A₂)) est alors F(a₁,a₂).

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

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

  append l1 (append l2 l3) =

  h1::(append l1' (append l2 l3))

  append (append l1 l2) l3 =

  append (h1::(append l1' l2)) l3 =

  h1::(append (append l1' l2) l3 )

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

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

• Si d divise n et m alors n = d n' et m = d m' et on a :
  n mod m = d n' mod d m' = d(n' mod m')
• et d divise n mod m.

3

sauf si m=n=0

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