From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <ocaml@optimojoe.com>
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83])
	by yquem.inria.fr (Postfix) with ESMTP id 29F2EBC57
	for <caml-list@yquem.inria.fr>; Wed,  3 Mar 2010 18:11:35 +0100 (CET)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AhQCAGsnjktCbwQZkWdsb2JhbACbBRcBAQkLCgcTBB7AcwWEfA
X-IronPort-AV: E=Sophos;i="4.49,574,1262559600"; 
   d="scan'208";a="45855282"
Received: from out1.smtp.messagingengine.com ([66.111.4.25])
  by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 03 Mar 2010 18:11:34 +0100
Received: from compute1.internal (compute1.internal [10.202.2.41])
	by gateway1.messagingengine.com (Postfix) with ESMTP id DD26AE2BFF
	for <caml-list@inria.fr>; Wed,  3 Mar 2010 12:11:33 -0500 (EST)
Received: from web6.messagingengine.com ([10.202.2.215])
  by compute1.internal (MEProxy); Wed, 03 Mar 2010 12:11:33 -0500
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=messagingengine.com; h=message-id:from:to:mime-version:content-transfer-encoding:content-type:subject:date; s=smtpout; bh=mf7eZLXcUV7iSJRVo0JKxyFW+90=; b=KMHI/BbB6UlUkFS0pOYiuiFVBYp7U9PNKrzUus9pEAtCZ2GDpOK6gBSJZdlWip9VSua+H/ZTqSaoWarjHw5UIrKgw92Qch5EF/RqtJTSxIJqxjPDNzA8YYcvWW1FEcFzBeA8CPmOPh/Hch8tVEWO78R2qQnOaPBRLwZA86g9hiY=
Received: by web6.messagingengine.com (Postfix, from userid 99)
	id BE708110E84; Wed,  3 Mar 2010 12:11:33 -0500 (EST)
Message-Id: <1267636293.17362.1362924937@webmail.messagingengine.com>
X-Sasl-Enc: hJ1CYVWhGrxFP3jrRwa2eMpPzyeT/VqOFgmwXPk0B2oi 1267636293
From: ocaml@optimojoe.com
To: caml-list@inria.fr
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset="us-ascii"
X-Mailer: MessagingEngine.com Webmail Interface
Subject: Encoding an extensible parse tree and subtyping within OCaml
Date: Wed, 03 Mar 2010 18:11:33 +0100
X-Spam: no; 0.00; ocaml:01 subtyping:01 ocaml:01 grammars:01 improper:01 printf:01 printf:01 rec:01 rec:01 extensible:01 encode:01 int:01 int:01 essentially:02 tree:02 

Hi,
     Is there a good way to encode a parse tree in OCaml where the terms
     in the parse tree can be extended later?  Essentially, it would be
     nice not to represent the trees for different grammars separately
     so that code for type checking, evaluation, or pretty printing can
     be reused.  I'm including one possible solution below that seems to
     work reasonably well, but I'm interested in whether this can be
     done better.  The two things that would be nice to improve upon the
     example are preventing statements such as "bad" where improper
     trees are created.  It would also be nice to have the OCaml type
     system flag an error on the line with "`Junk". Though, it does give
     a warning now.  

Joe

type base = [`Int of int];;
type 'a basic= [base | `Add of 'a*'a | `Sub of 'a*'a ];;
type 'a ext= ['a basic | `Mul of 'a*'a];;

type basic'=('a basic as 'a) basic;;
type ext'=('a ext as 'a) ext;;

let (x:'a basic)=`Add (`Int 1,`Int 2);;
let (y:'a ext)=`Mul (x,`Int 3);;
let (z:'a basic)=`Add (`Int 3,x);;
let w=`Add (`Mul (`Int 1,`Int 2),`Int 3);;
let (bad:'a basic)=`Add (1,2);;


let pp x=
    let rec pp (x:ext') =
        match x with
        | `Int x-> Printf.printf "%d" x
        | `Add (x,y) ->
            pp x; Printf.printf "+"; pp y
        | `Sub (x,y) ->
            pp x; Printf.printf "-"; pp y
        | `Mul (x,y) ->
            pp x; Printf.printf "*"; pp y
        | `Junk -> Printf.printf "BAD!"
    in
    pp (x :> ext');Printf.printf "\n"
;;

let eval x=
    let rec eval (x:basic')=
        match x with
        | `Int x -> x
        | `Add (x,y) -> (eval x) + (eval y)
        | `Sub (x,y) -> (eval x) - (eval y)
    in
    eval (x:>basic')
;;