Re: Dans l'art voluptueuse de ne rien comprendre

Je ne comprend pas ce que tu veux dire par là.

Prenons par exemple un langage très simple de fonctions sur les entiers, qui prennent un certain nombre d'arguments, et retournent un certain nombre de valeurs. Le type est alors simplement le couple d'entiers (nbr_entrees, nbr_sorties). On peut imaginer des fonctions polymorphes, comme id, qui est de type (n,n) quelque soit le n.

Comme on demande du code, voilà un AST classique (sans construction qui utilise des fonctions) :

type expr = Id | Fonction of int * int * string | Compose of expr * expr ;;
let exemple = Compose (Id, Fonction (2,3,"une fonction"));;

Tu peux décider que pour des raisons quelconques la seule chose qui t'intéresse, c'est le type de l'expression, dans ce cas, si on met de côté le cas de Id, on peut écrire la chose suivante :

type expr_type = int * int;;
let fonction i j nom = (i,j);;
let compose (i,j) (k,l) = if j = k then (i,l) else failwith "erreur";;
let exemple = compose id (fonction 2 3 "une fonction");;

On a toujours un langage intégré, mais au lieu de construire l'AST puis donner sa sémantique, on traite directement la sémantique. Maintenant, pour traiter le cas de id ... On a un petit problème, parce qu'on ne peut pas déterminer directement son type sans regarder autour ! Mais on peut enrichir la sémantique, pour ne pas inclure simplement le type de l'expression, mais plutôt un moyen de la calculer ...

L'exemple est assez chiant, mais en faisant un truc moche et peu efficace on a le code suivant :

type variable = int (* les variables de types sont identifiées à des entiers *)
type semantique = {
 equations : equation list;
 nbr_input : variable;
 nbr_output : variable
};;
let new_variable () = ... ;; (* crée un nouvel identifiant unique *)
let id = 
 let v = new_variable () in 
 { equations = []; nbr_input = v; nbr_output = v };;
let compose f g = 
 { equations = egalite_variable f.nbr_output g.nbr_input :: (f.equations @ g.equations) ; nbr_input = f.nbr_input; nbr_output = g.nbr_output };;
let fonction i j nom = 
 let vin = new_variable () in 
 let vout = new_variable () in 
 { equations = [ egalite_entier vin i ; egalite_entier vout j ] ; nbr_input = vin; nbr_output = vout};;

On part du principe que à partir des équations obtenues, on sait résoudre pour déterminer les valeurs des variables, et donc le type total de l'expression. Ici c'est assez simple à traiter.

Il faut remarquer que si on écrit une fonction qui prend l'AST et qui doit retourner un type, il faudra quand même traiter le cas de Id tout seul ... Et donc on soit on échoue sur certains arbres, soit on utilise aussi un type de retour plus riche.

On constate aussi qu'il n'y a pas d'allocations liées à l'AST, en fait, si le compilateur inline tout, on a juste les calculs de construction de sémantique (incompressibles à priori, vu que c'est ce qu'on veut calculer).

La construction présentée plus tard permet (enfin, c'est ce que j'ai compris) de conserver une certaine capacité à pouvoir être inliné, à être tail-récursif, tout en permettant d'avoir plusieurs interprétations sans avoir à changer le code de tous les constructeurs.