From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jyh@cs.caltech.edu>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.1.3
Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38])
	by yquem.inria.fr (Postfix) with ESMTP id 27143BC0B
	for <caml-list@yquem.inria.fr>; Wed, 27 Dec 2006 20:31:40 +0100 (CET)
Received: from flpvm23.prodigy.net (flpvm23.prodigy.net [207.115.20.53])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id kBRJVcU6030612
	for <caml-list@inria.fr>; Wed, 27 Dec 2006 20:31:39 +0100
X-ORBL: [67.120.175.91]
Received: from [67.120.175.91] (adsl-67-120-175-91.dsl.lsan03.pacbell.net [67.120.175.91])
	by flpvm23.prodigy.net (8.13.8 out.dk.spool/8.13.8) with ESMTP id kBRJVhqM024800;
	Wed, 27 Dec 2006 11:31:44 -0800
Mime-Version: 1.0 (Apple Message framework v752.3)
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
Message-Id: <DD63B67D-4F25-4DDE-8C08-213EED0A9BD7@cs.caltech.edu>
Content-Transfer-Encoding: 7bit
From: Jason Hickey <jyh@cs.caltech.edu>
Subject: Pure visitor patterns
Date: Wed, 27 Dec 2006 11:31:35 -0800
To: caml-list@inria.fr
X-Mailer: Apple Mail (2.752.3)
X-Miltered: at discorde with ID 4592CA1A.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; foo:01 'self:01 foo:01 'self:01 escapes:01 'foo:01 'foo:01 recursive:01 escapes:01 int:01 int:01 parameters:02 scope:03 scope:03 preserve:03 

I've been trying to write pure visitors (visitors that compute without
side-effects).  The main change is that a visitor returns a value.
Here is a (failed) example specification based on having only one kind
of thing "foo".

     class type ['a] visitor =
       object ('self)
         method visit_foo : foo -> 'a
       end

     and foo =
       object ('self)
         method accept : 'a. 'a visitor -> 'a
         method examine : int
       end

This fails because the variable 'a escapes its scope in the method  
accept.
It can be fixed by breaking apart the mutual type definition.

     class type ['a, 'foo] visitor =
       object ('self)
         method visit_foo : 'foo -> 'a
       end

     class type foo =
       object ('self)
         method accept : 'a. ('a, foo) visitor -> 'a
         method examine : int
       end

The second form works, but it is hard to use because of the number
of type parameters needed for the visitor (in general).

Here are my questions:

    - Why does 'a escape its scope in the recursive definition?
    - Is there some other style that would solve this problem?

Thanks!

Jason

P.S. Here is an alternate scheme with non-polymorphic visitors, where
the returned value is just a visitor.  The accept method needs to
preserve the type, so this one also has the "escapes its scope"
problem.

     class type visitor =
       object ('self)
         method visit_foo : foo -> 'self
       end

     and foo =
       object ('self)
         method accept : 'a. (#visitor as 'a) -> 'a
       end
     ...

--
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257