# SE580: Lecture 9

## Overview

The binary method problem

A solution: myType

Generic Java

Type inference for generics

## The binary method problem

Consider:

```  class Point {
field x : Integer; field y : Integer;
method infix <= (p : Point) : Boolean {
return this.x < p.x || (this.x == p.x && this.y <= p.y);
}
}
class ColoredPoint extends Point {
field color : Color;
method infix <= (p : ColoredPoint) : Boolean {
return this.x < p.x || (this.x == p.x && ( this.y < p.y || this.y == p.y && this.color <= p.color ) );
}
}
```

This code does not compile. Why not?

This is an instance of the binary method problem.

## The binary method problem

Java's solution (almost):

```  interface Comparable { method infix <= (p : Comparable) : Boolean; }
class Point implements Comparable {
field x : Integer; field y : Integer;
method infix <= (p : Comparable) : Boolean {
return this.x < p.x || (this.x == p.x && this.y <= p.y);
}
}
class ColoredPoint extends Point {
method infix <= (p : Comparable) : Boolean {
return this.x < p.x || (this.x == p.x && ( this.y < p.y || this.y == p.y && this.color <= p.color ) );
}
}
```

This code does not compile. Why not? What can we do about it?

## Introducing myType

Another possible solution:

```  class Point {
field x : Integer; field y : Integer;
method infix <= (p : myType) : Boolean {
return this.x < p.x || (this.x == p.x && this.y <= p.y);
}
}
class ColoredPoint extends Point {
field color : Color;
method infix <= (p : myType) : Boolean {
return this.x < p.x || (this.x == p.x && ( this.y < p.y || this.y == p.y && this.color <= p.color ) );
}
}
```

What is `myType` doing here?

## Introducing myType

Another example: cloning. How does Java handle cloning?

An alternative:

```  class Point {
...
field cloner : Cloner[myType];
method clone () : myType { return cloner.clone (this); }
}
interface Cloner [type a] { method clone (x : a) : a; }
class PointFactory implements Cloner[Point] {
method build (x : Integer, y : Integer) : Point { ... }
method clone (p : Point) : Point { ... }
}
```

How can we finish this example?

If `p:Point` we can now write `let q : Point = p.clone ();`

## A problem with myType

```  class Foo {
method m (x : myType) : Integer { return 0; }
}
class Bar extends Foo {
field b : Integer;
method m (x : myType) : Integer { return x.b; }
}
let x : Foo = new Foo {};
let y : Bar = new Bar { b = 37 };
let z : Foo = y;
z.m (x);
}
```

What is the problem? How can we fix this?

## Semantics of myType

Classes now declare a `myType` type variable:

```  class Foo extended myType {
// myType <# Foo is a local type variable here.
}
```

What changes to the syntax / dynamic semantics / static semantics are needed?

## Homework

Last homework! Implement `myType`.

## Another solution: F-bounded polymorphism

Another solution (adopted by Generic Java):

```  interface Comparable [type a] { method infix <= (x : a) : Boolean; }
class Foo implements Comparable[Foo] { ... }
class Bar implements Comparable[Bar] { ... }
interface SortedList [type a implements Comparable[a]] extends List[a] {
method insert (x : a) : SortedList[a];
}
```

How can we implement `SortedList`?

## Type inference for generics

An example Java 1.5 program:

```public class Example {
public static void main (String [] args) {
Ref<String> r = build ();
r.set ("hello");
System.out.println (r.get ());
}
static <A> Ref<A> build () {
return new Ref<A> ();
}
static <A> Ref<A> build (A x) {
Ref<A> result = build (); result.set (x); return result;
}
}
class Ref<A> {
A contents;
public void set (A x) { contents = x; }
public A get () { return contents; }
}
```

Note the code: `build ()` what is odd here?

## Type inference for generics

Generic Java does type inference on generic methods.

You write:

```        Ref<String> a = build ();
Ref<String> b = build ("hello");
```

The compiler figures out:

```        Ref<String> a = build<String> ();
Ref<String> b = build<String> ("hello");
```

Why does Java include type inference for generic methods?

## Type inference for generics

Two strategies for type inference for generic methods:

1. C++ bottom-up.

2. Standard ML constraint-solving (the Hindley-Milner algorithm).