PLS - Final Exam

OOP Satisfy Important Needs in Software Design

• Need to reuse software components as much as possible

• Need to modify program behavior with minimal changes to existing code

• Need to maintain the independence of different components

• Need to restrict access to internal details of software components

Four basic ways a software component can be modified for reuse

• Extension of the data or operations (adding methods to a queue)

• Redefinition of one or more of the operations (changing definition of area for a square if derived from rectangle)

• Abstraction (collection of similar operations from two different components into a new component)

• Polymorphism (the extension of the type of data that operations can apply to) (operator overloading)

Application framework

A collection of related software resources (usually in OOP) for developer use

Smalltalk

• Most consistent approach to object-oriented paradigm

• Everything is an object, including constants and the classes themselves (Purely object-oriented)

• Includes garbage collection and a windowing system with menus and a mouse

• For variables, uses reference semantics, not value semantics (a variable refers to an object, it does not contain an object)

Smalltalk object properties and behaviors:

Message

Receiver

Method

Sender

Mutators

Message passing

Interface

Selector

Message: a request for service

Receiver: object that receives a message

Method: how Smalltalk performs a service

Sender: originator of the message

Mutators: messages that result in a change of state in the receiver object

Message passing: the process of sending and receiving messages

Interface: the set of messages that an object recognizes

Selector: the message name

Smalltalk message types:

Class

Instance

Unary

Keyword

Binary

Class message: a message sent to a class

Instance message: a message sent to an instance of a class

Unary message: one with no arguments

Keyword messages: messages that expect arguments; name ends in a colon

Binary messages: allow you to write arithmetic and comparison expressions with infix notation

Smalltalk inheritance

Supports the reuse of structure and behavior

Smalltalk polymorphism

The use of the same names for messages requesting similar services from different classes

Ex. Smalltalk iterators which can work with any types of collections

Smalltalk concrete classes

Classes whose objects are normally created and manipulated by programs

Ex. Time and Date

Smalltalk abstract classes

Serve as repositories of common properties and behaviors for classes below them in the hierarchy

Ex. Magnitude and Number

Collection

A container whose elements are organized in a specific manner

Java

• Originally intended for systems embedded in appliances

• Emphasis was on portability

• Programs compile to machine-independent byte code (.class) run by the JVM

• Supports compile-time type checking

• Conventional syntax and a large set of libraries

• Purely object-oriented except for scalar data types

• Uses reference semantics (all objects passed by reference)

• Defaults to static binding but uses dynamic binding if an object’s method cannot be determined at compile time

Java method types:

Class

Accessor

Class method: a static method (belongs to the class itself, not specific instances)

Accessor methods: allow programs to view but not modify the internal state of a class

In Java, all classes inherit from which class?

Object

Java constructors

Specify initial values for instance variables and perform other initialization actions

private keyword limits access to variables and accessor methods

Default constructor

Has no parameters

Constructor chaining

When one constructor calls another

Java does not allow

Operator overloading

Multimethods - more than one object can be the target of a method call

Java framework

A collection of related classes

Java interface

A set of operations on objects of a given type

Only contains the type name and a set of public method headers

Classes may implement more than one interface

Static typing

All data types must be explicitly specified at compile time.

Java generic collections

Exploit parametric polymorphism

Ex. List<T>, Set<T>

Java private inner class

A class defined within another class

Java backing store

The collection object on which the iterator object is operating

Static binding

Process of determining at compile time which implementation of a method to use by determining the object’s actual class

Dynamic binding

Process of determining at runtime which implementation of a method to use by determining the object’s actual class

Java 8 streams

• Wrappers around a data source allowing for fast and convenient bulk processing of data.

• They do not store data or modify the underlying data source.

• They are lazy and performing computation and consuming elements only as needed.

C++

• A compromise language that contains most of the C language as a subset, plus other features, some object-oriented, some not

• Now includes multiple inheritance, templates, operator overloading, and exceptions

• Objects are not automatically pointers or references but are identical to the struct type

• No automatic garbage collection

• Allows multiple inheritance using a comma-separated list of base classes

• A class can open up details of its implementation to another class or function by specifying that class or function as a friend

C++ classes are composed of

Data members: instance variables

Member functions: methods

Derived classes: subclasses

Base classes: superclasses

C++ protection levels

Public - members are accessible to client code and derived classes

Protected - members are inaccessible to client code but are accessible to derived classes

Private - members are inaccessible to client and to derived classes

C++ destructors

Called when an object is deallocated

C++ template classes

Used to define generic collections in C++

C++ virtual declaration

The only type of member function which can be dynamically bound

An abstract function which cannot be called

Renders the containing class abstract

Must be overridden in a derived class

C++ repeated inheritance

Occurs when separate copies of each class are created on an inheritance path due to multiple inheritance

Can be fixed by using the virtual keyword to cause shared inheritance

Ruby

• Designed for productivity and fun

• An interpreted, high-level, general-purpose programming language, influenced by Perl and Smalltalk

• Most notorious for the web frameworks that are built on it

• All computation done via message passing

• Metaprogramming - Everything is an object

• Dynamic, not compiled

• Variables and scope - the name of a variable automatically determines its scope

• Has garbage collection

• Allows independent threading

• Allows dynamic polymorphism

• Has the unless keyword which is the opposite of if

Ruby singleton classes

Every object has two classes - a regular class and a singleton class

An object’s singleton class is a nameless class whose only instance is that object and is automatically created

These singleton classes can hold object specific methods

Ruby flexibility

Methods can be added to existing classes without subclasses, operators can be overloaded, and the behavior of the standard library can be redefined at runtime

Ruby superclass of all the classes

BasicObject

Ruby class access control

All instance variables hid by default unless accessor methods are created

Methods are public by default but protect and private access control can be specified

Ruby blocks

Every method may be passed a block and executed via the yield expression.

Similar to anonymous functions.

They have parameters, local variables, and can manipulate variables from enclosing scopes.

Must be declared as a Proc object to be used as a first-class function.

Ruby mixins

Classes may only have one superclass but may contain any number of modules

Ruby module

A container for methods. Its methods are mixed in while defining the class.

Ruby method lookup order

1. Object’s singleton class

2. Modules mixed into the singleton class

3. Object’s class

4. Modules mixed into the class

5. Class’s superclass

Ruby metaprogramming

Querying and manipulating classes, modules, methods, and procs.

Writing code that adds or removes classes, methods, and instance variables

OOP design issues

Features represent dynamic rather than static capabilities which introduces a runtime penalty.

Hard to properly organize the runtime environment and create a translator capable of discovering optimizations.

Design of the program is extremely important to gain maximum advantage of an OOP language.

Incorporating classes into the type system

Three options:

1. Exclude classes from type checking

2. Make classes type constructors: classes become part of the language type system

3. Let classes become the type system: all other structured types are then excluded from the system

Parametric polymorphism

Type parameters remain unspecified in declarations

Overloading

Different functions or method declarations share the same name but have different types of parameters in each

Subtype polymorphism

All operations of one type can be applied to another type

Inheritance

A kind of subtype polymorphism

Double-dispatch problem

Inheritance and overloading do not account for binary or (n-ary) methods that may need overloading based on class membership in two or more parameters

Object allocation

Java and Smalltalk allocate them on the heap

C++ allows them to be allocated directly on the stack or as a pointer

Single Responsibility Principle

There should never be more than one reason for a class to change.

Each component should have only one responsibility.

Open Closed Principle

New implementations can be added to extend functionality while the fundamental functionalities of a component will not change.

Attempts to make existing components resilient to changing requirements.

Liskov Substitution Principle

Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it.

Interface Segregation Principle

A class should not have to implement members that it does not need.

Dependency Inversion Principle

High-level modules should not depend on low-level modules.

Both should depend on abstractions.

Decouple low level components and high level components through a common abstraction

Python

• OOP with exception handling and garbage collection

• Many data types, huge standard libraries, many user-contributed packages

• Used for scripting and general-purpose programming

• Everything is an object

• Supports delayed evaluation through iterators and generators

Python unique features

Variables hold values and can be changed at any point

Lists are dynamic

List comprehensions allow multiple lines of code to be collapsed into one

Has dictionaries which store key-value pairs

All classes inherit from object

Supports multiple inheritance

Every method accepts the default self argument

Python module

Classes or functions stored in a file which can be imported

Python decorators

Decorators enable ways to enhance the behavior of functions and classes without actually adding any code directly inside the function or class.

They are a nice solution to cross-cutting concerns such as logging, transaction maintenance, persistence, authentication and so on

MATLAB

• Short for matrix laboratory

• Designed to operate primarily on whole matrices and arrays

• Focused on matrix manipulations, data visualization, and algorithm implementation (good for Eng, Sci, Econ)

• Both a language and an application

• Good for rapid prototyping and “programming in the small”

• All variables are multidimensional arrays and passed by value

• Uses 1-based indices

• Provides many predefined functions

• Allows many types of graph plots and anonymous functions

• Everything is an object

• Does not support function overloading and no generics

• Method dispatching based on the leftmost object in the argument list

• Supports integration with C/C++ and Python

Go

• Open-source programming language

• Designed at Google to improve programming productivity in an era of multicore networked machines and large codebases

• Designers desired to have a language that provided static typing and run-time efficiency, readability and usability, and high performance

• Every Go program is made up of packages (programs start in package main)

• Return values can be named and then paired with a naked return statement

• := short assignment operator can be used in a function when declaring variables

• Has pointers but no pointer arithmetic

• Has no classes but methods can be defined on types

• Methods with pointer receivers will modify the value to which the receiver points

• Allows interfaces which are implicit, separating the definition from an implementation

• Empty interfaces can handle unknown types

• Allows type parameters/generic functions

Go Defer

Defers the execution of a function until right before the surrounding function returns. These function calls are placed on a stack and executed in LIFO order

Go Arrays and Slices

Arrays cannot be resized

Slices are dynamically-sized and describe a section of an underlying array. Changing elements of a slice changes the underlying array. Slices have length (items in the slice) and capacity (items in the underlying array). The length of a slice can be increased by re-slicing it.

To build a dynamic array, make a slice with a large capacity but an empty length

Go closure

A function value that references variables from outside its body

Go stringer

A type that can describe itself as a string. The stringer type is a built-in interface

Go goroutine

A lightweight thread managed by the Go runtime

Runs in the same address space, so shared memory access must be synchronized

Go channels

A typed conduit through which you can send and receive values

These block until the other side is ready

Kotlin

• General-purpose programming language with type inference

• Designed to be better than Java but also interoperate with Java, allowing companies to transition

• Preferred language for Android app development

• Classes have common superclass any

• Classes can only be inherited if marked with the open keyword (single inheritance only)

• Class members are public and final by default

• Supports top-level functions

• when replaces the switch statement

• Variables are read-only or mutable

• Strings are immutable

• Singleton classes can be declared using the object keyword

• Distinguishes between nullable and non-nullable types

• Nullable types declared with a ? after the type name

• Users can add functions to any class without the need of derivation using extension functions

ALGOL billion-dollar mistake

Putting in a null reference.

Data Oriented Programming

Driven by the need for efficiency, especially in video game programming where large numbers of objects are needed.

Array of structures vs Structure of arrays ex. Easier to Load a single field into memory that contains an array for each person rather than load each person object into memory. Better to work around components of objects than the objects themselves.

Entity Component System

Architecture of organizing data that decouples functionality from data.

Entity - a general object that contains components, essentially an ID

Components - strictly hold data for one aspect of the object

Systems - affect components and are stateless

DOD Advantages and disadvantages

Advantages

• Parallelization

• Cache utilization

• Modularity

• Testing

• Performance and organization

Disadvantages

• Small difference in small projects

• Hard to understand

• Interfacing with existing code is harder

• Namespaces and file structure?

Aspect Oriented Programming

• Attempts to increase the modularity of code by allowing the separation of cross-cutting concerns

• Accomplishes this by adding additional behavior to existing code without modifying the code itself

• Pointcut - the code location to be modified

• Advice - a class of functions which modify other functions when they are later run

• Aspect = advice + pointcut

• Languages: AspectJ

• C, LISP, Python, and Ruby allow forms of AOP

Crosscutting concerns

Parts of a program that rely on or must affect many other parts of the system. They do not fit well in OOP or procedural programming.

They cannot be modularized because they typically follow a functional decomposition.

Ex. caching, error detection, logging, security & authentication, etc.

The implementation of a concern is scattered if

Code is spread out over multiple modules

The implementation of a concern is tangled if

Code is intermixed with code that implements other concerns

AOP Implementation

Two main ways:

• A combined program is produced, valid in the original language

• The ultimate environment is updated to understand and implement AOP features

Aspect weaver

Reads the aspect-oriented code and generates appropriate object oriented code with the aspects integrated

Can be done by preprocessors, during the build process, or at runtime.

Deploy-time weaving subclasses existing classes so the modification are introduced by method-overriding, leaving the originals untouched

AOP concerns

• Logic mistakes in expressing crosscutting can lead to widespread programming failure

• Control flow is obscured, known as obliviousness of application

• Forces developers to have whole-program knowledge to reason about the execution of an aspect-oriented program

NVIDIA CUDA

• Parallel programming models require specific hardware specifications

• An entire platform with its own compiler, hardware support, and API calls

• Has a large toolkit, offering software such as the NVCC compiler which separates parts of the program marked for parallel execution

• CUDA C programs execute on both the CPU and the GPU

• Host - CPU running the program

• Devices - GPUs which run the parallel sections

• Kernel - functions designed for the GPU

• Grid - Runs the kernel on a 3D array of blocks, which are a 3D arrays of threads. (Thread blocks may be divided into warps)

CUDA -capable GPU

• Has a large number of streaming multiprocessors

• Each SM has several streaming processors

• SPs share control logic and instruction cache

• SMs can access global memory and each has a local cache

• Each block gets its own SM, each thread its own SP

• Important to consider that if your program has to keep going to main memory, the GPU may slow down computation

Task parallelism

Separates the process into a bunch of independent tasks.

Memory between the host and the device need to be copied over.

Unified memory is shared between the host and device and removes the need for copying.

It is important to know device specifics, such as warp sizes and number of threads to optimize a kernel

Try to avoid different execution paths (divergence) within the same warp

Memory in CUDA

More important to choose block dimensions for performance than to match the data

Memory-bound program - memory access time is the limiting factor

Tiling memory - Breaking up the matrix into tiles to collaborate between threads. Threads will store results from global memory in the shared memory store. Reduces the trips to global memory by the width of a tile.

Accessing memory in the correct order and reducing trips to global memory can have a huge impact on performance

Threads in CUDA

Barrier synchronization forces all threads to catch up, since they execute in any order.

APOD Design Cycle for parallelizing existing programs

→ Assess (Analyze program to determine where the bulk of the work happens and find an upper bound on performance gains)

→ Parallelize (Write kernels or call GPU accelerated library functions)

→ Optimize (Optimize the code and make sure you approach what was expected in the assessment phase)

→ Deploy (Deploy the GPU-accelerated code

Strong vs weak scaling when estimating performance gain

Consider strong when the problem size remains constant

Consider weak if the problem size grows to fill the available processors

Optimizing an application

• Use the effective bandwidth of your computation as a metric when measure performance benefits

• Minimize traffic between the host and the device

• Coalesce traffic to global memory and minimize use of global memory through shared memory access

• Avoid divergence/different execution paths within the same warp

• Update drivers