From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 85D46BB9C for ; Wed, 16 Nov 2005 03:20:08 +0100 (CET) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jAG2K6bJ008438 for ; Wed, 16 Nov 2005 03:20:07 +0100 Received: from localhost (orion [130.54.16.5]) by kurims.kurims.kyoto-u.ac.jp (8.13.1/8.13.1) with ESMTP id jAG2K5vu020908 for ; Wed, 16 Nov 2005 11:20:05 +0900 (JST) Date: Wed, 16 Nov 2005 11:20:05 +0900 (JST) Message-Id: <20051116.112005.68539737.keiko@kurims.kyoto-u.ac.jp> To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Recursive types From: Keiko Nakata In-Reply-To: <20051116.084030.02302710.garrigue@math.nagoya-u.ac.jp> References: <20050506044107.1698.70519.Mailman@yquem.inria.fr> <437A64C1.3000807@cs.jhu.edu> <20051116.084030.02302710.garrigue@math.nagoya-u.ac.jp> X-Mailer: Mew version 4.2 on Emacs 20.7 / Mule 4.1 (AOI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 437A9756.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 recursive:01 recursive:01 checker:01 nodes:01 mutable:01 nodes:01 checker:01 arbitrary:01 functions:01 define:01 cyclic:01 jacques:01 loops:02 caml:02 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 From: Jacques Garrigue > From: Swaroop Sridhar > > > How are arbitrary recursive types implemented in caml? > > No, types are just implemented as (cyclic) graphs. > All functions in the type checker have to be careful about not going > into infinite loops. There are various techniques for that, either > keeping a list/set of visited nodes, or using some mutable fields. I am very interested in this subject. Since 1) I can define type abbreviations almost artitrary, as in type t = < m : t > ; and 2) type abbreviations can have parameters as in type 'a t = < m : 'a > , just keeping a list/set of visited nodes does not seem to be enough, especially for structual types. So I think the type checker does some very clever thing. Regards, Keiko.