Section notes: Week 8

CS 164, Fall 2005

General

• HW due this week: Last question from Fall 02 MT 1
• HW due next week: Add assignment (=) to the typechecker from today
• Follow-up: negation and subtraction
• Questions about assignment 4?

Type-checking

;; Example adapted from section 6.2 in the Dragon book

(def-jyacc simple-lang

  (P    -> vars E)
  (vars -> vars var \;)
  (vars -> )

  (var  -> id \: type)
  (type -> char)
  (type -> integer)
  (type -> array [ num ] of type)
  (type -> ^ type)

  (E    -> E1)
  (E1   -> E1 mod E2)
  (E1   -> E2)
  (E2   -> ^ E3)
                                 
  (E2   -> E3)
  (E3   -> E3 [ E ])
  (E3   -> E4)
  (E4   -> literal)
  (E4   -> num)
  (E4   -> id))

• Languages can be statically or dynamically typed (which is Lisp? Java?)
• Can put little or lots of information in the type system (even within one language -- e.g. lint)
• Can declare types or let the computer figure some out (type inference)
• Can compute types while parsing or after AST is built (why does the latter not work with MJ?)

Resolving names

// What is the output of this code?

class Week8 {
    public static void main(String[] a) {
        System.out.println(new Foo().Init().Goo(2));
    }
}

class Pop {
    int foo;
    public int Foo()        { return foo;   }
    public int Bar()        { return foo+1; }
    public int Goo(int bar) { System.out.println(bar); return 0; }
}

class Foo extends Pop {
    boolean foo;
    int bar;
    public Pop Init() { bar = 100; foo = true; return this; } 
    public int Foo()  { 
        int bar; 
        if (foo) bar = 2; else bar = 3; 
        return bar; 
    }
    public int Goo(int bar) {
        int baz;
        baz = bar + 5;
        System.out.println(this.Foo());
        System.out.println(this.Bar());
        System.out.println(bar);
        return baz;
    }
}

• What information should we keep with a variable name?
• What information should be kept for the symbol foo in class Foo?
• How should we keep track of method names?
• How do we decide what method to call at compile time?

Polymorphism

Same name, different functions. How do we get polymorphism in Java?

• Built-in operations (arithmetic, indexing, etc)
• Methods with the same name, different type signatures?
• Virtual methods

What about other languages?

• Macros and templates (e.g. C++)
• Multiple-dispatch generics (Common Lisp)
• Comes almost for free with dynamically-typed languages
• Can work with static typing (e.g. ML), but trickier