Differences

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

--- cs330_f2016:lab16shell [2017/04/17 22:38]
dhart created
+++ cs330_f2016:lab16shell [2021/06/30 23:42]
@@ Line 1: / Line 1: @@
-<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, ".")
-#
-# 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
-</file>

BYU CS classes

User Tools

Site Tools

Differences

Page Tools