Appendix C: Glossary
A
abstract machine A mathematical model of computation.
adder A computer component that adds two numbers.
algorithm A step-by-step procedure for solving a problem, such as Euclid’s algorithm, mergesort, and any Turing machine.
alias Two (or more) variables that refer to the same object.
alphabet A finite set of symbols, such as the binary alphabet {a, b}.
ALU (arithmetic logic unit) A computer's computational engine.
API (application programming interface) Specification of the set of operations that characterize how a client can use a data type.
array A data structure that holds a sequence of values of the same type, with support for creation, indexed access, indexed assignment, and iteration.
argument An expression that Java evaluates and passes by value to a method.
ASCII (American Standard Code for Information Interchange) A widely used standard for encoding English text, which is incorporated into Unicode.
assignment statement A Java statement consisting of a variable name followed by the equals sign (=) followed by an expression, which directs Java to evaluate the expression and to assign the value produced to the variable.
B
bit A binary digit (0 or 1).
Boolean algebra A formal system for symbolic manipulation of boolean expressions. boolean expression An expression that evaluates to a value of type boolean.
boolean function A function mapping boolean values to a boolean value.
Boolean logic The study of boolean functions.
boolean value 0 or 1; true or false.
booksite library A library created by the authors for use in the book, such as StdIn, StdOut, StdDraw, and StdAudio.
built-in type A data type built into the Java language, such as int, double, boolean, char, and String.
bus connection See data path.
bus mux A multiplexer for switching bus connections.
buzzer An unstable feedback loop in a circuit.
C
Church–Turing thesis. The idea that a Turing machine can perform any computation (decide a language or compute a function) that can be described by any physically realizable computing device.
circuit An interconnected network of wires, power connections, and switches.
class The Java construct to implement a user-defined data type, providing a template to create and manipulate objects holding values of the type, as specified by an API.
.class file A file with a .class extension that contains Java bytecode, suitable for execution on the Java Virtual Machine.
class variable See static variable.
client A program that uses an implementation via an API.
clock A sequential circuit that sequences the fetch and execute control lines in a processor.
combinational circuit A circuit with no loops.
command line The active line in the terminal application; used to invoke system commands and to run programs.
command-line argument A string passed to a program at the command line.
comment Explanatory text (ignored by the compiler) to help a reader understand the purpose of code.
comparable data type A Java data type that implements the Comparable interface and defines a total order.
compile-time error An error in syntax found by the compiler.
compiler A program that translates a program from a high-level language into a low-level language. The Java compiler translates a .java file (containing Java source code) to a .class file (containing Java bytecode).
computability The ability to solve a problem on a computer. Some problems, such as the halting problem, are not computable.
conditional statement A statement that performs a different computation depending on the value of one or more boolean expressions, such as an if, if-else, or switch statement.
constant variable A variable whose value is known at compile time and does not change during execution of the program (or from one execution of the program to the next).
constructor A special data-type method that creates and initializes a new object.
control A combinational circuit that organizes the control lines in a processor. control line A wire that carries a control signal (as opposed to a data value).
controlled switch A circuit element that can break a connection.
CPU (central processing unit) The circuit that implements a computer.
D
data path A set of wires connecting one module to another (also called a bus connection).
data structure A way to organize data in a computer (usually to save time or space), such as an array, a resizing array, a linked list, or a binary search tree.
data type A set of values and a set of operations defined on those values.
declaring a variable Specifying the name and type of a variable.
decoder A combinational circuit for selecting an output.
demultiplexer A combinational circuit that switches inputs to selected outputs.
deterministic A computation in which every step is completely determined from the current state.
deterministic finite-state automaton (DFA) A deterministic abstract machine that recognizes a regular language.
E
element One of the components in an array.
evaluate an expression Simplify an expression to a value by applying operators to the operands in the expression. Operator precedence, operator associativity, and order of evaluation determine the order in which to apply the operators to the operands.
exception An exceptional condition or error at run time.
exponential-time algorithm An algorithm that runs in time bounded below by an exponential function of the input size.
expression A combination of literals, variables, operators, and method calls that Java evaluates to produce a value.
F
fetch–increment–execute cycle Process underlying a computer’s operation.
flip-flop A sequential circuit that implements a memory bit.
floating point Generic description of the use of “scientific notation” to represent real numbers on a computer (see IEEE 754).
formal language A set of strings over a given alphabet. function See static method.
functional interface An interface with exactly one method.
G
garbage collection The process of automatically identifying and freeing memory when it is no longer in use.
gate A small combinational circuit that implements a boolean function, such as AND, OR, and NOT gates.
generalized regular expression pattern match (grep) A classic approach to using regular expressions for searching for patterns.
generic class A class that is parameterized by one or more type parameter, such as Stack, Queue, ST, or SET
global variable A variable whose scope is the entire program or file. See also static variable.
H
halting problem Turing’s original non-computable problem.
hashing Transforming a data-type value into an integer in a given range, so that different keys are unlikely to map to the same integer.
hash table A symbol-table implementation based on hashing.
hexadecimal Base-16 representation of integers.
I
identifier A name used to identify a variable, method, class, or other entity.
IEEE 754 International standard for floating-point computations, which is used in modern computer hardware (see floating point).
immutable data type A data type for which the data-type value of any instance cannot change, such as Integer, String, or Complex.
immutable object An object whose data-type value cannot change.
implementation A program that implements a set of methods defined in an API, for use by a client.
initializing a variable Assigning a value to a variable for the first time in a program.
instance An object of a particular class.
instance method The implementation of a data-type operation (a method that is invoked with respect to a particular object).
instance variable A variable defined inside a class (but outside any method) that represents a data-type value (data associated with each instance of the class).
instruction register (IR) Machine component that holds the instruction being executed.
interface A contract for a class to implement a certain set of methods.
interpreter A program that executes a program written in a high-level language, one line at a time. The Java Virtual Machine interprets Java bytecode and executes it on your computer.
intractability The inability to solve a problem on a computer in polynomial time. item One of the objects in a collection.
iterable data type A data type that implements the Iterable interface and can be used with a foreach loop, such as Stack, Queue, or SET
iterator A data type that implements the Iterator interface. Used to implement iterable data types. Java bytecode The low-level, machine-independent language used by the Java Virtual Machine.
J
.java file A file that contains a program written in the Java programming language.
Java programming language A general-purpose, object-oriented programming language.
Java Virtual Machine (JVM) The program that executes Java bytecode on a microprocessor, using both an both an interpreter and a just-in-time compiler.
just-in-time-compiler A compiler that continuously translates a program in a high-level language to a lower-level language, while the program executes. Java’s just-in-time compiler translates from Java bytecode to native machine language.
K
Kleene's theorem The idea that regular expressions (REs), deterministic finite-state automata (DFAs) and nondeterministic finite-state automata (NFAs) all characterize the regular languages.
L
lambda calculus The universal model of computation introduced by Alonso Church.
lambda expression An anonymous function that you can pass around and execute later.
library A .java file structured so that its features can be reused in other Java programs.
linked list A data structure that consists of a sequence of nodes, where each node contains a reference to the next node in the sequence.
literal Source-code representation of a data-type value for built-in types, such as 123, "Hello", or true.
local variable A variable defined within a method, whose scope is limited to that method.
loop A statement that repeatedly performs a computation depending on the value of some boolean expression, such as a for or while statement.
M
machine-language instruction An operation built into computer hardware, such as add, load, and branch zero in TOY.
machine-language program A sequence of machine-language instructions to be executed on a computer.
masking Isolating a group of bits in a computer word.
memory Machine component that holds data and instructions.
method A named sequence of statements that can be called by other code to perform a computation
method call An expression that executes a method and returns a value.
modular programming A style of programming that emphasizes using separate, independent modules to address a task.
module (software) An independent program, such as a Java class, that implements an API. A computer component, typically with bus inputs and outputs.
module (hardware) A computer component, typically with bus inputs and outputs.
Moore's law The observation, by Gordon Moore, that both processor power and memory capacity have doubled every two years since the introduction of integrated circuits in the 1960s.
multiplexer A combinational circuit that switches selected inputs to outputs.
mutable data type A data type for which the data-type value of an instance can change, such as Counter, Picture, or arrays.
mutable object An object whose data-type value can change.
N
nondeterministic A computation where multiple next steps are possible from one or more states.
nondeterministic finite-state automaton (NFA) A nondeterministic abstract machine that recognizes a regular language.
NP The set of all search problems, such as boolean equation satisfiability, factoring, and all problems in P.
NP-complete A characterization of the “hardest” problems in NP, such as boolean equation satisfiability, vertex cover, and integer linear inequality satisfiability.
null reference The special literal null that represents a reference to no object.
O
object An in-computer-memory representation of a value from a particular data type, characterized by its state (data-type value), behavior (data-type operations), and identity (location in memory).
object-oriented programming A style of programming that emphasizes modeling real-world or abstract entities using data types and objects.
object reference A concrete representation of the object’s identity (typically, the memory address where the object is stored).
operand A value on which an operator operates.
operating system The program on your computer that manages resources and provides common services for programs and applications.
operator A special symbol (or sequence of symbols) that represents a built-in data-type operation, such as +, -, *, and [].
operator associativity Rules that determine in which order to apply operators that have the same precedence, such as 1 - 2 - 3.
operator precedence Rules that determine in which order to apply the operators in an expression, such as 1 + 2 * 3.
order of evaluation The order in which subexpressions, such as f1() + f2() * f5(f3(), f4()), are evaluated. Regardless of operator precedence or operator associativity, Java evaluates subexpres-sions from left to right. Java evaluates method arguments from left to right, prior to calling the method.
overflow When the value of the result of an arithmetic operation exceeds the maximum possible value.
overloading a method Defining two or more methods with the same name (but different parameter lists).
overloading an operator Defining the behavior of an operator—such as +, *, <=, and []—for a data type. Java does not support operator overloading.
overriding a method Redefining an inherited method, such as equals() or hashCode().
P
P The set of all search problems for which there exist polynomial-time algorithms, such as sorting, shortest path, and linear inequality satisfiability.
P ≠ NP conjecture The notorious unresolved conjecture that some search problems cannot be solved in polynomial time.
package A collection of related classes and interfaces that share a common namespace. The package java.lang contains the most fundamental classes and interfaces and is imported automatically; the package java.util contains Java’s Collections Framework.
paper tape A primitive early input/output medium.
parameter variable A variable specified in the definition of a method. It is initialized to the corresponding argument when the method is called.
parsing Converting a string to an internal representation.
pass by value Java's style of passing arguments to methods—either as a data-type value (for primitive types) or as an object reference (for reference types).
PDP-8 A real computer in use in the 1970s.
polymorphism Using the same API (or partial API) for different types of data.
polynomial-time algorithm An algorithm that is guaranteed to run in time bounded by some polynomial function of the input size.
polynomial-time reduction Using a subroutine for one problem to help solve another problem efficiently.
primitive data type One of the eight data types defined by Java, which include boolean, char, double, and int. A variable of a primitive type stores the data-type value itself.
private Data-type implementation code that is not to be referenced by clients.
program A sequence of instructions to be executed on a computer.
program counter (PC) Machine component that holds the address of the next instruction to be executed.
pure function A function that, given the same arguments, always returns the same value, without producing any observable side effect.
R
reduction Using a subroutine for one problem to help solve another problem.
reference type A class type, interface type, or array type, such as String, Charge, Comparable, or int[]. A variable of a reference type stores an object reference, not the data-type value itself.
register A machine component that holds a word for processing.
regular expression (RE) An expression that uses union, concatenation, closure, and parentheses to specify a regular language.
regular language A language that can be recognized by a DFA or specified by a regular expression.
resizing array A data structure that ensures that a constant fraction of an array's elements are used.
return value The value provided to the caller as the result of a method call.
run-time error An error that occurs while the program is executing.
S
scope of a variable The part of a program that can refer to that variable by name.
search problem A problem with the property that there exists a polynomial-time algorithm to check the validity of any purported solution.
side effect A change in state, such as printing output, reading input, throwing an exception, or modifying the value of some persistent object (instance variable, parameter variable, or global variable).
sequential circuit A circuit having loops (feedback).
source code A program or program fragment in a high-level programming language, such as Java.
standard input, output, drawing, and audio Our input/output modules for Java.
statement An instruction that Java can execute, such as an assignment statement, an if statement, a while statement, and a return statement.
static method The implementation of a function in a Java class, such as Math.abs(), Euclid.gcd(), and StdIn.readInt().
static variable A variable associated with a class.
string A finite sequence of alphabet symbols.
sum-of-products representation A standard algebraic representation for boolean functions. terminal window An application for your operating system that accepts commands.
T
this Within an instance method or constructor, a keyword that refers to the object whose method or constructor is being called.
throw an exception Signal a compile-time or run-time error.
TOY An imaginary computer, similar to a PDP-8, designed for this book.
trace Step-by-step description of the operation of a program.
Turing machine (TM) The universal model of computation introduced by Alan Turing.
two's complement representation Convention for representing negative integers in a computer.
type parameter A placeholder in a generic class for some concrete type that is specified by the client.
U
Unicode An international standard for encoding text.
unit testing The practice of including code in every module that tests the code in that module.
universal Turing machine (UTM) A Turing machine that can simulate an arbitrary Turing machine on an arbitrary input.
universality The idea that all sufficiently powerful computing devices can decide the same set of formal languages and compute the same set of mathematical functions.
V
variable An entity that holds a value. Each Java variable has a name, type, and scope.
virtual machine A definition or implementation of a computer as a program on another computer.
von Neumann machine Computer architecture in which instructions and data are stored in the same memory.
W
wire A circuit element that carries a boolean value.
word A fixed-length sequence of bits, treated as a unit in a computer’s architecture.
wrapper type A reference type corresponding to one of the primitive types, such as Integer, Double, Boolean, or Character.