«Структура и интерпретация компьютерных программ Добросвет, 2006 Эта книга посвящается, с уважением и любовью, духу, который живет внутри компьютера. “Мне кажется, ...»

Scheme programming] 381, (упр. 4.41), 389 (упр. 4.44), (упр. 4.78) неопределенные значения [unspecied values] define 28п display 96п if без альтернативы 271п newline 96п set! 214п set-car! 242п set-cdr! 242п неподвижная точка [xed point, of a function] variable] 45, см. также лексическая (упр. 4.79) формальные параметры процедуры обмассив [obarray] обобщенные арифметические операции [generic arithmetic operations] 187 как контекст для вычисления обобщенные операции [generic operations] окружение времени компиляции обобщенные процедуры [generic обобщенный селектор 177, 179 операнды комбинации [operands of a обработка ошибок [error handling] в вычислителе с явным управлением в скомпилированном коде 554п в виде составного выражения обработка потоков [stream processing] 35п обработка сигналов [signal processing] переход сигнала через ноль (упр. 3.74), 323 (упр. 3.75), сглаживание сигнала 323 (упр. 3.75), обобщенные сглаживание функции 88 (упр. 1.44) определение процедуры [procedure обратная кавычка [backquote] 524п определения см. define; внутренние объект(ы) [object(s)] преимущества введения в с состоянием, меняющимся во времени объектная программа [object program] объектно-ориентированные языки программирования [object-oriented кода Хаффмана programming languages] 195п схемы Горнера 125п обычные числа [ordinary numbers] освобождение мьютекса в обобщенной арифметической системе особая форма [special form] ограничения [constraints] как производное выражение в окружение [environment] 28, 227 особые формы cond cons-stream (нс) define 28, delay (нс) lambda let let* 349 (упр. 4.7) letrec 363 (упр. 4.20) именованный let 349 (упр. 4.8) комплексные числа остановки проблема [halting problem] 360 многочлены остаток по модулю [remainder modulo n] рациональные числа отладка [debugging] 23 со списковой структурой [list-structured] отложенная операция [deferred operation] относительности теория [theory of пара (пары) [pair(s)] отношения, вычисления в терминах бесконечные потоки отображение [map] 121 использование для представления дерева отображение координат рамки [frame представленные с помощью векторов представление в виде пары векторов 142 стрелочная нотация представление в виде пары точек 99 и функциональное программирование отслеживаемая процедура [monitored механизмы для управления procedure] 217 (упр. 3.2) правильность параллельных программ передача сообщений [message passing] (упр.

3.82) в имитаторе цифровых схем 265 Пингала, Ачарья [Ach rya Pingala] 61п и модель с окружениями 240 (упр. 3.11) Питман, Кент [Kent Pitman] 24п и хвостовая рекурсия 51п Пифагоровы тройки [Pythagorean triples] переменная [variable] 28, см. также в недетерминистских программах значение [value] 28, область действия 45, см. также область план действий [agenda] 267, см. также действия переменной свободная связанная переменная образца [pattern variable] представление 430, переменная состояния [state variable] 51, внутренняя перенаправляющий адрес [forwarding address] перенос языка (на новый компьютер) [porting a language] перестановки множества [permutations of a переход сигнала через ноль (упр. 3.74), 323 (упр. 3.75), 324 подстановочная модель применения (упр. 3.76) перечислитель [enumerator] 121 неадекватность Перлис, Алан Дж. [Alan J. Perlis] 13, 107п форма процесса печать входных выражений [typing input expressions] 27п печать, элементарные процедуры несколько подтипов [primitives for printing] 96п подчиняется (правило) 414, пи () аппроксимация через интегрирование методом Монте-Карло 221 (упр. 3.5) приближенное вычисление методом половинного деления 80, 331 управляемый зависимостями приближенное вычисление через хронологический [chronological] интегрирование методом показатель конца списка [end-of-list поле типа [type eld] 491п последовательность выражений [sequence полноправные элементы вычисления [rst-class elements of computation] в следствии cond 37п 87, см. также элементы вычисления в теле процедуры 32п половинного деления метод [half-interval sequence] 521, half-interval-method 80 бесконечные см. бесконечные потоки полусумматор [half-adder] 261 используемые в интерпретаторе языка пометка с очисткой [mark-sweep] 495п пустые помеченные данные [tagged data] 175, реализованные в виде задержанных порождение предложений [generating реализованные в виде ленивых списков порядок вычисления [order of evaluation] пошаговое написание [incremental в вычислителе с явным управлением 505 пошаговое улучшение [iterative в компиляторе 546 (упр. 5.36) improvement] 89 (упр. 1.46) в метациклическом интерпретаторе 343 правило (в языке запросов) [rule] 407, зависимость от реализации 229п применение 422, 434, 436, порядок вычисления подвыражений [order предикат of subexpression evaluation] см. if порядок роста [order of growth] 58 ветви cond древовидно-рекурсивный процесс 58 соглашение об именах 41п линейно итеративный процесс 58 предложения [statements] 523, см.

линейно рекурсивный процесс 58 последовательность команд порядок событий [order of events] [unordered-list representation of sets] неопределенность в параллельных отделение от внешней структуры упорядоченных списков [ordered-list последовательное возведение в квадрат префикс [prex] [successive squaring] 60 префиксная нотация [prex notation] последовательности [sequences] 73п, 107 vs. инфиксная нотация 154 (упр. 2.58) как источник модульности 124 префиксный код [prex code] как стандартные интерфейсы 120 приведение к наименьшему знаменателю представленные в виде пар 107 приведение типов [coercion] в алгебраических манипуляциях 206 394, 396, см. также продолжение в арифметике многочленов процедура таблица применение процедур [procedure application] модель вычисления с окружениями обозначение комбинаций подстановочная модель см.

подстановочная модель применения присваивание [assignment] 212, см. также set!

вызванные ошибки 225п, 226 производные выражения в интерпретаторе расплата за провод, в цифровой схеме [wire] программа [program] как абстрактная машина как данные комментарии 129п пошаговое написание структура 28, 44, 46, см. также барьеры абстракции структурирование с помощью подпрограмм 359п программирование [programming] императивное управляемое данными см.

программирование, управляемое управляемое потребностями 304 высшего порядка см. процедура высшего функциональное см. функциональное элементы программирование, управляемое данными как данные [data-directed programming] 93, 171, как обобщенный метод в метациклическом интерпретаторе 348 мемоизированная 260 (упр. 3.27) продолжение [continuation] неявный begin в теле 214п в имитаторе регистровых машин 478п область действия формальных в недетерминистском интерпретаторе параметров определение отслеживаемая 217 (упр. 3.2) полноправный статус в Лиспе произвольное количество аргументов 26, создание с помощью define создание с помощью lambda 229, создание с помощью lambda составная [compound] тело формальные параметры процедура высшего порядка [higher-order procedure] в метациклическом интерпретаторе 341п и сильная типизация 328п процедура как возвращаемое значение процедура как обобщенный метод процедура в качестве аргумента процедурная абстракция [procedural abstraction] процедурное представление данных [procedural representation of data] изменяемые данные процесс [process] древовидно-рекурсивный линейно итеративный 51 разделяемое состояние [shared state] локальная эволюция 48 разделяемые ресурсы [shared resources] прочесывание внутренних определений polynomial] [scanning out internal denitions] 361 Райт, Джесси Б. [Jesse B. Wright] 100п в компиляторе 549п, 550 (упр. 5.43) Райт, Э. М. [E. M. Wright] 311п прямоугольники, их представление рак точки с запятой [cancer of the [representing rectangles] 99 (упр. 2.3) semicolon] 31п псевдоделение многочленов Рамануджан, Шриниваса [Srinivasa псевдоним [aliasing] 225п Рамануджана числа [Ramanujan numbers] псевдоостаток многочленов отображение координат 140 построение без define 364 (упр. 4.21) Ранкл, Джон Дэниел [John Daniel Runkle] рекурсивный процесс [recursive process] распространение ограничений [propagation vs. итеративный процесс 48, Рафаэль, Бертрам [Bertram Raphael] 405п vs. рекурсивная процедура рациональная арифметика [rational-number древовидный 53, взаимодействие с обобщенной регистровая машина арифметической системой 188 рекурсии теория [recursion theory] 359п необходимость составных данных 91 рекурсия [recursion] 29, рациональная функция [rational function] в правилах приведение к наименьшему знаменателю для работы с деревьями рациональные числа [rational numbers] референциальная прозрачность арифметические операции 93 решение уравнений [solving equations] см.

представление в виде пар 96 решето Эратосфена [sieve of Eratosthenes] приведение к наименьшему знаменателю регистр [register] 450 Ривест, Рональд Л. [Ronald L. Rivest] 67п, представление регистровая машина [register machine] действия диаграмма контроллера диаграмма путей данных контроллер отслеживание производительности подпрограмма программа моделирования проектирование пути данных стек тест трассировка 488 (упр. 5.18) язык для описания резолюции принцип [resolution principle] Хорновские формы 405п Рейтер, Андреас [Andreas Reuter] 297п рекурсивная процедура [recursive определение рекурсивной процедуры 43 Сазерленд, Айвен [Ivan Sutherland] 272п самовычисляющееся выражение селектор [selector] [self-evaluating expression] 340 как барьер абстракции самосознание, повышение уровня обобщенный 177, [expansion of consciousness] 342п семафор [semaphore] 294п вызова по имени [call-by-name] 306п сериализатор [serializer] 288, вызова по необходимости [call-by-need] реализация происхождение названия 372п сеть ограничений [constraint network] Сассман, Джеральд Джей [Gerald Jay garbage collector] 496п Сассман, Джули Эстер Мазель, сильно типизированный язык [strongly племянницы [nieces of Julie Esther typed language] 328п сбалансированное бинарное дерево encoding] [balanced binary tree] 160, см. также символ(ы) [symbol(s)] сбалансированный мобиль [balanced кавычки сборка мусора [garbage collection] 375п, равенство и изменения данных 242п символьная алгебра [symbolic algebra] и хвостовая рекурсия 535п expression] 92, см. также символ(ы) сжимающая [compacting] 496п символьное дифференцирование [symbolic через остановку с копированием dierentiation] 149, 183 (упр. 2.73) через пометку с очисткой [mark-sweep] интегрирования [Simpson’s Rule for сборщик мусора [garbage collector] 242п синтаксис [syntax] 339, см. также особые через пометку с очисткой 495п выражений, описание 32п свободная переменная [free variable] 45 языка программирования лексическая сфера действия 47 языка [parsing] связанная переменная [bound variable] 45 настоящая обработка языка vs.

сглаживание сигнала [smoothing a signal] выполнения [separating syntactic 323 (упр. 3.75), 324 (упр. 3.76) analysis from execution] сглаживание функции 88 (упр. 1.44) в имитаторе регистровых машин 476, секретарь, его важное значение [importance of a secretary] 408 в метациклическом интерпретаторе синтаксический интерфейс [syntax сопоставитель [pattern matcher] синтаксический сахар [syntactic sugar] 31п matching] процедура vs. данные 266п сопротивление [resistance] приближение при малых углах степенной ряд 312 (упр. 3.59) синхронизация см. параллелизм использование в качестве элементарных систематический поиск [systematic search] скобки [parentheses] в определении процедуры обозначающие клаузу cond обозначение применения функции к слизывание [snarng] 370п слияние [merge] слияние бесконечных потоков [merging innite streams] см. бесконечные смещение [displacement] собака идеально разумная, поведение [behavior of a perfectly rational dog] совместимое расширение [upward-compatible extension] (упр. 4.31) согласованность кэша [cache coherence] соглашение об именах [naming conventions] ! для присваиваний и изменений 214п ? для предикатов 41п соединитель (соединители) в системе ограничений [connector(s), in сокрытие связывания [shadowing a ленивый сокрытия принцип [hiding principle] 215п методы работы Соломонофф, Рэй [Ray Solomono] 218п обратная кавычка 524п обращение 111 (упр. 2.18) Стой, Джозеф Э. [Joseph E. Stoy] 34п, операции отображение последняя пара 111 (упр. 2.17) представление на печати преобразование в бинарное дерево преобразование из бинарного дерева пустой см. пустой список равенство 149 (упр. 2.54) с заголовком [headed] 255, 269п «сconsивание» соединение через append «уcdrивание» список свободных ячеек [free list] 493п список термов многочлена [term list of polynomial] 199, представление средства абстракции [means of abstraction] define средства комбинирования [means of cvombination] 25, см. также замыкание стандартный интерфейс [conventional interface] 92, последовательность стек [stack] 51п, для рекурсии в регистровой машине кадрированный 503п представление 474, степенной ряд, представленный как поток [power series, as a stream] (упр. 3.59) перемножение 313 (упр. 3.60) n-мерная 259 (упр. 3.25) степенные ряды как потоки для программирования, управляемого интегрирование 313 (упр. 3.59) Стил, Гай Льюис мл. [Guy Lewis Steele Jr.] 24п, 52п, 226п, 272п, 370п, 384п действий стиль, ориентированный на выражения, vs. используемая для хранения [expression-oriented style vs.

операций и типов см. таблица операций иерархия в символьной алгебре представленная в виде бинарного дерева несколько подтипов и надтипов vs. неупорядоченного списка 260 операции со смешанными типами проверка равенства ключей 259 спуск 195, 198 (упр. 2.85) хребет [backbone] 255 типизированный указатель [typed pointer] [operation-and-type table] 180 тождественность и изменение [sameness необходимость присваивания 213п and change] таблица регистров, в программе и разделяемые данные моделирования [register table] 475 торможение усреднением [average табуляризация [tabulation] 57п, 260 точечная запись [dotted-tail notation] как цепная дробь 83 (упр. 1.39) для процедурных параметров теговая архитектура [tagged architecture] точка входа [entry point] Тейтельман, Уоррен [Warren Teitelman] [nondeterministic choice point] текущее время, для имитации плана как символ комментария 129п тело процедуры [body of a procedure] 32 [point, represented as a pair] теорема об остановке [Halting Theorem] (упр. 2.2) Т рнер, Дэвид [David Turner] 128п, 319п, тест на равенство нулю (обобщенный) регистров [register] 488 (упр. 5.18) [zero test] 191 (упр. 2.80) требуемые регистры [needed registers] см.

для многочленов 204 (упр. 2.87) последовательность команд тест, операция в регистровой машине треугольник Паскаля [Pascal’s triangle] тета от f (n) ((f (n))) 58 тригонометрические тождества техника vs. математика [engineering vs. [trigonometric relations] в сильно типизированных языках 328п 360п Тэтчер, Джеймс У. [James W. Thatcher] уравнения, решения см. метод Уайз, Дэвид С. [David S. Wise] 306п Уайлс, Эндрю [Andrew Wiles] 65п Уайльд, Оскар, парафраза Перлиса [Oscar уголь, битумный [bituminous coal] 133п условное выражение [conditional удовлетворение запросу [satisfying a expression] Уиздом, Джек [Jack Wisdom] 24п устойчивость программы [robustness] Уинстон, Патрик Генри [Patrick Henry утверждение [assertion] типизированный [typed] умножение методом русского крестьянина [Russian peasant method of multiplication] 61п универсальная машина [universal machine] вычислитель с явным управлением компьютер общего назначения унификация [unication] 405, 417, vs. сопоставление с образцом 422, 424п открытие алгоритма 405п реализация Уодлер, Филип [Philip Wadler] 225п Уодсворт, Кристофер [Christopher Wadsworth] 329п Уокер, Фрэнсис Амаса [Francis Amasa Walker] 133п Уоллис, Джон [John Wallis] 73п Уотерс, Ричард К. [Richard C. Waters] 125п управляющий цикл [driver loop] в вычислителе с явным управлением в интерпретаторе запросов 424, в ленивом интерпретаторе в метациклическом интерпретаторе в недетерминистском интерпретаторе упрощение алгебраических выражений [simplication of algebraic expressions] уравнения рекурсии [recursion equations] формальные параметры процедуры [formal и вычислитель с явным управлением имена область действия форматирование входных выражений [formatting input expressions] 27п Фридман, Дэниел П. [Daniel P. Friedman] 306п, 337п функциональное программирование [functional programming] 222, и время и параллельность функциональный язык программирования функциональный элемент в цифровых схемах [function box] функциональный язык программирования [functional programming language] функция (математическая) [function] -нотация 81п vs. процедура Аккермана 52 (упр. 1.10) композиция 88 (упр. 1.42) многократное применение 88 (упр. 1.43) неподвижная точка производная рациональная [rational] сглаживание 88 (упр. 1.44) Хайтин, Грегори [Gregory Chaitin] 218п точные 42п Хансон, Кристофер П. [Cristopher P. (упр. 1.37) хаос в динамике Солнечной системы золотое сечение 82 (упр. 1.37) Харди, Годфри Харольд [Godfrey Harold цепь электрическая [circuit] Хаффман, Дэвид [David Human] 164 (упр. 3.73), 328 (упр. 3.80) Хаффмана код [Human code] 163, см. код Цзю Ши-Цзе [Chu Shih-Chieh] 57п порядок роста для кодирования 170 цикл обратной связи, моделируемый с хвостовая рекурсия [tail recursion] 51, 508 цикл чтение-вычисление-печать циклические конструкции [looping реализация в метациклическом шишка (правило) 413, 428 (упр. 4.65) интерпретаторе 350 (упр. 4.9) Шмидт, Эрик [Eric Schmidt] 225п цифровой сигнал [digital signal] 261 Шроуб, Ховард Э. [Howard E. Shrobe] Чанда-сутра 61п Чарняк, Юджин [Eugene Charniak] 385п Эдинбургский университет [University of Чезаро, Эрнесто [Ernesto Ces` ro] 219п Чепман, Дэвид [David Chapman] 385п (упр. 1.38) «Червь» в Интернете [Internet “worm”] доказательство Малой теоремы Ферма Ч рч, Алонсо [Alonzo Church] 75п, Ч рча числа [Church numerals] Ч рча-Тьюринга тезис [Church-Turing

thesis] 359п помощью потоков 322 (упр. 3.73),

в обобщенной арифметической системе элементарные выражения [primitive зависимость от реализации 42п имя элементарной процедуры простые по отношению к другому числу числа численные данные [numerical data] 25 = численный анализ [numerical analysis] 25п apply 182п “что такое” vs. “как сделать” [“how to” vs. atan 174п eval (нс) 360п list log 82 (упр. 1.36) max min newline 96п not null? number pair? quotient 312 (упр. 3.58) random (нс) 66, 221п read 356п remainder round 198п runtime (нс) 67 (упр. 1.22) set-car! set-cdr! sin symbol? vector-ref vector-set! элементарный запрос [primitive query] см.

простой запрос элементы вычисления первого класса [rst-class elements of computation] 87, см. также полноправные элементы вычисления Эратосфен 308п эффективность [eciency] см. также порядок роста вычисления доступа к базе данных 418п древовидно-рекурсивного процесса компиляции Лиспа обработки запросов Эшер, Мориц Корнелис [Maurits Cornelis Escher] 132п явное кодирование элементарных процедур [open coding of primitives] (упр. 5.38), 550 (упр. 5.44) язык [language] см. естественный язык;

язык программирования