Абельсон Х., Сассман Д.Д. Структура и интерпретация компьютерных программ
Подождите немного. Документ загружается.
Предметный указатель
601
самовычисляющееся выражение
[self-evaluating expression] 340
самосознание, повышение уровня
[expansion of consciousness] 342п
санк [thunk] 372
вызова по имени [call-by-name] 306п
вызова по необходимости [call-by-need]
306п
вынуждение 372
происхождение названия 372п
реализация 375
Сассман, Джеральд Джей [Gerald Jay
Sussman] 24п, 272п, 385п
Сассман, Джули Эстер Мазел ь,
племянницы [nieces of Julie Esther
Mazel Sussman ] 146
сбалансированное бинарное дерево
[balanced binary tree] 160, см. также
бинарное дерево
сбалансированный мобиль [balanced
mobile] 118 (упр. 2.29)
сборка мусора [garbage collection] 375п,
489, 494, 495
и изменения данных 242п
и мемоизация 375п
и хвостовая рекурсия 535п
сжимающая [compacting] 496п
через остановку с копированием
[stop-and-copy] 495
через пометку с очисткой [mark-sweep]
495п
сборщик мусора [garbage collector] 242п
остановка с копированием 495
сжимающий 496п
через пометку с очисткой 495п
свободная переменная [free variable] 45
захват 46
лексическая сфера действия 47
связанная переменная [bound variable] 45
связывание [binding] 45, 227
глубокое [deep] 354п
сглаживание сигнала [smoothing a signal]
323 (упр. 3.75), 324 (упр. 3.76)
сглаживание функции 88 (упр. 1.44)
секретарь, его важное значение
[importance of a secretary] 408
селектор [selector] 93
как барьер абстракции 98
обобщенный 177, 179
семафор [semaphore] 294п
размера n 296 (упр. 3.47)
сериализатор [serializ er] 288, 289
реализация 294
с множественными разделяемыми
ресурсами 291
сеть ограничений [constraint network] 272
сжимающий сборщик мусора [compacting
garbage collector] 496п
сигма-запись (
P
) 71
сильно типизированный язык [strongly
typed language] 328п
символ в коде ASCII [character in ASCII
encoding] 163
символ(ы) [symbol(s)] 146
восприятие 492
кавычки 147
представлен ие 491
равенство 148
уникальность 247п
символьная ал гебра [symbolic algebra] 198
символьное выражение [symbolic
expression] 92, см. также символ(ы)
символьное дифференцирование [symbolic
differentiation] 149, 183 (упр. 2.73)
Симпсона правило для численного
интегрирования [Simpson’s Rule for
numerical integration] 73 (упр. 1.29)
синтаксис [syntax] 339, см. также особые
формы
абстрактный см. абстрактный синтаксис
выражений, описание 32п
языка программирования 31
синтаксический анализ естественного
языка [parsing] 389
настоящая обработка языка vs.
игрушечный анализатор 393п
синтаксический анализ, отделение от
выполнения [separating syntactic
analysis from execution ]
в имитаторе регистровых машин 476,
481
в метациклическом интерпретаторе 365
602
Предметный указатель
синтаксический интерфейс [syntax
interface] 266п
синтаксический сахар [syntactic sugar] 31п
define 344
let 77
процедура vs. данные 266п
циклические конструкции 51
синус [sine]
приближение при малых углах 59
(упр. 1.15)
степенной ряд 312 (упр. 3.59)
синхронизация см. параллелизм
систематический поиск [systematic search]
384
скобки [parentheses]
в определении процедуры 32
обозначающие клаузу cond 36
обозначение применения функции к
аргументам 26
слизывание [snarfing] 370п
слияние [merge] 334
слияние бесконечных потоков [merging
infinite streams] см. бесконечные
потоки
смещение [displacement] 548
собака идеально разумная, поведение
[behavior of a perfectly rational dog]
296п
совместимое расширение
[upward-compatible extension] 378
(упр. 4.31)
согласованность кэша [cache coherence]
285п
соглашение об именах [naming
conventions]
! для присваиваний и изменений 214п
? для предикатов 41п
соединитель (соединители) в системе
ограничений [connector(s), in
constraint system] 272
операции 275
представлен ие 278
сокрытие связывания [shadowing a
binding] 228
сокрытия принцип [hiding principle] 215п
Соломонофф, Рэй [Ray Solomonoff] 218п
сопоставитель [pattern matcher] 417
сопоставление с образ цом [pattern
matching] 417
vs. унификация 422, 424п
реализация 434
сопротивление [resistance]
погрешность 102
формула для параллельных резисторов
102, 105
составная процедура [compound procedure]
31, см. также процедура
использование в качестве элементарных
33
составное выражение [compound
expression] 26, см. также
комбинация; особая форма
как оператор комбинации 39 (упр. 1.4)
составной з апрос [compound query] 411
обработка 419, 432, 447 (упр. 4.75), 448
(упр. 4.76), 448 (упр. 4.77)
составной объект данных [compound data
object] 91
составные данные, их необходимость
[compound data, need for] 90
состоя ние [state]
внутреннее см. внутреннее состояние
исчезновение в потоковой формулировке
332
разделяемое 285
Спаффорд, Юджин Г. [Eugene H. Spafford]
554п
специалист по численному анализу
[numerical analyst] 79п
списковая структура 96, 108п
vs. список 108п
изменяемая 242
представлен ная с помощью векторов 490
список [list] 108, 108п
n-й элемент 109
vs. списковая структура 108п
длина 110
кавычки 147
ленивый 379
манипуляции с car, cdr и cons 108
методы работы 109
обратная кавычка 524п
Предметный указатель
603
обращение 111 (упр. 2.18)
операции 109
отображение 112
последняя пара 111 (упр. 2.17)
представлен ие на печати 108
преобразование в бинарное дерево 161
(упр. 2.64)
преобразование из бинарного дерева 161
(упр. 2.63)
пустой см. пустой список
равенство 149 (упр. 2.54)
с заголовком [headed] 255, 269п
«сconsивание» 110
соединение через append 110
«уcdrивание» 109
список свободных ячеек [free list] 493п
список термов многоч лена [term list of
polynomial] 199, 200
представлен ие 203
средства абстракции [means of abstraction]
25
define 28
средства комбинирования [means of
cvombination] 25, см. также
замыкание
стандартный интерфейс [conventional
interface] 92, 120
последовательность 120
стек [stack] 51п, 467
для рекурсии в р егистровой машине 463
кадрированный 503п
представлен ие 474, 493
степенной ряд, представленный как поток
[power series, as a stream] 312
(упр. 3.59)
деление 314 (упр. 3.62)
перемножение 313 (упр. 3.60)
сложение 313 (упр. 3.60)
степенн ые ряды как потоки
интегрирование 313 (упр. 3.59)
Стил, Гай Льюис мл. [Guy Lewis Steele
Jr.] 24п, 52п, 226п, 272п, 370п, 384п
стиль, ориентированный на выражения, vs.
императивный стиль
[expression-oriented style vs.
imperative style] 281п
Стой, Джозеф Э. [Joseph E. Stoy] 34п,
62п, 364п
Столлман, Ричард М. [Richard M.
Stallman] 272п, 385п
Стрейчи, Кристофер [Christopher Strachey]
87п
стрелка [pointer] 106
в стрелочной диаграмме 106
стрелочная диаграмма [box-and-pointer
notation] 106
строгая процедура [procedure] 371
строка [string]
печатание 147п
элементарные процедуры 444п, 527п
структура управления [control structure]
425
сумматор [full-adder] 263
full-adder 263
каскадный [ripple-carry] 265 (упр. 3.30)
полу- 261
сумматор для сигналов [summer] 322
суммирование последовательности
[summation of a series] 71
с потоками 315
ускорение последовательности
приближений 315
схема [circuit]
моделируемая с помощью потоков 322
(упр. 3.73), 328 (упр. 3.80)
цифровая см. имитация цифровых схем
схема Горнера [Horner’s rule] 125
(упр. 2.34)
счет банковский см. банковский счет
счетчик программы [program counter] 475
таблица [table] 254
n-мерная 259 (упр. 3.25)
двумерная 256
для программирования, управляемого
дан ными 180
используемая для моделировани я плана
действий 269
используемая для хранения
вычисленных значений 260
(упр. 3.27)
локальная 258
604
Предметный указатель
одномерная 255
операций и типов см. таблица операций
и типов
представлен ная в виде бинарного дерева
vs. неупорядоченного списка 260
(упр. 3.26)
приведения 192
проверка равенства ключей 259
(упр. 3.24)
хребет [backbone] 255
таблица операций и типов
[operation-and-type table] 180
необходимость присваивания 213п
реализация 259
таблица регистров, в программе
моделирования [register table] 475
табло [tableau] 316
табуляризация [tabulation] 57п, 260
(упр. 3.27)
тангенс [tangent]
как цепная дробь 83 (упр. 1.39)
степенной ряд 314 (упр. 3.62)
тег типа [type tag] 491п
теговая архитектура [tagged architecture]
491п
Тейтельман, Уоррен [Warren Teitelman]
24п
текущее время, для имитации плана
[current time] 269
тело процедуры [body of a procedure] 32
теорема об остановке [Halting Theorem]
360п
Т
¨
ернер, Дэвид [David Turner] 128п, 319п,
333п
тест на равенство нулю (обобщенный)
[zero test] 191 (упр. 2.80)
для многочленов 204 (упр. 2.87)
тест, операция в регистровой машине
[test] 452
тета от f (n) (Θ(f(n))) 58
техника vs. математика [engineering vs.
mathematics] 66п
тип данных
башня [tower of types] 194
в Лиспе 191 (упр. 2.78)
в сильно типизированных языках 328п
диспетчеризация 179
иерархия в символьной алгебре 206
надтип 194
несколько подтипов и надтипов 195
операции со смешанными типами 191
подтип 194
подъем 194, 197 (упр. 2.83)
спуск 195, 198 (упр. 2.85)
тип связи [linkage descriptor] 520
типизированный указатель [typed pointer]
490
тождественность и изменение [sameness
and change]
значение 223
и разделяемые данные 246
торможение усреднением [average
damping] 82
точечная запись [dotted-tail notation]
в образцах запросов 410, 435
в правилах языка запросов 415
для процедурных параметров 112
(упр. 2.20), 182п
и read 436
точка входа [entry point] 454
точка неде терминистского выбора
[nondeterministic choice point] 384
точка с запятой [semicolon ] 31п
как символ комментария 129п
точка, представленная в виде пары чисел
[point, represented as a pair] 99
(упр. 2.2)
точные це лые числа [exact integers] 42п
трассировка [tracing]
команд [instruction] 488 (упр. 5.16)
регистров [register] 488 (упр. 5.18)
требуемые регистры [needed registers] см.
последовательность команд
треугольник Паскаля [Pascal’s triangle] 57
(упр. 1.12)
тригонометрические тождества
[trigonometric relations] 175
тупик 296, 297
выход 297п
способ избежания 297
Тьюринг, Алан М. [Alan M. Turing] 359п,
360п
Предметный указатель
605
Тэтчер, Джеймс У. [James W. Thatcher]
100п
Уайз, Дэвид С. [David S. Wise] 306п
Уайлс, Эндрю [Andrew Wiles] 65п
Уайльд, О скар, парафраза Перлиса [Oscar
Wilde] 27п
уголь, битумный [bituminous coal] 133п
удовлетворение запросу [satisfying a
pattern] 410
составному 411
Уиздом, Джек [Jack Wisdom] 24п
Уи нстон, Патрик Генри [Patrick Henry
Winston] 385п, 393п
указатель [pointer]
типизированный [typed] 490
умножение методом русского крестьянина
[Russian peasant method of
multiplication] 61п
универсальная машина [universal machine]
359
вычислитель с явным управлением 517
компьютер общего назначения 517
унификация [unification] 405, 417, 421
vs. сопос тавление с образцом 422, 424п
открытие алгоритма 405п
реализация 437
Уодлер, Филип [Philip Wadler] 225п
Уодсворт, Кристофер [Christopher
Wadsworth] 329п
Уокер, Фрэнсис Амаса [Francis Amasa
Walker] 133п
Уоллис, Джон [John Wallis] 73п
Уотерс, Ричард К. [Richard C. Waters] 125п
управляющий цикл [driver loop] 356
в вычислителе с явным управлением 512
в интерпретаторе запросов 424, 429
в ленивом интерпретаторе 374
в метациклическом интерпретаторе 356
в недетерминистском интерпретаторе
385, 401
упрощение алгебраических выражений
[simplification of algebraic expressions]
152
уравнения рекурсии [recursion equations]
23
уравнения, решения см. метод
половинного деления; Ньютона метод;
solve
уровневое проектирование [stratified
design] 145
ускоритель последовательности [sequence
accelerator] 315
условное выражение [conditional
expression]
cond 36
if 37
устойчивость программы [robustness] 145
утверждение [assertion] 407
неявное 413
утренняя звезда [morning star] см. Венера
факториал [factorial] 48, см. также
factorial
без letrec и define 364 (упр. 4.21)
бесконечный поток 311 (упр. 3.54)
с letrec 364 (упр. 4.20)
Фейгенбаум, Эдвард [Edward Feigenbaum]
406п
Феничель, Роберт [Robert Fenichel] 495п
Ферма Малая теорема [Fermat’s Little
Theorem] 65
альтернати вная формулировка 69
(упр. 1.28)
доказательство 65п
Ферма тест на простоту [Fermat test for
primality] 65
вариант 69 (упр. 1.28)
Ферма, Пьер де [Pierre de Fermat] 65п
Фибоначчи числа [Fibonacci numbers] 53,
см. также fib
бесконечный поток см. fibs
и алгоритм Евклида для НОД 63
Фили, Марк [Marc Feeley] 366п
Филипс, Хьюберт [Hubert Phillips] 388
(упр. 4.42)
фильтр [filter] 74 (упр. 1.33), 121
Флойд, Роберт [Robert Floyd] 385п
Форбус, Кеннет Д. [Kenneth D. Forbus]
385п
форма процесса [shape of a process] 50
606
Предметный указатель
формальные параметры процедуры [formal
parameters] 32
имена 45
область действия 45
форматирование входных выражени й
[formatting input expressions] 27п
Фридман, Дэниел П. [Daniel P. Friedman]
306п, 337п
функциональное программирование
[functional programming] 222, 330
и врем я 331
и параллельность 333
функциональный язык
программирован ия 333
функциональный элемент в цифровых
схемах [function box] 261
функциональный язык программирования
[functional programming language] 333
функция (математическая) [function]
7→-нотация 81п
vs. процедура 40
Аккермана 52 (упр. 1.10)
композиция 88 (упр. 1.42)
многократное применение 88 (упр. 1.43)
неподвижная точка 80
производная 85
рациональная [rational] 207
сглаживание 88 (упр. 1.44)
Хайтин, Грегори [Gregory Chaitin] 218п
Хайям, Омар 57п
Хансон, Кристофер П. [Cristopher P.
Hanson] 348п, 535п
хаос в динамике Солне чной системы
[chaos in Solar system] 24п
Харди, Годфри Харольд [Godfrey Harold
Hardy] 311п, 321п
Хаффман, Дэвид [David Huffman] 164
Хаффмана код [Huffman code] 163, см. код
Хаффмана
оптимальность 165
порядок роста для кодирования 170
(упр. 2.72)
хвостовая рекурсия [tail recursion] 51, 508
в Scheme 52п
и вычисли тель с явным у правлением
508, 515 (упр. 5.26), 516 (упр. 5.28)
и компилятор 535
и метациклический интерпретатор 508
и модель с окружениям и 234п
и сборка мусора 535п
хвостовая рекурсия в списке аргументов
[evlis tail recursion] 505п
Хейвендер, Дж. [J. Havender] 297п
Хейнс, Кристофер Т. [Christopher T.
Haynes] 337п
Хендерсон, Питер [Peter Henderson] 132п,
308п, 333п
хендерсоновская диаграмма 308
Херн, Энтони К. [Anthony C. Hearn] 24п
Хилфингер, Пол [Paul Hilfinger] 162п
Хоар, Чарльз Энтони Ричард [Charles
Anthony Richard Hoare] 100п
Ходжес, Эндрю [Andrew Hodges] 359п
Хофштадтер, Дуглас Р. [Douglas R.
Hofstadter] 359п
Хьюз, Р. Дж. М. [R. J. M. Hughes] 380п
Хьюи тт, Карл Эдди [Carl Eddie Hewitt]
51п, 385п, 405п, 495п
Хэммин г, Ричард Уэсли [Richard Wesley
Hamming] 165п, 311 (упр. 3.56)
целевой регистр [target] 520
целые числа [integers] 25п
деление 42п
точные 42п
цепная дробь [continued fraction] 82
(упр. 1.37)
e 83 (упр. 1.38)
золотое сечение 82 (упр. 1.37)
тангенс 83 (упр. 1.39)
цепь электрическая [circuit]
моделируемая с помощью потоков 322
(упр. 3.73), 328 (упр. 3.80)
Цзю Ши-Цзе [Chu Shih-Chieh] 57п
цикл в списке [cycle in list] 245 (упр. 3.13)
обнаружение 248 (упр. 3.18)
цикл обратной связи, моделируемый с
помощью потоков [feedback loop] 324
цикл чтение-вычисление-печать
[read-eval-print loop] 27, см. также
Предметный указатель
607
управляющий цикл
циклические конструкции [looping
constructs] 42, 51
реализация в метациклическом
интерпретаторе 350 (упр. 4.9)
цифровой сигнал [digital signal] 261
Чанда-сутра 61п
Чарняк, Юджин [Eugene Charniak] 385п
Чебышев, Пафнутий Львович 311п
Чезаро, Эрнесто [Ernesto Ces
`
aro] 219п
Чепман, Дэвид [David Chapman] 385п
«Червь» в Интернете [Internet “worm”]
554п
черн ый ящик [black box] 44
Ч
¨
ерч, Алонсо [Alonzo Church] 75п, 102
(упр. 2.6)
Ч
¨
ерча числа [Church numerals] 102
(упр. 2.6)
Ч
¨
ерча-Тьюрин га тезис [Church-Turing
thesis] 359п
чисел теория [number theory] 65п
числа [numbers]
в Лиспе 26
в обобщенной арифметической системе
187
вещественные [real] 25п
десятичная точка 42п
зависимость от реализации 42п
простые по отношению к другому числу
74 (упр. 1.33)
равенство 36, 149п, 491п
рациональные 42п
сравнение 36
точные це лые 42п
целые [integer] 25п
целые vs. веще ствен ные 25п
численные данные [numerical data] 25
численный анализ [numerical analysis] 25п
“что такое” vs. “как сделать” [“how to” vs.
“what is”] см. декларативное vs.
императивное знание
Чёрча–Тьюринга тезис см. те зис
Черча–Тьюринга
Шамир, Ади [Adi Shamir] 67п
шахматы, задача о восьми ферзях [chess,
eight-queens puzzle] 130 (упр. 2.42),
389 (упр. 4.44)
шишка (правило) 413, 428 (упр. 4.65)
Шмидт, Эрик [Eric Schmidt] 225п
Шроуб, Ховард Э. [Howard E. Shrobe]
406п
Эдинбургский университет [University of
Edinburgh] 405п
Эйлер, Леонард [Leonhard Euler] 83
(упр. 1.38)
доказательство Малой теоремы Ферма
65п
ускоритель рядов 315
Эйндховенский технический Университет
294п
экспоненциальный ро ст [exponential
growth] 58
электрические цепи, моделируемые с
помощью потоков 322 (упр. 3.73), 328
(упр. 3.80)
элементарное ограничение [primitive
constraint] 272
элементарные выражения [primitive
expressions] 25
вычисление 30
имя переменной 28
имя элементарной процедуры 26
числа 26
элементарные процедуры [primitives]
< 36
> 36
* 26
+ 26
- 26, 36п
/ 26
= 36
apply 182п
atan 174п
car 95
cdr 95
cons 95
cos 81
display 96п
eq? 148
608
Предметный указатель
error (нс) 80п
eval (нс) 360п
list 108
log 82 (упр. 1.36)
max 103
min 103
newline 96п
not 37
null? 110
number 150
pair? 117
quotient 312 (упр. 3.58)
random (нс) 66, 221п
read 356п
remainder 60
round 198п
runtime (нс) 67 (упр. 1.22)
set-car! 242
set-cdr! 242
sin 81
symbol? 151
vector-ref 490
vector-set! 490
элементарный запрос [primitive query] см.
простой запрос
элементы вычисления первого класса
[first-class elements of computation]
87, см. также полноправные
элементы вычисления
Эратосфен 308п
эффективность [efficiency] см. также
порядок роста
вычисления 365
доступа к базе данных 418п
древовидно-рекурсивного проце сса 57
компиляции 518
Лиспа 24
обработки запросов 420
Эшер, Мориц Корнелис [Maurits Cornelis
Escher] 132п
явное кодирование элементарных процедур
[open coding of primitives] 547
(упр. 5.38), 550 (упр. 5.44)
язык [language] см. естественный язык;
язык программирования
язык запросов [query language] 406, 407
vs. математическая логика 425
абстракция 412
база данных 407
логический вывод 415
правило см. правило (в языке запросов)
проверка на равенство 412п
простой запрос см. простой запрос
расширения 428 (упр. 4.66), 447
(упр. 4.75)
составной з апрос см. составной запрос
язык описания изображений [picture
language] 133
язык программирования [programming
language] 22
логического 406
объектно-ориентированный 195п
с аппликативным порядком вычислений
[applicative-order] 370
с нормальным порядком вычислений
[normal-order] 370
сверхвысокого уровня 40п
сильно типизированный 328п
строение 369
функциональный 333
язык регистровых машин [register machine
language]
assign 455, 471
branch 454, 471
const 455, 471
goto 454, 471
label 454
op 455, 471
perform 457, 471
reg 455, 471
restore 467, 471
save 467, 471
test 454, 471
метка 454
команды 454, 471
точки входа 454
язык сверхвысокого уровня [very high-level
language] 40п
ячейка, в реализации сериализатора [cell,
in serializer implementation] 295