Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 85
Текст из файла (страница 85)
Метаязыковая абстракциямодифицируя этот интерпретатор. В самом деле, часто изобретение нового языка начинается с того, что пишут интерпретатор, который встраивает новый язык в существующийязык высокого уровня. Например, если нам хочется обсудить какую-то деталь предлагаемой модификации Лиспа с другим членом Лисп-сообщества, мы можем предъявить емуинтерпретатор, в котором эта модификация реализована. Тогда наш адресат может поэкспериментировать с новым интерпретатором и послать в ответ свои замечания в видедальнейших модификаций. Реализация на высокоуровневой основе не только упрощаетпроверку и отладку вычислителя; такое встраивание к тому же позволяет разработчикуслизывать31 черты языка-основы, как наш встроенный интерпретатор Лиспа использовал примитивы и структуру управления нижележащего Лиспа.
Только позже (да и то невсегда) разработчику приходится брать на себя труд построения полной реализации нанизкоуровневом языке или в аппаратуре. В этом разделе и следующем мы изучаем некоторые вариации на тему Scheme, которые значительно увеличивают ее выразительнуюсилу.4.2.1. Нормальный порядок вычислений и аппликативный порядоквычисленийВ разделе 1.1, где мы начали обсуждение моделей вычисления, мы указали, чтоScheme — язык с аппликативным порядком вычисления (applicative-order language), аименно, что все аргументы процедур в Scheme вычисляются в момент вызова. Напротив,в языках с нормальным порядком вычисления (normal-order language) вычисление аргументов процедур задерживается до момента, когда действительно возникает нужда вих значениях.
Если вычисление аргументов процедур откладывается как можно дольше(например, до того момента, когда они требуются какой-либо элементарной процедуре),то говорят о ленивом вычислении (lazy evaluation)32 . Рассмотрим процедуру(define (try a b)(if (= a 0) 1 b))Выполнение (try 0 (/ 1 0)) в Scheme приводит к ошибке. При ленивых вычислениях никакой ошибки не возникнет. Вычисление выражения даст результат 1, поскольку каргументу (/ 1 0) обращаться не понадобится.Примером использования ленивых вычислений может служить процедура unless:(define (unless condition usual-value exceptional-value)(if condition exceptional-value usual-value))которую можно использовать в выражениях вроде31 Слизывать (snarf): «Брать, в особенности большой документ или файл, с целью использовать с разрешения владельца или без оного».
Пролизывать (snarf down): «Слизывать, иногда с дополнительным значениемвосприятия, переработки или понимания». (Эти определения были слизаны из Steele et al. 1983. См. такжеRaymond 1993.)32 Терминологическая разница между выражениями «ленивый» и «нормальный порядок вычислений» несколько размыта. Обычно «ленивый» относится к механизмам конкретных интерпретаторов, а «нормальный порядок»к семантике языков независимо от способа реализации. Однако разделение здесь не жесткое, и часто эти термины употребляются как синонимы.4.2. SCHEME с вариациями: ленивый интерпретатор371(unless (= b 0)(/ a b)(begin (display "exception: returning 0")0))В аппликативном языке это не будет работать, потому что и обычное значение, и значение исключения будут выполнены еще до вызова unless (См.
упражнение 1.6). Преимущество ленивых вычислений в том, что некоторые процедуры, например, та же unless,могут выполнять полезные действия, даже если вычисление некоторых их аргументовспособно привести к ошибке или бесконечному циклу.Если тело процедуры начинает выполняться прежде, чем вычисляется ее аргумент, топроцедура называется нестрогой (non-strict) по этому аргументу. Если же аргумент вычисляется прежде, чем происходит вход в процедуру, то процедура называется строгой(strict) по этому аргументу33. В чисто аппликативном языке все процедуры строги повсем своим аргументам.
В языке с чисто нормальным порядком вычислений все составные процедуры нестроги по всем своим аргументам, а элементарные процедуры могутбыть и такими, и такими. Бывают также языки (см. упражнение 4.31), которые даютпрограммисту возможность явно обозначать строгость определяемых им процедур.Яркий пример процедуры, которой может быть полезно оказаться нестрогой, — этоcons (и вообще почти любой конструктор структур данных).
Можно производить полезные вычисления, составлять из элементов структуры данных и работать с ними, дажеесли значения элементов неизвестны. Вполне имеет смысл задача, например, посчитатьдлину списка, не зная значений его отдельных элементов. В разделе 4.2.3 мы развиваемэту идею и реализуем потоки из главы 3 в виде списков, составленных из нестрогихcons-пар.Упражнение 4.25.Предположим, что мы (в обычной Scheme с аппликативным порядком вычислений) определяемunless как показано выше, а затем определяем factorial через unless:(define (factorial n)(unless (= n 1)(* n (factorial (- n 1)))1))Что произойдет, если мы попытаемся вычислить (factorial 5)? Будут ли наши определенияработать в языке с нормальным порядком вычислений?Упражнение 4.26.Бен Битобор и Лиза П. Хакер расходятся во мнениях о важности ленивых вычислений для реализации конструкций вроде unless.
Бен указывает, что при аппликативном порядке unlessможно реализовать как особую форму. Лиза отвечает, что в таком случае unless будет простосинтаксисом, а не процедурой, которую можно использовать в сочетании с процедурами высших33 Термины «строгий» и «нестрогий» означают, в сущности, то же самое, что «аппликативный» и «нормальный» порядок вычислений, но только они относятся к отдельным процедурам и их аргументам, а не к языкув целом. На конференциях по языкам программирования можно услышать, как кто-нибудь говорит: «В языке Hassle с нормальным порядком вычислений есть несколько строгих примитивов.
Остальные процедурыпринимают аргументы через ленивое вычисление».372Глава 4. Метаязыковая абстракцияпорядков. Проясните детали в обеих позициях. Покажите, как реализовать unless в виде производного выражения (вроде cond или let), и приведите пример ситуации, когда имеет смысл,чтобы unless была процедурой, а не особой формой.4.2.2.
Интерпретатор с ленивым вычислениемВ этом разделе мы реализуем язык с нормальным порядком вычислений, которыйотличается от Scheme только тем, что все составные процедуры по всем аргументамнестроги. Элементарные процедуры по-прежнему будут строгими. Совсем несложно, модифицируя интерпретатор из раздела 4.1.1, добиться, чтобы интерпретируемый язык велсебя таким образом. Почти что все требуемые изменения сосредоточены вокруг механизма процедурного вызова.Основная идея состоит в том, что при вызове процедуры интерпретатор должен определить, какие аргументы требуется вычислить, а какие задержать. Задержанные аргументы не вычисляются, а преобразуются в объекты, называемые санками (thunks)34∗ .В санке должна содержаться информация, необходимая, чтобы вычислить значение аргумента, когда оно потребуется, и сделать это так, как будто оно вычислено во времявызова.
Таким образом, санк должен содержать выражение-аргумент и окружение, вкотором вычисляется вызов процедуры.Процесс вычисления санка называется вынуждением (forcing a thunk)35 Вообще говоря, санк вынуждается только тогда, когда требуется его значение: когда он передаетсяв элементарную процедуру, использующую его значение; когда он служит предикатом вусловном выражении; или когда он является значением оператора, который нужно применить как процедуру. Мы должны решить, будем ли мы мемоизировать (memoize)санки, как мы делали с задержанными объектами в разделе 3.5.1. При использованиимемоизации, когда санк вынуждается в первый раз, он запоминает вычисленное значение.
Последующие вызовы только возвращают запомненное значение, не вычисляя егозаново. Мы делаем выбор в пользу мемоизации, поскольку для многих приложений этоэффективнее. Здесь, однако, имеются тонкости36.34 Название «санк» было придумано в неформальной группе, которая обсуждала реализацию вызова по именив Алголе 60. Было замечено, что большую часть анализа («обдумывания», thinking about) выражения можнопроизводить во время компиляции; таким образом, во время выполнения выражение будет уже большей частью«обдумано» (thunk about — намеренно неверно образованная английская форма) (Ingerman et al.
1960).∗ В русскоязычной литературе слово thunk иногда переводится как «переходник». Нам кажется, что в данномслучае такой перевод мешал бы пониманию текста. — прим. перев.35 Это аналогично использованию слова force («вынудить», «заставить») для задержанных объектов, припомощи которых в главе 3 представлялись потоки. Основная разница между тем, что мы делаем здесь, итем, чем мы занимались в главе 3, состоит в том, что теперь мы встраиваем задержку и вынуждение винтерпретатор, и они применяются автоматически и единообразно во всем языке.36 Ленивые вычисления, совмещенные с мемоизацией, иногда называют методом передачи аргументов свызовом по необходимости (call by need), в отличие от вызова по имени (call by name). (Вызов по имени,введенный в Алголе 60, аналогичен немемоизированному ленивому вычислению.) Как проектировщики языкамы можем сделать интерпретатор мемоизирующим или немемоизирующим, или же оставить это на усмотрениепрограммистов (упражнение 4.31).
Как можно было ожидать из главы 3, этот выбор вызывает к жизни вопросы,особенно тонкие и запутанные в присутствии присваивания. (См. упражнения 4.27 и 4.29.) В замечательнойстатье Клингера (Clinger 1982) делается попытка прояснить многомерную путаницу, которая здесь возникает.4.2. SCHEME с вариациями: ленивый интерпретатор373Преобразование интерпретатораОсновная разница между ленивым интерпретатором и интерпретатором из раздела 4.1.1 состоит в обработке вызовов процедур внутри eval и apply.Ветка application? в eval принимает вид((application? exp)(apply (actual-value (operator exp) env)(operands exp)env))Это почти тот же код, что был в ветке application? в eval из раздела 4.1.1.
Однакопри ленивом вычислении мы зовем apply с выражениями операндов, а не с аргументами, которые получаются при их вычислении. Мы также передаем apply окружение,поскольку оно понадобится для построения санков, если нам хочется, чтобы аргуметы вычислялись с задержкой. Оператор мы по-прежнему вычисляем, потому что самаприменяемая процедура нужна apply, чтобы выбрать действие на основании ее типа(элементарная или составная) и применить ее.Всякий раз, когда нам требуется собственно значение выражения, мы вместо простогоeval пользуемся процедурой(define (actual-value exp env)(force-it (eval exp env)))чтобы, если значение выражения является санком, оно было вынуждено.Наша новая версия apply также почти совпадает с версией из раздела 4.1.1.
Разницасостоит в том, что eval передает ей невычисленные выражения: для элементарныхпроцедур (они строгие) мы вычисляем все аргументы и затем вызываем примитив; длясоставных процедур (они нестрогие) мы прежде применения процедуры замораживаемвсе аргументы.(define (apply procedure arguments env)(cond ((primitive-procedure? procedure)(apply-primitive-procedureprocedure(list-of-arg-values arguments env))) ; изменение((compound-procedure? procedure)(eval-sequence(procedure-body procedure)(extend-environment(procedure-parameters procedure)(list-of-delayed-args arguments env) ; изменение(procedure-environment procedure))))(else(error"Неизвестный тип процедуры -- APPLY" procedure))))Процедуры, обрабатывающие аргументы, почти такие же, как list-of-values из раздела 4.1.1, но только list-of-delayed-args замораживает аргументы, вместо того,чтобы их вычислять, а в list-of-arg-values вместо eval используется actualvalue:374Глава 4.
Метаязыковая абстракция(define (list-of-arg-values exps env)(if (no-operands? exps)’()(cons (actual-value (first-operand exps) env)(list-of-arg-values (rest-operands exps)env))))(define (list-of-delayed-args exps env)(if (no-operands? exps)’()(cons (delay-it (first-operand exps) env)(list-of-delayed-args (rest-operands exps)env))))Кроме того, нам требуется изменить в интерпретаторе обработку if, где вместо evalмы должны вызывать actual-value, чтобы значение предикатного выражения вычислялось прежде, чем мы проверим, истинно оно или ложно:(define (eval-if exp env)(if (true? (actual-value (if-predicate exp) env))(eval (if-consequent exp) env)(eval (if-alternative exp) env)))Наконец, нужно изменить процедуру driver-loop (раздел 4.1.4), чтобы она звалаactual-value вместо eval.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
