Discussion :

[grusgrus]

Bonjour,
je débute avec la programmation fonctionnelle.
Je voudrais comprendre comment OCaml fait pour déterminer le type de l'expression suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
# let h x y z =(x y)(y z);;
val h : (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>

J'ai essayé de contruire l'arbre, mais sans succès.
Merci d'avance.

[gorgonite]

la détermination se fait par inférence... en gros, on démarre avec tous les types alpha, beta, gamme, etc, et on propage des contraintes

en pratique,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
let h x y z =(x y)(y z);;

tu vois que h est une fonction avec trois arguments x y z, on aura donc un début de ce style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
x = alpha_x
y = alpha_y
z = alpha_z
h = alpha_x -> alpha-y -> alpha_z -> alpha_resH

on remarque que x est appliquée à y... donc x est une fonction prenant en argument y et renvoyant alpha_resX

idem y est appliquée à z... donc z est une fonction prenant en argument y et renvoyant alpha_resY

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
y = alpha_z -> alpha_resY
x = alpha_y -> alpha_resX = (alpha_z -> alpha_resY) -> alpha_resX
z = alpha_z
h = alpha_x -> alpha-y -> alpha_z -> alpha_resH 
  = ((alpha_z -> alpha_resY) -> alpha_resX) -> (alpha_z -> alpha_resY) ->  alpha_z -> alpha_resH

on voit ensuite que x y est appliquée à y z, et le calcul est fini...
donc on a

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
alpha_resX = alpha_resY -> alpha_resH
y = alpha_z -> alpha_resY
x = alpha_y -> alpha_resX
  = (alpha_z -> alpha_resY) -> (alpha_resY -> alpha_resH)
z = alpha_z
h = alpha_x -> alpha-y -> alpha_z -> alpha_resH
  = ((alpha_z -> alpha_resY) -> alpha_resY -> alpha_resH) -> (alpha_z -> alpha_resY) ->  alpha_z -> alpha_resH

on renomme dans l'ordre d'apparition

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

h = (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

si tu veux des liens :

http://en.wikipedia.org/wiki/Type_inference

[grusgrus]

Merci pour ton aide, j'ai enfin compris !!!

[SpiceGuid]

En tant que programmeur fonctionnel il est toujours plus intéressant de questionner le pourquoi plutôt que le comment.
En particulier ce qui t'aide à corriger tes programmes ce n'est pas comment il ne peut pas inférer un type correct mais pourquoi il ne peut pas.
Et la réponse à cette question figure, en grande partie, dans la Partie II de mon tutoriel, où il faut chercher toutes les occureences des mots Règle d'inférence.

[Garulfo]

En tant que programmeur fonctionnel il est toujours plus intéressant de questionner le pourquoi plutôt que le comment.
En particulier ce qui t'aide à corriger tes programmes ce n'est pas comment il ne peut pas inférer un type correct mais pourquoi il ne peut pas.[...]

Oui enfin, tu m'expliqueras comment on peut faire pour savoir « pourquoi il ne peut pas » sans savoir « comment il fait pour inférer ».

[SpiceGuid]

Il s'agit d'une auto-promotion.
Mais ça me paraissait quand même une référence utile sur l'inférence de type en OCaml, et à laquelle j'aimerais bien connaître un équivalent (officiel si possible).