From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <garrigue@math.nagoya-u.ac.jp>
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 89050BB84
	for <caml-list@yquem.inria.fr>; Mon, 15 May 2006 14:40:20 +0200 (CEST)
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 k4FCeIrK032211
	for <caml-list@yquem.inria.fr>; Mon, 15 May 2006 14:40:19 +0200
Received: from localhost (suiren [130.54.16.25])
	by kurims.kurims.kyoto-u.ac.jp (8.13.6/8.13.6) with ESMTP id k4FCeAjc020491;
	Mon, 15 May 2006 21:40:11 +0900 (JST)
Date: Mon, 15 May 2006 21:40:07 +0900 (JST)
Message-Id: <20060515.214007.35474922.garrigue@math.nagoya-u.ac.jp>
To: Charles.Bouillaguet@crans.org
Cc: caml-list@yquem.inria.fr, romain.bardou@wanadoo.fr
Subject: Re: [Caml-list] Recursive Variant problem..
From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <20060515.202355.105436069.garrigue@math.nagoya-u.ac.jp>
References: <A4840FB4-9473-4B6C-8BB3-B10D7AA72B76@crans.org>
	<20060515.202355.105436069.garrigue@math.nagoya-u.ac.jp>
X-Mailer: Mew version 4.2 on Emacs 21.3 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Miltered: at nez-perce with ID 446876B2.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; recursive:01 variants:01 arrays:01 desc:01 polymorphic:01 caml-list:01 graph:01 define:01 jacques:01 jacques:01 int:01 int:01 variant:02 breaks:02 parameter: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.4 required=5.0 tests=DNS_FROM_RFC_ABUSE 
	autolearn=disabled version=3.0.3

> From: Charles Bouillaguet <Charles.Bouillaguet@crans.org>
> > The problem appear when I want to define my values :
> > 
> > type 'sort array_state = 'sort * [`ArrayStateVar of string |  
> > `ArrayWrite of 'me  * 'sort base_value * [`Int] base_value * 'sort  
> > base_value] as 'me
> > and 'sort base_value = 'sort * [`Inert of unit | `FieldRead of  
> > [`Object] base_value * 'sort field | `ArrayRead of 'sort array_state  
> > * ('sort array_) base_value * [`Int] base_value]
> > and 'sort field = 'sort * [`FieldVar of string | `FieldWrite of 'me *  
> > [`Object] base_value * 'sort base_value] as 'me

> The trouble is that the array case takes 'sort as a parameter, meaning
> that we would need an infinity of such duplicates.
> Here is the second problem: by nature, polymorphic variants only allow
> regular types (that can be represented by a regular graph), and your
> definitions do not represent a regular type (you can get ever deeper
> arrays.)

Note that this can be solved by introducing a nominal type (record or
sum type) that breaks the irregular cycles. Here the following is
sufficient.

type 'sort array_state =
    'sort *
    [ `ArrayStateVar of string
    | `ArrayWrite of
        'me  * 'sort base_value * [`Int] base_value * 'sort base_value] as 'me
and 'sort base_value =
    {sort: 'sort; desc:
     [ `Inert of unit
     | `FieldRead of [`Object] base_value * 'sort field
     | `ArrayRead of
        'sort array_state * ('sort array_) base_value * [`Int] base_value]}
and 'sort field =
    'sort *
    [ `FieldVar of string
    | `FieldWrite of 'me *  [`Object] base_value * 'sort base_value] as 'me

Probably this is not you wanted, but just to make things clear.

Jacques Garrigue