From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA08894 for caml-redistribution; Wed, 19 Nov 1997 11:30:02 +0100 (MET)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id JAA05562 for <caml-list@pauillac.inria.fr>; Wed, 19 Nov 1997 09:49:06 +0100 (MET)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.8.7/8.8.5) with ESMTP id JAA09239;
	Wed, 19 Nov 1997 09:49:02 +0100 (MET)
Received: (from remy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA05558; Wed, 19 Nov 1997 09:49:01 +0100 (MET)
Message-Id: <199711190849.JAA05558@pauillac.inria.fr>
Subject: Re: Algorithme de Milner =?us-ascii?Q?=28synth==3Fiso=2D8859=2D1=3FQ=3F=E8=3F=?= se de type)
In-Reply-To: <323_8540_879362618_1@someware> from Jean Charles Gregoire at "Nov 12, 97 02:23:39 pm"
To: gregoire@inrs-telecom.uquebec.ca (Jean Charles Gregoire)
Date: Wed, 19 Nov 1997 09:49:01 +0100 (MET)
Cc: caml-list@inria.fr
From: Didier.Remy@inria.fr (Didier Remy)
Reply-to: Didier.Remy@inria.fr
Organization: INRIA, BP 105, F-78153 Le Chesnay Cedex
Phone: (33) 1 3963 5317 -- Sec: (33) 1 3963 5570 -- Fax: (33) 1 3963 5684
Web: http://pauillac.inria.fr/~remy
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Sender: weis

> Quelqu'un connaîtrait-il une page Web décrivant le principe de l'algorithme
> H-M pour la synthèse de type à la ML ? C'est pour donner une réf. à un
> étudiant 
> qui doit le réaliser.

En annexe de [1], j'ai décrit une implémentation de l'algorithme de Milner, 
et le code Caml-Light correspondant.

Les types sont représentés par des graphes plutôt que des termes afin de
profiter au maximum du partage naturellement crée par l'unification. De plus
ce partage est conservé au cours des opérations de généralisation et
d'instantiation.

L'algorithme résultant a la même complexité que la borne théorique (ce qui
n'est pas le cas des algorithmes habituellement implantés), et se comporte
également très bien en pratique.

La contrepartie est que l'implémentation est un peu alourdie par
l'utilisation de graphes.

        --Didier


[1] @TechReport{Remy!mleth,
author     = "Didier R{\'e}my",
title      = "Extending {ML} Type System with a Sorted
              Equational Theory", 
institution= "Institut National de Recherche en Informatique et Automatisme",
address    = "Rocquencourt, BP 105, 78 153 Le Chesnay Cedex, France",
type       = "Research Report",
number     = 1766,
year       = 1992
}