From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 621E6BC88 for ; Tue, 1 Feb 2005 08:23:58 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j117NvBp002227 for ; Tue, 1 Feb 2005 08:23:58 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id IAA19326 for ; Tue, 1 Feb 2005 08:23:57 +0100 (MET) Received: from postfix3-1.free.fr (postfix3-1.free.fr [213.228.0.44]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j117NvoG008806 for ; Tue, 1 Feb 2005 08:23:57 +0100 Received: from warp (chateaudeau-4-82-225-176-25.fbx.proxad.net [82.225.176.25]) by postfix3-1.free.fr (Postfix) with SMTP id 134E11734D4; Tue, 1 Feb 2005 08:23:57 +0100 (CET) Message-ID: <002001c5082f$39f6fc20$19b0e152@warp> From: "Nicolas Cannasse" To: "Philippe Fremy" , References: <41FF1305.30308@inseal.com> Subject: Re: [Caml-list] type inference for python Date: Tue, 1 Feb 2005 08:25:37 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2800.1437 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1441 X-Miltered: at concorde with ID 41FF2E8D.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 41FF2E8D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; cannasse:01 warplayer:01 caml-list:01 inference:01 inference:01 ocaml:01 def:01 def:01 subtyping:01 subtyping:01 polymorphism:01 ocaml:01 variants:01 overriding:01 cannasse:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: > Hi, > > I would like to implement something similar to the type inference of > ocaml for the python language. I have always found it very impressive > (although I have only used caml light). > > I have no experience with the topic, it is just a project that seems > cool to me :-) > > Do you have any hints or where I could build up my knowledge (code, > books, article, ...) to do that kind of thing. > > I imagine that it works in a kind of three way pass: > > 1. analyse all the constraints of the code > Ex: > def f(a): a.append(1) > def g(a): a=a+1; f(a) > g('coucou') > > => a must support append > => a must also be an int > > 2. cross-validate the constraints consistency > => inconsistent assertions > > 3. validate the constraints against reality > => g('coucou') will not work In fact, the ML style type inference can be done in only one pass, at first your variables are monomorphic then they're unified witht the first type they match, creating linkages between types if needed. However in an OO system such as Python, you need more than core ML type inference. You will need some kind of structural subtyping, and subtyping is known to be tricky when used together with polymorphism. There is several kind of subtyping algorithms possible, using constraints is one of them (see work of François Pottier on this). I used another approach based on ocaml polymorphic variants typing scheme (somehow reversed) to implement this feature in MTypes, but it still have a lot of implementation holes difficult to handle. Also, the Python standard library must be designed with dynamic typing in mind (several types possible for arguments, variable number of arguments, operator overriding.....). It's possible to rely on a dynamicly typed library but you'll have to constraint the types a little more and add primitives so users can access different kinds of features which are not usable anymore. Good luck, Nicolas Cannasse