From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.6.10/8.6.6) id PAA28244 for caml-redistribution; Thu, 1 Feb 1996 15:04:17 +0100
Received: (from weis@localhost) by pauillac.inria.fr (8.6.10/8.6.6) id PAA28184; Thu, 1 Feb 1996 15:03:42 +0100
From: Pierre Weis <weis@pauillac.inria.fr>
Message-Id: <199602011403.PAA28184@pauillac.inria.fr>
Subject: Re: Fonction polymorphe
To: canon@poly.polytechnique.fr (Hubert Canon)
Date: Thu, 1 Feb 1996 15:03:42 +0100 (MET)
Cc: caml-list@pauillac.inria.fr
In-Reply-To: <199601241847.TAA02621@poly.polytechnique.fr> from "Hubert Canon" at Jan 24, 96 07:47:22 pm
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: weis


> Un bug probable de caml-light : j'ai une fonction qui devrait etre
> polymorphe, mais elle change de type au premier appel :
> 
> Avec caml light 7beta2 (le code n'est pas de moi) :
> 
> #let permutations =
>   let rec permut fixe = fun
>     [] [] -> [fixe] |
>     debut [] -> [] |
>     debut (x :: suite) -> (permut (fixe @ [x]) []
>                                   (debut @ suite)) @
>                           (permut fixe (debut @ [x]) suite)
>   in
>   permut [] [];;
> 
> - : permutations : '_a list -> '_a list list = <fun>

[English at the end of the message]

Ce n'est pas un bug du compilateur: la re'ponse est parfaitement
conforme a` la the'orie. Comme cela a de'ja` e'te' explique' dans
cette tribune (dont vous pouvez consulter l'historique sur
http://pauillac.inria.fr/), c'est un proble`me de typage du
polymorphisme: seule les fonctions, constantes et identificateurs
peuvent recevoir un type polymorphe; or votre phrase est la
de'finition d'une valeur qui n'est pas syntaxiquement une fonction,
mais une expression ``let .. in ...''; cette expression n'est donc pas
ge'ne'ralise'e (ne rec,oit pas un type polymorphe), ce qui est normal.

Pour re'parer, il suffit de rendre explicite pour le compilateur que
``permutations'' est une fonction en ajoutant un argument explicite:

#let permutations l =
  let rec permut ...
  in
  permut [] [] l;;
permutations : 'a list -> 'a list list = <fun>

Constatez que l'expression interne est ge'ne'ralisable, donc polymorphe:

#let rec permut fixe = fun
    [] [] -> [fixe] |
    debut [] -> [] |
    debut (x :: suite) -> (permut (fixe @ [x]) []
                                  (debut @ suite)) @
                          (permut fixe (debut @ [x]) suite)
;;
permut : 'a list -> 'a list -> 'a list -> 'a list list = <fun>

Rappelez-vous aussi que '_a signifie: un type ``a'' inconnu, a`
de'terminer par la suite (a` la manie`r d'une variable dans une
e'quation mathe'matique). Ce qui explique que ``a'' rec,oive une
valeur par la suite. Ces inconnues sont utiles, par exemple pour des
cre'er des re'f'erences:
#let l = ref [];;
l : '_a list ref = ref []

La premie`re affectation de l fixera le type re'el de l:

#l := 1 :: !l;;
- : unit = ()
#l;;
- : int list ref = ref [1]


[English]
This is not a bug but a feature. As explained earlier in this
mailing-list (that you may read via the server
http://pauillac.inria.fr/caml), this is due to the treatment of
polymorphism: only functions, constants, and variables may receive a
polymorphic type scheme; since your phrase defines a value that is not
(syntactically) a function but a ``let ... in ...'' expression, this
expression is not polymorphic.

To get a polymorphic type for permutations, you need to add an
explicit argument:
#let permutations l =
  let rec permut fixe = fun
  ...
  in
  permut [] [] l;;
permutations : 'a list -> 'a list list = <fun>

Remember that '_a means an unknown type named ``a'', to be fixed in
the sequel of the program (similarly to an unknown in mathematical
equations). Thta's why ``a'' is determined by the rest of your
program. These unknowns are useful for instance to define references:

#let l = ref [];;
l : '_a list ref = ref []

The first assigment to l fixes the intended type of l:

#l := 1 :: !l;;
- : unit = ()
#l;;
- : int list ref = ref [1]

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis