This is an old revision of the document!
# 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, ".") # # 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 using Error using Lexer export parse, type_of_expr, NumType, BoolType, FunType, NListType # =================================================== abstract AE abstract TypeVal abstract TypeEnvironment # =================================================== # AST nodes for expressions type Num <: AE n::Real end type Boolean <: AE v::Bool end type Plus <: AE lhs::AE rhs::AE end type Minus <: AE lhs::AE rhs::AE end type IsZero <: AE arg::AE end type IfB <: AE condition::AE true_branch::AE false_branch::AE end type With <: AE name::Symbol binding_expr::AE body::AE end type Id <: AE name::Symbol end type FunDef <: AE formal_parameter::Symbol formal_type::TypeVal fun_body::AE end type FunApp <: AE fun_expr::AE arg_expr::AE end type NEmpty <: AE end type NIsEmpty <: AE list::AE end type NCons <: AE f::AE r::AE end type NFirst <: AE list::AE end type NRest <: AE list::AE end # =================================================== # AST nodes for types (used for type information as well) type NumType <: TypeVal end type BoolType <: TypeVal end type FunType <: TypeVal arg_type::TypeVal result_type::TypeVal end type NListType <: TypeVal end # =================================================== # Type Environments type mtTypeEnvironment <: TypeEnvironment end type CTypeEnvironment <: TypeEnvironment name::Symbol value::TypeVal parent::TypeEnvironment end # =================================================== # Parser for expressions # functional for valid input, doesn't fully reject bad input) function parse( expr::Real ) return Num( expr ) end function parse( expr::Bool ) return Boolean( expr ) end function parse( expr::Symbol ) if expr == :nempty return NEmpty() else return Id( expr ) end end function parse( expr::Array{Any} ) op_symbol = expr[1] if op_symbol == :+ lhs = parse( expr[2] ) rhs = parse( expr[3] ) return Plus( lhs, rhs ) elseif op_symbol == :- lhs = parse( expr[2] ) rhs = parse( expr[3] ) return Minus( lhs, rhs ) elseif op_symbol == :iszero arg = parse( expr[2] ) return IsZero( arg ) elseif op_symbol == :ifb condition = parse( expr[2] ) true_branch = parse( expr[3] ) false_branch = parse( expr[4] ) return IfB( condition, true_branch, false_branch ) elseif op_symbol == :with # (with x (+ 5 1) (+ x x) ) sym = expr[2] binding_expr = parse( expr[3] ) body = parse( expr[4] ) return With( sym, binding_expr, body ) elseif op_symbol == :lambda formal = expr[2] formal_type = parse_type(expr[4]) body = parse(expr[5]) return FunDef( formal, formal_type, body ) elseif op_symbol == :ncons f = parse(expr[2]) r = parse(expr[3]) return NCons( f, r ) elseif op_symbol == :nisempty list = parse(expr[2]) return NIsEmpty( list ) elseif op_symbol == :nfirst list = parse(expr[2]) return NFirst( list ) elseif op_symbol == :nrest list = parse(expr[2]) return NRest( list ) else return FunApp( parse(expr[1]), parse(expr[2]) ) end end function parse( expr::Any ) throw( LispError("Invalid expression $expr") ) end # =================================================== # Parser for type expressions function parse_type( t::Symbol ) if (t == :number) return NumType() elseif (t == :boolean) return BoolType() elseif (t == :nlist) return NListType() end end function parse_type( t :: Array{Any} ) return FunType( parse_type(t[1]), parse_type(t[3])) end function parse_type( expr::Any ) throw( LispError("Invalid type $expr") ) end # =================================================== # Type checking functions (modeled after the earlier calc) function type_of_expr( ast::AE ) return type_of_expr( ast, mtTypeEnvironment() ) end function type_of_expr( ae::Num, env::TypeEnvironment ) return NumType() end function type_of_expr( ae::Boolean, env::TypeEnvironment ) return BoolType() end function type_of_expr( ae::Plus, env::TypeEnvironment ) left = type_of_expr( ae.lhs, env ) right = type_of_expr( ae.rhs, env ) return type_of_math_expr( left, right ) end function type_of_expr( ae::Minus, env::TypeEnvironment ) left = type_of_expr( ae.lhs, env ) right = type_of_expr( ae.rhs, env ) return type_of_math_expr( left, right ) end # the rest of your type-checking functions go here... # =================================================== # Helper function for comparing two type values recursively if necessary same_type( t1::FunType, t2::FunType ) = (same_type( t1.arg_type, t2.arg_type ) && same_type( t1.result_type, t2.result_type )) same_type{ T <: TypeVal }( t1::T, t2::T ) = true same_type( t1::TypeVal, t2::TypeVal ) = false # =================================================== # Type judgments (could be folded into type checking functions) function type_of_math_expr( left::NumType, right::NumType ) return NumType() end function type_of_math_expr( left::Any, right::Any ) throw( LispError("Operands for + or - must be numbers") ) end # the rest of your type-judgement functions (if you choose to separate them) go here... # =================================================== # convenience function to make everything easier function type_of_expr( expr::AbstractString ) return type_of_expr( parse( Lexer.lex(expr) ) ) end # =================================================== end # module