Абельсон Х., Сассман Д.Д. Структура и интерпретация компьютерных программ
Подождите немного. Документ загружается.
Литература
561
Havender, J. 1968. Avoiding deadlocks in multi-tasking systems. IBM Syst ems Journal
7(2):74–84.
Hearn, Anthony C. 1969. Standard Lisp. Technical report AIM-90, Artificial Intelligence
Project, Stanford University.
Henderson, Peter. 1980. Functional Programming: Application and Implementation.
Englewood Cliffs, N.J.: Prentice-Hall. (Русский перевод: П. Хендерсон. Функционально е
программирован ие. – М.: Мир, 1983.)
Henderson. Peter. 1982. Functional Geometry. In Conference Record of the 1982 ACM
Symposium on Lisp and Functional Programming, pp. 179-187.
Hewitt, Carl E. 1969. PLANNER: A language for proving theorems in robots. In
Proceedings of the International Joint Conference on Artificial Intelligence, pp. 295–301.
Hewitt, Carl E. 1977. Viewing control structures as patterns of passing messages. Jo urnal
of Artificial Intelligence 8(3):323–364.
Hoare, C. A. R. 1972. Proof of correctness of data representations. Acta Informatica 1(1).
Hodge s, Andrew. 1983. Alan Turing: The Enigma. New York: Simon and Schuster.
Hofstadter, Douglas R. 1979. G
¨
odel, Escher, Bach: An Eternal Golden Braid. New York:
Basic Books. (Русский перевод: Хофштадтер Д. Гёдель, Эшер, Бах: эта бесконечная
гирлянда. – Самара: Бахрах, 2001.)
Hughes, R. J. M. 1990. Why functional programming matters. In Research Topics in
Functional Programming, edited by David Turner. Reading, MA: Addison-Wesley, pp. 17–
42.
IEEE Std 1178-1990. 1990. IEEE Standard for the Scheme Programming Language.
Ingerman, Peter, Edgar Irons, Kirk Sattley, and Wallace Feurzeig; assisted by M. Lind,
Herbert Kanner, and Robert Floyd. 1960. THUNKS: A way of compiling procedure
statements, with some comments on procedure declarations. Неопубликованная рукопись.
(А также частное сообщение от Уоллеса Ферцейга.)
Kaldewaij, Anne. 1990. Programming: The Derivation of Algorithms . New York: Prentice-
Hall.
Kohlbecker, Eugene Edmund, Jr. 1986. Syntactic extensions in the programming language
Lisp. Ph.D. thesis, Indiana University.
Konopasek, Milos, and Sundaresan Jayaraman. 1984. The TK!Solver Book: A Guide
to Problem-Solving in Science, Enginee ring, Business, and Education. Berkeley, CA:
Osborne/McGraw-Hill.
Knuth, Donald E. 1973. Fundamental Algorithms. Volume 1 of The Art of Computer
Programming. 2nd edition. Reading, MA: Addison-Wesley. (Русский перевод: Кнут Д. Ис-
562
Литература
кусство программирования для ЭВМ. Т. 1.: Основные алгоритмы. – СПб.: Вильямс,
2000.)
Knuth, Donald E. 1981. Seminumerical Algorithms. Volume 2 of The Art of Computer
Programming. 2nd edition. Reading, MA: Addison-Wesley. (Русский перевод: Кнут Д. Ис-
кусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. – СПб.: Вильямс,
2000.)
Kowalski, Robert. 1973. Predicate logic as a programming language. Technical report
70, Department of Computational Logic, School of Artificial Intelligence, University of
Edinburgh.
Kowalski, Robert. 1979. Logic for Problem Solving. New York: North-Holland. (Русский
перевод: Ковальски Р. Логика в решении проблем. – М.: Наука, 1990.)
Lamport, Leslie. 1978. Time, clocks, and the ordering of events in a distributed system.
Communications of the ACM 21(7):558–565.
Lampson, Butler, J. J. Horning, R. London, J. G. Mitchell, and G. K. Popek. 1981. Report
on the programming language Euclid. Technical report, Computer Systems Research Group,
University of Toronto.
Landin, Peter. 1965. A correspondence between Algol 60 and Church’s lambda notation: Part
I. Communications of the ACM 8(2):89–101.
Lieberman, Henry, and Carl E. Hewitt. 1983. A real-time garbage collector based on the
lifetimes of objects. Communications of the ACM 26(6):419–429.
Liskov, Barbara H., and Stephen N. Zilles. 1975. Specification techniques for data
abstractions. IEEE Tran s actions on Software Engineering 1(1):7–19.
McAllester, David Allen. 1978. A three-valued truth-maintenance system. Memo 473, MIT
Artificial Intelligence L aboratory.
McAllester, David Allen. 1980. An outlook on truth maintenance. Memo 551, MIT Artificial
Intelligence Laboratory.
McCarthy, John. 1960. Recursive functions of symbolic expressions and their computation
by machine. Communications of the ACM 3(4):184–195.
McCarthy, John. 1967. A basis for a mathematical theory of computation. In Computer
Programing and Formal Systems, edited by P. Braffort and D. Hirschberg. North-Holland.
McCarthy, John. 1978. The history of Lisp. In Proceedings of the ACM SIGPLAN
Conference on the History of Programming Languages.
McCarthy, John, P. W. Abrahams, D. J . Edwards, T. P. Hart, and M . I. Levin. 1965. Lisp
1.5 Programmer’s Manual. 2nd edition. Cambridge, MA: MIT Press.
McDermott, Drew, and Gerald Jay Sussman. 1972. Conniver re ference manual. Memo 259,
Литература
563
MIT Artific ial Intelligence Laboratory.
Miller, Gary L. 1976. Riemann’s Hypothesis and tests for primality. Journal of Computer
and System Sciences 13(3):300–317.
Miller, James S., and Guillermo J. Rozas. 1994. Garbage collection is fast, but a stack is
faster. Memo 1462, MIT Artificial Intelligence Laboratory.
Moon, David. 1978. MacLisp reference manual, Version 0. Technical report, MIT Laboratory
for Computer Science.
Moon, David, and Daniel Weinreb. 1981. Lisp machine manual. Technical report, MIT
Artificial Intelligence L aboratory.
Morris, J. H., Eric Schmidt, and Philip Wadler. 1980. Experience with an applicative string
processing language. In Proceedings of the 7th Annual ACM SIGACT/SIGPLAN Symposium
on the Principles of Programming Languages.
Phillips, Hubert. 1934. The Sphinx Problem Book. London: Faber and Faber.
Pitman, Kent. 1983. The revised MacLisp Manual (Saturday evening edition). Technical
report 295, MIT Laboratory for Computer Science.
Rabin, Michael O. 1980. Probabilistic algorithm for testing primality. Journal of Numbe r
Theory 12:128–138.
Raymond, Eric. 1993. The New Hacker’s Dictionary. 2nd edition. Cambridge, MA: MIT
Press. (Русский перевод: Рэймонд Э. Новый словарь хакера. – М.: Цен тр Ком, 1996.)
Raynal, Michel. 1986. Algorithms for Mutual Exclusion. Cambridge, MA: MIT Press.
Rees, Jonathan A., and Norman I. Adams IV. 1982. T: A dialect of Lisp or, lambda: The
ultimate software tool. In Conference Record of the 1982 ACM Symposium on Lisp and
Functional Programming, pp. 114–122.
Rees, Jonathan, and William Clinger (eds). 1991. The revised
4
report on the algorithmic
language Scheme. Lisp Pointers, 4(3).
Rivest, Ronald, Adi Shamir, and Leonard Adleman. 1977. A method for obtaining digital
signatures and public-key cryptosystems. Technical memo LCS/TM82, MIT Laboratory for
Computer Sc ience.
Rob inson, J. A. 1965. A machine-oriented logic based on the resolution principle. Journal of
the ACM 12(1):23.
Rob inson, J. A. 1983. Logic programming—Past, present, and future. New Generation
Computing 1:107–124. (Русский перевод: Робинсон Дж. Логическое программирование
– прошлое, настоя щее и будущее. // В кн. Логическое программирование. – М.: Мир,
1988, с. 7–26.)
564
Литература
Spafford, Eugene H. 1989. The Internet Wo rm: Crisis and aftermath. Communications of
the ACM 32(6):678–688.
Steele, Guy Lewis, Jr. 1977. Debunking the “expensive procedure call” myth. In Proceeding s
of the National Conference of the ACM, pp. 153–62.
Steele, Guy Lewis, Jr. 1982. An overview of Common Lisp. In Proceedings of the ACM
Symposium on Lisp and Functional Programming, pp. 98–107.
Steele, Guy Lewis, Jr. 1990. Common Lis p: The Language. 2nd edition. Digital Press.
Steele, Guy Lewis, Jr., and Gerald Jay Sussman. 1975. Scheme: An interpreter for the
extended lambda calculus. Memo 349, MIT Artificial Intelligence Laboratory.
Steele, Guy L ewis, Jr., Donald R. Woods, Raphael A. Finkel, Mark R. Crispin, Richard M.
Stallman, and Geoffrey S. Goodfellow. 1983. The Hacker’s Dictionary. New York: Harper &
Row.
Stoy, Joseph E. 1977. Denotational Semantics. Cambridge, MA: MIT Press.
Sussman, Gerald Jay, and Richard M . Stallman. 1975. Heuristic techniques in computer-
aided circuit analysis. IEEE Transactions on Circuits and Systems CAS-22(11):857–865.
Sussman, Gerald Jay, and Guy Lewis Steele Jr. 1980. Constraints – A language for
expressing almost-hierachical descriptions. AI J ournal 14:1–39.
Sussman, Gerald Jay, and Jack Wisdom. 1992. Chaotic evolution of the solar system. Science
257:256-262.
Sussman, Gerald Jay, Terry Winograd, and Eugene Charniak. 1971. Microplanner reference
manual. Memo 203A, MIT Artificial Inte lligence Laboratory.
Sutherland, Ivan E. 1963. SKETCHPAD: A man-machine graphical communication system.
Technical report 296, MIT Lincoln Laboratory.
Teitelman, Warren. 1974. Interlisp reference manual. Technical report, Xerox Palo Alto
Research Center.
Thatcher, James W., Eric G. Wagner, and Jesse B. Wright. 1978. Data type specification:
Parameterization and the power of specification techniques. In Conference Record of the
Tenth Annual ACM Symposium on Theory of Computing, pp. 119–132.
Turner, David. 1981. The future of applicative languages. In Proceedings of the 3rd
European Conference on Informatics, Lecture Notes in Computer Science, volume 123.
New York: Springer-Verlag, pp. 334–348.
Wand, Mitchell. 1980. Continuation-based program transformation strategies. Journal of the
ACM 27(1):164–180.
Waters, Richard C. 1979. A method for analyzing loop programs. IEEE Transactions on
Литература
565
Software Engineer ing 5(3):237–247.
Winograd, Terry. 1971. Procedures as a representation for data in a computer program
for understanding natural language. Technical report AI TR-17, MIT Artificial Intelligence
Laboratory.
Winston, Patrick. 1992. Artificial Intelligence. 3rd edition. Reading, MA: Addison-Wesley.
Zabih, Ramin , David McAllester, and David Chapman. 1987. Non-deterministic Lisp with
dependency-directed backtracking. AAAI-87, pp. 59–64.
Zippel, Richard. 1979. Probabilistic algorithms for sparse polynomials. Ph.D. dissertation,
Department of Ele ctrical Engine ering and Computer Science, MIT.
Zippel, Richard. 1993. Effective P olynomial Computation. Boston, MA: Kluwer Academic
Publishers.
Предметный указатель
Все неточности в этом указателе
объясняются тем, что его готовили при
помощи вычислительной машины.
Дональд Э. Кнут, Основные алгоритмы
(Исскусство программирования для
ЭВМ, том 1)
Номера страниц для определений процедур даны курсивом.
Буква п после номера страницы отсылает к примечанию.
Буквы нс после названия элементарной функции либо особой формы означают, что она
не входит в стандарт Scheme IEEE.
" (двойная кавыч ка) 147п
‘ (обратная кавычка) 524п
’ (одинарная кавычка) 147п
и read 356п, 444п
< (элементарный предикат сравнения
чисел) 36
!, в именах процедур 214п
* (элементарная процедура умножения) 26
+ (элементарная процедура сложения) 26
, (запятая, внутри обратной кавычки)
524п
- (элементарная процедура вычитания) 26
как смена знака 36п
/ (элементарная процедура деления) 26
; см. точка с запятой
= (элементарный предикат сравнения
чисел) 36
=number? 153
=zero? (обобщенная) 191 (упр. 2.80)
для многочленов 204 (упр. 2.87)
> (элементарный предикат сравнения
чисел) 36
>= (элементарный предикат сравнения
чисел) 38
?, в именах предикатов 41п
7→, математическая запись для функций
81п
λ-исчисление см. лямбда-исчисление
π см. пи
P
см. сигма-запись
Θ(f(n)) см. тета от f(n)
abs 36, 37
accelerated-sequence 316
accumulate 74 (упр. 1.32), 123
то же, что fold-right 127 (упр. 2.38)
accumulate-n 126 (упр. 2.36)
actual-value 373
Ada (Ада)
рекурсивные процедуры 51
add (обобщенная) 187
примененная к коэффициентам
многочленов 202
566
Предметный указатель
567
add-action! 264, 266
add-binding-to-frame! 352
add-complex 173
add-complex-to-schemenum 191
add-interval 103
add-lists 380
add-poly 200
add-rat 94
add-rule-or-assertion! 441
add-streams 309
add-terms 201
add-to-agenda! 267, 270
add-vect 141 (упр. 2.46)
addend 150, 152
adder (элементарное ограничение) 275
adjoin-arg 504п
adjoin-set 154
для множеств взвешенных элементов
168
представлен ие в виде бинарных деревьев
159
представлен ие в виде неупорядоченных
списков 155
представлен ие в виде упорядоченных
списков 157 (упр. 2.61)
adjoin-term 201, 204
advance-pc 481
after-delay 264, 267
Algol (Алгол)
бедность средств работы с составными
объектами 281п
блочная струк тура 47
передача аргументов по имени [call by
name] 306п, 372п
санки 306п, 372п
all-regs (компилятор) 535п
always-true 434
amb 383
ambeval 396
an-element-of 383
an-integer-starting-from 383
analyze
метациклическая 366
недетерминистская 396
analyze-amb 401
analyze-...
метациклические 366, 369 (упр. 4.23)
недетерминистские 397
and (особая форма) 37
без подвыражений 348 (упр. 4.4)
вычисление 37
почему особая форма 38
and (язык запросов) 411
обработка 419, 432, 448 (упр. 4.76)
and-gate 264
angle
декартово представление 174
полярное представление 175
с помеченными данными 178
управляемая данными 182
angle-polar 177
angle-rectangular 176
announce-output 356
APL 125п
append 110, 110, 244 (упр. 3.12)
vs. append! 244 (упр. 3.12)
как накопление 125 (упр. 2.33)
как регистровая машина 494 (упр. 5.22)
с произвольным числом аргументов 538п
«что такое» (правила) или «как сделать»
(процедура) 405
append! 245 (упр. 3.12)
как регистровая машина 494 (упр. 5.22)
append-instruction-sequences 521,
537
append-to-form (правила) 415
application? 346
apply (ленивая) 373
apply (метациклическая) 341
vs. элементарная apply 355п
apply (элементарная процедура) 182п
apply-dispatch 506
с учетом скомпилированных процедур
551
apply-generic 182
с башней типов 194
с приведением 193, 197 (упр. 2.81)
с приведением нескольких аргументов
197 (упр. 2.82)
с приведением через последовательный
подъем 198 (упр. 2.84)
с упрощением типа 198 (упр. 2.85)
568
Предметный указатель
через передачу сообщений 185
apply-primitive-procedure 341, 351,
356
apply-rules 436
argl, регистр 501
articles 389
assemble 476, 478п
assert! (интерпретатор запросов) 424
assign (в р егистровой машине) 455
имитация 481
сохранение метки в регистре 461
assign-reg-name 481
assign-value-exp 481
assignment-value 344
assignment-variable 344
assignment? 344
assoc 256
atan (элементарная процедура) 174п
attach-tag 176
использование типов Scheme 191
(упр. 2.78)
augend 150, 152
average 41
average-damp 83
averager (ограничение) 279 (упр. 3.33)
B-деревья [B-trees] 160п
Basic (Бейсик)
бедность средств работы с составными
объектами 281п
ограничения на составные данные 107п
begin-actions 346
begin? 346
below 134, 145 (упр. 2.51)
beside 133, 144
branch (в р егистровой машине) 454
имитация 482
branch-dest 482
C (Си)
интерпретатор Scheme, написанный на
Си 557 (упр. 5.51), 557 (упр. 5.52)
компиляция процедур Scheme в команды
Си 557 (упр. 5.52)
обработка ошибок 516п, 554п
ограничения на составные данные 107п
рекурсивные процедуры 51
cadr 108п
ca...r 108п
call-each 266
car (элементарная процедура) 95
как операция над списком 108
описывающая аксиома 100
происхождение имени 95п
процедурная реализация 101, 102
(упр. 2.4), 249, 379
реализация с мутаторами 249
реализация через векторы 492
свойство замыкания 106
cd...r 108п
cdr (элементарная процедура) 95
как операция над списком 108
описывающая аксиома 100
происхождение имени 95п
процедурная реализация 101, 102
(упр. 2.4), 249, 379
реализация с мутаторами 249
реализация через векторы 492
celsius-fahrenheit-converter 273
в формате выражения 280 (упр. 3.37)
center 104
cesaro-stream 330
cesaro-test 219
coeff 201, 204
Common Lisp 24п
трактовка nil 109п
compile 520
compile-and-go 551, 553
compile-and-run 556 (упр. 5.48)
compile-application 530
compile-assignment 526
compile-definition 526
compile-if 527
compile-lambda 529
compile-linkage 524
compile-proc-appl 535
compile-procedure-call 533
compile-quoted 525
compile-self-evaluating 525
compile-sequence 528
compile-variable 525
compiled-apply 552
Предметный указатель
569
compiled-procedure 529п
compiled-procedure-entry 529п
compiled-procedure-env 529п
complex, пакет 189
complex->complex 197 (упр. 2.81)
compound-apply 506
compound-procedure? 351
cond (особая форма) 36
vs. if 37п
вариант синтаксиса ветвей 349 (упр. 4.5)
ветвь 36
вычисление 36
неявный begin в следствиях 214п
cond->if 347
cond-actions 347
cond-clauses 347
cond-else-clause? 347
cond-predicate 347
cond? 347
conjoin 432
connect 275, 279
Conniver (Коннивер) 385п
cons (элементарная процедура) 95
как операция над списком 109
описывающие аксиомы 100
происхождение имени 95п
процедурная реализация 101, 101
(упр. 2.4), 244, 249, 379
реализация с мутаторами 249
реализация через векторы 493
cons-stream (особая форма) 301, 302
и ленивые вычисления 379
почему особая форма 303п
const (в регистровой машине) 455
имитация 484
синтаксис 471
constant (элементарное ограничение)
277
constant-exp-value 484
constant-exp? 484
construct-arglist 531
contents 176
использование типов Scheme 191
(упр. 2.78)
continue, регистр 461
в вычислителе с явным управлением 501
и рекурсия 467
corner-split 137
cos (элементарная процедура) 81
count-change 56
count-leaves 115, 117
как накопление 126 (упр. 2.35)
как регистровая машина 494 (упр. 5.21)
count-pairs 248 (упр. 3.16)
cube 59 (упр. 1.15), 69, 85
cube-root 84
current-time 267, 270
decode 167
deep-reverse 117 (упр. 2.27)
define (особая форма) 28
vs. lambda 75
внутренняя см. внутренние определени я
для процедур 32, 75
значение выражения 28п
модель с окружениями 231
почему особая форма 30
синтаксический сахар 344
точечная запись 112 (упр. 2.20)
define-variable! 351, 353
definition-value 345
definition-variable 344
definition? 344
delay (особая форма) 302
и ленивые вычисления 379
мемоизированная 305, 312 (упр. 3.57)
почему особая форма 303п
реализация с помощью lambda 305
явная 325
явная vs. автоматическая 380
delay-it 375
delete-queue! 251, 253
denom 94, 96
описывающая аксиома 100
с приведением к наименьшему
знаменателю 99
deposit (сообщение для банковского
счета) 216
deposit, с внешним сериализатором 292
deriv (символическая) 151
управляемая данными 183 (упр. 2.73)
deriv (численная) 85
570
Предметный указатель
disjoin 432
display (элементарная пр оцедура) 67
(упр. 1.22), 96п
display-line 302
display-stream 302
distinct? 387п
div (обобщенная) 187
div-complex 174
div-interval 103
деление на ноль 104 (упр. 2.10)
div-poly 205 (упр. 2.91)
div-rat 94
div-series 314 (упр. 3.62)
div-terms 205 (упр. 2.91)
divides? 64
divisible? 307
DOS/Windows 516п
dot-product 127 (упр. 2.37)
draw-line 141
driver-loop
для ленивого интерпретатора 374
для метациклического интерпр етатора
356
для неде терминистского интерпретатора
402
e
как решение дифференциального
уравнения 326
как цепная дробь 83 (упр. 1.38)
e
x
, степенной ряд 312 (упр. 3.59)
edge1-frame 140
edge2-frame 140
EIEIO 298п
element-of-set? 154
представлен ие в виде бинарных деревьев
159
представлен ие в виде неупорядоченных
списков 155
представлен ие в виде упорядоченных
списков 156
else (особый символ в cond) 37
empty-agenda? 267, 270
empty-arglist 504п
empty-instruction-sequence 523
empty-queue? 251, 252
empty-termlist? 201, 204
enclosing-environment 352
encode 169 (упр. 2.68)
end-segment 99 (упр. 2.2), 142
(упр. 2.48)
end-with-linkage 525
entry 159
enumerate-interval 123
enumerate-tree 123
env, регистр 501
eq? (элементарная процедура) 148
для произвольных объектов 247
и равенство чисел 491п
как равенство указателей 247, 492
реализация для символов 492
equ? (обобщенный предикат) 191
(упр. 2.79)
equal-rat? 95
equal? 149 (упр. 2.54)
error (элементарная процедура) 80п
estimate-integral 221 (упр. 3.5)
estimate-pi 219
euler-transform 316
ev-application 504
ev-assignment 510
ev-begin 507
ev-definition 511
ev-if 510
ev-lambda 503
ev-quoted 503
ev-self-eval 502
ev-sequence
без хвостовой рекурсии 509
с хвостовой рекурсией 508
ev-variable 502
eval (ленивая) 373
eval (метациклическая) 339, 340
vs. элементарная eval 359п
анализирующий вариант 366
управляемая данными 348 (упр. 4.3)
eval (элементарная процедура) 359
MIT Scheme 360п
в интерпретаторе запросов 433
eval-assignment 342
eval-definition 343
eval-dispatch 502