Structure and Interpretation of Computer Programs, 2e: Chapter 4
Изучая дизайн программ в [SICP], мы видим что опытные программисты управляют сложностью своих проектов с помощью тех же общих методов, которые используются разработчиками всех сложных систем. Они
Проиллюстрировав эти методы, мы использовали Лисп как язык для описания процессов и для создания вычислительных объектов данных и процессов для моделирования сложных явлений в реальном мире. Однако по мере того, как мы сталкиваемся со все более сложными проблемами, мы обнаруживаем, что Lisp или любой фиксированный язык программирования недостаточен для наших нужд. Мы должны постоянно обращаться к новым языкам, чтобы более эффективно выражать наши идеи. Определение новых языков -- мощная стратегия контроля сложности инженерного проектирования; мы часто можем улучшить нашу способность справляться со сложной проблемой, применив новый язык, который позволяет нам описывать (и, следовательно, думать о ней) проблему по-другому, используя примитивы, средства комбинирования и средства абстракции, которые особенно важны, и хорошо подходят для решения поставленной задачи. [205]
Программирование всегда тесно связано с множеством языков. Существуют физически низкоуровневые языки, например машинные языки для компьютеров определенной архитектуры. Эти языки предназначены для представления данных и управления в терминах отдельных битов памяти, и примитивных машинных инструкций. Программист, работающий на машинном языке, заинтересован в использовании данного оборудования для создания систем и утилит для максимально эффективной реализации вычислений в ограниченных ресурсах. Языки высокого уровня, выращенные поверх машинного языка, скрывают заботы по поводу представления данных в виде наборов битов в памяти, и представления программ в виде последовательностей примитивных инструкций. В этих языках есть средства комбинирования и абстракции, такие как определение процедур, которые подходят для крупномасштабной организации систем.
Металингвистическая абстракция — создание новых языков -- играет важную роль во всех отраслях инженерного проектирования. Это особенно важно для компьютерного программирования, потому что в программировании мы можем не только формулировать новые языки, но и реализовывать эти языки, создавая вычислители. Вычислитель (или интерпретатор) для языка программирования — это процедура, которая при применении к выражению языка выполняет действия, необходимые для оценки (evaluate) этого выражения.
Не будет преувеличением считать это самой фундаментальной идеей программирования:
вычислитель (evaluator), который определяет значение выражений на некотором языке программирования -- это просто еще одна программа
Понять это -- значит изменить наше представление о себе как о программистах. Мы начинаем видеть себя разработчиками языков, а не только пользователями языков, созданных другими.
Фактически, мы можем рассматривать почти любую программу как средство вычисления, зананное для некоторого языка. Например, система манипулирования полиномами из 2.5.3 следует правилам полиномиальной арифметики, и реализует их в терминах операций со структурированными списковыми данными. Если мы дополним эту систему процедурами чтения и печати полиномиальных выражений, мы получим ядро специализированного языка для решения задач символьной математики. Симулятор цифровой логики 3.3.4 и распространитель ограничений 3.3.5 явно являются самостоятельными языками сами по себе, каждый со своими примитивами, средствами комбинирования и средствами абстракции. С этой точки зрения, технология взаимодействия с крупномасштабными компьютерными системами сливается с технологией создания новых компьютерных языков, а сама информатика становится не более (и не менее) чем дисциплиной по созданию соответствующих описательных языков.
Теперь мы можем отправиться в путешествие по технологии, с помощью которой языки устанавливаются по отношению к другим языкам. В 4 главе [SICP][ мы будем использовать Lisp в качестве основы, реализуя собственные средства интерпретации как процедуры Lisp. Lisp особенно хорошо подходит для этой задачи из-за его способности представлять и манипулировать символьными выражениями. Мы сделаем первый шаг в понимании того, как реализуются языки, создав вычислитель для самого Lisp. Язык, реализованный нашим вычислителем, будет подмножеством диалекта Scheme Lisp, который мы используем в этой книге. Хотя вычислитель, описанный в этой главе, написан для определенного диалекта Лиспа, он содержит основную структуру интерпретатора для любого языка, ориентированного на выражения, предназначенного для написания программ для последовательной машины. (Фактически, большинство программ работающих с языками, содержат в себе небольшой интерпретатор Lisp.) Оценщик был упрощен для целей иллюстрации и обсуждения, а болшинство функций, необхоимых для практически-применимой Лисп-системы, были опущены. Тем не менее этого простого интерпретатора достаточно для выполнения большинства программ из этой книги. [206]
Аналогично, в metaL мы меняем базовую структуру данных для представления программ, и применяем объектно-ориентированный подход вместо функционально-процедурного, но общие принципы реализации системы интерпретации объектного графа как его вычисления в некоторое значение (тоже граф) остается без изменений. Здесь и далее по тексту Lisp нужно читать как Python.
Отдельно стоит отметить, что, хотя традиционно принято иметь некоторое хранимое представление программ в виде текстовых файлов, наличие синтаксиса для языка вообще говоря не обязательно. Язык полезно определить не на последовательностях символов, представляющих программы, а на данных, то есть рассматривать в качестве непосредственного представления программ некоторые прозвольно выбранные структуры данных. В этом случае мы можем полагаться при работе на все механизмы, уже существующие в языке реализации -- готовый общеизвестный синтаксис и его парсер, отладчик, менеджер памяти, любые существующие библиотеки и готовую инфраструктуру.
Важным преимуществом доступности интерпретатора как обычной программы на Лиспе является то, что мы можем реализовать альтернативные правила вычисления, описывая их как модификации программы-вычислителя. Одно из мест, где мы можем использовать эту силу для получения хорошего эффекта, — это получить дополнительный контроль над тем, как вычислительные модели воплощают понятие времени, которое было центральным в обсуждении в главе 3. Здесь мы смягчили некоторые сложности, связанные с состоянием и присваиванием, используя потоки для разделения представления времени в мире от времени в компьютере. Однако наши потоковые программы иногда были громоздкими, потому что они ограничивались аппликативнам порядком вычислений Scheme. В 4.2 мы изменим базовый язык, чтобы обеспечить более элегантный подход, изменив интерпретатор так, чтобы обеспечить вычисление в нормальном порядке.
В разделе 4.3 реализовано более амбициозное лингвистическое изменение, согласно которому выражения имеют много значений, а не одно единственное. На этом языке недетерминированных вычислений естественно выражать процессы, которые генерируют все возможные значения для выражения, а затем отбирают те значения, которые удовлетворяют определённым ограничениям. С точки зрения моделей вычислений и времени, это похоже на разветвление времени на набор «возможных вариантов будущего» и последующий поиск подходящих временных линий. С нашим недетерминированным интерпретатором вычисление нескольких значений и выполнение поиска автоматически обрабатываются внутренним механизмом языка.
В 4.4 мы реализуем язык логического программирования, в котором знания выражаются в терминах отношений, а не в терминах вычислений со входами и выходами. Несмотря на то, что это резко отличает язык от Лиспа или даже от любого обычного языка, мы увидим, что вычислитель для логического программирования разделяет ту же необходимую структуру интерпретатора Лиспа.