BYU CS classes

User Tools

Site Tools

Trace: • lab16shell
cs330_f2016:lab16shell

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision 		Previous revision
cs330_f2016:lab16shell [2017/04/17 22:38]
dhart created 		cs330_f2016:lab16shell [2021/06/30 23:42] (current)
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 
 + 
 +push!(LOAD_PATH,​ pwd())
  
 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>​ 
 +struct NumNode ​<: AE
   n::Real   n::Real
 end end
  
-type Boolean ​<: AE+# <​expr>​ ::= true 
 +# <​expr>​ ::= false 
 +struct BooleanNode ​<: AE
   v::Bool   v::Bool
 end end
  
-type Plus <: AE +# <​expr>​ ::= (+ <​expr>​ <​expr>​) 
-  lhs::AE +struct PlusNode ​<: AE 
-  rhs::AE+    lhs::AE 
 +    rhs::AE
 end end
  
-type Minus <: AE +# <​expr>​ ::= (- <​expr>​ <​expr>​) 
-  lhs::AE +struct MinusNode ​<: AE 
-  rhs::AE+    lhs::AE 
 +    rhs::AE
 end end
  
-type IsZero ​<: AE+# <​expr>​ ::= (iszero <​expr>​) 
 +struct IsZeroNode ​<: AE
   arg::AE   arg::AE
 end end
  
-type IfB <: AE +# <​expr>​ ::= (ifb <​expr>​ <​expr>​ <​expr>​) 
-  ​condition::AE +struct 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 +struct WithNode ​<: AE 
-  binding_expr::​AE +    sym::Symbol 
-  body::AE+    binding_expr::​AE 
 +    body::AE
 end end
  
-type Id <: AE +# <​expr>​ ::= <​id>​ 
-  name::Symbol+struct VarRefNode ​<: AE 
 +    sym::Symbol
 end end
  
-type FunDef ​<: AE+# <​expr>​ ::= (lambda <id> : <type> <​expr>​) 
 +struct 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 +struct FuncAppNode ​<: AE 
-  arg_expr::​AE+    fun_expr::​AE 
 +    arg_expr::​AE
 end end
  
-type NEmpty ​<: AE+# <​expr>​ ::= nempty 
 +struct NEmptyNode ​<: AE
 end end
  
-type NIsEmpty ​<: AE+# <​expr>​ ::= (nisempty <​expr>​) 
 +struct NIsEmptyNode ​<: AE
   list::AE   list::AE
 end end
  
-type NCons <: AE+# <​expr>​ ::= (ncons <​expr>​ <​expr>​) 
 +struct NConsNode ​<: AE
   f::AE   f::AE
   r::AE   r::AE
 end end
  
-type NFirst ​<: AE+# <​expr>​ ::= (nfirst <​expr>​) 
 +struct NFirstNode ​<: AE
   list::AE   list::AE
 end end
  
-type NRest <: AE+# <​expr>​ ::= (nrest <​expr>​) 
 +struct NRestNode ​<: AE
   list::AE   list::AE
 end end
Line 100: Line 107:
 # =================================================== # ===================================================
  
-# AST nodes for types (used for type information as well) +# <type> ::= number 
- +struct ​NumType <: TypeVal
-type NumType <: TypeVal+
 end end
  
-type BoolType <: TypeVal+# <type> ::= boolean 
 +struct ​BoolType <: TypeVal
 end end
  
-type FunType ​<: TypeVal+# <type> ::= (<​type>​ : <​type>​) 
 +struct FuncType ​<: TypeVal
   arg_type::​TypeVal   arg_type::​TypeVal
   result_type::​TypeVal   result_type::​TypeVal
 end end
  
-type NListType <: TypeVal+# <type> ::= nlist 
 +struct ​NListType <: TypeVal
 end end
  
 # =================================================== # ===================================================
  
-# Type Environments+abstract type TypeEnvironment 
 +end
  
-type mtTypeEnvironment ​<: TypeEnvironment+struct EmptyTypeEnv ​<: TypeEnvironment
 end end
  
-type CTypeEnvironment ​<: TypeEnvironment +struct ExtendedTypeEnv ​<: TypeEnvironment 
-  name::Symbol +    sym::Symbol 
-  value::TypeVal +    val::TypeVal 
-  parent::​TypeEnvironment+    parent::​TypeEnvironment
 end end
  
Line 132: Line 142:
  
 # 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 167:
     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 182:
     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 194:
     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 238:
  
 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 251:
  
 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 280:
 # 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 ))
  
-same_type{ T <: TypeVal }( t1::T, t2::T ) = true+same_type( t1::T, t2::T ) where {T <: TypeVal} ​= true
  
 same_type( t1::​TypeVal,​ t2::TypeVal ) = false same_type( t1::​TypeVal,​ t2::TypeVal ) = false
Line 297: Line 307:
 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
  
cs330_f2016/lab16shell.1492468737.txt.gz · Last modified: 2021/06/30 23:40 (external edit)

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki