From 7f49a45703ca203ba500506a52a69bfb804fbaa2 Mon Sep 17 00:00:00 2001
From: Mike Lowis <mike.lowis@gentex.com>
Date: Mon, 4 Dec 2023 16:15:28 -0500
Subject: [PATCH] started implementing type checking

---
 cerise.m  |  10 +-
 cerise.rb | 919 ++++++++++++++++++++++++++++--------------------------
 2 files changed, 489 insertions(+), 440 deletions(-)

diff --git a/cerise.m b/cerise.m
index 94d3da2..92ace9c 100644
--- a/cerise.m
+++ b/cerise.m
@@ -1,3 +1,8 @@
+main()
+{
+    return sum(1+1,3)
+}
+
 sum(a,b)
 {
     def c = 5
@@ -11,8 +16,3 @@ sum(a,b)
     }
     return c
 }
-
-main()
-{
-    return sum(1+1,3)
-}
diff --git a/cerise.rb b/cerise.rb
index 85d2ed2..767b4e1 100755
--- a/cerise.rb
+++ b/cerise.rb
@@ -14,6 +14,45 @@
 require 'stringio'
 require 'strscan'
 
+
+##
+# Intermediate Representation Module
+##
+
+module IR
+  Func   = Struct.new(:loc, :type, :args, :locals, :body)
+  Return = Struct.new(:loc, :type, :value)
+  Const  = Struct.new(:loc, :type, :value)
+  Var    = Struct.new(:loc, :type, :name)
+  Def    = Struct.new(:loc, :type, :name, :value)
+  Set    = Struct.new(:loc, :type, :name, :value)
+  Op     = Struct.new(:loc, :type, :op, :left, :right)
+  Call   = Struct.new(:loc, :type, :func, :args)
+  If     = Struct.new(:loc, :type, :cond, :then, :else)
+end
+
+
+##
+# Data Type Representation Module
+##
+
+module Value
+  # Forms: :bool, :int, :float, :void, :array, :record, :string, :proc
+  Type  = Struct.new(:form, :fields, :base, :size)
+  Field = Struct.new(:type, :offset)
+
+  # Base type definitions
+  Void  = Type.new(:void,  nil, nil, 0)
+  Bool  = Type.new(:bool,  nil, nil, 1)
+  Int   = Type.new(:int,   nil, nil, 8)
+  Float = Type.new(:float, nil, nil, 8)
+end
+
+
+##
+# Lexical Analyzer Definition
+##
+
 class Lexer
   Tok = Struct.new(:text, :file, :pos, :type)
 
@@ -33,7 +72,8 @@ class Lexer
   end
 
   def linenum(pos = nil)
-    @text[0..(pos || @data.pos)].count("\n") + 1
+    pos = [pos || @data.pos].flatten.last
+    @text[0..pos].count("\n") + 1
   end
 
   SPACE = /([ \t\v\n\r]+|#.*\n)/
@@ -50,9 +90,6 @@ class Lexer
     "else"   => :else,
     "def"    => :def,
     "set"    => :set,
-#    "func"   => :func,
-#    "in"     => :in,
-    "is"     => :is,
     "return" => :return,
   }
 
@@ -83,414 +120,18 @@ class Lexer
   end
 end
 
-class SymTable
-  Symbol = Struct.new(:name, :loc, :kind, :type, :value)
-
-  def initialize()
-    @scopes = [{}, {}]
-  end
-
-  def builtin?(name)
-    (not local? name) and (not (@scopes[0] || {})[name].nil?)
-  end
-
-  def global?(name)
-    (not local? name) and (not (@scopes[1] || {})[name].nil?)
-  end
-
-  def parameter?(name)
-    (not local? name) and (not (@scopes[2] || {})[name].nil?)
-  end
-
-  def local?(name)
-    find_sym(@scopes[3..-1], name)
-  end
-
-  def find_sym(scopes, name)
-    scopes.reverse_each.detect do |scope|
-      return scope[name]
-    end
-  end
-
-  def open_scope()
-    @scopes.push({})
-  end
-
-  def close_scope()
-    @scopes.pop
-  end
-
-  def reset_scope()
-    @scopes = @scopes[0..1]
-  end
-
-  def [](name)
-    find_sym(@scopes, name)
-  end
-
-  def add_builtin(name, kind, type, value)
-    @scopes[0][name] =
-      Symbol.new(name, 0, kind, type, value)
-  end
-
-  def add_sym(name, loc, kind, type, value)
-    @scopes.last[name] =
-      Symbol.new(name, loc, kind, type, value)
-  end
-
-  def each(&block)
-    @scopes.last.each(&block)
-  end
-end
-
-
-
-module IR
-  Func   = Struct.new(:loc, :type, :args, :locals, :body)
-  Return = Struct.new(:loc, :type, :value)
-  Const  = Struct.new(:loc, :type, :value)
-  Var    = Struct.new(:loc, :type, :name)
-  Def    = Struct.new(:loc, :type, :name, :value)
-  Set    = Struct.new(:loc, :type, :name, :value)
-  Op     = Struct.new(:loc, :type, :op, :left, :right)
-  Call   = Struct.new(:loc, :type, :func, :args)
-  If     = Struct.new(:loc, :type, :cond, :then, :else)
-
-#  EnvRef = Struct.new(:loc, :type, :index)
-#  Let    = Struct.new(:loc, :type, :var,  :expr, :body)
-#  If     = Struct.new(:loc, :type, :cond, :then, :else)
-#  Set    = Struct.new(:loc, :type, :var,  :expr)
-#  Apply  = Struct.new(:loc, :type, :func, :args)
-end
-
-
-class TypeChecker
-  UnaryOps = {
-    "+" => {
-      int: [:int, :int],
-      float: [:float, :float],
-    },
-    "-" => {
-      int: [:int, :int],
-      float: [:float, :float],
-    },
-    "!" => {
-      bool: [:bool, :bool]
-    },
-  }
-
-  BinaryOps = {
-    "+" => {
-      int: [:int, :int, :int],
-      float: [:float, :float, :float],
-    },
-    "-" => {
-      int: [:int, :int, :int],
-      float: [:float, :float, :float],
-    },
-    "*" => {
-      int: [:int, :int, :int],
-      float: [:float, :float, :float],
-    },
-    "/" => {
-      int: [:int, :int, :int],
-      float: [:float, :float, :float],
-    },
-    "%" => {
-      int: [:int, :int, :int],
-# Float modulo normally implemented as library function
-#      float: [:float, :float, :float],
-    },
-    "<" => {
-      int: [:int, :int, :bool],
-      float: [:float, :float, :bool],
-    },
-    ">" => {
-      int: [:int, :int, :bool],
-      float: [:float, :float, :bool],
-    },
-    "<=" => {
-      int: [:int, :int, :bool],
-      float: [:float, :float, :bool],
-    },
-    ">=" => {
-      int: [:int, :int, :bool],
-      float: [:float, :float, :bool],
-    },
-    "==" => {
-      int: [:int, :int, :bool],
-      float: [:float, :float, :bool],
-      string: [:string, :string, :bool],
-    },
-    "!=" => {
-      int: [:int, :int, :bool],
-      float: [:float, :float, :bool],
-      string: [:string, :string, :bool],
-    },
-    "&&" => { bool: [:bool, :bool, :bool] },
-    "||" => { bool: [:bool, :bool, :bool] },
-    "<<" => { int: [:int, :int, :int] },
-    ">>" => { int: [:int, :int, :int] },
-    "&"  => { int: [:int, :int, :int] },
-    "^"  => { int: [:int, :int, :int] },
-    "|"  => { int: [:int, :int, :int] },
-  }
-
-  def initialize(parser)
-    @parser = parser
-  end
-
-  def error(loc, msg)
-    @parser.error(msg, loc)
-  end
-
-  def check(env, expr, type)
-    if (expr.is_a? IR::If)
-      check_ifexpr(env, expr, type)
-    elsif (expr.is_a? IR::Func)
-      check_func(env, expr, type)
-    elsif (expr.is_a? IR::Var)
-      check_var(env, expr, type)
-    elsif (expr.is_a? IR::Let)
-      check_let(env, expr, type)
-#    elsif (expr.is_a? IR::Apply)
-#      check_apply(env, expr, type)
-    else
-      etype = infer(env, expr)
-      if type != etype
-        error(expr.loc, "expected #{type}, received #{etype}")
-      end
-    end
-    expr.type = type
-  end
-
-  def infer(env, expr)
-    if expr.is_a? IR::Const
-      infer_const(env, expr)
-    elsif expr.is_a? IR::Var
-      infer_var(env, expr)
-    elsif expr.is_a? IR::Let
-      infer_let(env, expr)
-    elsif expr.is_a? IR::If
-      infer_ifexpr(env, expr)
-    elsif expr.is_a? IR::Set
-      infer_set(env, expr)
-    elsif expr.is_a? IR::Func
-      infer_func(env, expr)
-    elsif expr.is_a? IR::Apply
-      infer_apply(env, expr)
-    else
-      error(expr.loc, "unable to determine type of expression")
-    end
-  end
-
-  private
-
-  def make_typevar()
-    @typevar ||= 0
-    var = "abcdefghijklmnopqrstuvwxyz"[@typevar]
-    @typevar += 1
-    var
-  end
-
-  def var?(expr)
-    expr.class == IR::Var
-  end
-
-  def untyped_global_func?(env, func, type)
-    type.nil? and
-    var?(func) and
-    env.global?(func.name) and
-    env[func.name][:value]
-  end
-
-  def check_apply(env, expr, type)
-    # Handle global functions that haven't been typed yet but are
-    # being called. We pause to infer their type.
-    if untyped_global_func?(env, expr.func, type)
-      value = env[expr.func.name][:value]
-      env[expr.func.name][:value] = nil
-      infer(@parser.syms, value)
-      type = infer(env, expr.func)
-    end
-
-    error(expr.loc, "object being applied is not a function (has type: #{type.to_s})") if not type.is_a? Array
-    error(expr.loc, "wrong number of arguments to function call") if (type.length - 1) != expr.args.length
-    type[0..-2].each_with_index do |t,i|
-      check(env, expr.args[i], t)
-    end
-    expr.type = type.last
-  end
-
-  def check_ifexpr(env, expr, type)
-    check(env, expr.cond, :bool)
-    check(env, expr.then, type)
-    check(env, expr.else, type)
-  end
-
-  def check_var(env, expr, type)
-    etype = infer(env, expr)
-    if (etype.class == String)
-      expr.type = type
-      env.set_type(expr.name, type)
-    elsif expr.type != type
-      error(expr.loc, "expected #{type}, received #{etype}")
-    end
-    type
-  end
-
-  def verify(cond, loc, msg)
-    error(loc, msg) if not cond
-  end
-
-  def check_func(env, expr, type)
-    env = env.clone
-    verify((type.length-1) == expr.args.length, expr.loc,
-      "incorrect number of arguments (#{expr.args.length}, expected #{(type.length-1)}")
-    expr.args.each_with_index do |a,i|
-      env.add_sym(a.name, a.loc, :arg, type[i])
-    end
-    check(env, expr.expr, type.last)
-  end
-
-  def check_let(env, let, type)
-    env = env.clone
-    env.add_sym(let.var.name, let.var.loc, :var, let.var.type)
-    check(env, let.expr, type)
-  end
-
-  def infer_const(env, expr)
-    expr.type
-  end
-
-  def infer_var(env, expr)
-    if not env.defined?(expr.name)
-      error(expr.loc, "symbol '#{expr.name}' not defined")
-    end
-    expr.type = env[expr.name][:type]
-  end
-
-  def infer_let(env, let)
-    if let.body.nil?
-      infer_decl(env, let)
-    else
-      infer_let_expr(env, let)
-    end
-  end
-
-  def infer_decl(env, let)
-    env = env.clone
-    # handle the binding
-    if let.var.type
-      check(env, let.expr, let.var.type)
-    else
-      let.var.type = infer(env, let.expr)
-    end
-    env.set_type(let.var.name, let.var.type)
-    env[let.var.name][:value] = nil
-    let.type = :void
-  end
-
-  def infer_let_expr(env, let)
-    env = env.clone
-
-    # handle the binding
-    if let.var.type
-      check(env, let.expr, let.var.type)
-    else
-      let.var.type = infer(env, let.expr)
-    end
-
-    env.add_sym(let.var.name, let.var.loc, :var, let.var.type)
-    let.type = infer(env, let.body)
-  end
-
-  def infer_ifexpr(env, expr)
-    check(env, expr, infer(env, expr.then))
-  end
-
-  def infer_set(env, expr)
-    error(expr.loc, "infer_set unimplemented")
-  end
-
-  def infer_func(env, expr)
-    env = env.clone
-    @typevar = 0
-    expr.args.each do |a|
-      a.type ||= make_typevar()
-      env.add_sym(a.name, a.loc, :arg, a.type)
-    end
-    infer(env, expr.expr)
-    type = (expr.args + [expr.expr]).map {|v| v.type }
-    type.unshift(:void) if type.length == 1
-
-    # the body may have inferred an arg type, fix it up here
-    expr.args.each_with_index do |a,i|
-      a.type = env[a.name][:type]
-      type[i] = a.type
-    end
-    expr.type = type
-  end
-
-  def infer_apply(env, expr)
-    if expr.func.is_a? String
-      expr.type = infer_opcall(env, expr)
-    else
-      type = infer(env, expr.func)
-      check_apply(env, expr, type)
-    end
-  end
-
-  def assign_type(env, var, type)
-    if var.class == IR::Var and (var.type.nil? or var.type == String) then
-      var.type = type
-      env[var.name][:type] = type
-    end
-  end
-
-  def infer_opcall(env, expr)
-    # infer the operand type first
-    vtype = infer(env, expr.args[0])
-    if (not vtype or vtype.class == String) and expr.args.length == 2
-      vtype = infer(env, expr.args[1])
-    end
-
-    # use the operand type to pick op type and check it
-    if expr.args.length == 1
-      check_unary(env, expr, vtype)
-
-    elsif expr.args.length == 2
-      check_binary(env, expr, vtype)
-    else
-      error(expr.loc, "too many operands for operator '#{expr.func}'")
-    end
-  end
-
-  def check_unary(env, expr, vtype)
-    optype = UnaryOps[expr.func][vtype]
-    error(expr.loc, "unknown unary operation '#{expr.func}' for operand type #{vtype}") if not optype
-    check_apply(env, expr, optype)
-  end
-
-  def check_binary(env, expr, vtype)
-    optype = BinaryOps[expr.func][vtype]
-    error(expr.loc, "unknown binary operation '#{expr.func}' for operand type #{vtype}") if optype.nil?
-
-    expr.args.each_with_index do |a, i|
-      assign_type(env, a, optype[i])
-    end
-    check_apply(env, expr, optype)
-  end
-end
 
+##
+# Code Parsing Module
+##
 
 class Parser
-#  attr_accessor :exprs
   attr_accessor :syms
-  attr_accessor :defs
+  attr_accessor :checker
 
   def initialize(path = nil)
     @syms = SymTable.new
+    @checker = TypeChecker.new(self)
     syms.add_builtin(:void,   0, :type, :void)
     syms.add_builtin(:bool,   0, :type, :bool)
     syms.add_builtin(:int,    0, :type, :int)
@@ -559,10 +200,6 @@ class Parser
     end
   end
 
-
-
-
-
   OPERATORS = {
     "+"  => true,
     "-"  => true,
@@ -622,10 +259,6 @@ class Parser
       val = function_definition(ident)
     elsif matches("=") then
       val = constant_definition(ident)
-    elsif matches(":") then
-      val = type_annotation(ident)
-    elsif matches(:is)
-      val = type_definition(ident)
     else
       error("#{ident.name} is not a valid toplevel definition")
     end
@@ -653,14 +286,6 @@ class Parser
     error("constant definitions not yet supported")
   end
 
-  def type_definition(name)
-    error("type definitions not yet supported")
-  end
-
-  def type_annotation(name)
-    error("type annotations not yet supported")
-  end
-
   def function_arglist()
     args = []
     expect("(")
@@ -690,11 +315,6 @@ class Parser
   end
 
   def statement()
-    # variable definition
-    # variable assignment
-    # if statement
-    # expression
-
     if matches(:set)
       variable_assignment()
     elsif matches(:if)
@@ -769,7 +389,7 @@ class Parser
       loc = location
       op = consume()
       right = simple_expr()
-      left = IR::Op.new(loc, nil, op.text, left, right)
+      left = make_binop(loc, op.text, left, right)
     end
     left
   end
@@ -780,7 +400,7 @@ class Parser
       loc = location
       op = consume()
       left = term()
-      left = IR::Op.new(location, nil, op.text, left, nil)
+      left = make_unop(location, op.text, left, nil)
     else
       left = term()
     end
@@ -790,7 +410,7 @@ class Parser
       loc = location
       op = consume()
       right = term()
-      left = IR::Op.new(loc, nil, op.text, left, right)
+      left = make_binop(loc, op.text, left, right)
     end
     left
   end
@@ -801,11 +421,23 @@ class Parser
       loc = location
       op = consume()
       right = factor();
-      left = IR::Op.new(loc, nil, op.text, left, right)
+      left = make_binop(loc, op.text, left, right)
     end
     left
   end
 
+  def make_binop(loc, op, left, right)
+    node = IR::Op.new(loc, nil, op, left, right)
+    checker.infer(syms, node)
+    node
+  end
+
+  def make_unop(loc, op, value)
+    node = IR::Op.new(loc, nil, op, value, nil)
+    checker.infer(syms, node)
+    node
+  end
+
   def factor()
     if accept("(")
       expr = expression()
@@ -835,15 +467,15 @@ class Parser
   def const_or_ident()
     tok = consume()
     if tok.type == :bool
-      IR::Const.new(tok.pos, :bool, tok.text == "true")
+      IR::Const.new(tok.pos, Value::Bool, tok.text == "true")
     elsif tok.type == :string
-      IR::Const.new(tok.pos, :string, tok.text)
+      IR::Const.new(tok.pos, Value::String, tok.text)
     elsif tok.type == :int
-      IR::Const.new(tok.pos, :int, tok.text.to_i)
+      IR::Const.new(tok.pos, Value::Int, tok.text.to_i)
     elsif tok.type == :float
-      IR::Const.new(tok.pos, :float, tok.text.to_f)
+      IR::Const.new(tok.pos, Value::Float, tok.text.to_f)
     elsif tok.type == :void
-      IR::Const.new(tok.pos, :void, :void)
+      IR::Const.new(tok.pos, Value::Void, :void)
     elsif tok.type == :ident
       IR::Var.new(tok.pos, nil, tok.text.to_sym)
     else
@@ -852,6 +484,418 @@ class Parser
   end
 end
 
+
+##
+# Symbol Table Definition
+##
+
+class SymTable
+  Symbol = Struct.new(:name, :loc, :kind, :type, :value)
+
+  def initialize()
+    @scopes = [{}, {}]
+  end
+
+  def builtin?(name)
+    (not local? name) and (not (@scopes[0] || {})[name].nil?)
+  end
+
+  def global?(name)
+    (not local? name) and (not (@scopes[1] || {})[name].nil?)
+  end
+
+  def parameter?(name)
+    (not local? name) and (not (@scopes[2] || {})[name].nil?)
+  end
+
+  def local?(name)
+    find_sym(@scopes[3..-1], name)
+  end
+
+  def find_sym(scopes, name)
+    scopes.reverse_each.detect do |scope|
+      return scope[name]
+    end
+  end
+
+  def open_scope()
+    @scopes.push({})
+  end
+
+  def close_scope()
+    @scopes.pop
+  end
+
+  def reset_scope()
+    @scopes = @scopes[0..1]
+  end
+
+  def [](name)
+    find_sym(@scopes, name)
+  end
+
+  def add_builtin(name, kind, type, value)
+    @scopes[0][name] =
+      Symbol.new(name, 0, kind, type, value)
+  end
+
+  def add_sym(name, loc, kind, type, value)
+    @scopes.last[name] =
+      Symbol.new(name, loc, kind, type, value)
+  end
+
+  def each(&block)
+    @scopes.last.each(&block)
+  end
+end
+
+
+##
+# Type Checking/Inference Module
+##
+
+class TypeChecker
+  BaseToTypes = {
+    :bool   => Value::Bool,
+    :int    => Value::Int,
+    :float  => Value::Float,
+#    :string => Value::String,
+  }
+
+  TypesToBase = {
+    Value::Bool  => :bool,
+    Value::Int   => :int,
+    Value::Float => :float,
+  }
+
+  UnaryOps = {
+    "+" => {
+      int: [:int, :int],
+      float: [:float, :float],
+    },
+    "-" => {
+      int: [:int, :int],
+      float: [:float, :float],
+    },
+    "!" => {
+      bool: [:bool, :bool]
+    },
+  }
+
+  BinaryOps = {
+    "+" => {
+      int: [:int, :int, :int],
+      float: [:float, :float, :float],
+    },
+    "-" => {
+      int: [:int, :int, :int],
+      float: [:float, :float, :float],
+    },
+    "*" => {
+      int: [:int, :int, :int],
+      float: [:float, :float, :float],
+    },
+    "/" => {
+      int: [:int, :int, :int],
+      float: [:float, :float, :float],
+    },
+    "%" => {
+      int: [:int, :int, :int],
+# Float modulo normally implemented as library function
+#      float: [:float, :float, :float],
+    },
+    "<" => {
+      int:   [:int, :int, :bool],
+      float: [:float, :float, :bool],
+    },
+    ">" => {
+      int:   [:int, :int, :bool],
+      float: [:float, :float, :bool],
+    },
+    "<=" => {
+      int:   [:int, :int, :bool],
+      float: [:float, :float, :bool],
+    },
+    ">=" => {
+      int:   [:int, :int, :bool],
+      float: [:float, :float, :bool],
+      bool:  [:bool, :bool, :bool],
+    },
+    "==" => {
+      int:    [:int, :int, :bool],
+      float:  [:float, :float, :bool],
+      bool:   [:bool, :bool, :bool],
+      string: [:string, :string, :bool],
+    },
+    "!=" => {
+      int:    [:int, :int, :bool],
+      float:  [:float, :float, :bool],
+      bool:   [:bool, :bool, :bool],
+      string: [:string, :string, :bool],
+    },
+    "&&" => { bool: [:bool, :bool, :bool] },
+    "||" => { bool: [:bool, :bool, :bool] },
+    "<<" => { int: [:int, :int, :int] },
+    ">>" => { int: [:int, :int, :int] },
+    "&"  => { int: [:int, :int, :int] },
+    "^"  => { int: [:int, :int, :int] },
+    "|"  => { int: [:int, :int, :int] },
+  }
+
+  def initialize(parser)
+    @parser = parser
+  end
+
+  def error(loc, msg)
+    @parser.error(msg, loc)
+  end
+
+  def check(env, expr, type)
+#    if (expr.is_a? IR::If)
+#      check_ifexpr(env, expr, type)
+#    elsif (expr.is_a? IR::Func)
+#      check_func(env, expr, type)
+#    elsif (expr.is_a? IR::Var)
+#      check_var(env, expr, type)
+#    elsif (expr.is_a? IR::Let)
+#      check_let(env, expr, type)
+##    elsif (expr.is_a? IR::Apply)
+##      check_apply(env, expr, type)
+
+    if (expr.is_a? IR::Op)
+      check_op(env, expr, type)
+    else
+      etype = infer(env, expr)
+      if type != etype
+        error(expr.loc, "expected #{type}, received #{etype}")
+      end
+    end
+    expr.type = type
+  end
+#
+  def infer(env, expr)
+    if expr.is_a? IR::Const
+      infer_const(env, expr)
+    elsif (expr.is_a? IR::Op)
+      infer_op(env, expr)
+
+#    elsif expr.is_a? IR::Var
+#      infer_var(env, expr)
+#    elsif expr.is_a? IR::Let
+#      infer_let(env, expr)
+#    elsif expr.is_a? IR::If
+#      infer_ifexpr(env, expr)
+#    elsif expr.is_a? IR::Set
+#      infer_set(env, expr)
+#    elsif expr.is_a? IR::Func
+#      infer_func(env, expr)
+#    elsif expr.is_a? IR::Apply
+#      infer_apply(env, expr)
+    else
+      error(expr.loc, "unable to determine type of expression")
+    end
+  end
+
+  private
+
+#  def make_typevar()
+#    @typevar ||= 0
+#    var = "abcdefghijklmnopqrstuvwxyz"[@typevar]
+#    @typevar += 1
+#    var
+#  end
+#
+#  def var?(expr)
+#    expr.class == IR::Var
+#  end
+#
+#  def untyped_global_func?(env, func, type)
+#    type.nil? and
+#    var?(func) and
+#    env.global?(func.name) and
+#    env[func.name][:value]
+#  end
+#
+#  def check_apply(env, expr, type)
+#    # Handle global functions that haven't been typed yet but are
+#    # being called. We pause to infer their type.
+#    if untyped_global_func?(env, expr.func, type)
+#      value = env[expr.func.name][:value]
+#      env[expr.func.name][:value] = nil
+#      infer(@parser.syms, value)
+#      type = infer(env, expr.func)
+#    end
+#
+#    error(expr.loc, "object being applied is not a function (has type: #{type.to_s})") if not type.is_a? Array
+#    error(expr.loc, "wrong number of arguments to function call") if (type.length - 1) != expr.args.length
+#    type[0..-2].each_with_index do |t,i|
+#      check(env, expr.args[i], t)
+#    end
+#    expr.type = type.last
+#  end
+#
+#  def check_ifexpr(env, expr, type)
+#    check(env, expr.cond, :bool)
+#    check(env, expr.then, type)
+#    check(env, expr.else, type)
+#  end
+#
+#  def check_var(env, expr, type)
+#    etype = infer(env, expr)
+#    if (etype.class == String)
+#      expr.type = type
+#      env.set_type(expr.name, type)
+#    elsif expr.type != type
+#      error(expr.loc, "expected #{type}, received #{etype}")
+#    end
+#    type
+#  end
+#
+#  def verify(cond, loc, msg)
+#    error(loc, msg) if not cond
+#  end
+#
+#  def check_func(env, expr, type)
+#    env = env.clone
+#    verify((type.length-1) == expr.args.length, expr.loc,
+#      "incorrect number of arguments (#{expr.args.length}, expected #{(type.length-1)}")
+#    expr.args.each_with_index do |a,i|
+#      env.add_sym(a.name, a.loc, :arg, type[i])
+#    end
+#    check(env, expr.expr, type.last)
+#  end
+#
+#  def check_let(env, let, type)
+#    env = env.clone
+#    env.add_sym(let.var.name, let.var.loc, :var, let.var.type)
+#    check(env, let.expr, type)
+#  end
+
+  def infer_const(env, expr)
+    expr.type
+  end
+
+  def infer_op(env, expr)
+    # infer the operand type first
+    vtype = infer(env, expr.left)
+    if (expr.left and expr.right)
+      check_binary(env, expr, vtype)
+    else
+      check_unary(env, expr, vtype)
+    end
+  end
+
+
+#  def infer_var(env, expr)
+#    if not env.defined?(expr.name)
+#      error(expr.loc, "symbol '#{expr.name}' not defined")
+#    end
+#    expr.type = env[expr.name][:type]
+#  end
+#
+#  def infer_let(env, let)
+#    if let.body.nil?
+#      infer_decl(env, let)
+#    else
+#      infer_let_expr(env, let)
+#    end
+#  end
+#
+#  def infer_decl(env, let)
+#    env = env.clone
+#    # handle the binding
+#    if let.var.type
+#      check(env, let.expr, let.var.type)
+#    else
+#      let.var.type = infer(env, let.expr)
+#    end
+#    env.set_type(let.var.name, let.var.type)
+#    env[let.var.name][:value] = nil
+#    let.type = :void
+#  end
+#
+#  def infer_let_expr(env, let)
+#    env = env.clone
+#
+#    # handle the binding
+#    if let.var.type
+#      check(env, let.expr, let.var.type)
+#    else
+#      let.var.type = infer(env, let.expr)
+#    end
+#
+#    env.add_sym(let.var.name, let.var.loc, :var, let.var.type)
+#    let.type = infer(env, let.body)
+#  end
+#
+#  def infer_ifexpr(env, expr)
+#    check(env, expr, infer(env, expr.then))
+#  end
+#
+#  def infer_set(env, expr)
+#    error(expr.loc, "infer_set unimplemented")
+#  end
+#
+#  def infer_func(env, expr)
+#    env = env.clone
+#    @typevar = 0
+#    expr.args.each do |a|
+#      a.type ||= make_typevar()
+#      env.add_sym(a.name, a.loc, :arg, a.type)
+#    end
+#    infer(env, expr.expr)
+#    type = (expr.args + [expr.expr]).map {|v| v.type }
+#    type.unshift(:void) if type.length == 1
+#
+#    # the body may have inferred an arg type, fix it up here
+#    expr.args.each_with_index do |a,i|
+#      a.type = env[a.name][:type]
+#      type[i] = a.type
+#    end
+#    expr.type = type
+#  end
+#
+#  def infer_apply(env, expr)
+#    if expr.func.is_a? String
+#      expr.type = infer_opcall(env, expr)
+#    else
+#      type = infer(env, expr.func)
+#      check_apply(env, expr, type)
+#    end
+#  end
+#
+#  def assign_type(env, var, type)
+#    if var.class == IR::Var and (var.type.nil? or var.type == String) then
+#      var.type = type
+#      env[var.name][:type] = type
+#    end
+#  end
+
+
+  def check_unary(env, expr, vtype)
+    optype = UnaryOps[expr.op][TypesToBase[vtype]]
+    error(expr.loc, "unknown unary operation '#{expr.op}' for operand type #{vtype}") if not optype
+    optype = optype.map{|v| BaseToTypes[v] }
+    check(env, expr.left,  optype[0])
+    expr.type = optype[-1]
+  end
+
+  def check_binary(env, expr, vtype)
+    pp expr
+    optype = BinaryOps[expr.op][TypesToBase[vtype]]
+    error(expr.loc, "unknown binary operation '#{expr.op}' for operand type #{vtype}") if optype.nil?
+    optype = optype.map{|v| BaseToTypes[v] }
+    check(env, expr.left,  optype[0])
+    check(env, expr.right, optype[1])
+    expr.type = optype[-1]
+  end
+end
+
+
+##
+# Code Generation Module
+##
+
 module Codegen
   State = Struct.new(:label, :locals, :syms)
 
@@ -988,6 +1032,11 @@ module Codegen
   end
 end
 
+
+##
+# Emit the Code
+##
+
 $parser = Parser.new("cerise.m")
 state = Codegen.init($parser.syms)
 $parser.syms.each do |name, val|
-- 
2.52.0