Как сделать язык гомоиконическим

16

Согласно этой статье следующая строка кода на Лиспе выводит «Hello world» на стандартный вывод.

(format t "hello, world")

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

Теперь представьте, что мы написали следующий макрос:

(defmacro backwards (expr) (reverse expr))

в обратном направлении - это имя макроса, который принимает выражение (представленное в виде списка) и обращает его в обратном порядке. Вот снова «Hello, world», на этот раз с помощью макроса:

(backwards ("hello, world" t format))

Когда компилятор Lisp видит эту строку кода, он смотрит на первый атом в списке ( backwards) и замечает, что он называет макрос. Он передает неоцененный список ("hello, world" t format)макросу, который переупорядочивает список (format t "hello, world"). Результирующий список заменяет выражение макроса, и это то, что будет оцениваться во время выполнения. Окружение Lisp увидит, что его первый atom ( format) является функцией, и оценит его, передав ему остальные аргументы.

В Лиспе решить эту задачу легко (поправьте меня, если я ошибаюсь), потому что код реализован в виде списка ( s-выражения ?).

Теперь взгляните на этот фрагмент OCaml (который не является гомоиконическим):

let print () =
    let message = "Hello world" in
    print_endline message
;;

Представьте, что вы хотите добавить гомоконичность в OCaml, который использует гораздо более сложный синтаксис по сравнению с Lisp. Как бы Вы это сделали? Должен ли язык иметь особенно простой синтаксис, чтобы достичь гомоконичности?

РЕДАКТИРОВАТЬ : из этой темы я нашел другой способ достижения гомоконичности, отличающийся от Lisp: тот, который реализован на языке io . Это может частично ответить на этот вопрос.

Здесь давайте начнем с простого блока:

Io> plus := block(a, b, a + b)
==> method(a, b, 
        a + b
    )
Io> plus call(2, 3)
==> 5

Итак, блок работает. Блок плюс добавил два числа.

Теперь давайте сделаем некоторый самоанализ этого маленького парня.

Io> plus argumentNames
==> list("a", "b")
Io> plus code
==> block(a, b, a +(b))
Io> plus message name
==> a
Io> plus message next
==> +(b)
Io> plus message next name
==> +

Горячая святая холодная плесень. Вы можете не только получить названия параметров блока. И не только вы можете получить строку полного исходного кода блока. Вы можете проникнуть в код и просмотреть сообщения внутри. И самое удивительное: это ужасно просто и естественно. Верный для квеста Ио. Зеркало Руби не видит ничего из этого.

Но, воу, воу, эй, не трогай этот диск.

Io> plus message next setName("-")
==> -(b)
Io> plus
==> method(a, b, 
        a - b
    )
Io> plus call(2, 3)
==> -1
incud
источник
1
Возможно, вы захотите взглянуть на то, как Scala делала свои макросы
Bergi
1
У @Bergi Scala новый подход к макросам: scala.meta .
Мартин Бергер
Я всегда, хотя гомоконичность переоценена. В любом достаточно мощном языке вы всегда можете определить древовидную структуру, которая отражает структуру самого языка, и можно написать вспомогательные функции для перевода в исходный язык и из него (и / или в скомпилированную форму) по мере необходимости. Да, в LISP это немного проще, но, учитывая, что (а) подавляющее большинство работ по программированию не должно быть метапрограммированием и (б) LISP пожертвовал ясностью языка, чтобы сделать это возможным, я не думаю, что компромисс стоит того.
Периата Breatta
@PeriataBreatta Вы правы, но ключевое преимущество MP в том, что MP позволяет абстракции без штрафа во время выполнения . Таким образом, MP устраняет противоречие между абстракцией и производительностью, хотя и за счет увеличения языковой сложности. Стоит ли оно того? Я бы сказал, что тот факт, что все основные PL имеют расширения MP, указывает на то, что многие работающие программисты находят компромиссные предложения MP полезными.
Мартин Бергер

Ответы:

10

Вы можете сделать любой язык homoiconic. По сути, вы делаете это путем «зеркалирования» языка (то есть для любого языкового конструктора вы добавляете соответствующее представление этого конструктора в виде данных, подумайте AST). Вам также необходимо добавить несколько дополнительных операций, таких как цитирование и отмена цитаты. Это более или менее так.

У Lisp это было рано из-за его простого синтаксиса, но семейство языков MetaML W. Taha показало, что это возможно для любого языка.

Весь процесс изложен в Моделировании однородного генеративного метапрограммирования . Более легкое введение в тот же материал здесь .

Мартин Бергер
источник
1
Поправьте меня если я ошибаюсь. «Зеркальное отображение» относится ко второй части вопроса (гомоконичность в io lang), верно?
incud
@Ignus Я не уверен, что полностью понимаю ваше замечание. Цель гомоконичности заключается в том, чтобы дать возможность трактовать код как данные. Это означает, что любая форма кода должна иметь представление в виде данных. Есть несколько способов сделать это (например, квази-кавычки AST, используя типы, чтобы отличить код от данных, как это делается с помощью легкого модульного поэтапного подхода), но все они требуют дублирования / зеркального отражения синтаксиса языка в некоторой форме.
Мартин Бергер
Я предполагаю, что @Ignus выиграет от просмотра MetaOCaml? Значит ли быть «гомикономичным» просто значит быть цитируемым? Я предполагаю, что многоэтапные языки, такие как MetaML и MetaOCaml, идут дальше?
Стивен Шоу,
1
@StevenShaw MetaOCaml очень интересен, особенно новый BER MetaOCaml Олега . Тем не менее, он несколько ограничен в том, что он выполняет только метапрограммирование во время выполнения и представляет код только через квази-кавычки, которые не так выразительны, как AST.
Мартин Бергер
7

Компилятор Ocaml написан на самом Ocaml, поэтому, безусловно, есть способ манипулировать AST Ocaml в Ocaml.

Можно было бы представить добавление встроенного типа ocaml_syntaxк языку и наличие defmacroвстроенной функции, которая принимает ввод типа, скажем

f : ocaml_syntax -> ocaml_syntax

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

Эта проблема не возникает в lisp, поскольку язык динамически типизирован, и никакой тип не должен быть приписан самому макросу во время компиляции. Одним из решений было бы иметь

defmacro : (ocaml_syntax -> ocaml_syntax) -> 'a

что позволит использовать макрос в любом контексте. Но это небезопасно, конечно, это позволило быbool бы использовать вместо string, сбой программы во время выполнения.

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

В заключение: наличие сложного синтаксиса не является проблемой, поскольку существует много способов представить синтаксис внутри языка и, возможно, использовать метапрограммирование как quoteоперацию для встраивания «простого» синтаксиса во внутренний ocaml_syntax.

Проблема состоит в том, чтобы сделать это хорошо типизированным, в частности, имея механизм макро-времени выполнения, который не допускает ошибок типа.

Имея время компиляции механизм макросов на языке , как OCaml можно, конечно, смотри , например , , MetaOcaml .

Также возможно полезно: улица Джейн на метапрограммировании в Окамле

Коди
источник
2
MetaOCaml имеет метапрограммирование времени выполнения, а не метапрограммирование времени компиляции. Также система ввода MetaOCaml не имеет зависимых типов. (MetaOCaml также был признан неподходящим для типов!) У шаблона Haskell есть интересный промежуточный подход: каждый этап безопасен для типов, но при переходе на новый этап мы должны повторно выполнить проверку типов. По моему опыту, на практике это работает очень хорошо, и вы не потеряете преимущества безопасности типов на заключительном этапе (во время выполнения).
Мартин Бергер
@ Может быть, есть метапрограммирование в OCaml также с точками расширения , верно?
incud 14.09.16
@Ignus Боюсь, я мало что знаю о точках расширения, хотя я упоминаю об этом в ссылке на блог Джейн Стрит.
Коди
1
Мой компилятор C написан на C, но это не значит, что вы можете манипулировать AST в C ...
BlueRaja - Дэнни Пфлугхофт
2
@immibis: Очевидно, но если это то, что он имел в виду, то это утверждение и бессмысленно, и не имеет отношения к вопросу ...
BlueRaja - Дэнни Пфлугхофт
1

В качестве примера рассмотрим F # (на основе OCaml). F # не полностью гомоичен, но поддерживает получение кода функции как AST при определенных обстоятельствах.

В F # ваш printбудет представлен как, Exprкоторый печатается как:

Let (message, Value ("Hello world"), Call (None, print_endline, [message]))

Чтобы лучше выделить структуру, вот альтернативный способ, как вы могли бы создать то же самое Expr:

let messageVar = Var("message", typeof<string>)
let expr = Expr.Let(messageVar,
                    Expr.Value("Hello world"),
                    Expr.Call(print_endline_method, [Expr.Var(messageVar)]))
svick
источник
Я не поняла это. Вы имеете в виду, что F # позволяет вам «построить» AST выражения и затем выполнить его? Если да, то в чем разница с языками, которые позволяют использовать эту eval(<string>)функцию? ( Согласно многим ресурсам, наличие функции eval отличается от гомоконичности - это причина, по которой вы сказали, что F # не полностью гомоичен?)
incud
@Ignus Вы можете создать AST самостоятельно или позволить компилятору это сделать. Гомоиконичность "позволяет получить доступ ко всему коду на языке и преобразовать его в данные" . В F # вы можете получить доступ к некоторому коду в качестве данных. (К примеру, вам нужно знаком printс [<ReflectedDefinition>]атрибутом.)
svick