CS 474 - First Midterm

Based on the in-class notes

Object-Oriented

Programming style where data and code are bundled together in *objects*

(Programming) Languages

A vocabulary and set of rules for instructing a computer to perform a task

Environments​​

* Languages do not exist in isolation; they need a set of tools to work​​
* E.g. build system (ant, makefile), compiler (clang, gcc), IDE (eclipse)​​

Goal

Understand what it means for a language to be OO, how it helps, what the choices are, how it affects the way we program​

Modularity

* A system that is composed of modules is called modular​
* Modularity allows the principle of **separation of concerns** to apply​
* When dealing with details of each module in isolation​
* When dealing with the overall characteristics of all modules and their relationships​

Horizontal modularity

* unrelated parts of a system are implemented separately​
* E.g., implementation of Established state is separate from implementation of Closed state​

Vertical modularity

implementation of behavior is separate from its use​

Separation of Concerns

Each state only reasons about properties directly related to that state​

Practical benefits of modularity

* Decompose complex systems into simpler elements​
* Divide and conquer​
* Compose complex systems from existing modules​
* Understand the system in terms of its elements, and modify the system by modifying a small number of its elements​

Cohesion

relationships between elements within a module​

Coupling

dependencies between modules

Abstraction

* Ignore nonessential details of objects​
* Deal with a generalized, idealized models​
* Recognize the class and object hierarchies within a complex software system​
* Interfaces, design patterns, etc. are mechanisms for achieving abstraction​
* Need to balance between hiding details that won’t be used, and exposing information that users will need​
* Abstraction is taking a bunch of complicated code/ideas and figuring out general principles that describe most of it

Refinement

Refinement is the opposite of abstraction

* Refinement is taking a high-level idea and gradually implementing more and more of the details/special cases​
* Refinement is useful for improving or perfecting code once it’s written​
* E.g., stepwise refinement: write complex programs by progressively introducing implementation details into simpler programs

Incrementality

* Many software development activities proceed in a stepwise fashion, or in increments​
* Feedback plays important role in incremental software processes​
* Identify functions that constitute the core of software functionality​
* Progressively add functions to the application being developed​
* Identify intermediate stages for a software product​
* Rapid prototyping is a way of progressively developing an application hand in hand with understanding its requirements

Object

* An object is a kind of **first-class value** – it can be stored in a variable, passed as an argument, returned from a function, etc.​
* An object contains both **state** and **behavior**​
* In a typed language with classes, a class is usually a **type**, and objects are **instances** of that type ​
* Objects usually have a concept of **identity** that is separate from **equality**​
* In most OO languages, an object’s behavior is **dynamically dispatched** – which version of a behavior we’ll see depends on the specific object we have at runtime​

First-Class Values

* Can we assign it to a variable?​
* Can we pass it to a function?​
* Can we use it inside a function?​
* Can we return it from a function?​
* If any answer is “no”, then it is not a first-class value

Composite Values

* More complex types made of other types​
* Compare to primitive types like int, bool, float, that have only 1 value​
* Example:  structs in C
* Example:  classes in OO languages

Identity and Equality

* For a primitive type, the answer is just “yes” – if the values are the same, then they’re equal.
* Java’s answer is No. obj1 and obj2 are different objects (stored in different places in memory), and that’s what == checks.
* Yes: obj1 and obj2 contain the same data (Equality)
* No: obj1 and obj2 are not the same object​ (Identity)
* Objects have an identity that is separate from equality

\

Strings in Java

* Unlike with int/Integer, String can be treated as both primitive and a class type!
* Strings are composite types in Java​
* Have equality and identity​
* But Java caches string constants​
* All equal string constants also have the same identity​
* E.g., s1 and s2 in the previous slide​
* It’s a good idea to __**never use == on Strings**__​
* Unless you’re implementing a cache, you want to use equals
* Strings are immutable​
* You cannot change a string​
* If you try to change a string, you get another string with the change​
* E.g., replace in the previous slide

Identity vs Equality in Java

* You can define your own logic for equality​
* Add a method equals to your class​
* Identity is built-in, you cannot change it​

\
* How to check for identity?​
* Use == for composite types​
* Primitive types do not have identity​

\
* How to check for equality?​
* Use .equals for composite types​
* Use == for primitive types​

What makes a language *object-oriented*?​

* It has objects in it​
* Programming in the language is *centered* *around* objects​

Encapsulation​

* Encapsulation is the enforcement mechanism for abstraction​
* Encapsulation separates the contractual *interface* of an abstraction from its *implementation*​
* E.g., interface List vs class LinkedList​
* Clients can use the interface, but cannot access the implementation (private fields, etc.)​

Modules

* Group **data (variables)** and **behavior (functions)** together while avoiding conflicts with existing similar names​


* Complex visibility rules​
* Some elements should be visible from the outside​
* Other elements must not be visible from the outside​

Namespaces as Modules

* Static scope​
* Modules live as long as the program​

\
* No name collisions​
* set_seed can be accessed through rand_mod::set_seed​
* No problem if there’s another set_seed defined elsewhere​

\
* All module internals accessible/visible from outside the module​

\
* Only allows one random generator​
* But we can actually fix that​

Classes as modules

* Static scope​
* Avoids name collisions​
* We can control what to make visible and what to hide​


* No external access to internal variable seed​


* Better syntax for clients to use this module​
* We can even have classes inside modules, which helps with abstraction​


* Many invisible classes may work behind a visible class​

Hierarchy

* Simon’s law: __Hierarchical structures reduce complexity__​
* Hierarchy is a ranking or ordering of abstractions​
* In OO languages hierarchy is implemented using **inheritance**​
* A class can be derived from one or more superclasses​
* Languages may support single and/or multiple inheritance​

Inheritance

* Inheritance is a generalization/specialization hierarchy​

Inheritance and Aggregation

* Inheritance expresses “is-a” relationship​
* A Hawk “is-a” Bird​
* A Car “is-a” Vehicle​
* Aggregation expresses “has-a” relationship​
* A Car “has-a” engine and 4 wheels​
* A Bicycle “has-a” 2 pedals and 2 wheels​
* Both cars and bicycles “is-a” vehicles​

Single Inheritance

* Each class has at most one​
* Superclass is also called parent class​
* Used in: Java, C#, Ruby​
* Topmost class has no superclass​
* java.lang.Object in Java has no superclass

Multiple Inheritance​

* Each class may have many superclasses​

Typing

* The type of an object is the __range of values__ that the object is allowed to take​
* int : -231; …; -1,0; 1; 2; …; 231 ​
* float: 2.33; 3.1415; …​
* Point: { x = 1, y = 2 }; { x = 5, y = 12 }; …​
* Types are flexible: we can substitute in subclasses​
* List:  List, LinkedList, ArrayList​
* Type checking makes sure variables have a consistent type, and operations take operands of appropriate types​
* If typing is not possible: compiler error

Subtyping

* If B is a subtype of A, then an object of B can be used where an object of A is expected​
* SortedLinkedList is a subtype of LinkedList​
* An object of SortedLinkedList can be used wherever an object of LinkedList is expected​

Static vs Dynamic Types

* Static type:  LinkedList​
* We can use any operation of LinkedList​
* We cannot use operations only defined in SortedLinkedList​
* Dynamic type:  SortedLinkedList​
* The implementation of SortedLinkedList will be used at runtime​

Subtype Polymorphism

* Many shapes (poly: many, morph: shape)​
* A SortedLinkedList can “take on the shape” of a LinkedList​
* A reference to a LinkedList could actually contain a SortedLinkedList​

Dynamic Dispatch

* s.getGrade() is a polymorphic call​
* Calls the most specific method, depending on the runtime type of s​
* The subclasses of Student __override__ the getGrade method with their own implementations

What are the conditions for overriding

A method has the __same signature__ as another **non-private** and **non-static** method in __one of__ the parent classes​

* Same name​
* Same return type​
* Same number of arguments​
* Same argument types​

What does overriding do

Overriding is the thing we do in code that makes dynamic dispatch happen when the program runs.​

\
​Bound at method call time (runtime)​

* Calls the most specific method​
* new A().method() -> A​
* new B().method() -> B​
* new C().method() -> B​
* Same call site may call different methods (dynamic dispatch)​

What are the conditions for OVERLOADING

A method has the __same name and return__, **but different arguments**, than another method **on the same class**​

How is overloading done behind the scenes?

* Bound at compile-time​
* Compiler decides which method to call, based on the number and type of arguments in a method call​
* May not be the most specific method possible
* Same call-site always calls the same overloaded method

Overriding vs Overloading

An overloaded method has the __same name and return__, **but different arguments**, than another method on the same class (including inherited methods)​

\
An overridden method has the __same name and signature__ as another **non-private** method in __one of__ the parent classes​

Diamond Problem

Which method to call if a class extends from multiple parents simultaneously that override the same method

Method Resolution Order

MRO is the algorithm that Python uses to turn multiple inheritance into a single line

Java Abstract Classes

* Can declare fields that are not static (interfaces can only declare static fields)
* Abstract classes can extend other classes and implement interfaces (interfaces can only “implement” other interfaces)​
* Similar to interfaces, abstract methods do not require implementation.  Concrete classes extending abstract classes must implement all abstract methods​

Multiple Inheritance

* Allows to reuse code easily​
* The code on default methods can be reused among many classes with ease​
* Dangerous in practice​
* Diamond problem​
* Use only if needed, only when needed

Classes and Traits

* Classes are **instance generators** __first__, and **units of reuse** __second__​
* Traits are units of reuse **only**​
* Classes have a single line of hierarchy​
* Avoid multiple line problems of multiple inheritance​
* Still allows for incrementality​
* Traits are essentially a set of methods with the state they keep​
* State is per-instance, not per-class (unlike Java interfaces)​

Inheritance Root

* In many OO languages, everything is an object​
* Which means that there is an inheritance root​
* Java: java.lang.Object​
* Not true in C++, no inheritance root​
* Top type​
* Denoted as ⊤​
* All objects are instances of  ⊤​

Inheritance bottom

* Denoted as ⊥​
* Opposite of inheritance top​
* Instances of any type is also an instance of ⊤​
* Everything is a java.lang.Object​
* Instances of ⊥ are also instances of all types​

\
* Null can go anywhere an object (reference type) can go​
* There is a single instance of null​
* Close to ⊥ but not quite​

Public

* **Public**:  All classes can access​

Private

* **Private**:  Only defining class can access​
* Uses static dispatch, unlike all other modifiers

Protected

* **Protected**:  Private + subclasses​

Default

* **Default**:  Package private, only classes in the same package can access​

Minimum number of classes with a specific access modifier?

* A Java source file may have many classes​
* Only one public class, zero or more default classes

Static

* **Static**:  Field/method belongs to the class​
* Does not belong to an instance​
* Consequences:​
* Static methods use static dispatch​
* All instances share the same value for a static field

Final in Java

* Final class:  Cannot be extended​
* Final field:  Read-only​
* Not initializing it is a compilation error​
* Final method:  Cannot be overriden​
* Opposite of __virtual__ in C++​
* Final local variable or argument:  Read-only​
* Allows anonymous inner classes (and lambdas) to refer to that variable

Opaque Type

* An object with no state or methods available from the outside​
* Can’t access members of the object, but can still assign it to variables, pass it as an argument, etc.​

Casting

* Casting allows to re-interpret an existing object __a__ of type __A__ as an object of another type __B__​
* In Java, C++, C#: (B) a​

Upcasting

* __t__ has type __T__​
* **T

Downcasting

* __s__ has type __S__​
* **T

Static vs. Dynamic Types

AbstractCollection c = **new** LinkedList();

\
What is the type of c?​

* Static type:  AbstractCollection​
* We can use any operation of AbstractCollection​
* We cannot use operations only defined in LinkedList​
* Dynamic type:  LinkedList​
* The implementation of LinkedList will be used at runtime​

What does casting do at runtime?

* Casting doesn’t do anything at runtime! (except for checks and exceptions for downcasts)​
* l, c, and s are all references to exactly the same object​

When is casting unsafe?

* Downcasting is __unsafe__​
* May fail at runtime​
* __c__ may be a LinkedList, or it may be any other collection​
* E.g., a HashMap​
* Compiler inserts runtime check​
* If failed, throws a java.lang.ClassCastException

How could you make downcasting safer?

* Never fails​
* We know that​
* But compiler still inserts check​
* Think twice before using instanceof​
* You may be breaking abstraction/encapsulation​
* Typically, there’s a better way around it

instanceof

* Checks the dynamic type of an object​
* obj instanceof Class​
* True if obj is an instance of Class​
* Or an instance of a subclass of Class​
* obj instanceof Interface​
* True if obj’s class implements Interface​
* Directly or transitively

Are sideway casts valid?

NO!

“Sideways” casts fail at compile time (which makes sense, because they’d always fail at runtime!).

Summarize Casting

* Upcast​
* Never fails, always succeeds​
* Checked by the compiler​
* No check at runtime​
* Downcast​
* May fail​
* Checked by the compiler​
* Checked at runtime​
* Unsafe cast​
* Downcasts are unsafe casts​
* Invalid cast​
* Never succeeds​
* Rejected by the compiler (compilation error)​
* Casts don’t change the underlying object in any way!​

Type Coercion

* The two types are fundamentally different​
* int is not a double, double is not an int​
* However, one can be converted into the other​
* The language knows how to do it automatically​
* You can express that by using a type coercion​
* Alternative:  convert the types yourself

Static Typing

* A Java program only compiles if all the types make sense​
* Lots of guarantees:​
* Methods exist​
* A variable contains only objects of the declared type​
* A method call is valid, all arguments are correct​
* A Python program (dynamically typed) does not provide any of these guarantees​
* More bugs

Dynamic Typing

* A Python program runs if the program text can be parsed​
* Less guarantees:​
* Methods may not exist​
* A variable contains different types of objects​
* Argument types in method calls may be wrong​
* These errors only happen at runtime!​
* Programs that use static types are free of these errors​

\
* Faster implementation​
* Types may slow you down at the start​
* “I’m prototyping some code, types slow me down”​
* “I’ll add types later”

Gradual Typing

* Add types as you can, the language will figure out the rest​
* Still an active research area with lots of open questions

Subtyping

* If B is a subtype of A, then an object of B can be used where an object of A is expected​
* LinkedList is a subtype of​
* AbstractSequentialList​
* AbstractList​
* AbstractCollection​
* Object​
* An object of LinkedList can be used wherever an object of its super types is expected​
* On this course, **B

Static vs Dynamic Types Example

\
AbstactCollection c = **new** LinkedList();​

\
What is the type of c?​

* Static type:  AbstractCollection​
* We can use any operation of AbstractCollection​
* We cannot use operations only defined in LinkedList​
* Dynamic type:  LinkedList​
* The implementation of LinkedList will be used at runtime​

Liskov’s Substitution Principle

Let ϕ(**x**) be a property provable about objects **x** of type **T**.  Then ϕ(**y**) should also be true for objects **y** of type **S** where **S** is a subtype of **T**.​

* E.g., **T** has method/field m​
* More general and abstract than subtyping​
* You should consider this when you design your own OO programs

Circle-Ellipse Problem

Barbara Liskov

* Turing Award recipient in 2008​
* “Nobel Prize” for Computer Science​
* Turing lecture and interviews:  __https://amturing.acm.org/award_winners/liskov_1108679.cfm__​
* Invented the language CLU in 1975​
* Abstract Data Types​
* Iterators​
* Exceptions​
* Subtype Polymorphism​
* Liskov’s Substitution Principle​
* **And many more contributions!**

Constructor Order (Java, C++)

* From most abstract to most specific​

\


1. Run inline initializers for current class​
2. Call the super constructor​

1. Explicitly​

2. Implicitly calls the constructor without arguments​


3. Run the body of the constructor

Constructor Forwarding (Java)

* Forwarding to a constructor on the parent (i.e., **super**()) must:​
* Be done at most once​
* Be the first thing done in a constructor​


* Forwarding to **super**() can be omitted __if there is a constructor without arguments__ on the parent class​
* There is an implicit call to super() on all constructors​

How do constructors behave like?

Constructors behave like overloaded methods​

* Static dispatch:  The compiler decides which constructor to run​
* No dynamic dispatch​
* new A((List) new LinkedList()) would call A(Object)​
* There is no constructor for List, even though there is one for LinkedList​
* Only looks at static type

Limitations of constructors

Java/C++ Limitations:​

* Cannot have different constructors with same args​


* Hard to express all combinations of optional arguments

**Named and Optional Arguments (C# 4.0)**​

Better solution than overloading

**Keyword and Optional Arguments in Python**​

Constructors in C++

A a;          // Calls A::A()​

A **b**(**10**, 'x'); // Calls A::A(int,char)​

A **c**{**10**, 'x’}; // Same as above since C++11​

​

A \*d; // No constructor called​

A &e; // No constructor called

Copy Constructors in C++

* Intent:  Declare a new object which content is “the same” as an existing object​
* **Copy Constructors**:  Constructors with a single argument, which has the same type as the class being constructed

Constructor Forwarding (C++)

**class** **List** {​

  **int** size;​

  List(**int** size) { **this**.size = size; }​

  List() : List(**0**) { }​

}​

​

**class** **LinkedList extends List** {​

  Node \*first;​

  LinkedList(Node \*first) : List(**1**) { **this**.first = first; }​

  LinkedList() : List(**0**) { **this**.first = NULL; }​

}

Explicit Destruction

* C++ needs explicit destructors due to manual memory management​
* Destructors called in reverse order of constructors, on delete​
* From specific class to its parents​

Implicit Destruction (C++)

* C++ calls destructors implicitly when stack frames go out of scope​

Implicit Destruction (Rust)

* Rust only uses implicit destruction​
* No GC​
* Automatic memory management​
* Rust tracks lifetime of allocated memory​
* References “own” the data​
* Assigning  transfers ownership​
* Returning transfers ownership​
* Functions can borrow data​
* Get ownership for the duration and return ownership at the end​

**Garbage Collection and Finalizers**​

* Finalizers are methods that are called when an object is reclaimed by the garbage collector​

**You Should not use Finalizers**​

* You don’t have any guarantee that finalizers will ever run​
* Relying on them may cause your program to crash in weird and unexpected ways (e.g., see prev slide)​
* Finalizers are slow and inefficient​
* The code below is valid, which means that the GC cannot reclaim an object that has a finalizer on the current cycle​
* Needs to keep it around until the next GC cycle​

\
**class** **A** {​

  **static** Object IDontLikeGC;​

  **public** **void** **finalize**() {  A.IDontLikeGC = **this**; }​

}

**Java Weak/Soft References**​

* Object only reachable through weak or soft references are considered garbage and can be collected​
* **Weak References**:  Collected eagerly as soon as possible​
* **Soft References**:  Left as floating garbage for as long as possible​
* Useful for implementing caches​

**Java Phantom References**

* Finalizers done better​
* You get notified when a phantom reference is enqueued​
* You then must do the clean-up and then dequeue the object​
* Only then will the object be collected​
* No way to get the original reference back​
* If it is enqueued, you already lost all references​

**Reification (to reify)**​

* When you think of or treat something abstract as a physical thing.​
* To consider or represent (something abstract) as a material or concrete thing : to give definite content and form to (a concept or idea)​
* Process by which an abstract idea about a computer program is turned into an explicit data model or other object created in a programming language​

How do different languages handle reification?

* __C__ reifies memory addresses​
* E.g., **char**\* buffer = (**char**\*) **0xB800000**;​


* __Java__ reifies generics​
* E.g., List, List​


* __Javascript__, __Python__ reify their own interpreter​
* Function eval​

Reflection

* **Reification** is necessary for reflection​
* We need to represent the program as objects that the program itself can manipulate​
* **Introspection**:  Ability to __observe__ the structure of the program​
* E.g., list the methods of a class​
* **Intercession**:  Ability to __modify__ the structure of the program​
* E.g., add a new method, modify existing methods​
* Sometimes called “self-modifying code”​

Is reflection widely used in practice?

**Reflection is widely used in practice**​

\
* How does JUnit know to run this test method?​
* Use reflection to list all methods​
* Look for methods that have the @Test annotation​
* Earlier JUnit versions just looked for methods whose name started with test​
* E.g., testFeature1, testFeature2​

\
**public** **class** **Test01** {​

  **@Test**​

  **public** **void** **test**() {​

      …​

      Map

How is reflection used in practice?

* Test libraries​
* Every company that uses Java use JUnit​
* Integrated Desktop Environments (IDEs)​
* Eclipse/Netbeans are IDEs for Java written in Java​
* Use reflection to reason about developed program​
* Serialization libraries​
* Generic libraries that can convert objects into text, and text into objects​
* Debuggers, analysis tools, etc.​

Reflection in Java

* Located in package java.lang.reflect​
* Class java.lang.Class is also part of the reflection API​
* Allows to:​
* Get **R**un-**T**ime **T**ype **I**nformation (RTTI)​
* Classes, superclasses, interfaces, methods, fields​
* Create objects by class name​
* Invoke methods by name and argument types​
* Get/set contents of fields​
* Throws a ton of exceptions​

\
Basically, reflection lets you write code that does at runtime the things you usually do at compile time!

Meta-classes

* A meta-class is a class that represents other classes​
* java.lang.Class in Java​
* Instances of a meta-class are classes​
* Meta-classes define the state and behavior of other classes​
* Just as classes define the state and behavior of instances

Refleciton/Reification

Meta-Object Protocol

* Description of how an object-oriented system works​
* E.g., rules for overriding and dynamic dispatch​
* E.g., rules for how single/multiple inheritance works​
* In most languages, it cannot be modified​
* E.g., Java, C#, C++, Python​
* Some languages allow the developer to modify the MOP __while the program is running__​
* E.g., LISP, CLOS, Smalltalk

\
* In CLOS, it is possible to change the following as the program is running:​
* How to access fields (e.g., fields are never hidden)​
* Which method to call​
* Perform dynamic dispatch on the receiver? (Java)​
* Treat overloading as more dynamic dispatch?

Class Info in java.lang.Class

* **getName**: Fully qualified name of the class​
* E.g., java.lang.String​
* **getSimpleName**:  Class name as defined in the source code​
* E.g., String​
* **getModifiers**:  int that encodes modifiers