gmanzone(at)irif.fr
Repo
Annale

But : écrire un compilateur en Fopix vers une JVM.

transfo
Déroulé des cours :

Projet en Scala.

hexedit pour voir le code générer.
javap -c -v File.class pour voir le code générer d’une façon lisible.

Instructions bytecode

xmachin_noù n est compris entre 0 et 5 (c’est une optimisation).
Quand on utilise des références, on remplace le xmachin par amachin

CAN : http://www.classfileanalyzer.javaseiten.de/

Cours Scala

AST Fopix

Executer le code du projet

Dans SBT (recommandé)

$ sbt

# Ensuite on compile
$ compile

# Ensuite on lance le fichier
$ run exemples/test.fx

Lancer directement le test

Prend + de temps

$ sbt "run exemples/test.fx"

Traduction directe

Fopix \ra Javix (\subseteq JVM)

Arguments

On va faire la passation d’arguments à la mano, sans utiliser les arguments spécifiques de la JVM.

Par exemple :

args

Avant de faire le saut vers le corps de la fonction f, il faut sauvegarder les variables utilisées dans la pile.

Après le retour de la fonction :

Attention au sommet de la pile : mettre le résultat de la fonction.

Il faudra utiliser DISPATCH : tableswitch permettant de sauter à une étiquette.

Exemple

def min(x, y) = if x < y then x else y

val a = 1
val b = min(a, 3)
val _ = print_int(b + a)

Code :

  iconst_1 # a  = 1
  istore 0 # v0 = 1

# Appel à min 
  iload 0
  sipush 1000
  iload 0  # 
  iconst_3 # v0 = a 
  istore 1 # v1 = 3
  istore 0 #
  goto min_body

min_body:
  iload 0
  iload 1
  if_cmpge ifelse
  iload 0 # Positif
  goto ifexit
ifelse:
  iload 1 # Négatif
ifexit:
  swap
  goto dispatch
ret_min: # Retour de la fonction retour, on doit renvoyer la valeur
  swap
  istore 0
# End call min
  istore 1
  iload 1
  iload 0
  iaobl
  "print_int"
  return

Rappel :

graph TD
  Fopix --> ANF
  ANF --> Kontix
  Kontix --> Javix

Kontix

f(x_{1}, \dots, x_{n}) \underset{\text{Kontix}}{\implies} f(K, \text{Env}, x_{1,} \dots, x_{n})

main Kontix -> début du programme Javix

Au début

Compilation

En général

programme

\RA Permet d’estimer une taille précise de la taille de la pile

Le If

Le if basique

Comme dans Javix, rien de spécial, 2 étiquettes if_else et if_exit.

Le if(comp, TailExpr, TailExpr)

Si la condition est vraie, alors on continue avec l’expression récursive terminale, donc on ne revient jamais en arrière
Si la condition est fausse, on a une autre expression récursive terminale, alors on ne revient pas en arrière.

Donc vu qu’on ne revient jamais en arrière, pas besoin d’étiquette if_exit.

Exemple : if(b) call(f) else call(g).

if((comp_op, be1, be2), te1, te2)
compil(be1)
compil(be2)
ificmp_invop label_if_else
compil(te1)
label_if_else:
compile(te2)

Let/Blet : Let/BLet(id, e1, e2)

Compiler(e1)
; Générer une variable associée à l'id
; Mettre dans cette variable le résultat
Compiler(e2)

Appel de fonction : Call(be, [a0, ..., an]

be : basic expression
[a_{0}, \dots, a_{n}] un ensemble de variables

Appel direct be = Fun f

Exemple f(1, 3) : Call(Fun f, [Num(1), Num(3)]

; Il faut calculer les arguments a de 0 à n.
; Puis on AStore
AStore(n+2)
; ...
AStore(2)
Goto f_body ; étiquette qui traduit le K de la fonction f

Appel indirect be n’est pas un Fun, c’est une expression + compliquée

; Calcul de be
; Il faut calculer les arguments a de 0 à n.
; Puis on AStore
IStore(n+2)
; ...
AStore(2)
Goto dispatch

Appel à Kontinuation : Call(K, [be]) = Ret(be)

be est l’argument de la kontinuation.

ALoad(0) ; v0 = Kontinuation courante
Calcul(be)
AStore 2 ; résultat de be
Goto dispatch

dispatch

Push : PushCont(cont, ids, e)

let E = [K, E, eds] in
 let K = cont in e

Push taille len(ids) + 2 ; 2 : 1 pour k et 1 pour e
ANewArray ; création du tableau
; Maintenant on écrit dedans les nouvelles valeurs
E[0] <- v0
E[1] <- v1
E[2] <- les autres variables "ids"
AStore 1 ; on met l'adresse du tableau E sur la pile
; Il faut laisser au sommet de la pile l'adresse de la kontinuation correspondante
Push 'adresse'
IStore 0

Def : DefCont(cont, [x, y, z], res, expr)

def kont(e, res) =
     let [K, E, x, y, z] = e in
     expr

label_kont:
 ; extraire l'environnement e
 ; v1 = (kont, env, variables)
 v0 <- v1[0] ; on change de Kontinuation
 v3 <- v1[2] ; x
 v4 <- v1[3] ; y
 v5 <- v1[4] ; z
 v1 <- v1[1] ; env, qu'il faut faire à la fin pour pas perdre les variables, car on écrit dans v1

Trampoline

trampo

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.

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

exeptions-kontinuations

Cf. les notes de cours.

“Devoir”

Correction de TailRec.md la semaine prochaine.