This shows you the differences between two versions of the page.
Next revision | Previous revision Next revision Both sides next revision | ||
cs330_f2016:lab16shell [2017/04/17 22:38] dhart created |
cs330_f2016:lab16shell [2018/04/10 19:33] morse |
||
---|---|---|---|
Line 1: | Line 1: | ||
<file type_checker.jl> | <file type_checker.jl> | ||
- | |||
- | # If you're getting errors about not being able to load this, you may | ||
- | # need to add the current directory to the module load path: | ||
# | # | ||
- | # push!(LOAD_PATH, ".") | + | # Class Interpreter - Type Checker |
- | # | + | |
- | # This is how I make sure it's reloaded when something changes: | + | |
- | # workspace(); reload("CITypes"); using CITypes | + | |
- | # | + | |
- | # This is a helper function to run through a bunch of tests in a file: | + | |
- | # CITypes.testf( "./tests.txt" ) | + | |
# | # | ||
- | module CITypes # based on the CI5 interpreter | + | module CITypes # based on the CI3 interpreter |
using Error | using Error | ||
using Lexer | using Lexer | ||
- | export parse, type_of_expr, NumType, BoolType, FunType, NListType | + | export parse, type_of_expr, NumType, BoolType, FuncType, NListType |
# =================================================== | # =================================================== | ||
- | abstract AE | + | abstract type AE |
- | abstract TypeVal | + | end |
- | abstract TypeEnvironment | + | |
- | # =================================================== | + | abstract type TypeVal |
- | + | end | |
- | # AST nodes for expressions | + | |
- | type Num <: AE | + | # <expr> ::= <number> |
+ | type NumNode <: AE | ||
n::Real | n::Real | ||
end | end | ||
- | type Boolean <: AE | + | # <expr> ::= true |
+ | # <expr> ::= false | ||
+ | type BooleanNode <: AE | ||
v::Bool | v::Bool | ||
end | end | ||
- | type Plus <: AE | + | # <expr> ::= (+ <expr> <expr>) |
- | lhs::AE | + | type PlusNode <: AE |
- | rhs::AE | + | lhs::AE |
+ | rhs::AE | ||
end | end | ||
- | type Minus <: AE | + | # <expr> ::= (- <expr> <expr>) |
- | lhs::AE | + | type MinusNode <: AE |
- | rhs::AE | + | lhs::AE |
+ | rhs::AE | ||
end | end | ||
- | type IsZero <: AE | + | # <expr> ::= (iszero <expr>) |
+ | type IsZeroNode <: AE | ||
arg::AE | arg::AE | ||
end | end | ||
- | type IfB <: AE | + | # <expr> ::= (ifb <expr> <expr> <expr>) |
- | condition::AE | + | type IfBNode <: AE |
- | true_branch::AE | + | cond::AE |
- | false_branch::AE | + | zerobranch::AE |
+ | nzerobranch::AE | ||
end | end | ||
- | type With <: AE | + | # <expr> ::= (with <id> <expr> <expr>) |
- | name::Symbol | + | type WithNode <: AE |
- | binding_expr::AE | + | sym::Symbol |
- | body::AE | + | binding_expr::AE |
+ | body::AE | ||
end | end | ||
- | type Id <: AE | + | # <expr> ::= <id> |
- | name::Symbol | + | type VarRefNode <: AE |
+ | sym::Symbol | ||
end | end | ||
- | type FunDef <: AE | + | # <expr> ::= (lambda <id> : <type> <expr>) |
+ | type FuncDefNode <: AE | ||
formal_parameter::Symbol | formal_parameter::Symbol | ||
formal_type::TypeVal | formal_type::TypeVal | ||
- | fun_body::AE | + | body::AE |
end | end | ||
- | type FunApp <: AE | + | # <expr> ::= (<expr> <expr>) |
- | fun_expr::AE | + | type FuncAppNode <: AE |
- | arg_expr::AE | + | fun_expr::AE |
+ | arg_expr::AE | ||
end | end | ||
- | type NEmpty <: AE | + | # <expr> ::= nempty |
+ | type NEmptyNode <: AE | ||
end | end | ||
- | type NIsEmpty <: AE | + | # <expr> ::= (nisempty <expr>) |
+ | type NIsEmptyNode <: AE | ||
list::AE | list::AE | ||
end | end | ||
- | type NCons <: AE | + | # <expr> ::= (ncons <expr> <expr>) |
+ | type NConsNode <: AE | ||
f::AE | f::AE | ||
r::AE | r::AE | ||
end | end | ||
- | type NFirst <: AE | + | # <expr> ::= (nfirst <expr>) |
+ | type NFirstNode <: AE | ||
list::AE | list::AE | ||
end | end | ||
- | type NRest <: AE | + | # <expr> ::= (nrest <expr>) |
+ | type NRestNode <: AE | ||
list::AE | list::AE | ||
end | end | ||
Line 100: | Line 105: | ||
# =================================================== | # =================================================== | ||
- | # AST nodes for types (used for type information as well) | + | # <type> ::= number |
type NumType <: TypeVal | type NumType <: TypeVal | ||
end | end | ||
+ | # <type> ::= boolean | ||
type BoolType <: TypeVal | type BoolType <: TypeVal | ||
end | end | ||
- | type FunType <: TypeVal | + | # <type> ::= (<type> : <type>) |
+ | type FuncType <: TypeVal | ||
arg_type::TypeVal | arg_type::TypeVal | ||
result_type::TypeVal | result_type::TypeVal | ||
end | end | ||
+ | # <type> ::= nlist | ||
type NListType <: TypeVal | type NListType <: TypeVal | ||
end | end | ||
Line 118: | Line 125: | ||
# =================================================== | # =================================================== | ||
- | # Type Environments | + | abstract type TypeEnvironment |
+ | end | ||
- | type mtTypeEnvironment <: TypeEnvironment | + | type EmptyTypeEnv <: TypeEnvironment |
end | end | ||
- | type CTypeEnvironment <: TypeEnvironment | + | type ExtendedTypeEnv <: TypeEnvironment |
- | name::Symbol | + | sym::Symbol |
- | value::TypeVal | + | val::TypeVal |
- | parent::TypeEnvironment | + | parent::TypeEnvironment |
end | end | ||
Line 132: | Line 140: | ||
# Parser for expressions | # Parser for expressions | ||
- | # functional for valid input, doesn't fully reject bad input) | + | # Functional for valid input, doesn't fully reject bad input |
- | function parse( expr::Real ) | + | function parse( expr::Number ) |
- | return Num( expr ) | + | return NumNode( expr ) |
end | end | ||
function parse( expr::Bool ) | function parse( expr::Bool ) | ||
- | return Boolean( expr ) | + | return BooleanNode( expr ) |
end | end | ||
function parse( expr::Symbol ) | function parse( expr::Symbol ) | ||
if expr == :nempty | if expr == :nempty | ||
- | return NEmpty() | + | return NEmptyNode() |
else | else | ||
- | return Id( expr ) | + | return VarRefNode( expr ) |
end | end | ||
end | end | ||
Line 157: | Line 165: | ||
lhs = parse( expr[2] ) | lhs = parse( expr[2] ) | ||
rhs = parse( expr[3] ) | rhs = parse( expr[3] ) | ||
- | return Plus( lhs, rhs ) | + | return PlusNode( lhs, rhs ) |
elseif op_symbol == :- | elseif op_symbol == :- | ||
lhs = parse( expr[2] ) | lhs = parse( expr[2] ) | ||
rhs = parse( expr[3] ) | rhs = parse( expr[3] ) | ||
- | return Minus( lhs, rhs ) | + | return MinusNode( lhs, rhs ) |
elseif op_symbol == :iszero | elseif op_symbol == :iszero | ||
arg = parse( expr[2] ) | arg = parse( expr[2] ) | ||
- | return IsZero( arg ) | + | return IsZeroNode( arg ) |
elseif op_symbol == :ifb | elseif op_symbol == :ifb | ||
Line 172: | Line 180: | ||
true_branch = parse( expr[3] ) | true_branch = parse( expr[3] ) | ||
false_branch = parse( expr[4] ) | false_branch = parse( expr[4] ) | ||
- | return IfB( condition, true_branch, false_branch ) | + | return IfBNode( condition, true_branch, false_branch ) |
- | elseif op_symbol == :with # (with x (+ 5 1) (+ x x) ) | + | elseif op_symbol == :with |
sym = expr[2] | sym = expr[2] | ||
binding_expr = parse( expr[3] ) | binding_expr = parse( expr[3] ) | ||
body = parse( expr[4] ) | body = parse( expr[4] ) | ||
- | return With( sym, binding_expr, body ) | + | return WithNode( sym, binding_expr, body ) |
elseif op_symbol == :lambda | elseif op_symbol == :lambda | ||
Line 184: | Line 192: | ||
formal_type = parse_type(expr[4]) | formal_type = parse_type(expr[4]) | ||
body = parse(expr[5]) | body = parse(expr[5]) | ||
- | return FunDef( formal, formal_type, body ) | + | return FuncDefNode( formal, formal_type, body ) |
elseif op_symbol == :ncons | elseif op_symbol == :ncons | ||
f = parse(expr[2]) | f = parse(expr[2]) | ||
r = parse(expr[3]) | r = parse(expr[3]) | ||
- | return NCons( f, r ) | + | return NConsNode( f, r ) |
elseif op_symbol == :nisempty | elseif op_symbol == :nisempty | ||
list = parse(expr[2]) | list = parse(expr[2]) | ||
- | return NIsEmpty( list ) | + | return NIsEmptyNode( list ) |
elseif op_symbol == :nfirst | elseif op_symbol == :nfirst | ||
list = parse(expr[2]) | list = parse(expr[2]) | ||
- | return NFirst( list ) | + | return NFirstNode( list ) |
elseif op_symbol == :nrest | elseif op_symbol == :nrest | ||
list = parse(expr[2]) | list = parse(expr[2]) | ||
- | return NRest( list ) | + | return NRestNode( list ) |
else | else | ||
- | return FunApp( parse(expr[1]), parse(expr[2]) ) | + | return FuncAppNode( parse(expr[1]), parse(expr[2]) ) |
end | end | ||
Line 228: | Line 236: | ||
function parse_type( t :: Array{Any} ) | function parse_type( t :: Array{Any} ) | ||
- | return FunType( parse_type(t[1]), | + | return FuncType( parse_type(t[1]), |
parse_type(t[3])) | parse_type(t[3])) | ||
end | end | ||
Line 241: | Line 249: | ||
function type_of_expr( ast::AE ) | function type_of_expr( ast::AE ) | ||
- | return type_of_expr( ast, mtTypeEnvironment() ) | + | return type_of_expr( ast, EmptyTypeEnv() ) |
end | end | ||
- | function type_of_expr( ae::Num, env::TypeEnvironment ) | + | function type_of_expr( ast::NumNode, env::TypeEnvironment ) |
return NumType() | return NumType() | ||
end | end | ||
- | function type_of_expr( ae::Boolean, env::TypeEnvironment ) | + | function type_of_expr( ast::BooleanNode, env::TypeEnvironment ) |
return BoolType() | return BoolType() | ||
end | end | ||
- | function type_of_expr( ae::Plus, env::TypeEnvironment ) | + | function type_of_expr( ast::PlusNode, env::TypeEnvironment ) |
- | left = type_of_expr( ae.lhs, env ) | + | left = type_of_expr( ast.lhs, env ) |
- | right = type_of_expr( ae.rhs, env ) | + | right = type_of_expr( ast.rhs, env ) |
return type_of_math_expr( left, right ) | return type_of_math_expr( left, right ) | ||
end | end | ||
- | function type_of_expr( ae::Minus, env::TypeEnvironment ) | + | function type_of_expr( ast::MinusNode, env::TypeEnvironment ) |
- | left = type_of_expr( ae.lhs, env ) | + | left = type_of_expr( ast.lhs, env ) |
- | right = type_of_expr( ae.rhs, env ) | + | right = type_of_expr( ast.rhs, env ) |
return type_of_math_expr( left, right ) | return type_of_math_expr( left, right ) | ||
end | end | ||
Line 270: | Line 278: | ||
# Helper function for comparing two type values recursively if necessary | # Helper function for comparing two type values recursively if necessary | ||
- | same_type( t1::FunType, t2::FunType ) = | + | same_type( t1::FuncType, t2::FuncType ) = |
(same_type( t1.arg_type, t2.arg_type ) | (same_type( t1.arg_type, t2.arg_type ) | ||
&& same_type( t1.result_type, t2.result_type )) | && same_type( t1.result_type, t2.result_type )) | ||
Line 297: | Line 305: | ||
function type_of_expr( expr::AbstractString ) | function type_of_expr( expr::AbstractString ) | ||
return type_of_expr( parse( Lexer.lex(expr) ) ) | return type_of_expr( parse( Lexer.lex(expr) ) ) | ||
+ | end | ||
+ | |||
+ | # evaluate a series of tests in a file | ||
+ | function typef( fn::AbstractString ) | ||
+ | f = open( fn ) | ||
+ | |||
+ | cur_prog = "" | ||
+ | for ln in eachline(f) | ||
+ | ln = chomp( ln ) | ||
+ | if length(ln) == 0 && length(cur_prog) > 0 | ||
+ | println( "" ) | ||
+ | println( "--------- Evaluating ----------" ) | ||
+ | println( cur_prog ) | ||
+ | println( "---------- Returned -----------" ) | ||
+ | try | ||
+ | println( type_of_expr( cur_prog ) ) | ||
+ | catch errobj | ||
+ | println( ">> ERROR: lxd" ) | ||
+ | lxd = Lexer.lex( cur_prog ) | ||
+ | println( lxd ) | ||
+ | println( ">> ERROR: ast" ) | ||
+ | ast = parse( lxd ) | ||
+ | println( ast ) | ||
+ | println( ">> ERROR: rethrowing error" ) | ||
+ | throw( errobj ) | ||
+ | end | ||
+ | println( "------------ done -------------" ) | ||
+ | println( "" ) | ||
+ | cur_prog = "" | ||
+ | else | ||
+ | cur_prog *= ln | ||
+ | end | ||
+ | end | ||
+ | |||
+ | close( f ) | ||
end | end | ||