Re: Jai: Language for game programmming

Dans la série liens intéressants et instructifs : Demystifying Type Classes sur le site de Oleg Kiselyov. D'une manière générale, son site est une véritable mine d'or ! :-)

Sur cette page, il y explique de manière didactique et complète le principe des type classes en étudiant trois implémentations possibles du système dans un langage : par passage de dictionnaire, par monomorphisation ou par analyse intentionnelle de type. La première étant la plus répandue et les deux secondes étant issues de l'article pionnier sur le sujet : Parametric overloading in polymorphic programming languages de Stephan Kaes en 1988 (un lien vers cet article est donné en bas de page).

On y trouve aussi une comparaison avec des techniques du C++, comme il le souligne en conclusion :

We have presented the intensional type analysis, the third way of compiling type classes. Whereas monomorphization is akin to C++ template instantiation and dictionary passing is similar to vtable, the intensional type analysis reminds one of resolving overloading by a large switch statement.

Traduction rapide :

Nous avons présenté l'analyse intentionnelle de type, la troisième façon de compiler les classes de type. Tandis que la monomorphisation est similaire à l'instantiation de template C++ et le passage de dictionnaire est similaire aux vtable, l'analyse intentionnelle de type fait penser à la résolution de surcharge comme à un grand switch.

La dernière technique m'a donné une idée un peu différente de la sienne, mais largement inspirée de son illustration en OCaml, en utilisant des types sommes ouverts et des GADT. Exemple avec la fonction show :

(* on définit un type somme ouvert dans lequel on peut rajouter des cas après coup *)
type 'a showable = ..
(* on définit la fonction show pour ce type encore vide *)
let show : type a. a showable -> a -> string =
 fun _ x -> failwith "failed overloading resolution";;
val show : 'a showable -> 'a -> string = <fun>
(* on rajoute des cas dans le type avec leur instance pour show *)
type 'a showable += Int : int showable;;
type 'a showable += Int : int showable
let show : type a. a showable -> a -> string = function
 | Int -> string_of_int
 | ty -> show ty;;
val show : 'a showable -> 'a -> string = <fun>
type 'a showable += Bool : bool showable;;
type 'a showable += Bool : bool showable
let show : type a. a showable -> a -> string = function
 | Bool -> string_of_bool
 | ty -> show ty;;
val show : 'a showable -> 'a -> string = <fun>
type 'a showable += List : 'a showable -> 'a list showable;;
type 'a showable += List : 'a showable -> 'a list showable
let show : type a. a showable -> a -> string = function
 | List ty ->
 fun l ->
 let rec loop first = function
 | [] -> "]"
 | h::t -> 
 (if first then "" else ", ") ^ show ty h ^ loop false t
 in "[" ^ loop true xs
 | ty -> show ty;;
val show : 'a showable -> 'a -> string = <fun>
(* quelques exemples *)
show Int 1;;
- : string = "1"
show Bool true;;
- : string = "true"
show (List Int) [1; 2; 3];;
- : string = "[1, 2, 3]"
(* limitations du système *)
(* on définit une fonction print sur les showable *)
let print ty x = print_endline (show ty x);;
val print : 'a showable -> 'a -> unit = <fun>
(* cela marche bien... pour l'instant *)
print Int 1;;
1
- : unit = ()
print (List Int) [1; 2; 3];;
[1, 2, 3]
- : unit = ()
(* maintenant on rajoute les float mais sans implémentation pour show *)
type 'a showable += Float : float showable;;
type 'a showable += Float : float showable
(* la c'est normal, dans le grand switch le cas Float n'est pas encore géré *)
print (Float) 1.2;;
Exception: Failure "failed overloading resolution".
(* on rajoute le cas au switch *)
let show : type a. a showable -> a -> string = function
 | Float -> string_of_float
 | t -> show t;;
val show : 'a showable -> 'a -> string = <fun>
show Float 1.2;;
- : string = "1.2"
(* et là : pouf, ça marche pas pour print !!! *)
print (Float) 1.2;;
Exception: Failure "failed overloading resolution".
(* la raison en est que en OCaml lorsque l'on définit un terme,
 * sa définition ne doit dépendre que des termes déjà défini qui le précèdent
 * et donc rajouter un cas à show après avoir défini print ne change rien à son code :
 * il faut la redéfinir à chaque fois que l'on rajoute une instance :-/ *)
let print ty x = print_endline (show ty x);;
val print : 'a showable -> 'a -> unit = <fun>
print Float 1.2;;
1.2
- : unit = ()
(* au final cette implémentation n'est pas compatible avec la programmation
 * modulaire et les avantages des compilations séparées. *)

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.