из AST в c/cpp/objc: как?

1. Пиши на языке с ADT и pattern matching, тогда таких глупых вопросов не будет.

2. Читай про term rewriting.

3. LLVM - это очень, очень просто - см. Kaleidoscope

4. Генери C++, если в процессе выяснится, что никаких особых плюсовых фичей не используешь, переключись на голый Си.

Читай про term rewriting.

Спасибо, у меня всё на нём и основано. Значит я в правильном направлении.

LLVM - это очень, очень просто - см. Kaleidoscope

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

Если ещё один язык с трансляцией в C и не будет LINQ, то стоит задуматься, нужно ли.

Мне изначально предлагали использовать llvm, но для меня это ад.

Недавно попадалась новость, что под него кто-то из/для АМД чего-то параллельного хотел сделать и выяснил, что когда llvm создавали, об этом ещё никто толком не задумывался. С тех пор жду новой новости, что кто-то серьёзно займётся llvm new parallel generation. Но у тебя же не всё так сложно, и всё равно не подошло?

AST само себя обходит и транслируется. Т.е. каждая нода знает как себя преобразовать в код. У этого подхода есть недостатки, кмк.

Визиторы - это говно. Не надо так делать.

Кроме того, не надо сразу генерить код. Это глупо. Нужна цепочка преобразований, и чем они проще каждое по отдельности, тем лучше. Например - отдельный pass над AST для разрешения lexical scoping (присвоение всем переменным новых, уникальных имен), отдельный pass для lambda lifting (можно его предварить еще и pass-ом для вычисления списков свободных и связанных переменных для каждого блока), отдельный pass для превращения структурных конструкций (if, while, for, do, ...) в плоские последовательности из goto и label-ов, и т.д.

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

И какие же такие сложности с параллелизмом в llvm? Рассказывай. Atomic intrinsics имеются в наличии. Чего еще надо от низкоуровневого языка?

llvm

языка

typical linuxoed

Неграмотное чмо пытается тявкнуть, что LLVM IR якобы не является языком, что у него нет синтаксиса и семантики? Ну, тогда и его близкий родственник C-- тоже «не язык», да и C тоже, недалеко по уровню от IR ушедший, тоже «не язык».

Не стыдно тебе быть такой тупой свиньей?

К сожалению, ничего толкового для кодогенерации не нагуглил.

Везде сами делают — GHC (старый бакенд), JHC, UHC, NHC, MLTon, Gambit, Bigloo, Chiken, Stalin, ECL, OOC, Vala для Си (+ рантайм), HPHPc, MOC для С++ (+ рантайм).

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

Кстати о кодогенерации - смотри на nanopass framework:

https://github.com/akeep/nanopass-framework

Но у тебя же не всё так сложно, и всё равно не подошло?

Не нравится мне, например, своим static single assigment. Я так и не понял зачем это должен делать фронтенд для llvm. Или заморочки с типами когда каждый раз в указателях я должен указывать размерность массива. Часть проблем снимается использованием кодогенератора (для llvm их прилично нагородили). Часть же вопросов придётся решать самому. После долгих раздумий я пришёл к выводу что проще будет отранслировать в более высокоуровневый ЯП чем в ассемблер абстрактной рисковой машины.

Не нравится мне, например, своим static single assigment. Я так и не понял зачем это должен делать фронтенд для llvm.

Але! Фротнэнд и не должен никакого SSA уметь! Фронтэнд должен высирать alloca/load/store, а потом llvm это пропустит через mem2reg pass и получит SSA.

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

А кто, кроме тебя, знает эту самую размерность?

После долгих раздумий я пришёл к выводу что проще будет отранслировать в более высокоуровневый ЯП чем в ассемблер абстрактной рисковой машины.

LLVM и так очень высокоуровневый язык. С более строгой типизацией, чем в Си. От Си отличается только тем, что flow явный, и нет высокоуровневых структурных конструкций - ну так они для backend-а и не нужны в любом случае.

в LLVM или JVM

Пиши на языке с ADT и pattern matching, тогда таких глупых вопросов не будет.

Читай про term rewriting.

Я правильно понимаю что ADT и pattern matching нам нужны для ulti-pass tree rewriting? Т.е. что-то типа xquery мы делаем (если говорить моим ламерским языком)?

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

llvm это пропустит через mem2reg pass и получит SSA

Вот это новость. Чёртовы туториалы, половина из тех что я видел на две трети состояла из того как ручками перевести программу SSA и потом откомпилить. Возможно, это было просто объяснение как оно внутри работает, я хз, но мне эти phi() одно время снились.

Если пока не знаешь, что именно выбрать -.генери код на общеи подмножестве Си и Си++. Хотя, ИМХО, Си++ не имеет сиысла в качестве целевого языка, разве что ты стремишься к совместимости именно с Си ++.

А что на счёт obj C?

На счёт целесообразности. В cpp уже есть ООП и генерики, не облегчит ли это жизнь?

В cpp уже есть ООП и генерики, не облегчит ли это жизнь?

Если задаешь такие вопросы, то рановато ты взялся за свой язык.

Если бы я «дорос» то не задавал вопросов на лоре.

Я правильно понимаю что ADT и pattern matching нам нужны для ulti-pass tree rewriting?

Оно и для одного пасса не помешает (хотя, делать все в один проход - это гнусная виртовщина).

Т.е. что-то типа xquery мы делаем (если говорить моим ламерским языком)?

Нет. Из одной точки дерева запросы к другим делать не надо. Достаточно смотреть на локальный кусок дерева через узенькое окно - тот самый pattern matching.

Типа, на произвольном псевдокоде: if(condition, iftrue, iffalse) -> A = newlabel(); B = newlabel(); C = newlabel(); emit({condbranch(compileexpr(condition), A, B); label(A); compilestmt(iftrue); branch(C); label(B); compilestmt(iffalse); branch(C); label(C)})

многие туториалы по компиляторам написаны таким языком что хрен поймёшь

Есть и хорошие. Рекомендую почитать про nanopass, там очень четко и понятно.

Возможно, это было просто объяснение как оно внутри работает, я хз, но мне эти phi() одно время снились.

Можно пользоваться LLVM и ничего про phi вообще не знать.

На лоре можно уже ничего не спрашивать. Был технический ресурс, да весь вышел.

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

Вот, нашёл ссылку: r600g: status of my [Vadim Girlin] work on the shader optimization.

I spent some time last year studying the LLVM infrastructure and R600 LLVM backend and trying to improve it, but after all I came to the conclusion that for me it might be easier to implement all that I wanted in the custom backend. This allows for more simple and efficient implementation - e.g. I don't have to deal with CFGs because in fact we have structured code, so it's possible to use more simple and efficient algorithms.

Ещё:

I understand that it's not tuned for performance, and I understand why, and I think one of the reasons is that it's really hard to tune it for performance for such a non-standard (for LLVM) architecture as r600.

И? R600 действительно странная архитектура, LLVM для обычных RISC-подобных процессоров создавался.

Типа, на произвольном псевдокоде: if(condition, iftrue, iffalse) -> A = newlabel(); B = newlabel(); C = newlabel(); emit({condbranch(compileexpr(condition), A, B); label(A); compilestmt(iftrue); branch(C); label(B); compilestmt(iffalse); branch(C); label(C)})

Можно в пару слов почему ноды AST не могут сами себя преобразовать так как ты пишешь? Пусть if_condition сам создаст нужные блоки, например. Чем это плохо?

для обычных

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

Читай... пиши... генери... изучай...

Ерунда это всё! Главное — не забудь формочку заполнить: http://colinm.org/language_checklist.html

Можно в пару слов почему ноды AST не могут сами себя преобразовать так как ты пишешь?

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

Чем это плохо?

Громоздко, криво, тяжело поддерживать.

Как ты, например, с таким преобразованием справишься:

if(not(condition),iftrue,iffalse) -> if(condition, iffalse, iftrue)

И? Так я об этом и упомянул в первом посте.

Ты писал про параллельные языки. Какое отношение хитровыдрюченные GPU имеют к параллельным языкам? Кстати, чуть более чем все реализации OpenCL работают именно поверх LLVM, так что для GPU оно тоже применимо - не все GPU такие хитровывернутые, как R600.

Как ты, например, с таким преобразованием справишься

Вот так это будет выглядеть:

class Not:
  def __init__(self, expr):
    self.expr = expr
  ...

class IfClause:
  def __init__(self, cond, cons, alt=None):
    self.cond = cond  # condition
    self.cons = cons  # consequence
    self.alt  = alt   # else statement (if any)

  def codegen(self):
    if isinstance(self.cond, Not) and self.alt:
      self.cond = self.cond.expr
      self.cons, self.alt = self.alt, self.cons
    ...

Можешь показать как бы это выглядело на ocaml или haskell?

Ну и на кой хер такая простыня из if-ов? Такой код абсолютно нечитабельный. И ты слил несколько разных pass-ов вместе.

На ML-подобном языке было бы что-то вроде:

let rec ifpass src = 
   match src with
     | If (Not cnd) iftrue iffalse -> If (ifpass cnd) (ifpass iffalse) (ifpass iftrue)
     | _ -> genrecur ifpass src

...

let rec codegen src = 
   match src with
      | If cnd iftrue iffalse -> Seq [(BranchOn (codegen cnd)); ...]
      | ...

И посмотри таки на nanopass

Ты писал про параллельные языки. Какое отношение хитровыдрюченные GPU имеют к параллельным языкам?

Сегодняшние GPU - высокопараллельные вычислительные устройства.

Кстати, чуть более чем все реализации OpenCL работают именно поверх LLVM, так что для GPU оно тоже применимо

Так оно и есть, т.к. боятся/AMD не даёт денег создать что-то более подходящее. А скооперироваться с интелом и нвидией не хочется/не можется.

Сегодняшние GPU - высокопараллельные вычислительные устройства.

Я тебя удивлю, но параллельные вычисления GPU не ограничиваются, языки для GPU никакой особой «параллельной» семантикой не отличаются, а подавляющее большинство GPU ядер - обычные RISC или в крайнем случае VLIW, без особых извращений (таких, как в R600).

В OpenCL или CUDA нет ничего такого «параллельного».

Параллельные языки - это, например, Occam. И я не вижу причин, почему нельзя его реализовать поверх LLVM.

А скооперироваться с интелом и нвидией не хочется/не можется.

Вообще-то они и так все скооперировались (см. Khronos).

И кстати, R600 - далеко не самый извращенческий backend в LLVM. Посмотри на Hexagon, он на порядок страшнее.

А что на счёт obj C?

То же самое, что и насчет Си++ - если специально не стремиться к соместимости, то я лично смысла не вижу.

В cpp уже есть ООП и генерики, не облегчит ли это жизнь?

Ты должен будешь спроектировать свои дженерики и ООП-систему, сделать их поддержку в компиляторе, и после этого, может быть, тебе помогут ООП и шаблоны (никакие не дженерики) Си++. И я так думаю, что помогут они тебе только в том случае, если при проектировании ты будешь ориентироваться на них.

25.01.2013 «как быстро создать свой ЯП?»

23.08.2013 «из AST в c/cpp/objc: как?»

Девятый месяц пылает станица :)

Хорошее упорство, здорово, но кажется что ты какими-то зигзагами движешься к цели.

Я не эксперт, конечно (и, читая некоторые комментарии, надеюсь что никогда им не стану), но довольно часто приходится делать разные DSL-и. Уже писал в предыдущую тему, щас еще раз напишу тезисно.

Дело в том что и граматика не контекстно-свободная и вообще некоторые вещи должны генериться по-разному

Ну вот я бегло посмотрел на livescript, там же можно привести к контекстно-свободной грамматике? И парсить уже традиционно, лексер/LALR(1)-парсер, все дела. Разве что лексер будет слегка развесистый.

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

А зачем тебе, кстати, генерировать С-код? Мне кажется, быстрее будет разработать транслятор, который генерирует свой «байт-код» и выполняет его в своей же (скажем, стековой) ВМ. Для рабочего прототипа должно вполне подойти. Некоторые вообще так и живут, и ничего.

во что транслировать AST

Ну, если уж хочется именно так, то лучше в С, наверное. Если хочется покрыть своим языком побольше, то С нормальный выбор.

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

Разделение на лексер и парсер это и есть шаг назад. Фиксированный и не зависимый от контекста набор токенов, меньше возможностей для подсказок при ошибках, syntax highlighting и авооматического вывода pretty printing. Драконы - чмо устарелое, за пегом будущее.

За все в один проход без AST надо розгами пороть. Иди, посмотри на nanopass, поймешь, насколько ты не прав.

Хорошее упорство, здорово, но кажется что ты какими-то зигзагами движешься к цели.

если делать по-простому, то можно сделать достаточно быстро

Я это делаю под настроение и когда есть время. Иногда захожу в тупик и бросаю, иногда находит вдохновение... Мне главное чтобы приносило радость. Поэтому я старательно избегаю решения которые мне не нравятся. Плюс это хорошая тренировка мозгов.

Ну вот я бегло посмотрел на livescript, там же можно привести к контекстно-свободной грамматике?

Парсинг будем считать пройденным этапом. Он, наверно, кривой по меркам гуру, но парсинг в три прохода (indent -> peg -> pratt == ast) пока решает для меня проблему, причём минимум кода и всяких заморочек (всего 9кб). Я смотрел различные доки по парсерам, ну нахрен килотонны сложного кода когда есть простые средства. Причём, один раз разобравшись писать парсеры не проблема. Надо только знать некоторые типичные грабли и ограничения, но понимание этого быстро приходит. Т.е. не надо читать умные книжки чтобы знать что у peg проблема с рекурсией. Другое дело что в умных книжках напишут как с этим бороться, но я тупо переложил всё на pratt (и немного подпилил грамматику первой версии ЯП чтобы всё красиво друг на друга ложилось, щас в этом нужды нет).

быстрее будет разработать транслятор, который генерирует свой «байт-код» и выполняет его в своей же (скажем, стековой) ВМ

Да можно прямо сейчас каждому элементу AST приделать метод execute() и будет работать :). Но я хочу компилер. Планы у меня наполеоновские :).

Если не секрет, можешь показать что-нить из того что делал? Можно приватом :).

У packrat нет проблем с левой рекурсией. И я тебе когда-то давал уже ссылку на статью.

Но pratt тоже хорошо. Немерлисты по этому же пути пошли.

У packrat нет проблем с левой рекурсией. И я тебе когда-то давал уже ссылку на статью.

Да, спасибо. Теперь я даже понимаю почему. К сожалению, многие статьи слишком сложны для меня. Но я постараюсь осилить nanopass.

В cpp нет генериков. И в С++ тоже.

Генери llvm.

можешь показать что-нить из того что делал?

Open source с DSL-ами? Ну вот http://xenoeye.com , например. Коллектор и анализатор Netflow. Там, правда, DSL простой, чуть сложнее калькулятора, но умеет проверять типы :) DSL нужен для фильтров по IP-адресам, портам, протоколам и для записи что нужно аггрегировать.

Говоришь ему что-то типа такого: фильтр "(daddr in 192.168.0.0/24) and (daddr != 192.168.0.255) and (proto == 6)", поля «sum(octets) desc, saddr». и он выбирает IP-адреса с которых шел TCP трафик на 192.168.0.0/24, кроме широковещательных, суммирует трафик от каждого узла и распологает их в порядке убывания суммы.

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

Еще недавно мы делали препроцессор для программ на языке 1С-предприятия. Чтоб 1С-программистам было проще делать всякие хитрые запросы непосредственно в СУБД. Но это довольно рутинная и нудная работа, самое сложное было добиться от 1С-программистов как им было бы удобнее этой штукой пользоваться. Такое я даже показать стесняюсь, да оно мало кому нужно

В OpenCL или CUDA нет ничего такого «параллельного»

Параллельные операции с данными?

Параллельные языки - это, например, Occam

Occam конкурентный — может предоставлять абстракцию процессов CSP, но при этом работать на одном ядре, то есть не параллельно, а последовательно.

В cpp нет генериков. И в С++ тоже.

А как же http://en.wikipedia.org/wiki/Template_(C++) ? Или темплейты это не то?

http://stackoverflow.com/questions/36347/what-are-the-differences-between-gen...
http://msdn.microsoft.com/en-us/library/c6cyy67b.aspx

Или темплейты это не то?

Ни разу не то. Темплейты — это макросистема, они полностью разворачиваются. Генерики не разворачиваются вообще.

Параллельность там внешняя. Ядро в opencl сугубо последовательное, и с другими потоками не взаимодействует. От чистого Си отличается только наличием векторных операций из коробки и address spaces.

Темплейты — это макросистема

Это, конечно, не так.

Генерики не разворачиваются вообще.

Мономорфизация - это один из способов реализации дженериков.

Это, конечно, не так.

Это, конечно, так.

Мономорфизация - это один из способов реализации дженериков.

Да. Точнее: это один из неправильных способов реализации дженериков.

Это, конечно, так.

+1

это один из неправильных способов реализации дженериков.

Неужели? И почему же? Особенно интересно, что не так с runtime monomorphization.

Неужели? И почему же?

Уже постил на ЛОР как-то раз задачку.

Нужно написать две функции. Одна принимает две последовательности (списки, массивы, вектора, пофигу что) из int-ов (или как они там в вашем языке называются), и возвращает их скалярное произведение. Другая — генерирует каким-то образом две последовательности одинаковой длины (длина идёт к ней параметром), после чего передаёт их первой и возвращает её результат.

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

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

В Хаскеле это делается тривиально.

В C# — легко.

В Java — легко (почти дословно переводится с C#).

В OCaml — с гребенями, но делается.

Это были языки с дженериками. Теперь языки с этой самой мономорфизацией:

С++ — не может.

Rust — не может.

Что забыл?

Точнее: это один из неправильных способов реализации дженериков.

Точнее: это один из способов оптимизации дженериков. Например от такого

test :: (a -> b -> a) -> (b -> b) -> (b -> Bool) -> a -> b -> a
test f s p = go where
  go a x = if p x then a else go (f a x) (s x)

... x :: Int
... test (*) (flip (-) 1) (== 0) 1 x

в core останется только

Rec {
Main.$wgo [Occ=LoopBreaker]
  :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int#
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LL]
Main.$wgo =
  \ (ww_s234 :: GHC.Prim.Int#) (ww1_s238 :: GHC.Prim.Int#) ->
    case ww1_s238 of wild_Xx {
      __DEFAULT ->
        Main.$wgo (GHC.Prim.*# ww_s234 wild_Xx) (GHC.Prim.-# wild_Xx 1);
      0 -> ww_s234
    }
end Rec }

(то есть даже не боксированное).