►Introduction to Programming Languages
►Labs and Assignments
▼Labs
►11 Java
On this page:
11.1 Javette
11.2 Data Definitions
11.3 Compilation and Type Checking
11.3.1 Operations to Check
11.3.2 Compiling Field Lookups
11.3.3 Null and Type-checking
11.3.4 Type Compatibility
11.3.5 The Type of this
11.4 Runtime Behavior
11.4.1 The Structure of Objects
11.4.2 Default Values
11.4.3 Null
11.4.4 Runtime Behavior of Method Calls (and Binding this)
11.4.5 Lack of Booleans
11.5 Support Code
11.6 Written Questions
11.7 Testing and Submission Steps
11.8 Grading
    ← prev  up  next → 
11 Java

This assignment has you implement a mini-Java, we’ll call it Javette. There are a few major lessons in this assignment:

11.1 Javette

Like Java, Javette programs consist of a collection of class definitions, and a main expression to evaluate. Here’s an example Javette program that defines a Point class, constructs a Point object, sets a field, and does arithmetic with them:

(program
  (classes
    (class Point extends Object
      (fields (x Num) (y Num))
      (methods)))
  (let (Point p (new Point))
    (do
      (set p x 10)
      (+ (get p x) (get p y)))))

This produces 10.

A few things to note already:

We can add a method to the class, and use this to access the fields:

(program
  (classes
    (class Point extends Object
      (fields (x Num) (y Num))
      (methods (method Num sum (Num _) (+ (get this x) (get this y))))))
  (let (Point p (new Point))
    (do
      (set p x 10)
      (call p sum 0))))

This also produces 10.

All methods have a single argument with an annotated type, in this case we use _ to simulate a 0-argument function.

11.2 Data Definitions

prog :=

  | (program (classes <class> ...) <exp>)

class :=

  | (class <class-name> extends <class-name>

      (fields <field> ...) (methods <method> ...))

field :=

  | (<field-name> <type>)

method :=

  | (<type> <method-name> (<type> <id>) <exp>)

 

exp :=

  | <num>

  | <id>

  | (+ <exp> <expr>)

  | (do <exp> <expr> ...)

  | (let (<type> <id> <exp>) <expr>)

  | (if <exp> <exp> <exp>)

 

  | (get <exp> <field-name>)

  | (set <exp> <field-name> <expr>)

  | (call <exp> <method-name> <expr>)

 

  | (new <class-name>)

  | this

  | (null <class-name>)

 

class-name, method-name, field-name, id :=

  Any non-keyword symbol

 

type :=

  | Num

  | <class-name>

The abstract syntax is:

data JProgramSrc:
  | src-program(classes :: List<JClassSrc>, psvm :: JExprSrc)
end

data JClassSrc:
  | src-class(name :: String, superclass :: String,
            fields :: List<JFieldSrc>, methods :: List<JMethodSrc>)
end

data JMethodSrc:
  | src-method(ret-type :: JType, name :: String,
      arg-type :: JType, arg :: String, body :: JExprSrc)
end

data JFieldSrc:
  | src-field(name :: String, field-type :: JType)
end

data JExprSrc:
    # Fields & Methods:
  | src-get-field(obj :: JExprSrc, field :: String)
  | src-set-field(obj :: JExprSrc, field :: String, val :: JExprSrc)
  | src-method-call(obj :: JExprSrc, meth :: String, arg :: JExprSrc)
    # Objects:
  | src-new(class-name :: String)
  | src-this
  | src-null(class-name :: String)
    # Basic Language Stuff:
  | src-let(arg-type :: JType, arg :: String, val :: JExprSrc, body :: JExprSrc)
  | src-num(num :: Number)
  | src-plus(left :: JExprSrc, right :: JExprSrc)
  | src-if(cond :: JExprSrc, consq :: JExprSrc, els :: JExprSrc)
  | src-do(exprs :: List<JExprSrc>)
  | src-id(var-name :: String)
end

data JType:
  | t-num
  | t-obj(class-name :: String)
end

The result of parse is a JProgramSrc.

The evaluation of a JProgramSrc is defined in two stages: first compilation and type-checking, then interpreting the result. Compilation and type-checking produce new ASTs, which have different shape:

data JProgram:
  | j-program(classes :: List<JClass>, psvm :: JExpr)
end

data JClass:
  | j-class(name :: String, superclass :: String,
            fields :: List<JField>, methods :: List<JMethod>)
end

data JMethod:
  | j-method(name :: String, arg :: String, body :: JExpr)
end

data JField:
  | j-field(name :: String, field-type :: JType)
end

data JExpr:
    # Fields & Methods:
  | j-get-field(obj :: JExpr, class-name :: String, field :: String)
  | j-set-field(obj :: JExpr, class-name :: String, field :: String, val :: JExpr)
  | j-method-call(obj :: JExpr, meth :: String, arg :: JExpr)
    # Objects:
  | j-new(class-name :: String)
  | j-this
  | j-null
    # Basic Language Stuff:
  | j-let(arg :: String, val :: JExpr, body :: JExpr)
  | j-num(num :: Number)
  | j-plus(left :: JExpr, right :: JExpr)
  | j-do(exprs :: List<JExpr>)
  | j-if(cond :: JExpr, consq :: JExpr, els :: JExpr)
  | j-id(var-name :: String)
end

So compilation takes a JProgramSrc, does some work on it, and produces a JProgram. The interpreter takes a JProgram, and produces a value (as a JVal):

# map from class names -> (map from field name -> value)
type FieldSet = D.StringDict<D.MutableStringDict<JVal>>

data JVal:
  | v-num(num :: Number)
  | v-null
    # `class-name` is the class used to construct the object
    # `field-sets` stores all of the object's fields, grouped by class.
  | v-object(class-name :: String, field-sets :: FieldSet)
end

data TypeError:
  | err-class-not-found
  | err-field-not-found
  | err-method-not-found
  | err-type-mismatch
  | err-this-outside-of-method
  | err-non-object
  | err-unbound-id
end

data DynamicError:
  | null-pointer-exception
end
11.3 Compilation and Type Checking

The compiler needs to do a number of type-checking operations:

11.3.1 Operations to Check

These checks ensure that almost all possible errors are caught at compilation/type-checking time, rather than happening in the interpreter. It should be clear from your implementation that all the errors are caught in the compiler, and not left for the interpreter to catch!

11.3.2 Compiling Field Lookups

We noted in lab that the compiler also affects field lookup by using information from the type checker. This motivates the difference between src-get-field and j-get-field:

| src-get-field(obj :: JExprSrc, field :: String)
| j-get-field(obj :: JExpr, class-name :: String, field :: String)

The latter, which will be in the output of the compiler, has an explicit position, class-name for keeping track of which class the type checker computes for obj. Note that this can never be Num, since that would be a error because it isn’t possible to look up fields on numbers. An analogous extra position is in j-set-field for src-get-field, which have the same type-directed lookup behavior.

11.3.3 Null and Type-checking

Java (and Javette) has a special value called null which can have any class type. To slightly simplify null handling, in Javette an explicit class name is provided in each user-written use of null. So the type of src-null("C"), for example, is the type t-obj("C"). This avoids adding new rules about “the type of null” to the type system, which makes things more complicated but not more illuminating.

11.3.4 Type Compatibility

When checking if two types match, Java uses subtyping rather than type equality. This includes:

11.3.5 The Type of this

The type of the special this expression is always the type of the enclosing class. If this appears in the main expression of a program, an err-if-outside-of-method exception should be raised.

11.4 Runtime Behavior
11.4.1 The Structure of Objects

Once compiled to a JExpr, the program can be run. The structure of values is interesting, as we saw in lab, objects store a set of field for each class in the chain from the class up to Object. For example, consider this example:

(program
  (classes
    (class A extends Object
      (fields (x Num) (y Num))
      (methods))
    (class B extends A
      (fields (y Num))
      (methods)))

  (let (B b (new B))
    (let (A a b)
      (do
        (set a x 10)
        (set a y 5)
        (set b y 3)
        b))))

This should return this object:

v-object("B",
  [string-dict:
    "B", [mutable-string-dict: "y", v-num(3)],
    "A", [mutable-string-dict: "y", v-num(5), "x", v-num(10)]
  ])

That is, it:

Also note that the two set expressions on the y field updated different fields, which gets back to the point of using the type of the object expression to select which field to assign into.

11.4.2 Default Values

When using new, all fields with Num type should be initialized to 0, and all fields with a class type should be initialized to v-null. Example:

(program
  (classes
    (class A extends Object
      (fields (x Num) (y Num))
      (methods))
    (class B extends A
      (fields (y A))
      (methods)))

  (new B))

produces

v-object("B",
  [string-dict:
    "B", [mutable-string-dict: "y", v-null],
    "A", [mutable-string-dict: "y", v-num(0), "x", v-num(0)]
  ])
11.4.3 Null

If you’re wondering why the heck there’s all this nonsense around null, good question. At first glance, it seems like it’s just there to avoid needing to initialize fields, and to use as a dummy value, which would be a pretty weak argument for having it. A better argument is that without some default value for fields, it would be difficult to create cycles between objects. The chapter on cyclic data in PAPL discusses a few design tradeoffs here. There are certainly alternatives to the null design, and they may be preferable. There is one distinguished null value (in Java and Javette), called v-null. It is a runtime error to get or set a field, or call a method, on the null value. It is a specific runtime error So, for example, these programs throw null-pointer-exceptions when run, though they successfully type-check:

(program (classes
  (class C extends Object
    (fields (x Num))
    (methods)))
  (get (null C) x))

(program (classes
  (class C extends Object
    (fields (x Num))
    (methods)))
  (set (null C) x 0))

(program (classes
  (class C extends Object
    (fields)
    (methods (method Num id (Num x) x))))
  (call (null C) m 0))
11.4.4 Runtime Behavior of Method Calls (and Binding this)

On each call to a method, the provided argument is evaluated, and then bound to the method’s parameter name in the environment, just as in a function call. In addition, the object on which the method is called is “passed in” as the current binding for this. It’s up to you how to handle this (no pun intended), which might be part of the environment or an extra parameter to the interpreter, for example.

11.4.5 Lack of Booleans

There are no boolean values in Javette. if expressions evaluate the then branch on 0 and v-null, and the else branch on all other values. There are no errors (type or runtime) for if expressions in Javette.

11.5 Support Code

For reference, the Java quiz:

https://docs.google.com/forms/d/1ij--psfv-AvuMgGKV_XDr3hSF-ZziknYqM-P_GJG_Io/viewform

Tests:

https://code.pyret.org/editor#share=0B32bNEogmncObmlfQ2hXVXFVZTg&v=v0.5r852

Code:

https://code.pyret.org/editor#share=0B32bNEogmncOUHJRZERTWnlXMVE&v=v0.5r852

Definitions:

https://code.pyret.org/editor#share=0B32bNEogmncOUFdMNDhkVjVvOXM&v=v0.5r852

11.6 Written Questions

There are a few written questions you need to submit answers to along with your final submission. Put them in a separate file.

11.7 Testing and Submission Steps

You can work with a partner on this assignment. You should do test submission and review separately, and then work together subsequently. Feel free to start working together before the Thursday test deadline, but do submit separate test suites. This is better for you: it forces you to see more diversity in tests.

Report to me by email by Thursday midnight if you’re working with a partner, and who; CC your partner. If you want to be randomly assigned a partner, I’ll try to accommodate, but since partners are optional, no promises.

By midnight Thursday (April 2), you should submit 5-10 of what you think are the most interesting tests to Captain Teach at the cs91-type-infer link from:

https://www.captain-teach.org/swarthmore-cs091/assignments/

Submit a single Pyret file with your test cases filled into the check block in the template file.

By midnight Friday (April 3), you should submit any reviews you were assigned. You should feel free to complete the reviews at any time before then, and they will be assigned as submissions come in.

Update Bad solutions are up, usable with:

import shared-gdrive("java-bad-interps.arr", "0B32bNEogmncOdmpzN1RSNngzdzg") as G
G.dynamic-get
G.dynamic-set
G.co-arg-aka-typescript
G.contra-ret
G.trust-method-body
G.zero-object-default
G.null-propagates-on-get
G.let-uses-expr-type
G.set-allows-super-type
11.8 Grading

Your grade will be in a few parts:

Peer reviews will not factor into your grade, though you are free to copy tests from others that you see during review. Please don’t share tests with one another outside of what’s provided during test review.

    ← prev  up  next →