test-and-set!
, [2]
test-condition
text-of-quotation
Thatcher, James W.
THE Multiprogramming System
the-cars
register, [2]
vector
the-cdrs
register, [2]
vector
the-empty-stream
in MIT Scheme
the-empty-termlist
, [2]
the-global-environment
, [2]
theorem proving (automatic)
(f(n)) (theta of f(n))
thunk
call-by-name
call-by-need
forcing
implementation of
origin of name
time
assignment and
communication and
in concurrent systems
functional programming and
in nondeterministic computing, [2]
purpose of
time segment, in agenda
time slicing
timed-prime-test
timing diagram
TK!Solver
tower of types
tracing
instruction execution
register assignment
transform-painter
transparency, referential
transpose
a matrix
tree
B-tree
binary, see also binary tree
combination viewed as
counting leaves of
enumerating leaves of
fringe of
Huffman
lazy
mapping over
red-black
represented as pairs
reversing at all levels
tree accumulation
tree->list...
tree-map
tree-recursive process
order of growth
trigonometric relations
true
true
true?
truncation error
truth maintenance
try-again
Turing machine
Turing, Alan M., [2]
Turner, David, [2], [3]
type field
type tag, [2]
two-level
type(s)
cross-type operations
dispatching on
hierarchy in symbolic algebra
hierarchy of
lowering, [2]
multiple subtype and supertype
raising, [2]
subtype
supertype
tower of
type-inferencing mechanism
type-tag
using Scheme data types
typed pointer
typing input expressions
unbound variable
unev
register
unification
discovery of algorithm
implementation
pattern matching vs., [2]
unify-match
union-set
binary-tree representation
ordered-list representation
unordered-list representation
unique
(query language)
unique-pairs
unit square
univariate polynomial
universal machine
explicit-control evaluator as
general-purpose computer as
University of California at Berkeley
University of Edinburgh
University of Marseille
UNIX, [2]
unknown-expression-type
unknown-procedure-type
unordered-list representation of sets
unspecified values
define
display
if
without alternative
newline
set!
set-car!
set-cdr!
up-split
update-insts!
upper-bound
upward compatibility
user-initial-environment
(MIT Scheme)
user-print
modified for compiled code
V operation on semaphore
val
register
value
of a combination
of an expression, see also unspecified values
value-proc
variable, see also local variable
bound
free
scope of, see also scope of a variable
unbound
value of, [2]
variable
variable-length code
variable?
, [2]
vector (data structure)
vector (mathematical)
operations on, [2]
in picture-language frame
represented as pair
represented as sequence
vector-ref
(primitive procedure)
vector-set!
(primitive procedure)
Venus
verbs
very high-level language
Wadler, Philip
Wadsworth, Christopher
Wagner, Eric G.
Walker, Francis Amasa
Wallis, John
Wand, Mitchell, [2]
Waters, Richard C.
weight
weight-leaf
Weyl, Hermann
‘‘what is’’ vs. ‘‘how to’’ description, see declarative vs. imperative knowledge
wheel
(rule), [2]
width
width of an interval
Wilde, Oscar (Perlis’s paraphrase of)
Wiles, Andrew
Winograd, Terry
Winston, Patrick Henry, [2]
wire, in digital circuit
Wisdom, Jack
Wise, David S.
wishful thinking, [2]
withdraw
problems in concurrent system
without-interrupts
world line of a particle, [2]
Wright, E. M.
Wright, Jesse B.
xcor-vect
Xerox Palo Alto Research Center, [2]
Y operator
ycor-vect
Yochelson, Jerome C.
Zabih, Ramin
zero crossings of a signal, [2], [3]
zero test (generic)
for polynomials
Zetalisp
Zilles, Stephen N.
Zippel, Richard E.
[Go to first, previous, next page; contents; index]
Document Outline - Structure and Interpretation of Computer Programs
- € Contents
- € Foreword
- € Preface to the Second Edition
- € Preface to the First Edition
- € Acknowledgments
- Chapter 1 Building Abstractions with Procedures
-
- 1.1€€The Elements of Programming
- 1.1.1€€Expressions
- 1.1.2€€Naming and the Environment
- 1.1.3€€Evaluating Combinations
- 1.1.4€€Compound Procedures
- 1.1.5€€The Substitution Model for Procedure Application
- Applicative order versus normal order
- 1.1.6€€Conditional Expressions and Predicates
- 1.1.7€€Example: Square Roots by Newton's Method
- 1.1.8€€Procedures as Black-Box Abstractions
- Local names
- Internal definitions and block structure
-
- 1.2€€Procedures and the Processes They Generate
- 1.2.1€€Linear Recursion and Iteration
- 1.2.2€€Tree Recursion
- 1.2.3€€Orders of Growth
- 1.2.4€€Exponentiation
- 1.2.5€€Greatest Common Divisors
- 1.2.6€€Example: Testing for Primality
- Searching for divisors
- The Fermat test
- Probabilistic methods
-
- 1.3€€Formulating Abstractions with Higher-Order Procedures
- 1.3.1€€Procedures as Arguments
- 1.3.2€€Constructing Procedures Using Lambda
- Using let to create local variables
- 1.3.3€€Procedures as General Methods
- Finding roots of equations by the half-interval method
- Finding fixed points of functions
- 1.3.4€€Procedures as Returned Values
- Newton's method
- Abstractions and first-class procedures
- Chapter 2 Building Abstractions with Data
-
- 2.1€€Introduction to Data Abstraction
- 2.1.1€€Example: Arithmetic Operations for Rational Numbers
- Pairs
- Representing rational numbers
- 2.1.2€€Abstraction Barriers
- 2.1.3€€What Is Meant by Data?
- 2.1.4€€Extended Exercise: Interval Arithmetic
-
- 2.2€€Hierarchical Data and the Closure Property
- 2.2.1€€Representing Sequences
- List operations
- Mapping over lists
- 2.2.2€€Hierarchical Structures
- 2.2.3€€Sequences as Conventional Interfaces
- Sequence Operations
- Nested Mappings
- 2.2.4€€Example: A Picture Language
- The picture language
- Higher-order operations
- Frames
- Painters
- Transforming and combining painters
- Levels of language for robust design
-
- 2.3€€Symbolic Data
- 2.3.1€€Quotation
- 2.3.2€€Example: Symbolic Differentiation
- The differentiation program with abstract data
- Representing algebraic expressions
- 2.3.3€€Example: Representing Sets
- Sets as unordered lists
- Sets as ordered lists
- Sets as binary trees
- Sets and information retrieval
- 2.3.4€€Example: Huffman Encoding Trees
- Generating Huffman trees
- Representing Huffman trees
- The decoding procedure
- Sets of weighted elements
-
- 2.4€€Multiple Representations for Abstract Data
- 2.4.1€€Representations for Complex Numbers
- 2.4.2€€Tagged data
- 2.4.3€€Data-Directed Programming and Additivity
-
- 2.5€€Systems with Generic Operations
- 2.5.1€€Generic Arithmetic Operations
- 2.5.2€€Combining Data of Different Types
- Coercion
- Hierarchies of types
- Inadequacies of hierarchies
- 2.5.3€€Example: Symbolic Algebra
- Chapter 3 Modularity, Objects, and State
-
- 3.1€€Assignment and Local State
- 3.1.1€€Local State Variables
- 3.1.2€€The Benefits of Introducing Assignment
- 3.1.3€€The Costs of Introducing Assignment
- Sameness and change
- Pitfalls of imperative programming
-
- 3.2€€The Environment Model of Evaluation
- 3.2.1€€The Rules for Evaluation
- 3.2.2€€Applying Simple Procedures
- 3.2.3€€Frames as the Repository of Local State
- 3.2.4€€Internal Definitions
-
- 3.3€€Modeling with Mutable Data
- 3.3.1€€Mutable List Structure
- Sharing and identity
- Mutation is just assignment
- 3.3.2€€Representing Queues
- 3.3.3€€Representing Tables
- Two-dimensional tables
- Creating local tables
- 3.3.4€€A Simulator for Digital Circuits
- Primitive function boxes
- Representing wires
- The agenda
- A sample simulation
- Implementing the agenda
- 3.3.5€€Propagation of Constraints
- Using the constraint system
- Implementing the constraint system
- Representing connectors
-
- 3.4€€Concurrency: Time Is of the Essence
- 3.4.1€€The Nature of Time in Concurrent Systems
- Correct behavior of concurrent programs
- 3.4.2€€Mechanisms for Controlling Concurrency
- Serializing access to shared state
- Serializers in Scheme
- Complexity of using multiple shared resources
- Implementing serializers
- Deadlock
- Concurrency, time, and communication
-
- 3.5€€Streams
- 3.5.1€€Streams Are Delayed Lists
- The stream implementation in action
- Implementing delay and force
- 3.5.2€€Infinite Streams
- Defining streams implicitly
- 3.5.3€€Exploiting the Stream Paradigm
- Formulating iterations as stream processes
- Infinite streams of pairs
- Streams as signals
- 3.5.4€€Streams and Delayed Evaluation
- 3.5.5€€Modularity of Functional Programs and Modularity of Objects
- A functional-programming view of time
- Chapter 4 Metalinguistic Abstraction
-
- 4.1€€The Metacircular Evaluator
- 4.1.1€€The Core of the Evaluator
- Eval
- Primitive expressions
- Special forms
- Combinations
- Apply
- Procedure arguments
- Conditionals
- Sequences
- Assignments and definitions
- 4.1.2€€Representing Expressions
- 4.1.3€€Evaluator Data Structures
- Testing of predicates
- Representing procedures
- Operations on Environments
- 4.1.4€€Running the Evaluator as a Program
- 4.1.5€€Data as Programs
- 4.1.6€€Internal Definitions
- 4.1.7€€Separating Syntactic Analysis from Execution
-
- 4.2€€Variations on a Scheme -- Lazy Evaluation
- 4.2.1€€Normal Order and Applicative Order
- 4.2.2€€An Interpreter with Lazy Evaluation
- Modifying the evaluator
- Representing thunks
- 4.2.3€€Streams as Lazy Lists
-
- 4.3€€Variations on a Scheme -- Nondeterministic Computing
- 4.3.1€€Amb and Search
- 4.3.2€€Examples of Nondeterministic Programs
- Logic Puzzles
- Parsing natural language
- 4.3.3€€Implementing the Amb Evaluator
- Execution procedures and continuations
- Structure of the evaluator
- Simple expressions
- Conditionals and sequences
- Definitions and assignments
- Procedure applications
- Evaluating amb expressions
- Driver loop
-
- 4.4€€Logic Programming
- 4.4.1€€Deductive Information Retrieval
- A sample data base
- Simple queries
- Compound queries
- Rules
- Logic as programs
- 4.4.2€€How the Query System Works
- Pattern matching
- Streams of frames
- Compound queries
- Unification
- Applying rules
- Simple queries
- The query evaluator and the driver loop
- 4.4.3€€Is Logic Programming Mathematical Logic?
- Infinite loops
- Problems with not
- 4.4.4€€Implementing the Query System
- 4.4.4.1€€The Driver Loop and Instantiation
- 4.4.4.2€€The Evaluator
- Simple queries
- Compound queries
- Filters
- 4.4.4.3€€Finding Assertions by Pattern Matching
- Patterns with dotted tails
- 4.4.4.4€€Rules and Unification
- 4.4.4.5€€Maintaining the Data Base
- 4.4.4.6€€Stream Operations
- 4.4.4.7€€Query Syntax Procedures
- 4.4.4.8€€Frames and Bindings
- Chapter 5 Computing with Register Machines
-
- 5.1€€Designing Register Machines
- 5.1.1€€A Language for Describing Register Machines
- 5.1.2€€Abstraction in Machine Design
- 5.1.3€€Subroutines
- 5.1.4€€Using a Stack to Implement Recursion
- 5.1.5€€Instruction Summary
-
- 5.2€€A Register-Machine Simulator
- 5.2.1€€The Machine Model
- Registers
- The stack
- The basic machine
- 5.2.2€€The Assembler
- 5.2.3€€Generating Execution Procedures for Instructions
- Assign instructions
- Test, branch, and goto instructions
- Other instructions
- Execution procedures for subexpressions
- 5.2.4€€Monitoring Machine Performance
-
- 5.3€€Storage Allocation and Garbage Collection
- 5.3.1€€Memory as Vectors
- Representing Lisp data
- Implementing the primitive list operations
- Implementing stacks
- 5.3.2€€Maintaining the Illusion of Infinite Memory
- Implementation of a stop-and-copy garbage collector
-
- 5.4€€The Explicit-Control Evaluator
-
- 5.4.1€€The Core of the Explicit-Control Evaluator
- 5.4.2€€Sequence Evaluation and Tail Recursion
- 5.4.3€€Conditionals, Assignments, and Definitions
- Assignments and definitions
- 5.4.4€€Running the Evaluator
- Monitoring the performance of the evaluator
-
- 5.5€€Compilation
-
- An overview of the compiler
- 5.5.1€€Structure of the Compiler
- Targets and linkages
- Instruction sequences and stack usage
- 5.5.2€€Compiling Expressions
- Compiling linkage code
- Compiling simple expressions
- Compiling conditional expressions
- Compiling sequences
- Compiling lambda expressions
- 5.5.3€€Compiling Combinations
- Applying procedures
- Applying compiled procedures
- 5.5.4€€Combining Instruction Sequences
- 5.5.5€€An Example of Compiled Code
- 5.5.6€€Lexical Addressing
- 5.5.7€€Interfacing Compiled Code to the Evaluator
- Interpretation and compilation
- € References
- € List of Exercises
- € Index
Dostları ilə paylaş: |
