PLC Midterm Terms

Everything marked by Pterry the Pterodactyl plus anything that seemed like a term that could become a flashcard.

Software Design

The process of defining the specification and structure of a program from an outside perspective.

Concerns questions like how the program’s implementation will be interfaced with the API, how the client and supplier interact, and how the caller and callee of the program behave with each other.

Specification

The requirements of a program or parts of a program, especially considering their inputs and outputs.

Structure

In terms of software design, the layout of how a program is or will be built.

Interface

Defines what a components of the program does and its contract.

Complexity

How difficult a codebase is to understand, design, modify, test, and maintain. This can also refer to how much space or time it takes to run the program.

Maintainability

How easy it is to understand a codebase in order to continue its longevity, especially considering environment updates and security.

Contract

A specification of a part of a program (like a function, class, etc), including preconditions and postconditions.

Preconditions

A public set of requirements set by a contract that must be met by the caller. This ensures the callee can run smoothly.

Postconditions

A public set of requirements set by the contract that describes what is outputted by the callee (implementation). This allows the caller to know what the output should be.

Client

The party responsible for satisfying preconditions. These are usually users.

Supplier

The party responsible for satisfying postconditions if the preconditions are met. These are the designers of the program.

Design by Contract

A software design technique that utilizes contracts, preconditions, and postconditions to structure how a program is built and interacted with. The client and supplier are both expected to fulfill their required preconditions and postconditions, but can still verify their counterpart’s requirements as needed.

Invariants

An aspect of mutable data, like classes, that define a valid state of a program. This is affected by the precondition and postcondition, and may be temporarily broken within methods of the program. Otherwise, the program must maintain this valid state.

The Pseudocode Problem

A problem when writing sample code in that certain operators and keywords may have different behaviors when considering different languages. For example, operators, indexing, and ranges may differ between languages, making the same sample code behave differently depending on what language the reader defaults to.

Regex (regular expression)

A language that defines a pattern for matching text values. These are used for searching and validating text, especially user inputs like numbers, emails, and file paths.

Domain Specific Language (DSL)

A language that focuses on solving a specific problem. These have their own grammars, parsers, and compilers.

Scunthorpe Problem

A problem that arises when using regex to filter wanted words where patterns will match anything that fulfills it, regardless of context. See Scunthorpe and Medieval.

Coverage

A metric for how well test cases “cover” the behavior of code. This is helpful for identifying untested behavior and edge cases and how well the software is tested.

This must be considered in context, because implementing this has a cost. 90% of this could mean that the other 10% of the program is not valuable.

Equivalence Classes

Unique behaviors of a program that can be tested. These are used in a superset of tests that start with a baseline test of the bare minimum, and adds variations on the baseline for more coverage with minimal changes.

Edge Cases

Specific equivalence classes (even just values) that have distinct behaviors from others, typical to a smaller set of values or combinations of values that are less likely to occur in normal programs and cases.

There are a few categories of this:

• Values (null, 0, empty lists)

• Boundary values

• Error Cases

• Extreme inputs

Error Cases

A subset of edge cases that cover known error conditions like invalid user inputs and IO exceptions.

Object-Oriented Programming (OOP)

An approach to programming that uses classes and objects with methods and inheritance to structure the language. More advanced versions of this include encapsulation and polymorphism.

Used improperly, this can make a codebase needlessly verbose and complex.

Inheritance

A principle of object-oriented programming in that subclasses (children) derive state and methods from their superclass (parent).

This is useful for code reuse, sharing, and behavior extension.

Classes can override parent methods for further customization.

Good usage of this principle includes:

• Generic methods

• Knowing what subtypes might do

• Prioritizing behavior over the signature

Otherwise, this principle can be commonly misused.

Encapsulation

A principle of object-oriented programming that describes that individual classes can contain their own methods and states. This information can be regulated by the class through member methods.

Polymorphism

A principle of object-oriented programming that describes that a single interface, function, or method to have different behaviors depending on what object or data type is being called.

State

The current value of any stored, mutable data. A class controls this for objects.

Field

A ‘space’ for any stored data.

Java Records

These define “simple” objects focused on data access/storage and are immutable. These have fields, getters, equals(), hashCode(), and toString(), but no setters. This also has a copy invariant, stating that records are just carriers of field values and will copy over the values.

For example, Token, Ast, and RuntimeValue are records.

Java Class

A data container in Java that:

• can extend only one class

• can implement multiple interfaces and inherit their states

• can define fields, constructors, and methods; has a state

• methods can be public, protected, or private

  • can be instantiated if not abstract

Java Interface

A data container in Java that:

• always implicitly extends Object

• can extend multiple interfaces

• can only define methods; has no state

• methods may only be public

  • can only be extended or implemented by another interface/class

Lexing

Also known as scanning. The process of grouping characters into tokens.

Token

The ‘building blocks’ of grammars that define a language. These are built by the lexer, and used by the parser.

Grammar

A formal definition of what strings are valid in a language. Inputs are either accepted or rejected. These have named rules that can be referenced by other rules as well, which can be recursive. These are not unique.

Ambiguous

Describes a grammar that has multiple valid derivations to accept an input.

Maximal munch

A lexing technique that dictates that the longest possible token should be prioritized. This also helps resolve ambiguity.

Committing

A lexing and parsing technique that involves externally specifying when a partially matched rule must accept. This is especially useful for clearer error messages and for resolving ambiguity.

Rule

A component of a grammar that defines productions for the language and uses other rules. These are notated by capital letters in our grammar.

Production

A component of a grammar that specifies how to replace one symbol with another.

Terminal

The raw characters that are part of the language; the accepted character set. These are notated by lowercase letters in our grammar.

Chomsky Hierarchy

A classification of grammars/languages based on their capabilities, outlining what rule combinations are possible and their complexities.

Regular grammar (Regular language)

This type of grammar has all terminals consistently on the left or right of rules. This can be also represented by a regular expression and be parsed by a finite state machine.

Pros/Cons:

• Good for simple inputs; not good for hierarchical inputs

• Finite state machines are simple to create and implement

• Finite state machines run in linear time

ex: S ::= aS | bX , X ::= cX | ε

Finite state machine (FSM) (Finite state automata) (FSA)

A flowchart that has a finite number of states and transitions between those states. They start at an initial state (marked by a large arrow), and each step of the input transitions the FSM to the next state. If no valid transition exists, the input is rejected. If the input ends on a final state (marked by a double-circle), the input is accepted.

Deterministic Finite State Machine (DFA) (Deterministic FSM)

A type of finite state machine that requires all state transitions to be deterministic for the next input.

• On the flowchart, transitioning arrows must have a requirement

• Inputs must transition to only one state (no having one input have an ambiguous transition)

This is an easier model of computation, but needs optimizing for regex.

Non-Deterministic Finite State Machine (NDFA) (Non-Deterministic FSM)

A type of finite state machine that allows multiple transitions to be considered simultaneously for the next input

• Inputs may transition to multiple states

• “epsilon”/empty transitions are allowed

Harder model of computation, but better matches regex structure

Context-Free Grammar (Context-Free Language)

This type of grammar has all rules use a single, nonterminal character (like another rule). Parsed by a push-down automaton. This category represents ‘languages that are feasible to use’

Pros/Cons:

• Easier for humans to read and understand

• Easier for machines to parse/validate

• Subclasses of these exist specifically for optimal parsing

ex: X ::= ε, X ::= aYa, Y :: bXb