CSE 2231 Final

Abstract class

A "partial" or "incomplete" class that contains bodies for some but (typically) not all of the methods of the interfaces it claims to implement

Factoring out common code

Method bodies that can be written once— and work for any implementation of NaturalNumberKernel because they are programmed to that interface—have been factored out into an abstract class

Can you instantiate an abstract class?

No - You can't use an abstract class like a normal class and create objects from it

UUT

Unit under testing

How to achieve single-point control over change in this situation

"Re-route" all UUT constructor calls to another method, which then calls the UUT constructor, so only the body of that one method needs to be changed to accommodate a different UUT

Class ending with "L"

Kernel class that directly represents the new type using a component from Java libraries

Instance variable

There is a distinct variable (with the same name) for each instance of the class in which it is declared

Criteria for kernel implementation

1. Easy to understand and write

2. More efficient

Sequence3 on Stack

Sequence represented as 2 stacks, left and right. Sequence = rev(left) + right

Representation of sequence is 2 stacks "facing each other" in the middle of sequence

Client view

Mathematical models, method contracts

Kernel interface shows WHAT the software does

Implementer view

Data representation, algorithms

Kernel class shows HOW the software does it

Abstract state space

The set of all possible math model values as seen by the client

Concrete state space

The set of all possible math model values of the data representation

Abstraction function

How to interpret any concrete value (that satisfies the representation invariant) as an abstract value?

@correspondence

Representation invariant

What configurations of values of the instance variables can arise?

@convention

Why hashing?

1. Can be quickly identified

2. Must contain the item

T/F: Nodes in a linked list must always have consecutive memory addresses?

False

T/F: Nodes in a linked list can be accessed in constant time?

False

T/F: Nodes in a linked list require at least one smart node?

False

T/F: Nodes in a linked list can be accessed sequentially in linear time?

True

T/F: The process of building a heap will completely sort its elements?

False

T/F: A subroutine is needed to adjust the root of a subtree to its proper position, assuming the subtree is a heap except for its root

True

T/F: Heaps are parameterized by a type and an ordering process?

True

T/F: A heap is a binary tree with extra constraints on its shape and organization

True

Collection type definition

Any type whose abstract mathematical model involves: string, set, multiset, tree, binary tree

Collection type examples

Array, queue, set, sequence, stack, map, sorting machine

Array pros

-Direct access

-Constant time access (regardless of length)

Array cons

-Fixed size; can run out of room

-Fixed size; initialization might be expensive if entries go unused

-Adding/removing entires in the middle requires moving other entries, which is slow

Array is represented by...

A contiguous block of memory locations with consecutive memory addresses so the memory address of the entry at index i can be directly calculated from the memory address of the first entry, by using simple arithmetic

JVM

Java Virtual Machine

Binary tree

-Can be empty tree

-Or can be non-empty tree consisting of root node and 2 subtrees

-Mathematical type: Binary trees with any label of type T

Traversal Orders

1. Pre-order: Root, left, right

2. In-order: Left, root, right

3. Post-order: Left, right, root

Binary Search Tree (BST)

A binary tree where the left node < root, and right node > root

Sorting Machine

-Allows adding elements of type T to a

collection of such elements, and then removing them one at a time in sorted order

-Mathematical model: 3-tuple

{insertion_mode: boolean,

ordering: binary relation on T,

contents: finite multiset of T}

Why is sorting machine better than sort?

-If all elements are already sorted by the end of "changeToExtractionMode", then there is no difference in performance

-If elements are not already sorted by the end of "changeToExtractionMode", then the performance advantage is that you don't need to remove all the elements

T/F: Smart nodes can prevent run-time errors arising from the code managing of a linked list?

False

T/F: Smart nodes can provide significantly faster performance when manipulating the elements of a linked list

False

T/F: Smart nodes can make initial setup of the linked list faster

False

T/F: Smart nodes can aid removal of special cases from some methods that work with a linked list

True

What is the data structure of a doubly-linked list?

2 references per node: one to the "next" node and one to the "previous" node

TF

Type family interface whose kernel is being implemented

What does the standard method newInstance() do?

Returns a new object with the same DYNAMIC type as this, having an initial value (usually 0 or empty)

Server (BugsWorld)

Keeps track of "the world" - Processes client requests, resolves conflicts

Client (BugsWorld)

Each client program simulates creature (bug) behavior for all creatures of one species

Displays (BugsWorld)

Each display shows the current state of the world, plus some statistics about the simulation

3 Compiler Parts

Tokenizer --> Parser --> Code Generator

(TPC)

Abstract Syntax Tree (AST)

-Tree model of an entire program or certain "program structure" (Ex: A statement or expression)

-"Abstract" because characters used in the concrete program do not appear in this representation

-Mathematical model: 3-tuple

{KIND of statement,

TEST of condition,

CALL of instruction}

NOTE: Either test or call is relevant information, depending on the kind of statement it is

Statement

-Component family which allows manipulation of ASTs for BL statements

-Mathematical model: Tree of statement_label

5 Kinds of Statements

1. Block --> Child can be anything except block

2. If --> Child must be block

3. While --> Child must be block

4. If_Else --> 2 children must both be blocks

5. Call --> 0 children

T/F: You can use == to test equality of enums

True

Enumeration (Enum)

Special construct that easily allows use of meaningful symbolic names where you might otherwise be inclined to declare int variables and give them arbitrary values to participate just in equality tests

Statement no-arg constructor

this = compose((BLOCK, ?, ?), <>)

Program

-Component family which allows manipulation of values modeling complete BL programs

-Mathematical model: 3-tuple

{name: IDENTIFIER,

context: CONTEXT,

body: STATEMENT_MODEL}

Program no-arg constructor

this = ("Unnamed", {}, compose((BLOCK, ?, ?), <>))

Refactoring

Restructuring code without changing its behavior for the purpose of improving readability, making small syntax changes, etc.

Context-Free Grammar (CFG)

-A set of formation rules for strings in a language that satisfies certain technical conditions

-Used to implement a recursive-descent parser

Recursive-Descent Parser

An algorithm to parse a BL program and construct the corresponding Program object

Terminal symbols

Terminates at the point, stop writing when you hit that symbol, typically bolded

Non-terminal symbols

Only appears on the left side of a production, typically italicized

Metagrammar

Used to define the context free grammar itself, not a part of the alphabet

Derivation

-A sequence of specific rewrite-rule applications that begin with the start symbol and continue until only terminal symbols remain

-Can be depicted in a derivation tree

Ambiguity

When some strings in the language of the CFG have more than one derivation tree, which makes it harder to evaluate to the correct outcome

Token

A single entity in the language

T/F: Purpose of a tokenizer is to transform source code into machine/object code the computer can more easily understand or interpret?

False (I think this is the parser's job)

T/F: Purpose of a tokenizer is to remove whitespace and separate the source code into small, meaningful units?

True

T/F: Purpose of a tokenizer is to construct an abstract representation of a program that holds information about its intended meaning?

False

BL Tokenizer

Treats string of consecutive whitespace characters as separators between tokens, since the tokens are the words

2 main uses of CGFs

1. Generate strings in the language

2. Detect if a string is in the language

Parsing

Going from a string to its derivation tree/AST

5 Rules of a Recursive-Descent Parser

1. One parse/method/non-terminal symbol

2. Non-terminal symbol on RHS of rewrite rule --> Call parse method for that non-terminal symbol

3. Terminal symbol on RHS of rewrite rule --> Consume token from input token string

4. "|" in CFG --> "If-else" in parser

5. "{ }" in CFG --> "While" in parser

CFG Symbols { }

-Indicates that the enclosed sequence of symbols can occur 0+ times

-Helps turn a left-recursive CFG into an equivalent CFG that can be parsed by recursive-descent

Parsing an arithmetic expression?

The parser evaluates it by turning the string of tokens (in the language of the CFG) to the value of that expression as an int

Expression

-Starts with term

-Followed by 0+ add-ops and terms

Term

-Starts with factor

-Followed by 0+ mult-ops and factors

Factor

-Starts with "("

-Followed by expression

-Ends with ")"

-Otherwise, it is a number token

2 facts recognized by modern software

1. Modern software consists of potentially large number of components, that are composed into larger components/systems

2. A class is a component with its client-visible specifications in the interface it implements

How many interfaces can an interface extend?

One or more

T/F: An interface be generic?

True

What contains a description of WHAT the software does?

Interface

What contains a description of HOW the software does it?

Class

What CAN interfaces define?

-Instance methods

-Static final variables

(IS)

What CAN'T interfaces define?

-Constructors

-Instance variables (Not client-view information!!)

-Static methods (Java 8 allows this, but it goes against use of interfaces for client views)

(CIS)

All instance methods in an interface are automatically?

public abstract

T/F: It is usual for an interface to define variables?

False

T/F: Constructors are instance methods?

False; constructors can't be defined in an interface, which is where instance methods are defined

Kernel Interface defines...

1. Mathematical model

2. Contract(s) for constructors

3. Contract(s) for kernel methods

4. Contract(s) for methods from Java library interfaces without their own contract specifications (Ex: Iterator, comparator)

Enhanced Interface defines...

1. Contract(s) for all other methods for the type

Kernel methods should be a ______________ of ______________ that is ______________.

a) minimal set

b) methods

c) functionally complete

A functionally complete set of kernel methods is powerful enough to...

1. Give variable of the type ANY allowable value

2. Determine the value of a variable of the type

3. Implement "equals" and "toString"

4. Check every kernel method's precondition

(GDI-Chick)

Circularity

Interface A extends something of general type interface B in initialization, and interface B extends interface A

A java interface defines a ____ ____ along with its set of ________ _______

a) type name

b) instance methods

T/F: An interface type may be used in Java even if there is no implementation of it in scope

True

Interfaces are _______-____ construct

Compile-time

After a Java program compiles, object types are kept at ___-____ construct

Run-time

Declared (Static) Type

Interface type (left side)

Object (Dynamic) Type

Class type (right side)

T/F: The declared type of a variable may be an interface type

True

T/F: The object type can be an interface type

False; Because you may not instantiate a variable using new followed by an interface type

What happens if the declared type is an interface type?

The object type (a class) MUST implement the declared type (an interface)

What happens to declared types once a Java program compiles?

They disappear in the JVM