Index

! in names
" (double quote)
calculus, see lambda calculus
notation for mathematical function
, see pi
sum (sigma) notation
, see theta
' (single quote)
    read and, [2]
* (primitive multiplication procedure)
+ (primitive addition procedure)
, (comma, used with backquote)
- (primitive subtraction procedure)
    as negation
/ (primitive division procedure)
< (primitive numeric comparison predicate)
= (primitive numeric equality predicate)
=number?
=zero? (generic)
    for polynomials
> (primitive numeric comparison predicate)
>=, [2]
? , in predicate names
#f
#t
` (backquote)
;, see semicolon

Abelson, Harold
abs, [2], [3]
absolute value
abstract data, see also data abstraction
abstract models for data
abstract syntax
    in metacircular evaluator
    in query interpreter
abstraction, see also means of abstraction; data abstraction; higher-order procedures
    common pattern and
    metalinguistic
    procedural
    in register-machine design
    of search in nondeterministic programming
abstraction barriers, [2], [3]
    in complex-number system
    in generic arithmetic system
accelerated-sequence
accumulate, [2]
    same as fold-right
accumulate-n
accumulator, [2]
Áchárya, Bháscara
Ackermann's function
acquire a mutex
actions, in register machine
actual-value
Ada
    recursive procedures
Adams, Norman I., IV
add (generic)
    used for polynomial coefficients, [2]
add-action!, [2]
add-binding-to-frame!
add-complex
add-complex-to-schemenum
add-interval
add-lists
add-poly
add-rat
add-rule-or-assertion!
add-streams
add-terms
add-to-agenda!, [2]
add-vect
addend
adder
    full
    half
    ripple-carry
adder (primitive constraint)
additivity, [2], [3], [4]
address
address arithmetic
Adelman, Leonard
adjoin-arg
adjoin-set
    binary-tree representation
    ordered-list representation
    unordered-list representation
    for weighted sets
adjoin-term, [2]
advance-pc
after-delay, [2]
agenda, see digital-circuit simulation
A'h-mose
algebra, symbolic, see symbolic algebra
algebraic expression
    differentiating
    representing
    simplifying
algebraic specification for data
Algol
    block structure
    call-by-name argument passing, [2]
    thunks, [2]
    weakness in handling compound objects
algorithm
    optimal
    probabilistic, [2]
aliasing
all-regs (compiler)
Allen, John
alternative of if
always-true
amb
amb evaluator, see nondeterministic evaluator
ambeval
an-element-of
an-integer-starting-from
analog computer
analyze
    metacircular
    nondeterministic
analyze-...
    metacircular, [2]
    nondeterministic
analyze-amb
analyzing evaluator
    as basis for nondeterministic evaluator
    let
and (query language)
    evaluation of, [2], [3]
and (special form)
    evaluation of
    why a special form
    with no subexpressions
and-gate
    and-gate
angle
    data-directed
    polar representation
    rectangular representation
    with tagged data
angle-polar
angle-rectangular
announce-output
APL
Appel, Andrew W.
append, [2], [3]
    as accumulation
    append! vs.
    with arbitrary number of arguments
    as register machine
    ``what is'' (rules) vs. ``how to'' (procedure)
append!
    as register machine
append-instruction-sequences, [2]
append-to-form (rules)
application?
applicative-order evaluation
    in Lisp
    normal order vs., [2], [3]
apply (lazy)
apply (metacircular)
    primitive apply vs.
apply (primitive procedure)
apply-dispatch
    modified for compiled code
apply-generic
    with coercion, [2]
    with coercion by raising
    with coercion of multiple arguments
    with coercion to simplify
    with message passing
    with tower of types
apply-primitive-procedure, [2], [3]
apply-rules
arbiter
arctangent
argl register
argument passing, see call-by-name argument passing; call-by-need argument passing
argument(s)
    arbitrary number of, [2]
    delayed
Aristotle's De caelo (Buridan's commentary on)
arithmetic
    address arithmetic
    generic, see also generic arithmetic operations
    on complex numbers
    on intervals
    on polynomials, see polynomial arithmetic
    on power series, [2]
    on rational numbers
    primitive procedures for
articles
ASCII code
assemble, [2]
assembler, [2]
assert! (query interpreter)
assertion
    implicit
assign (in register machine)
    simulating
    storing label in register
assign-reg-name
assign-value-exp
assignment, see also set!
    benefits of
    bugs associated with, [2]
    costs of
assignment operator, see also set!
assignment-value
assignment-variable
assignment?
assoc
atan (primitive procedure)
atomic operations supported in hardware
atomic requirement for test-and-set!
attach-tag
    using Scheme data types
augend
automagically
automatic search, see also search
    history of
automatic storage allocation
average
average damping
average-damp
averager (constraint)

B-tree
backquote
backtracking, see also nondeterministic computing
Backus, John
Baker, Henry G., Jr.
balanced binary tree, see also binary tree
balanced mobile
bank account, [2]
    exchanging balances
    joint, [2]
    joint, modeled with streams
    joint, with concurrent access
    password-protected
    serialized
    stream model
    transferring money
barrier synchronization
Barth, John
Basic
    restrictions on compound data
    weakness in handling compound objects
Batali, John Dean
begin (special form)
    implicit in consequent of cond and in procedure body
begin-actions
begin?
below, [2]
Bertrand's Hypothesis
beside, [2]
bignum
binary numbers, addition of, see adder
binary search
binary tree
    balanced
    converting a list to a
    converting to a list
    for Huffman encoding
    represented with lists
    sets represented as
    table structured as
bind
binding
    deep
binomial coefficients
black box
block structure, [2]
    in environment model
    in query language
blocked process
body of a procedure
Bolt Beranek and Newman Inc.
Borning, Alan
Borodin, Alan
bound variable
box-and-pointer notation
    end-of-list marker
branch (in register machine)
    simulating
branch of a tree
branch-dest
breakpoint
broken heart
bug
    capturing a free variable
    order of assignments
    side effect with aliasing
bureaucracy
Buridan, Jean
busy-waiting

C
    compiling Scheme into
    error handling, [2]
    recursive procedures
    restrictions on compound data
    Scheme interpreter written in, [2]
ca...r
cache-coherence protocols
cadr
calculator, fixed points with
call-by-name argument passing, [2]
call-by-need argument passing, [2]
    memoization and
call-each
cancer of the semicolon
canonical form, for polynomials
capturing a free variable
car (primitive procedure)
    axiom for
    implemented with vectors
    as list operation
    origin of the name
    procedural implementation of, [2], [3], [4], [5]
Carmichael numbers, [2]
case analysis
    data-directed programming vs.
    general, see also cond
    with two cases (if)
cd...r
cdr (primitive procedure)
    axiom for
    implemented with vectors
    as list operation
    origin of the name
    procedural implementation of, [2], [3], [4], [5]
cdr down a list
cell, in serializer implementation
celsius-fahrenheit-converter
    expression-oriented
center
Cesàro, Ernesto
cesaro-stream
cesaro-test
Chaitin, Gregory
Chandah-sutra
change and sameness
    meaning of
    shared data and
changing money, see counting change
chaos in the Solar System
Chapman, David
character strings
    primitive procedures for, [2]
    quotation of
character, ASCII encoding
Charniak, Eugene
Chebyshev, Pafnutii L'vovich
chess, eight-queens puzzle, [2]
chip implementation of Scheme, [2]
chronological backtracking
Chu Shih-chieh
Church numerals
Church, Alonzo, [2]
Church-Turing thesis
circuit
    digital, see digital-circuit simulation
    modeled with streams, [2]
Clark, Keith L.
clause, of a cond
    additional syntax
Clinger, William, [2]
closed world assumption
closure
    in abstract algebra
    closure property of cons
    closure property of picture-language operations, [2]
    lack of in many languages
coal, bituminous
code
    ASCII
    fixed-length
    Huffman, see Huffman code
    Morse
    prefix
    variable-length
code generator
    arguments of
    value of
coeff, [2]
coercion
    in algebraic manipulation
    in polynomial arithmetic
    procedure
    table
Colmerauer, Alain
combination
    combination as operator of
    compound expression as operator of
    evaluation of
    lambda expression as operator of
    as operator of combination
    as a tree
combination, means of, see also closure
comma, used with backquote
comments in programs
Common Lisp
    treatment of nil
compacting garbage collector
compilation, see compiler
compile
compile-and-go, [2]
compile-and-run
compile-application
compile-assignment
compile-definition
compile-if
compile-lambda
compile-linkage
compile-proc-appl
compile-procedure-call
compile-quoted
compile-self-evaluating
compile-sequence
compile-time environment, [2], [3]
    open coding and
compile-variable
compiled-apply
compiled-procedure-entry
compiled-procedure-env
compiled-procedure?
compiler
    interpreter vs., [2]
    tail recursion, stack allocation, and garbage-collection
compiler for Scheme, see also code generator; compile-time environment; instruction sequence; linkage descriptor; target register
    analyzing evaluator vs., [2]
    assignments
    code generators, see compile-...
    combinations
    conditionals
    definitions
    efficiency
    example compilation
    explicit-control evaluator vs., [2], [3]
    expression-syntax procedures
    interfacing to evaluator
    label generation
    lambda expressions
    lexical addressing
    linkage code
    machine-operation use
    monitoring performance (stack use) of compiled code, [2], [3]
    open coding of primitives, [2]
    order of operand evaluation
    procedure applications
    quotations
    register use, [2], [3]
    running compiled code
    scanning out internal definitions, [2]
    self-evaluating expressions
    sequences of expressions
    stack usage, [2], [3]
    structure of
    tail-recursive code generated by
    variables
complex package
complex numbers
    polar representation
    rectangular representation
    rectangular vs. polar form
    represented as tagged data
complex->complex
complex-number arithmetic
    interfaced to generic arithmetic system
    structure of system
composition of functions
compound data, need for
compound expression, see also combination; special form
    as operator of combination
compound procedure, see also procedure
    used like primitive procedure
compound query
    processing, [2], [3], [4], [5]
compound-apply
compound-procedure?
computability, [2]
computational process, see also process
computer science, [2]
    mathematics vs., [2]
concrete data representation
concurrency
    correctness of concurrent programs
    deadlock
    functional programming and
    mechanisms for controlling
cond (special form)
    additional clause syntax
    clause
    evaluation of
    if vs.
    implicit begin in consequent
cond->if
cond-actions
cond-clauses
cond-else-clause?
cond-predicate
cond?
conditional expression
    cond
    if
congruent modulo n
conjoin
connect, [2]
connector(s), in constraint system
    operations on
    representing
Conniver
cons (primitive procedure)
    axiom for
    closure property of
    implemented with mutators
    implemented with vectors
    as list operation
    meaning of the name
    procedural implementation of, [2], [3], [4], [5], [6]
cons up a list
cons-stream (special form), [2]
    lazy evaluation and
    why a special form
consciousness, expansion of
consequent
    of cond clause
    of if
const (in register machine)
    simulating
    syntax of
constant (primitive constraint)
constant, specifying in register machine
constant-exp
constant-exp-value
constraint network
constraint(s)
    primitive
    propagation of
construct-arglist
constructor
    as abstraction barrier
contents
    using Scheme data types
continuation
    in nondeterministic evaluator, [2], see also failure continuation; success continuation
    in register-machine simulator
continue register
    in explicit-control evaluator
    recursion and
continued fraction
    e as
    golden ratio as
    tangent as
control structure
controller for register machine
    controller diagram
conventional interface
    sequence as
Cormen, Thomas H.
corner-split
correctness of a program
cos (primitive procedure)
cosine
    fixed point of
    power series for
cosmic radiation
count-change
count-leaves, [2]
    as accumulation
    as register machine
count-pairs
counting change, [2]
credit-card accounts, international
Cressey, David
cross-type operations
cryptography
cube, [2], [3]
cube root
    as fixed point
    by Newton's method
cube-root
current time, for simulation agenda
current-time, [2]
cycle in list
    detecting

Darlington, John
data, [2]
    abstract, see also data abstraction
    abstract models for
    algebraic specification for
    compound
    concrete representation of
    hierarchical, [2]
    list-structured
    meaning of
    mutable, see mutable data objects
    numerical
    procedural representation of
    as program
    shared
    symbolic
    tagged, [2]
data abstraction, [2], [3], [4], [5], see also metacircular evaluator
    for queue
data base
    data-directed programming and
    indexing, [2]
    Insatiable Enterprises personnel
    logic programming and
    Microshaft personnel
    as set of records
data paths for register machine
    data-path diagram
data types
    in Lisp
    in strongly typed languages
data-directed programming, [2]
    case analysis vs.
    in metacircular evaluator
    in query interpreter
data-directed recursion
deadlock
    avoidance
    recovery
debug
decimal point in numbers
declarative vs. imperative knowledge, [2]
    logic programming and, [2]
    nondeterministic computing and
decode
decomposition of program into parts
deep binding
deep-reverse
deferred operations
define (special form)
    with dotted-tail notation
    environment model of
    lambda vs.
    for procedures, [2]
    syntactic sugar
    value of
    why a special form
define (special form)
    internal, see internal definition
define-variable!, [2]
definite integral
    estimated with Monte Carlo simulation, [2]
definition, see define; internal definition
definition-value
definition-variable
definition?
deKleer, Johan, [2]
delay (special form)
    explicit
    explicit vs. automatic
    implementation using lambda
    lazy evaluation and
    memoized, [2]
    why a special form
delay, in digital circuit
delay-it
delayed argument
delayed evaluation, [2]
    assignment and
    explicit vs. automatic
    in lazy evaluator
    normal-order evaluation and
    printing and
    streams and
delayed object
delete-queue!, [2]
denom, [2]
    axiom for
    reducing to lowest terms
dense polynomial
dependency-directed backtracking
deposit , with external serializer
deposit message for bank account
depth-first search
deque
deriv (numerical)
deriv (symbolic)
    data-directed
derivative of a function
derived expressions in evaluator
    adding to explicit-control evaluator
design, stratified
differential equation, see also solve
    second-order, [2]
differentiation
    numerical
    rules for, [2]
    symbolic, [2]
diffusion, simulation of
digital signal
digital-circuit simulation
    agenda
    agenda implementation
    primitive function boxes
    representing wires
    sample simulation
Dijkstra, Edsger Wybe
Dinesman, Howard P.
Diophantus's Arithmetic, Fermat's copy of
disjoin
dispatching
    comparing different styles
    on type, see also data-directed programming
display (primitive procedure), [2]
display-line
display-stream
distinct?
div (generic)
div-complex
div-interval
    division by zero
div-poly
div-rat
div-series
div-terms
divides?
divisible?
division of integers
dog, perfectly rational, behavior of
DOS/Windows
dot-product
dotted-tail notation
    for procedure parameters, [2]
    in query pattern, [2]
    in query-language rule
    read and
Doyle, Jon
draw-line
driver loop
    in explicit-control evaluator
    in lazy evaluator
    in metacircular evaluator
    in nondeterministic evaluator, [2]
    in query interpreter, [2]
driver-loop
    for lazy evaluator
    for metacircular evaluator
    for nondeterministic evaluator

e
    as continued fraction
    as solution to differential equation
e^x, power series for
Earth, measuring circumference of
edge1-frame
edge2-frame
efficiency, see also order of growth, see also order of growth
    of compilation
    of data-base access
    of evaluation
    of Lisp
    of query processing
    of tree-recursive process
EIEIO
eight-queens puzzle, [2]
electrical circuits, modeled with streams, [2]
element-of-set?
    binary-tree representation
    ordered-list representation
    unordered-list representation
else (special symbol in cond)
embedded language, language design using
empty list
    denoted as '()
    recognizing with null?
empty stream
empty-agenda?, [2]
empty-arglist
empty-instruction-sequence
empty-queue?, [2]
empty-termlist?, [2]
encapsulated name
enclosing environment
enclosing-environment
encode
end-of-list marker
end-segment, [2]
end-with-linkage
engineering vs. mathematics
entry
enumerate-interval
enumerate-tree
enumerator
env register
environment, [2]
    compile-time, see compile-time environment
    as context for evaluation
    enclosing
    global, see global environment
    lexical scoping and
    in query interpreter
    renaming vs.
environment model of evaluation, [2]
    environment structure
    internal definitions
    local state
    message passing
    metacircular evaluator and
    procedure-application example
    rules for evaluation
    tail recursion and
eq? (primitive procedure)
    for arbitrary objects
    as equality of pointers, [2]
    implementation for symbols
    numerical equality and
equ? (generic predicate)
equal-rat?
equal?
equality
    in generic arithmetic system
    of lists
    of numbers, [2], [3]
    referential transparency and
    of symbols
equation, solving, see half-interval method; Newton's method; solve
Eratosthenes
error (primitive procedure)
error handling
    in compiled code
    in explicit-control evaluator, [2]
Escher, Maurits Cornelis
estimate-integral
estimate-pi, [2]
Euclid's Algorithm, [2], see also greatest common divisor
    order of growth
    for polynomials
Euclid's Elements
Euclid's proof of infinite number of primes
Euclidean ring
Euler, Leonhard
    proof of Fermat's Little Theorem
    series accelerator
euler-transform
ev-application
ev-assignment
ev-begin
ev-definition
ev-if
ev-lambda
ev-quoted
ev-self-eval
ev-sequence
    with tail recursion
    without tail recursion
ev-variable
eval (lazy)
eval (metacircular), [2]
    analyzing version
    data-directed
    primitive eval vs.
eval (primitive procedure)
    MIT Scheme
    used in query interpreter
eval-assignment
eval-definition
eval-dispatch
eval-if (lazy)
eval-if (metacircular)
eval-sequence
evaluation
    applicative-order, see applicative-order evaluation
    delayed, see delayed evaluation
    environment model of, see environment model of evaluation
    models of
    normal-order, see normal-order evaluation
    of a combination
    of and
    of cond
    of if
    of or
    of primitive expressions
    of special forms
    order of subexpression evaluation, see order of evaluation
    substitution model of, see substitution model of procedure application
evaluator, see also interpreter
    as abstract machine
    metacircular
    as universal machine
evaluators, see metacircular evaluator; analyzing evaluator; lazy evaluator; nondeterministic evaluator; query interpreter; explicit-control evaluator
even-fibs, [2]
even?
evening star, see Venus
event-driven simulation
evlis tail recursion
exact integer
exchange
exclamation point in names
execute
execute-application
    metacircular
    nondeterministic
execution procedure
    in analyzing evaluator
    in nondeterministic evaluator, [2], [3]
    in register-machine simulator, [2]
exp register
expand-clauses
explicit-control evaluator for Scheme
    assignments
    combinations
    compound procedures
    conditionals
    controller
    data paths
    definitions
    derived expressions
    driver loop
    error handling, [2]
    expressions with no subexpressions to evaluate
    as machine-language program
    machine model
    modified for compiled code
    monitoring performance (stack use)
    normal-order evaluation
    operand evaluation
    operations
    optimizations (additional)
    primitive procedures
    procedure application
    registers
    running
    sequences of expressions
    special forms (additional), [2]
    stack usage
    tail recursion, [2], [3]
    as universal machine
expmod, [2], [3]
exponential growth
    of tree-recursive Fibonacci-number computation
exponentiation
    modulo n
expression, see also compound expression; primitive expression
    algebraic, see algebraic expressions
    self-evaluating
    symbolic, see also symbol(s)
expression-oriented vs. imperative programming style
expt
    linear iterative version
    linear recursive version
    register machine for
extend-environment, [2]
extend-if-consistent
extend-if-possible
external-entry
extract-labels, [2]