Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 103

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 103)

Эта операцияподобна унификации.Упражнение 4.77.В разделе 4.4.3 мы видели, что выражения not и lisp-value могут заставить язык запросоввыдавать «неправильные» значения, если эти фильтрующие операции применяются к кадрам снесвязанными переменными. Придумайте способ избавиться от этого недостатка. Одна из возможностей состоит в том, чтобы проводить «задержанную» фильтрацию, цепляя к кадру «обещание»провести ее, которое выполняется только тогда, когда связано достаточно переменных, чтобы операция стала возможна.

Можно ждать и проводить фильтрацию только тогда, когда выполнены всеостальные операции. Однако из соображений эффективности хотелось бы фильтровать как можнораньше, чтобы уменьшить число порождаемых промежуточных кадров.Упражнение 4.78.Перестройте язык запросов в виде недетерминистской программы, реализуемой интерпретаторомиз раздела 4.3, а не в виде процесса обработки потоков.

При таком подходе каждый запрос будетпорождать один ответ (а не поток всех возможных ответов), а пользователь может ввести tryagain и получить следующий ответ. Вы увидите, что существенная часть механизмов, которыемы построили в этом разделе, заменяется недетерминистским поиском и перебором с возвратами.Однако помимо этого, Вы обнаружите, что новый язык запросов отличается в тонких деталях поведения от реализованного нами в этом разделе. Можете ли Вы привести примеры, показывающиеэти отличия?Упражнение 4.79.Когда мы реализовывали в разделе 4.1 интерпретатор, мы видели, как можно избежать конфликтовмежду именами параметров процедур при помощи локальных окружений.

Например, при вычислении(define (square x)(* x x))(define (sum-of-squares x y)(+ (square x) (square y)))(sum-of-squares 3 4)4.4. Логическое программирование449не возникает смешения между x из square и x из sum-of-squares, поскольку тело каждойпроцедуры мы вычисляем в окружении, которое специально построено для связывания локальных переменных. В запросной системе мы избегаем конфликтов имен при применении правилс помощью другой стратегии. Каждый раз при применении правила мы переименовываем переменные и даем им новые имена, которые обязаны быть уникальными. Аналогичная стратегия винтерпретаторе Лиспа заключалась бы в том, чтобы отменить внутренние окружения и простопереименовывать переменные в теле процедуры каждый раз, как мы ее вызываем.Реализуйте для языка запросов метод применения правил, который использует не переименования, а окружения.

Рассмотрите, можно ли использовать Вашу систему окружений для построенияв языке запросов конструкций для работы с большими системами, например аналога блочнойструктуры процедур для правил. Можно ли связать это с проблемой ведения рассуждений в контексте (например: «Если бы я предположил, что истинно P , то я смог бы доказать A и B»)в качестве метода решения задач? (Это упражнение не имеет однозначного решения. Хорошийответ, скорее всего, мог бы служить темой диссертации.)ГЛАВА 5ВЫЧИСЛЕНИЯНА РЕГИСТРОВЫХ МАШИНАХМоя цель — показать, что небеснаямашина не некое божественное живоесущество, а скорее часовой механизм (атот, кто верит, что у часов есть душа,приписывает славу творца творению),поскольку почти все из еемногочисленных движений вызываютсяпростейшей материальной силой, так же,как все движения часов вызываютсявесом гири.Иоганн Кеплер(письмо к Герварту фон Гогенбургу, 1605)Эта книга начинается с изучения процессов и с описания процессов в терминахпроцедур, написанных на Лиспе.

Чтобы объяснить значение этих процедур, мы последовательно использовали несколько моделей вычисления: подстановочную модель из главы 1, модель с окружениями из главы 3 и метациклический интерпретатор из главы 4.Изучая последний, мы по большей части сняли покров тайны с деталей интерпретациилиспоподобных языков.

Однако даже метациклический интерпретатор оставляет многиевопросы без ответа, поскольку он не проясняет механизмы управления Лисп-системы.Например, интерпретатор не показывает, как при вычислении подвыражения удается вернуть значение выражению, это значение использующему, или почему одни рекурсивныепроцедуры порождают итеративные процессы (то есть занимают неизменный объем памяти), в то время как другие процедуры порождают рекурсивные процессы.

Эти вопросыостаются без ответа потому, что метациклический интерпретатор сам по себе являетсяпрограммой на Лиспе, а следовательно, наследует управляющую структуру нижележащей Лисп-системы. Чтобы предоставить более полное описание управляющей структурывычислителя Лиспа, нам нужно работать на более элементарном уровне, чем сам Лисп.В этой главе мы будем описывать процессы в терминах пошаговых операций традиционного<b>Текст обрезан, так как является слишком большим</b>.

Характеристики

Список файлов книги