Polymorphisme sur des fonctions de toutes signatures

pour un *toy langage*

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut,

Je code en ce moment un langage LISP-like pour tester Parsec. Cependant, je bloque pour l'évaluation des appels de fonction. Actuellement, je fais un lookup sur mon environnement pour récupérer ma fonction grâce à son nom. Le souci c'est que le type des fonctions varie selon leur signature, donc je peux pas stocker dans une structure de donnée plusieurs fonctions tant que leurs signatures sont différentes. Comment pourrai-je stocker ces fonctions dans mon environnement, ou quelle autre "architecture" mon programme pourrait prendre pour pouvoir importer des fonctions de Haskell dans mon langage ?

On m'a conseillé d'utiliser Data.Dynamic mais je n'ai pas trop compris comment l'utiliser malgré des recherches.

PS: (Autre question qui n'a rien à voir) Est-ce correct d'utiliser le même nom pour un constructeur et son argument ? ex:

1
data Value = Int Int | Float Float | String String

Édité par felko

Anciennement AlphaZeta

+1 -0

Je ne comprends pas ce que tu cherches à faire, donc je vais avoir du mal à t'aider sur ta première question. Un exemple précis, avec un bout de code, pourrait aider.

Pour ta deuxième question, c'est non. Int, Float et String sont déjà des constructeurs de valeur, tu ne peux pas les redéfinir.

#JeSuisGrimur #OnVautMieuxQueÇa

+0 -0
Auteur du sujet

Un exemple précis, avec un bout de code, pourrait aider.

Voici les principaux types que j'utilise:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
type Name = String

type Environment = [(Name, Value)]

data Value
    = IntegerV    Integer
    | DoubleV     Double
    | StringV     String
    | ListV       [Value]
    | TupleV      [Value]
    | FunctionV   Function
    | TypeV       Type

data Parameter = Parameter Name Type
data Signature = Signature [Parameter] Type
data Function
    = UserFn    Signature AST.Expr
    | HaskellFn <type>

data Type
    = IntegerT
    | DoubleT
    | StringT
    | ListT Type
    | TupleT [Type]
    | FunctionT Signature
    | TypeT
    deriving Eq

Je voudrais un type tel que je puisse écrire par exemple "HaskellFn (+)" mais aussi "HaskellFn (div)", sachant que (+) et (div) sont de type différent.

Édité par felko

Anciennement AlphaZeta

+0 -0

Cette réponse a aidé l'auteur du sujet

La question du polymorphisme dans la conception d'un langage informatique est une vraie question qui a plusieurs solutions selon les objectifs du créateurs.

En OCaml, nous avons un polymorphisme uniforme ou polymorphisme paramétrique dans le sens où les opérations de la fonction polymorphe sur les valeurs seront toujours les mêmes quelque soit le type. Par exemple, let rec map f = function [] -> [] | x :: r -> f x :: map f r donne le type ('a -> 'b) -> 'a list -> 'b list. Que la liste soit int list ou float list, le traitement restera le même - à savoir l'application de la fonction f sur tout les éléments de la liste.

Au contraire du polymorphisme ad-hoc, nous avons une fonction générique (note bien la différence entre générique et polymorphe) qui accepte des valeurs de tous types mais dont les opérations diffèrent selon le type des valeurs. C'est le cas en C++ par exemple avec une différence notable a OCaml qui est la surcharge des opérateurs comme + qui peut autant s'appliquer à des int qu'à des float ou à d'autres objets plus complexes pour peu qu'on est défini le traitement.

Dans un polymorphisme ad-hoc, une fonction générique à donc plusieurs algorithmes selon le type des valeurs. C'est le cas par exemple du print en Python qui, selon le type, va afficher d'une certaines manières la valeur (un dictionnaire n'apparait pas de la même manière qu'un entier avec cette fonction). Sur la question que tu te poses, tu pars déjà sur un polymorphisme ad-hoc: avoir des fonctions du même nom mais avec une signature différente - et par extension un traitement différent selon le type.

Maintenant, la vraie question que tu te poses, c'est d'implémenter un mécanisme de dispatch lors de l'application de la fonction pour savoir qu'elle algorithme il faut utiliser - ce choix dépendra, comme tu le sais, du type de ton argument. Par exemple, pour l'implémentation d'un print tel que celui de Python, nous pourrions avoir ceci:

1
2
3
4
5
let print = function
  | Int v -> print_int v
  | Float v -> print_float v
  | String v -> print_string v
  | _ -> raise Not_implemented

On a bien un mécanisme de dispatch selon le type de l'argument. Bien entendu, l'extensibilité de la fonction print à d'autres types (comme ceux créé par l'utilisateur) n'est pas possible, on peut alors imaginer ce code modifié tiré de ce document:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
type type_id = string
type val = VInt of int | VFloat of float | VObject of value
type ty = TInt | TFloat | TObject of type_id

let printers =
  ref ([(TInt, (function VInt i -> print_int i | _ -> assert false));
        (TFloat, (function VFloat f -> print_float f | _ -> assert false))]
       : (ty * (value -> unit)) list)

let rec print (ty, value) =
    try let (_, printer) = List.find ((=) ty) !printers in
        printer value
    with Not_found -> raise Not_implemented

Comme tu le constates, tu dois avoir l'information du type de la valeur que tu manipules - ce dernier va pouvoir faire un dispatch recherchant selon le type, le bon printer dans liste. Ici, c'est une liste associative ty * printer mais on peut imaginer une Map avec pour clé ty pour être plus efficient dans la recherche.

On peut rendre ce genre d'algorithme plus général pour l'application d'une fonction. Puisque tu fais un LISP, ça reste de la programmation fonctionnel et on peut décrire les types d'une fonction à l'aide d'un TArrow:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
type ty = TTop | TInt | TFloat | TArrow of (ty * ty)
type value = VTop | ... | VArrow of (value -> value)

let rec ty_eq ty1 ty2 = match ty1, ty2 with
  | TTop, _ | _, TTop -> true
  | ...
  | TArrow (tya, tyb), TArrow (tya', tyb') ->
    ty_eq tya tya' && ty_eq tyb tyb'

let rec eval ?(expected_ty = TTop) environment =
  | Variable name ->
    Env.find name environment : (ty * value) list
    |> List.find (ty_eq expected_ty)
  | Application (f, v) ->
    let (ty_v, v) = eval environment v in
    let (ty_f, f) = eval ~expected_ty:ty_v environment f in
    match f with
    | VArrow f -> f v
    | _ -> raise Is_not_function

Alors plusieurs choses, j'ai enlevé Object pour simplifié le code (ce dernier permettait à ce que l'utilisateur puisse définir ses propres types mais il faudrait implémenter une fonction unlink qui réduirait l'Object à ce qu'il peut être structurellement - et à ce moment, on parle déjà de duck typing comme en Python). Le type Top est la borne supérieur à tout les types (comme le type Object en Java) - en général, on y associe aucuns traitements, et si on est face à une valeur Top, c'est qu'on essaye d'appliquer une fonction à une valeur où nous n'aurions pas trouver une signature/un algorithme correspondant et c'est notamment pour éviter que l'évaluation s'arrête face à ce genre d'erreur. Enfin, Arrow est l'équivalent de l'abstraction en lambda calcul.

Cela reste une implémentation imparfaite mais qui donne une idée général de ce que peut être le polymorphisme ad-hoc. Cependant, il y a plusieurs points à expliquer ici qui ne sont pas forcément facile à comprendre sans recul.

Le premier point, c'est l'obligation de se coltiner le type de nos valeurs tout le long de l'évaluation (et c'est le cas en Python) qui fait qu'à un niveau plus bas, on parle de valeur boxé. Bien entendu, on trouve toujours d'autres moyens comme en C++ avec le name-mangling mais ce qu'il faut dénoter, c'est qu'à vouloir du polymorphisme ad-hoc, on complexifie fortement le runtime pour quelque chose qui, AMHA, reste de l'utilisation occasionnelle.

Ensuite, c'est la gestion des erreurs. Il est difficile de gérer de manière exhaustive toutes les erreurs qui peuvent provenir du polymorphisme ad-hoc (je me souviens des messages d'erreurs de link avec GCC avec l'utilisation de template parce qu'il ne trouver pas tel ou tel méthode dans ma classe). L’inexistence d'une signature d'une fonction peut donc poser des soucis lors de l'évaluation et c'est pour cette raison que j'ai créé le type Top qui rend cette erreur silencieuse d'une certaines manières mais doit on considérer que cette erreur doit arrêter tout le programme ou non ? C'est encore une question ouverte.

La finalité, c'est qu'au travers de tout ces inconvénients, j'ai une préférence pour un système de type statique comme celui d'OCaml ou Haskell mais où l'implémentation est certainement un peu plus complexe au niveau du compilateur mais où l'overhead est inexistant au niveau du runtime. C'est pour cette raison que j'ai fait une présentation au début du polymorphisme paramétrique comme une autre solution.

Cette réponse a aidé l'auteur du sujet

Une solution en première approximation serait de paramétrer ton type Function, ainsi que les types Value et Environment qui en dépendent. Tu aurais ainsi la définition suivante.

1
2
3
data Function a
    = UserFn    Signature AST.Expr
    | HaskellFn a

Je viens de faire l'essai, il n'y a aucune difficulté à faire HaskellFn (+) et HaskellFn (&&). La limite à cela, c'est que tu ne pourras pas faire de liste de Function a dont le a est différent. Par exemple [HaskellFn (+), HaskellFn (&&)] ne passera pas.

Maintenant, si tu as besoin de quelque chose de plus solide, ça va commencer à devenir compliqué.

#JeSuisGrimur #OnVautMieuxQueÇa

+1 -0
Auteur du sujet

Merci Dinausaure pour tes explications.

Comme tu le constates, tu dois avoir l'information du type de la valeur que tu manipules

Oui, j'ai une fonction qui s'en charge.

Arrow est l'équivalent de l'abstraction en lambda calcul.

Le souci c'est que dans ta définition de TArrow et de VArrow, les fonctions n'acceptent qu'un seul argument de ce que j'ai compris (je ne fais pas d'OCaml, promis je m'y met un jour).

La limite à cela, c'est que tu ne pourras pas faire de liste de Function a dont le a est différent

Du coup on peut pas les mettre dans l'environnement :/

Je vais approfondir mes recherches sur Data.Dynamic, c'est la seule piste que j'ai pour l'instant.

Pour ta deuxième question, c'est non. Int, Float et String sont déjà des constructeurs de valeur, tu ne peux pas les redéfinir.

Le fait est que ça marche (parce que Int, Float, etc… ne sont pas des constructeurs mais des types), ma question était surtout pour les conventions :euh:

Anciennement AlphaZeta

+0 -0

Cette réponse a aidé l'auteur du sujet

Le souci c'est que dans ta définition de TArrow et de VArrow, les fonctions n'acceptent qu'un seul argument de ce que j'ai compris (je ne fais pas d'OCaml, promis je m'y met un jour).

Alors je me souviens plus de l'associativité de -> mais une fonction tel que int -> int -> int peut être vu de cette manière (int -> int) -> int et donc Arrow (Arrow (Int, Int), Int) ce qui permet d'ailleurs de faire de la curryfication ;) !

Auteur du sujet

Salut,

J'ai enfin réussi à faire marcher tout ça, c'est un peu long pour faire des bindings depuis Haskell mais ça marche bien :p

Ça m'a quand même l'air d'être plus propre que d'utiliser du "boilerplate" comme avec Dynamic.

Merci beaucoup Dinosaure et Dominus Carnufex

Anciennement AlphaZeta

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte