Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 78
Текст из файла (страница 78)
Например, система работы с многочленами из раздела 2.5.3 заключает в себе правила арифметики многочленов и реализует их в терминах операций надданными в списочной форме. Если мы дополним эту систему процедурами для чтенияи печати многочленов, то перед нами окажется ядро специализированного языка длярешения задач символьной математики. И программа моделирования цифровой логикииз раздела 3.3.4, и программа распространения ограничений из раздела 3.3.5 содержатсвои собственные языки, со своими примитивами, средствами их комбинирования и абстракции. С этой точки зрения, техника работы с крупномасштабными компьютернымисистемами сливается с техникой создания новых компьютерных языков, и вся информатика — не более (но и не менее), чем наука о построении подходящих языков описания.Сейчас мы начинаем обзор методов, которые позволяют создавать одни языки наских элементов.
Элементарными объектами этого языка являются элементарные электрические компоненты —резисторы, конденсаторы, катушки индуктивности и транзисторы, задаваемые через физические переменные:напряжение и ток. Описывая схемы на языке сетей, инженер озабочен физическими характеристиками своегопроекта. Элементами системного языка, напротив, являются модули обработки сигнала, например, фильтрыи усилители. Существенно только функциональное поведение модулей, и сигналами манипулируют безотносительно к тому, в виде какого напряжения или тока они реализуются физически. Язык систем построен наязыке сетей, в том смысле, что элементы систем обработки сигнала состоят из электрических схем. Однакоздесь инженера интересует крупномасштабная организация электрических устройств, решающая определенную задачу; их физическая совместимость подразумевается. Такая послойная организация языков служит ещеодним примером уровневого метода проектирования, проиллюстрированного в разделе 2.2.4 на примере языкаописания изображений.337основе других.
В этой главе в качестве основы мы будем использовать Лисп, и вычислители будем реализовывать как процедуры на Лиспе. Лисп особенно хорошо подходитдля этой задачи благодаря своей способности представлять символические выражения иобрабатывать их. Первый шаг к пониманию того, как реализуются языки, мы сделаем,построив вычислитель для самого Лиспа. Язык, реализуемый нашим интерпретатором,будет подмножеством диалекта Лиспа Scheme, которым мы пользуемся в этой книге.Несмотря на то, что интерпретатор, описанный в этой главе, написан для конкретногодиалекта Лиспа, он содержит основную структуру вычислителя для любого языка, ориентированного на выражения и предназначенного для написания программ для последовательной машины. (На самом деле, глубоко внутри большинства языковых процессоровсодержится маленький интерпретатор «Лиспа».) Этот интерпретатор несколько упрощендля удобства и наглядности обсуждения, и некоторые детали, которые важно было бывключить в Лисп-систему промышленного качества, здесь были оставлены за рамкамиизложения.
Тем не менее, этот простой интерпретатор способен выполнить большинствопрограмм из данной книги.2Важное преимущество, которое нам дает вычислитель, доступный в виде программына Лиспе, состоит в том, что мы можем реализовывать альтернативные правила вычисления, описывая их как модификации программы вычислителя. В частности, мы можемизвлечь из этой способности немалую выгоду, добиваясь более полного контроля надтем, как в вычислительных моделях реализуется понятие времени. Этому вопросу быласпециально посвящена глава 3.
Там мы смягчили некоторые сложности работы с состоянием и присваиваниями, при помощи потоков отделив представление времени во внешнем мире от времени внутри компьютера. Однако программы, работающие с потоками,иногда бывали излишне громоздки, поскольку их ограничивал аппликативный порядоквычисления, принятый в Scheme. В разделе 4.2 мы изменим язык и получим более изящный подход в виде интерпретатора с нормальным порядком вычисления (normal-orderevaluation).В разделе 4.3 язык меняется более радикально, и выражения получают не одноединственное значение, а множество.
В этом языке недетерминистских вычислений(nondeterministic computing) становится естественным порождать все возможные значения выражения, а затем искать среди них те, которые удовлетворяют определеннымограничениям. Если описывать это в терминах вычисления и времени, то время как будто разветвляется на множество «возможных будущих», и мы ищем среди них подходящие временные линии. При работе с недетерминистским интерпретатором отслеживаниемножества значений и поиск осуществляются автоматически встроенными механизмамиязыка.В разделе 4.4 мы реализуем язык логического программирования (logicprogramming), в котором знание выражается в терминах отношений, а не в терминахвычислений со входами и выходами. Несмотря на то, что язык при этом оказываетсясильно отличным от Лиспа, как, впрочем, и от любого привычного языка, мы увидим,что интерпретатор для языка логического программирования имеет, в сущности, ту жеструктуру, что и интерпретатор Лиспа.2 Самое важное, чего не хватает в нашем интерпретаторе, — это механизмов, обрабатывающих ошибки иподдерживающих отладку.
Более подробное обсуждение вычислителей можно найти в книге Friedman, Wand,and Haynes 1992, которая содержит обзор языков программирования на примере последовательности интерпретаторов, написанных на Scheme.338Глава 4. Метаязыковая абстракция4.1. Метациклический интерпретаторНаш интерпретатор Лиспа будет реализован как программа на Лиспе.
Может показаться, что размышления о выполнении Лисп-программ при помощи интерпретатора,который сам написан на Лиспе, составляют порочный круг. Однако вычисление естьпроцесс, так что вполне логично описывать процесс вычисления с помощью Лиспа — вконце концов, это наш инструмент для описания процессов3 . Интерпретатор, написанныйна языке, который он сам реализует, называется метациклическим (metacircular).В сущности, метациклический интерпретатор является формулировкой на языкеScheme модели вычислений с окружениями, описанной в разделе 3.2.
Напомним, чтов этой модели было две основные части:• Чтобы выполнить комбинацию (составное выражение, не являющееся особой формой), нужно вычислить его подвыражения и затем применить значение подвыраженияоператора к значениям подвыражений-операндов.• Чтобы применить составную процедуру к набору аргументов, нужно выполнитьтело процедуры в новом окружении.
Для того, чтобы построить это окружение, нужно расширить окружение объекта-процедуры кадром, в котором формальные параметрыпроцедуры связаны с аргументами, к которым процедура применяется.Эти два правила описывают сущность процесса вычисления, основной цикл, в котором выражения, которые требуется выполнить в окружении, сводятся к процедурам,которые нужно применить к аргументам, а те, в свою очередь, сводятся к новым выражениям, которые нужно выполнить в новых окружениях, и так далее, пока мы недоберемся до символов, чьи значения достаточно найти в окружении, и элементарныхпроцедур, которые применяются напрямую (см. рис. 4.1)4 .
Этот цикл вычисления будет построен в виде взаимодействия двух основных процедур интерпретатора, eval иapply, описанных в разделе 4.1.1 (см. рис. 4.1).3 Даже с учетом этого, остаются важные стороны процесса вычисления, которые в нашем интерпретаторене проясняются.
Самая важная из них — точные механизмы того, как одни процедуры вызывают другиеи возвращают значения процедурам, которые их вызвали. Эти вопросы мы рассмотрим в главе 5, где мыисследуем процесс вычисления более внимательно, реализуя вычислитель как простую регистровую машину.4 Если нам дается возможность применять примитивы, то что остается сделать для реализации интерпретатора? Задача интерпретатора состоит не в том, чтобы определить примитивы языка, а в том, чтобы обеспечитьсвязующие элементы — средства комбинирования и абстракции, — которые превращают набор примитивов вязык.
А именно:• Интерпретатор позволяет работать с вложенными выражениями. Например, чтобы вычислить значениевыражения (+ 1 6), достаточно применения примитивов, но этого недостаточно для работы с выражением(+ 1 (* 2 3)). Сама по себе элементарная процедура + способна работать только с числами, и если передать ей аргумент — выражение (* 2 3), она сломается. Одна из важных задач интерпретатора — устроитьвычисление так, чтобы (* 2 3) свелось к значению 6, прежде чем оно будет передано + как аргумент.• Интерпретатор позволяет использовать переменные. Например, элементарная процедура сложения незнает, как работать с выражениями вроде (+ x 1).
Нам нужен интерпретатор, чтобы следить за переменнымии получать их значения, прежде чем запускать элементарные процедуры.• Интерпретатор позволяет определять составные процедуры. При этом нужно хранить определения процедур, знать, как эти определения используются при вычислении выражений, и обеспечивать механизм, который позволяет процедурам принимать аргументы.• Интерпретатор дает особые формы, вычисляющиеся иначе, чем вызовы процедур.4.1. Метациклический интерпретатор339процедура,аргументывыражение,EvalApplyокружениеРис.
4.1. Цикл eval–apply раскрывает сущность компьютерного языка.Реализация интерпретатора будет зависеть от процедур, определяющих синтаксис(syntax) выполняемых выражений. При помощи абстракции данных мы сделаем интерпретатор независимым от представления языка. К примеру, вместо того, чтобы окончательно решать, что присваивание выражается в виде списка, в котором первым элементом стоит символ set!, мы пользуемся абстрактным предикатом assignment?, чтобы распознавать присваивание, и абстрактными селекторами assignment-variable иassignment-value, чтобы обращаться к его частям. Реализация выражений будет подробно рассмотрена в разделе 4.1.2. Имеются также операции, описанные в разделе 4.1.3,которые определяют представление процедур и окружений. Например, make-procedure порождает составные процедуры, lookup-variable-value извлекает значенияпеременных, а apply-primitive-procedure применяет элементарную процедуру куказанному списку аргументов.4.1.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
