CS 294-5: Statistical Natural Language Processing

R. Pełka: Programming Languages

William H. (Bill) Gates



Born Oct, 28, 1955, Seattle, Washington, U.S.



CEO of Microsoft, richest person in the world (1999)



First developed a BASIC compiler while at Harvard



Dropped out (asked to leave?) went on to develop
Microsoft

“You’ve got to be willing to read other people’s
code, then write your own, then have other people
review your code”



Generous to Computer Science and philanthropic in
general



Visionary, perhaps cutthroat

Microsoft in 1978
Can you find Bill
Gates ?

R. Pełka: Programming Languages

Outline

 Inheritance – in-depth look

 Inheritance revisited – repetition from previous lectures
 Subtyping
 Substitution
 Polymorphic variables

 Advanced OO concepts

 Static dynamic types
 Overriding
 Method lookup
 Method Polymorphism
 Abstract classes
 Interfaces

R. Pełka: Programming Languages

DoME

objects:

The DoME example

 Database of Multimedia Entertainment
 stores details about CDs and DVDs

 CD: title, artist, # tracks, playing time, got-it, comment
 DVD: title, director, playing time, got-it, comment

 allows (later) to search for information or print lists

R. Pełka: Programming Languages

CD
source
code

public

class

{

private

String title;

private

String artist;

private

String comment;

CD(String theTitle, String theArtist)
{

title = theTitle;
artist = theArtist;
comment = " ";

}

void

setComment(String newComment)

{ ... }

String getComment()
{ ... }

void

print()

{ ... }
...
}

incomplete

(comments!)

R. Pełka: Programming Languages

DVD
source
code

public

class

DVD

{

private

String title;

private

String director;

private

String comment;

DVD(String theTitle, String theDirector)
{

title = theTitle;
director = theDirector;
comment = " ";

}

void

setComment(String newComment)

{ ... }

String getComment()
{ ... }

void

print()

{ ... }
...
}

Code of
classes CD
and DVD is
very
similar

incomplete

(comments!)

R. Pełka: Programming Languages

class

Database {

private

ArrayList<CD> cds;

private

ArrayList<DVD> dvds;

...

public

void

list(){

for

(CD cd : cds) {

cd.print();
System.out.println();

// empty line between items

}

for

(DVD dvd : dvds) {

dvd.print();
System.out.println();

// empty line between items

}
}
}

Database source code

very similar code too

 code duplication



CD and DVD classes are very similar (large parts are

identical)



makes maintenance difficult/more work

 code duplication also in Database class

R. Pełka: Programming Languages

Using inheritance

means

inherits or is

derived from



define one

superclass

Item



define

subclasses

for

CD and DVD



the superclass defines
common attributes



the subclasses

inherit

the superclass
attributes



the subclasses add own
attributes

R. Pełka: Programming Languages

Inheritance in Java

public class Item
{
...
}

public class CD

extends Item

{
...
}

public class DVD

extends Item

{
...
}

no change
here

change

here

R. Pełka: Programming Languages

Superclass and subclasses

public

class

Item

{

private

String title;

private

int playingTime;

private

boolean gotIt;

private

String comment;

// constructors and methods

// omitted.

}

public class

extends Item

{

private

String artist;

private

int numberOfTracks;

// constructors and methods

// omitted.

}

public class

DVD

extends Item

{

private

String director;

// constructors and methods

// omitted.

}

R. Pełka: Programming Languages

public class

Item {

private

String title;

private

int playingTime;

private

boolean gotIt;

private

String comment;

/**

* Initialise the fields of the item.
*/

public

Item(String theTitle, int time) {

        title = theTitle;
        playingTime = time;
        gotIt = false;
        comment = "";
    }

// methods omitted

}

Inheritance and constructors

R. Pełka: Programming Languages

Inheritance and constructors

public class CD

extends Item

{
private String artist;
private int numberOfTracks;

/**

* Constructor for objects of class CD
*/

    public CD(String theTitle, String theArtist,
              int tracks, int time)
    {

super(theTitle, time);

        artist = theArtist;
        numberOfTracks = tracks;
    }

// methods omitted

}



Subclass constructors must
always contain a

'super'

call.



If none is written, the
compiler inserts one
(without parameters)



works only, if the superclass
has a constructor without
parameters

R. Pełka: Programming Languages

Adding more classes



Inheritance (so far) helps
with:



Avoiding code
duplication



Code reuse



Easier maintenance



Extendibility

R. Pełka: Programming Languages

New Database

public class

Database

{

private

ArrayList<Item> items;

/**

* Construct an empty Database.
*/

public

Database()

    {
        items = new ArrayList<Item>();
    }

/**

* Add an item to the database.
*/

public

void addItem(Item theItem)

    {
        items.add(theItem);
    }
    ...
}

R. Pełka: Programming Languages

/**
* Print a list of all currently stored CDs and
* DVDs to the text terminal.
*/

public

void list()

{

for

(Item item : items) {

item.print();

// Print an empty line between items

System.out.println();
}
}

New Database

cntd.

avoids
code
duplicatio
n

R. Pełka: Programming Languages

Subtyping

First, we had:

public

void addCD(CD theCD)

public

void addVideo(DVD theDVD)

Now, we have:

public

void addItem(Item theItem)

We call this method with:

DVD myDVD = new DVD(...);
database.addItem(myDVD);

R. Pełka: Programming Languages

Subclasses and subtyping



Classes define types.



Subclasses define subtypes.



Objects of subclasses can be used
where objects of supertypes are
required.

 e.g. if someone ask us to give them a

pen, we can fulfill the request by giving
them a fountain pen or a ball pen.

 (This is called

substitution

)

R. Pełka: Programming Languages

Subtyping and assignment

Vehicle v1 = new Vehicle();
Vehicle v2 = new Car();
Vehicle v3 = new Bicycle();

subclass

objects may be
assigned to

superclass

variables

R. Pełka: Programming Languages

Subtyping and parameter
passing

public

class Database

{

public

void addItem(Item

theItem)
    {
        ...
    }
}

DVD dvd = new DVD(...);
CD cd = new CD(...);

database.addItem(dvd);
database.addItem(cd);

subclass

objects may be
passed to

superclass

parameters

R. Pełka: Programming Languages

Polymorphic variables



Object variables in Java are

polymorphic

Polymorphic means “of multiple forms”.(They can

hold objects of more than one type.).



Typing rule: “A variable can hold
objects of the declared type, or of
any subtype of the declared type.”

R. Pełka: Programming Languages

Casting



Can assign subtype to supertype.



Cannot assign supertype to subtype!

  Vehicle v;
  Car c = new Car();
  v = c;

// correct; v contains

// a car variable

c = v;

// compile-time error! even

// if v contains a car now



Casting

fixes this:

c = (Car) v;

 only ok if the vehicle

really is a Car!)



An object type in parentheses.



Used to overcome 'type loss'.



The object is not changed in any way.



A runtime check is made to ensure the
object really is of that type:

 ClassCastException

if it isn't!



Use it sparingly.

R. Pełka: Programming Languages

Polymorphic collections



All collections are polymorphic.



The elements are of type Object.

public

void

add(Object element)

public

Object get(

int

index)



All objects can be entered into collections ...



... because collections accept elements of type
Object ...



... and all classes are subtypes of Object.



Great! But what about simple types?



... remember Wrapper classes ?

R. Pełka: Programming Languages

Wrapper classes



Primitive types (

int

char

, etc)

are not objects. They must be
wrapped into an object!

 This is why Java is not a “pure” OO language



Wrapper classes exist for all simple types

simple type

wrapper class

int

Integer

float

Float

char

Character

...

int

i = 18;

Integer iwrap =

new

Integer(i);

…

int

value = iwrap.intValue();

wrap the value
unwrap it

In practice,

autoboxing

and

unboxing

mean we

don't often have to do

this.

R. Pełka: Programming Languages

Review – inheritance



Inheritance allows the definition of classes as extensions of
other classes.



Inheritance

 avoids code duplication
 allows code reuse
 simplifies the code
 simplifies maintenance and extending



Variables can hold subtype objects.



Subtypes can be used wherever supertype objects are
expected (substitution).



There is controversy in the reliability of using inheritance. It
is argued that it is safer to use interfaces (to be studied
later) instead of inheritance

R. Pełka: Programming Languages

Abstract classes and methods



Abstract methods have

abstract

in the

signature.



Abstract methods

have no body



Abstract methods

make the class abstract



Abstract classes cannot be instantiated.



Concrete subclasses complete the
implementation.

// example of abstract class

abstract class AbstractClass {
        public abstract void methodA();
        void methodB() {
              // ...
        }
}

// example of abstract class

abstract

class AbstractClass {

public

abstract

void methodA();

        void methodB() {
              // ...
        }
}

methodA has no body

R. Pełka: Programming Languages

Abstract Class

 No implementation, gives the framework only

 Abstract class cannot have object
 To give the consistency when we use the method at other

out classes

 Can be used after inherit by other class

 The object can be created after all abstract methods are

implemented in subclass.

R. Pełka: Programming Languages

Why use Abstract classes?

 Declaring a class to be abstract is good

programming practice:

 if we don't intend to create an object directly from a

class, then declaring it to be

abstract

forces us to

respect this

 if we want to create

polymorphic

methods at the lower

levels, instead of providing a method body which we
don't intend to use, declare the method to be

abstract

This also forces us to provide a method for the
subclasses - Java won't let us forget.

R. Pełka: Programming Languages

Principles of OO Programming

 The four principles of object-oriented

programming are:



abstraction

- develop an abstract representation (i.e. a

class) for what you want to model, without unneeded
detail



encapsulation

- an object contains all relevant attributes

and behaviours, and its class hides the details of the
implementation behind a public interface



inheritance

- define common attributes and behaviours

at a higher level, and pass them down to subclasses



polymorphism

- allow different behaviour to be referred

to by the same name when appropriate

R. Pełka: Programming Languages

OO modelling tips

 Think about the different things you need in your

model:

 if you think of "it" as an

idea

, make it a

class

 if you think of "it" as an

entity

, make it an

object

a class

 if two classes have

something in common

, put the

common things into a

superclass

 if you are not clear whether you should be using

inheritance or composition for relating A and B, try:



a B: A

inherits

from B



A is

part of

B: A is member data in B (

composition

)

R. Pełka: Programming Languages

How should we design classes?

1. obtain a statement of the problem
2. sketch a sample scenario
3. work out what objects are involved

(do the following one class at a time:)

4. work out how those objects are meant to

behave

design the interface for the class

6. define the variables
7. implement the methods
8. test the class

 the interface only shows the

public methods and data

 it does not show private data

or methods

 it does not state how the

class is implemented

 the

interface

only shows the

public methods and data



it does not show private data
or methods



it does not state how the
class is implemented

R. Pełka: Programming Languages

Determining the interface

 before writing a class definition, determine the

interface



the set of services we offer to clients

 similarly, if defining data structures, we should

first determine the interface



stacks support a constructor and methods: push,
pop, size, isEmpty, and top



queues offer a constructor and methods enqueue,
dequeue, size, isEmpty and front

 people refer to the interface as the



abstract data type

R. Pełka: Programming Languages

Data Abstraction

 if the

interface

remains the same, clients don't

need to be changed, even if the implementation
behind the interface changes

public

class Time {

private

int timeInSecs;

//public methods

}

public

class Time {

private

int hours;

private

int minutes

private

int secs;

   //same public methods
   //but with different
   //bodies

}

R. Pełka: Programming Languages

Java Interfaces

 Java allows us to take this one stage further, by

formally recording the interface as a

Java interface

 a Java interface is just a collection of abstract methods

(i.e. we state the signatures, but not the bodies)

public

interface

MyStack {

   public int size();
   public boolean isEmpty();
   public Object top();
   public void push(Object elt);
   public Object pop();
}

states that
this is an
interface,
not a class

note no
bodies for
the methods

R. Pełka: Programming Languages

Interfaces vs classes

 a

class

definition can contain instance/class

variables and instance/class methods, including
both the signature and the body

 a Java

interface

contains only the signatures of

public instance methods (and named constants)

 a Java interface acts like a specification



it says what it means to be e.g. a stack



to be a stack, an object must offer at least those methods
in its public interface

R. Pełka: Programming Languages

Using Java interfaces

 Java allows us to tell the compiler that a class will

implement an

interface

 regard it as a contract stating that you will meet the

specification

 any class that implements an interface must provide

implementations of the public methods (or it must
be abstract, and its subclasses provide them)

 the compiler will check, and if the bodies are not

provided, it won't compile

R. Pełka: Programming Languages

Example

import

java.util.ArrayList;

public

class

ALStack<E>

implements

MyStack {

private

ArrayList<E> al;

public

ALStack() {

al =

new

ArrayList<E>();

}

public

int

size() {

return

al.size(); }

//and versions of isEmpty, push, pop and top ...

}

promises that we
will provide bodies for
all the MyStack methods

R. Pełka: Programming Languages

Example

cntd.

public class ArrayStack

implements

MyStack {

   private int capacity;
   private Object[] s;
   private int top = -1;

   public ArrayStack(int reqdCapacity) {
      capacity = reqdCapacity;
      s = new Object[capacity];
   }

public int size() { return top+1; }

//and versions of isEmpty, push, pop and top ...

}

R. Pełka: Programming Languages

Interface – summary

 An

interface

is like an abstract class - it specifies

what its methods should look like, but gives no body

 if a class

implements

an interface, it is equivalent to

signing a contract saying that it will provide a body
for the specified method - Java will not compile the
program unless we provide the method definition

 we can refer to an object as though it were an object

of the interface, and invoke the interface methods

 Interfaces allow

multiple inheritance

R. Pełka: Programming Languages

Summary

 Inheritance – in-depth look

 Inheritance revisited – repetition from previous lectures
 Subtyping
 Substitution
 Polymorphic variables

 Advanced OO concepts

 Static dynamic types
 Overriding
 Method lookup
 Method Polymorphism
 Abstract classes
 Interfaces

Document Outline