[Caml-list] polymorphic variant typing question

[Caml-list] polymorphic variant typing question

[skaller]

Consider this:

type ('x, 'a) regexp_t' =
  [
  | `REGEXP_char of int
  | `REGEXP_seq of 'x * 'x (** concatenation *)
  | `REGEXP_alt of 'x * 'x (** alternation *)
  | `REGEXP_aster of 'x (** Kleene closure *)
  | `REGEXP_epsilon (** epsilon: null string *)
  | `REGEXP_code of 'a (** associated code *)
  ] 

type 'a regexp_t = ('x, 'a) regexp_t' as 'x


(* extend the regexp type -- polymorpic variants are wonderful! *)
type 'a gre_t = [ 
  | ('b,'a) regexp_t' 
  | `REGEXP_group of 'b
  ] as 'b
;;

type 'b gcode = [`User of 'b | `Left of int | `Right of int ]
;;

let groupify (re: 'a gre_t) : 'a gcode regexp_t =
  let counter = ref 0 in
  let rec aux (re: 'a gre_t) : 'a gcode regexp_t = match re with
  | `REGEXP_group a ->
    let n = !counter in incr counter;
    let a = aux a in
    seq (seq (code (`Left n)) a) (code (`Right n))
    
  | `REGEXP_code a -> `REGEXP_code (`User a)
  | `REGEXP_alt (a,b) -> 
    let a = aux a in
    let b = aux b in
    `REGEXP_alt (a,b)

  | `REGEXP_seq (a,b) -> 
    let a = aux a in
    let b = aux b in
    `REGEXP_alt (a,b)
  
  | `REGEXP_aster a -> `REGEXP_aster (aux a)
  | `REGEXP_epsilon -> `REGEXP_epsilon
  | `REGEXP_char c -> `REGEXP_char c
  in 
    aux re

What this does is extend the regular expression
type to allow a group combinator, but then reduce it
by using left/right bracket codes. This typing
compiles.

Question: how can I replace the last two lines of
the match with something which just handles 'all the
rest of the cases'?

Those cases are invariant, but a coercion

  | (x : 'a gre_t ) -> ( x : 'a gre_t :> 'a gcode regexp_t)

doesn't work because in general, 'a gre_t isn't a subtype
of 'a gcode regexp_t. I need to reduce the type functor
from gre_t to regexp_t, and 'a to 'a gcode.

Do I have to factor the original regexp_t into invariant
and variant parts??

[BTW: the typing of all this is awesome!]

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] polymorphic variant typing question

[Damien]

On 11 Sep 2004 17:49:25 +1000 skaller wrote:

> Consider this:
> [...]
> What this does is extend the regular expression
> type to allow a group combinator, but then reduce it
> by using left/right bracket codes. This typing
> compiles.
> 
> Question: how can I replace the last two lines of
> the match with something which just handles 'all the
> rest of the cases'?
>
> Do I have to factor the original regexp_t into invariant
> and variant parts??
I think yes...

I often use the following scheme :

<<
(* invariant type *)
type t  = [ `A | `B ]

(*** first level ***)
type 'x v1 = [ t | `C of 'x ]
type t1 = 'x v1 as 'x

(* open recursion with r *)
let r1 r = function
  | #t as x -> x
  | `C x -> `C (r x)

(* close the recursion for use at the first level *)
let rec f1: t1 -> t1 = fun x -> r1 f1 x



(*** second level ***)
type 'x v2 = [ 'x v1 | `D of 'x ]
type t2 = 'x v2 as 'x

(* open recursion (use the previous open recursion) *)
let r2 r = function
(*  | `C x -> `D (r x)   (* possible overriding of the `C case *) *)
  | #v1 as x1 -> r1 r x1
  | `D x -> `D (r x)

(* close the recursion at the second level *)
let rec f2: t2 -> t2 = fun x -> r2 f2 x



(* second to first level (similar to your groupify function) *)
let r21 r = function
  | #v1 as x1 -> r1 r x1 (* first level recursion *)
  | `D x -> `C (r x) (* convert GROUPS into brackets here... *)
let rec f21: t2 -> t1 = fun x -> r21 f21 x
>>

You may be interested by this paper from Jacques Garrigue :
<http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/papers/variant-reuse.pdf>

Hope this helps,
damien


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners