recursive polymorphic variants?

recursive polymorphic variants?

[Norman Ramsey]

I'm trying to write a small, extensible interpreter, and I'd like to
use polymorphic variants as the extension mechanism.  But I'm getting
stuck on very simple things.  For example, I would like the value type
to include a few simple values, but I would also like it to be
extensible, thus:

  type value = [ `Nil
               | `Number   of float
               | `String   of string
               | `Function of [>value] list -> [>value]
               | `Table    of ([>value], [>value]) Hashtbl.t
               ]

However, when I do this, the compiler complains that

  The type constructor value is not yet completely defined

Is there some way to define a recursive, *extensible* type using
polymorphic variants?  



Norman

Re: [Caml-list] recursive polymorphic variants?

[Jacques Garrigue]

From: nr@eecs.harvard.edu (Norman Ramsey)

> I'm trying to write a small, extensible interpreter, and I'd like to
> use polymorphic variants as the extension mechanism.  But I'm getting
> stuck on very simple things.  For example, I would like the value type
> to include a few simple values, but I would also like it to be
> extensible, thus:
> 
>   type value = [ `Nil
>                | `Number   of float
>                | `String   of string
>                | `Function of [>value] list -> [>value]
>                | `Table    of ([>value], [>value]) Hashtbl.t
>                ]
> 
> However, when I do this, the compiler complains that
> 
>   The type constructor value is not yet completely defined
> 
> Is there some way to define a recursive, *extensible* type using
> polymorphic variants?  

Have a look at "Private rows: abstracting the unnamed" and
"Code reuse through polymorphic variants" at
http://www.math.nagoya-u.ac.jp/~garrigue/papers/

They both give examples of how to define extensible languages using
polymorphic variants. The first one relies on an experimental feature
only available in the CVS version of ocaml.

Jacques Garrigue

Re: [Caml-list] recursive polymorphic variants?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 2505 bytes --]

On Fri, 2005-08-19 at 06:51 +0900, Jacques Garrigue wrote:
> From: nr@eecs.harvard.edu (Norman Ramsey)
> 
> > I'm trying to write a small, extensible interpreter, and I'd like to
> > use polymorphic variants as the extension mechanism. 

> > Is there some way to define a recursive, *extensible* type using
> > polymorphic variants?  
> 

> "Code reuse through polymorphic variants" at
> http://www.math.nagoya-u.ac.jp/~garrigue/papers/

This paper is good but very skimpy .. :)

Open recursion is used, and types are inferred from functions.
It is possible to use the same techniques to define the
required types explicitly too, basic Felix bound term type
definition uses this:

(** value typing *)
type 't b0typecode_t' = 
  [
  | `BTYP_inst of bid_t * 't list 
  | `BTYP_tuple of 't list         
  | `BTYP_unitsum of int
  | `BTYP_sum of 't list 
  | `BTYP_function of 't * 't
  | `BTYP_pointer  of 't 
  | `BTYP_lvalue  of 't 
  | `BTYP_array of 't * 't 
  | `BTYP_void                       
  | `BTYP_fix of int      
  | `BTYP_var of int     
  ]

(** meta typing *)
type 't b1typecode_t' =
  [
  | `BTYP_apply of 't * 't 
  | `BTYP_typefun of (int * 't) list * 't * 't
  | `BTYP_type
  | `BTYP_type_tuple of 't list
  | `BTYP_type_match of 't * ('t * 't) list
  ]

(** general typing *)
type 't btypecode_t' =
  [
  | 't b0typecode_t'
  | 't b1typecode_t'
  ]

type b0typecode_t = 't b0typecode_t' as 't
type btypecode_t = 't btypecode_t' as 't

Unfortunately, whilst I could use this technique for many terms
other than typecodes, I haven't because it is somewhat clumbsy
to write out terms with all the required added parameters and
then close the recursions. For just one extension over one variable
we have a 1 parameter overhead in the type definitions, and 9 lines
for the closure.

Inference removes the need to write out the types, but it makes
debugging virtually impossible. In addition, type inference isn't
strong enough to deduce the "correct" typing for all expressions,
coercions are sometimes required, and in practice to write them
abbreviations are necessary.

Having warned you .. I would never go back to ordinary variants
after using polymorphic ones: Felix uses them almost exclusively,
and even though I don't use the features heavily, knowing that
it is possible to refine the typing later seems a major software
engineering plus.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] recursive polymorphic variants?

[Jon Harrop]

On Thursday 18 August 2005 22:51, Jacques Garrigue wrote:
> Have a look at "Private rows: abstracting the unnamed" and
> "Code reuse through polymorphic variants" at
> http://www.math.nagoya-u.ac.jp/~garrigue/papers/
>
> They both give examples of how to define extensible languages using
> polymorphic variants. The first one relies on an experimental feature
> only available in the CVS version of ocaml.

Excellent papers, thanks.

Firstly, may I ask if there is an ETA on the release of a new OCaml version 
with this added functionality?

Secondly, I've been playing around with a term-level interpreter for a DSL 
and, in particular, have been looking at including O(n log n) patterns as 
well as a the usual linear patterns. I've done this by supplementing the 
usual list and array containers with a built-in set container based upon the 
one in OCaml's stdlib.

As this is a set of values and a value can be a set, there is an obvious 
recursion. I implemented it by cut and pasting the stdlib code into my own 
and altering it to have mutually recursive "value set" and "value" comparison 
functions.

Would your private row types let me do this without cut and pasting the code? 
I can't see how, but I'm hoping. :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] recursive polymorphic variants?

[Alain Frisch]

Jon Harrop a écrit :
> As this is a set of values and a value can be a set, there is an obvious 
> recursion. I implemented it by cut and pasting the stdlib code into my own 
> and altering it to have mutually recursive "value set" and "value" comparison 
> functions.

Cannot you use recursive modules?

-- Alain