From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <swaroop.sridhar@gmail.com>
X-Original-To: caml-list@yquem.inria.fr
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 ED0D2BB9C
	for <caml-list@yquem.inria.fr>; Thu, 17 Nov 2005 00:56:39 +0100 (CET)
Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.194])
	by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAGNuc9E001729
	for <caml-list@yquem.inria.fr>; Thu, 17 Nov 2005 00:56:39 +0100
Received: by xproxy.gmail.com with SMTP id i27so2229258wxd
        for <caml-list@yquem.inria.fr>; Wed, 16 Nov 2005 15:56:38 -0800 (PST)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
        s=beta; d=gmail.com;
        h=received:message-id:date:reply-to:user-agent:x-accept-language:mime-version:to:subject:references:in-reply-to:content-type:content-transfer-encoding:from;
        b=e4tWUibPdvKBSfc8gIeQvCCDQiAIT8b2ikdiSLOr9I0tKGlECk7axWQxZd05XTZRluDyX5fmUQKEHV9aJNj8qLxsXKx/1I+LC/1bcoAJthYwX5hdpnbGk8H+26GaZvOX0jfadlk34CEA3lG+On/7u00wXt95SupId2nvn0ZpKvE=
Received: by 10.70.50.4 with SMTP id x4mr2261267wxx;
        Wed, 16 Nov 2005 15:56:38 -0800 (PST)
Received: from ?192.168.1.2? ( [68.33.49.160])
        by mx.gmail.com with ESMTP id i14sm16550wxd.2005.11.16.15.56.33;
        Wed, 16 Nov 2005 15:56:36 -0800 (PST)
Message-ID: <437BC73D.1010002@cs.jhu.edu>
Date: Wed, 16 Nov 2005 18:56:45 -0500
Reply-To: swaroop@cs.jhu.edu
User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716)
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>,
	caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Recursive types
References: <437A64C1.3000807@cs.jhu.edu>	<20051116.084030.02302710.garrigue@math.nagoya-u.ac.jp>	<437AA762.5060909@cs.jhu.edu>	<20051116.173802.68165704.garrigue@math.nagoya-u.ac.jp> <437BBA00.3090505@cs.jhu.edu>
In-Reply-To: <437BBA00.3090505@cs.jhu.edu>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
From: Swaroop Sridhar <swaroop.sridhar@gmail.com>
X-Miltered: at concorde with ID 437BC736.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; caml-list:01 recursive:01 unify:01 unification:01 tvar:01 tvar:01 unify:01 unification:01 integer:01 integer:01 termination:01 match:02 match:02 types:02 types: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=RCVD_BY_IP autolearn=disabled 
	version=3.0.3

A (small) correction, I forgot to write the base case that will allow 
for termination:

> 
> Unify (first:TYPE, second: TYPE)
>    will return true on Unification false if not.
> 
> 1. Start
> 2. let t1 = repr first
>    let t2 = repr second

   2.5  if t1 equals t2
	   return true
> 
> 3. match (t1.kind, t2.kind) with
> 
>    case (Integer, Integer) ->
>            return true
> 
>    case (Tvar, _ )  ->
>            t1.link = Some t2
>            return true
> 
>    case (_, Tvar) ->
>            t2.link = Some t1
>            return true
> 
>    case (Record, Record) ->
> 
>            if the record lengths don't match
>               return false
> 
>         t1.link = t2  (***** linked speculatively *****)
> 
>            for each i in 0 to t1.components.size()
>               Unify (t1.components[i], t2.components[i])
>               if Unification fails,
>             t1.link = None
>             unlink all types that were linked until now
>             return false
>           endif
> 
>            for each i in 0 to t1.typeArgs.size()
>               Unify (t1.typeArgs[i], t2.typeArgs[i])
>               if Unification fails,
>             unlink all types that were linked until now
>             return false
>           endif
> 
>        return true
> 
>    case (_, _)  ->
>            return false
> 
> 4. Stop

Swaroop.