From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <garrigue@math.nagoya-u.ac.jp>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.4 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE 
	autolearn=disabled version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by yquem.inria.fr (Postfix) with ESMTP id BE34CBBAF
	for <caml-list@yquem.inria.fr>; Mon,  1 Jun 2009 06:21:53 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: ApoEAIP0IkqCNhAB/2dsb2JhbADLK4I4gVQF
X-IronPort-AV: E=Sophos;i="4.41,281,1241388000"; 
   d="scan'208";a="40869446"
Received: from kurims.kurims.kyoto-u.ac.jp ([130.54.16.1])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 01 Jun 2009 06:21:52 +0200
Received: from localhost (orion [130.54.16.5])
	by kurims.kurims.kyoto-u.ac.jp (8.13.8/8.13.8) with ESMTP id n514Ld6f010866;
	Mon, 1 Jun 2009 13:21:39 +0900 (JST)
Date: Mon, 01 Jun 2009 13:21:23 +0900 (JST)
Message-Id: <20090601.132123.210988323.garrigue@math.nagoya-u.ac.jp>
To: dave@ramenlabs.com
Cc: darioteixeira@yahoo.com, caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Width subtyping
From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <4A22132E.30505@ramenlabs.com>
References: <380372.47429.qm@web111503.mail.gq1.yahoo.com>
	<4A22132E.30505@ramenlabs.com>
X-Mailer: Mew version 4.2 on Emacs 22.3 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Spam: no; 0.00; subtyping:01 syntax:01 camlp:01 syntax:01 translated:01 ocaml:01 notation:01 runtime:01 ocamlc:01 camlp:01 -pp:01 ocamlc:01 ocaml:01 dynlink:01 cmo:01 

From: Dave Benjamin <dave@ramenlabs.com>

> Heavier in terms of efficiency, or syntax? If you mean the latter, I 
> wonder if a camlp4 syntax extension might help ease the burden; perhaps 
> something like:
> 
>    #{x=5; y=6}
> 
> could be translated to:
> 
>    object method x = 5 method y = 6 end
> 
> and then you could benefit from a lightweight syntax and still get the 
> static type checking.

This is already possible with pa_oo, which you can get from the same
place as pa_polymap:

http://www.math.nagoya-u.ac.jp/~garrigue/code/ocaml.html

Also, concerning the typing of pa_polymap, the "weakness" is intended,
otherwise you wouldn't be able to add new fields to an existing value
(using the with notation).
If you just want to create values without allowing modifications, here
is a modified of pa_polymap.ml which gives them closed types. (It
still needs the original Polymap module.)

Concerning efficiency, since pa_polymap is based on the Map module,
you cannot expect it to be more efficient than the pa_oo based approach,
neither in terms of data size or runtime speed. It only probably wins
for generated code size, as classes are big.

Of course, both are much worse than real records. But whether it
matters or not depends much on what you use them for in your program.

        Jacques Garrigue

(*
   To compile:
     ocamlc -I +camlp4 -c -pp camlp4orf pa_polymap.ml
     ocamlc -c polymap.ml
   To use:
     ocaml dynlink.cma camlp4o.cma pa_polymap.cmo polymap.cmo
   or
     ocamlc -pp 'camlp4o -I . pa_polymap.cmo'
*)

open StdLabels
open Camlp4.PreCast
module Pcaml = Syntax

let next =
  let n = ref 0 in
  fun () -> incr n; string_of_int !n

let add _loc org (s,e) tv =
  <:expr< Polymap.add (Obj.magic `$s$) (Obj.magic ($e$ : $tv$))
            ($org$ : Polymap.t [> `$s$ of $tv$ ]) >>

let test_key_eq =
  let test strm =
    match Stream.npeek 2 strm with
      [(UIDENT _|LIDENT _), _; KEYWORD "=", _] -> ()
    | _ -> raise Stream.Failure
  in
  Gram.Entry.of_parser "test_key_eq" test

let upper_bound _loc e l =
  match l with
    [] -> e
  | s::l ->
     let typ = List.fold_left ~init:<:ctyp< `$s$ of _ >> l
       ~f:(fun t s -> <:ctyp< `$s$ of _ | $t$ >>)
     in <:expr< ($e$ : Polymap.t [< $typ$ ]) >>

EXTEND Pcaml.Gram
  GLOBAL: Pcaml.expr;
  Pcaml.expr: LEVEL "." [
    [ e = SELF; "."; "`"; s = Pcaml.a_ident ->
      let tv = <:ctyp< '$"pm_"^next()$ >> in
      <:expr<
        (Obj.magic
           (Polymap.find (Obj.magic `$s$) ($e$ : Polymap.t [> `$s$ of $tv$ ]))
        : $tv$)
      >> ]
  ];
  Pcaml.expr: LEVEL "simple" [
    [ "`"; "{"; "}" -> <:expr< Polymap.empty >>
    | "`"; "{"; test_key_eq; lel = lbl_expr_list; "}" ->
        let (e, tl) = lel <:expr< Polymap.empty >> in
        upper_bound _loc e tl
    | "`"; "{"; e = Pcaml.expr LEVEL "."; "with"; lel = lbl_expr_list;
      "}" -> fst (lel e) ]
  ];
  lbl_expr_list: [
    [ fields = LIST1 field SEP ";" ->
        let tl = List.map fields ~f:(fun _ -> <:ctyp< '$"pm_"^next()$ >>) in
        fun org ->
          (match fields with
            [s,e] -> add _loc org (s,e) (List.hd tl)
          | _ ->
            List.fold_left2 ~init:org fields tl ~f:(add _loc)),
          List.map fst fields ]
  ];
  field: [[ s = Pcaml.a_ident; "="; e = Pcaml.expr LEVEL "top"  -> (s,e) ]];
END;;