Structure and Interpretation of Computer Programs (114 page)

#f
factorial
,
see also
factorial
    
infinite stream
    
with
letrec
    
without
letrec
or
define
factorial
    
as an abstract machine
    
compilation of
,
[2]
    
environment structure in evaluating
    
linear iterative version
    
linear recursive version
    
register machine for (iterative)
,
[2]
    
register machine for (recursive)
,
[2]
    
stack usage, compiled
    
stack usage, interpreted
,
[2]
    
stack usage, register machine
    
with assignment
    
with higher-order procedures
failure continuation (nondeterministic evaluator)
,
[2]
    
constructed by
amb
    
constructed by assignment
    
constructed by driver loop
failure, in nondeterministic computation
    
bug vs.
    
searching and
false
false
false?
fast-expt
fast-prime?
feedback loop, modeled with streams
Feeley, Marc
Feigenbaum, Edward
Fenichel, Robert
Fermat, Pierre de
Fermat test for primality
    
variant of
Fermat's Little Theorem
    
alternate form
    
proof
fermat-test
fetch-assertions
fetch-rules
fib
    
linear iterative version
    
logarithmic version
    
register machine for (tree-recursive)
,
[2]
    
stack usage, compiled
    
stack usage, interpreted
    
tree-recursive version
,
[2]
    
with memoization
    
with named
let
Fibonacci numbers
,
see also
fib
    
Euclid's GCD algorithm and
    infinite stream of,
see
fibs
fibs
(infinite stream)
    
implicit definition
FIFO buffer
filter
,
[2]
filter
filtered-accumulate
find-assertions
find-divisor
first-agenda-item
,
[2]
first-class elements in language
first-exp
first-frame
first-operand
first-segment
first-term
,
[2]
fixed point
    
computing with calculator
    
of cosine
    
cube root as
    
fourth root as
    
golden ratio as
    
as iterative improvement
    
in Newton's method
    
n
th root as
    
square root as
,
[2]
,
[3]
    
of transformed function
    
unification and
fixed-length code
fixed-point
    
as iterative improvement
fixed-point-of-transform
flag
register
flatmap
flatten-stream
flip-horiz
,
[2]
flip-vert
,
[2]
flipped-pairs
,
[2]
,
[3]
Floyd, Robert
fold-left
fold-right
for-each
,
[2]
for-each-except
Forbus, Kenneth D.
force
,
[2]
    
forcing a thunk vs.
force a thunk
force-it
    
memoized version
forget-value!
,
[2]
formal parameters
    
names of
    
scope of
formatting input expressions
Fortran
,
[2]
    
inventor of
    
restrictions on compound data
forwarding address
fourth root, as fixed point
fraction,
see
rational number(s)
frame (environment model)
    
as repository of local state
    
global
frame (picture language)
,
[2]
    
coordinate map
frame (query interpreter)
,
see also
pattern matching; unification
    
representation
frame-coord-map
frame-values
frame-variables
framed-stack discipline
Franz Lisp
free
register
,
[2]
free list
free variable
    
capturing
    
in internal definition
Friedman, Daniel P.
,
[2]
fringe
    
as a tree enumeration
front-ptr
front-queue
,
[2]
full-adder
    
full-adder
function (mathematical)
    
⟼ notation for
    
Ackermann's
    
composition of
    
derivative of
    
fixed point of
    
procedure vs.
    
rational
    
repeated application of
    
smoothing of
function box, in digital circuit
functional programming
,
[2]
    
concurrency and
    
functional programming languages
    
time and

Gabriel, Richard P.
garbage collection
    
memoization and
    
mutation and
    
tail recursion and
garbage collector
    
compacting
    
mark-sweep
    
stop-and-copy
GCD,
see
greatest common divisor
gcd
    
register machine for
,
[2]
gcd-terms
general-purpose computer, as universal machine
generate-huffman-tree
generating sentences
generic arithmetic operations
    
structure of system
generic operation
generic procedure
,
[2]
    
generic selector
,
[2]
Genesis
get
,
[2]
get-contents
get-global-environment
get-register
get-register-contents
,
[2]
get-signal
,
[2]
get-value
,
[2]
glitch
global environment
,
[2]
    
in metacircular evaluator
global frame
Goguen, Joseph
golden ratio
    
as continued fraction
    
as fixed point
Gordon, Michael
goto
(in register machine)
    
label as destination
    
simulating
goto-dest
grammar
graphics,
see
picture language
Gray, Jim
greatest common divisor
,
see also
gcd
    
generic
    
of polynomials
    
used to estimate π
    
used in rational-number arithmetic
Green, Cordell
Griss, Martin Lewis
Guttag, John Vogel

half-adder
    
half-adder
    
simulation of
half-interval method
    
half-interval-method
    
Newton's method vs.
halting problem
Halting Theorem
Hamming, Richard Wesley
,
[2]
Hanson, Christopher P.
,
[2]
Hardy, Godfrey Harold
,
[2]
has-value?
,
[2]
Hassle
Havender, J.
Haynes, Christopher T.
headed list
,
[2]
Hearn, Anthony C.
Henderson, Peter
,
[2]
,
[3]
    
Henderson diagram
Heraclitus
Heron of Alexandria
Hewitt, Carl Eddie
,
[2]
,
[3]
,
[4]
hiding principle
hierarchical data structures
,
[2]
hierarchy of types
    
in symbolic algebra
    
inadequacy of
high-level language, machine language vs.
higher-order procedures
    
in metacircular evaluator
    
procedure as argument
    
procedure as general method
    
procedure as returned value
    
strong typing and
Hilfinger, Paul
Hoare, Charles Antony Richard
Hodges, Andrew
Hofstadter, Douglas R.
Horner, W. G.
Horner's rule
“how to” vs. “what is” description,
see
imperative vs. declarative knowledge
Huffman code
    
optimality of
    
order of growth of encoding
Huffman, David
Hughes, R. J. M.

IBM 704
identity
if
(special form)
    
cond
vs.
    
evaluation of
    
normal-order evaluation of
    
one-armed (without alternative)
    
predicate, consequent, and alternative of
    
why a special form
if-alternative
if-consequent
if-predicate
if?
imag-part
    
data-directed
    
polar representation
    
rectangular representation
    
with tagged data
imag-part-polar
imag-part-rectangular
imperative programming
imperative vs. declarative knowledge
,
[2]
    
logic programming and
,
[2]
    
nondeterministic computing and
imperative vs. expression-oriented programming style
implementation dependencies,
see also
unspecified values
    
numbers
    
order of subexpression evaluation
inc
incremental development of programs
indeterminate of a polynomial
indexing a data base
,
[2]
inference, method of
infinite series
infinite stream(s)
    
merging
,
[2]
,
[3]
,
[4]
    
merging as a relation
    
of factorials
    of Fibonacci numbers,
see
fibs
    of integers,
see
integers
    
of pairs
    of prime numbers,
see
primes
    
of random numbers
    
representing power series
    
to model signals
    
to sum a series
infix notation, prefix notation vs.
inform-about-no-value
inform-about-value
information retrieval,
see
data base
Ingerman, Peter
initialize-stack
operation in register machine
,
[2]
insert!
    
in one-dimensional table
    
in two-dimensional table
insert-queue!
,
[2]
install-complex-package
install-polar-package
install-polynomial-package
install-rational-package
install-rectangular-package
install-scheme-number-package
instantiate
instantiate a pattern
instruction counting
instruction execution procedure
instruction sequence
,
[2]
instruction tracing
instruction-execution-proc
instruction-text
integer(s)
    
dividing
    
exact
integerizing factor
integers
(infinite stream)
    
implicit definition
    
lazy-list version
integers-starting-from
integral,
see also
definite integral; Monte Carlo integration
    
of a power series
integral
,
[2]
,
[3]
    
with delayed argument
    
with
lambda
    
lazy-list version
    
need for delayed evaluation
integrate-series
integrated-circuit implementation of Scheme
,
[2]
integrator, for signals
interleave
interleave-delayed
Interlisp
internal definition
    
in environment model
    
free variable in
    
let
vs.
    
in nondeterministic evaluator
    
position of
    
restrictions on
    
scanning out
    
scope of name
Internet “Worm”
interning symbols
interpreter
,
see also
evaluator
    
compiler vs.
,
[2]
    
read-eval-print loop
intersection-set
    
binary-tree representation
    
ordered-list representation
    
unordered-list representation
interval arithmetic
invariant quantity of an iterative process
inverter
    
inverter
iteration contructs,
see
looping constructs
iterative improvement
iterative process
    
as a stream process
    
design of algorithm
    
implemented by procedure call
,
[2]
,
[3]
,
see also
tail recursion
    
linear
,
[2]
    
recursive process vs.
,
[2]
,
[3]
,
[4]
    
register machine for