# **References**
- [1]Harold Abelson and Gerald Jay Sussman with Julie Sussman, *Structure and Interpretation of Computer Programs* (2nd ed.). Cambridge, MA: MIT Press, 1996.
- [2]Harold Abelson, Don Allen, Daniel Coore, Chris Hanson, George Homsy, Thomas F. Knight Jr., Radhika Nagpal, Erik Rauch, Gerald Jay Sussman, and Ron Weiss; "Amorphous Computing," in *Communications of the ACM*, 43(5) (May 2000): 74–82.
- [3]Lee Altenberg; "The Evolution of Evolvability in Genetic Programming," in *Advances in Genetic Programming*, ed. Kenneth E. Kinnear Jr., 47–74. Cambridge, MA: MIT Press, 1994.
- [4]*The ARRL Handbook for Radio Amateurs*, American Radio Relay League, Newington, CT (annual).
- [5]Jean-Paul Arcangeli and Christian Pomian; "Principles of Plasma Pattern and Alternative Structure Compilation," in *Theoretical Computer Science*, 71 (1990): 177–191.
- [6]Franz Baader and Wayne Snyder; "Unification theory," in *Handbook of Automated Reasoning*, ed. Alan Robinson and Andrei Voronkov. Elsevier Science Publishers B.V., 2001.
- [7]Jonathan B.L. Bard; *Morphogenesis*, Cambridge: Cambridge University Press, 1990.
- [8]Alan Bawden and Jonathan Rees; "Syntactic closures," in *Proc. Lisp and Functional Programming* (1988).
- [9]Jacob Beal; *Generating Communications Systems Through Shared Context*, S.M. thesis, MIT, also Artificial Intelligence Laboratory Technical Report 2002-002, January 2002.
- [10]Jacob Beal; "Programming an Amorphous Computational Medium," in *Unconventional Programming Paradigms International Workshop* (September 2004). Updated version in Lecture Notes in Computer Science, 3566 (August 2005).
- [11]M.R. Bernfield, S.D. Banerjee, J.E. Koda, and A.C. Rapraeger; "Remodelling of the basement membrane as a mechanism of morphogenic tissue interaction," in *The role of extracellular matrix in development*, ed. R.L. Trelstad, 542–572. New York: Alan R. Liss, 1984.
- [12]Martin Berz; "Automatic differentiation as nonarchimedean analysis," in *Computer Arithmetic and Enclosure Methods*, ed. L. Atanassova and J. Herzberger. Elsevier Science Publishers B.V. (North-Holland), 1992.
- [13]Philip L. Bewig; *Scheme Requests for Implementation 41: Streams* (2008).
- [14]R.C. Bohlin and R.L. Gilliland; "Hubble Space Telescope Absolute Spectrophotometry of Vega from the Far-Ultraviolet to the Infrared," in *The Astronomical Journal*, 127(6) (June 2004): 3508–3515.
- [15]J.P. Brocks; "Amphibian limb regeneration: rebuilding a complex structure," in *Science*, 276 (1997): 81–87.
- [16]Alonzo Church; *The Calculi of Lambda-Conversion*. Princeton, NJ: Princeton University Press, 1941.
- [17]Alonzo Church; "An Unsolvable Problem of Elementary Number Theory," *American Journal of Mathematics*, 58 (1936): 345–
- [18]Alonzo Church; "A Note on the Entscheidungsproblem," in *Journal of Symbolic Logic*, 1 (1936): 40–41.
- [19]Lauren Clement and Radhika Nagpal; "Self-Assembly and Self-Repairing Topologies," in *Workshop on Adaptability in Multi-Agent Systems*, RoboCup Australian Open, January 2003.
- [20]William Kingdon Clifford; "Preliminary sketch of biquaternions," in *Proceedings of the London Mathematical Society*, 4 (1873): 381– 395.
- [21]William Clinger; "Nondeterministic Call by Need is Neither Lazy Nor by Name," in *Proceedings of the 1982 ACM symposium on LISP and functional programming*, 226–234 (August 1982).
- [22]William Clinger and Jonathan Rees; "Macros that work," in *Proceedings of the 1991 ACM Conference on Principles of Programming Languages*, 155–162 (1991).
- [23]A Colmerauer., H. Kanoui, R. Pasero, and P. Roussel; *Un système de communication homme-machine en français*, Technical report, Groupe Intelligence Artificielle, Université d'Aix Marseille, Luminy, 1973.
- [24]*Constraints, An International Journal* ISSN: 1383-7133 (Print) 1572-9354 (Online).
- [25]Wikipedia article on continuations.
- [26]Haskell Brooks Curry; "Grundlagen der Kombinatorischen Logik," in *American Journal of Mathematics*. Baltimore: Johns Hopkins University Press, 1930.
- [27]Johan deKleer, Jon Doyle, Guy Steele, and Gerald J. Sussman; "AMORD: Explicit control of reasoning," in *Proceedings of the*
- *ACM Symposium on Artificial Intelligence and Programming Languages*, 116–125 (1977).
- [28]E.M. del Pino and R.P. Elinson; "A novel developmental pattern for frogs: gastrulation produces an embryonic disk," in *Nature*, 306 (1983): 589–591.
- [29]Howard P. Dinesman; *Superior Mathematical Puzzles*. New York: Simon and Schuster, 1968.
- [30]Jon Doyle; "A truth maintenance system," in *Artificial Intelligence*, 12 (1979): 231–272.
- [31]K. Dybvig, R. Hieb, and C. Bruggerman; "Syntactic abstraction in Scheme," in *Proc. Lisp and Symbolic Computation* (1993).
- [32]G.M. Edelman and J.A. Gally; "Degeneracy and complexity in biological systems," *Proceedings of the National Academy of Sciences*, 98 (2001): 13763–13768.
- [33]M. D. Ernst, C. Kaplan, and C. Chambers; "Predicate Dispatching: A Unified Theory of Dispatch," in *ECOOP'98— Object-Oriented Programming: 12th European Conference*, *Proceedings*, ed. Eric Jul, 186–211, Lecture Notes in Computer Science, 1445. Berlin: Springer, 1998.
- [34]Zsuzsa Farkas; "LISTLOG—A PROLOG extension for list processing," in *TAPSOFT 1987*, ed. Ehrig H., Kowalski R., Levi G., Montanari U., Lecture Notes in Computer Science, 250. Berlin: Springer, 1987.
- [35]Robert Floyd; "Nondeterministic algorithms," in *Journal of the ACM*, 14(4) (1967): 636–644.
- [36]Kenneth D. Forbus and Johan de Kleer; *Building Problem Solvers*. Cambridge, MA: MIT Press, 1993.
- [37]Stefanie Forrest, Anil Somayaji, David H. Ackley; "Building Diverse Computer Systems," in *Proceedings of the 6th*
- *workshop on Hot Topics in Operating Systems*, 67–72. Los Alamitos, CA: IEEE Computer Society Press, 1997.
- [38]Joseph Frankel; *Pattern Formation, Ciliate Studies and Models*. New York: Oxford University Press, 1989.
- [39]Eugene C. Freuder; *Synthesizing Constraint Expressions*. AI Memo 370, MIT Artificial Intelligence Laboratory, July 1976.
- [40]Daniel P. Friedman and David S. Wise; "Cons should not evaluate its arguments," in *Automata Languages and Programming*; Proc. Third International Colloquium at the University of Edinburgh, ed. S. Michaelson and R. Milner, 257– 284 (July 1976).
- [41]Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes; *Essentials of Programming Languages.* Cambridge, MA: MIT Press/McGraw-Hill, 1992.
- [42]Richard P. Gabriel and Linda DeMichiel; "The Common Lisp Object System: An Overview," in *Proceedings of ECOOP'87. European Conference on Object-Oriented Programming*, ed. Jean Bezivin, Jean-Marie Hullot, Pierre Cointe, and Henry Lieberman, 151–170. Paris: Springer, 1987.
- [43]George Gatewood and Joost Kiewiet de Jonge; "Map-based Trigonometric Parallaxes of Altair and Vega," in *The Astrophysical Journal*, 450 (September 1995): 364–368.
- [44]George Gatewood; "Astrometric Studies of Aldebaran, Arcturus, Vega, the Hyades, and Other Regions," in *The Astronomical Journal*, 136(1) (2008): 452–460.
- [45]Kurt Gödel; "On Undecidable Propositions of Formal Mathematical Systems," *Lecture notes taken by Kleene and Rosser at the Institute for Advanced Study* (1934), reprinted in Martin Davis *The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions*, 39–74. New York: Raven, 1965.
- [46]Adele Goldberg and David Robson; *Smalltalk-80: The Language and Its Implementation*. Reading, MA: Addison-Wesley, 1983.
- [47]Michael Gordon, Robin Milner, and Christopher Wadsworth; *Edinburgh LCF*, Lecture Notes in Computer Science, 78. New York: Springer-Verlag, 1979.
- [48]Cordell Green; "Application of theorem proving to problem solving," in *Proceedings of the International Joint Conference on Artificial Intelligence*, 219–240 (1969).
- [49]Cordell Green and Bertram Raphael; "The use of theoremproving techniques in question-answering systems," in *Proceedings of the ACM National Conference*, 169–181 (1968).
- [50]John V. Guttag; "Abstract data types and the development of data structures," *Communications of the ACM*, 20(6) (1977): 397–404.
- [51]Chris Hanson; *MIT/GNU Scheme Reference Manual*.
- [52]Chris Hanson; SOS software: Scheme Object System, 1993.
- [53]Chris Hanson, Tim Berners-Lee, Lalana Kagal, Gerald Jay Sussman, and Daniel Weitzner; "Data-Purpose Algebra: Modeling Data Usage Policies," in *Eighth IEEE International Workshop on Policies for Distributed Systems and Networks (POLICY'07)*, (June 2007).
- [54]Hyman Hartman and Temple F. Smith; "The Evolution of the Ribosome and the Genetic Code," in *Life*, 4 (2014): 227–249.
- [55]Jacques Herbrand; "Sur la non-contradiction de larithmetique," *Journal fur die reine und angewandte Mathematik*, 166 (1932): 1–8.
- [56]Carl E. Hewitt; "PLANNER: A language for proving theorems in robots," in *Proceedings of the International Joint Conference on Artificial Intelligence*, 295–301 (1969).
- [57]Carl E. Hewitt; "Viewing control structures as patterns of passing messages," in *Journal of Artificial Intelligence*, 8(3) (1977): 323–364.
- [58]Carl Hewitt, Peter Bishop, Richard Steiger; "A Universal Modular ACTOR Formalism for Artificial Intelligence," in *IJCAI-73: Proceedings of the Third International Joint Conference on Artificial Intelligence*, 235–245 (1973).
- [59]Edwin Hewitt; "Rings of real-valued continuous functions. I," in *Transactions of the American Mathematical Society*, 64 (1948): 45–99.
- [60]Paul Horowitz and Winfield Hill; *The Art of Electronics*. Cambridge: Cambridge University Press, 1980.
- [61]IEEE Std 1178-1990, *IEEE Standard for the Scheme Programming Language*, Institute of Electrical and Electronic Engineers, Inc., 1991.
- [62]Paul-Alan Johnson; *The Theory of Architecture: Concepts, Themes, & Practices*. New York: Van Nostrand Reinhold, 1994.
- [63]Jerome H. Keisler; "The hyperreal line. Real numbers, generalizations of the reals, and theories of continua," in *Synthese Library*, 242, 207–237. Dordrecht: Kluwer Academic, 1994.
- [64]Richard Kelsey, William Clinger, and Jonathan Rees (editors); *Revised* 5 *Report on the Algorithmic Language Scheme* (1998).
- [65]Richard Kelsey; *Scheme Requests for Implementation 9: Defining Record types* (1999).
- [66]Gregor Kiczales; Tiny CLOS software: Kernelized CLOS, with a metaobject protocol, 1992.
- [67]Gregor Kiczales, John Lamping, Anurag Mendhekar, Chris Maeda, Cristina Videira Lopes, Jean-Marc Loingtier, and John Irwin; "Aspect-oriented programming," in *ECOOP'97: Proceedings of the 11th European Conference on Object-Oriented Programming*, 220–242 (1997).
- [68]Gregor Kiczales, Jim des Rivieres, and Daniel G. Bobrow; *The Art of the Metaobject Protocol*. Cambridge, MA: MIT Press, 1991.
- [69]Simon Kirby; *Language evolution without natural selection: From vocabulary to syntax in a population of learners.*, Edinburgh Occasional Paper in Linguistics EOPL-98-1, University of Edinburgh Department of Linguistics (1998).
- [70]Marc W. Kirschner and John C. Gerhart; *The Plausibility of Life: Resolving Darwin's Dilemma*. New Haven: Yale University Press, 2005.
- [71]Marc W. Kirschner, Tim Mitchison; "Beyond self-assembly: from microtubules to morphogenesis," in *Cell*, 45(3) (May 1986): 329–342.
- [72]D. Knuth, P. Bendix; "Simple word problems in universal algebras," in *Computational Problems in Abstract Algebra*, ed. John Leech, 263–297. London: Pergamon Press, 1970.
- [73]E. Kohlbecker, D. P. Friedman, M. Felleisen, and B. Duba; "Hygienic Macro Expansion," in *ACM Conference on LISP and Functional Programming* (1986).
- [74]E. Kohlbecker and Mitchell Wand; "Macro-by-example: Deriving syntactic transformations from their specifications," in *Proc. Symposium on Principles of Programming Languages* (1987).
- [75]Milos Konopasek and Sundaresan Jayaraman; *The TK!Solver Book: A Guide to Problem-Solving in Science, Engineering, Business, and Education.* Berkeley, CA: Osborne/McGraw-Hill, 1984.
- [76]Robert Kowalski; *Predicate logic as a programming language*, Technical report 70, Department of Computational Logic, School of Artificial Intelligence, University of Edinburgh, 1973.
- [77]Robert Kowalski; *Logic for Problem Solving*. New York: North-Holland, 1979.
- [78]Robert M. Kowalski; "The Early Years of Logic Programming," in *Communications of the ACM*, 31(1) (January 1988): 38–43.
- [79]Temur Kutsia; "Pattern Unification with Sequence Variables and Flexible Arity Symbols," in *Electronic Notes in Theoretical Computer Science*, 66(5) (2002): 52–69.
- [80]Butler Lampson, J. J. Horning, R. London, J. G. Mitchell, and G. K. Popek; *Report on the programming language Euclid*, Technical report, Computer Systems Research Group, University of Toronto, 1981.
- [81]Peter Landin; "A correspondence between Algol 60 and Church's lambda notation: Part I," *Communications of the ACM*, 8(2) (1965): 89–101.
- [82]Henrietta S. Leavitt; "1777 variables in the Magellanic Clouds," in *Annals of Harvard College Observatory*, 60 (1908): 87–108.
- [83]Floor Van Leeuwen; "Validation of the new Hipparcos reduction," in *Astronomy & Astrophysics*, 474(2) (2007): 653– 664.
- [84]Karl Lieberherr; *Informationsverdichtung von Modellen in der Aus-sagenlogik und das P=NP Problem*, ETH Dissertation, 1977.
- [85]Barbara H. Liskov and Stephen N. Zilles; " Specification techniques for data abstractions," in *IEEE Transactions on Software Engineering*, 1(1) (1975): 7–19.
- [86]Harvey Lodish, Arnold Berk, S Lawrence Zipursky, Paul Matsudaira, David Baltimore, and James E Darnell; *Molecular Cell Biology* (4th ed.). New York: W. H. Freeman & Co., 1999.
- [87]Oleksandr Manzyuk, Barak A. Pearlmutter, Alexey Andreyevich Radul, David R. Rush, and Jeffrey Mark Siskind; "Confusion of Tagged Perturbations in Forward Automatic Differentiation of Higher-Order Functions," arxiv:1211.4892 (2012).
- [88]David Allen McAllester; *A three-valued truth-maintenance system*, AI Memo 473, MIT Artificial Intelligence Laboratory, 1978.
- [89]David Allen McAllester "An outlook on truth maintenance," AI Memo 551, MIT Artificial Intelligence Laboratory, 1980.
- [90]John McCarthy; "A basis for a mathematical theory of computation," in *Computer Programming and Formal Systems*, ed. P. Braffort and D. Hirshberg, 33–70. Amsterdam: North-Holland, 1963.
- [91]Wikipedia article on MDL. (programming language)
- [92]Piotr Mitros; *Constraint-Satisfaction Modules: A Methodology for Analog Circuit Design*, PhD thesis, MIT, Department of Electrical Engineering and Computer Science, 2007.
- [93]Paul Penfield Jr.; *MARTHA User's Manual*, MIT Research Laboratory of Electronics, Electrodynamics Memorandum No. 6 (1970).
- [94]Barak A. Perlmutter and Jeffrey Mark Siskind; "Lazy Multivariate Higher-Order Forward-Mode AD," in *Proc. POPL'07*, 155–160. New York: ACM, 2007.
- [95]Tim Peters; *PEP 20—The Zen of Python*.
- [96]*POSIX.1-2017*, "Base Definitions," Chapter 9, "Regular Expressions."
- [97]Jonathan Bruce Postel; *RFC 760: DoD standard Internet Protocol* (January 1980). http://www.rfc[editor.org/rfc/rfc760.txt](http://www.rfc-editor.org/rfc/rfc760.txt)
- [98]W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling; "Richardson Extrapolation and the Bulirsch-Stoer Method," in *Numerical Recipes in C: The Art of Scientific Computing* (2nd ed.), 718–725. Cambridge: Cambridge University Press, 1992.
- [99]Alexey Andreyevich Radul and Gerald Jay Sussman; "The Art of the Propagator," MIT CSAIL Technical Report MIT-CSAIL-TR-2009-002; Abridged version in *Proc. 2009 International Lisp Conference* (March 2009).
- [100]Alexey Andreyevich Radul; *Propagation networks: a flexible and expressive substrate for computation*, PhD thesis, MIT, Department of Electrical Engineering and Computer Science, 2009.
- [101]Eric Raymond; *The New Hacker's Dictionary* (2nd ed.). Cambridge, MA: MIT Press, 1993.
- [102]Jonathan A. Rees and Norman I. Adams IV; "T: A dialect of Lisp or, lambda: The ultimate software tool," in *Conference Record of the 1982 ACM Symposium on Lisp and Functional Programming*, 114–122 (1982).
- [103]John C. Reynolds; "The discoveries of continuations," in *Proc. Lisp and Symbolic Computation*, 233–248 (1993).
- [104]J.A. Robinson; "A Machine-Oriented Logic Based on the Resolution Principle," in *Journal of the ACM*, 12(1) (January 1965): 23–41.
- [105]Guido van Rossum; *The Python Language Reference Manual*, ed. Fred L. Drake Jr., Network Theory Ltd, 2003.
- [106]Jane L. Russell, George D. Gatewood, and Thaddeus F. Worek; "Parallax Studies of Four Selected Fields," in *The Astronomical Journal*, 87(2) (February 1982): 428–432.
- [107]Erik Sandewall; "From systems to logic in the early development of nonmonotonic reasoning," in *Artificial Intelligence*, 175 (2011): 416–427.
- [108]Moses Schönfinkel; "Uber die Bausteine der mathematischen Logik," in *Mathematische Annalen*, 92 (1924): 305–316.
- [109]Alex Shinn, John Cowan, and Arthur Gleckler (editors); *Revised* 7 *Report on the Algorithmic Language Scheme* (2013).
- [110]Alex Shinn; *Scheme Requests for Implementation 115: Scheme Regular Expressions* (2014). [https://srfi.schemers.org/srfi-](https://srfi.schemers.org/srfi-115/)115/
- [111]Jeffrey Mark Siskind and Barak A. Perlmutter; "Perturbation confusion and referential transparency: Correct functional implementation of forward-mode AD," in *Implementation and application of functional languages–17th international workshop*, ed. Andrew Butterfield, Trinity College Dublin Computer Science Department Technical Report TCD-CS-2005-60, 2005.
- [112]Brian Cantwell Smith; *Procedural Reflection in Programming Languages*, PhD thesis, MIT, Department of Electrical Engineering and Computer Science, 1982.
- [113]Richard Matthew Stallman; *EMACS: The Extensible, Customizable, Self-Documenting Display Editor*, AI Memo 519A, MIT Artificial Intelligence Laboratory, March 1981.
- [114]Richard Matthew Stallman and Gerald Jay Sussman; "Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis," in *Artificial Intelligence*, 9 (1977): 135–196.
- [115]Guy Lewis Steele Jr.; *Common Lisp the language*. Maynard, MA: Digital Equipment Corporation, 1990.
- [116]Guy L. Steele Jr.; *The Definition and Implementation of a Computer Programming Language Based on Constraints*, PhD thesis, MIT, also Artificial Intelligence Laboratory Technical Report 595, August 1980.
- [117]Guy Lewis Steele Jr., Donald R. Woods, Raphael A. Finkel, Mark R. Crispin, Richard M. Stallman, and Geoffrey S. Goodfellow; *The Hacker's Dictionary*. New York: Harper & Row, 1983.
- [118]Patrick Suppes; *Introduction to Logic*. New York: D. Van Nostrand, 1957.
- [119]Gerald Jay Sussman and Richard Matthew Stallman; "Heuristic Techniques in Computer-Aided Circuit Analysis," in *IEEE Transactions on Circuits and Systems*, 22(11) (November 1975): 857–865.
- [120]Gerald Jay Sussman and Guy L. Steele Jr; "The First Report on Scheme Revisited," in *Higher-Order and Symbolic Computation*, 11(4) (December 1998): 399–404.
- [121]Gerald Jay Sussman and Jack Wisdom; *Structure and Interpretation of Classical Mechanics*. Cambridge, MA: MIT Press, 2001/2014.
- [122]Gerald Jay Sussman and Jack Wisdom with Will Farr; *Functional Differential Geometry*. Cambridge, MA: MIT Press, 2013.
- [123]*The TTL Data Book for Design Engineers*, by the Engineering Staff of Texas Instruments Incorporated, Semiconductor Group.
- [124]Alan M. Turing; "On Computable Numbers, with an Application to the Entscheidungsproblem," in *Proceedings of the London Mathematical Society (Series 2)*, 42 (1936): 230– 265.
- [125]David L. Waltz; *Generating Semantic Descriptions From Drawings of Scenes With Shadows*, PhD thesis, MIT, also Artificial Intelligence Laboratory Technical Report 271, November 1972.
- [126]Stephen A. Ward and Robert H. Halstead Jr.; *Computation Structures*. Cambridge, MA: MIT Press, 1990.
- [127]Stephen Webb; *Measuring the Universe: The Cosmological Distance Ladder*, Springer-Praxis Series in Astronomy and Astrophysics. Berlin: Springer, 1999.
- [128]Daniel J. Weitzner, Hal Abelson, Tim Berners-Lee, Chris Hanson, Jim Hendler, Lalana Kagal, Deborah McGuinness, Gerald Jay Sussman, and K. Krasnow Waterman; *Transparent Accountable Data Mining: New Strategies for Privacy Protection*, MIT CSAIL Technical Report MIT-CSAIL-TR-2006- 007, January 2006.
- [129]Robert Edwin Wengert; "A simple automatic derivative evaluation program," in *Communications of the ACM*, 7(8) (1964): 463–464.
- [130]Carter Wiseman; *Louis I. Kahn: Beyond Time and Style: A Life in Architecture*. New York: W.W. Norton, 2007.
- [131]Lewis Wolpert, Rosa Beddington, Thomas Jessell, Peter Lawrence, Elliot Meyerowitz, and Jim Smith; *Principles of Development* (2nd ed.). Oxford: Oxford University Press, 2001.
- [132]Ramin Zabih, David McAllester, and David Chapman; "Nondeterministic Lisp with dependency-directed backtracking," in *AAAI-87*. (1987): 59–64.
# **Index**
Any inaccuracies in this index may be explained by the fact that it has been prepared with the help of a computer.
Donald E. Knuth, *Fundamental Algorithms* (Volume 1 of *The Art of Computer Programming*)
Page numbers for Scheme procedure definitions are in *italics*. Page numbers followed by *n* indicate footnotes.
```
% naming convention, 152
! naming convention, 393 n
λ (lambda) calculus, 1 n
λ expression. See lambda
λ notation, 380 n
π (pi), 381
+->interval, 333
' (quote in Scheme), 390
' (backquote in Scheme), 391
, (comma) in backquote, 391
- (negation or subtraction), 390
```
pattern-directed, 168
```
. in formal parameters, 267 (ex. 5.12), 389
. in printed representation of pair, 387
/ in rational constant, 47
;. See Semicolon
? for pattern variable, 158
? in predicate name, 386 n
?? for segment variable, 159
?* in graph matching, 215
() in Scheme (empty list), 387
(...) in Scheme, 380
# in Scheme vector printout, 388
# in character constant, 40
#!optional parameter, 118
#f (false), 386
#t (true), 386
a:, 274 n
a:advance, 274, 275
a:apply, 274
Abelson, Harold, 114 n, 118 n
Abstract predicate, 134
accumulate, 389
Activation policy for propagator, 347
ACTOR framework message passing, 396 n
add-arithmetics, 77
```
add-cell-content!, *346*
```
add-cell-neighbor!, 346
add-content!, 344
add-streams, 255
add-to-generic-arithmetic!, 91
address-of, 218
address=, 219
advance. See a:advance; g:advance; x:advance
Adventure game, 138–152
inheritance, 140
object properties, 139, 142, 145
Algebra rules, 161–163
segment variables in, 162
Algol-60 thunk, 253 n
Alist (association list), 303
all-args, 74
all-knight-moves, 214
Alternative in conditional, 384
Alternative values, set of, 350
Alternative world views and propagation, 349–351
Alyssa P. Hacker, 44 (ex. 2.7), 277 (ex. 5.17)
amb, 271. See also Backtracking
continuation implementation, 288–292
evaluator implementation, 273–277
order of alternatives, 277, 279
(ex. 5.20), 290–292, 294 (ex. 5.23)
```
### propagation implementation, 355–364
## Amorphous Computing, 10 *n*
analyze, *260*. *See also* x:analyze
analyze-amb, *277*
analyze-application, *260* , 268
(ex. 5.13), *275*
analyze-assignment, *263* , *276*
analyze-begin, *263*
analyze-definition, *264*
analyze-if, *262* , *275*
analyze-lambda, *262*
analyze-quoted, *261*
analyze-self-evaluating, *261*
analyze-undoable-assignment, *276*
analyze-variable, *261*
Anna Logue, 340 (ex. 7.2)
annotate-expr, *196*
Annotation layer, 304
any-arg, 76
any-object?, 91
APL, 87 *n*
Applicability of procedure, 73, 76, 78, 88, 98
application?, *236*
Application of procedures, 235, 244–246
Applicative order, 234, 245
```
apply, 23, 375
in evaluator, 234 (see also a:apply; g:apply; x:apply)
with "extra" argument, 85 (ex. 3.2)
Architecture
parti , 5, 299
of programs, 5–6
Arguments
indefinite number of (see n-ary procedure)
in Scheme, 250, 380
non-strict, 250
strict, 251
Arithmetic. See also Arithmetic package; Combinators: arithmetic
combinators
boolean, 84 (ex. 3.1)
on functions, 80–83
generic (see Generic arithmetic) layered, 309–310
symbolic, 71–73
with units, 310–314
on vectors, 85 (ex. 3.2)
Arithmetic operators modulating, 71–73
Arithmetic package, 71
combining arithmetics, 73–80
Arity. See also n-ary procedure
of function, 23, 27
of operator, 74
procedure-arity, 28
```
```
Armstrong, Edwin, 10 (fig. 1.1)
Aspect-oriented programming, 88 n
assert! in propagator, 336, 349
assert in Scheme, 28
Assignment
! naming convention, 393 n
backtracking and, 276
in evaluator, 243
in Scheme, 392–394
set!, 393
assignment?, 243
assignment-value, 243
assignment-variable, 243
Association list (alist), 303
Astronomy
distances to stars, 329
magnitudes of stars, 336
attach-rule!, 168, 170
Automagically, 10
Automatic differentiation, 103
generic arithmetic handlers for, 107–110
higher-order functions, 119
literal functions, 123
n-ary functions, 111
Newton's method using, 104
```
```
Autonomous agent in game, 139, 140, 144
Avatar in game, 139
Backquote in Scheme, 391
Backtracking, 269–271. See also Exploratory behavior; Generate and
test; Search
amb (see amb)
assignment and, 276
continuations and, 287, 288–289
dependency-directed (see Dependency-directed backtracking)
generate and test, 16
language and, 270–271
rules and, 162, 164
segment variables and, 172
Ballantyne, Michael, 203 n
Bard, Jonathan B. L., 16 n
base-layer, 303
base-layer-value, 305
basic-knight-move, 213
basic-queen-move, 215
Beal, Jacob, 8 n
begin?, 242
begin, in evaluator and Scheme, 242
begin-actions, 242
Belief status of premise, 349
Ben Bitdiddle, 44 (ex. 2.7), 277 (ex. 5.17)
```
```
Bessel, Friedrich Wilhelm, 332
binary-amb, 360
Binary amb, 359–363
Binding, 381 n
of formal parameters, 234, 246
of pattern variables, 170, 172, 175
Biology, ideas from, 8–17
board-addresses, 217
Board game domain model, 53
checkers, 54–55, 59
Body
of let expression, 385
of procedure, 234, 381
Body plan, 9–12
animal, 9
combinators and, 11, 36
domain-specific language, 11
radio receiver, 10
software, 11
Bohlin, R.C., 337
boolean?, 84 (ex. 3.1)
Boolean arithmetic, 84 (ex. 3.1)
Boolean values, 386
Bourne shell, 42
BRE (Basic Regular Expression), 38
```
```
Breadth-first search, 290–292
Brittle software, 1
Bundle, 395–397
bundle, 396
Byrd, Will, 203 n
C, 65, 238
C++ and overloading, 154
c:, 331 (fig. 7.3)
cache-wrapped-dispatch-store, 132
Caching, for generic dispatch, 131
call-with-current-continuation, 282
call-with-values, 31 n
call/cc, 282
Call by need, 245, 251
capture?, 223
car, 387
Carroll, Lewis, 285 n
cdr, 387
Cell (propagation), 342, 343–346
cell-merge, 344
cell-strongest, 346
chaining-generic-procedure, 138
Chapman, David, 358 n
Checkers, 53–64
domain model, 54–55, 59
```
```
Chen, Kenny, 203 n
Chess, 64 (ex. 2.12), 213–224
board as graph, 216
compiling move patterns to matcher procedures, 225–231
knight move patterns, 213, 214
making moves, 221
move patterns on board graph, 213
queen move patterns, 215
Choice, nondeterministic. See amb
Choice propagator, 356–364. See also binary-amb; p:amb
Church, Alonzo, 1 n, 380 n
Circuit, electrical, 340 (ex. 7.2)
Clausal learning, 358 n
Clause in conditional, 383
Clifford, William Klingdon, 106 n
Clinger, William, 277 n
CLOS, 88 n
Code smell, 6 n
Colmerauer, Alain, 271, 370 n
color, 218
Combination in Scheme, 235, 380. See also Procedure: application
of
Combinatorial puzzles, 277 (ex. 5.17), 364–367
Combinator language, 11, 30
Combinators, 11, 22–36
arithmetic combinators, 67–84
```
```
body plans and, 11, 36
function combinators, 23–29 (see also Function combinators)
for pattern matching, 170, 175
problems with, 83, 88
for regular expressions, 38–43
system of, 21, 22
combined-arithmetic, 79
Combining arithmetics, 73–80
Comma in backquote, 391
Common Lisp Object System, 88 n
Compiler optimization, 160, 259, 269 (ex. 5.15)
assignment and, 264
constant folding, 268 (ex. 5.14)
peephole, 168
Compile time, 259
Compiling, 259
for graph patterns, 225–231
formal-parameter declarations, 269 (ex. 5.16)
for pattern matching, 176–179
to execution procedures, 259–267, 273–277 (see also
analyze-...)
to propagator networks, 337 n, 340 (ex. 7.1), 367 (ex. 7.6)
to regular expressions, 39–43
complement, 203 n, 309 n
compose, 23 , 24 (fig. 2.1), 32 , 382
compound-propagator, 347
```
```
Compound data in Scheme, 386–389
cond
in evaluator, 241
in Scheme, 383
cond?, 241
cond-clause-consequent, 241
cond-clause-predicate, 241
cond-clauses, 241
cond->if, 241
Conditionals
in evaluator, 238
in Scheme, 383–384
conjoin, 309 n
connect!, 212
connect-up-square, 219
cons, 387
g:cons (graph version), 210
Consequent in conditional, 383, 384
Consequent of rule, 161
constant-union, 77
Constant folding, 268 (ex. 5.14)
Constraint propagator (c:), 330, 331 (fig. 7.3)
Constructors in Scheme, 386
Continuation-passing style, 280–281
for amb, 273
```
```
in matcher, 170
in rule system, 164
in unifier, 186
Continuations in Scheme, 280–287
backtracking and, 287, 288–289
call/cc, 282
call-with-current-continuation, 282
nonlocal exits, 284–285
nonlocal transfer of control, 285–287
underlying, 281–287
Contradiction object for
propagation, 345
Correctness vs. flexibility, 18
Curry, Haskell, 34
curry-argument, 34 , 34 (fig. 2.6)
Currying, 34
for multiple arguments, 138 n
partial derivatives and, 113 (ex.
3.8)
Cy D. Fect, 277 (ex. 5.17)
Data
layered, 302–305
restrictions on use of, 324
tagged, 134, 155
Data-purpose algebra, 325
```
```
Debugging, 24 n, 260, 268 (ex. 5.13). See also Paranoid
programming
dependencies for, 315, 322, 329
numerical code, 71, 96, 100
Declarations
compiling, 269 (ex. 5.16)
constants, 268 (ex. 5.14)
on formal parameters, 233, 250
inferred type, 195
layering for, 6, 299, 321 (ex. 6.4)
lazy and lazy memo formal parameters, 253
optional parameter, 258 (ex. 5.11)
record type, 388
relationships between predicates, 135, 155
rest parameter, 258 (ex. 5.11)
restrictions on formal parameters, 257 (ex. 5.10)
restrictions on pattern variables, 163
default-object, 75 n
default-object?, 75 n
define
'.' for rest parameters, 267 (ex. 5.12), 389
in evaluator, 244
in Scheme, 381
define-c:prop, 348
define-clock-handler, 145
define-generic-procedure-handler, 89, 99
```
```
define-layered-procedure-handler, 353
definition?, 244
definition-value, 244
definition-variable, 244
Definitions in Scheme, 381–383. See also Internal definitions in
Scheme
Degeneracy, 4, 12–14
in biological systems, 12
in engineered systems, 14
evolution and, 13
of genetic code, 12
partial information and, 14
physics and, 13
propagation and, 369
redundancy vs., 12 n
deKleer, Johan, 358 n
delay, 211
Delegate procedure in bundle, 396
Delegation, 128
del Pino, E. M., 16 n
Dependency-directed
backtracking, 315, 324, 358–364, 370. See also amb: propagation
implementation combinatorial puzzles, 364–367
Depth-first search, 277, 290–292
derivative, 107
Derived expression types, 240–242
```
```
Diamond, ball of mud vs., 87
Dictionary, 166, 170, 175
Differential equations, integrating, 68–70, 256 (ex. 5.8)
Differential object, 105
Differentiation, automatic. See Automatic differentiation
Direction
on checkerboard, 55
on chessboard, 213
Directional propagator (p:), 331, 332 (fig. 7.4)
discard-argument, 33 , 33 (fig.
2.5)
disjoin*, 77 n
Dispatch. See Generic dispatch; Pattern-directed invocation
Dispatch key, 131, 136
Dispatch store, 90, 98, 125, 128, 131, 136–138
Distances to stars, 329
Domain model for board game, 53
checkers, 54–55, 59
Domain predicate, 74
Dotted-tail notation, 389
Doyle, Jon, 358 n
Driver loop (read-eval-print loop), 246
Dual numbers, 106 n
Dynamic binding in Scheme, 394–395
e, as integral, 257 (ex. 5.8)
```
```
Edge, of graph, 209, 211
edge-value, 212
Effects. See also Assignment
in evaluator, 242–243
in Scheme, 392–394
Efficiency vs. flexibility, 17
Electrical circuit, 340 (ex. 7.2)
Element variable, 171
Elinson, R. P., 16 n
else in cond, 383
else-clause?, 241
Emacs, 1 n
Empty list, 387
Engineering
degeneracy and, 14
half-full glass, 18
redundancy and, 14
Environment, in evaluation, 234, 245
lexical scoping, 239, 246
procedure application, 234
Environment, in pattern matching. See Dictionary
eq?, 390
ERE (Extended Regular Expression), 38, 46 (ex. 2.10)
Ernst, M. D., 88 n
eval, 234, 375. See also g:eval; x:eval
```
```
Evaluation of expressions, 235–244
lambda expressions, 239
applications, 235
assignments, 243
conditionals, 238
definitions, 243
derived expressions, 240–242
quotations, 237
self-evaluating expressions, 236
sequences, 242
variables, 238
Eva Lu Ator, 44 (ex. 2.7), 277 (ex. 5.17), 294 (ex. 5.23)
Evaluator, 12. See also Evaluation of expressions; Interpreter
evolver, 70
Exclamation point in name, 393 n
execute-strict, 275
Exploratory behavior, 14–17, 269–271. See also Backtracking;
Generate and test; Search
Expressions in Scheme, 379
extend-arithmetic, 78
extend-generic-arithmetic!, 93
extract-dx-part, 110
factorial, 384 , 385
pattern-directed, 168
Fibonacci numbers, 129, 255
finite-part, 118
```
```
Finite part of differential object, 106
First-class object, 282, 382
Flexibility
additivity, 2
body plan, 9
brittleness vs., 1
combinators (see Combinators)
combinators vs., 83
correctness vs., 18
degeneracy, 4, 12, 370, 371
diamond vs. ball of mud, 87
efficiency vs., 17
exploratory behavior, 14, 329
generic procedures, 67
layered system, 4, 299, 356
mix-and-match parts, 3, 22, 170, 232
pattern-directed invocation (see Pattern-directed invocation)
Postel's law, 3, 19 n
program architecture, 5
propagator network, 328
redundancy, 12, 371
rule system, 157
flip-coin, 144
Floyd, Bob, 271
Fluid variable. See Parameter
```
```
Forbus, Ken, 358 n
force, 211
Formal parameters of procedure, 234, 381
declarations, 233, 250
lazy and lazy memo declarations, 253
lazy arguments, 251
optional argument, 118, 258
(ex. 5.11)
rest arguments, 248 n, 258 (ex. 5.11), 267 (ex. 5.12), 389–390
restriction declarations, 257 (ex. 5.10)
Franklin, Benjamin, 183
Fredkin, Edward, 125 n
Freuder, Eugene, 332 n
Friedman, Daniel P., 254 n
Fully supported, 349
function-extender, 82
Functional programming, 394 n
Function arithmetic, 80–83
Function combinators, 23–29
compose, 23
curry-argument, 34
discard-argument, 33
parallel-combine, 25
permute-arguments, 35
spread-combine, 26
```
```
g:, 236 n
g:advance, 236
handlers, 254
g:apply, 245
handlers, 245–246
g:eval, 235
handlers, 235–244
Scheme primitives and, 238 n
g:handle-operand, 252
Games. See Adventure game; Checkers; Chess Gatewood, George D.,
334 n
Generate and test, 14–17, 288, 292. See also Backtracking;
Exploratory behavior; Search
backtracking, 16
in biology, 14
in evolution, 16
generic-move!, 146
generic-procedure-constructor, 90, 97
generic-procedure-dispatch, 100 , 125
generic-symbolic, 309
generic-with-layers, 309
Generic arithmetic, 90–96
automatic differentiation handlers, 107–110
problems with, 94
Generic dispatch, 4, 99. See also Dispatch store
caching for, 131
```
```
chaining handlers, 137
most specific handler, 136
pattern matching vs., 157
resolution policy, 98, 130, 136
rules for, 88
trie data structure for, 125–130
Generic procedures extensible, 87–101
flexibility, 67
implementation, 97–100
object-oriented programming and, 4, 88 n, 138–152
Gerhart, John C., 9 n, 14 n
get-arity, 28
get-handler, 98
get-hunger, 143
Gilliland, R.L., 337
giuoco-piano-opening, 223
gmatch:compile-path, 226
gmatch:compile-target, 228
gmatch:compile-var, 230
Gödel, Kurt, 1 n
Golden ratio, 256
Gossip propagation, 354 (ex. 7.4)
Graph
alternate views, 216
chessboard as, 216
```
```
implementation of, 211–212
lazy, 211
list as, 210
pattern matching on, 209–231
propagation and, 342 (ex. 7.3)
graph-match, 225
graph-node-view, 216
Graph edge, 209, 211
Graph node, 209, 211
grep, 42
guarantee, 151 n
guarantee-list-of, 151 n
handle-cell-contradiction, 363
handle-operand. See g:handle-operand; x:handle-operand
Handler
applicability of, 73, 98
choosing efficiently, 125
for arithmetic operation, 71
for generic procedure, 88
for layered procedure, 306
term-rewriting rule consequent, 165
has-edge?, 212
Hash table, 29 n
for memoization, 132
for sticky note, 29, 254
```
```
Haskell, 22 n, 251
currying, 138 n
overloading, 154
type system, xvi Herbrand, Jacques, 1 n
Hewitt, Carl E., 170 n, 271, 370 n
Hewitt, Edwin, 106 n
Hipparchus, 336 n
Hipparcos satellite, 335, 335 n, 336 n
Hox complex (genes), 9
Hubble space telescope, 337
Hygienic macro, 167, 240 n
Hyperreal numbers, 106 n
Hypothetical premise, 356, 359–364
IDE (Integrated Development Environment), 321 (ex. 6.4)
if
in evaluator, 239
in Scheme, 384
if?, 239
if-alternative, 239
if-consequent, 239
if-predicate, 239
Improper list, 248 n
in (believed), 349
Indentation in Scheme, 382 n
Index
```
```
of this book, 409
trie, 125
zero-based, 388
infer-program-types, 194, 196
infinitesimal-part, 118
Infinitesimal part of differential object, 106
Infix notation, 250 (ex. 5.7)
Inheritance
delegation vs., 128
object-oriented programming, 140
inquire in propagator, 334
install-arithmetic!, 72
Integrated Development Environment (IDE), 321 (ex. 6.4)
Integrating differential equations, 68–70, 256 (ex. 5.8)
Internal definitions in Scheme, 24, 383, 385
Interpreter, 233–254
Intervals
in measurements, 332–336
merging, 352
invert-address, 219
iota, 112 n
Iteration in Scheme, 385
Java, 1 n, 6, 22 n
chaining, 146
combinators, 65
```
```
interfaces, 6 n
Jonge, Joost Kiewiet de, 334 n
Justification, annotation of, 322
Kahn, Louis Isadore, 5
Kanizsa, Gaetano, 328
Kanizsa's triangle illusion, 328, 328 (fig. 7.1)
Kirschner, Marc W., 9 n, 14 n
Knuth, Donald E., 409
Kowalski, Robert M., 271
Kutsia, Temur, 203 n
lambda
'.' or symbol for rest parameters, 248 n, 267 (ex. 5.12), 389
in evaluator, 239
in Scheme, 380
lambda (λ) calculus, 1 n
lambda?, 239
lambda-body, 239
lambda-parameters, 239
layer-accessor, 305
layered-datum, 303
layered-extender, 310
Layered arithmetic, 309–310
Layered data, 302–305
```
Layered procedure, 301, 305–309, 352
```
Layering, 4, 299. See also Architecture: of programs
declarations, 299, 321 (ex. 6.4)
program architecture, 5
Layers
annotation layer, 304
base layer, 303
justification layer, 322
support layer, 317
units layer, 304
Lazy arguments, 251. See also Postponed evaluation
lazy and lazy memo declarations, 253
Lazy graph, 211
Lazy list (stream), 211, 254–256
integration using, 256 (ex. 5.8)
Lem E. Tweakit, 277 (ex. 5.17)
let
in evaluator, 241
in Scheme, 384
let?, 242
let*, 385
let-body, 242
let-bound-values, 242
let-bound-variables, 242
let-cells, 330
let->combination, 242
```
```
let-values, 31 n
Lexical scoping, 239, 245, 246, 382
Lieberherr, Karl, 358 n
Lisp, xvi, 235, 387 n
Perlis quip, 17
list, 386
list?, 386
list->graph, 211
list->lazy-graph, 211
list-ref, 388
list-set!, 393
Lists
as graphs, 210
improper, 248 n
in pattern matching, 158
in Scheme, 386–389, 393
lazy (streams), 211, 254–256, 256 (ex. 5.8)
printing, 72 n
literal-function, 83
Literal symbol in Scheme, 390–391
Local names in Scheme, 384–385
Local state, 393
object-oriented programming and, 138
Logic puzzles. See Combinatorial puzzles
lookup-variable-value, 238
```
```
Loops in Scheme, 385
Louis Reasoner, 44 (ex. 2.7), 277 (ex. 5.17)
lset library, 320
Macro, 240 n, 264
hygienic, 167
syntactic closure, 167
syntax rules, 288, 295 (ex. 5.25)
Magnitudes of stars, 336
make-annotation-layer, 304
make-arithmetic, 74
make-begin, 242
make-cached-chaining-dispatch-store, 138
make-cached-most-specific-dispatch-store, 138
make-cell, 344
make-chaining-dispatch-store, 137
make-chess-board, 217
make-chess-board-internal, 218
make-generic-arithmetic, 90
make-graph-edge, 212
make-graph-node, 212
make-if, 239
make-infinitesimal, 116
make-lambda, 240
make-layered-datum, 303
make-layered-procedure, 306
```
```
make-most-specific-dispatch-store, 137
make-operation, 74
make-parameter, 395
make-pattern-operator, 169
make-property, 142, 150, 151
make-rule, 166
make-simple-dispatch-store, 90, 98
make-type, 142, 150, 152
Manzyuk, Oleksandr, 121 n
map, 249 (ex. 5.5)
match-args, 108
match:bindings, 175
match:compile-pattern, 179
match:dict-substitution, 186
match:element, 171, 180
match:element-var?, 178
match:eqv, 171
match:extend-dict, 176
match:list, 174
match:lookup, 176
match:new-dict, 175
match:segment, 173
match:segment-var?, 178
match:var?, 178
```
Matcher. *See* Match procedure Match procedure, 166, 170
```
Matrix arithmetic, 102 (ex. 3.6), 103 (ex. 3.7)
Maximal factor, 117
maybe-grab-segment, 205
maybe-set!, 276, 295 (ex. 5.25)
maybe-substitute, 191
Mayer, Meinhard E., 114 n
McAllester, David, 358 n
McCarthy, John, 271, 277 n
MDL, 249 (ex. 5.6)
Memoization
hash table for, 132
lazy evaluation and, 251 n
merge, 351
merge-intervals, 352
merge-value-sets, 353
Message-accepting procedure, 396
Metaobject Protocol, 88 n
Method. See Handler; Message-accepting procedure
MIT/GNU Scheme, 379
Mitros, Piotr, 11 n
Mix-and-match parts, 3, 7 n, 22. See also Combinators
Moses, Joel, 87 n
most-specific-generic-procedure, 138
Mud, ball of, 87
Multiple values in Scheme, 30–32
```
```
n:, 69 n
Naming conventions
! for assignment, 393 n
? for predicate, 386 n
%, 152
narrate!, 144
n-ary procedure (indefinite number of arguments), 29, 72 n, 248
(ex. 5.2), 258 (ex. 5.11), 267 (ex. 5.12), 389–390
Neighbor in propagator, 342
Nested definition in Scheme. See Internal definitions in Scheme
.net, 1 n
Newton's method, 104
next-turn, 219
Node, of graph, 209, 211
node-at, 218
Nogood set, 358
Nondeterministic choice. See amb
Non-strict argument, 250. See also Postponed evaluation
Non-strict procedure, 250
Normal order, 236, 245
nothing?, 343
null?, 387
number?, 237
*number-of-calls-to-fail*, 289
Numbers in Scheme, 237
```
Numeral, 379. *See also* Rational constant
```
numeric-arithmetic, 75
Numerical integration, 68–70, 256 (ex. 5.8)
Object-oriented programming generic procedures and, 4, 88 n, 138–
152
inheritance, 140
local state and, 138
modeling with, 138
ODE integrator, 68–70
Offset on checkerboard, 55
operands, 236
Operands of combination, 234, 380
order of evaluation, 246
operation-applicability, 74
operation-union, 78
operation-union-dispatch, 78
operator, 236
Operator of combination, 234, 380
Optical illusion, 328, 328 (fig.
7.1)
Optional argument, 118
optional declarations, 258 (ex. 5.11)
out (not believed), 349
Overloading, 71–73, 154
override-rule!, 170
```
```
p:, 332 (fig. 7.4)
p:amb, 357, 363, 364
pair?, 387
Pairs in Scheme, 387, 393
parallel-combine, 25 (fig. 2.2), 26
Parameter (fluid variable), 395
Parameter (of procedure). See Formal parameters of procedure
parameterize, 395
Parametric types, 202 (ex. 4.15)
Paranoid programming, 28, 65, 321 (ex. 6.3)
Parentheses in Scheme, 380, 387
Parti , 5, 299
partial (derivative), 111
Partial information, 4, 130, 157
degeneracy and, 14
propagation, 344
type inference, 193–201
unification, 183, 185
Pattern, 157
partial information, 157, 183
rules and, 157, 160
Pattern-directed invocation, 158, 168–170, 370 n
- (negation or subtraction), 168
factorial, 168
Pattern matching, 157. See also Pattern-directed invocation;
Unification
```
```
combinators for, 170, 175
equality testing vs., 157, 183
generic dispatch vs., 157
on graphs, 209–231
on lists, 158
term rewriting, 160–167
Pattern variable, 157, 158. See also Segment variable
in graph matching, 213, 215
restrictions, 163
Perlis, Alan J., 17, 150, 159
Perlmutter, Barak A., 121 n
permute-arguments, 35 (fig. 2.7), 36
Perturbational programming, 323
π (pi), 381
piece-at, 221
piece-in, 221
PLANNER
backtracking, 271
pattern-directed invocation, 370 n
populate-sides, 220
possible-directions, 55
Postel, Jonathan Bruce, 3
Postel's law, 3, 19 n
Postponed evaluation, 236. See also delay; force; Stream
compound propagator, 347
```
```
lazy graph, 211
non-strict arguments, 253–254, 266
pp (pretty-print), 72 n
predicate?, 133
predicate-constructor, 135
Predicate as type, 132–138
for argument checking, 151 n
as dispatch key, 136
for formal parameter, 257 (ex. 5.10)
in pattern variable, 162, 179
Predicate in conditional, 383, 384
Predicates, 386 n. See also Predicate as type
? naming convention, 386 n
abstract predicate, 134
domain predicate, 74
for procedure applicability, 73, 98
registration of, 133
relationships between, 135, 155
Premise, 315
belief status, 349
hypothetical, 356, 359–364
premise-nogoods, 359
Pretty-print (pp), 72 n
Prime number test, 134
primitive-propagator, 347
```
```
Primitive procedure, 245
print-all-results, 173
Printing list structure, 72 n
Procedure
application of, 235, 244–246
lambda expression for, 380 (see also lambda)
layered, 301, 305–309, 352
match procedure, 166, 170
message-accepting, 396
with multiple values, 30–32
n-ary (see n-ary procedure)
with non-strict arguments, 250–256
non-strict, 250
primitive, 245
strict, 245, 250
variadic (see n-ary procedure)
with indefinite number of arguments (see n-ary procedure)
procedure-parameter-name, 252
program-constraints, 199
Programming
additive, 1–5
architecture of, 5–6
layered, 299
Prolog
backtracking, 271
```
```
occurs check, 191 n
pattern-directed invocation, 370 n
segment variables, 203 n
Propagation
activation policy, 347
alternative world views, 349–351
amb, 355–364
astronomy example, 329–340
cell, 342, 343–346
circuit example, 340 (ex. 7.2)
degeneracy and, 369
graph example, 342 (ex. 7.3)
mechanism, 342–349
merging values, 351–354
model of computation, 327–329
neighbor, 342
partial information, 344
propagator, 342, 346–349 (see also Propagator)
scheduler, 342, 343
searching alternatives, 355–364
type inference, 368 (ex. 7.8)
unification and, 354 (ex. 7.4)
wiring diagram vs. expression, 327, 331 (fig. 7.3), 337 n, 340 (ex.
7.1), 367 (ex. 7.6), 369
Propagator, 342, 346–349
choice propagator (see Choice propagator)
```
```
constraint propagator (c:), 330, 331 (fig. 7.3)
directional propagator (p:), 331, 332 (fig. 7.4)
input and output cells, 343
propagator, 346
property-getter, 145
Property list, 303
Provenance, 299, 315, 322, 328, 333
Puzzles (combinatorial), 277 (ex. 5.17), 364–367
Pythagorean triples, 272, 293 (ex. 5.22), 357
Python, 6, 14 n
generic arithmetic, 87
Quasiquotation in Scheme, 391
Question mark. See ?
Quotation
in evaluator, 237
in Scheme, 390–391
quote, 237
quoted?, 237
Radio receiver, 10
Radul, Alexey Andreyevich, 121 n, 344 n, 358 n, 370
random-bias, 143
random-choice, 143
random-number, 144
Randomness. See flip-coin; random-...
```
```
Rational constant, 47, 379
Read-eval-print loop (repl), 246
Records in Scheme, 151, 386–389, 394
record type declaration, 388
Recursive procedures, 384
reduce-right, 263
Redundancy, 12–14, 130
in biological systems, 12
degeneracy vs., 12 n
in engineered systems, 14
ref-stream, 255
Referee for game, 53, 210
Registration of predicate, 133
Regular expressions, 37–38
combinator implementation, 38–43
Relationships between predicates, 135, 155
repl, 246
require, 272, 292
Resolution policy for generic dispatch, 98, 130, 136
Rest parameter, 248 n, 267 (ex. 5.12), 390
rest declarations, 258 (ex. 5.11)
restrict-arity, 28
Restrictions
on formal parameters, 257 (ex. 5.10)
on pattern variables, 163
```
```
restrict-to declarations, 258
(ex. 5.10)
result-receiver, 170
retract! in propagator, 335, 349
Returning multiple values in Scheme, 30–32
Robinson, John Alan, 183
rotate-180-view, 216
Roussel, Phillipe, 271
Ruby and continuations, 282
rule, 167
rule-simplifier, 161, 165
Rules
algebra, 161–163
backtracking and, 162, 164
for generic procedure dispatch, 88
patterns and, 157, 160
Run time, 259
Russell, Jane L., 334
Sandewall, Erik, 271 n
Satellite, Hipparcos, 335, 335 n, 336 n
SAT solver, 358 n, 368
say!, 148
Scheduler for propagation, 342, 343
Scheme, xvi, 244, 379–395
MIT/GNU Scheme, 379
```
```
Schönfinkel, Moses, 34 n
scmutils, 101
Scope, 381 n. See also Lexical scoping
Search, 355–356. See also amb; Backtracking; Exploratory behavior;
Generate and test
depth-first and breadth-first, 277, 290–292
Segment variable, 159. See also Pattern variable
in algebra rules, 162
backtracking and, 172
unification and, 203–208
Selectors in Scheme, 386
self-evaluating?, 237
Semicolon (;). See also Syntactic sugar
comment introduced by, 390
Sensitivity analysis, 323
sequence->begin, 240
set!
in evaluator, 243
in Scheme, 393
set-car!, 393
set-cdr!, 393
set-piece-at, 221
set-predicate<=!, 136
setup-propagator-system, 366
SI (International System of Units), 314 (ex. 6.1)
SICP, 379
```
```
inhabitants, 44 (ex. 2.7), 277 (ex. 5.17), 294 (ex. 5.23)
simple-abstract-predicate, 134
simple-generic-procedure, 89, 89 , 97
simple-move, 222
simple-operation, 74
Simplification, algebraic, 161–163
Siskind, Jeffrey Mark, 121 n
Smalltalk
continuations, 282
currying, 138 n
message passing, 396 n
Smith, Brian Cantwell, 237 n
SML and continuations, 282
Snark hunt, 285 (ex. 5.21)
Software support for book, 377
SOS, 88 n
Special form, 235, 380
implemented by macro, 264
in evaluator, 237–244
spread-apply, 32
spread-combine, 27 (fig. 2.3), 28 , 31 , 31 (fig. 2.4)
square, 381
Stallman, Richard Matthew, 332 n, 358 n
Standards, 46 (ex. 2.10)
Stars
```
```
distances to, 329
magnitudes of, 336
start-chess-game, 220
Steele, Guy Lewis Jr., 30 n, 332 n, 358 n
Sticky note
hash table for, 29, 254
for metadata, 169
stormer-2, 69
Stormer's integrator, 68
Stream (lazy list), 211, 254–256
integration using, 256 (ex. 5.8)
Strict argument, 251
Strict procedure, 245, 250
strongest-consequence, 351
strongest-value, 350
Struve, Friedrich G. W. von, 332
Suppes, Patrick, 322 n
support-layer, 318
support-layer-value, 318
support-set abstraction (...support-set...), 319
Support for datum, 316
Support layer, 317
Support set, 315
Sussman, Gerald Jay, 106 n, 114 n, 332 n, 358 n, 370
Symbol, in Scheme, 238 n, 390–391
```
```
symbolic-extender, 76
Symbolic arithmetic, 71–73
symmetrize-move, 214
Syntactic sugar, 159, 315 (ex. 6.1)
define as, 382
derived expression types, 240–242
Syntax. See Combination; Macro; Special form; Syntactic
sugar
Tag, for predicate, 131, 133, 136
tagged-list?, 238
Tagged data, 134, 155
take-thing, 147
Tannenbaum, Andrew S., 46 (ex. 2.10)
tell! in adventure game, 147
tell! in propagator, 333
Term rewriting, 160–167
for algebraic simplification, 161–163
for compiler optimization, 160, 168
equational theories, 160
pattern matching, 160–167
test-content!, 344 , 345
text-of-quotation, 237
the-contradiction, 345
the-nothing, 343, 344
the-unspecified-value, 239
```
```
Thunk, 253 n
tinyCLOS, 88 n
Trie data structure, for generic dispatch, 125–130
Troll, 139, 142–144
Truth-maintenance system, 358 n
try-rules, 165
TTL mix-and-match parts, 7 n
Turing, Alan, 1 n
Turn in chess
labeling edge to piece, 220, 221
next-turn, 219
turn state variable, 218
type-instantiator, 142, 150, 152
type-properties, 152
Typed expression, 194
Type inference, 193–201
inferred declaration, 195
propagation for, 368 (ex. 7.8)
unification for, 196, 200
Types. See also Predicate as type in adventure game, 142–145, 150–
152
parametric, 202 (ex. 4.15)
union, 202 (ex. 4.16)
user-defined, 132–138
Unbound variable, 238, 247 (ex. 5.1)
```
```
Unification, 157, 183–184
as equation solving, 185
partial information and, 183, 185
propagation and, 354 (ex. 7.4)
segment variables and, 203–208
substitution instance, 183
type inference and, 193–201
unifier, 183
unifier, 186
unify, 186
unify-constraints, 200
unify:internal, 187
Union types, 202 (ex. 4.16)
unit, 311
unit-arithmetic, 312
unit-layer, 304
Units (of measurement), 47–48
arithmetic with, 310–314
base vs. derived units, 310 n
SI (International System of Units), 314 (ex. 6.1)
units layer, 304
wrappers for, 49–52
UNIX and streams, 297
User-defined types, 132–138
```
```
Value set, 350
merging, 353
Variable, 381. See also Pattern variable; Segment variable
in evaluator, 238
variable?, 238
Variadic procedure. See n-ary procedure
vector, 388
vector?, 388
vector-ref, 388
vector-set!, 393
Vector arithmetic, 85 (ex. 3.2), 102 (ex. 3.6), 103 (ex. 3.7)
Vectors and covectors, 112, 113 (ex. 3.10)
Vectors in Scheme, 386–389, 393
Vectors of procedures, 248 (ex. 5.3)
Waltz, David L., 332 n
Waltz algorithm, 342 (ex. 7.3)
Warren, David, 271
Website for book software, 377
Wengert, Robert Edwin, 103 n
white-move?, 218
Whitespace in Scheme, 382 n
Wilde, Oscar (Perlis's paraphrase of), 17
Wiring diagram. See Propagation: wiring diagram
Wisdom, Jack, 104 n, 114 n
Wise, David S., 254 n
```
```
with-breadth-first-schedule, 290
with-depth-first-schedule, 290
Wrappers, 46–52
specializers, 49
units of measurement and, 49–52
write-line, 392 n
x:, 260 n
x:advance, 261
handlers, 267
x:analyze, 260
handlers, 261–264
```
x:apply, *265* handlers, 265–266 x:eval, *259* x:handle-operand, *266*
Zabih, Ramin, 358 *n* Zero-based indexing, 388 Zuras, Dan, 106 *n*
# **List of Exercises**
| 2.1 | 2.4 | 2.7 | 2.10 | 2.13 |
|-----|------|------|------|------|
| 29 | 36 | 44 | 46 | 64 |
| 2.2 | 2.5 | 2.8 | 2.11 | 2.14 |
| 29 | 37 | 45 | 52 | 64 |
| 2.3 | 2.6 | 2.9 | 2.12 | |
| 32 | 43 | 46 | 64 | |
| | | | | |
| 3.1 | 3.6 | 3.11 | 3.16 | 3.21 |
| 84 | 102 | 123 | 153 | 153 |
| 3.2 | 3.7 | 3.12 | 3.17 | 3.22 |
| 85 | 103 | 124 | 153 | 154 |
| 3.3 | 3.8 | 3.13 | 3.18 | |
| 86 | 113 | 129 | 153 | |
| 3.4 | 3.9 | 3.14 | 3.19 | |
| 101 | 113 | 130 | 153 | |
| 3.5 | 3.10 | 3.15 | 3.20 | |
| 101 | 113 | 132 | 153 | |
| | | | | |
| 4.1 | 4.6 | 4.11 | 4.16 | 4.21 |
| 162 | 180 | 193 | 202 | 209 |
| 4.2 | 4.7 | 4.12 | 4.17 | 4.22 |
| 163 | 181 | 193 | 202 | 213 |
| 4.3 | 4.8 | 4.13 | 4.18 | 4.23 |
| 164 | 182 | 193 | 202 | 216 |
| 4.4 | 4.9 | 4.14 | 4.19 | 4.24 |
| 164 | 182 | 201 | 208 | 225 |
| 4.5 | 4.10 | 4.15 | 4.20 | 4.25 |
| 179 | 193 | 202 | 209 | 231 |
| | | | | |
| 5.1 | 5.7 | 5.13 | 5.19 | 5.25 |
| 247 | 250 | 268 | 278 | 295 |
| 5.2 | 5.8 | 5.14 | 5.20 | 5.26 |
| 248 | 256 | 268 | 279 | 295 |
| 5.3 | 5.9 | 5.15 | 5.21 | |
| 248 | 257 | 269 | 285 | |
| 5.4 | 5.10 | 5.16 | 5.22 | |
| 249 | 257 | 269 | 293 | |
| 5.5 | 5.11 | 5.17 | 5.23 | |
| 249 | 258 | 277 | 294 | |
| 5.6 | 5.12 | 5.18 | 5.24 | |
| 249 | 267 | 278 | 294 | |
| | | | | |
| 6.1 | 6.2 | 6.3 | 6.4 | 6.5 |
| 314 | 320 | 321 | 321 | 323 |
| | | | | |
| 7.1 | 7.3 | 7.5 | 7.7 | |
| 340 | 342 | 367 | 368 | |
| 7.2 | 7.4 | 7.6 | 7.8 | |
| 340 | 354 | 367 | 368 | |