access time: the elapsed time between a request for data from a memory and the time when the data is furnished.
actual parameter: the parameter passed to a subroutine when it is called during execution.
algorithm: a precisely specified procedure for computing a result or solving a problem in a finite number of steps. (From al-Khuw=arizmi, Arab mathematician, 825 A.D.)
alist: abbreviation of association list.
ALU: arithmetic and logic unit, a part of a central processor that performs computations on data.
ambiguity: a case in which more than one meaning might be assigned to a language construct.
anonymous type: a type that is specified without giving it a name.
argument: parameter.
array: a linear sequence of elements. An element can be accessed by specifying its index; usually, access to any element takes the same amount of time.
artificial intelligence (AI): the branch of computer science that studies the computational basis of intelligent behavior.
ascending: a sort in which the values of items increases, as in an ordinary alphabetic order.
ASCII: (pronounced ``ask-ee'') the American Standard Code for Information Interchange, a commonly used character code.
assignment: giving a new value to a variable, which will retain that value until the value is changed by another assignment.
assignment compatible: describes a case in which a value of one type can be assigned to a variable of the same or a different type. For example, an integer value may be assigned to a real variable, and the compiler will convert the value to real.
assignment statement: a statement that specifies that the value of a variable should be set to the value of an expression.
association list: a list of pairs, where each pair consists of a key and a corresponding value.
atom: a terminal value in a list structure, e.g a symbol or number. Anything that is not a pair (cons cell) is an atom in Common Lisp.
auxiliary function: a function written to perform some task for, or do the work of, another function.
Babbage, Charles: English mathematician (1791 -- 1871) who designed mechanical calculating machines that were forerunners of the modern computer.
base case: a simple case (of a recursive problem) that can be solved directly without further recursion.
bignum: short for ``big number'': an integer of arbitrary size.
big O() notation: an expression of the order of a computation: how the time (or storage) required by a program increases as the size of the problem becomes large.
binary: a number representation in arabic numerals using the base 2. Each digit is 0 or 1.
binary file: a file whose contents are machine binary words, usually specific to a single kind of machine.
binary search: a search of a binary tree or other structure in which the structure is divided in half at each step of the search.
binary tree: a data structure in which each record may have two successors (children).
binding: the association of a name with a value.
bit: a contraction of binary digit: a 0 or 1. The smallest unit of information representation in a computer.
Boole, George: English mathematician (1815 -- 1864) who developed Boolean algebra.
Boolean: a type consisting of values true and false and operations and, or, and not. A Boolean value can be represented by one bit, conventionally as false = 0 and true = 1.
Boolean algebra: an algebra using Boolean variables and operations and, or, and not.
branch: a change in the location at which instructions are being executed in a program (also, jump or go-to); an instruction or command that causes a branch.
byte: a group of 8 bits, which can be used to represent a character.
Caesar cipher: a form of encryption in which each letter is replaced by the letter n later in the alphabet.
call by reference: a form of parameter transmission in which the address of the parameter is transmitted to a procedure. Specified by var parameters in Pascal.
call by value: a form of parameter transmission in which a copy of the value of a parameter is sent to a procedure.
case insensitive: a comparison of characters or strings in which the case of the characters does not matter.
case sensitive: a comparison of characters or strings in which the case of the characters does matter.
CD-ROM: compact disk read-only memory.
central processor: the main computational unit of a computer, including control, an arithmetic and logic unit (ALU), and registers.
character: a type that represents a single character, often as a single byte of storage.
character code: an assignment of numeric codes to letters, numbers, and punctuation symbols, e.g. ASCII.
close: to terminate the use of a file by a program. When a file is closed, the operating system performs final actions such as writing out the last buffer of information and updating the file directory.
code: machine-readable specification of a computer program.
combination: in Scheme, a function call, consisting of a function name and arguments written within parentheses.
compiler: a program that translates a program written in a higher-level language into a lower-level language or machine language.
concatenation: placing two or more sequences adjacent to form a new sequence consisting of the contents of both.
conditional: a statement such as if or case that takes different actions depending on some condition.
cons cell: see dotted pair.
constant: a value that cannot change; a specification of a constant in a programming language, such as 3 or true.
count-controlled loop: a loop in which the number of repetitions is determined by the value of a counter.
CPU: central processing unit; see central processor.
data abstraction: the separation of the logical properties or operations on data from the implementation of the data and operations.
data type: a set of values and one or more operations on the values. Examples include integer, real, rational, character, string, and list.
decryption: conversion of an encrypted message to a form that is readable.
dereference: to convert from a pointer to the thing denoted by the pointer, i.e., the record it points to.
descending: a sort in which the values of items decreases.
destructive operation: an operation that alters existing data that might also be used by other parts of the program.
disk: a peripheral device that stores data on a rotating disk using magnetic or optical recording.
dotted pair: or pair: a record structure in Lisp, containing two pointer values accessed by the functions car and cdr. A pair is created by the function cons. Also, cons cell.
driver: a program whose purpose is to provide data to a procedure for testing.
dynamic: performed at runtime.
dynamic storage: storage that is assigned to the program at runtime, e.g. by cons or new, and accessed by means of a pointer.
dynamic type checking: type checking performed at runtime, as in Lisp.
dynamic variable: dynamic storage.
element: an individual component of an array, list, or set. Written x S in set notation.
encapsulation: allowing access to data or procedures only via a specified interface.
encryption: conversion of a message to a form that is unreadable but still contains the original information.
enumerate: to write out or create the members of a set individually.
enumerated type: a scalar type consisting of a specified set of ordered values.
environment: the set of variable values seen by a section of program code during execution.
evaluation: the process of determining the value of an expression.
event-controlled loop: a loop that terminates when some event or condition becomes true (or false).
exact number: a numeric type, such as integer or rational in Scheme, whose values are represented exactly in the computer.
exponent: the part of a floating-point number that specifies a power of the number base by which the mantissa is multiplied.
external representation: the representation of data used outside the computer, i.e., typed in by the user or printed out.
field: a named component of a record.
file: a sequence of characters or data records, often stored on a disk.
first-class: describes a language element that may be named by variables, passed as arguments to procedures, returned as results of procedures, and included in data structures [Abelson & Sussman, p. 76]. Scheme has first-class procedures.
fixed-point: 1. an integer number representation, or a representation in which the location of the decimal point is fixed. 2. for a given function, an input such that the output of the function is the same value.
floating-point number: an approximate representation of a real number value in scientific notation, consisting of a fractional part (mantissa) and an exponent. E.g. 0.196E31 represents the number 0.196 10^31 .
formal parameter: a parameter specified in the definition of a procedure.
function: a procedure that returns a value.
functional programming: programming in terms of function calls. In pure functional programming, there are no side effects such as assignment.
garbage: 1. data that has no meaningful connection to reality. 2. dynamic memory in Lisp that is no longer being used.
garbage collection: the process of reclaiming and recycling dynamic memory that is not being used.
GIGO: an abbreviation of the phrase ``Garbage in, garbage out.'' That is, if the input of a program is garbage, its output will be also.
global variable: a variable that can be accessed by all parts of a program.
goto: an instruction that specifies that the instruction execution is to begin at a different location. Also, branch or jump.
hexadecimal: a number representation in arabic numerals using the base 16, with digits 0 through 9 and A through F. One hexadecimal digit occupies 4 bits.
hiding: using encapsulation to hide the implementation of a program or data, so that it can only be accessed through a public interface.
high-level language: a language that allows programs to be expressed in a way that is shorter than machine language and is usually machine-independent.
higher-order procedure: a procedure that manipulates procedures [Abelson & Sussman, p. 57].
I/O: input/output.
identifier: a symbol that names a variable, procedure, type, etc.
implicit begin: a place in a Scheme program where multiple statements can be placed without enclosing them in a begin.
index: a number that specifies the desired element of an array.
inexact number: a numeric type, such as floating point, whose values are represented in the computer as approximations rather than exact values.
infinite loop: a loop that never terminates.
infix notation: a notation for arithmetic expressions in which an operator is written between its operands.
initialize: to give an initial value to a variable.
input/output: transfer of data between a CPU and a peripheral device.
integer: a number that is restricted to whole values, e.g. 1 or -7. A data type that represents integers within a certain range.
interface: 1. a connection between two devices, such as a CPU and a peripheral device, that allows them to exchange data. 2. a specification of the input and output of a procedure or program module.
internal representation:the representation of data used inside the computer.
interpreter: a program that reads instructions in some language and executes them or simulates their execution.
intersection: the intersection of two sets is the set of elements that are common to both. Written S T .
invariant: a condition that is always true at a certain point in a program.
invocation: a call to a procedure.
isomorphism: a one-to-one mapping between two sets that preserves the relationship of elements under corresponding operations on each set.
iteration: repeated execution of the same sequence of instructions.
jump: see goto.
key: a number or code that is needed in order to decrypt a message.
keyword: an identifier such as if that is part of a programming language and specifies a particular kind of statement.
lexical scoping: a method of determining scope in which the location of a reference in the text of a program determines the variables that can be accessed.
Lisp: a computer language; the name is an abbreviation of LISt Processing. Lisp is a functional language in which an operation (function name) is written, followed by its arguments, inside parentheses, e.g. (+ x 3).
list: a sequence of records in which each record contains a pointer to the next record. In Lisp, a list is composed of pairs and is written as a sequence of items enclosed in parentheses. Also, linked list.
local variable: a variable that can be accessed by only a part of a program.
loop: a sequence of instructions that is executed repeatedly, typically by a branch from the bottom of the sequence back to the top.
Lovelace, Ada: the daughter of the poet Lord Byron and an associate of Charles Babbage.
machine language: the language executed by computer hardware.
macro: a user-specifiable programming language construct that is expanded into source language code at compilation or interpretation time. In Lisp, a macro is a function that produces Lisp code as its result.
mantissa: the fractional part of a floating-point number.
mapping: a function from a set (the domain) to a second set (the range) that assigns a unique member of the second set to each member of the first set. In Lisp, a function that applies a specified function to each member of a list and produces a list of the resulting values.
memory: the part of a computer that stores both the program and data values.
mnemonic: an abbreviation that is chosen to be easy for humans to remember.
named type: a type that is given a name.
nesting: inclusion of a statement or loop as part of another statement or loop.
octal: a number representation in arabic numerals using the base 8, with digits 0 through 7. One octal digit occupies 3 bits.
open: to initiate the use of a file by a program. A file must be opened before I/O to the file can take place. cf. close.
operation: a function on values that produces a new value.
pair: see dotted pair.
parameter: a variable in the definition of a procedure that can be assigned different values when the procedure is called.
pattern matching: testing whether an input sentence or structure matches a pattern that may contain variables. Use of pattern matching followed by substitution into an output pattern to transform expressions.
peripheral: a device such as a keyboard, display, or printer that is interfaced to a CPU.
pointer: a value that denotes the location of data, such as the memory address of the data.
polynomial: describes an algorithm whose performance is specified by a polynomial function, e.g. O(n) or O(n^2).
port: an abstraction of a channel via which input/output may be performed in a higher-level language.
precedence: an ordering of operators such that if two operators are adjacent in a flat (unparenthesized) expression, the operator with higher precedence is performed first.
predicate: a function that returns true or false as its value.
prefix notation: a notation for arithmetic expressions in which an operator is written before its operands.
private: accessible only from part of a program or from code that is closely associated with a kind of data.
procedure: a part of a program that is abstracted as a unit and that can be called from multiple places, often with parameters.
prompt: one or more characters printed by an interpreter to indicate that it is ready for user input.
proper subset: a set that is a subset of another set and smaller than the other set. Written S T .
pseudocode: a way of writing program descriptions that is similar to programming languages but may include English descriptions and does not have a precise syntax.
public: accessible to anyone or to all parts of a program.
public key: an encryption key that is published and available to anyone.
public-key cryptosystem: a system for encrypting messages in which the key for encryption is public but in which decryption can only be performed by the intended recipient of the message.
quote: to specify that the value of data is the data itself rather than the evaluation of the data. Specified in Lisp with the character ' or the pseudo-function quote.
RAM: random-access memory.
random-access memory: memory whose access time is constant, independent of the address that is accessed. Abbreviated RAM.
rational: a number that is an integer or ratio of two integers, e.g. 1 or 13 .
read-eval-print loop: in Lisp, the process of reading input from the user, evaluating it, and printing the result, repeatedly. This is the ``top level'' interpreter of Lisp; in our notation, we could write it as: (while #t (write (eval (read))))
read-only memory: a kind of memory whose values can be read but cannot be changed. Abbreviated ROM.
real: in mathematics, a number that represents any value along a continuous line. The term real is often used for floating-point numbers.
record: a block of contiguous storage containing named fields that may have different types.
recursion: a kind of programming in which a procedure may call itself as a subroutine.
register: a memory cell inside a central processor that is used to hold values and results of computations.
requirements: a specification of the task a program should perform.
reserved word: a word that is used as part of a programming language and may not be used as a name by the user.
ROM: read-only memory.
runtime: the period of time during which a program is executing.
scalar: a value set consisting of a finite ordered set of possible values.
Scheme: a small, elegant dialect of Lisp.
scope: the range of program code over which a variable is visible.
scope rules: the rules that determine where in a program a name can be accessed.
sentinel: a special or illegal value that is used in a sequence of input to indicate the end of the input.
sentinel-controlled loop: a loop that terminates when a sentinel value is found.
separator: a symbol that separates two similar items, such as blank in Lisp or ; in Pascal.
set: a collection of distinct objects (elements or members) such that for any object, it can be determined whether the object belongs to the collection.
set difference: the members of the first set that do not appear in the second set. Written S - T .
S-expression: short for Symbolic expression, defined recursively:
side effect: an effect of a function other than returning a value, e.g., changing the value of a variable or printing.
sort: to arrange elements of a sequence in order according to some criterion, e.g. alphabetic order.
special form: a form in Lisp that is evaluated using a nonstandard evaluation method (the standard method is to evaluate all arguments first), e.g. if, quote, define, set!.
stack frame: an area of the execution stack, corresponding to one subroutine call and containing values for variables of that call.
state: the value of a variable or set of values of a procedure.
static: describes properties of a program that can be determined at compile time, i.e. without running the program.
static type checking: type checking performed at compile time.
string: a sequence of characters.
strongly typed: describes a language such as Pascal, in which all types can be checked at compile time so that no type errors can occur at runtime.
structure sharing: this occurs when the same memory locations are part of two or more data structures.
stub: a dummy procedure definition that has a name and parameters but whose body is not yet implemented.
subprogram: subroutine or function.
subrange: a value set formed by taking a contiguous subsequence of values from a finite ordered set such as integer.
subroutine: a procedure that is called by another program to help it accomplish its task.
subset: a set is a subset of another if each of its elements is a member of the other set. Written S T .
substitution: replacement of variables in an expression or pattern by values of the variables.
substring: a contiguous sequence of characters taken from a string.
symbol: a name that is used to stand for some object.
tail recursion: recursion in which the value returned by a function either does not involve another recursive call to that function or is exactly the value returned by a recursive call.
termination: the property of a program that it is guaranteed to finish.
terminator: a symbol that terminates a statement.
top level: in Lisp, the read-eval-print loop or Lisp interpreter. To return to top level after a Lisp error means to discard the partial execution of user code that occurred up to the point of the error.
top level of a list: a linear chain of dotted pair cells linked by the cdr pointers.
transformation: changing an expression from one form to another, e.g. by pattern matching following by substitution.
type: data type.
type-change function: a function that changes the type of its argument but not its value, e.g. ord or chr in Pascal.
type compatible: a case in which two types are compatible, e.g. for use in an operation.
type error: an attempt to perform an operation on arguments of the wrong types.
union: the union of two sets is the set of elements that appear in either of the sets. Written S T .
value: a possible state of a variable.
value parameter: a parameter passed using call by value.
variable: a memory location that can contain a value. A variable often has a name and, in many languages, a fixed type.
variable parameter: a parameter passed using call by reference; a var parameter in Pascal.
vector: term for an array in Scheme.
von Neumann, John: American mathematician (1903 - 1957) who invented the CPU architecture used in most modern computers.
well-founded ordering: an ordering that can be put into correspondence with the natural numbers (positive integers).
whitespace: characters whose printed representation is blank: space, tab, and newline.