Add OCaml tutorial to the examples.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97966 91177308-0d34-0410-b5e6-96231b3b80d8

64 files changed, 3413 insertions, 1 deletions

diff --git a/examples/Makefile b/examples/Makefile
index 0737eaf579..162a94e7a7 100644
--- a/examples/Makefile
+++ b/examples/Makefile
@@ -10,7 +10,8 @@ LEVEL=..
 
 include $(LEVEL)/Makefile.config
 
-PARALLEL_DIRS:= BrainF Fibonacci HowToUseJIT Kaleidoscope ModuleMaker
+PARALLEL_DIRS:= BrainF Fibonacci HowToUseJIT Kaleidoscope ModuleMaker \
+	OCaml-Kaleidoscope
 
 ifeq ($(HAVE_PTHREAD),1)
 PARALLEL_DIRS += ParallelJIT 
diff --git a/examples/OCaml-Kaleidoscope/Chapter2/Makefile b/examples/OCaml-Kaleidoscope/Chapter2/Makefile
new file mode 100644
index 0000000000..8fc03da0fb
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter2/Makefile
@@ -0,0 +1,22 @@
+##===- examples/OCaml-Kaleidoscope/Chapter2/Makefile -------*- Makefile -*-===##
+# 
+#                     The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+# 
+##===----------------------------------------------------------------------===##
+# 
+# This is the makefile for the Objective Caml kaleidoscope tutorial, chapter 2.
+# 
+##===----------------------------------------------------------------------===##
+
+LEVEL := ../../..
+TOOLNAME := OCaml-Kaleidoscope-Ch2
+EXAMPLE_TOOL := 1
+UsedComponents := core
+UsedOcamLibs := llvm
+
+OCAMLCFLAGS += -pp camlp4of
+
+include $(LEVEL)/bindings/ocaml/Makefile.ocaml
diff --git a/examples/OCaml-Kaleidoscope/Chapter2/_tags b/examples/OCaml-Kaleidoscope/Chapter2/_tags
new file mode 100644
index 0000000000..7b9b80b1e9
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter2/_tags
@@ -0,0 +1 @@
+<{lexer,parser}.ml>: use_camlp4, pp(camlp4of)
diff --git a/examples/OCaml-Kaleidoscope/Chapter2/ast.ml b/examples/OCaml-Kaleidoscope/Chapter2/ast.ml
new file mode 100644
index 0000000000..4cc2dea86b
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter2/ast.ml
@@ -0,0 +1,25 @@
+(*===----------------------------------------------------------------------===
+ * Abstract Syntax Tree (aka Parse Tree)
+ *===----------------------------------------------------------------------===*)
+
+(* expr - Base type for all expression nodes. *)
+type expr =
+  (* variant for numeric literals like "1.0". *)
+  | Number of float
+
+  (* variant for referencing a variable, like "a". *)
+  | Variable of string
+
+  (* variant for a binary operator. *)
+  | Binary of char * expr * expr
+
+  (* variant for function calls. *)
+  | Call of string * expr array
+
+(* proto - This type represents the "prototype" for a function, which captures
+ * its name, and its argument names (thus implicitly the number of arguments the
+ * function takes). *)
+type proto = Prototype of string * string array
+
+(* func - This type represents a function definition itself. *)
+type func = Function of proto * expr
diff --git a/examples/OCaml-Kaleidoscope/Chapter2/lexer.ml b/examples/OCaml-Kaleidoscope/Chapter2/lexer.ml
new file mode 100644
index 0000000000..22a915552f
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter2/lexer.ml
@@ -0,0 +1,52 @@
+(*===----------------------------------------------------------------------===
+ * Lexer
+ *===----------------------------------------------------------------------===*)
+
+let rec lex = parser
+  (* Skip any whitespace. *)
+  | [< ' (' ' | '\n' | '\r' | '\t'); stream >] -> lex stream
+
+  (* identifier: [a-zA-Z][a-zA-Z0-9] *)
+  | [< ' ('A' .. 'Z' | 'a' .. 'z' as c); stream >] ->
+      let buffer = Buffer.create 1 in
+      Buffer.add_char buffer c;
+      lex_ident buffer stream
+
+  (* number: [0-9.]+ *)
+  | [< ' ('0' .. '9' as c); stream >] ->
+      let buffer = Buffer.create 1 in
+      Buffer.add_char buffer c;
+      lex_number buffer stream
+
+  (* Comment until end of line. *)
+  | [< ' ('#'); stream >] ->
+      lex_comment stream
+
+  (* Otherwise, just return the character as its ascii value. *)
+  | [< 'c; stream >] ->
+      [< 'Token.Kwd c; lex stream >]
+
+  (* end of stream. *)
+  | [< >] -> [< >]
+
+and lex_number buffer = parser
+  | [< ' ('0' .. '9' | '.' as c); stream >] ->
+      Buffer.add_char buffer c;
+      lex_number buffer stream
+  | [< stream=lex >] ->
+      [< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >]
+
+and lex_ident buffer = parser
+  | [< ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream >] ->
+      Buffer.add_char buffer c;
+      lex_ident buffer stream
+  | [< stream=lex >] ->
+      match Buffer.contents buffer with
+      | "def" -> [< 'Token.Def; stream >]
+      | "extern" -> [< 'Token.Extern; stream >]
+      | id -> [< 'Token.Ident id; stream >]
+
+and lex_comment = parser
+  | [< ' ('\n'); stream=lex >] -> stream
+  | [< 'c; e=lex_comment >] -> e
+  | [< >] -> [< >]
diff --git a/examples/OCaml-Kaleidoscope/Chapter2/parser.ml b/examples/OCaml-Kaleidoscope/Chapter2/parser.ml
new file mode 100644
index 0000000000..83d9874a4a
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter2/parser.ml
@@ -0,0 +1,122 @@
+(*===---------------------------------------------------------------------===
+ * Parser
+ *===---------------------------------------------------------------------===*)
+
+(* binop_precedence - This holds the precedence for each binary operator that is
+ * defined *)
+let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
+
+(* precedence - Get the precedence of the pending binary operator token. *)
+let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
+
+(* primary
+ *   ::= identifier
+ *   ::= numberexpr
+ *   ::= parenexpr *)
+let rec parse_primary = parser
+  (* numberexpr ::= number *)
+  | [< 'Token.Number n >] -> Ast.Number n
+
+  (* parenexpr ::= '(' expression ')' *)
+  | [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
+
+  (* identifierexpr
+   *   ::= identifier
+   *   ::= identifier '(' argumentexpr ')' *)
+  | [< 'Token.Ident id; stream >] ->
+      let rec parse_args accumulator = parser
+        | [< e=parse_expr; stream >] ->
+            begin parser
+              | [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
+              | [< >] -> e :: accumulator
+            end stream
+        | [< >] -> accumulator
+      in
+      let rec parse_ident id = parser
+        (* Call. *)
+        | [< 'Token.Kwd '(';
+             args=parse_args [];
+             'Token.Kwd ')' ?? "expected ')'">] ->
+            Ast.Call (id, Array.of_list (List.rev args))
+
+        (* Simple variable ref. *)
+        | [< >] -> Ast.Variable id
+      in
+      parse_ident id stream
+
+  | [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
+
+(* binoprhs
+ *   ::= ('+' primary)* *)
+and parse_bin_rhs expr_prec lhs stream =
+  match Stream.peek stream with
+  (* If this is a binop, find its precedence. *)
+  | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
+      let token_prec = precedence c in
+
+      (* If this is a binop that binds at least as tightly as the current binop,
+       * consume it, otherwise we are done. *)
+      if token_prec < expr_prec then lhs else begin
+        (* Eat the binop. *)
+        Stream.junk stream;
+
+        (* Parse the primary expression after the binary operator. *)
+        let rhs = parse_primary stream in
+
+        (* Okay, we know this is a binop. *)
+        let rhs =
+          match Stream.peek stream with
+          | Some (Token.Kwd c2) ->
+              (* If BinOp binds less tightly with rhs than the operator after
+               * rhs, let the pending operator take rhs as its lhs. *)
+              let next_prec = precedence c2 in
+              if token_prec < next_prec
+              then parse_bin_rhs (token_prec + 1) rhs stream
+              else rhs
+          | _ -> rhs
+        in
+
+        (* Merge lhs/rhs. *)
+        let lhs = Ast.Binary (c, lhs, rhs) in
+        parse_bin_rhs expr_prec lhs stream
+      end
+  | _ -> lhs
+
+(* expression
+ *   ::= primary binoprhs *)
+and parse_expr = parser
+  | [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
+
+(* prototype
+ *   ::= id '(' id* ')' *)
+let parse_prototype =
+  let rec parse_args accumulator = parser
+    | [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
+    | [< >] -> accumulator
+  in
+
+  parser
+  | [< 'Token.Ident id;
+       'Token.Kwd '(' ?? "expected '(' in prototype";
+       args=parse_args [];
+       'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
+      (* success. *)
+      Ast.Prototype (id, Array.of_list (List.rev args))
+
+  | [< >] ->
+      raise (Stream.Error "expected function name in prototype")
+
+(* definition ::= 'def' prototype expression *)
+let parse_definition = parser
+  | [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
+      Ast.Function (p, e)
+
+(* toplevelexpr ::= expression *)
+let parse_toplevel = parser
+  | [< e=parse_expr >] ->
+      (* Make an anonymous proto. *)
+      Ast.Function (Ast.Prototype ("", [||]), e)
+
+(*  external ::= 'extern' prototype *)
+let parse_extern = parser
+  | [< 'Token.Extern; e=parse_prototype >] -> e
diff --git a/examples/OCaml-Kaleidoscope/Chapter2/token.ml b/examples/OCaml-Kaleidoscope/Chapter2/token.ml
new file mode 100644
index 0000000000..2ca782e149
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter2/token.ml
@@ -0,0 +1,15 @@
+(*===----------------------------------------------------------------------===
+ * Lexer Tokens
+ *===----------------------------------------------------------------------===*)
+
+(* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
+ * these others for known things. *)
+type token =
+  (* commands *)
+  | Def | Extern
+
+  (* primary *)
+  | Ident of string | Number of float
+
+  (* unknown *)
+  | Kwd of char
diff --git a/examples/OCaml-Kaleidoscope/Chapter2/toplevel.ml b/examples/OCaml-Kaleidoscope/Chapter2/toplevel.ml
new file mode 100644
index 0000000000..01c85bd70d
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter2/toplevel.ml
@@ -0,0 +1,34 @@
+(*===----------------------------------------------------------------------===
+ * Top-Level parsing and JIT Driver
+ *===----------------------------------------------------------------------===*)
+
+(* top ::= definition | external | expression | ';' *)
+let rec main_loop stream =
+  match Stream.peek stream with
+  | None -> ()
+
+  (* ignore top-level semicolons. *)
+  | Some (Token.Kwd ';') ->
+      Stream.junk stream;
+      main_loop stream
+
+  | Some token ->
+      begin
+        try match token with
+        | Token.Def ->
+            ignore(Parser.parse_definition stream);
+            print_endline "parsed a function definition.";
+        | Token.Extern ->
+            ignore(Parser.parse_extern stream);
+            print_endline "parsed an extern.";
+        | _ ->
+            (* Evaluate a top-level expression into an anonymous function. *)
+            ignore(Parser.parse_toplevel stream);
+            print_endline "parsed a top-level expr";
+        with Stream.Error s ->
+          (* Skip token for error recovery. *)
+          Stream.junk stream;
+          print_endline s;
+      end;
+      print_string "ready> "; flush stdout;
+      main_loop stream
diff --git a/examples/OCaml-Kaleidoscope/Chapter2/toy.ml b/examples/OCaml-Kaleidoscope/Chapter2/toy.ml
new file mode 100644
index 0000000000..42b19fec00
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter2/toy.ml
@@ -0,0 +1,21 @@
+(*===----------------------------------------------------------------------===
+ * Main driver code.
+ *===----------------------------------------------------------------------===*)
+
+let main () =
+  (* Install standard binary operators.
+   * 1 is the lowest precedence. *)
+  Hashtbl.add Parser.binop_precedence '<' 10;
+  Hashtbl.add Parser.binop_precedence '+' 20;
+  Hashtbl.add Parser.binop_precedence '-' 20;
+  Hashtbl.add Parser.binop_precedence '*' 40;    (* highest. *)
+
+  (* Prime the first token. *)
+  print_string "ready> "; flush stdout;
+  let stream = Lexer.lex (Stream.of_channel stdin) in
+
+  (* Run the main "interpreter loop" now. *)
+  Toplevel.main_loop stream;
+;;
+
+main ()
diff --git a/examples/OCaml-Kaleidoscope/Chapter3/Makefile b/examples/OCaml-Kaleidoscope/Chapter3/Makefile
new file mode 100644
index 0000000000..fdbcd5191f
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter3/Makefile
@@ -0,0 +1,24 @@
+##===- examples/OCaml-Kaleidoscope/Chapter3/Makefile -------*- Makefile -*-===##
+# 
+#                     The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+# 
+##===----------------------------------------------------------------------===##
+# 
+# This is the makefile for the Objective Caml kaleidoscope tutorial, chapter 3.
+# 
+##===----------------------------------------------------------------------===##
+
+LEVEL := ../../..
+TOOLNAME := OCaml-Kaleidoscope-Ch3
+EXAMPLE_TOOL := 1
+UsedComponents := core
+UsedOcamLibs := llvm llvm_analysis
+
+OCAMLCFLAGS += -pp camlp4of
+
+ExcludeSources = $(PROJ_SRC_DIR)/myocamlbuild.ml
+
+include $(LEVEL)/bindings/ocaml/Makefile.ocaml
diff --git a/examples/OCaml-Kaleidoscope/Chapter3/_tags b/examples/OCaml-Kaleidoscope/Chapter3/_tags
new file mode 100644
index 0000000000..990490a5db
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter3/_tags
@@ -0,0 +1,2 @@
+<{lexer,parser}.ml>: use_camlp4, pp(camlp4of)
+<*.{byte,native}>: g++, use_llvm, use_llvm_analysis
diff --git a/examples/OCaml-Kaleidoscope/Chapter3/ast.ml b/examples/OCaml-Kaleidoscope/Chapter3/ast.ml
new file mode 100644
index 0000000000..4cc2dea86b
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter3/ast.ml
@@ -0,0 +1,25 @@
+(*===----------------------------------------------------------------------===
+ * Abstract Syntax Tree (aka Parse Tree)
+ *===----------------------------------------------------------------------===*)
+
+(* expr - Base type for all expression nodes. *)
+type expr =
+  (* variant for numeric literals like "1.0". *)
+  | Number of float
+
+  (* variant for referencing a variable, like "a". *)
+  | Variable of string
+
+  (* variant for a binary operator. *)
+  | Binary of char * expr * expr
+
+  (* variant for function calls. *)
+  | Call of string * expr array
+
+(* proto - This type represents the "prototype" for a function, which captures
+ * its name, and its argument names (thus implicitly the number of arguments the
+ * function takes). *)
+type proto = Prototype of string * string array
+
+(* func - This type represents a function definition itself. *)
+type func = Function of proto * expr
diff --git a/examples/OCaml-Kaleidoscope/Chapter3/codegen.ml b/examples/OCaml-Kaleidoscope/Chapter3/codegen.ml
new file mode 100644
index 0000000000..275cd0bee0
--- /dev/null
+++ b/examples/OCaml-Kaleidoscope/Chapter3/codegen.ml
@@ -0,0 +1,100 @@
+(*===----------------------------------------------------------------------===
+ * Code Generation
+ *===----------------------------------------------------------------------===*)
+
+open Llvm
+
+exception Error of string
+
+let context = global_context ()
+let the_module = create_module context "my cool jit"
+let builder = builder context
+let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
+let double_type = double_type context
+
+let rec codegen_expr = function
+  | Ast.Number n -> const_float double_type n
+  | Ast.Variable name ->
+      (try Hashtbl.find named_values name with
+        | Not_found -> raise (Error "unknown variable name"))
+  | Ast.Binary (op, lhs, rhs) ->
+      let lhs_val = codegen_expr lhs in
+      let rhs_val = codegen_expr rhs in
+      begin
+        match op with
+        | '+' -> build_add lhs_val rhs_val "addtmp" builder
+        | '-' -> build_sub lhs_val rhs_val "subtmp" builder
+        | '*' -> build_mul lhs_val rhs_val "multmp" builder
+        | '<' ->
+            (* Convert bool 0/1 to double 0.0 or 1.0 *)
+            let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
+            build_uitofp i double_type "booltmp" builder
+        | _ -> raise (Error "invalid binary operator")
+      end
+  | Ast.Call (callee, args) ->
+      (* Look up the name in the module table. *)
+      let callee =
+        match lookup_function callee the_module with
+        | Some callee -> callee
+        | None -> raise (Error "unknown function referenced")
+      in
+      let params = params callee in
+
+      (* If argument mismatch error. *)
+