https://hal.inria.fr/hal-01499946/document
"A modular module system", Xavier Leroy

Утверждение, что (ML-style) система модулей не зависит от "базового" языка программирования, и может быть реализована почти для любого, а не только ML, широко известно и озвучивалось в литературе. Данная статья приводит конструктивное доказательство этого тезиса, реализуя такую (слегка упрощённую) систему модулей, в виде, явно параметризованном относительно синтаксиса и системы типов базового языка.

Несмотря на ряд упрощений по сравнению с системой модулей того же Standard ML, представленная модельная система содержит (и корректно реализует) все базовые возможности, включая структурную типизацию модулей, абстрактные типы, функторы, зависимость (типа) результата функтора от (типа) аргумента а также равенства между (абстрактными) типами.

> All in all, module type matching resembles subtyping in a functional language with records, with some extra complications due to the dependencies in functor types and signatures.

Статья составлена в духе Literate Programming, перемежая пояснительный текст и реальный рабочий код на языке OCaml. Реализация системы модулей ML с помощью системы модулей ML отсылает к традиции метациркулярных интерпретаторов Лисп. Леруа выражает надежду, что такой способ представления материала не только не запутает читателя, но и дополнительно прояснит связь конкретного и абстрактного синтаксиса как и практическую полезность (и даже необходимость) всех возможностей представленной системы. (По-видимому, метациркулярность системы не оставила Лисперов равнодушными, что привело к появлению реализации MiniML с полноценной системой модулей на Scheme: http://wiki.call-cc.org/eggref/4/miniML 😊)

Для иллюстрации приводятся два примера "надстраивания" реализованной системы модулей над "упрощённым C" в качестве императивного (процедурного) базового языка и Mini-ML в качестве функционального, приближенного к используемым на практике, в частности, реализующего типы высших порядков (Higher-Kinded Types).

Кратко обсуждаются вопросы (модульной) компиляции таких модулей. Упоминаются три основных варианта: компиляция самих модулей в виде структур данных, а функторов — в виде (полиморфных) функций, специализация функторов для всех применений в духе C++ templates и полное стирание модулей во время компиляции (аналогично девиртуализации вызовов методов в ООП). Но за деталями интересующиеся читатели отсылаются к соответствующим публикациям.

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

Таким образом, статья представляет собой практическое введение в ML-style системы модулей и связанные вопросы, полезное как для пользователей таких систем, так и для авторов языков программирования, желающих реализовать собственную систему модулей. 😊

#modules #sml #ocaml #leroy #classic

Рекурсивный спуск - это реализация LL(k).

Вообще-то, нет.
Рекурсивный спуск обычно начинается как реализация LL(1), а потом нередко превращается в кашу просто код на используемом языке, который примерно похож на реализацию грамматики, но на самом деле разбирает unrestricted grammar (т.е. и близко не LL(1) по мощности). В общем, это такой "ассемблер" среди парсеров — разобрать можно что угодно, но a) разбирается уже не грамматика, а что-то непонятное, к чему нельзя применить формальные подходы (доказать неоднозначность, "вытащить" в виде EBNF или NPDA и так далее) и б) все проблемы работы с машиной Тьюринга (или её аналогами, если реализация в функциональном языке / используются комбинаторы и т.п., если я правильно понимаю) "входят в комплект".

"Что угодно"-то нет, без левой-то рекурсии

Именно поэтому я сел писать свой LR-генератор, и он даже уже что-то парсит (но лексер пока сломан)

Только "наивная" реализация recursive descent не может работать с левой рекурсией.
Опять-таки, суть в том, что в нём можно написать вообще всё, что угодно. И пишут же, между прочим.

Не-наивную-то, без раскрутки (подъёма, по сути) или трансформации LR->LL сделать сложно, в отличие от LR

Я в терминологии не силен, не закидывайте камнями. Верно, LL(k) не предусматривает возврат к предыдущим символам. Я имел ввиду recursive descent parser with backtracking. В моей реализации я заглядываю максимум на 1 лексему вперед, поэтому это является LL(1) , так ведь?

Также появился вопрос, Clang, GCC и прочие компиляторы реализуют рекурсивный спуск с откатом LL(*)? Необязательно писать собственный LR парсер генератор для разбора особо сложных грамматик как к примеру в С++. Я верно понимаю?

Я хочу выбрать для себя путь реализации парсера, так как грамматика моего языка не может быть разобрана при помощи стандартного LL(k) парсера.

Насколько я могу судить по тому, что было выше, плюсы без lr не вскрыть
Но могу ошибаться, конечно, я только вкатываюсь

Я делал генератор LR(1)-таблиц по драгонбуку, и это, к моему величайшему удивлению, оказалось не сложно, да и реализация ядра заняла немного времени.

Раньше я писал парсеры языков на рекурсивном спуске

expr = foldl1 App (some term)  -- f x y z

term = lam <|> num <|> var <|> ...

lam = do  -- \x y z -> body
  token "fun"
  az <- many arg
  token "->"
  body <- expr
  return (Lam az body)

Но потом меня начало воротить от этого, потому что
1) нет левой рекурсии - приходится левоассоциативные конструкции a x b парсить как a (x b)*, а потом переворачивать руками
2) можно запросто написать парсер, который разбирает какой-то кусок за O(expr(N))
3) чтобы этого не случилось, есть комбинатор try, включающий бэктрекинг, но он делает код некрасивым
3) <|> - это ambiguous choice, и выяснить без тестов, что правило Field = Expr {field-decl} берёт приоритет над Field {capture} и поэтому {foo = 1, bar} ожидает = после bar для более сложных конструкций можно только через тесты.

У LR есть свои проблемы:
1) U have 51 shift/reduce and 3 reduce/reduce conflicts.
2) Без приоритетов не разрулить некоторые ситуации. Ну или разрулить - перепахав всю грамматику. Но я бы посовтовал слушать LR, оно обычно херни не посоветует.

У LR есть преимущества:
1) конфликты - это ситуации, которые потом придётся ловить тестами, т.е., LR-генератор делает статическую верификацию однозначности грамматики.
2) LR всегда разбирает за O(N).
3) Грамматика в виде .y-файла или EDSL выглядит как грамматика.

Теперь к вопросам.

LL(k) ничего не говорит про возврат, только про то, что для выбора нужно заглянуть не далее чем на k лексем вперёд.

Нормальные компиляторы берут LR-генератор. Я видел одних (michelson), которые вручную сделали рекурсивный подъём. ANTLR делает LL(k), насколько я знаю, но я рекомендую взять yacc, menhir, happy или любой другой аналог.

> грамматика моего языка не может быть разобрана при помощи стандартного LL(k) парсера

LR, самый простой способ. Заодно поправите кучу неоднозначностей в грамматике.

Да, необязательно писать LR-генератор, можно взять готовый.

——

На каком языке пишете? Если будете делать свой LR-парсер, я могу проконсультировать

expr = foldl1 App (some term)  -- f x y z

term = lam <|> num <|> var <|> ...

lam = do  -- \x y z -> body
  token "fun"
  az <- many arg
  token "->"
  body <- expr
  return (Lam az body)

Спасибо за развернутый ответ. К сожалению, я очень много чего не понял)

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

Пишу на Go) С функциональными языками никогда не сталкивался

> парсером возврата которые требует экспоненциальное время работы

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

Я прям открыл драгонбук на реализации LR(0) и по тексту делал.

Уву, асуждаю, я не выношу читать не с самого начала книги

Тогда придётся одолеть ещё 300+ страниц

Я сделаю это или умру, пытаясь.

Вот это хороший подход

Я так хаскель лезу изучать.

Иногда надо делать передышку, чтобы утряслось

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

/me изучал и в большой степени изучил Haskell, когда книжек по нему не было вообще...