| Brian
Harvey University of California, Berkeley |
| Matthew
Wright University of California, Santa Barbara |
| Download PDF version |
| Back to Table of Contents |
| BACK chapter thread NEXT |
| MIT Press web page for Simply Scheme |
|
|
|
ADT: See abstract data type.
a-list: Synonym for association list.
abstract data type: A type that isn't provided automatically by Scheme, but that the programmer invents. In order to create an abstract data type, a programmer must define selectors and constructors for that type, and possibly also mutators.
abstraction: An approach to complex problems in which the solution is built in layers. The structures needed to solve the problem (algorithms and data structures) are implemented using lower-level capabilities and given names that can then be used as if they were primitive facilities.
actual argument expression: An expression that produces an actual
argument value. In (+ 2 (* 3 5)), the subexpression (* 3 5) is
an actual argument expression, since it provides an argument for the
invocation of +.
actual argument value: A value used as an argument to a
procedure. For example, in the expression (+ 2 (* 3 5)), the number
15 is an actual argument value.
aggregate: An object that consists of a number of other objects. For example, a sentence is an aggregate whose elements are words. Lists and vectors are also aggregates. A word can be thought of, for some purposes, as an aggregate whose elements are one-letter words.
algorithm: A method for solving a problem. A computer program is the expression of an algorithm in a particular programming language; the same algorithm might also be expressed in a different language.
apply: To invoke a procedure with arguments. For example,
"Apply the procedure + to the arguments 3 and 4."
argument: A datum provided to a procedure. For example, in
(square 13), 13 is the argument to square.
association list: A list in which each element contains a name and a corresponding value. The list is used to look up a value, given a name.
atomic expression: An expression that isn't composed of smaller pieces.
backtracking: A programming technique in which the program tries one possible solution to a problem, but tries a different solution if the first isn't successful.
base case: In a recursive procedure, the part that solves the smallest possible version of the problem without needing a recursive invocation.
body: An expression, part of the definition of a procedure, that is evaluated when that procedure is invoked. For example, in
(define (square x) (* x x))
the expression (* x x) is the body of the square
procedure.
Boolean: The value #t, meaning "true," or #f,
meaning "false."
branch node: A tree node with children. The opposite of a leaf node.
bug: An error in a program. This word did not originate with Grace Hopper finding an actual insect inside a malfunctioning computer; she may have done so, but the terminology predates computers by centuries.
call: Synonym for invoke.
cell: One location in a spreadsheet.
children: The nodes directly under this one, in a tree. (See also siblings and parent.)
composition of functions: Using the value returned by a function
as an argument to another. In the expression (+ 2 (* 3 5)), the value
returned by the * function is used as an argument to the +
function.
compound expression: An expression that contains subexpressions. Opposite of atomic expression.
compound procedure: A procedure that a programmer defines. This is the opposite of a primitive procedure.
constructor: A procedure that returns a new object of a certain
type. For example, the word procedure is a constructor that takes
words as arguments and returns a new word. See also selector, mutator, and abstract data type.
data abstraction: The invention of abstract data types.
data structure: A mechanism through which several pieces of information are combined into one larger unit. The most appropriate mechanism will depend on the ways in which the small pieces are used in the program, for example, sequentially or in arbitrary order.
database program: A program that maintains an organized collection of data, with facilities to modify or delete old entries, add new entries, and select certain entries for display.
datum: The piece of information stored in each node of a tree.
debugging: The process by which a programmer finds and corrects mistakes in a program. No interesting program works the first time; debugging is a skill to develop, not something to be ashamed of.
destructive: A destructive procedure is one that modifies its
arguments. Since the only data type in this book that can be modified is
the vector, all destructive procedures call vector-set!.
domain: The set of all legal arguments to a function. For
example, the domain of the count function is the set of all sentences
and all words.
effect: Something a procedure does other than return a value. For example, a procedure might create a file on disk, or print something to the screen, or change the contents of a vector.
empty sentence: The sentence (), which has no words in it.
empty word: The word "", which has no letters in it.
end-of-file object: What the file-reading procedures return if asked to read a file with no more unread data.
expression: The representation in Scheme notation of a request to
perform a computation. An expression is either an atomic expression,
such as 345 or x, or a compound expression consisting of
one or more subexpressions enclosed in parentheses, such as (+ 3 4).
field: A single component of a database record. For example, "title" is a field in our example database of albums.
first-class data: Data with the following four properties:
| • | It can be the argument to a procedure. |
|---|
| • | It can be the return value from a procedure. |
|---|
| • | It can be given a name. |
|---|
| • | It can be part of a data aggregate. |
|---|
forest: A list of trees.
formal parameter: In a procedure definition, the name given to refer to an argument. In
(define (square x) (* x x))
x is the formal parameter. (Note that this is not the same
thing as an actual argument! When we invoke square later, the
argument will be a number, such as 5. The parameter is the name for
that number, not the number itself.)
function: A transformation of information that associates a
return value with some number of argument values. There may
be many different algorithms that compute the same function; the
function itself is the relationship between argument values and return
value, no matter how it may be implemented.
functional programming: A style of programming in which programs are expressed as compositions of functions, emphasizing their arguments and return values. Compare to sequential programming.
global variable: A variable created with define, which has
meaning everywhere in the program. The opposite of a local
variable.
helper procedure: A procedure that exists to help another procedure do its work. Normally, a user does not invoke a helper procedure directly. Instead, the user invokes a top-level procedure, which invokes the helper procedure to assist it in coming up with the answer.
higher-order procedure: A procedure whose domain or range includes other procedures.
index: A number used to select one of the elements of a vector.
initialization procedure: A procedure that doesn't do any work except to invoke a helper procedure with appropriate argument values.
interactive: An interactive program or programming language does its work in response to messages typed by the user at a keyboard (or perhaps indicated with a pointing device like a mouse). Each message from the user causes the program to respond in some way. By contrast, a non-interactive program works with input data that have been prepared in advance.
invoke: To ask a procedure to do its work and come up with a
return value. For example, "Invoke the + procedure," or "Invoke
the + procedure with the arguments 3 and 4."
keyword: The name of a special form.
kludge: A method that gets the job done but isn't very elegant. Usually the result is a program that can't be extended the next time a new feature is needed.
leaf node: A tree node with no children. The opposite of a branch node.
leap of faith: A method for understanding recursion in which you say to yourself, "I'm going to assume that the recursive call always returns the right answer," and then use the answer from the recursive call to produce the answer to the entire problem.
list: A data aggregate containing elements that may be of any type.
local variable: A variable that associates a formal parameter
name with an actual argument value. It's "local" because the variable
exists only within one procedure invocation. (This includes variables
created by let.) This is the opposite of a global variable.
mutable: A data structure is mutable if its contents can change.
mutator: A procedure that changes the value of a data object. In
this book, the only mutable data objects we use are vectors, so every
mutator is implemented using vector-set!. See also selector,
constructor, and abstract data type.
mutual recursion: The program structure in which one procedure invokes another, and the second invokes the first.
node: An element of a tree. A node has a datum and zero or more children.
parent: The node above this one, in a tree. (See also children and siblings.)
pattern matcher: A program that takes a pattern and a piece of data as inputs and says whether or not that piece of data is one that the pattern describes. We present a pattern matcher in Chapter 16.
plumbing diagram: A pictorial representation of the composition of functions, with the return value from one procedure connected to an argument intake of another.
port: An object that Scheme uses to keep track of a file that is currently open for reading or writing.
portable: A portable program is one that can be run in more than one version of Scheme or on more than one computer.
potsticker: A Chinese dumpling stuffed with meat and vegetables, first steamed and then pan-fried, or sometimes first pan-fried and then simmered in water added to the pan.
predicate: A procedure that always returns a Boolean
value. By convention, Scheme predicates have names like "equal?" that
end in a question mark.
primitive procedure: A procedure that is already defined when a Scheme session begins. By contrast, a compound procedure is one that the programmer defines in Scheme.
procedure: The expression of an algorithm in Scheme notation.
prompt: A character or characters that an interactive program
prints to tell the user that it's ready for the user to type something. In
many versions of Scheme, the prompt is a > character.
random access: A data structure allows random access if the time required to locate an element of the structure is independent of its position within the structure.
range: The set of all possible return values from a function. For
example, the range of the count function is the set of non-negative
integers.
read-eval-print loop: The overall structure of a Scheme interpreter. It reads an expression from the keyboard, evaluates the expression by invoking procedures, etc., and prints the resulting value. The same process repeats forever.
record: One complete entry in a database. For example, one album in our database of albums. A record contains several fields.
recursion: Solving a big problem by reducing it to smaller problems of the same kind. If something is defined recursively, then it's defined in terms of itself. See recursion.
recursive case: In a recursive procedure, the part that requires a recursive invocation. The opposite of the base case.
rest parameter: A parameter that represents a variable number of
arguments. In the formal parameter list (a b . x), x is a
rest parameter.
result replacement: A technique people can use to figure out the value of a complicated Scheme expression by rewriting the expression repeatedly, each time replacing some small subexpression with a simpler expression that has the same value, until all that's left is a single quoted or self-evaluating value.
robust: Able to function despite user errors. Robust programs check for likely errors and recover from them gracefully.
root node: The node at the very top of a tree.
selector: A procedure that takes an object as its argument and
returns some part of that object. For example, the selector first
takes a word or sentence as argument and returns the first letter of the
word or first word of the sentence. See also constructor, mutator, and abstract data type.
self-evaluating: An expression is self-evaluating if, when evaluated, it has as its value the expression itself. Numbers, Booleans, and strings are the only self-evaluating objects we use in this book.
semipredicate: A procedure that answers a yes-no question by
returning #f for "no," but instead of returning #t for
"yes," it returns some additional piece of information. The primitive
member procedure is a good example of a semipredicate.
("Semipredicate" isn't a common term; we made it up for this book.)
sequencing: Evaluating two or more expressions one after the other, for the sake of their effects.
sequential programming: A style of programming in which programs say, "First do this, then do that, then do that other thing." (Compare to functional programming.)
siblings: Two nodes of a tree that are the children of the same node. (See also children and parent.)
side effect: See effect.
special form: A Scheme expression that begins with a keyword and is evaluated using a special rule. In particular, some of
the subexpressions might not be evaluated. The keywords used in this book
are and, begin, cond, define, if, lambda, let, or, and quote. (The keyword itself is also
sometimes called a special form.)
spreadsheet program: A program that maintains a two-dimensional display of data can compute some elements automatically, based on the values of other elements.
state: A program's memory of what has happened in the past.
string: A word delimited by double-quote
marks, such as "A Hard Day's Night" or "000123".
structured list: A list with sublists.
subexpression: An element of a compound expression. For
example, the expression (+ (* 2 3) 4) has three subexpressions: +, (* 2 3), and 4.
sublist: An element of a list that is itself a smaller list. For
example, (c d) is a sublist of the list (a b (c d) e).
substitution model: The way we've explained how Scheme evaluates function invocations. According to the substitution model, when a compound procedure is invoked, Scheme goes through the body of that procedure and replaces every copy of a formal parameter with the corresponding actual argument value. Then Scheme evaluates the resulting expression.
subtree: A tree that is part of a larger tree.
symbol: A word that isn't a number or a string.
symbolic computing: Computing that is about words, sentences, and ideas instead of just numbers.
tree: A two-dimensional data structure used to represent hierarchical information.
tree recursion: A form of recursion in which a procedure calls itself recursively more than one time in each level of the recursion.
type: A category of data. For example, words, sentences, Booleans, and procedures are types. Some types overlap: All numbers are also words, for example.
variable: A connection between a name and a value. Variables can be global or local.
vector: A primitive data structure that is mutable and allows random access.
word: A sequence of characters, including letters, digits, or punctuation. Numbers are a special case of words.
Brian Harvey,
bh@cs.berkeley.edu