feat(wpcarro/scratch): Implement "Algorithm W" r/5194

I've been wanting to grok Haskell-style type inference for awhile, so instead of
just watching conference talks and reading papers about it, I've decided to
attempt to implement it to more readily test my understanding of it.

Change-Id: I69261202a3d74d55c6e38763d7ddfec73c392465
Reviewed-on: https://cl.tvl.fyi/c/depot/+/6988
Tested-by: BuildkiteCI
Reviewed-by: wpcarro <wpcarro@gmail.com>
Autosubmit: wpcarro <wpcarro@gmail.com>

1 files changed, 48 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/compiler/parser.ml b/users/wpcarro/scratch/compiler/parser.ml
new file mode 100644
index 0000000000..75cbe04a3f
--- /dev/null
+++ b/users/wpcarro/scratch/compiler/parser.ml
@@ -0,0 +1,48 @@
+(*******************************************************************************
+ * Defines a generic parser class.
+ ******************************************************************************)
+
+exception ParseError of string
+
+type token = string
+type state = { i : int; tokens : token array }
+
+let get (i : int) (xs : 'a array) : 'a option =
+  if i >= Array.length xs then None else Some xs.(i)
+
+class parser (tokens : token array) =
+  object (self)
+    val mutable tokens : token array = tokens
+    val mutable i = ref 0
+    method print_state = Printf.sprintf "{ i = %d; }" !i
+    method advance = i := !i + 1
+    method prev : token option = get (!i - 1) tokens
+    method curr : token option = get !i tokens
+    method next : token option = get (!i + 1) tokens
+
+    method consume : token option =
+      match self#curr with
+      | None -> None
+      | Some x as res ->
+          self#advance;
+          res
+
+    method expect (x : token) =
+      match self#curr with
+      | Some y when x = y -> self#advance
+      | _ -> raise (ParseError (Printf.sprintf "Expected %s" x))
+
+    method matches (x : token) : bool =
+      match self#curr with
+      | None -> false
+      | Some y ->
+          if x = y then
+            begin
+              self#advance;
+              true
+            end
+          else false
+
+    method exhausted : bool = !i >= Array.length tokens
+    method state : state = { i = !i; tokens }
+  end