Как вы компилируете макросы в компиляторе Lisp?

Question

В интерпретаторе Lisp в eval может легко существовать ветвь, которая может расширять макрос, и в процессе его расширения вызывать функции для создания расширенного выражения. Я делал это до того, как использовал низкоуровневые макросы, это легко сделать.

Но в компиляторе нет никаких функций для вызова расширенного кода: проблему можно увидеть довольно просто в следующем примере:

(defmacro cube (n)
    (let ((x (gensym)))
      `(let ((,x ,n))
          (* ,x ,x ,x))))

Когда макрос раскрывается интерпретатором, он вызывает gensym и делает то, что вы ожидаете. При расширении компилятором вы сгенерируете код для let, который связывает x с (gensym), но символ gensymmed необходим только для компилятора, чтобы делать правильные вещи. А поскольку gensym на самом деле не вызывается до компиляции макроса, это не очень полезно.

Это становится еще более странным для меня, когда макрос создает список для использования в качестве расширения, используя map или filter.

Так как это работает? Конечно, скомпилированный код не скомпилирован в (eval *macro-code*), потому что это было бы ужасно неэффективно. Есть ли хорошо написанный компилятор Lisp, где это ясно?

Answer 1

Как это работает, сильно отличается в разных диалектах Лисп.Для Common Lisp он стандартизирован в стандарте ANSI Common Lisp, и различные реализации Common Lisp отличаются в основном от того, используют ли они компилятор, интерпретатор или оба.

В следующем предполагается, что Common Lisp.

EVAL не переводчик .EVAL может быть реализован с помощью компилятора.Некоторые реализации Common Lisp даже не имеют интерпретатора.Затем EVAL является вызовом компилятора для компиляции кода, а затем вызывает скомпилированный код.В этих реализациях используется инкрементный компилятор, который может компилировать также простые выражения, такие как 2, (+ 2 3), (gensym) и т. Д.

Макроразложение выполняется с помощью функций MACROEXPAND и MACROEXPAND-1.

Макрос в Common Lisp - это функция, которая ожидает некоторые формы и возвращает другую форму.DEFMACRO регистрирует эту функцию как макрос.

Ваш макрос

(defmacro cube (n)
  (let ((x (gensym)))
    `(let ((,x ,n))
        (* ,x ,x ,x))))

- не что иное, как функция Lisp, которая зарегистрирована как макрос.

Эффект похож наthis:

(defun cube-internal (form environment)
  (destructuring-bind (name n) form   ; the name would be CUBE
    (let ((x (gensym)))
      `(let ((,x ,n))
         (* ,x ,x ,x)))))

(setf (macro-function 'my-cube) #'cube-internal)

В реальной реализации CL DEFMACRO расширяется по-разному и не использует имя, подобное CUBE-INTERNAL.Но концептуально это определение макрофункции и ее регистрация.

Когда компилятор Lisp видит определение макроса, он обычно компилирует макрофункцию и сохраняет ее в текущей так называемой среде.Если среда является средой выполнения, она запоминается во время выполнения.Если среда является средой компилятора при компиляции файла, макрос будет забыт после компиляции файла.Скомпилированный файл должен быть загружен так, чтобы Lisp знал макрос.

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

Когда компилятор теперь видит некоторый код, который использует макрос (cube 10), тогда компилятор просто вызывает функцию макроса, которая хранится в текущей среде.под именем CUBE вызывает эту макрофункцию, которая 10 в качестве аргумента, а затем компилирует сгенерированную форму.Как упоминалось выше, это делается не напрямую, а через функции MACROEXPAND.

Вот определение макроса:

CL-USER 5 > (defmacro cube (n)
              (let ((x (gensym)))
                `(let ((,x ,n))
                   (* ,x ,x ,x))))
CUBE

Мы скомпилируем макрос:

CL-USER 6 > (compile 'cube)
CUBE
NIL
NIL

MACRO-FUNCTION возвращает функцию для макроса.Мы можем вызвать его как любую другую функцию с FUNCALL.Он ожидает два аргумента: целую форму, такую ​​как (cube 10) и среду (здесь NIL).

CL-USER 7 > (funcall (macro-function 'cube) '(cube 10) nil)
(LET ((#:G2251 10)) (* #:G2251 #:G2251 #:G2251))

Также можно взять функцию (которая принимает два аргумента: форму и среду) и сохраните его, используя SETF в качестве макрофункции.

Сводка

Когда работает компилятор Common Lisp, он просто знает функции макроса и при необходимости вызывает их для расширениякод через встроенный макроэкспандер.Макро-функции - это просто код на ЛиспеКогда компилятор Lisp видит определение макроса, он компилирует функцию макроса, сохраняет ее в текущей среде и использует ее для расширения последующего использования макроса.

Примечание. В Common Lisp необходимо, чтобы макросопределяется до того, как он может быть использован компилятором.

Answer 2

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

Так что FEXPER были выброшены в пользу макросов, которые в некотором роде более "хорошо себя ведут".Вы в основном выполняете расширение макроса один раз и компилируете полученный код.Как обычно, здесь есть несколько стратегий, которые могут привести к разным результатам.Например, «развернуть один раз» не указывает , когда расширяется.Это может произойти, как только код будет прочитан, или (обычно), когда он скомпилирован, или даже просто при первом запуске.

Другой вопрос здесь - и это, по сути, то, где вы стоите -в какой среде вы оцениваете код макроса.В большинстве Лиспов все происходит в одной и той же счастливой глобальной среде.Макрос может свободно обращаться к функциям, что может привести к некоторым тонким проблемам.Одним из результатов этого является то, что многие коммерческие реализации Common Lisp предоставляют вам среду разработки, в которой вы выполняете большую часть своей работы и компилируете вещи - это делает одну и ту же среду доступной на обоих уровнях.(На самом деле, поскольку макросы могут использовать макросы, здесь существует произвольное количество уровней.) Для развертывания приложения вы получаете ограниченную среду, в которой нет, например, компилятора (то есть функции compile), посколькуесли вы развертываете код, который использует это, ваш код по сути является компилятором CL.Таким образом, идея состоит в том, что вы компилируете код на полную реализацию, и это расширяет все макросы, что означает, что скомпилированный код не использует макросы дополнительно.

Но, конечно, это может привести к тем тонким проблемам, которыеЯ говорил о.Например, некоторые побочные эффекты могут привести к беспорядку в порядке загрузки, когда вам нужно загрузить код в определенном порядке.Хуже того, вы можете попасть в ловушку, где код выполняется для вас в одну сторону, а в другую - когда компилируется - поскольку во скомпилированном коде все макросы (и вызовы, которые они совершали) уже были расширены заранее.Есть несколько хакерских решений, таких как eval-when, которые определяют определенные условия для оценки некоторого кода.Есть также несколько систем пакетов для CL, где вы указываете такие вещи, как порядок загрузки (например, asdf ).Тем не менее, там нет реального надежного решения, и вы все равно можете попасть в эти ловушки (см., Например, этот расширенный спор ).

Конечно, есть альтернативы.В частности, Racket использует свою модульную систему.Модуль может быть "создан" несколько раз, и состояние уникально для каждого экземпляра.Теперь, когда какой-либо модуль используется как в макросах, так и во время выполнения, два экземпляра этих модулей различны, что означает, что компиляция всегда надежна, и ни одна из перечисленных выше проблем не возникает.В мире Scheme это называется «отдельными фазами», где каждая фаза (время выполнения, время компиляции и более высокий уровень с макросами-использованием-макросами) имеет отдельные экземпляры модуля.Для хорошего ознакомления с этим и подробного объяснения прочитайте Мэтью Флэтт * Компонируемые и компилируемые макросы .Вы также можете просто взглянуть на Racket docs , например, раздел Фазы компиляции и выполнения .

Answer 3

Вы обнаружили одно из основных отличий между Лиспом и другими языками.

В Лиспе выполнение динамически создаваемого кода необходимо и, например, необходимо для расширения макроса.

При написанииlisp to C compiler Я обнаружил эту теперь очевидную вещь сам и пришел к выводу, что если вы хотите написать компилятор Lisp, есть только два решения:

1. Вы пишете ОБА компилятор иинтерпретатор, так что вы можете вызвать интерпретатор для расширения макроса во время компиляции.

2. Вы должны быть в состоянии динамически компилировать код и вызывать его (или использовать худшие "приемы", такие как компиляция динамически загружаемого модуляи затем загрузить его).

Если вы работаете над компилятором для C, одна из возможностей - использовать библиотеку TCC Фабриса Белларда , которая позволяет прямую компиляцию кода C длябуфер памяти.

Я пишу Lisp для компилятора Javascript, и в этом случае, конечно, нет проблемlem, потому что «железо» может с этим справиться, и вы можете попросить Javascript оценить, например, строку "function(...){...}", а затем вызвать получившийся объект.Использование Javascript также решает, что является IMO одной из самых сложных проблем для ядра Lisp, которая заключается в правильной реализации лексических замыканий.

Действительно, в моем компиляторе javascript eval просто более или менее

(defun eval (x)
    (funcall (js-eval (js-compile x))))

где js-compile является основным интерфейсом компилятора, и при наличии формы lisp вернет строку, содержащую код javascript, который при оценке (с eval javascript, который я экспортировал до уровня lisp как js-eval) выполняет код.Интересно также, что eval никогда не используется (за единственным несущественным исключением из вспомогательного макроса, в котором я должен выполнять пользовательский код во время раскрытия макроса).

Одна важная вещь, которую следует учитывать, - это то, что в Common Lisp естьТакое разделение между «временем чтения», «временем компиляции» и «временем выполнения», однако, это разделение более логично, чем физическое, поскольку работающий код всегда Lisp.Компиляция в Лиспе - это просто вызов функции.Даже фаза "синтаксического анализа" - это просто выполнение обычной функции lisp ... это Лисп до конца: -)

Ссылки на мой компилятор игрушек Lisp → Js

• Исходный код
• Видео демо 1
• Видео демо 2
• Сайт

Answer 4

В макросах нет ничего особенного.

На высоком уровне они просто функции. Функции, которые возвращают S-Exprs для форм Lisp. «Время выполнения» для макроса доступно в функции macroexpand, которая, как вы, возможно, уже знаете, расширяет макросы.

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

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