Types 2

• Refresher: What are types?
• Types in Java
• Static and dynamic typing
• Type conversions
• Super- and subtypes

What Are Types?

• Type = set of values + permitted operations on these values
• Example: int in Java. Set of numbers between Integer.MIN_VALUE and Integer.MAX_VALUE. Operations +, -, *, etc.
• Used for
  • IDE help
  • Code generation
  • Error handling
• Types in Java:
  • Primitive types: int short long byte char float double boolean
  • Reference types: classes, interfaces, arrays

Types in SL3

• SL3 = SL1 with a type system
• Int
• Bool
• Function types (ParamType1,...,ParamTypeN) => ReturnType
• Example: (Int, Int) => Bool
• Types of expressions and variables are inferred (like in Scala)

  val x = 3 * 4; // is an Int
  val y = 3 < 4; // is a Bool

Flow-Based vs. Inference-Based Typing

• SL3 uses flow-based typing (like Scala)

  val x = 3;
  val y = 4;
  val z = x * y;

  Know types of x and y, therefore type of z.

• Doesn't work for function parameters:

  { x, y => x * y }

  Don't have initial values for x, y

• Some languages use type inference: Since * is (Int,Int)=>Int, x and y must be int
• SL3: Specify parameter types

  { x : Int, y : Int => x * y }

Return Type Inference

• Return type of function is inferred

  { x : Int, y : Int => x < y }

  Return type is Bool

• Exception: Recursive functions

  def fac = { x : Int => if (x == 0) 1 else x * fac(x - 1) };

  Flow analysis doesn't work—doesn't know type of fac

• Remedy: def must specify return type (like in Scala)

  def fac : Int = { x : Int => if (x == 0) 1 else x * fac(x - 1) };

Higher Order Functions

• Parameters can be functions:

  val twice = { f : (Int)=>Int, a : Int => f(f(a)) };
  val triple = { x : Int => 3 * x };
  twice(triple, 2)

• What is the output of this program?

  http://ActiveLecture.org

• Return types can be functions:

  val mystery  = { n : Int => { x : Int => n * x } };
  val enigma = mystery(3);
  enigma(2)

• What is the output of this program?

  http://ActiveLecture.org

Function Types

• What is the type of twice?

  val twice = { f : (Int)=>Int, a : Int => f(f(a)) };

  http://ActiveLecture.org

• What is the type of mystery?

  val mystery  = { n : Int => { x : Int => n * x } };

  http://ActiveLecture.org

Type Checking

• Classes to represent SL3 types

  class SL3Type
  case class SL3Int extends SL3Type
  case class SL3Bool extends SL3Type
  case class SL3Fun(paramTypes : List[SL3Type], returnType : SL3Type) extends SL3Type
      

• Function for determining the type of an expression

  def typeof(expr : ExprTree, types : List[(String, SL3Type)]) : SL3Type

• Needs to know types of variables
• Example: expr is Operator(Variable(x), Number(2), <function>) and types contains the pair ("x", SL3Int())

    expr match {
      case Number(_) => SL3Int()
      case Variable(name) => lookup(name, types)
      case Operator(left, right, _) => {
        assert(typeof(left, types) == SL3Int())
        assert(typeof(right, types) == SL3Int())
        SL3Int()
   }

• Detects type errors

  2 * (x < 0)

Type Checking Details

• SL3 parser implements type checker
• Function class now holds parameter names and types

  case class Function(params : List[(String, SL3Type)], body : Block) extends ExprTree

• Type of function = (paramTypes)=>returnType

      case Function(params, body) => SL3Fun(
        params.map({_._2}), typeofBlock(body, params ::: types))

• Example: typeof applied to { x : Int, y : Int => x < y } (i.e. Function(List("x", SL3Int()), ("y", SL3Int())), body) yields SL3Fun(List(SL3Int(), SL3Int()), SL3Bool())
• Just like with eval/evalDefs/evalBlock, we have typeof/typeofDefs/typeofBlock
• What does params.map({_._2}) do? http://ActiveLecture.org

Lab

• Check into eCampus in the usual way
• Scribe puts in report
• Buddy puts in comment with scribe's name

Step 1: Kick the Tires of the SL3 Interpreter

1. Put this program into the interpreter

   val twice = { f : (Int)=>Int, a : Int => f(f(a)) };
   val triple = { x : Int => 3 * x };
   twice(triple, 2)

   What type do you get for the result?

2. What is reported as the type of triple? Hint: Just modify the program to evaluate triple instead of twice(triple, 2).
3. The type is written as a complex SLFun expression. Translate it back into a SL3 type of the form (paramTypes)=>returnType
4. What is the type of twice? Translate it into a SL3 type

Step 2: Type Errors

1. The following is a type error since the types of the branches don't agree

   val x = 1;
   if (x < 2) x else x < 2

   What happens when you run the SL3 interpreter with this input?

2. Which part of the interpreter code diagnosed the error?
3. Now consider this program that lies about a recursive type:

   def fac : Bool = { x : Int => if (x == 0) 1 else x * fac(x - 1) };
   fac(3)

   You'll get an exception when you run the program, but the stack trace doesn't tell you much about the cause of the error. Run the debugger instead. When the stack trace hits, the program will stop on the line assert(typeof(right, types) == SL3Int()). What is the value of right?

Step 3: Code Cleanup

• It isn't a good idea to use pairs such as (String, SL3Type). They lead to messy expressions such as _._2. A better way is to use a case class

  case class TypedIdent(name : String, type3 : SL3Type)

  (type is a reserved word in Scala.)

• Make that change in the SL3 interpreter. Change the List[(String, SL3Type)] into a List[TypedIdent]. Make the other necessary changes and check that the correct version of the fac function still works. What changes did you make?