Trampoline

Fonctionne pour n’importe quelle fonction

Exemple : mutuellement récursif

// On implémente le trampoline une fois pour toute
sealed trait State[A]
case class Stop[A](resultat: A)           extends State[A]
case class Next[A](thunk: () => State[A]) extends State[A]

def trampoline[A](init_state: State[A]): A = {
	var state: State[A] = init_state
	while (state.isInstanceOf[Next[A]]) {
		state = state.asInstanceOf[Next[A]].thunk()
	}
	state.asInstanceOf[Stop[A]].result
}

// Exemple avec de la récursivité mutuelle

/* Dans tout les cas, les fontions even et odd terminent directement, 
 * soit avec un Stop, soit avec un Next. */

def even(n: Int): State[Boolean] = {
	if n == 0 {
		Stop(true)
	} else {
		Next(() => odd(n - 1)) // notre thunk
	}
}

def odd(n: Int): State[Boolean] = {
	if n == 0 {
		Stop(false)
	} else {
		Next(() => even(n - 1)) // notre thunk
	}
}

trampoline(even(200)) // => Renvois Stop(true)

// Un even + transparent vis-à-vis de son fonctionnement
def even_rec(n: Int): Boolean = trampoline(even(n)).isInstanceOf(Stop[Boolean].result)

En OCaml

type 'a state =
  | Stop of 'a
  | Next of (unit -> 'a state)

let rec trampoline = function
  | Next thunk -> trampoline (thunk ())
  | Stop x -> x
;;

(*define some functions which use them *)
let rec fact_norec n acc =
  if n == 0 then Stop acc else Next (fun () -> fact_norec (n - 1) (n * acc))
;;

let rec even n = if n = 0 then Stop true else Next (fun () -> odd (n - 1))
and odd n = if n = 0 then Stop false else Next (fun () -> even (n - 1))

Examen de 2024

Notes de cours autorisées 💃💃
On voit en détail treelist.fx pour coder le type Some.

On peut coder les expressions en assignant chaque expression (Var, Num, Sum, Prod) à une valeur (0, 1, 2, 3) et ensuite les traduire en Fopix.

• Ret/PushCont à préciser

Réponse de l’exo 4 : Oui, mais l’approche est moins générale que la CPS donc le niveau d’optimisation est plus basse (CPS est meilleure).

Exceptions

Probablement à l’examen cette année

Arrêter l’exécution du programme et faire quelque chose de différent, comme les kontinuations.
\RA simuler les exceptions avec les kontinuations

• Une fonction termine soit avec K(resultat) soit avec Ke(mon_exception)
• try ... catch \RA PushCont(ke)

Cf. les notes de cours.

“Devoir”

Correction de TailRec.md la semaine prochaine.