Structure and Interpretation of Computer Programs (116 page)

name,
see also
local name; variable; local variable
    
encapsulated
    
of a formal parameter
    
of a procedure
named
let
(special form)
naming
    
of computational objects
    
of procedures
naming conventions
    
!
for assignment and mutation
    
?
for predicates
native language of machine
natural language
    parsing,
see
parsing natural language
    
quotation in
needed registers,
see
instruction sequence
needs-register?
negate
nested applications of
car
and
cdr
nested combinations
nested definitions,
see
internal definition
nested mappings,
see
mapping
new
register
new-cars
register
new-cdrs
register
new-withdraw
newline
(primitive procedure)
,
[2]
Newton's method
    
for cube roots
    
for differentiable functions
    
half-interval method vs.
    
for square roots
,
[2]
,
[3]
newton-transform
newtons-method
next
(linkage descriptor)
next-to
(rules)
nil
    
dispensing with
    
as empty list
    
as end-of-list marker
    
as ordinary variable in Scheme
no-more-exps?
no-operands?
node of a tree
non-computable
non-strict
nondeterminism, in behavior of concurrent programs
,
[2]
nondeterministic choice point
nondeterministic computing
nondeterministic evaluator
    
order of operand evaluation
nondeterministic programming vs. Scheme programming
,
[2]
,
[3]
,
[4]
nondeterministic programs
    
logic puzzles
    
pairs with prime sums
    
parsing natural language
    
Pythagorean triples
,
[2]
,
[3]
normal-order evaluation
    
applicative order vs.
,
[2]
,
[3]
    
delayed evaluation and
    
in explicit-control evaluator
    
of
if
normal-order evaluator,
see
lazy evaluator
not
(primitive procedure)
not
(query language)
,
[2]
    
evaluation of
,
[2]
,
[3]
notation in this book
    
italic symbols in expression syntax
    
slanted characters for interpreter response
nouns
n
th root, as fixed point
null?
(primitive procedure)
    
implemented with typed pointers
number theory
number(s)
    
comparison of
    
decimal point in
    
equality of
,
[2]
,
[3]
    
in generic arithmetic system
    
implementation dependencies
    
integer vs. real number
    
integer, exact
    
in Lisp
    
rational number
number?
(primitive procedure)
    
data types and
    
implemented with typed pointers
numer
,
[2]
    
axiom for
    
reducing to lowest terms
numerical analysis
numerical analyst
numerical data

obarray
object program
object(s)
    
benefits of modeling with
    
with time-varying state
object-oriented programming languages
old
register
oldcr
register
ones
(infinite stream)
    
lazy-list version
op
(in register machine)
    
simulating
open coding of primitives
,
[2]
operands
operands of a combination
operation
    
cross-type
    
generic
    
in register machine
operation-and-type table
    
assignment needed for
    
implementing
operation-exp
operation-exp-op
operation-exp-operands
operator
operator of a combination
    
combination as
    
compound expression as
    
lambda
expression as
optimality
    
of Horner's rule
    
of Huffman code
or
(query language)
    
evaluation of
,
[2]
or
(special form)
    
evaluation of
    
why a special form
    
with no subexpressions
or-gate
    
or-gate
,
[2]
order
,
[2]
order notation
order of evaluation
    
assignment and
    
implementation-dependent
    
in compiler
    
in explicit-control evaluator
    
in metacircular evaluator
    
in Scheme
order of events
    
decoupling apparent from actual
    
indeterminacy in concurrent systems
order of growth
    
linear iterative process
    
linear recursive process
    
logarithmic
    
tree-recursive process
order of subexpression evaluation,
see
order of evaluation
ordered-list representation of sets
ordinary numbers (in generic arithmetic system)
origin-frame
Ostrowski, A. M.
outranked-by
(rule)
,
[2]

P operation on semaphore
package
    
complex-number
    
polar representation
    
polynomial
    
rational-number
    
rectangular representation
    
Scheme-number
painter(s)
    
higher-order operations
    
operations
    
represented as procedures
    
transforming and combining
pair(s)
    
axiomatic definition of
    
box-and-pointer notation for
    
infinite stream of
    
lazy
    
mutable
    
procedural representation of
,
[2]
,
[3]
    
represented using vectors
    
used to represent sequence
    
used to represent tree
pair?
(primitive procedure)
    
implemented with typed pointers
pairs
Pan, V. Y.
parallel-execute
parallel-instruction-sequences
parallelism,
see
concurrency
parameter,
see
formal parameters
parameter passing,
see
call-by-name argument passing; call-by-need argument passing
parentheses
    
delimiting combination
    
delimiting
cond
clauses
    
in procedure definition
parse
parse-...
parsing natural language
    
real language understanding vs. toy parser
partial-sums
Pascal
    
lack of higher-order procedures
    
recursive procedures
    
restrictions on compound data
    
weakness in handling compound objects
Pascal, Blaise
Pascal's triangle
password-protected bank account
pattern
pattern matching
    
implementation
    
unification vs.
,
[2]
pattern variable
    
representation of
,
[2]
pattern-match
pc
register
perform
(in register machine)
    
simulating
perform-action
Perlis, Alan J.
,
[2]
    
quips
,
[2]
permutations of a set
    
permutations
Phillips, Hubert
π (pi)
    
approximation with half-interval method
    
approximation with Monte Carlo integration
,
[2]
    
Cesàro estimate for
,
[2]
    
Leibniz's series for
,
[2]
    
stream of approximations
    
Wallis's formula for
pi-stream
pi-sum
    
with higher-order procedures
    
with
lambda
picture language
Pingala, Áchárya
pipelining
Pitman, Kent M.
Planner
point, represented as a pair
pointer
    
in box-and-pointer notation
    
typed
polar
package
polar?
poly
polynomial
package
polynomial arithmetic
    
addition
    
division
    
Euclid's Algorithm
    
greatest common divisor
,
[2]
    
interfaced to generic arithmetic system
    
multiplication
    
probabilistic algorithm for GCD
    
rational functions
    
subtraction
polynomial(s)
    
canonical form
    
dense
    
evaluating with Horner's rule
    
hierarchy of types
    
indeterminate of
    
sparse
    
univariate
pop
Portable Standard Lisp
porting a language
power series, as stream
    
adding
    
dividing
    
integrating
    
multiplying
PowerPC
predicate
    
of
cond
clause
    
of
if
    
naming convention for
prefix code
prefix notation
    
infix notation vs.
prepositions
preserving
,
[2]
,
[3]
,
[4]
pretty-printing
prime number(s)
    
cryptography and
    
Eratosthenes's sieve for
    
Fermat test for
    infinite stream of,
see
primes
    
Miller-Rabin test for
    
testing for
prime-sum-pair
prime-sum-pairs
    
infinite stream
prime?
,
[2]
primes
(infinite stream)
    
implicit definition
primitive constraints
primitive expression
    
evaluation of
    
name of primitive procedure
    
name of variable
    
number
primitive procedures (those marked
ns
are not in the IEEE Scheme standard)
    
*
    
+
    
-
,
[2]
    
/
    
<
    
=
    
>
    
apply
    
atan
    
car
    
cdr
    
cons
    
cos
    
display
    
eq?
    
error
(
ns
)
    
eval
(
ns
)
    
list
    
log
    
max
    
min
    
newline
    
not
    
null?
    
number?
    
pair?
    
quotient
    
random
(
ns
)
,
[2]
    
read
    
remainder
    
round
    
runtime
(
ns
)
    
set-car!
    
set-cdr!
    
sin
    
symbol?
    
vector-ref
    
vector-set!
primitive query,
see
simple query
primitive-apply
primitive-implementation
primitive-procedure-names
primitive-procedure-objects
primitive-procedure?
,
[2]
principle of least commitment
print
operation in register machine
print-point
print-queue
print-rat
print-result
    
monitored-stack version
print-stack-statistics
operation in register machine
printing, primitives for
probabilistic algorithm
,
[2]
,
[3]
probe
    
in constraint system
    
in digital-circuit simulator
proc
register
procedural abstraction
procedural representation of data
    
mutable data
procedure
,
[2]
    
anonymous
    
arbitrary number of arguments
,
[2]
    
as argument
    
as black box
    
body of
    
compound
    
creating with
define
    
creating with
lambda
,
[2]
,
[3]
    
as data
    
definition of
    
first-class in Lisp
    
formal parameters of
    
as general method
    
generic
,
[2]
    higher-order,
see
higher-order procedure
    
implicit
begin
in body of
    
mathematical function vs.
    
memoized
    
monitored
    
name of
    
naming (with
define
)
    
as pattern for local evolution of a process
    
as returned value
    
returning multiple values
    
scope of formal parameters
    
special form vs.
,
[2]
procedure application
    
combination denoting
    
environment model of
    substitution model of,
see
substitution model of procedure application
procedure-body
procedure-environment
procedure-parameters
process
    
iterative
    
linear iterative
    
linear recursive
    
local evolution of
    
order of growth of
    
recursive
    
resources required by
    
shape of
    
tree-recursive
product
    
as accumulation
product?
program
    
as abstract machine
    
comments in
    
as data
    
incremental development of
    
structure of
,
[2]
,
[3]
,
see also
abstraction barriers
    
structured with subroutines
program counter
programming
    data-directed,
see
data-directed programming
    
demand-driven
    
elements of
    functional,
see
functional programming
    
imperative
    
odious style
programming language
    
design of
    
functional
    
logic
    
object-oriented
    
strongly typed
    
very high-level
Prolog
,
[2]
prompt-for-input
prompts
    
explicit-control evaluator
    
lazy evaluator
    
metacircular evaluator
    
nondeterministic evaluator
    
query interpreter
propagate
propagation of constraints
proving programs correct
pseudo-random sequence
pseudodivision of polynomials
pseudoremainder of polynomials
push
put
,
[2]
puzzles
    
eight-queens puzzle
,
[2]
    
logic puzzles
Pythagorean triples
    
with nondeterministic programs
,
[2]
,
[3]
    
with streams