# Exercises

- 1.1 Sequence of expressions
- 1.2 Into prefix form
- 1.3 Sum of the squares
- 1.4 Composite expressions
- 1.5 Calculation order
- 1.6 Special form
- 1.7 Square root
- 1.8 Cube root
- 1.9 Procedures of sum
- 1.10 Ackermann's function
- 1.11 Iterative and recursive processes
- 1.12 Pascal's triangle
- 1.13 Fibonacci numbers and golden ratio
- 1.14 Exchange 11 cents
- 1.15 The sine of an angle
- 1.16 Fast exponentiation
- 1.17 Multiplication by means of repeated addition
- 1.18 Iterative process for multiplying two integers
- 1.19 Fibonacci numbers through transformation
- 1.20 Gcd and orders of evaluation
- 1.21 Smallest divisor
- 1.22 Smallest primes
- 1.23 Modify the smallest-divisor
- 1.24 Modify the timed-prime-test
- 1.25 Extra work
- 1.26 Slow procedure
- 1.27 Carmichael numbers
- 1.28 Miller-Rabin test
- 1.29 Simpson's Rule
- 1.30 Iteration
- 1.31 Higher-order procedures
- 1.32 Accumulation
- 1.33 General accumulation
- 1.34 Evaluate the combination
- 1.35 Golden ratio
- 1.36 Fixed point
- 1.37 Finite continued fraction
- 1.38 Euler's expansion
- 1.39 Lambert's formula
- 1.40 Approximate zeros
- 1.41 Double
- 1.42 Composition
- 1.43 Nth repeated application of f
- 1.44 N-fold smoothed function
- 1.45 Computing nth roots
- 1.46 Iterative improvement

- 2.1 Modify the make-rat
- 2.2 Representation of line segments on the plane.
- 2.3 Representation of rectangles on a plane
- 2.4 Procedural representation of pairs
- 2.5 Representation of pairs using only numbers and arithmetic operations
- 2.6 Church numerals
- 2.7 Upper and lower bounds of interval
- 2.8 Subtraction of intervals
- 2.9 The width of an interval
- 2.10 Interval that spans zero
- 2.11 The signs of the endpoints of the intervals
- 2.12 Interval produced by center and percentage tolerance
- 2.13 Percentage tolerance of the product of two intervals
- 2.14 Different answers for the two ways of computing formulas for parallel resistors
- 2.15 A form of formula that no variable that represents an uncertain number is repeated
- 2.16 Different answers in equivalent algebraic expressions in general
- 2.17 Last element of list
- 2.18 Reverse
- 2.19 Change coins of different currencies
- 2.20 Dotted-tail notation
- 2.21 A list of the squares
- 2.22 Square-list with iterative process
- 2.23 The procedure for-each
- 2.24 Box-and-pointer structure
- 2.25 Pick 7 from lists
- 2.26 Expressions with two lists
- 2.27 Deep reverse
- 2.28 List of tree leaves
- 2.29 Binary mobile
- 2.30 A tree of the squares
- 2.31 Tree map
- 2.32 The set of all subsets
- 2.33 List-manipulation operations as accumulations
- 2.34 Horner's rule
- 2.35 Count-leaves as an accumulation
- 2.36 Accumulate-n
- 2.37 Matrix operations
- 2.38 Folds
- 2.39 Reverse in terms of folds
- 2.40 Unique pairs
- 2.41 Ordered triples
- 2.42 Eight queens puzzle
- 2.43 Optimization of queens
- 2.44 Up-split procedure
- 2.45 Split procedure
- 2.46 Representation of vectors
- 2.47 Frames implementation
- 2.48 Representation of segments using vectors.
- 2.49 Primitive painters
- 2.50 Flip and rotate transformations
- 2.51 Below procedure
- 2.52 Modification of wave
- 2.53 Expressions evaluating
- 2.54 Equal? as a procedure
- 2.55 Expressions with quotes
- 2.56 Basic differentiator
- 2.57 Differentiation of arbitrary numbers of terms
- 2.58 Modification of the differentiation program
- 2.59 Union-set for sets represented as unordered lists
- 2.60 Set with duplicates
- 2.61 Adjoin-set for the ordered representation
- 2.62 Union-set for for sets represented as ordered lists
- 2.63 Converting a binary tree to a list
- 2.64 Partial-tree procedure
- 2.65 Procedures for sets implemented as (balanced) binary trees
- 2.66 Lookup procedure
- 2.67 Message decoding
- 2.68 Encode-symbol procedure
- 2.69 Successive-merge procedure
- 2.70 Encode the message
- 2.71 Frequencies of the symbols
- 2.72 Growth order for character encoding
- 2.73 Symbolic differentiation program with dispatching
- 2.74 Data Structures at Insatiable Enterprises, Inc
- 2.75 Make-from-mag-ang constructor in message-passing style
- 2.76 Evolving system with generalized operations.
- 2.77 Complex-number selectors
- 2.78 Scheme's internal type system
- 2.79 Generic equality predicate equ?
- 2.80 Generic predicate =zero?
- 2.81 Coercion of the arguments with same type
- 2.82 Coercion in the general case of multiple arguments
- 2.83 A generic raise operation
- 2.84 Successive raising
- 2.85 Drop procedure
- 2.86 Generic complex numbers
- 2.87 =zero? for polynomials
- 2.88 Subtraction of polynomials
- 2.89 Procedures for dense polynomials
- 2.90 Generic operations on term lists
- 2.91 Division of univariate polynomial
- 2.92 Addition and multiplication of polynomials with different variables
- 2.93 Generic operations in rational-arithmetic package
- 2.94 Generic operation
- 2.95 Pseudodivision
- 2.96 Integerizing factor
- 2.97 Algorithm as a procedure

- 3.1 Creation of accumulators
- 3.2 Number of procedure calls
- 3.3 Password-protected account
- 3.4 Control the number of password attempts
- 3.5 Monte Carlo integration
- 3.6 Advanced random number generator
- 3.7 Joint accounts
- 3.8 Order for evaluating subexpressions
- 3.9 Factorial procedure environments
- 3.10 Alternative Version Analysis
- 3.11 Internal Definitions
- 3.12 Appending lists
- 3.13 Make-cycle procedure
- 3.14 Mystery procedure
- 3.15 Box-and-pointer diagrams
- 3.16 The procedure to count the number of pairs
- 3.17 The number of distinct pairs in a structure
- 3.18 Determine if a loop is in the list
- 3.19 Optimize memory usage
- 3.20 Draw environment diagrams
- 3.21 Print-queue procedure
- 3.22 A queue as a procedure with local state
- 3.23 A deque
- 3.24 A table constructor make-table
- 3.25 Generalizing one- and two-dimensional tables
- 3.26 Ordered keys in a table organized as a binary tree
- 3.27 Memoization
- 3.28 An or-gate as a primitive function box
- 3.29 An or-gate as a compound digital logic device
- 3.30 Ripple-carry adder
- 3.31 Accept-action-procedure! procedure
- 3.32 The procedures in a queue
- 3.33 Averager procedure
- 3.34 Squarer
- 3.35 Squarer as a primitive constraint
- 3.36 Environment diagram
- 3.37 ''Сonstraint'' versions of the arithmetic operations
- 3.38 Joint bank account
- 3.39 Remaining possibilities
- 3.40 All possible values of x
- 3.41 Serialized make-account
- 3.42 Make-account changing
- 3.43 Timing diagrams
- 3.44 The problem of transferring an amount from one account to another
- 3.45 Redefine accounts
- 3.46 Draw a timing diagram
- 3.47 Implementations of semaphores
- 3.48 Serialized-exchange with the deadlock-avoidance method
- 3.49 Scenario where the deadlock-avoidance mechanism does not work
- 3.50 Generic stream-map
- 3.51 Value of expressions
- 3.52 The value of sum
- 3.53 Description of the elements of the stream
- 3.54 Mul-streams procedure
- 3.55 Partial-sums procedure
- 3.56 Hamming's problem of number generation
- 3.57 Additions in computing Fibonacci numbers.
- 3.58 An interpretation of the stream
- 3.59 Power series represented as infinite streams
- 3.60 Procedure for multiplying series
- 3.61 Invert-unit-series procedure
- 3.62 Div-series procedure
- 3.63 Efficient of the sqrt-stream procedure
- 3.64 Stream-limit procedure
- 3.65 Three sequences of approximations to the natural logarithm of 2
- 3.66 Order of pairs in the stream
- 3.67 Modification of pairs
- 3.68 Alternative definition of pairs
- 3.69 Triples procedure
- 3.70 Weighting function
- 3.71 Ramanujan numbers
- 3.72 A stream of numbers that can be written as the sum of two squares
- 3.73 An RC circuit
- 3.74 Zero crossings
- 3.75 Signal smoothing
- 3.76 Smooth procedure
- 3.77 Modification of the integral procedure
- 3.78 Solve-2nd procedure
- 3.79 Generalize the solve-2nd procedure
- 3.80 A series RLC circuit
- 3.81 Stream of random numbers
- 3.82 Monte Carlo integration in terms of streams

- 4.1 Evaluation order
- 4.2 Help Louis
- 4.3 Rewrite eval
- 4.4 Special forms
- 4.5 Modify the handling of cond
- 4.6 Implement a syntactic transformation
- 4.7 Let*
- 4.8 Named let
- 4.9 Iteration constructs
- 4.10 Implement a new syntax for Scheme
- 4.11 Rewrite the environment operations
- 4.12 The common patterns
- 4.13 Implement a special form make-unbound!
- 4.14 Why Louis's map fails?
- 4.15 Show that it is impossible to write a procedure halts?
- 4.16 Implement the method for interpreting internal definitions
- 4.17 Draw diagrams of the environment
- 4.18 Alternative strategy for scanning out definitions
- 4.19 Implement internal definitions
- 4.20 Special form of letrec
- 4.21 Recursive procedures without using letrec
- 4.22 Extend the evaluator
- 4.23 Compare the two versions of analyze-sequence
- 4.24 Design and carry out some experiments
- 4.25 Attempt to evaluate Factorial
- 4.26 The importance of lazy evaluation
- 4.27 The interaction between lazy evaluation and side effects
- 4.28 Evaluate the operator using actual-value
- 4.29 Demonstrate the benefits of memoization
- 4.30 Working with sequences in the lazy evaluator
- 4.31 The behavior of the lazy evaluator
- 4.32 The difference between the streams and the lazy lists
- 4.33 Modify the evaluator's treatment of quoted expressions
- 4.34 Modify the driver loop for the evaluator
- 4.35 Write a procedure an-integer-between
- 4.36 Generate arbitrary Pythagorean triples
- 4.37 Efficiency of generating Pythagorean triples
- 4.38 Modify the multiple-dwelling procedure
- 4.39 The order of the restrictions in the multiple-dwelling
- 4.40 Efficiency of generating possibilities
- 4.41 Solve the multiple dwelling puzzle
- 4.42 Solve the "Liars" puzzle
- 4.43 Who is Lorna's father?
- 4.44 A nondeterministic program to solve ''eight-queens puzzle''
- 4.45 Five different ways of sentence parsing
- 4.46 Order of operands evaluation
- 4.47 Alternative variant of parse-verb-phrase
- 4.48 The grammar extension
- 4.49 Sentences generating
- 4.50 Special form ramb
- 4.51 Permanent-set! assignment
- 4.52 If-fail construct
- 4.53 The result of evaluating
- 4.54 Analyze-require procedure
- 4.55 Simple queries
- 4.56 Compound queries
- 4.57 'Replace person' rule
- 4.58 ''Big shot'' rule
- 4.59 Meeting-time rule
- 4.60 Lives-near query
- 4.61 Rules for next-to relation
- 4.62 Rules for last-pair
- 4.63 Genesis 4
- 4.64 An infinite loop
- 4.65 A query to find all the wheels
- 4.66 The total salaries of all the computer programmers
- 4.67 The query system loop detector
- 4.68 Rules for reverse operation
- 4.69 A rule for adding ''greats'' to a grandson relationship
- 4.70 The purpose of the let bindings in the procedures add-assertion! and add-rule!
- 4.71 Explicit delay in the simple-query and disjoin procedures
- 4.72 Streams interleaving
- 4.73 Explicit delay in flatten-stream
- 4.74 A simpler version of stream-flatmap
- 4.75 A new special form - unique
- 4.76 Separate processing the two clauses of the 'and'
- 4.77 The filtering in a ''delayed'' manner
- 4.78 The query language as a nondeterministic program
- 4.79 A rule-application method that uses environments

- 5.1 Register machine
- 5.2 Describe the iterative factorial machine
- 5.3 Сompute square roots using Newton's method
- 5.4 Specify register machines
- 5.5 Hand-simulate the factorial and Fibonacci machines
- 5.6 Extra save and extra restore
- 5.7 Test the machines
- 5.8 Modify the extract-labels procedure
- 5.9 Using operations to registers and constants only
- 5.10 New syntax for register-machine
- 5.11 Restore a register that was not the last one saved
- 5.12 Extend the assembler
- 5.13 Machine registers determination
- 5.14 The number of pushes and the maximum stack depth required to compute n!
- 5.15 Instruction counting
- 5.16 Instruction tracing
- 5.17 Labels print
- 5.18 Traced registers
- 5.19 A breakpoint feature
- 5.20 Box-and-pointer and memory-vector representations
- 5.21 Register machines for count-leaves
- 5.22 A register machine for append procedure
- 5.23 Derived expressions handling
- 5.24 Сond as a new basic special form
- 5.25 Normal order evaluator based on lazy evaluator
- 5.26 Exploration of the tail-recursive property of the evaluator
- 5.27 The maximum depth of the stack and the total number of pushes used in evaluating n!
- 5.28 The evaluator without tail-recursion
- 5.29 The stack operations in the tree-recursive Fibonacci computation
- 5.30 Error handling system
- 5.31 Superfluous operations
- 5.32 Combinations whose operator is a symbol
- 5.33 Сompare the resulting code of a factorial procedure
- 5.34 The essential difference between the code for iterative and recursive versions of factorial
- 5.35 An example of compiler output
- 5.36 Order of evaluation of compiler
- 5.37 Compiler's preserving mechanism
- 5.38 Support open coding of selected primitives
- 5.39 lexical-address-lookup and lexical-address-set! procedures
- 5.40 Compile-time environment maintaining
- 5.41 Find-variable procedure
- 5.42 Compile-variable and compile-assignment with lexical-address instructions
- 5.43 The compiler and internal definitions
- 5.44 Modification of the open-coding compiler
- 5.45 The quality of the compiler
- 5.46 The effectiveness of compiling the tree-recursive Fibonacci procedure
- 5.47 Modifying evaluator
- 5.48 Compile-and-run primitive
- 5.49 Register machine
- 5.50 Metacircular evaluator
- 5.51 Rudimentary implementation of Scheme in C
- 5.52 Scheme compiler into C instructions