Accueil > Enseignement > Anciens cours (avant 2015-2016) > Programmation fonctionnelle (L3, 2013-2014) > Semaine 1 — Premiers pas en Caml

Semaine 1 — Premiers pas en Caml

jeudi 16 janvier 2014, par Pierre

Premières prise de contact avec le langage et le REPL. Typage. Types de base, listes, tuples, fonctions, correspondance de motifs (pattern-matching). Pour que les fonctions soient des objets de première classe il faut associer à chaque fonction non seulement son code mais aussi son contexte (sa clôture). Illustration de cette nécessité des clôtures par ce dont son absence nous prive, avec un exemple en langage C.

(* Premier cours de caml *)
(* ocaml + emacs + tuareg mode *)

(* operations sur les entiers *)
1 + 2;; (* taper ctrl-c ctrl-e pour evaluer dans le repl *)
1 - 2;;
1 / 2;;
1 * 2;;

(* sur les float *)
1. +. 2.;;
1. -. 2.;;
1. /. 2.;;
2. *. 3.;;

(* les noms *)
let toto = 2 * 3;;
let x = 5;;
let y = x + 3;;
let x = 4;;
(* portee limitee des noms *)
let x = 0 in x + 1;;
x + 1;;

(* les fonctions *)
let triple = function x -> 3 * x;;
triple 2;;
let quadruple x = 4 * x;;
quadruple 1;;
let addition x y = x + y;;
let addition2 = function x -> function y -> x + y;;
let addition3 = fun x y -> x + y;;
let increment = function x -> x + 1;;

(* fonction qui retourne une fonction *)
let increment2 = addition 1;;
increment2 4;;
(addition 3) 4;;

(* fonction qui prend en argument une fonction *)
let appliquera2 = function f -> f 2;;
let triple = function x -> 3 * x;;
appliquera2 triple;;
(* expression a valeur de fonction *)
appliquera2 (function x -> x + 1);;
(function x -> x + 1) 3;;

(* les listes et les tuples *)
[3; 4];; (* liste de deux elements 3 et 4 *)
[];;    (* liste vide *)
[1, 2];; (* erreur courante *)
("salut", 2, 1.1);; (* un tuple *)
(* ["salut"; 2; 1.1];; (* une erreur *) *)
3::(4::(5::[]));; (* meme chose que [3; 4; 5] *)


(* exercices : reimplementer la bibliotheque des listes *)
let estVide = function  [] -> true
                      | _ -> false;;

estVide [];;
estVide ["salut"];;
exception ListeVide;;
let tete = function [] -> raise ListeVide
                  | x::xs -> x;;
tete [];;
tete ["salut"; "koly"];;
let rec taille = function [] -> 0
                        | x::xs -> 1 + taille(xs);;
taille [];;
taille [3; 2];;
let queue = function [] -> raise ListeVide
                  | x::xs -> xs;;
queue [];;
queue [1;2;3];;

let rec nieme = function
    (1, x::xs) -> x
  | (n, l) -> nieme (n-1, queue l);;
nieme(2,  [8; 800; 10; 80]);;
nieme(0,  [8; 800; 10; 80]);;
nieme(10, [8; 800; 08; 80]);;
nieme(10, []);;

let rec dernier = function
    [] -> raise ListeVide
  | x::[] -> x
  | x::xs -> dernier xs;;
dernier ["salut"; "c'est toi"; "le"; "chat"];;

let rec renverser = function
    [] -> []
  | x::xs -> (renverser xs)@[x];;

(* @ effectue la concatenation on peut aussi definir la concatenation *)
renverser ["bien"; "trop"; "c'est"];;

let rec concatener = function
    ([], l) -> l
  | (x::xs, l) -> x::concatener(xs, l) ;;

#trace concatener;;
concatener ([1; 2], [3]);;
concatener ([], []);;

(*
definir la fonction map.
Exemple map f [a; b; c; d] = [f a; f b; f c; f d]
*)
let rec map = function (f, []) -> []
            | (f, x::xs) -> f x :: map(f, xs);;

let successeur = function x -> x + 1;;
map (successeur, [1; 3; 5]);; (* [2; 4; 6] *)
map (successeur, []);;        (* [] *)
map (estVide, [[]; [3; 4]]);; (* [true; false] *)

#include <stdlib.h>
#include <stdio.h>


/* type des fonction N -> N */
typedef int (*nat2nat) (int);

/* quelques fonctions N -> N */
int triple(int x) {
  return 3*x;
}
int successeur(int x) {
  return x + 1;
}

/* fonction passee en parametre OK */
int appliquera2(nat2nat f) {
  return f(2);
}

/* fonction comme valeur de retour: FAIL */
nat2nat ajouteur(int n) {
/* s'il y avait des clotures n serait alloue sur le tas et non
   (seulement) sur la pile pour survivre a l'invalidation du cadre
   courant */
  int f(int x) {
    return x + n;
  }
  return f;
}

void garbage() {
  int t[1024];
  int i;
  for (i = 0; i < 1024; i += 1) {
    t[i] = 0;
  }
}

int main() {
  nat2nat f;

  f = ajouteur(100);
  garbage(); /* ecrase les anciens cadres sur la pile */
  printf("%d\n", f(2));

  return EXIT_SUCCESS;
}

Semaine 1 — Premiers pas en Caml

Portfolio