BYU CS classes

User Tools

Site Tools

Trace:
cs330_f2016:lab16shell

Differences

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

Link to this comparison view

Next revision Both sides next revision
cs330_f2016:lab16shell [2017/04/17 22:38]
dhart created 		cs330_f2016:lab16shell [2018/04/06 02:25]
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 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
  
cs330_f2016/lab16shell.txt · Last modified: 2021/06/30 23:42 (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