From 8576e0a2da3d02eb88cfec93cadf1531989c1fa5 Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Wed, 24 Jun 2020 16:49:03 -0400 Subject: [PATCH] implemented basic type checking and inference --- dyn.rb | 193 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-- dyn.src | 26 ++++---- 2 files changed, 198 insertions(+), 21 deletions(-) diff --git a/dyn.rb b/dyn.rb index 240c0e7..b593997 100755 --- a/dyn.rb +++ b/dyn.rb @@ -42,7 +42,7 @@ class Lexer if @data.scan(IDENT) type = get_id_type(@data.matched) elsif @data.scan(NUMBER) - type = :num + type = :int elsif @data.scan(STRING) type = :string elsif @data.scan(BRACES) @@ -94,7 +94,7 @@ class Parser "{" => { prefix: :constant, infix: nil, level: :none }, :nil => { prefix: :constant, infix: nil, level: :none }, :bool => { prefix: :constant, infix: nil, level: :none }, - :num => { prefix: :constant, infix: nil, level: :none }, + :int => { prefix: :constant, infix: nil, level: :none }, :string => { prefix: :constant, infix: nil, level: :none }, :char => { prefix: :constant, infix: nil, level: :none }, :byte => { prefix: :constant, infix: nil, level: :none }, @@ -132,7 +132,7 @@ class Parser error("symbol '#{expr.name}' multiply defined in scope", expr.loc) if syms[expr.name] and syms[expr.name][:loc] syms[expr.name] ||= {} syms[expr.name][:loc] = expr.loc - exprs << Call.new(expr.loc, :set!, [expr.name, expr.value]) + exprs << Call.new(expr.loc, nil, :set!, [expr.name, expr.value]) elsif expr.is_a? Ann and expr.expr.class == Symbol error("symbol '#{expr.expr}' multiply annotated in scope", expr.loc) if syms[expr.expr] and syms[expr.expr][:type] syms[expr.expr] ||= {} @@ -209,8 +209,8 @@ class Parser end def constant() - if (@prev.type == :num) - Val.new(location(), :num, @prev.text.to_f) + if (@prev.type == :int) + Val.new(location(), :int, @prev.text.to_f) elsif (@prev.type == :string) Val.new(location(), :string, @prev.text) elsif (@prev.type == :nil) @@ -326,13 +326,194 @@ class Parser end module TypeChecker + UnaryOps = { + "+" => { + int: [:int, :int], + float: [:float, :float], + }, + "-" => { + int: [:int, :int], + float: [:float, :float], + }, + "!" => { + bool: [:bool, :bool] + }, + "~" => { + int: [:int, :int, :int] + }, + } + + 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: [: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 self.check(env, expr, type) + if (expr.is_a? Parser::IfExpr) + check_ifexpr(env, expr, type) + elsif (expr.is_a? Parser::Func) + check_func(env, expr, type) + else + etype = infer(env, expr) + raise "expected #{type}, recieved #{etype}" if type != etype + end + type + end + + def self.check_ifexpr(env, expr, type) + check(env, expr.cond, :bool) + check(env, expr.br1, type) + check(env, expr.br2, type) + end + + def self.check_func(env, expr, type) + env = env.clone + type[0..-2].each_with_index do |t, i| + env[expr.args[i]] = { type: t } + end + check(env, expr.body, type.last) + end + + def self.check_call(env, expr, type) + type[0..-2].each_with_index do |t,i| + check(env, expr.args[i], t) + end + type.last end def self.infer(env, expr) + if expr.is_a? Parser::Val + infer_value(env, expr) + elsif expr.is_a? Symbol + infer_symbol(env, expr) + elsif expr.is_a? Parser::Ann + infer_annotation(env, expr) + elsif expr.is_a? Parser::Block + infer_block(env, expr) + elsif expr.is_a? Parser::Call + infer_call(env, expr) + elsif expr.is_a? Parser::IfExpr + infer_ifexpr(env, expr) + else + raise "unable to infer type of expression" + end + end + + def self.infer_value(env, expr) + expr.type + end + + def self.infer_symbol(env, expr) + raise "undefined symbol '#{expr}'" if env[expr].nil? + raise "symbol '#{expr}' has unknown type" if env[expr][:type].nil? + env[expr][:type] + end + + def infer_annotation(env, expr) + check(env, expr.expr, expr.type) + end + + def self.infer_block(env, expr) + env = env.merge(expr.syms) + types = expr.exprs.map {|e| infer(env, e) } + expr.type = types.last + end + + def self.infer_call(env, expr) + if expr.func == :set! + infer_def(env, expr) + elsif expr.func.is_a? String + infer_opcall(env, expr) + else + type = infer(env, expr.func) + check_call(env, expr, type) + end + end + + def self.infer_def(env, expr) + expr.type = env[expr.args[0]][:type] + if (expr.type) + check(env, expr.args[1], expr.type) + else + expr.type = infer(env, expr.args[1]) + end + end + + def self.infer_opcall(env, expr) + ltype = infer(env, expr.args[0]) + if expr.args.length == 1 + optype = UnaryOps[expr.func][ltype] + raise "unknown unary operation '#{expr.func}' for operand type #{ltype}" if not optype + check_call(env, expr, optype) + elsif expr.args.length == 2 + optype = BinaryOps[expr.func][ltype] + raise "unknown binary operation '#{expr.func}' for operand type #{ltype}" if not optype + check_call(env, expr, optype) + else + raise "too many operands for operator '#{expr.func}'" + end + end + + def self.infer_ifexpr(env, expr) + check(env, expr, infer(env, expr.br1)) end end parse = Parser.new("dyn.src") block = Parser.new("dyn.src").toplevel -TypeChecker.infer({}, block) +pp TypeChecker.infer({}, block) + + +# TODO: +# * refine rules for use of variables before definition and mutually recursive procedures... \ No newline at end of file diff --git a/dyn.src b/dyn.src index c7d7885..f672b78 100644 --- a/dyn.src +++ b/dyn.src @@ -5,7 +5,6 @@ false 123 123.0 "foo" -a = 1 #b = [1,2,3] #{ "foo": 123, foo: 24 } @@ -18,27 +17,24 @@ e = (-1) f = (+1) # conditionals -if (1) { +if (true) { 2 -} else if (1) { - asd - asd +} else if (true) { 21 } else { 1 } - -# functions and application -println("foo!") -print(1,2,3,4,5,6,7,8,9) - +## functions and application +##println("foo!") +##print(1,2,3,4,5,6,7,8,9) +# foo1 : int -> int foo1 = fun(a) { b = 123 - println("hi!") +# println("hi!") } - -# TODO: -# * Get rid of end keyword -# * Replace with single or multi-expression blocks +# +## TODO: +## * Get rid of end keyword +## * Replace with single or multi-expression blocks -- 2.54.0