LINUX.ORG.RU

Аккуратный туториал по созданию интерпретатора императивного динамического языка

 ,


0

2

Мне нужно написать несколько статей про оптимизации в интерпретаторах.
Структура статей должна быть такая:
1) Пишем интерпретатор
2) Накладываем оптимизации

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

Плюс тема имеет тенденцию к разрастанию из туториала на 10 страниц в талмуд на тысячу, в формате «и тут Остапа понесло». Ты ждешь, что там будет всего несколько файлов кода, но у вот уже у тебя несколько десятков классов для айара, и это выглядит как только начало :)

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

Я для низкоуровневой реализации буду юзать джаву (потому что люди, понимающие C++ потихоньку исчезают), поэтому желательно, чтобы у автора туториала было что-то похожее. Не имею целью оскорбить, но лисполапша или ассемблер очень плохо влияют на скорость осмысления и адаптации под императивный язык.

★★★★☆

драгонбук уже советовали?

anonymous ()

Можно еще нагуглить How to create your own freaking awesome programming language. Про динамику, хоть и не java.

anonymous ()

Ребята, да вы офигели :) Нужно что-нибудь страниц на 10 максимум (без листингов), какой нафиг драгонбук.

Да и те десять страниц придется обмазать «картинками для привлечения внимания», иначе современный хаброюзер заскучает примерно так на первой

stevejobs ★★★★☆ ()
Последнее исправление: stevejobs (всего исправлений: 1)

А можно подробнее описать, что Вы таки подразумеваете под «Пишем интерпретатор»? Тут https://www.cis.upenn.edu/~bcpierce/tapl/ в упражнениях например полно мелких интерпритаторов. Я и свой подобный на котлине писал, выходило проще, чем ссылка выше, поскольку я не заморачиваясь сходу вкатал call by value в иерархию подклассов класса Term. Или надо обязательно байткод разработать и решить в каком виде значения хранить в памяти и GC организовать.

q0tw4 ★★★★ ()
Ответ на: комментарий от slaykovsky

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

q0tw4 ★★★★ ()
Ответ на: комментарий от slaykovsky

Самое смешное, что я даже и не догадывался, что то что я делаю - классическая лисп-машина. Для меня это было просто условие задачи и не более того. И то, что тут лучше подходит лисп в качестве фронтенда я решил сам.

q0tw4 ★★★★ ()

но лисполапша или ассемблер очень плохо влияют на скорость осмысления и адаптации под императивный язык

Сообщение удалено tailgunner по причине 4.2, 4.3 и просто толсто (0)

aedeph_ ★★ ()
Ответ на: комментарий от q0tw4

давай порассуждаю вслух

смысл работы такой: представим, что в Java разрешили использовать слово var, чтобы можно было иногда указывать не конкретный тип или статический вывод типа, а полную динамику. Это очевидно приведет к падению производительности, и нам нужно придумать тридцать два способа, как это обойти.

то есть, смысл работы в типах. В оптимизации интенсивной работы с shared mutable state функций с сайдэффектами, вызываемых по модели классического ООП (принцип подстановки Лисков, итп)

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

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

если подумать, то интерпретатор «си с классами» или джаваскрипта (какого-то его минимального подмножества, работающего с прототипами) тут подойдет ок. Мы можем смотреть, что на протяжении определенного «времени», объекты имеют одну и ту же структуру и считать их «временными классами» - это клёво и полностью совпадает с целью происходящего

что нужно сделать

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

дальше нужно написать туториал, пройдя по которому читатель ручками без использования тяжелой машинерии (типа antlr) сможет написать лексер, парсер, трансформатор деревьев, выполнятор этой штуки.

у меня для себя есть «игровой» интерпретатор лиспа, который умеет делать пары, и умеет в функцию последовательного исполнения do. В плане парсинга до ast и ir получается реально очень просто и компактно.

но я думаю что это дохлый номер потому что:

- совершенно весь код должен быть под нотацией do, исходя из смысла происходящего. Мы же оптимизируем в хлам грязный императивный код типа «лапша из ифов»!

- в плане объектной системы нужно пере-изобрести шота типа Common Lisp Object System - что требует телодвижений

- причем так, чтобы все кусочки не валялись отдельно в каких-нибудь defmethod, а были сгруппированы в один монолит на тему Java/C++, иначе пользователей Java/C++ (основная целевая аудитория текста) от такой работы стошнит прямо на пол

- после превращения в ir логику ООП всё равно реализовывать, и лисповские огроаничения внизу будут приносить совершенно не нужную сложность

- last but not least, от лисповой лапши у целевой аудитории (C++/Java программистов) возникает рвотный рефлекс. Для меня это уже всё равно, потому что дело не в синтаксисе, а в ir, но первое впечатление очень важно. Кусок do-нотации посреди скобкоты, в которых без поллитры не справишься - это плохое первое впечатление. Гораздо лучше было бы иметь целевой си-подобный синтаксис

короче, простота лиспа завораживает, но про неё очень плохие предчувствия

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

stevejobs ★★★★☆ ()
Ответ на: комментарий от slaykovsky

в лиспе проблем, которые я решаю, не существует

stevejobs ★★★★☆ ()
Ответ на: комментарий от stevejobs

Мы же оптимизируем в хлам грязный императивный код типа «лапша из ифов»!

Подсказываю как из функциональщины сваять империативщину

seq(
  var("name", "vasya"),
  if(eq($("name"), "muhaha"), 
    statementIf(),
    statementElse(),
  ),
  doAnotherUglyThing(),
)

ну и тп. синтаксис кошмарен, но в приципе фиксится маленьким костыликом парсера

Deleted ()
Ответ на: комментарий от stevejobs

в плане объектной системы нужно пере-изобрести шота типа Common Lisp Object System - что требует телодвижен

FYI: в лиспе существовало много разных объектных систем. Просто CLOS оказался удачным его и взяли в стандарт.

Для игрушечного язычка клос не нужен.

Oxdeadbeef ★★★ ()
Ответ на: комментарий от stevejobs

что в Java разрешили использовать слово var

котлин

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

Object не подойдет? В котлине даже боксинга примитивов не видно. Есть кстати полноценный динамический groovy, правда да, на jvm с динамикой тупит адски (рефлекшен фикли), но говорили вроде, что в .net-е собирались нормальную динамику ввести. Надо чекнуть как там дела обстоят.

в плане объектной системы нужно пере-изобрести шота типа Common Lisp Object System - что требует телодвижений

Смотри классы в ракете. Я в свое время, когда комп был, а инета еще небыло изобрел классы на лиспе сам, вполне так работали даже без макросов, просто много лишнего в синтаксисе было. CLOS конечно крут, но у меня оставались к нему некоторые вопросы по поводу использования разных пакетов. Ну в общем смысл его копировать не совсем ясен.

совершенно все студенты, специализирующиеся на теории типов, пишут точно такие же поделия

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

И это, http://www.squirrel-lang.org видел? Вполне вменяемый скрипт, сочетает простоту подключения из lua и синтаксис из плюсиков.

q0tw4 ★★★★ ()
Ответ на: комментарий от stevejobs

Стиви хауту и руководства быстрого старта по разработке игрушечного языка под LLVM написали задолго до сего треда.

pylin ★★★★★ ()
Ответ на: комментарий от Deleted

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

stevejobs ★★★★☆ ()
Последнее исправление: stevejobs (всего исправлений: 2)
Ответ на: комментарий от stevejobs

без префиксной очень убого выходит, особенно если лямбды внедрять (а ради них и писалось) - потом юзеру ну совсем тяжело понять что за юхня написана, почти как в лиспе 8)

Deleted ()
Ответ на: комментарий от stevejobs

В качестве базовой конструкции есть пары

Пары — это вообще то не конструкции, а структуры данных, linked lists/

их можно даже вот так однопроходно выполнять по мере интерпретации, даже не перегоняя в аст

А в чем проблема делать это с любыми выражениями? Спарсил выражение, выполнил, пошел дальше.

noconformism ()
Ответ на: комментарий от stevejobs

Собственно, в чем смысл построения AST? По-моему, его смысл только в том, чтобы можно было по нему ходить, в других случаях оно если и нужно, то только для читаемости и удобства.

noconformism ()
Ответ на: комментарий от noconformism

в том что ООП - это вообще не про последовательное выполнение. По нему нужно не просто ходить, а еще и постоянно менять по мере исполнения. Собственно про это и есть смысл работы.

stevejobs ★★★★☆ ()
Ответ на: комментарий от stevejobs

А это точно касается AST?:) AST — это абстрактное синтаксическое дерево, это дерево для выполнения кода, а то что меняется представлено структурами языка, которые создаются и меняются в ходе выполнения, это разные вещи. Или я не прав? Скажем, есть синтаксис makeFunction, которая при выполнении создает объект функции, и, этот объект не хранится в AST он существует независимо от него, не?

noconformism ()
Ответ на: комментарий от noconformism

экий ты жирненький :3 гляди, есть конкретный синтаксис (parse tree - то что написал программист), и абстрактный синтаксис (abstract syntax tree - то что нужно компилятору). Один конкретный синтаксис можно отобразить на множество абстрактных.

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

Твоя makeFunction скорее всего изменяет не аст, а конкретные экземпляры выполнения, и это совершенно ортогональный вопрос. То есть, факт вызова makeFunction может привести к изменению аста, да, но сама makeFunction об этом никак не узнает. Можно дать возможность пользовательскому коду управлять трансформациями - например, помечать куски кода «хинтами» типа «@vectorize» - но это совершенно другая песня

stevejobs ★★★★☆ ()
Ответ на: комментарий от stevejobs

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

noconformism ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.