Seance 1 — Bases du langage

1.1 Le Lambda-calcul

1.1.1 Reduction beta

(* Exemple : (λx. x + 1) 3 ⟶ 3 + 1 = 4 *)

(* La reduction est deterministic : il existe un seul resultat normal *)

1.2 Codage de Church

Le codage de Church encode les donnees et les operations dans le lambda-calcul pur, sans primitives exposees.

1.2.1 Booleens de Church

true  = λx. λy. x     (* choisit le premier argument *)
false = λx. λy. y     (* choisit le deuxieme argument *)
if b then t else f = b t f

1.2.2 Entiers naturels de Church

&bar;0; = &lambda>f. λx. x
&bar;1; = &lambda>f. λx. f x
&bar;2; = &lambda>f. λx. f (f x)
&bar;3; = &lambda)f. λx. f (f (f x))

(* Successeur : *)
succ = λn. λf. λx. f (n f x)

(* Addition : *)
add = λm. λn. λf. λx. m f (n f x)

(* Multiplication : *)
mul = λm. λn. λf. λx. m (n f) x

1.2.3 Paires

pair  = λa. λb. λf. f a b
fst   = λp. p (λa. λb. a)
snd   = λp. p (λa. λb. b)

1.2.4 Listes (fold-right)

nil    = λc. λn. n
cons   = λh. λt. λc. λn. c h (t c n)
isnil  = λl. l (λh. λt. false) true

1.3 Le langage OCaml

1.3.1 Types de base

Type	Exemples	Description
int	0, 42, -7	Entiers (precision machine)
float	3.14, -0.5	Flottants (IEEE 754)
bool	true, false	Booleens
char	'a', 'Z'	Caracteres
string	"bonjour"	Chaines de caracteres
unit	()	Type a unique valeur

1.3.2 Liaison et recursivite

let x = 42 in x + 1      (* liaison locale *)

let rec factorielle n =
  if n = 0 then 1
  else n * factorielle (n - 1)

let rec fib n =
  if n <= 1 then n
  else fib (n - 1) + fib (n - 2)

(* Pattern matching *)
let signe x =
  match x with
  | x when x > 0 -> "positif"
  | x when x < 0 -> "negatif"
  | _ -> "nul"

1.3.3 Fonctions d'ordre superieur

(* Application partielle *)
let add5 = (+) 5
(* add5 3 = 8 *)

(* Fonction anonyme *)
let carres = List.map (fun x -> x * x) [1; 2; 3; 4]

(* Composition *)
let compose f g x = f (g x)

(* Application partielle sur deux arguments *)
let add a b = a + b
let add10 = add 10    (* add10 5 = 15 *)

1.3.4 Operateurs binaires

(* Operations arithmetiques *)
(+)   (-)   (*)   (/)   (mod)
(+.)  (-.)  (*.)  (/.)

(* Operations sur les chaines *)
(^)   (* concatenation *)

(* Comparaisons *)
(=)   (<>)   (<)   (>)   (<=)   (>=)

(* Logiques *)
(&&)  (||)  not

1.4 Application — Calcul numerique

1.4.1 Approximation de pi

(* Serie de Leibniz : pi/4 = 1 - 1/3 + 1/5 - 1/7 + ... *)
let rec somme_series n =
  if n = 0 then 0.0
  else
    let k = float (2 * n - 1) in
    ((-1.0) ** (n + 1 |> float)) /. k +. somme_series (n - 1)

let pi_approx n = 4.0 *. somme_series n

1.4.2 Derivees numeriques

(* Difference centree : f'(x) ~ (f(x+h) - f(x-h)) / 2h *)
let derivee f x =
  let h = 1e-8 in
  (f (x +. h) -. f (x -. h)) /. (2.0 *. h)

(* Exemple : derivee de x^2 en x=3 = 6.0 *)
let () = Printf.printf "%.4f\n" (derivee (fun x -> x *. x) 3.0)

1.4.3 Integrales numeriques

(* Methode des trapezes : integrale de f sur [a,b] *)
let integrale f a b n =
  let dx = (b -. a) /. float n in
  let rec aux i acc =
    if i >= n then acc
    else
      let x = a +. float i *. dx in
      aux (i + 1) (acc +. (f x +. f (x +. dx)) *. dx /. 2.0)
  in aux 0 0.0

(* Exemple : integrale de x^2 sur [0,1] ~ 1/3 *)

1.4.4 Systeme logistique

let rec iterations r x n =
  if n = 0 then [x]
  else
    let x' = r *. x *. (1.0 -. x) in
    x :: iterations r x' (n - 1)

let logistique r x0 n =
  List.rev (iterations r x0 n)

(* Bifurcation : tracer logistique r x0 100 pour r = 2.5 a 4.0 *)