CSCI 70 Exam Polymorphism, Functional Programming

Polymorphism

• “Many forms”

  • Allow several definitions under a single function/method name

• Ex. “move” means something for a person object but means something else for a car object

2 Types of Binding

Static binding

Dynamic binding

Overloading

• type of polymorphism

• enables subroutines to share the same name

Subtype polymorphism

• Occurs in object-oriented contexts

• Method resolution within the class inheritance hierarchy introduces interesting features and complications

• Static VS. dynamic method binding

Parametric polymorphism

• abstracts a subroutine over its parameters by allowing type parameters in its definitions (generics)

Operators

• In C++, operators like =, +, *, ==, etc. can be defined, just like methods

Method overloading

• ability to define multiple methods with the same name but different parameters within a class

class Matrix {
   Matrix operator+(Matrix m) { … }
}

c = a + b;  // equiv to c = a.operator+(b);

What impacts how OO languages’ implement subtype polymorphism?

Inheritance and Dynamic Binding

• Same method across inheritance hierarchy (classes & subclasses)

• Method designed to work for a given type (class) but are applicable to its subtypes (subclasses)

• Method (same signature) applies to subtypes but can be overridden

Inheritance/Type Extension

Let D be a subclass of C (C is a superclass or a base class; D is a subclass or a derived class)

• Data and methods in C are accessible in D unless otherwise specified

Inheritance/Type Extension: Subtype polymorphism

• Ability to use D in a context that expects C

• D objects can be viewed as C objects

Which option best describes inheritance/type extension?

A mechanism in OOP where a new class reuses, extends, or modifies the behavior of an existing class. The subclass gains access to the data and methods of the superclass unless restrictions are declared. This enables code reuse, hierarchical classification, and the possibility for a superclass reference to point to subclass objects, though method overriding introduces complexity regarding which implementation is ultimately executed.

Which best defines subtype polymorphism?

The principle that a value of a subclass type may be used wherever a value of the superclass type is expected. A reference of the superclass may point to an object of the subclass, and overridden methods are resolved based on the actual object’s type during runtime, introducing dynamic dispatch.

True or False: If D is a subclass of C, then all methods in C are automatically copied into D and become independent versions, so overriding in D does not affect how those methods behave when called through a C reference.

False (Methods are not copied — they're inherited, and overriding affects dynamic dispatch.)

True or False: A subclass always has unrestricted access to all data fields of the superclass.

False (Access depends on visibility modifiers.)

Which option correctly describes how overridden methods behave when a superclass variable refers to a subclass object?

The version of the method in the subclass runs, because method dispatch is determined by the actual object type at runtime, not by variable type, which is the essence of subtype polymorphism and dynamic binding.

Which situation demonstrates subtype polymorphism correctly?

You use a subclass instance anywhere a superclass type is expected, and overridden methods behave according to the subclass version, not the superclass version.

Superclass Variables and Subclass Objects in C++

• Create Student object named s

• Take the address of that object and store it in a pointer of type person* (the superclass pointer).

• This is allowed because a Student is a Person. There’s no automatic binding to the subclass methods, but you can call virtual methods (if Person has virtual functions) and get dynamic dispatch

Superclass Variables and Subclass Objects in Java

• Create a Student object and assign it to a variable of type Person.

• Since Java variables are references, both s and p refer to the same underlying Student object.

• The type of the reference (Person) is the static type, but the actual object is a Student (dynamic type)

Superclass Variables and Subclass Objects in C++ vs Java Code

C++

student s;
person *p = &s;

Java

Student s = new Student();
Person p = s;

Static Method Binding

• Use the type of the variable (reference)

  • Determined at compile-time

  • Method is applicable to all of its subtypes anyway

  • Default 

Dynamic Method Binding

• use the type of the actual object

  • Determined at run-time (comes with overhead)

  • More appropriate response if method is overridden

  • Think of an array of superclass references referring to objects of its different

  • Subclasses

What kind of binding does C++ use by default?

Static Binding

• Else, need to mention that methods are virtual meaning programmer expects the method to be overridden by derived classes

If method is virtual…

• C++ calls the method from the actual object decided at run time

• “I will call the method that belongs to the actual object, not just the pointer type.”

• Dynamic binding

If method is not virtual…

• C++ calls the method from the pointer type decided at compile time

• “I will call the version of the method that matches the pointer type, not the actual object.”

• Static binding

Java is _____ binding by default

Dynamic Binding

• Java automatically chooses the method based on the actual object, not the variable type

• No need to write virtual like C++

• Java assumes “everything can be overridden,” unless you mark it otherwise

If you have:

• a Person class

• a Student class that extends Person

• and you store a Student inside a Person variable

Person p = new Student();
p.speak();

What version will java call for p.speak(); ?

Java will call the Student version of speak()

Because Java always asks:

“What object are you REALLY? Oh, you're a Student? Then I'll call the Student method.”

If the subclass overrides the method, what does Java do?

Java uses the subclass method.

If it doesn’t override it → Java moves up the class tree until it finds a version.

This is called method overriding.

What method to use if the Student does override the method but still wants to use the parent’s version? (Java)

super.speak();

This means: “Run the Person version of this method.”

How is dynamic binding implemented in Java?

• Through virtual method tables (“vtables”):

  • List inside Java that maps addresses of virtual methods for each class

  • Every class has its own vtable

  • Java (since its methods are virtual; except static and final methods) and C++ (for its virtual methods) employ vtables

Virtual Methods

• Methods that the programmer anticipates to be defined in derived classes (subclass) of the base class (superclass)

• Base class may or may not define the method

  • If not defined, C++ calls the method a pure virtual method (=0).

  • In Java, undefined methods are labelled abstract

Abstract Class

• A class that cannot be created directly (you can’t make an object from it)

• At least one method is abstract

• Template or blueprint for other classes

“Here are the rules and structure. The subclasses must finish the details.”

Interface (Java keyword)

• If all methods in a class are abstract/not defined

Analogy:

• Abstract class = a partially built house:

  • Some parts already built, some parts must be completed by subclasses.

• Interface = a checklist:

  • “If you call yourself this kind of thing, you MUST have all these functions.”

  • No construction, no real code—just requirements.

Concrete Classes

• Provides actual definitions for methods specified in the abstract class or interface that it extends (or implements)

Abstract classes, Interfaces, and Concrete Classes

• Abstract classes are “incomplete” concepts (e.g., shape)

• Interfaces focus on what things do (names), not how they are done

• Concrete classes flesh out the details

How are abstract classes/interfaces used meaningfully?

• Can’t create objects from an abstract class or an interface, BUT can use them as variable types

• Because they describe what the object can do, so you can refer to any object that follows those rules.

• They’re used to define shared rules or behaviors that different classes must follow

• Help enforce consistency and make programs easier to organize and extend

Static Methods and Polymorphism

• Methods applicable to a class, not its objects

  • Works on static/class-level data

• Can have the same method name across classes but these have no “inheritance” relationships

  • Overloading, not parametric or subtype polymorphism

• Resolved at compile time

• Think of public static void main(…) methods in Java

Generics and Parametric Polymorphism

• parametric polymorphism → “polymorphism by parameters (types)”

• Same code applicable in different instances (for different parameter types)

• Template code defined once and then instantiated for types as needed

  • Multiple copies of the code could be produced

Parametric Polymorphism vs Function Overloading

• Overloading = you write separate versions of the function for each type.

• Generics = you write ONE general version, and the compiler adapts it.

Why does Generics and Parametric Polymorphism exist?

• Saves time

• Less duplicated code

• Less chance for mistakes

• Works for ANY type that fits the rules

When can instantiation be done in Generics and Parametric Polymorphism?

Compile time

Containers

• Classes that hold collections of any type of object

• Types of contained objects are not important

• But the methods of the container behave in a standard way

Why are generics commonly used with containers?

• They allow containers to store any type while still being type-safe.

• You write one container class but can use it for any type: List<Integer>, List<Student>, etc.

What happens if a language does not support generics?

• Containers must store everything as Object (the most general type).

• This removes type safety and forces you to cast items manually.

What is the problem with storing everything as Object in Java?

Every element must be treated as the most general type, so the compiler can’t detect wrong types, forcing you to cast manually and risking runtime type errors.

What does “parameterizing a class” mean in the context of generics?

Class takes a type parameter, letting you use it with different data types without rewriting it.

Multiple Inheritance

• When a class has more than one parent

• Derived class inherits functionality of base classes

Why is Multiple Inheritance risky or difficult?

Because if the two parent classes have:

• the same method name,

• or the same variable,

• or conflicting behavior,

the child class might not know which version to use.

What do languages do to avoid the problems of Multiple Inheritance?

Java:

• “Mix-in inheritance”

  • A class can only extend one superclass,

  • But can implement multiple interfaces

Function

• A mapping that takes an input from a domain (set of allowed inputs) and produces an output in a range (set of possible outputs)

• Function definition has 2 parts: signature and mapping rule

Different Ways to define functions in programming languages

• Lisp (CLISP): (defun square (x) (* x x))

• Python: def square(x):

• return x*x

Function Signature

• Header

• name, domain, range

square: integer → integer
Meaning: square takes an integer and returns an integer.

Function Mapping Rule

• Body

• Describes how the input is turned into the output

• Specifies range value for each domain value

square(n) = n × n

This tells you: Take the input n, multiply it by itself, and that’s the output.

Function Application (How it works)

Definition: Using a function by giving it an input

1. Element from the domain is chosen

2. Element replaces the parameter in the definition

3. Other function applications are carried out

4. Yields an associated element (output) in the range

Function Application of square(n)

Function: square(n) = n × n
Application: square(2)
→ replace n with 2
→ compute 2 × 2
→ result is 4.

Variables in Functional Programs

• In a function definition, a variable stands for any member of the domain set

• During function application, a variable is bound to one specific value (and it never changes thereafter)

• Sometimes better to refer to variables as names

True or False: Concept of a variable in functional programs is different from a programming variable

True – because functional variables represent fixed values and do not change once defined

Values

• Traditionally, functional languages would support values for

  • primitive types (e.g., numbers and strings)

  • and a single high-level data structure type like a list

• Values are bound to variables or names

• Lisp example: 2 x * square

True or False: Functions themselves are values

True – because functions can be treated like any other data: stored, passed, and returned

Components of a Functional Programming Language

1. A set of data objects

   • Numbers, lists, etc.

2. A set of built-in functions

   • For manipulating data objects

3. A set of functional forms

   • Higher-order functions

   • For building new functions (e.g. defun in Lisp)

Lambda Calculus

• A model of computation using functions

  • Underlying theoretical model for functional languages

• Expressions of lambda calculus:

  • Identifiers (names) or constants ( e.g., y or 2 )

  • Function definition  ( e.g., x.x*x )

  • Function application ( e.g. (x.x*x 3) )

Expression Evaluation

• Outermost evaluation

  • Replace arguments before evaluating them

• Innermost evaluation

  • Evaluate arguments first before substituting

Decision in Functional Programming

• Can view “if” as a function with 3 arguments

  • Condition

  • Then-result

  • Else-result

• Example: abs(x) = if(x<0, -x, x)

“Iteration” in Functional Programming

• Use recursion to carry out the equivalent of an iterative process

• Recurrence relations are common in math function specification

• Example: fac(n) = if(n=0,1,n*fac(n-1))

Functional Programming Environments

• Environments are often interpreters that are interactive

• Commands from user are expressions that are repeatedly evaluated

• Set of bindings (variable to value) is maintained and updated on each command

Sample Languages

• LISP: list processing

• APL: assignment-oriented (not pure) but applicative

• ML: strongly-typed functional programming

• Haskell: outermost evaluation

LISP

• Lisp: List Processor

• Designed in 1958 by McCarthy (2nd oldest programming language)

• Functional programming language, interpreted

• Based on symbolic expressions, lists, functions, recursion

LISP Symbol

• String of characters (letters, digits, and hyphens)

• Examples: x Move a1 turn-right SQR

• NOT case sensitive

LISP Number

• Examples: 123 -1.234 8e99 -7.8E-23

• Just like int or double constants in C/Java

LISP Lists

• Sequence of symbols, numbers, or lists

• Examples:

  • (a b c d e 1 2 3)

  • (This list (contains (4 elements)) (really))

• Expressions that aren’t lists are atoms

  • Examples:   A   1   really

  • Note: there are other atoms outside of number and symbols

LISP Empty List

• Empty list is nil

• nil is a special symbol

  • both a list and an atom

LISP Expressions and the LISP Interpreter

• Interpreter repeatedly:

  • Prompts for a well-formed expression

  • Evaluates the expression

  • Returns a response

>(expt 5 2)
25
>(first ’((a b) c (1 2) 3))
(a b)

Functions

• (a b c) when evaluated means a is evaluated with args b and c

  • Ex: (expt 5 2) evaluates to 25

• Syntax: (func arg1 arg2 arg3 …)

• Some functions allow a variable number of arguments

Ex: (+ 1 2 3 9 8 7) evaluates to 30

LISP Built-in Functions

1. Numeric functions

2. Quote function

3. List access functions

4. List construction functions

5. Predicates

6. setq

7. defun

8. Conditions: if and cond

Numeric Functions: Arithmetic operators

+ - * /

• e.g., (+ 5 8) evaluates to 13

• Multiple arguments applicable, e.g. (+ 5 8 3 2) evaluates to 18

Numeric Functions: sqrt

one argument, computes square root

Numeric Functions: expt

• 2 arguments, raises first argument by the second argumente

• e.g., (expt 6 2) evaluates to 36

Numeric Functions: min, max

may have one or more arguments

Numeric Functions: mod

2 arguments, computes a remainder

Numeric Functions: abs

absolute value

Numeric Functions: sin, cos, tan

trigonometric functions

Quote Function

• quote or ’ prevents an expression from being evaluated

• (quote exp) same as ’exp

>(expt 3 2)
9
>’(expt 3 2)
(expt 3 2)
a
Error since a can’t be evaluated
>’a
a

List Access Functions: first or CAR

returns the first element of its argument list

List Access Functions: rest or CDR

returns a list containing all but the first element of a list

List Access Functions: last

returns the last element (as a list) of a list

List Access Functions: length

returns the number of elements in a list

What does this output?

(first ‘(a 1 b 2 z))

a

What does this output?

(rest ‘(a 1 b 2 z))

(1 b 2 z)

What does this output?

(last ‘(a 1 b 2 z))

(z) sends as a list

What does this output?

(length ‘(a 1 b 2 z))

5

What does this output?

(first ‘((a 1) b (2) z))

(a 1)

What does this output?

(rest ‘((a 1) b (2) z))

(b (2) z)

What does this output?

(length ‘((a 1) b (2) z))

4

What does this output?

(rest ‘(x))

NIL

List Construction Functions: cons

• takes two arguments; returns the result of inserting the first argument in front of the second argument (opposite of first/car)

  • (cons ‘a ‘(b c d)) => (a b c d)

List Construction Functions: append

• takes two list arguments; returns a concatenation of the two lists

  • (append ‘(1 a 2) ‘(x y)) => (1 a 2 x y)

List Construction Functions: list

• returns a list of all its arguments

  • (list ‘a ‘b ‘x ‘y ‘z) => (a b x y z)

What does this output?

(cons ‘(a b) ‘(1 2 3))

((a b) 1 2 3)

What does this output?

(append ‘(a b) ‘(1 2 3))

(a b 1 2 3)

What does this output?

(list ‘(a b) ‘(1 2 3))

((a b) (1 2 3))

Predicates

listp

numberp

integerp

symbolp

atom

and (allows variable args)

or (allows variable args)

not