Готовый перевод Let Over Lambda - 50 Years of Lisp / Let Over Lambda - 50 лет Lisp-у: Глава 8 - Лисп, переходящий в Форт, переходящий в Лисп

8.1 Причудливая Архитектура

Эта глава - кульминация многих, увиденных ранее в этой книге макро техник. Используя абстракции из написанных нами макросов мы создадим реализацию одного из моих самых любимых языков программирования: forth. И хотя эта реализация воплощает многие идеи форта, она очень отличается от форта и является лисповой. Несмотря на то, что код приведённый в этой главе можно использовать в других интересных целях, его главным назначением является обучение основам и концепциям метапрограммирования форта для лисп аудитории и использование в роли платформы для дискуссий по центральной теме этой книги - создание и использование дуализма синтаксиса в макросах.

Форт обладает богатой, захватывающей историей развития, в отличие от многих других языков, за исключением лиспа и я рад, что открыл форт для себя. По этой и другим причинам эта глава посвящена с любовью моему отцу Брайану Хойту, познакомившему меня с фортом и с программированием на компьютере. Эта глава частично вдохновлена [THREADING-LISP] и исследованием Генри Бейкера [LINEAR-LISP] [LINEAR-LISP-AND-FORTH].

Форт был первым языком программирования, который был создан и развивался без сильной правительственной, академической или корпоративной помощи - или по-крайней мере первый развившийся подобным образом язык. Вместо того, чтобы появиться в результате нужд большой организации, форт был создан независимо от всего Чаком Муром около 1968 года для решения его собственных вычислительных задач в астрономии, проектировании устройств и многого другого. После чего форт был распространён, реализован и улучшен силами многочисленного сообщества энтузиастов [EVOLUTION-FORTH-HOPL2]. В отличие от патронажа MIT (и позже DARPA) над ранними лиспами и COMMON LISP, IBM-овского FORTRAN-а и AT&T-шного юникс языка C.

В следствии происхождения и, в целом, другой философии роли компьютерного программного обеспечения и аппаратного обеспечения, форт стал иным. Даже больше чем лисп форт выглядит странным. Но как и в лиспе, странность форта обладает своей причиной: он был спроектирован больше для ума, чем для стиля. Форт странен своей архитектурой, и эта архитектура имеет отношение к макросам.

Сегодня форт чаще всего встречается в так называемых встраиваемых платформах - компьютерах с сильно ограниченными ресурсами. Это свидетельствует об архитектуре форта, как языке, который можно полностью реализовать на почти всех, когда либо созданных программируемых компьютерных системах. Форт спроектирован так, чтобы быть как можно более простым для реализации и экспериментов с ним. На самом деле создание клона форта настолько тривиально, что реализация форто-подобного стекового языка или нескольких языков является обязательным обрядом посвящения для программистов интересующихся архитектурой языков программирования. Некоторые стековые языки программирования восходят к форту, одними из интересных языков являются PostScript и Joy.

Часто важные решения при реализации форта основываются на непосредственных ресурсах компьютера на котором будет реализовываться форт. Форт программисты разработали набор абстрактных регистров, которые должны отображаться либо в настоящие регистры, либо располагаться в памяти или, возможно, реализуются какими-то другими способами. Но что если мы реализуем форт на лиспе, среде с неограниченным потенциалом и малыми ограничениями? Прежде чем начать отображать абстрактные регистры форта в лисп код, мы сделаем отступление. Как бы выглядел форт если бы у Чака была лисп машина? Чем подгонять форт к особенностям отдельной машины, настоящей или виртуальной, мы рассмотрим минимальный набор абстрактных регистров форта, оптимизированных для упрощения реализации при реализации на лиспе.

Листинг 8.1: FORTH-REGISTERS
(defvar forth-registers
’(pstack rstack pc
dict compiling dtab1e))

Вместо того, чтобы искать оптимальный набор абстрактных концепций, воспользуемся опытом Чака, создавшего десятки различных реализаций форта на многих архитектурах. Это то, что делает форт настолько замечательным. Как и лисп, форт предоставляет огромный простор в архитектуре языка и также, как и лисп, форт не столько язык программирования или набор стандартов, сколько строительный материал и набор знаний о том, что работает или не работает.

Переменная forth-registers - это список символов, представляющих абстрактные регистры нашей форт машины. Конечно, лисп не думает терминами регистров и целыми числами, а думает переменными и символами. Может показаться странным начинать нашу разработку форт среды всего лишь списком имён переменных, но этот факт всегда является первым шагом в реализации форт системы. Создание форта - это гениальный процесс самопостроения красивей и продуманней которого может быть только лисп. Небольшое описание этого процесса последует позже.

Одной из характерных особенностей форта является его прямой доступ к структуре стековых данных, используемый вашей программой и для передачи параметров подпрограммам и для отслеживания процесса выполнения программы через эти подпрограммы. Особенно интересен форт ещё и тем, что, в отличие от большинства языков программирования, разделяет эти два применения структуры стековых данных на два стека, которыми вы можете управлять непосредственно сами 1. В типичной C реализации параметры вызова функции и, так называемого адреса возврата, сохраняются в единственном кадре стека размером в переменную для каждого вызова функции. В форте они представляют из себя два различных стека под названием стек параметра и стек возврата, которые представлены нами как наши абстрактные регистры pstack и rstack. Мы используем макросы COMMON LISP push и pop для обозначения этих стеков, реализованных с помощью связанного списка cons ячеек взамен структур из массива данных, используемых в большинстве фортов.

1 Большинство языков вообще не позволяют управлять стеком.

Листинг 8.2: FORTH-WORD
(defstruct forth-word
name prev immediate thread)

Абстрактный регистр pc - это сокращение от program counter (счётчик программы), указатель на исполняемый в данный момент код. Что такое форт код, как мы можем ссылаться на него и для чего служат абстрактные регистры compiling и dtable будет описано позже.

Другим строительным блоком форта является концепция словаря. Словарь форта - это единый связанный список форт слов, аналогичных лисп функциям 2. Слова представлены лисп структурой. Структуры - это эффективные слот-ориентированные структуры данных, обычно реализуемые как векторы. Слот name предназначен для символа, используемого для поиска слова в словаре. Имейте в виду, что словарь форта составлен не в алфавитном, а в хронологическом порядке. Когда мы добавляем новые слова, то мы добавляем их в конец словаря, таким образом при проходе по словарю последние определённые слова будут рассматриваться первыми. Последний элемент нашего словаря всегда хранится в абстрактном регистре dict. Для прохода по словарю мы начинаем с dict и следуем по указателю prev в структуре слова, которое указывает либо на предыдущее определённое слово, либо на nil если текущее слово было последним словом 3.

2 Иначе говоря, они вовсе не функции, но скорее процедуры.

3 Да, иногда лисп программисты используют альтернативы cons ячейкам для связанных списков.

Дано w, искомое слово, и last, словарь, по-которому выполняется поиск, forth-lookup будет возвращать структуру форт слова или nil в зависимости от того, было ли найдено слово w в словаре или нет. Вместо eq было использовано слово eql, в отличие от лиспа, форт позволяет в качестве названий слова использовать цифры и другие не-символьные знаки.

Листинг 8.3:FORTH-LOOKUP
(defun forth-lookup (w last)
(if last
(if (eql (forth-word-name last) U)
last
(forth-lookup
H (forth-word-prev last)))))

Слот immediate нашего форт слова - это флаг, обозначающий признак незамедлительности слова. Незамедлительность - это концепция метапрограммирования форта, которую мы скоро будем серьёзно изучать. Ну а пока мы сделаем грубую аналогию с лиспом: незамедлительные слова похожи на лисп макросы тем, что это форт функции, выполняемые во время компиляции, а не во время выполнения. Что? Предполагалось что только в лиспе есть макросы. Правда в том, что макросистема COMMON LISP мощнее всех других макросистем - включая лучшие форт реализации - но форт обладает способностью расширения, превосходящей почти все остальные языки. Как и в лиспе, эта способность является результатом философии архитектуры: если это хорошо для автора реализации языка, то это достаточно хорошо и для разработчика приложений на этом языке. Как и лисп, форт не признаёт понятия примитива. Вместо этого предоставляется набор мета-примитивов, которые можно комбинировать для построения того языка, который хотите видеть вы, программист. Как и в лиспе, но не в Блаб языках, расширение языка новыми способами через применение макросов не только возможно, но и поощряется. Как и лисп, форт создан не из соображений стиля, но из соображений мощи.

8.2 Cons Шитый Код

В предыдущем разделе мы сфокусировались на абстрактных регистрах. Эти регистры находятся в центре фокуса, благодаря им философия форта настолько фундаментальна, но на самом деле эти регистры всего лишь компоненты более важной концепции: абстрактная машина. Возможно наиболее отличительная черта различных форт систем - это их реализации шитого кода. То, что в форте обозначается под шитым кодом - очень отличается от традиционного понимания нитей процессов в разделённой памяти с вытесняющей многозадачностью 4. Форт нити не имеют ничего общего с параллелизмом. Форт нити - это основа для разговора о компиляции кода и метапрограммировании.

4 Эта книга не рекомендует использовать эти типы нитей из за соображений безопасности и надёжности.

И если лисп даёт доступ к дереву структуры данных 5 символов из которых собрана в памяти и скомпилирована ваша программа, то в форте нет символьных манипуляций. Вместо этого форт даёт доступ к процессу сборки - сшивания - кода в памяти. Для посторонних наиболее примечательными особенностями форта являются стеки и постфиксная нотация, но, на самом деле изюминкой форта являются нити. Форт также завязан на стеки, как и лисп на списки. Они просто созданы для того, чтобы быть наиболее удобными структурами данных для решения задач мета-программирования - то, для чего предназначены форт и лисп.

5 На самом деле - ориентированный ацикличный граф.

Классический стиль сшивания известен как косвенное сшивание, но более современные разновидности форта реализованы с прямым сшиванием. Разница заключается в уровне косвенности. Низкоуровневая эффективность реализации косвенности зависит от процессора, и мы не будем углубляться в детали. По форт сшиваниям есть немало хороших руководств [STARTING-FORTH] [MOVING-FORTH]. В памяти компьютера эти оба стиля сшивания реализованы как смежные ячейки, в которых целочисленные машинные слова представляют указатели. Внутренний интерпретатор - маленький, компактный машинный код - обычно предназначается для процессора, выполняющего свою важную работу: следовать по указателям этих форт нитей, с последующей интерпретацией их значений. По-умолчанию, при встрече ячейки используется такое поведение: поместить текущий указатель расположения программы в стек возврата, после чего изменить указатель расположения программы на то, что указывает содержимое ячейки. Когда внутренний интерпретатор достигнет конца нити, он извлечёт значение из стека возврата и продолжит исполнение с прежнего места - там где оно остановилось 6.

6 В большинстве фортов, конец нити обозначается форт словом exit.

Как вы можете себе представить, такой тип программного хранилища предназначен для чрезвычайно маленьких программ. Скомпилированное форт слово - это всего лишь последовательный массив целых чисел, большинство из которых представляют указатели на другие слова. Это всегда было одним из преимуществ форта. Из-за прозрачности сшивания программы в памяти, форт позволяет хорошо контролировать многие компромиссы, на которые приходится идти при программировании, включая один из наиболее важных: Скорость выполнения против размера программы. Шитый код позволяет нам оптимизировать наши абстракции настолько близко к проблеме, насколько это возможно, в результате получая экстремально быстрые, маленькие программы. Но, лисп макросы предназначены для гораздо большего, чем просто эффективность, то же самое можно сказать и по отношению к форт нитям. Как и большинство лисп программистов, форт программисты склонны считать себя реализаторами нового, а не просто пользователями. Форт и лисп - оба предназначены для контроля - пишите свои собственные правила.

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

Flub (Флаб) - это язык, работающий только с шитым кодом на подпрограммах или язык, реализация которого предоставляет только шитый код на подпрограммах.

Например, C - это Флаб потому, что единственное что он позволяет программистам - это создавать функции - непрозрачные блоки шитого кода на подпрограммах. Конечно, мы можем реализовать на C внутренний интерпретатор для обработки косвенно шитого кода 7 и, с помощью этой программы, самостоятельно выстроить стековый язык, но, тогда получается, что мы уже не программируем на C. Почти все Блаб языки - Флабы. Форт - как мы это только что выяснили - не Флаб. Позже мы увидим что форт даёт программистам/создателям языков много возможности для контроля компиляции их программ.

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

Является ли лисп Флабом? Интересно, но лисп, возможно, был первым не Флаб языком программирования, но потом постепенно стал в основном Флабом. Хотя это не строго требуется стандартом, основные COMMON LISP компиляторы только компилируют функции в блоки непрозрачного машинного кода и, таким образом, они являются Флабами. Но в самых первых версиях лиспа функции сохранялись как списки - странная разновидность сшивания кода, не сильно отличающаяся от форт нити. Такой подход позволял выполнять некоторые очень умные трюки во время выполнения программы, включая создание цикличного кода, но, был безнадёжно неэффективным. В отличие от фортовских разновидностей сшивания - эффективно реализованных на почти всех архитектурах - такое внутреннее представление лисп функций было недопустимым и лисп был модифицирован для того, чтобы генерировать (чрезвычайно) эффективный код. Соответственно, для метапрограммистов, большинство реализаций COMMON LISP-а являются Флабами.

Но есть разница между свойствами, которые невозможно добавить в язык и свойствами, которые мы можем добавить с помощью макросов. С помощью макросов мы можем расширять язык любыми способами и он по-прежнему будет оставаться лиспом. В COMMON LISP-е нет форт нитей из-за тех же причин, по которым нет продолжений и первоклассных макросов: они сознательно не реализованы в языке для того, чтобы писатели макросов реализовали их так, как им нужно. Одна из наиболее важных целей самой главы и её кода в том, чтобы показать, что лисп хоть и является Флабом, но может трансформироваться в не-Флаб языки с помощью макросов. Не Блаб подразумевает, не Флаб, или другими словами, если вы не можете преобразовать язык в не Флаб, то он должен быть Блабом. Однако, обратное неверно. Не Флаб языки, такие как форт продолжают оставаться Блабом и самый короткий путь сделать их не Блабом - это реализовать с их помощью лисп среду - после чего вам остаётся программировать на лиспе.

Листинг 8.4: FORTH-INNER-INTERPRETER
(défmacro forth-inner-interpreter ()
‘(loop
do (cond
((functionp (car pc))
(funcall (car pc)))
((consp (car pc))
(push (cdr pc) rstack)
(set! pc (car pc)))
((nu11 pc)
(setf pc (pop rstack)))
(t
(push (car pc) pstack)
(setf pc (cdr pc))))
until (and (null pc) (null rstack))))

Вместо того, чтобы использовать последовательные ячейки памяти для представления косвенных/непосредственных нитей, наш форт воспользуется преимуществом лисповской динамической типизации и структурой списка из cons ячеек. Мы называем такой код cons шитым кодом. Макрос forth-inner-interpreter расширяется в код, способный следовать по нитям, состоящим из cons ячеек связанных списков. Может показаться странным начинать программировать логику нашей форт среды именно так - с помощью макросов, которые должны раскрываться в некоторое, ещё недостаточно известное выражение - но, на самом деле - это предпочтительный шаблон лисп программирования. Поскольку макросы позволяют нам начинать программировать везде где мы хотим, почему бы не начать с действительно интересного, основного механизма программы? Этот механизм будет оказывать наибольшее влияние на окончательную архитектуру программы.

Определение forth-inner-interpreter представляет собой четкое описание того, что мы подразумеваем под cons шитым кодом. Car каждой cons ячейки указывает либо на функцию, другую cons ячейку, либо на другой лисп atom. Функции исполняются в таком порядке, в каком они встречаются. Заметьте, что изменение pc регистра остается на усмотрение самой функции. Если в нити найдена cons ячейка, то предполагается указание на вызов подпрограммы – вызов слова. Наш внутренний интерпретатор поместит точку возобновления из pc в стек возврата и перейдет к этой новой нити. Если встретится какой-то другой атом, то он будет просто помещен в стек параметров и выполнение продолжится со следующей ячейки нашей нити. Внутренний интерпретатор завершит работу, когда дойдет до конца нити и не останется других нитей для возобновления в его стеке возврата.

Листинг 8.5: PRIM-FORMS
;; Prim-form: (name immediate . forms)
(defvar forth-prim-forms nil)
(defmacro def-forth-naked-prim (hrest code)
‘(push ’,code forth-prim-forms))
(detmacro def-forth-prim (trout code)
‘(def-forth-naked-prim
,0code
(setf pc (cdr pc))))

Но конечно же функции не могут изменить pc переменную, если они не определены в ее лексической области видимости 8, поэтому обратимся к другой технике макросов: вместо использования defun мы создаем похожий интерфейс, который делает нечто совершенно иное. Def-forth-naked-prim очень похож на создание функций с помощью defun за исключением того, что код, в который он расширяется, вставляет формы, определённые пользователем, в список, хранимый в forth-prim-forth. Наш итоговый макрос будет использовать эти формы, для того чтобы определять примитивы форта в лексической области видимости. Так как эти формы всегда будут разворачиваться в эту среду, то мы можем без ограничений писать код, использующий все наши абстрактные регистры форта, такие как pc, pstack и т.д.

8 Есть исключения. Смотри Анафорические макросы.

Примитивы, определенные с помощью def-forth-naked-prim не будут устанавливать переменную pc на следующую ячейку в нити. Для большинства примитивов нам следует использовать def-forth-prim для выполнения обычного обновления. Оба этих макроса ожидают, что первым аргументом будет символ для ссылки на данный примитив, вторым будет булево значение, указывающее, будет ли данный примитив незамедлительным. Остаток аргументов - лисп формы, которые будут вычисляться при выполнении примитива.

Листинг 8.6: BASIC-PR.IM-FORMS
(def-forth-prim nop nil)
(def-forth-prim * nil
(push (* (pop pstack) (pop pstack))
pstack))
(def-forth-prim drop nil
(pop pstack))
(def-forth-prim dup nil
(push (car pstack) pstack))
(def-forth-prim swap nil
(rotatef (car pstack) (cadr pstack)))
(def-forth-prim print nil
(print (pop pstack)))
(def-forth-prim >r nil
(push (pop pstack) rstack))
(def-forth-prim r> nil
(push (pop rstack) pstack))

Восемь простых примитивов - ни один из них не является изолированным (naked) или незамедлительным - будут описаны прямо сейчас. Nop - фиктивная инструкция, которая ничего не делает ("нет операции" ("no operaiton")). Примитив * является операцией умножения: он достает два верхних элемента из стека параметров, перемножает их, затем помещает результат обратно. Dup - краткое название для "дубликат" ("duplicate"), он помещает верхний элемент стека снова в стек, создавая два идентичных значения. Swap меняет местами два элемента стека параметров, используя очень полезный COMMON LISP макрос: rotatef. Это не случайно, что форт также имеет (оперирующие стеком) механизмы замены. Print вынимает элемент стека параметров и печатает его. >r перемещает значение из стека параметров в стек возврата, r> делает обратную операцию.

Нарушает ли имя * наше важное правило захвата переменых из раздела 3.5 Нежелательный Захват, которое запрещает переопределять функции, определенные самим COMMON LISP? Нет, потому что, на самом деле, мы не импользуем этот символ для связывания с какой-то функцией - это просто первый элемент одного из списков в foth-prim-forms. Мы не сделали ничего неправильного. Символы независимы от функций или макросов, которых они иногда обозначают. Мы можем использовать любые символы где угодно, до тех пор, пока мы уверены, что не нарушаем наши важные правила захвата переменных. Они вступают в игру только при написании лиспа; мы же пишем форт.

8.3 Двойственность Синтаксиса, Определённая

Если вы ещё ничего не запомнили из этой книги, то запомните заголовок этого раздела. Здесь мы, наконец, определяем и объясняем, уже затронутую ранее, концепцию: двойственность синтаксиса. Подразумевается что ещё до чтения этой главы вы прочитали хотя бы три первых глав, главу 6, Анафорические Макросы и предыдущие разделы этой главы.

Большинству программистов очевидно из опыта, что программировать на лиспе более производительно и в итоге более естественно, чем программировать на Блаб языке, но гораздо труднее ответить на вопрос почему это так. Хоть и правда, что лисп черпает удивительную силу выразительности из макросов - и мы видели много интересных примеров в этой книге и в других источниках - все объяснения кажутся неудовлетворительными. В чем настоящее преимущество макросов? Частичное объяснение конечно включает лаконичность, делающее ваши программы короче. Вот его определение:

Пусть L язык программирования, F свойство (feature) этого языка программирования, и A произвольная (arbitrary) программа на L. F обеспечивает лаконичность L, если A короче, чем была бы в версии L без F.

Свойства лаконичности определяют базис и рациональность теории лаконичности:

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

Теория лаконичности основана на идее о том, что если ваши программные абстракции делают выражения в программе очень короткими и выразительными, то написание их становится легче, потому что требуется написать меньше кода. Наши CL-PPCRE макросы чтения являются примерами свойств лаконичности: они укорачивают достаточно длинные CL-PPCRE имена функций до выражений в стиле Perl, которые экономят нажатия на клавиши каждый раз, когда мы их используем. Теория лаконичности хорошо применима для написания маленьких программ, которые понятны для написания с самого начала 9. К сожалению, большинство программ не такие. Большинство программ - по крайней мере интересных - созданы итеративно посредством серии интерактивных пиши-тестируй циклов, результаты которых принимаются в расчет на каждом шаге на всем протяжении процесса. Ваши абстракции могут быть краткими, но если вы всегда вынуждены менять их на другие (возможно такие же короткие) абстракции, вы скорее всего не сократите усилия. Вместо оценки длины итоговой программы, возможно, будет лучше если мы оценим длину процесса её создания.

9 Часто называемые как Perl-однострочники, даже если они написаны не на Perl.

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

Хм, где мы были? Ах да, мы поболтали немного об абстрактных регистрах, абстрактных машинах и шитом коде, кроме этого определили утилиту для поиска команд под названием forth-lookup, внутренний интерпретатор для нашего cons шитого кода и систему для сбора примитивов, представленных списками в нашей форт системе. Но каким будет форт на лиспе? Ну, какая самая естественная форма для любой абстракции, которая сочетает в себе поведение и состояние? Замыкания, конечно. Наши старые друзья, let и lambda. Поработав над этой идеей можно получить следующий макрос:

(defmacro new-forth ()
‘(let ,forth-registers
(forth-install-prims)
(lambda (v)
(let ((word (forth-lookup v dict)))
(if word
(forth-handle-found)
(forth-handle-not-found))))))

Наш список абстрактных регистров форта, forth-registers, будет объединён непосредственно с расширением, где абстрактные регистры изначально привязанны к nil. Обратите внимание что мы оставили прилично пробелов в функциональности этого макроса. Мы обнаружили, что нам ещё предстоит определить макрос forth-install-prims, устанавливающий наши формы-примитивы, а также макросы forth-handle-found и forth-handle-not-found. Но самое важное, что мы вынесли из этого наброска: да, архитектура этого замыкания выглядит жизнеспособной и вполне может работать. Идея, являющаяся логическим следствием простому следованию архитектуре лиспа, приводит к тому, что форт будет замыканием, вызываемым единожды для каждого слова, переданного нами в форт. Наш набросок описывает реализацию для последующего использования (use case). Так мы представляем создание новой форт среды:

(defvar my-forth (new-forth))

Некоторый форт код, возводящий в квадрат число 3 и печатающий результат:

3 dup * print

Вот так мы можем исполнить его в нашей форт среде:

(progn
(funcall my-forth 3)
(funcall my-forth ’dup)
(funcall my-forth ’*)
(funcall my-forth ’print))

Листинг 8.7: GO-FORTH
(defmacro! go-forth (olforth &rest words)
‘(dolist (W ’,words)
(funcall ,g!forth w)))

Листинг 8.8: FORTH-STDLIB
(defvar forth-stdlib nil)
(defmacro forth-stdlib-add (&rest all)
‘(setf forth-stdlib
(nconc forth-stdlib
’,a11)))

Довольно корявый в использовании интерфейс, но мы программируем в лиспе, и мы знаем что всегда можем создать макрос, скрывающий эти детали, именно это мы сделаем в макросе go-forth. Заметьте, что go-forth использует автоматическую once-only (только единожды) функциональность defmacro!, поскольку первый аргумент переданный в go-forth попадает во внутренний цикл определённый через dolist и, возможно, будет вычислен не только единожды, как это могло бы быть задумано пользователем макроса. С помощью go-forth ввод форт кода в нашу форт среду становится гораздо более ясным:

(go-forth my-forth
3 dup * print)

В этот момент обстоятельства могут сложиться так, что нам периодически может потребоваться выполнение некоторого самозагружаемого форт кода при создании новых форт сред. Мы должны быть в состоянии вызвать замыкание при создании сред. Что в свою очередь может потребовать изменить архитектуру приложения "Let, окружающий Lambda" или, возможно, создать некоторую разновидность функции-обёртки поверх нашего макроса new-forth использующую макрос new-forth, загружающую стандартную библиотеку и возвращающую получившийся форт.

Поскольку форт код - это всего лишь список символов и других атомов, то наша стандартная библиотека, обеспечивающая всю необходимую нам самозагрузку (за исключением некоторых примитивов), может содержаться в списке. Переменная forth-stdlib содержит этот список форт кода и это содержимое будет запускаться при создании новых фортов, а макрос forth-stdlib-add будет расширяться в лисп код, объединяющий новый форт код со списком forth-stdlib.

С помощью какого самого лёгкого способа можно изменить new-forth так, чтобы он поддерживал загрузку этой стандартной библиотеки? Вы помните макрос alet, который мы написали в разделе 6.3, Alet и Машины с Конечным Состоянием? Целью этого макроса было создание двойственности синтаксиса с помощью let COMMON LISP'а одновременно привязывая анафорическую переменную this к переданному коду. This ссылается на результат, который будет возвращен из alet - замыкание форта .

Изменить наш набросок будет даже легче, чем ожидалось. Все, что нам нужно сделать - поменять первый let символ в нашем наброске на alet и затем добавить немного кода для загрузки стандартной среды в this, замыкание форта.10 Мы ничего не должны перестраивать, потому что синтаксис alet предусмотрительно связан с синтаксисом let. Ниже представлен вид этой следующей итерации:

10 Выполняется после установки примитивов, таким образом, ими может воспользоваться и стандартная библиотека.

(defmacro new-forth ()
‘(alet ,forth-registers
(forth-install-prims)
(dolist (v forth-stdlib)
(funcall this v))
(lambda (V)
(let ((word (forth-lookup v dict)))
(if word
(forth-handle-found)
(forth-handle-not-found))))))

Помните, что alet вводит слой косвенности, используя замыкание и таким образом делает нашу среду форта слегка менее эффективной. Однако, так как мы не знаем будет ли эта неэффективность слишком критичной, мы также не знаем стоит ли избавляться от этой косвенности. Чтобы исключить косвенность, используйте alet% макрос, определенный до alet.

Возможно теперь, а возможно позже, когда мы попытаемся собрать или отладить нашу форт среду, может оказаться, что было бы полезно иметь доступ к абстрактным регистрам извне среды форта. К несчастью эти переменные закрыты let-ом, окружающим lambda. Мы должны будем снова изменить нашу программу, чтобы сделать их доступными. Существует, конечно же, много способов сделать это. Мы можем встроить и возвращать много замыканий в нашей среде форта, часть из которых сохраняет и обращается к абстрактным регистрам, или мы можем пересмотреть нашу стратегию let, окружающую lambda полностью. Но перед тем как начать действовать посмотрим есть ли какая-нибудь двойственность, помогающая нам? Вспомним plambda из разела 6.7, Пандорические Макросы? Их цель была создать двойственность синтаксиса с помощью lambda, а также создать замыкание, на самом деле открытое для остального мира. Изменение нашего наброска для поддержания этого лишь вопрос добавления к префиксу символа p к lambda, которое мы возвращаем как наше замыкание и добавление списка переменных, который мы хотим экспортировать. Наш список удобно доступен нам в регистрах форта11. Наш набросок приобретает такой вид:

11 Хотя вклеивание этих переменных с помощью раскавычивания будет работать только при написании макросов, макросы чтения позволяют нам сделать похожие вещи при написании функций.

(defmacro new-forth ()
‘(alet ,forth-registers
(forth—insta11-prims)
(dolist (v forth-stdlib)
(funcall this v))
(plambda (v) ,forth-registers
(let ((word (forth-lookup v dict)))
(if word
(forth-handle-found)
(forth-handle-not-found))))))

С открытым замыканием форта нам становится доступен следующий сценарий использования. Вставим пять элементов в стек форта:

* (go-forth my-forth
1 2.0 "three" ’four ’(f i v e))
NIL

Листинг 8.9: NEW-FORTH
(defmacro new-forth ()
‘(alet ,forth-registers
(setq dtable (make-hash-tab1e))
(forth-install-prime)
(dolist (v forth-stdlib)
(funcall this v))
(plambda (v) ,forth-registers
(let ((word (forth-lockup v dict)))
(if word
(forth-handle-found)
(forth-handle-not-found))))))

И мы можем пандорически открыть my-forth, чтобы посмотреть его стек параметров:

* (with-pandoric (pstack) my-forth
pstack)
((F I V E) FOUR "three" 2.0 1)

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

Программирование, по крайней мере интересная его часть, это не написание программ, а, на самом деле, их изменение. С точки зрения эффективности лаконичность только подводит нас к этому. Мы можем переименовать lambda в, скажем fn, но такое свойство лаконичности не сэкономит много за исключением нескольких нажатий кавиш там и сям12. Что может сэкономить усилия, так это наличие абстракций, похожих на lambda, которые мы можем использовать для изменения работы кода, не меняя значительно сам код. Двойственность синтаксиса сэкономит усилия.

12 Многие из нас считают, что lamda и так хороша, спасибо.

Также как выделение "наушниками" имен ваших специальных переменных может раздражать вас необходимостью добавлять или убирать символы *, когда вы меняете свое решение о том должна быть эта переменная специальной или лексической13, ненужное разделение синтаксиса и избегание двойственности может стать причиной многих необоснованных усилий во время программирования. Другой пример: шарп-закавычивать ваши лямбда формы - это плохая идея, потому что в конечном счёте вам придётся вносить намного больше изменений, когда вы решите, что функция на самом деле должна быть alambda или когда вы решите использовать lambda форму на позиции функции в списке. Обобщенные переменные также обеспечивают очень важную двойственность: когда пишем макросы одна и та же форма может быть вклеена в раскрытие как для считывания, так и для изменения переменной. Другой пример - COMMON LISP-овксая двойственность в обозначении пустого списка и значения false булевой переменной - на самом деле нет никаких причин для того, чтобы эти две сущности объединялись в одну за исключением двойственности синтаксиса. Также из-за двойственности эта книга пропагандирует замыкания вместо других свойств CLOS 14 таких как defclass и defmethod. Обычно бывает меньше трудностей при модификации программ, которые используют замыкания, чем при модификации программ, использующих классы и объекты, так как у нас есть так много хороших двойственностей синтаксиса для замыканий и потому что программирование макросов, которые строят замыкания, более унифицировано 15. Учитывая эти и другие примеры мы можем наконец дать ясное определение того, что мы подразумеваем под двойственностью синтаксиса:

13 Или возможно оставляя некорректную документацию в коде.

14 Здесь слово "других" подразумевает тот факт, что даже программирование с замыканиями в COMMON LISP является свойством CLOS. CLOS настолько фундаментален, что вы не можете избежать его (и не должны этого хотеть).

15 Стоит сказать, что обобщенные функции очень важны, так как они реализуют двойственность мульти-методов.

Пусть L - язык программирования, F - свойство в этом языке программирования, и A и B - произвольные программы на L. F является свойством двойственности синтаксиса, если требуется меньше модификаций для преобразования A в B чем в версии языка L без F.

Что приводит к гипотезе двойственности:

Усилия, необходимые для написания программы обратно пропроциональны объему двойственного синтаксиса, доступного в используемом языке программирования.

В то время как концепция двойственности синтаксиса и влияния их преимуществ совершенно понятны, гораздо менее понятно как на деле придумать хорошие двойственности. Какие двойственности наиболее полезны в конкретном языке? Как можно определить какой из двух различных языков предлагает лучшие двойственности синтаксиса для некоторой данной проблемы?

Поскольку в лиспе мы контролируем язык программирования полностью, то у нас есть возможность спроектировать язык с таким уровнем двойственности синтаксиса, какой только мы пожелаем. На мой взгляд такая цепь размышлений, на данный момент, наиболее плодородная область в исследовании языков программирования. Используя лисп макросы мы можем делать похожими друг на друга наши разрозненные программы, упростится ли изменение этих программ в новые программы16?

16 Иногда превращение программ в новые программы называется разработкой, особенно когда итоговая программа больше чем исходная.

В обоих определениях лаконичности и двойственности, является ли свойство F эффективным или нет, зависит от программы, которую пишут или изменяют. Иногда свойства, которые обеспечивают лаконичность или двойственность, могут на деле увеличить количество затрачиваемых усилий. Лучшим подходом может стать предоставление стольких полезных свойств лаконичности и двойственности сколько является возможным, так как удаление ставших ненужными свойств может привести больше к вреду, чем к пользе.

8.5 Работающий Форт

В этом разделе мы получим работающий форт, заполнив пробелы, оставленные в макросе new-forth из предыдущего раздела. После проверки работы механизма нити форта, мы запустим среду программирования форта, и, попутно, рассмотрим что же такое незамедлительность (immediacy) форта, и как оно относится к макросам лиспа.

В определении new-forth мы оставили пробелы в макросе, которые будут заполнены с помощью forth-install-prims. Мы хотели бы использовать именованную абстракцию без отбрасывания лексической среды, поэтому нам нужен макрос. Смысл этого макроса заключается в том, чтобы компилировать и устанавливать примитивы в форт словарь при создании нового экземпляра форта. Forth-install-prims расширяется в progn форму, где каждая внутренняя форма является инструкцией, добавляющей слово-примитив в связанный список dict, оборачивает переданный код в lambda, и устанавливает name (имя) слова и слоты immediate. В дополнение, функция, созданная для каждого слова с помощью lambda, называется как thread (нить) и добавляется к нашей хэш-таблице dtable (рассмотрим позже). Поскольку все эти функции будут созданы в области видимости нашего исходного макроса new-forth, то у них будет полный доступ к форт среде, определённой нашими абстрактными регистрами. Заметьте, что привязка thread не захватывает thread из переданного пользователем кода, поэтому нам не нужно прибегать к именованию через gensym.

Listing 8.10: FORTH-INSTALL-PRIMS
;; Prim-form: (name immediate . forms)
(defmacro forth-install-prims ()
‘(progn
,@(mapcar
#‘(1et ((thread (lambda ()
,@(cddr a1))))
(setf dict
(make-forth-word
zname ’,(car a1)
zprev dict
:immediate ,(cadr a1)
zthread thread))
(setf (gethash thread dtable)
’.(cddr a1)))
forth-prim-forms)))

Мы сказали, что форт обеспечивает систему мета программирования, не совсем отличную от лисповой и эта система базируется на концепции так называемой незамедлительности. В традиционных фортах есть переменная под названием состояние (state), принимающая значения ноль или не-ноль. Если значение ноль, то считается, что форт находится в обычном интерпретирующем (исполняющем) состоянии. Если мы передадим слово в форт в этом состоянии, то оно будет найдено и выполнено. Если же переменная base не-ноль, то говорится, что форт находится в состоянии компиляции. Если мы передаем слово в форт в этом состоянии, то адрес переданного слова будет добавлен к текущей компилируемой нити - обычно самому последнему созданному слову в словаре. Правда существует одно исключение, и это важное свойство незамедлительности. Если в состоянии компиляции передать незамедлительное слово, то это слово будет выполнено, а не скомпилировано. Таким образом, также как в лиспе, форт позволяет нам выполнять произвольный код во время компиляции.

Listing 8.11: FORTH-PRlMS-COMPILATION-CONTROL
(def-forth-prim [ t ; <- t means immediate
(setf compiling ni1))
(def-forth-prim ] nil ; <- not immediate
(setf compiling t))

Так как мы строим наш форт как абстрактную машину на лиспе, нам не запрещено произвольное сопоставление целочисленных значений значениям true и false. В лиспе динамическая система типов, которая позволяет наслаждаться произвольным сопоставлением любых значений в true и false. Вместо переменной state состояния форта наша система форта использует абстрактный регистр компиляции compiling для хранения нашего состояния компиляции как обобщенной булевой переменной. Традиционные слова форта для изменения состояния компиляции - [ и ], открывающая и закрывающая квадратные скобки. [ выводит нас из состояния компиляции и поэтому это слово должно быть незамедлительным словом. ] возвращает нас обратно в режим компиляции, выполнятся только если мы в режиме интерпретации и не должно быть незамедлительным. Такой выбор символов может сейчас показаться странным, но станет более понятным в высокоуровневом форт коде. Эти квадратные скобки позволяют нам пометить для выполнения блок кода во время компиляции форт нити. В определенном смысле эти скобки похожи на лисповские операторы обратной кавычки и раскавычивания. Ниже пример типичного использования этих слов в форт коде:

... compiled words ...
[ interpret these words ]
... more compiled words ...

Listing 8.12: FORTH-COMPILE-IN
(defmacro forth-compile-in (V)
‘(setf (forth-word-thread dict)
(nconc (forth-word-thread dict)
(list ,v))))

Как и большинство деталей форта эти слова определены прозрачно, что позволяет нам использовать их нетрадиционным способом. Например, эти слова не сбалансированы в том же смысле, что и скобки лиспа. При желании мы можем использовать их в противоположном направлении:

. interpret these words ...
] compile these words [
. more interpreted words ...

У нас даже возникает вложенность, но это не настоящая вложенность, поскольку нам доступно единственное состояние: Компилировать или не компилировать.

. compiled words ...
[ interpret these words
] compile these words [
interpret these words
]
. more compiled words . . .

Наш форт использует макрос forth-compile-in как макрос-аббревиатуру. Этот макрос компилирует форт слово в нашу текущую нить, нить последнего созданного слова. Поскольку наши нити представлены в виде cons ячеек, то мы можем использовать лисп функцию nconc для простого добавления указателя на нить нужного слова в нашу текущую нить.

Другой пробел оставленный в макросе new-forth заключается в том, что должен делать форт если удалось найти указанное слово в словаре. Этот пробел заполнится макросом forth-handle-found. Этот макрос реализует описанную выше незамедлительность форта. Если мы выполняем компиляцию и найденное слово не является незамедлительным, то мы компилируем его в текущую нить. В противном случае мы помещаем в наш программный счётчик pc указатель на нить найденного слова и запускаем внутренний интерпретатор на исполнение слова. Не забудьте, что этот макрос будет расширен в лексическую среду, в которой word привязан к найденному форт слову.

Листинг 8.13: FORTH-HANDLE-FOUND
(defmacro forth-handle-found ()
‘(if (and compiling
(not (forth-word-immediate word)))
(forth-compile-in (forth-word-thread word))
(progn
(setf pc (list (forth-word-thread word)))
(forth-inner-interpreter))))

Листинг 8.14: FORTH-HANDLE-NOT-FOUND
(defmacro forth-handle-not-found ()
‘(cond
((and (consp v) (eq (car v) ’quote))
(if compiling
(forth-compile-in (cadr v))
(push (cadr v) pstack)))
((and (consp v) (eq (car v) ’postpone))
(let ((word (forth-lookup (cadr v) dict)))
(if (not word)
(error "Postpone failed: "a" (cadr v)))
(forth-compile-in (forth-word-thread word))))
((symbo1p v)
(error "Word "a not found" v))
(1:
(if compiling
(forth-compile-in v)
(push v pstack)))))

Наш последний пробел в new-forth заключается в том, что форт должен сделать если не может найти слово в своём словаре. Forth-handle-not-found заполняет этот пробел и реализует некоторые специальные случаи. Напомним, что forth-handle-not-found будет расширен в лексическую среду, содержащую привязку v, ссылающуюся на значение, переданное форту. Также мы знаем, что если будет вызван этот код, v не будет ссылаться ни на какое слово в словаре. Если v будет символом, forth-handle-not-found вызовет ошибку. Если значение не будет символом, то поведение будет заключаться во вставке v в стек параметров или, если мы выполняем компиляцию, скомпилировать его в текущую нить. Однако, будет выполняться проверка на два специальных случая. Если v будет списком с первым элементом quote, то мы вставим закавыченное значение в стек параметров. Это объясняется тем, что мы можем вставлять символы в стек параметров без интерпретирования их как слов. Второй специальный случай возникает тогда, когда v является списком с первым элементом postpone (отложить). Postpone - это слово из ANSI Forth, объединяющее и разъясняющее пару традиционных форт слов. Postpone используется для того, чтобы всегда компилировать слово даже если это слово будет незамедлительным. Таким образом, если мы находимся в режиме компиляции, отложенное незамедлительное слово будет скомпилировано в наш текущий тред даже если это слово незамедлительно. Пример откладывания слова [:

... компилирование ...
(postpone [)
... компилирование продолжается ...

Все пробелы в макросе new-forth заполнены, и теперь мы можем создать новый экземпляр форта с помощью макроса new-forth. Раньше мы создали специальную переменную под названием my-forth с помощью defvar. Даже если бы мы этого не сделали, мы можем неявно декларировать её специальной присвоив ей значение с помощью высокоуровневого setq17:

17 Некоторые реализации не дадут вам выполнить это. Решением будет перейти на реализацию, позволяющую выполнить эту операцию (например CMUCL) или использовать в таких случая defparameter вместо setq.

* (setq my-forth (new-forth))
#<Interpreted Function>

Теперь, с помощью go-forth мы можем использовать форт:

* (go-forth my-forth
2 3 * print)
6
NIL

Листинг 8.15: FORTH-PRIMS-DEFINING-WORDS
(def-forth-prim create nil
(setf dict (make-forth-word :prev dict)))
(def-forth-prim name nil
(setf (forth-word-name dict) (pop pstack)))
(def-forth-prim immediate nil
(setf (forth-word-immediate dict) t))

Но до сих пор мы определили только слова dup, * и print. Для того, чтобы сделать что-то полезное нам нужно больше примитивов. Как и лисп, реализации форта промышленного уровня обладают большим количеством слов, определённых для удобства программиста. В процессе десятилетий использования форта, были определены многие общие шаблоны программирования, абстрагированы в слова и затем введены в общеиспользуемый форт. Как и в лиспе наличие возможности расширять язык, определённый как часть языка, стала результатом очень ценных экспериментов. Поскольку мы изучаем этот процесс и философию, то мы не будем определять многие форт слова, которыми пользуются опытные форт программисты. Вместо этого нашей целью будет минимальный набор примитивов, требуемых для изучения системы метапрограммирования форта и её сравнение с лисп макросами.

Определены ещё три примитива, ни один из них не является незамедлительным или незащищённым: create, name и immediate. Слово create добавляет безымянное слово в словарь. Name извлекает значение из стека параметров и устанавливает название последнего слова словаря в это значение. Immediate просто делает незамедлительным последнее определённое слово. По умолчанию слова не являются незамедлительными.

Напомним что мы можем исполнять код с помощью нашего макроса go-forth в нашей форт среде my-forth. Так мы возведём в квадрат число 3 и напечатаем результат:

* (go-forth my-forth
3 dup * print)
9

Достаточно ли у нас форта для запуска самопостроения форта с помощью форт слов? И хотя мы ещё не определили достаточно слов, но благодаря прозрачной спецификации поточного кода мы можем написать форт слова, используя форт. Например, вот так можно использовать create для добавления новых пустых слов в словарь:

* (go-forth my-forth
create)
NIL

Теперь мы можем иcпользовать ] для начала компиляции, добавить слова dup и * в тред, затем использовать [, стобы выйти из режима компиляции:

* (go-forth my-forth
] dup * [
NIL

Теперь у нас есть новое слово в нашем словаре - одно с законченной форт нитью, которое, исполненное нашим внутренним интерпретатором, возведет в квадрат первое число в стеке. Но это слово не очень полезно, если у нас не будет способа вызвать его. Мы можем дать ему имя, используя слово name. Присвоенное имя будет ключом доступа к нашей новой нити.

* (go-forth my-forth
’square name)
NIL

Обратите внимание, что первое передаваемое значение закавычено. Вспомните, что мы решили что такое поведение заставит форт поместить символ square в стек параметров. Этот символ потом будет использован словом name. Теперь наше слово названо, и мы можем вычислять его как любое другое, используя символ square:

Listing 8.16: FORTH-START-DEFINING
(forth-stdlib-add
create
] create ] [
’{ name)

Listing 8.17: FORTH-STOP-DEFINING
(forth-stdlib-add
{ (postpone [) [
’} name immediate)

(go-forth my-forth
3 square print)
9
NIL

Итак, следующий шаблон представляет общую технику создания новых слов:

create
] ... compiled words ... [
’whatever name

Но мы можем использовать кусочек мета-программирования форта, чтобы улучшить этот интерфейс. Определение нового форт слова { добавлено в стандартную библиотеку. Эта нить состоит из двух указателей, первый указывает на слово create, а второй указывает на слово ]. Таким образом, когда нить данного слова выполняется, то в словарь добавляется новое слово и мы переключаемся в режим компиляции. Форт обычно использует : слово для этой цели, но из-за конфликта с использованием : в лиспе мы выбрали { для определения слова.

Аналогично, мы добавляем сопряженное слово } в стандартную библиотеку ( заменяя традиционное фортовское ;). На самом деле нет причин для определения этого слова - единственное, что оно делает, выводит нас из режима компиляции. Для этого у нас уже есть слово [. Несмотря на это, определение { полезно, потому что даёт нам нормально сбалансированные скобки18 создавая пару слов { и }, что делает определение новых слов интуитивным.

18 Как противоположность к обратно сбалансированным квадратным скобкам форта, данным для определения слова.

Теперь мы можем создать форт для того, чтобы воспользоваться новыми особенностями стандартной библиотеки (отбросив наше предыдущее определение слова square):

* (setq my-forth (new-forth))
#<Interpreted Function)

С новыми словами определения слов { и } square будет выглядеть так:

* (go-forth my-forth
{ dup * } ‘square name)
NIL
* (go-forth my-forth
5 square print)
25

И новые нити могут ссылаться на наши специально созданные слова так, как если бы они были примитивами. Так мы можем определить слово quartic как нить с двумя указателями на наше слово square:

* (go-forth my-forth
{ square square } ’quartic name)
NIL

Действительно, (Expt 1/2 4) равен 1/16:

* (go-forth my-forth
1/2 quartic print)
1/16
NIL

Поскольку не-символы напрямую компилируются в форт нить и наш внутренний интерпретатор рассматривает не-функции как элементы данных, при встрече с которыми следует выполнить вставку в стек, то мы можем включать числа в определение слов:

* (go-forth my-forth
{ 3 } ’three name
three three * print)
9
NIL

Напомним, что мы просматриваем все элементы переданные форту в поисках имени в словаре с помощью функции eql. Следствием этого является то, что мы можем использовать любой лисп объект в качестве имени слова. Так мы используем число19:

19 Во многих фортах, такие общие числа, как 0, 1, -1 и так далее, определены как слова поскольку скомпилированный указатель на слово, обычно, занимает меньше памяти чем скомпилированная лексема.

* (go-forth my-forth
{ 4.0 } ’4 name
4 4 * print)
16 . 0
NIL

Форт - замечательный язык для изучения использования области видимости указателя. Форт определяет два простых оператора, используемых для чтения/записи значений из/в память: @ (fetch - получить) и ! (store - поместить). Поскольку наши форт слова сохранены в cons ячейки вместо слов памяти, то переопределение указателя с помощью fetch реализовано через получение car указателя. Присвоение значения реализовано через присвоение значения car-у используя setf. Fetch извлечёт значение из стека параметров, предполагая его cons ячейкой, выделит его car и поместит его в стек. Store извлечёт значение из стека параметров, предполагая его cons ячейкой, извлечёт другое значение из стека и поместит его в car первого значения. Пример того, как мы можем создать и напечатать циклический список:

Листинг 8.18: MEMORY-PRIMS
(def-forth-prim @ nil
(push (car (pop pstack))
pstack))
(def-forth-prim ! nil
(let ((1ocation (pop pstack)))
(setf (car location) (pop pstack))))

* (let ((*print-circ1e* t))
(go-forth my-forth
’(ni1) dup dup ! print))
#1=(#1#)
NIL

Теперь мы программируем в форте используя шитый код. Где же мы? Отошли ли мы отошли от лиспа? Разница между двумя языками настолько размыта, что её едва ли можно заметить. Остаток этой главы будет посвящён ещё большему размытию при дальнейшем изучении метапрограммирования форта.

8.5 Более Фортово

В COMMON LISP есть порядочно функций, которые нам хотелось бы иметь возможность вставить в наши форт нити. Forth-unary-word-definer раскрывается в такое же количество форм def-forth-prim, сколько элементов передано в его тело макроса. Под элементами подразумеваются символы, обозначающие либо макросы, либо функции, но они также могут быть лямбда формами. Единственным ограничением для примитивов, именованных лямбда формами является то, что для их вызова вам понадобится передать такую же (eq) лямбда форму в среду форта. Вот раскрытие, когда передан один символ, not:

Listing 8.19: FORTH-UNARY-WORD-DEFINER
(defmacro forth-unary-word-definer (treat words)
‘(progn
,O(mapcar
#‘(def-forth-prim ,a1 nil
(push (,a1 (pop pstack))
pstack))
words)))

Listing 8.20: FORTH-BINARY-WORD-DEFINER
(defmacro! forth-binary-word-definer (&rest words)
‘(progn
,@(mapcar
#‘(def-forth-prim ,a1 nil
(let ((.g!top (pop pstack)))
(push (,a1 (pop pstack)
,g!top)
pstack)))
words)))

* (macroexpand
’(forth-unary-word-definer
not))
(progn
(DEF-FORTH-PRIM NOT NIL
(PUSH (NOT (POP PSTACK))
PSTACK)))

Мы можем использовать любую функцию COMMON LISP, которая принимает один аргумент, и forth-unary-word-definer определит форт примитив, который применит эту функцию к верхнему элементу стека параметров форта.

Listing 8.21: FORTH-AND-LISP-WORDS
(forth-unary-word-definer
not car cdr cadr caddr cadddr
oddp evenp)
(forth-binary-word-define:
eq equal + - / = < > <= >=
max min and or)

Расширением этой идеи служит forth-binary-word-definer, который делает то же самое, только для операторов, принимающих два значения. Правило форта использования второго от вершины элемента как первого элемента для таких двухэлементных функций, как - и / достигается созданием временного let связывания для удержания верхнего элемента из стека параметров. Вот раскрытие для слова -:

* (macroexpand
’(forth-binary-word-definer
-))
(LET ()
(PROGN
(DEF-FORTH-PRIM - NIL
(LET ((#:TOP1767 (POP PSTACK)))
(PUSH (- (POP PSTACK) #:TOP1767)
PSTACK)))))

Упражнение: Каким образом достигается возможность рассмотрения таких макросов как and и or в качестве первоклассных значений при использовании forth-binary-word-definer?

Трудное упражнение: Почему необходимо использовать gensym (g!top) для избежания нежелательного захвата переменной в forth-binary-word-definer? Подсказка: Мы уже говорили об этом в этом разделе.

Итак, эти макросы позволяют нам добавить разные функции лиспа в нашу среду примитивов форта, и мы можем использовать их внутри форта. Вот пример использования унарного примитива cadr:

* (go-forth my-forth
’(a (b) c) cadr print)
(B)
NIL

А вот бинарного <:

* (go-forth my-forth
2 3 < print)
T
NIL

Так как наши нити суть ориентированные ацикличные графы, это означает, что они состоят из структуры связанных ячеек, которые нигде не указывают на себя (не являются самоотносящимися) и которые в итоге оканчиваются нашими примитивами, листьями дерева. Например, мы можем использовать пандорические макросы, чтобы получить нить, которую мы создали в предыдущем разделе, когда определяли слово qurtic:

* (with-pandoric (dict) my-forth
(forth-word-thread
(forth-lookup ’quartic dict)))
((#<Interpreted Function> ;; square->|->dup
#<Interpreted Function>) ;; |->*
(#<Interpreted Function) ;; square->|->dup
#<Interpreted Function>)) ;; |->*

Вышерасположенные комментарии показаны с точки зрения печати формы в лиспе. Мы не можем увидеть из кода или из комментариев, что это нитевая структура на самом деле общая. Чтобы увидеть эта, используем eq:

* (eq (car *) (cadr *))
T

Или посмотрим на это с установленным *print-circle*:

* (let ((*print-circle* t))
(print **)
t)
(#1=(#<Interpreted Function) ;; square->|->dup
#<Interpreted Function>) ;; |->*
#1#) ;; ------ --I
T

Шитый код форта позволяет достичь удивительных преимуществ в памяти и размере. В целом, системы форта - это скомпилированный код, сшитый вместе так же, как и наш код - начиная с сетевых драйверов и заканчивая высокоуровневыми пользовательскими программами. Что более важно, обратите внимание, как мы смогли безболезненно извлечь нить из quartic не имея дело со многими другими нитями. Например, в нашем языке есть много таких примитивов, как + и cadddr, но они не появляются в вышеприведённой нити. Как будто у нас есть сборка мусора использующая алгоритм пометок и извлекающая для нас только нить необходимую для исполнения данного форт слова. В лиспе этот процесс называется утряской дерева (tree shaking) и в целом этот процесс не очень эффективен. И наоборот, в форте данный процесс чрезвычайно эффективен.

К несчастью нить quartic, пандорически извлекаемая из my-forth, на самом деле не так уж и полезна для нас. Она по прежнему постоянно расположена в замыкании my-forth. Таким образом, лямбда выражения, представляющие примитивы dup и * обладают своими ссылками на абстрактные регистры форта, захваченные расширением нашего макроса new-forth. Можем ли мы сохранить этот код в плоскости лисп макросов так, чтобы в последующем встроить его в новые программы? Позже мы вернёмся к этому вопросу, но сейчас мы немного углубимся в мета-программирование форта.

На некотором уровне любого языка - обычно уровне скрытом от программиста - обязательным условием для кода является возможность сослаться на самого себя. Наиболее удобным примером этой обязательности является наблюдение, что коду нужна возможность сослаться на самое себя для того, чтобы реализовать циклы, рекурсии и такие условные выражения, как определения if. Разница между Флаб и не-Флаб языками в том, что Флаб не даёт вам возможности прямой модификации того как, где и каким образом вставлять ссылку на самого себя. Но, лисповский не-Блаб статус обозначает что мы можем сконструировать не-Флаб и мы сейчас это сделаем.

Листинг 8.22: BRANCH-IF
(def-forth-naked-prim branch-if nil
(setf pc (if (pop pstack)
(cadr pc)
(cddr pc))))

Наша форт система в своём текущем состоянии (без возможности вставки ссылок на саму себя) - почти чистый Флаб. Подобно тому, как чистые функциональные языки сознательно определены как язык лишённый побочных эффектов и не статических отображений, так же и чистые Флаб языки определены так, чтобы не содержать конструкции кода, не содержащие ссылок на самих себя, как например, циклы и рекурсии. Следствием этого является то, что интерпретация Флаб нитей всегда конечна. Наша форт среда не полностью чиста поскольку мы можем - и будем - нарушать Флаб чистоту, но, чиста в том смысле, что если мы будем продолжать использовать уже определённые конструкции, то результатом будут чистые Флаб нити. Чистый Флаб не очень полезен, поэтому давайте разрушим Флаб чистоту нашей форт среды. Вместо того, чтобы идти в направлении Флаба - к таким Флаб языкам, как COMMON LISP где шитьё кода непрозрачно и недоступно - давайте двигаться в направлении форта и сделаем этот атрибут кода макро изменяемым.

Примитив branch-if - это первый изолированный примитив. Напомним, что изолированные примитивы - это примитивы не обновляющие автоматически абстрактный регистр счётчика программы (pc). Вместо автоматического обновления счётчика эти примитивы должны произвести самостоятельное обновление счётчика. Branch-if извлекает значение из стека параметров. Если значение не-null, то pc устанавливается в содержимое следующей ячейки интерпретируемой нити. Если значение nil, то pc обрабатывается как обычно, с тем исключением, что пропускается следующая ячейка в интерпретируемой нити.

Например, следующий пример создаёт форт среду, в которой мы можем воспользоваться возможностями нашего нового примитива branch-if и определяются два слова: double и if-then-double.

* (go-forth (setq my-forth (new-forth))
{ 2 * } ’doub1e name
{ branch-if double "Not doubling" print }
’if-then-double name)
NIL

Double просто умножает верхний элемент стека параметров на два, удваивает значение. If-then-double требует двух элементов в стеке параметров. Верхний элемент нужен для if-then-double, а второй элемент будет удваиваться только тогда, когда значение верхнего элемента будет не-null. Заметьте, что поскольку следующее значение в нити после branch-if является указателем на другую нить (double), то контроль исполнения перемещается на эту другую нить без вставки места возобновления в стек возврата. В лиспе это называется хвостовым вызовом (tail-call). Поэтому если мы передадим nil 20 в if-then-double то будет выбрана не удваивающая ветвь и напечатана строка:

20 Нам нужно закавычить nil поскольку мы не хотим чтобы выполнялся поиск в словаре форта.

* (go-forth my-forth
4 ’ni1 if-then-double print)
"Not doubling"
4
NIL

Но если значение не-null, то ветвь не будет выбрана, произойдёт удваивание и строка не напечатается:

* (go-forth my-forth
4 ’t if-then-double print)
8
NIL

Но, существует более простой способ выйти из слова, и этот способ реализован с помощью нового слова под названием exit. Интересной особенностью форта является то, что будучи вызванным слово может решить быть ему хвостовым вызовом или нет. Exit - это обычное форт слово и процедура вызова осуществляется так же, как и всегда: форт вставляет текущее расположение нити в стек возврата, затем присваивает счётчику программы указатель на начало слова exit. После вызова exit, поскольку у этого слова есть прямой доступ к стеку возврата с помощью примитивов r> и >r, мы можем сделать так, чтобы вызванное слово никогда не возвращало контроль исполнения просто переместив место возобновления из стека возврата и отбросив это значение. Вот пример использования exit:

Листинг 8.23: EXIT
(forth-stdlib-add
{ r> drop } ‘exit name)

Листинг 8.24: COMPILER-PRIMS
(def-forth-naked-prim compile nil
(setf (forth-word-thread dict)
(nconc (forth-word-thread dict)
(list (cadr pc))))
(setf pc (cddr pc)))
(def-forth-prim here nil
(push (last (forth-word-thread dict))
pstack))

* (go-forth my-forth
{ "hello" print
exit
;; Never gets here
"world" print } ‘exit-test name
exit-test)
"hello"
NIL

Так как branch-if реализует jump или goto инструкцию, с помощью которой возможно перейти к значению, хранящемуся в последующей ячейке нити,которую мы выполняем. Получение значения из нити, которую вы в данный момент выполняете - является обычным шаблоном и требует изолированных примитивов. Другой примитив compile также использует этот шаблон. Compile - это изолированный примитив, который будет брать значение следующей ячейки, в нити, выполняющейся в данный момент, и затем компилирует это значение в нить последнего слова, добавленного в словарь, - обычно слова, которое мы в данный момент компилируем. Here простой примитив, который вставляет последнюю ячейку компилируемой нити в стек параметров. Наш here слегка отличается от обычного фортового слова here. В форте here обычно вставляет следующее место, которое будет компилироваться вместо последнего скомпилированного места. Это потому что, в традиционном форте, следующее место в памяти для компиляции известно сразу - это будет следующая примыкающая ячейка памяти. Для cons шитого кода мы не можем этого знать, так как мы еще не присоединили эту память.

С доступными compile и here мы можем теперь начать писать форт макросы. Вспомним, что когда форт слово является незамедлительным, то во время компиляции оно будет выполнено, а не скомпилировано в нить последнего определенного слова. Такими же способами, которыми мы можем адаптировать и расширять лисп с помощью макросов, мы можем использовать незамедлительные слова для адаптации и расширения форта. В лиспе основными структурами данных, используемых для метапрограммирования являются списки. В форте основные структуры данных стеки.

Вы могли заметить, что наша среда форта даже не имеет выражения if. У нас есть условно ветвящийся (branching) примитив, названный branch-if, но пока он может быть полезен только для выполнения хвостовых вызовов других слов форта. Вспомним, что форт слова представлены нитями и мы можем поместить значение любой нити в ячейку, на которую совершит переход branch-if. Что если мы положим значение, которое ведет к части нити, компилируемой в данный момент? Мы сможем в известном смысле сделать хвостовой вызов к другой части нашего текущего форт слова. Ну что ж, выражение if делает то же самое - условный хвостовой вызов к окончанию if выражения, который выполняется только когда условие пусто.

Так как мы сейчас программируем на форте, нет необходимости добавлять новые примитивы. Чтобы добавить if выражение в форт, мы просто добавим некоторый форт код к нашей стандартной библиотеке макросом forth-stdlib-add. Заметьте, что if определен как незамедлительное слово, это значит, что оно должно использоваться во время компляции. Но так как оно незамедлительное, то оно будет выполнено, а не скомпилировано. Когда встречаются неазмедлительные слова, в заданную нить ничего автоматически не компилируется. Так if сам компилируется в три слова в заданную нить: not, branch-if и nop. Затем выполняется слово here которая вставляет адрес последнего скомпилированного слова (nop) в стек. Оно вставляется в стек? Странное поведение слова во время компиляции. В какой стек вставляем? Строго говоря стек, используемый во время компиляции называется контрольным стеком. В большинстве фортов контрольный стек это то же самое, что и стек параметров. Отличать необходимо из-за различных способов реализации форта. Иногда, особенно в кросс-компиляционных средах, контрольный стек совершенно отличается от того что будет в итоге стеком параметров. Но здесь - как с большинством интерактивных форт сред - мы используем стек параметров для контрольного стека.

Listing 8.25: IF
(forth-stdlib-add
{ compile not
compile branch-if
compile nop
here } ’if name immediate)

Итак, if помещает значение, соответствующее месту, где был скомпилирован nop. Какая от этого польза? Nop сам по себе не очень важен, важно то, что ему предшествует. В ячейке, непосредственно предшествующей nop, находится скомпилированная инструкция branch-if. Что бы мы не меняли значение nop будет местом, куда перейдет наш интерпретатор в случае, если условие окажется null.

Но почему мы поместили туда nop, а не адрес ячейки памяти? Потому что мы еще не знаем этот адрес. Мы должны дождаться, пока программист выполнит другое незамедлительное слово - then - которое потребит значение, оставленное if в контрольном стеке. Then скомпилирует nop и запишет расположение этого nop поверх nop, скомпилированного if. Таким образом, все слова между if и then будут пропущены, если условие равняется null.

Listing 8.26: THEN
(forth-stdlib-add
{ compile nop
here swap ! } ’then name immediate)

Listing 8.27: ABS
(forth-stdlib-add
{ 0 swap - } ’negate name
{ dup 0 < if negate then } ’abs name)

Abs - это слово, использующее if и then для вычисления абсолютного значения верхнего элемента стека. Оно просто проверяет, что значение меньше 0 и, если это так, вызывает другое слово, negate, для перевода отрицательного значения в его абсолютное значение.

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

Так как форт не Флаб язык, то, для нас, для адаптации и расширения, создание и сшивание нитей с контролирующими структурами типа if выражений, определено прозрачно и открыто. Большинство языков имеет else часть, связанную с if выражением; может и нам стоит ее добавить. Еще одно незамедлительное слово else добавлено к стандартной библиотеке. Else компилируется в безусловную ветку, чтобы завершить then, так что если мы пошли по истинной (второй или последующей) ветке, то мы пропустим ложную (третью или альтернативную) ветку. Else таким образом использует значение, оставленное if-ом в стеке, чтобы заменить этот nop ссылкой на начало else части. Затем оно оставляет в стеке ссылку на свой nop для использования then-ом. Так как мы хотим, чтобы then работал одинаково независимо от того, что оставило ссылку if или else, then будет работать даже если if не имеет else части.

Listing 8.28: ELSE
(forth-stdlib-add
{ compile ’t
compile branch-if
compile nop
here swap
compile nop
here swap ! } ’e1se name immediate)

Listing 8.29: MOD2
(forth-stdlib-add
{ evenp if 0 else 1 then } ‘mod2 name)

Listing 8.30: BEGIN-AGAIN
(forth-stdlib-add
{ compile nop
here } ‘begin name immediate
{ compile ’t
compile branch-if
compile nop
here ! } ’again name immediate)

Слово mod2 использует if, else и then чтобы уменьшить целое до его натурального остатка по модулю 2. Оно помещает 0, если вершина стека четная и 1, если нечетное.

Так как наши условные операторы выполняют хвостовые вызовы к другим частям компилируемой нити, то нет причины, по которой мы не можем применить ту же технику для создания таких итеративных конструкций как циклы. Самый базовый форт цикл определён с помощью незамедлительных слов begin и again. Эти два слова обеспечивают простой бесконечный цикл и реализованы очень похоже на if и then, кроме того, что адрес, который сохраняется в стеке между этими словами соответствует адресу,который должен быть скомпилирован в выражение ветвления, а не в место для компиляции адреса. Вот простой цикл для обратного отсчета до 1, начиная от числа, хранящегося в стеке, по достижению 1 производится выход из слова.

* (go-forth my-forth
{ begin
dup 1 < if drop exit then
dup print
1-
again } ’countdown name

5 countdown)

5
4
3
2
1
NIL

В вышеприведенном примере видно, что if и then конструкции вложены внутрь begin-again цикла. Благодаря фортовскому контрольному стеку, он идеально приспособлен для хранения любой контролирующей структуры, соблюдающей стек. Для того, чтобы соблюдать стек, контролирующая структура должна избегать вынимания из стека значений, которые она туда не клала, и не оставлять значений по завершению. Но также как мы, при конструировании лисп макросов, выбираем нарушение ссылочной прозрачности, так и в форте мы часто выбираем несоблюдение стека при компиляции. Следующий пример идентичен предыдущему, кроме использования слова exit при выходе из цикла. Вместо этого мы входим в режим компиляции, используя слова [ и ] и переставляем указатели, помещенные туда словами begin и if так что мы можем использовать соответствующие им слова then и again в другом порядке:

* (go-forth my-forth
{ begin
dup 1 >= if
dup print
1-
[ swap ] again
then
drop
} ’countdown-for-teh-haxorz name
5 countdown-for-teh-haxorz)

5
4
3
2
1
NIL

Выше код, скомпилированный словом again, переносит нас обратно к begin и выполняется только в if выражении. Очень немногие из других языков позволяют вам получать доступ к компилятору таким способом - только не-Флаб языки, если быть точным. Из-за этой свободы форт программисты иногда более привычны к комбинациям макросов чем лисп программисты. Хотя лисп код в этой книге регулярно использует техники комбинаций макросов, эти техники и выигрыш, который они могут предоставить, не используются в полную возможную силу большинством существующего лисп кода. Однако, как это пытается проиллюстрировать книга, лисп исключительно хорошо подходит для комбинаций макросов. Место таких комбинационных техник там, где, как я думаю, находятся одни из наибольших достижений в продуктивности программиста которые будут найдены в, примерно, следующее десятилетие исследований языков.

8.6 Переходим в Лисп

В этой главе до этого момента определялась минимальная форт среда и показаны некоторые из наиболее важных фортовских концепций мета-программирования с точки зрения лиспа. Надеюсь вам стало видно, как мало усилий требуется для проектирования и реализации форта, когда у вас есть правильный инструмент (COMMON LISP). Мы можем писать фортовские программы, которые пишут фортовские программы - но мы и так это знали. Для этого и существует форт. Более того, имея систему макросов лиспа мы можем писать лисповские программы, которые пишут фортовские программы. Но можем ли мы писать фортовские программы, которые пишут лисповские программы?

Listing 8.31: PRINT-FORTH-THREAD
(defun get-forth-thread (forth word)
(with-pandoric (dict) forth
(forth-word-thread
(forth-lookup word dict))))
(defun print-forth-thread (forth word)
(let ((*print-circlet t))
(print (get-forth-thread forth vord))
t))

Вспомним, что наши форт нити это cons ячейки, связанные вместе и что листья этих деревьев это либо функции (представлящющие примитивы), либо атомы (представляющие данные для помещения в стек параметров). Так как мы решили сделать абсртактные регистры форта доступными через пандорические макросы, легко написать утилиты для получения и печати форт нитей. Get-forth-thread пандорически открывает форт замыкание forth, переданное ему, затем получает и возвращает нить слова, переданного в word. Print-to-forth-thread печатает эту результирующую нить с *print-circle*, установленным в t на случай если она содержит циклы.

Для демонстрации предположим что мы определим два форт слова square и squares:

* (go-forth my-forth
{ dup * } ’square name
{ 3 square print } ’square3 name)
NIL

В скомпилированной форт нити, все символы и другая информация, относящаяся к слову будут удалены. Всё что у нас есть - это кусок списковой структуры, извлечённой из форт словаря my-forth:

* (print-forth-thread my-forth ’square3)
(3
(#<Interpreted Function)
#<Interpreted Function>)
#<Interpreted Function>)
T

Вышеприведённый код не имеет циклов и поэтому является чистой Флаб программой. Как было сказано ранее, почти все интересные программы содержат циклы. Для создания условий и циклов мы можем использовать изолированный форт примитив branch-if который позволяет нам изменять абстрактный регистр pc и сослаться с помощью некоторого значения в последующей ячейке на некоторое место в исполняемой форт нити. Также мы в состоянии реализовать хвостовые вызовы через прямой доступ к стеку возврата с помощью >r и r>. В отличие от большинства других языков, мы можем непосредственно модифицировать вызовы в хвостовые вызовы - даже если слово было вызвано извне.

Но, похоже что мы упустили конструкцию, занимающую одно из центральных мест в лиспе: рекурсия. Может ли слово вызвать само себя? Мы увидели как мы можем использовать branch-if для прыжка назад в начало слова - хвостовую рекурсию. Однако, нам по-настоящему хотелось бы получить слово, способное вызвать себя через обычный механизм нити. Для того чтобы сделать это, нужно сохранить начало нити как ячейку в нашей нити, так текущее местоположение будет сохранено в стеке возврата и нужно установить pc в начало слова. До сих пор ни одно из наших слов не было способно использовать полную рекурсию, однако, поскольку мы не называли слово до тех пор, пока не скомпилировали его - оно недоступно для нас пока мы ищем его в словаре, пытаясь скомпилировать рекурсивный вызов. К счастью, есть простой трюк с помощью которого мы можем обойти это ограничение. Мы можем просто выйти из режима компиляции и назвать компилируемое слово до того, как мы скомпилируем рекурсивный вызов. Вот пример определения полностью рекурсивного вычисления факториала:

* (go-forth (setq my-forth (new-forth))
{ [ ’fact name ]
dup 1 -
dup 1 > if fact then
* })

Убедимся, что (fact 5) равно 120:

* (go-forth my-forth
5 fact print)
120
NIL

Упражнение. Некоторые реализации форта используют слово recurse, которое просто ищет начало нити слова, компилируемого в данный момент, и вставляет ее в компилируемую нить. Это называется анонимная рекурсия. Напишите незамедлительное слово, которое делает это как альтернативу именованной рекурсии.

Нить fact более сложная чем нить square3, описанная выше. Она содержит код, ссылающийся на себя:

* (print-forth-thread my-forth ’fact)
#1=(#2=#<Interpreted Function>
1 #<Interpreted Function> #2# 1
#<Interpreted Function>
#<Interpreted Function>
#<Interpreted Function>
#4=(#<Interpreted Function>
#<Interpreted Function>)
#1# . #4#)

В вышеприведенном примере #2# ссылается на примитив dup и был скомпилирован дважды. #1# ссылается на нить fact, реализуя рекурсию.

Эти структуры очень похожи на списковые структуры лиспа, которые мы использовали для написания лисп программ, не так ли? Поскольку мы понимаем абстрактную машину, которая будет исполнять эти нити, то мы можем, с помощью нескольких коротко описанных ограничений, скомпилировать эти форт нити обратно в списковую структуру лиспа, которая может быть вставлена в выражение с помощью макроса и скомпилирована с помощью нашего лисп компилятора. Этот процесс известен как флабирование (flubifying) кода, поскольку мы конвертируем скомпилированную программу из однообразной, программируемой структуры данных (нить) в непрозрачный, недоступный блок кода (скомпилированную COMMON LISP функцию).

Конечно, есть большая разница между нитями форта и лисповскими списковыми структурами, которые мы можем вычислить или вставить в макросы. Во-первых, примитивы форта - это простые указатели на функции (показанные здесь как #<Interpreted Function>), но нам нужна лисповская списковая структура, с которыми были созданы эти функции. И наконец, пришло время разобраться с созданным нами абстрактным регистром dtable. Dtable - это хэш-таблица, которая даёт отображение с этих функций в создавшую их списковую структуру.

Большая разница между форт нитями и нашими лисп программами заключается в том, что форт нити предполагают возможность использования стека возврата - концепции, не существующей на самом деле в таких Флабах, как COMMON LISP. Мы хотим избавиться от необходимости в коде inner-interpreter и, вместо этого, позволить лисп компилятору обрабатывать это с помощью обычных лисповских контрольных структур, как вызов функции и формы tagbody/go.

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

Flubify-aux - это макрос, расширяющийся в функцию, получающую форт нить и конвертирующую её в кусок флаб лисп кода пользуясь тем фактом, что каждое не примитивное слово окружено tagbody и таким образом, можно воспользоваться gensym-ами в роли тегов для goto.

Assemble-flub активно используется в flubify-aux как аббревиатура, проверяющая хэш-таблицу go-ht на присутствие любых переходов обнаруженных в предыдущем проходе, которые ссылаются на место, компилируемое нами в текущий момент. Если это так, то добавляется ранее выбранный gensym тег для этой формы тела тега.

Листинг 8.32: FLUBIFY-AUX
(defmacro flubify-aux ()
‘(alambda (c)
(if c
(cond
((gethash (car c) prim-ht)
(assemble-flub
‘(funcall
,(gethash (car c) prim-ht))
(self (cdr c))))
((gethash (car c) thread-ht)
(assemble-flub
‘(funcall #’,(car (gethash (car c)
thread-ht)))
(self (cdr c))))
((eq (car c) branch-if)
(assemble-flub
‘(if (pop pstack)
(go ,(gethash (cadr c) go-ht)))
(self (cddr c))))
((consp (car c))
(flubify forth (car c) prim-ht
thread-ht branch-if)
(self c))
(t
(assemble-flub
‘(push ’,(car c) pstack)
(self (cdr C))))))))

Листинг 8.33: ASSEMBLE-FLUB
(defmacro assemble-flub (form rest)
‘(if (gethash c go-ht)
(1ist* (gethash c go-ht)
,form
,rest)
(1ist* ,form
,rest)))

Листинг 8.34: FLUBIFY
(defun flubify (forth thread prim-ht
thread-ht branch-if)
(unless #1=(gethash thread thread-ht)
(setf #13 (list (gensym)))
(let ((go-ht (make-hash-table)))
(funcall
(alambda (c)
(when c
(cond
((eq (car c) branch-if)
(setf (gethash (cadr c) go-ht)
Cgensyml)
(self (cddr c)))
((consp (car c))
(flubify forth thread prim-ht
thread-ht branch-if)))
(self (cdr c))))
thread)
(setf #1# (nconc #1# (funcall
(flubify-aux)
thread))))))

Flubify - это функция, использующая flubify-aux. Она выполняет первый проход, проверяет на инструкции branch-if и строит хэш-таблицу go-ht. Также рекурсивно выполняется флабирование всех нитей, присоединённых к нашей текущей нити. На деле flubify может быть двойным рекурсивным - вы просто не видите этого пока не расширите использование flubify-aux. Вы не видите этого, но лисп может. Если ссылочная прозрачность - это прозрачный лист стекла, то здесь мы смотрим в дом зеркал.

Compile-flubified получает хэш-таблицу, построенную с помощью flubify и конвертирует её в форму, использующую labels для привязки каждой из этих флабированных нитей в функцию, именованную с помощью gensym-а в пространстве имён функций. Внутри этой области видимости, его расширение выполняет funcall-ы исходной нити (также флабированной).

Листинг 8.35: COMPILE-FLUBIFIED
(defun compile-flubified (thread thread-ht)
‘(labels (.@(1et (collect)
(maphash
(lambda (k v)
(declare (ignore k))
(push
‘(.(car v) ()
(tagbody ,@(cdr v)))
co11ect))
thread-ht)
(nreverse co11ect)))
(funcall #’,(car (gethash thread thread-ht)))))

Листинг 8.36: FLUBIFY-THREAD-SHAKER
(defun flubify-thread-shaker
(forth thread ht tmp-ht branch-if compile)
(if (gethash thread tmp-ht)
(return-from flubify-thread-shaker)
(setf (gethash thread tmp-ht) t))
(cond
((and (consp thread) (eq (car thread) branch-if))
(if (cddr thread)
(flubify-thread-shaker
forth (cddr thread) ht
tmp-ht branch-if compile)))
((and (consp thread) (eq (car thread) compile))
(error "Can't convert compiling word to 1isp"))
((consp thread)
(flubify-thread-shaker
forth (car thread) ht
tmp-ht branch-if compile)
(if (cdr thread)
(flubify-thread-shaker
forth (cdr thread) ht
tmp-ht branch-if compi1e)))
((not (gethash thread ht))
(if (functionp thread)
(setf (gethash thread ht)
(with-pandoric (dtable) forth
(gethash thread dtab1e)))))))

Листинг 8.37: FORTH-TO-LISP
(defun forth-to-lisp (forth word)
(let ((thread (get-forth-thread forth word))
(shaker-ht (make-hash-table))
(prim-ht (make-hash-tab1e))
(thread-ht (make-hash-table))
(branch-if (get-forth-thread forth ’branch-if))
(compile (get-forth-thread forth ’compile)))
(flubify-thread-shaker
forth thread shaker-ht
(make-hash-table) branch-if compile)
(maphash (lambda (k v)
(declare (ignore v))
(setf (gethash k prim-ht) (gensym)))
shaker-ht)
(flubify forth thread prim-ht thread-ht branch-if)
‘(let (pstack)
(let (,@(let (collect)
(maphash
(lambda (k v)
(push ‘(,(gethash k prim-ht)
(lambda () ,@(butlast v)))
collect))
shaker-ht)
(nreverse collect)))
,(compile-flubified
thread thread-ht)))))

Flubify-thread-shaker - это функция, которая в действительности обходит нашу форт нить. Она рекурсивно перетряхивает все соединенные форт нити. Это значит, что она изолирует только соответствующую структуру форт нити, необходимую для выполнения данной нити с помощью утилиты get-forth-thread, затем переводит каждую функцию в соответствующий лисп код, пропуская if-branch, и создает ошибку, когда обнаруживает compile.

Forth-to-lisp - окончательная функция, которую подготовили предыдущие макросы и функции этой главы. Она принимает среду форта, созданную new-forth, ищет нить, на которую указывает символ, переданный как word, затем возвращает соответствующий lisp код, чтобы выполнить эту нить. Сначала она перетряхивает нить (рекурсивно перебирая все связанные нити), затем применяет процедуру флабификации. И наконец, она оборачивает маленькое количество лисп кода, реализующего внутренний интерпретатор с помощью обычных управляющих структур лиспа.

Для демонстрации вспомним форт слова square и square3, определённые нами ранее. И опять, вот как они были определены в среде форта my-forth:

* (go-forth my-forth
{ dup * } ’square name
{ 3 square print } ’square3 name)
NIL

Здесь мы конвертируем нить square3 в лисп:

* (forth-to-lisp my-forth ’square3)
(LET (PSTACK)
(LET ((#:G1814 (LAMBDA () ; dup
(PUSH (CAR PSTACK) PSTACK)))
(#:G1815 (LAMBDA () ; *
(PUSH (* (POP PSTACK)
(POP PSTACK))
PSTACK)))
(#:G1816 (LAMBDA C) ; print
(PRINT (POP PSTACK)))))
(LABELS ((#:G1817 C) ; square3
CTAGBODY
(PUSH '3 PSTACK)
(FUNCALL #’#:G1818)
(FUNCALL #:G1816)))
(#:G1818 () 3 %quare
(TAGBODY
(FUNCALL #:G1814)
(FUNCALL #:G1815))))
(FUNCALL #’#:G1817))))

Достаточно очевидно, что вышеприведённая программа - это исполняемый лисп код. Если он нам понадобится, то мы можем скомпилировать его где-нибудь используя макрос. Или мы можем просто за-eval-ить его:

* (eval *)
9
NIL

Для того, чтобы увидеть как флаббируется форт нить с ветвлением и рекурсией посмотрим на кусок скомпилированного лисп кода с форт слова fact:

* (forth-to-lisp my-forth ’fact)
(LABELS ((#:G1803 () ; fact
CTAGBODY
(FUNCALL #:G1797) ; dup
(PUSH ’1 PSTACK)
(FUNCALL #:G1798) ; '
(FUNCALL #:G1797) ; dup
(PUSH '1 PSTACK)
(FUNCALL #:G1799) ; >
(FUNCALL #:G1800) ; not
(IF (POP PSTACK) (G0 #:G1804))
(FUNCALL #’#:G1803) ; fact
#:G1804
(FUNCALL #:G1801) ; nop
(FUNCALL #:G1802)))) ; *
(FUNCALL #’#:G1803)) ; fact

Итак, мы написали эту программу с помощью форта, но сейчас эта программа на лиспе. Мы использовали незамедлительные форт слова if и then для компиляции управляющей структуры, работающей с условиями и контролирующей где имеет, а где не имеет место рекурсия. В случае со стеком возврата лисп будет реализовывать для нас эту рекурсию используя традиционную инфраструктуру вызова функции.

Проводя тесты с помощью eval имейте в виду, что слово fact подразумевает наличие значения в стеке, а мы начинаем работу со свежесозданного стека. Для тестирования этого слова мы должны создать обёртку, добавляющую значение в стек. Например:

* (go-forth my-forth
{ 5 fact print } ’fact5 name)
NIL

Которую мы можем выполнить:

* (eval (forth-to-lisp my-forth ’fact5))
120
NIL

Как было замечено, из-за отличий между фортом и лиспом наш компилятор из форта в лисп имеет определенные ограничения. Например, так как мы не можем обеспечить доступ к стеку возврата, то запрещены любые форт слова, использующие r> и >r. К ним относится exit, поэтому наше ранее определенное слово countdown не будет работать. Но будет работать countdown-for-teh-haxorz, так как оно не использует exit. По причине того, что лисп программы не могут получить доступ к их стекам возврата, не все из фортовых управляющих структур могут быть реализованы во флаб языках типа COMMON LISP. Упражнение: Добавьте exit как слово специального случая, использующее лисп блокировки для возврата из слова.

Другое ограничение заключается в том, что лисп код не может компилировать не-флаб код, поэтому мы не можем транслировать форт слова использующие compile, например, if, then, begin и again. Конечно, следует помнить, что форт нити созданные с помощью этих слов по прежнему могут быть использованы для компиляции слов, пример: вышеприведённый fact. И последнее ограничение, в форте branch-if может перепрыгнуть к любой нити, даже если она была создана внутри слова отличающегося от исполняемого в данный момент. В лиспе мы можем использовать go для перехода в другое место только в пределах нашего tagbody. Форт допускает не локальные ветвления, но, в целом, не локальные ветвления не допустимы в таких Флабах как COMMON LISP.

Секундочку. Разве мы не обошли все эти Флаб ограничения ранее, когда программировали в нашей форт среде? Да. Макросы позволяют нам конвертировать программы с лиспа и на лисп. Благодаря макросам всё возможно запрограммировать в лиспе.

Переведено на Нотабеноиде
http://notabenoid.org/book/40014/259170

Переводчики: Charlz_Klug, alex_fff