Caml typed AST

Caml typed AST

[Martin Potier]

Dear List,

I have a school research assignment about defunctionalization.

I'd like to implement a defunctionalization algorithm for Caml, using
Caml, that's why I'd like to know if there is a way to retrieve a typped
AST from Caml.

I had a look at the option -dparsetree of the Caml interpreter, but it
doesn't fit my need for two reasons : first it's not typped, and second
it's not easily reusable.

In a way, I just want to "plug in" right after the typing of the Caml
AST in order to reuse it.

Does anyone know the Caml source well enough to point me to a place
where a function uses a typped AST ?

--
Martin Potier

Re: [Caml-list] Caml typed AST

[Martin Potier]

Thank you for your answer.

I still have no clue how to use it, or even pretty-print from that AST.
Is there a simple way to do so ?
Is there a documentation on using basic caml elements, like building an
AST from a string of ocaml code, typing, type-checking, transforming and
prettyprinting from this AST ?

--
Martin

Le 09/06/2010 00:46, Ruslan Ledesma Garza a écrit :
> Hello Martin,
> 
> Looking at toploop.ml in 3.11.1, a line reads:
> 
> let (str, sg, newenv) = Typemod.type_structure oldenv sstr Location.none
> 
> I believe str contains the AST you are looking for.
> 
> Best regards,
> Ruslan.
> 
> On Jun 8, 2010, at 11:29 PM, Martin Potier wrote:
> 
>> Dear List,
>>
>> I have a school research assignment about defunctionalization.
>>
>> I'd like to implement a defunctionalization algorithm for Caml, using
>> Caml, that's why I'd like to know if there is a way to retrieve a typped
>> AST from Caml.
>>
>> I had a look at the option -dparsetree of the Caml interpreter, but it
>> doesn't fit my need for two reasons : first it's not typped, and second
>> it's not easily reusable.
>>
>> In a way, I just want to "plug in" right after the typing of the Caml
>> AST in order to reuse it.
>>
>> Does anyone know the Caml source well enough to point me to a place
>> where a function uses a typped AST ?
>>
>> --
>> Martin Potier
>>
>> _______________________________________________
>> Caml-list mailing list. Subscription management:
>> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>> Archives: http://caml.inria.fr
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 

Re: [Caml-list] Caml typed AST

[bluestorm]

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

The OCaml typedtree (post-typing AST) is rather intricate and contains
details about the type inference process that you might not want to have to
know about.

If you don't need the full width of the OCaml language features, I would
recommend starting from a smaller codebase. Rewriting a parser for a subset
of the OCaml language is easy, type inference difficulty depends on the
features you have in your language, but there are numerous smaller projects
you could reuse.
See for example [MinCaml], a minimalistic compiler for teaching purpose, or
the [poly] language from the Programming Language Zoo.

 [MinCaml] http://min-caml.sourceforge.net/index-e.html
 [poly] http://andrej.com/plzoo/html/poly.html

[-- Attachment #2: Type: text/html, Size: 1036 bytes --]

Re: Caml typed AST

[oleg]

Martin Potier wrote:
> I'd like to know if there is a way to retrieve a typped AST from Caml.

The function read_type_exp : string -> Typedtree.expression
takes a string of OCaml code, parses it, typechecks and returns the
typed tree. For example, evaluating

let test1 = read_type_exp "let x = 21 and twice y = 2 * y in twice x";;

prints

val test1 : Typedtree.expression =
  {Typedtree.exp_desc =
    Typedtree.Texp_let (Asttypes.Nonrecursive,
     [({Typedtree.pat_desc = Typedtree.Tpat_var <abstr>;
        Typedtree.pat_loc =
         {Location.loc_start =
           {Lexing.pos_fname = ""; Lexing.pos_lnum = 1; Lexing.pos_bol = 0;
            Lexing.pos_cnum = 4};
          Location.loc_end =
           {Lexing.pos_fname = ""; Lexing.pos_lnum = 1; Lexing.pos_bol = 0;
            Lexing.pos_cnum = 5};
          Location.loc_ghost = false};
        Typedtree.pat_type =
         {Types.desc =
           Types.Tlink
            {Types.desc =
              Types.Tconstr (Path.Pident <abstr>, [],
               {contents = Types.Mnil});
             Types.level = 100000000; Types.id = 649};
          Types.level = 59; Types.id = 647};
        Typedtree.pat_env = <abstr>},
       {Typedtree.exp_desc = Typedtree.Texp_constant (Asttypes.Const_int 21);
        Typedtree.exp_loc =
         {Location.loc_start =
           {Lexing.pos_fname = ""; Lexing.pos_lnum = 1; Lexing.pos_bol = 0;
            Lexing.pos_cnum = 8};
          Location.loc_end =
           {Lexing.pos_fname = ""; Lexing.pos_lnum = 1; Lexing.pos_bol = 0;
            Lexing.pos_cnum = 10};
          Location.loc_ghost = false};
        Typedtree.exp_type =
         {Types.desc =
           Types.Tconstr (Path.Pident <abstr>, [], {contents = Types.Mnil});
          Types.level = 100000000; Types.id = 649};
        Typedtree.exp_env = <abstr>});
...plus many more lines....

(and this is only the part that corresponds let x = 21). As you can
see (although probably not easily) the type-checker has figured
out that both x and 21 have the type int. The module
typing/printtyp.mli in the OCaml distribution has a few nicer printing
functions.

Here is the code (top-level script)

(* In the directory directives below, replace
   /usr/ports/lang/ocaml/work/ocaml-3.11.1/
 with the complete path to your ocaml distribution.
 It is assumed the directory contains the made OCaml.
*)

#directory "/usr/ports/lang/ocaml/work/ocaml-3.11.1/parsing";;
#directory "/usr/ports/lang/ocaml/work/ocaml-3.11.1/typing";;
#directory "/usr/ports/lang/ocaml/work/ocaml-3.11.1/toplevel";;
#directory "/usr/ports/lang/ocaml/work/ocaml-3.11.1/utils";;


(* Please do NOT change the order of the following directives! *)
(* This must be loaded first! It is stateful, and affects Predef *)
#load "ident.cmo";; 

(* Load the rest of the compiler *)
#load "misc.cmo";;
#load "path.cmo";;
#load "types.cmo";;
#load "btype.cmo";;
#load "tbl.cmo";;
#load "subst.cmo";;
#load "predef.cmo";;
#load "datarepr.cmo";;
#load "config.cmo";;
#load "consistbl.cmo";;
#load "clflags.cmo";;
#load "env.cmo";;
#load "ctype.cmo";;
#load "printast.cmo";;
#load "oprint.cmo";;
#load "primitive.cmo";;
#load "printtyp.cmo";;

#load "linenum.cmo";;
#load "warnings.cmo";;
#load "location.cmo";;

#load "typetexp.cmo";;
#load "includecore.cmo";;
#load "typedecl.cmo";;
#load "typedtree.cmo";;
#load "stypes.cmo";;
#load "parmatch.cmo";;
#load "typecore.cmo";;
#load "includeclass.cmo";;
#load "typeclass.cmo";;
#load "mtype.cmo";;
#load "includemod.cmo";;
#load "longident.cmo";;
#load "typemod.cmo";;

#load "ccomp.cmo";;
#load "lexer.cmo";;
#load "syntaxerr.cmo";;
#load "parser.cmo";;
#load "parse.cmo";;


(* from driver/compile.ml *)
let initial_env () =
  Config.load_path := [""; "/usr/local/lib/ocaml"];
  Env.reset_cache ();
  Ident.reinit();
  try
    Env.open_pers_signature "Pervasives" Env.initial
  with Not_found ->
    failwith "cannot open pervasives.cmi"
;;

let env = initial_env()
;;

(* toplevel/toploop.ml *)

let read_type_exp src_string =
  let lb = Lexing.from_string src_string in
  match Parse.implementation lb  with
  | [{Parsetree.pstr_desc = Parsetree.Pstr_eval exp}] ->
      Ctype.init_def(Ident.current_time()); 
      Typecore.reset_delayed_checks ();
      let texp = Typecore.type_expression env exp
      in Typecore.force_delayed_checks (); texp
  | _ -> failwith "Only expressions are expected"
;;

let test1 = read_type_exp "let x = 21 and twice y = 2 * y in twice x";;