Goal: detect whether there will be errors in any execution

Starting point: our interpreter from Handling Scopes in Interpreters

/* What did we do compared to interpreter:
    - erased concrete values in IntValue, BoolValue
    - erased the use of concrete values in evalExpr, checkType
    - checking types and initialization earlier: for every getVar
    - handling of if statements
    - procedure calls: 
        - check parameters at call (in insertArgs)
    - not visiting one procedure twice: ensures termination
    - visiting even procedures that are not called (not done, should be):
        - manufacture initialized arguments
*/
object SemanticAnalyzer {
  type Ident = String
 
  case class Program(classes : List[ClassDef], classToRun : Ident)
 
  case class ClassDef(name : Ident, decls : List[ClassDecl])
 
  sealed abstract class Typ
  case object IntType extends Typ
  case object BoolType extends Typ
  case object VoidType extends Typ
 
  case class VarDecl(name : Ident, tp : Typ)
 
  sealed abstract class ClassDecl
  case class FieldDecl(decl : VarDecl) extends ClassDecl
  case class MethodDecl(name : Ident, 
			args : List[VarDecl],
			result : Typ,
		        body : Statement) extends ClassDecl
 
  sealed abstract class Statement
  case class DeclStat(decl : VarDecl) extends Statement
  case class AssignStat(lhs : Ident, rhs : Expression) extends Statement
  case class PrintStat(id : Expression) extends Statement
  case class IfStat(cond : Expression, 
		    trueS : Statement,
		    falseS : Statement) extends Statement
  // lhs = className.methodName(args)
  case class CallStat(lhs : Ident,
		      className : Ident,
		      methodName : Ident,
		      args : List[Expression]) extends Statement
  case class ReturnStat(expr : Expression) extends Statement
  case class BlockStat(sts : List[Statement]) extends Statement
 
  sealed abstract class Expression
  case class Var(name : Ident) extends Expression
  case class IntConst(c : Int) extends Expression
  case class Plus(e1 : Expression, e2 : Expression) extends Expression
  case class BoolConst(c : Boolean) extends Expression
  case class Leq(e1 : Expression, e2 : Expression) extends Expression
  case class And(e1 : Expression, e2 : Expression) extends Expression
 
  sealed abstract class Value
  case object IntValue extends Value  // no actual value
  case object BoolValue extends Value // no actual value
  case object UnitValue extends Value 
  case object Uninitialized extends Value
 
  sealed abstract class EnvEntry
  case class ClassEntry(cd : ClassDef) extends EnvEntry
  case class VarEntry(decl : VarDecl, var v : Value) extends EnvEntry
  case class MethodEntry(md : MethodDecl, 
			 var visited : Boolean) extends EnvEntry
 
  type Env = Map[Ident,EnvEntry]
 
  def varsAsNiceString(e : Env) : String = {
    var res = "{"
    for ((k,v) <- e) {
      v match {
	case VarEntry(vd,v) => {res = res + "" + k + " <- " + v + ",\n"}
	case _ => ()
      }
    }
    res = res + "}"
    res
  }
 
  def error(s : String) = { 
    println(s) 
    println("Fatal error, exiting!")
    exit(-1)
  }
 
  // check that v is initialized and has type t
  def checkType(v : Value, t : Typ) : Unit = {
    (v,t) match {
      case (IntValue,IntType) => ()
      case (BoolValue,BoolType) => ()
      case (UnitValue,VoidType) => ()
      case (Uninitialized,_) => error("Uninitialized value")
      case (_,_) => error("type error: have " + v + " expected " + t)
    }
  }
  def getValueForType(t : Typ) : Value = {
    t match {
      case IntType => IntValue
      case BoolType => BoolValue
      case VoidType => UnitValue
    }
  }
 
  def printIntValue(v : Value) : Unit = {
    v match {
      case IntValue => ()
      case _ => error("argument of print must be int but was " + v)
    }
  }
  def qualify(cl : String, n : String) = { cl + "$" + n}
  def getVar(e : Env, n : Ident) : VarEntry = {
    e(n) match {
      case (ve : VarEntry) => ve
      case _ => error("Could not find variable n ")
    }
  }
  def getClass(e : Env, n : Ident) : ClassEntry = {
    e(n) match {
      case (ce : ClassEntry) => ce
      case _ => error("Could not find class " + n)
    }
  }
 
  def makeClassEntries(p : Program) : Env = {
    var e : Map[Ident,EnvEntry] = Map()
    for (c <- p.classes) {
      e = e + (c.name -> ClassEntry(c))
      for (d <- c.decls) {
	e = e + (d match {
	  case FieldDecl(d) => 
	    qualify(c.name, d.name) -> VarEntry(d,Uninitialized)
	  case (md : MethodDecl) => 
	    qualify(c.name, md.name) -> MethodEntry(md,false)
	})
      }
    }
    e
  }
 
  // insert unqualified names for a class
  def withClassScope(e0 : Env, className : Ident) : Env = {
    var e = e0
    val ce : ClassEntry = getClass(e0, className)
    for (d <- ce.cd.decls) {
      d match {
	case FieldDecl(d) => 
	  e = e + (d.name -> e(qualify(className, d.name)))
	case (md : MethodDecl) => 
	  e = e + (md.name -> e(qualify(className, md.name)))
      }
    }
    e
  }
 
  def insertArgs(e : Env,
		 formals : List[VarDecl], 
		 actuals : List[Value]) : Env = {
     (formals,actuals) match {
       case (Nil,Nil) => e
       case (VarDecl(n,t)::vds,v::vs) => {
	 checkType(v,t)
	 insertArgs(e + (n -> VarEntry(VarDecl(n,t),v)),
		    vds,vs)
       }
       case (_,Nil) => error("More formals than actuals")
       case (Nil,_) => error("More actuals than formals")
     }
   }
 
  def interpExpr(e : Env)(expr : Expression) : Value = {
    expr match {
      case Var(n) => {
	val v = getVar(e, n).v
	v match {
	  case Uninitialized => error("Possible read of " + 
				      "uninitalized variable " + n)
	  case _ => v 
	}
      }
      case IntConst(i) => IntValue
      case Plus(expr1,expr2) => {
	 (interpExpr(e)(expr1),interpExpr(e)(expr2)) match {
	   case (IntValue,IntValue) => IntValue
	   case (_,_) => error("type error: arguments of '+'"+
			       "are not both integers, tried '" + 
			       expr1 + " + " + expr2 +"'" + " in env" +
			       varsAsNiceString(e))
	 }
       }
       case BoolConst(b) => BoolValue
       case Leq(expr1, expr2) => {
	 (interpExpr(e)(expr1),interpExpr(e)(expr2)) match {
	   case (IntValue,IntValue) => BoolValue
	   case (_,_) => error("type error: arguments of '<='"+
			       "are not both integers!")
	 }
       }
       case And(expr1, expr2) => {
	 (interpExpr(e)(expr1),interpExpr(e)(expr2)) match {
	   case (BoolValue,BoolValue) => BoolValue
	   case (_,_) => error("type error: arguments of '&&'"+
			       "are not both booleans!")
	 }
       }
     }
  }
 
  def interpCall(e : Env, className : Ident, methodName : Ident, 
		 actualArgs : List[Value]) : Value = {
    val me = e(qualify(className,methodName)) match {
      case (me : MethodEntry) => me
      case _ => error("Unknown method " + qualify(className,methodName))
    }
    val md = me.md
    val e1 =  withClassScope(e, className)
    val e2 = insertArgs(e1, md.args, actualArgs)
    if (!me.visited) {
      me.visited = true
      val res = interpStats(e2, UnitValue, List(md.body))
      checkType(res, md.result)
      res
    } else {
      getValueForType(md.result) // manufacturing value for type
    }
  }
 
  def interpStats(e : Env, v : Value, 
		  stmts : List[Statement]) : Value = {
   stmts match {
	case Nil => v
	case stmt::stmts1 => {
          stmt match {
	    case DeclStat(VarDecl(n,t)) =>
	      interpStats(e + (n -> VarEntry(VarDecl(n,t),Uninitialized)),
			   v, stmts1)
	    case AssignStat(id,rhs) => {
	      val ve = getVar(e,id)
	      val res = interpExpr(e)(rhs)
	      checkType(res, ve.decl.tp)
	      ve.v = res
	      interpStats(e, UnitValue, stmts1)
	    }
	    case PrintStat(expr) => { 
	      printIntValue(interpExpr(e)(expr))
	      interpStats(e, UnitValue, stmts1)
	    }
	    case IfStat(cond,trueS,falseS) => {
	      interpExpr(e)(cond) match {
		case BoolValue => {
		  interpStats(e, UnitValue, List(trueS))
		  interpStats(e, UnitValue, List(falseS))
		  interpStats(e, UnitValue, stmts1)
		}
		case _ => error("Expected boolean as condition")
	      }
	    }
	    case CallStat(lhs,className,methodName,args) => {
	      val ve = getVar(e, lhs)
	      val res = interpCall(e, className, methodName, 
				   args.map(interpExpr(e)))
	      ve.v = res
	      interpStats(e, UnitValue, stmts1)
	    }
	    case ReturnStat(expr) => interpExpr(e)(expr)
	    case BlockStat(sts) => 
	      interpStats(e, UnitValue, sts ::: stmts1)
	  }
	}
      }
  }
 
  def interpret(p : Program) = {
    var e0 : Env = makeClassEntries(p)
    val v = interpCall(e0, p.classToRun, "main", List())
    checkType(v, VoidType)
  }
 
  def main(args : Array[String]) = {
    val prog1 = Program(
      List(ClassDef("Example", List(
	FieldDecl(VarDecl("x", BoolType)),
	FieldDecl(VarDecl("y",IntType)),
	FieldDecl(VarDecl("z",IntType)),
	MethodDecl("compute", 
		   List(VarDecl("x", IntType),
			VarDecl("y", IntType)),
		   IntType,
		   BlockStat(List(
		     DeclStat(VarDecl("z", IntType)),
		     AssignStat("z", IntConst(17)),
		     CallStat("z", "Example", "compute",
			      List(Var("z"),Var("z"))),
		     ReturnStat(Plus(Plus(Var("x"),Var("y")),Var("z")))
		   ))
		 ),
	MethodDecl("main", List(), VoidType, BlockStat(List(
	  DeclStat(VarDecl("res", IntType)),
	  AssignStat("x", BoolConst(true)),
	  AssignStat("y", IntConst(10)),
	  AssignStat("z", IntConst(17)),
	  CallStat("res", "Example", "compute", 
		   List(Var("z"), Plus(Var("z"),IntConst(1)))),
	  PrintStat(Var("res"))
	)))
      ))),
      "Example"
    )
    interpret(prog1)
  }
}

How long can interpretation take?

How long will semantic analysis take?

What does above analysis do if some code is unreachable?