Глава 4 Метаязыковая абстракция

... Именно в словах кроется магия - в таких, как «абракадабра», «Сезам, откройся» и проч., - но магические слова из одной истории перестают быть таковыми в следующей. Настоящая магия состоит в том, чтобы понять, когда и для чего слово сработает; трюк в том, чтобы выучить трюк. ... А слова эти состоят из букв нашего алфавита: пара дюжин закорючек, которые мы способны черкнуть пером. Вот где ключ. . . ! И сокровище тоже, если только мы сумеем его заполучить! Как будто. . . как будто ключ к сокровищу и есть само сокровище!

Джон Барт. «Химера»

(Перевод Виктора Лапицкого)

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

1 Та же самая идея встречается во всех областях техники. Например, у инженеров-электронщиков существует множество языков для описания схем. Два из них - это язык электрических сетей и язык электрических систем. Язык сетей делает акцент на физическом моделировании устройств в терминах дискретных электрических элементов. Элементарными объектами этого языка являются элементарные электрические компоненты - резисторы, конденсаторы, катушки индуктивности

Программирование изобилует языками. Есть физические языки, например, языки машинных кодов для конкретных компьютеров. Основным вопросом для них является представление данных и управления через отдельные биты памяти и машинные команды. Пишущий программы на машинном языке озабочен тем, чтобы при помощи данной аппаратуры создать системы и инструменты для эффективной реализации вычисления при ограниченных ресурсах. Языки высокого уровня, возводимые поверх машинных, скрывают вопросы конкретной реализации данных в виде набора битов и представления программ как последовательности машинных команд. В этих языках присутствуют средства комбинации и абстракции, например определения функций, которые подходят для более крупномасштабной организации систем.

Метаязыковая абстракция (metalinguistic abstraction), то есть построение новых языков, играет важную роль во всех отраслях инженерного проектирования. Для компьютерного программирования она особенно важна, поскольку в программировании мы можем не только формулировать новые языки, но и ре-ализовывать их через построение вычислителей. Вычислитель (evaluator) (или интерпретатор (interpreter)) для языка программирования - это процедура, которая, будучи примененной к выражению языка, производит действия, необходимые для вычисления этого выражения.

Без преувеличения можно сказать, что самая основополагающая идея в программировании такова:

Вычислитель, который определяет значение выражений в языке программирования - всего лишь обычная программа.

С этой мыслью приходит и новое представление о себе самих: мы начинаем видеть в себе разработчиков языков, а не просто пользователей языков, придуманных другими.

На самом деле, почти любую программу можно рассматривать как вычислитель для какого-то языка. Например, система работы с многочленами из раздела 2.5.3 заключает в себе правила арифметики многочленов и реализует их в терминах операций над данными в списочной форме. Если мы дополним эту систему процедурами для чтения и печати многочленов, то перед нами окажется ядро специализированного языка для решения задач символьной математики. И программа моделирования цифровой логики из раздела 3.3.4, и программа распространения ограничений из раздела 3.3.5 содержат свои собственные языки, со своими примитивами, средствами их комбинирования и абстракции. С этой точки зрения, техника работы с крупномасштабными компьютерными системами сливается с техникой создания новых компьютерных языков, и вся информатика - не более (но и не менее), чем наука о построении подходящих языков описания.

и транзисторы, задаваемые через физические переменные: напряжение и ток. Описывая схемы на языке сетей, инженер озабочен физическими характеристиками своего проекта. Элементами системного языка, напротив, являются модули обработки сигнала, например, фильтры и усилители. Существенно только функциональное поведение модулей, и сигналами манипулируют безотносительно к тому, в виде какого напряжения или тока они реализуются физически. Язык систем построен на языке сетей, в том смысле, что элементы систем обработки сигнала состоят из электрических схем. Однако здесь инженера интересует крупномасштабная организация электрических устройств, решающая определенную задачу; их физическая совместимость подразумевается. Такая послойная организация языков служит еще одним примером уровневого метода проектирования, проиллюстрированного в разделе 2.2.4 на примере языка описания изображений.

Сейчас мы начинаем обзор методов, которые позволяют создавать одни языки на основе других. В этой главе в качестве основы мы будем использовать Лисп, и вычислители будем реализовывать как процедуры на Лиспе. Лисп особенно хорошо подходит для этой задачи благодаря своей способности представлять символические выражения и обрабатывать их. Первый шаг к пониманию того, как реализуются языки, мы сделаем, построив вычислитель для самого Лиспа. Язык, реализуемый нашим интерпретатором, будет подмножеством диалекта Лиспа Scheme, которым мы пользуемся в этой книге. Несмотря на то, что интерпретатор, описанный в этой главе, написан для конкретного диалекта Лиспа, он содержит основную структуру вычислителя для любого языка, ориентированного на выражения и предназначенного для написания программ для последовательной машины. (На самом деле, глубоко внутри большинства языковых процессоров содержится маленький интерпретатор «Лиспа».) Этот интерпретатор несколько упрощен для удобства и наглядности обсуждения, и некоторые детали, которые важно было бы включить в Лисп-систему промышленного качества, здесь были оставлены за рамками изложения. Тем не менее, этот простой интерпретатор способен выполнить большинство программ из данной книги.2

Важное преимущество, которое нам дает вычислитель, доступный в виде программы на Лиспе, состоит в том, что мы можем реализовывать альтернативные правила вычисления, описывая их как модификации программы вычислителя. В частности, мы можем извлечь из этой способности немалую выгоду, добиваясь более полного контроля над тем, как в вычислительных моделях реализуется понятие времени. Этому вопросу была специально посвящена глава 3. Там мы смягчили некоторые сложности работы с состоянием и присваиваниями, при помощи потоков отделив представление времени во внешнем мире от времени внутри компьютера. Однако программы, работающие с потоками, иногда бывали излишне громоздки, поскольку их ограничивал аппликативный порядок вычисления, принятый в Scheme. В разделе 4.2 мы изменим язык и получим более изящный подход в виде интерпретатора с нормальным порядком вычисления (normal-order evaluation).

В разделе 4.3 язык меняется более радикально, и выражения получают не одно единственное значение, а множество. В этом языке недетерминистских вычислений (nondeterministic computing) становится естественным порождать все возможные значения выражения, а затем искать среди них те, которые удовлетворяют определенным ограничениям. Если описывать это в терминах вычисления и времени, то время как будто разветвляется на множество «возможных будущих», и мы ищем среди них подходящие временные линии. При работе с недетерминистским интерпретатором отслеживание множества значений и поиск осуществляются автоматически встроенными механизмами языка.

В разделе 4.4 мы реализуем язык логического программирования (logic programming), в котором знание выражается в терминах отношений, а не в терминах вычислений со входами и выходами. Несмотря на то, что язык при этом оказывается сильно отличным от Лиспа, как, впрочем, и от любого привычного языка, мы увидим, что интерпретатор для языка

2Самое важное, чего не хватает в нашем интерпретаторе, - это механизмов, обрабатывающих ошибки и поддерживающих отладку. Более подробное обсуждение вычислителей можно найти в книге Friedman, Wand, and Haynes 1992, которая содержит обзор языков программирования на примере последовательности интерпретаторов, написанных на Scheme.