CST, а это отнюдь не однопроходный компилятор (aka syntax-directed translation)

Тут какая-то путаница в терминологии. Вот же я baverman'у писал:

Cинтаксически управляемая трансляция - это просто связывание синтаксического анализатора с «действиями». Действия могут быть какими угодно: непосредственное выполнение, генерация кода для выполнения позже, еще что-нибудь

В академических кругах (и на спецкурсах по CS) под «еще что-нибудь» предполагается генерация AST. Но во многих случаях это лишнее.

Именно - они ее сделали. Причем сделали давно.

Да я же уже писал: сделать генерацию AST - не фокус, это не сложнее чем генерировать байткод. А вот что с ним делать дальше? «анализировать и трансформировать»?. Это очень нетривиально, хорошо такое сделать могут себе позволить вообще единицы проектов, основная масса генерируют потому что так в книжках пишут. А потом из AST просто делают байткод. Ну вот как в Руби, например.

AST не имеет отношения к интерпретации. Если ТС хочет статическую типизацию(...), ему нужно представление гораздо более высокого уровня, чем байткод

Обычно типы операндов известны в первом проходе и можно их сразу же проверять.

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

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

На всякий случай: я не противник использования AST в трансляторах если они действительно нужны. Иногда построение такого дерева не нужно для трансляции, но его (или что-то похожее) нужно генерировать отдельно для рефлексии.

Но начинать разработку нового языка с этого (если цель просто написать транслятор) - перебор

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

А много трансляторов ты написал? Подозреваю, чир нисколько.

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

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

В общем, напиши сначала пару-тройку трансляторов, а потом уже имей мнение.

Racket или PFront/mbase.

Динамически типизированный отстой. Есть гораздо более адекватные и более декларативные подходы.

Именно - они ее сделали. Причем сделали давно.

Да я же уже писал: сделать генерацию AST - не фокус

Ты написал, что Ruby до сих пор обходится без AST - это утверждение ложно.

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

Ага, сохраним в байткоде еще отображение терма на source location, и получим... кривой аналог AST. Но, конечно, так тоже можно.

А вот что с ним делать дальше? «анализировать и трансформировать»?. Это очень нетривиально,

Чушь. Это тривиально. Это полностью декларативно. Для этого даже Тьюринг-полного языка не надо.

хорошо такое сделать могут себе позволить вообще единицы проектов,

Чушь.

основная масса генерируют потому что так в книжках пишут.

Чушь. Это просто удобно.

С другой стороны, если хочется еще и прокачать LLVM скилл и помучиться с оптимизацией на AST - ну да, наверное, надо идти сложным путем

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

,

NB: всё это just for fun. Тем более что уже много готовых средств для этого, почему бы ими не воспользоваться?

Основной упор я хочу сделать на элегантность синтаксиса. Мне нравится синтаксис питона. По крайней мере как там выглядят функции и классы. А так же отсутствие скобочек. Это оставляю. А вот тернерный оператор из си не помешал бы :)

Не нравится: динамическая типизация (у меня, увы, тоже пошли ошибки, теперь без тестов никуда) и отсутствия дополнительных контекстов. Хочу следующие контексты: 1) встроенные регекспы 2) вызов шелл-комманд в бэктиках, это чертовски удобно в скриптах 3) возможность определения доп-контекстов аля «а вот тут идёт сишный код». Сишный потому что у меня достаточно много си потому что на нём написано ядро и куча библиотек. Соотв. хочу удобное средство интеграции.

3) бесшовная интеграция с C. При использовании llvm это тривиально если считать что сам llvm тривиален и типы данных совместимы с сишными. Вызвать printf у меня получилось (скопипастил пример из туториала) :). Но синтаксис сложноват для человека который асм держал один раз лет 10 назад при программировании микроконтроллера. Да и вообще открывается дорога ко всему что построено поверх llvm. Кстати, при нормальной интеграции в си можно будет встраивать и питонячий код (опыт написания экстеншенов к питону есть) :). Не знаю, правда, зачем, но можно.

4) ООП: хочу сделать упор на интерфейсах и сделать public/private/protected поля с явным указанием типа.

5) есть ещё идеи которые я подсмотрел в haskell, ocaml и руби. Пока рано об этом говорить. Например, использовать функции как операторы в `infix` нотации. А так же возможность вводить свои операторы. Впрочем, это можно сделать через концепцию интерфейсов (наверно, это содрано с type classes у хаскеля).

Пока я по диагонали прочитал мануал к llvm и сейчас думаю на счёт парсера.

Динамически типизированный

Будто что-то плохое.

отстой

Обоснуй.

Есть гораздо более адекватные и более декларативные подходы.

Например?

Будто что-то плохое.

В данном контексте - да, очень плохое. Важно верифицировать, что преобразования определены над ровно тем AST, что выдает парсер и что сам парсер корректное дерево создает.

Обоснуй.

Racket: примитивный (но быстрый) генератор парсеров, слабые средства для описания преобразований над AST, в качестве target только сам Racket. Довольно тормозной и мало с чем совместимый рантайм.

Mbase: леворекурсивный Packrat, что хорошо, но при этом весьма тормозной код парсера генерится. Никакой проверки корректности результата, и никаких внятных сообщений об ошибках. Типизированные AST используются только для генерации кода визиторов, но любая ошибка приводит к длинным нечитабельным выхлопам, хуже чем в Spirit. Поддерживаются множественные, таргеты, в том числе и LLVM, но никакой документации нет, и код опубликован только частично.

Например?

Coq. Смотреть на CompCert.

Так это же питон, только с некоторыми, м-м, плюшками, не?

Хотя вот это слегка смущает:

возможность определения доп-контекстов аля «а вот тут идёт сишный код»
бесшовная интеграция с C

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

Или интерпретатор, который умеет вызывать С-функции (статически слинковавшись или через dlopen()/dlsym() )?

Так это же питон, только с некоторыми, м-м, плюшками, не?

Ну, грубо говоря, да :). Была идея добавить макросами и пре-процессингом то что мне хотелось, но я посмотрел на существующие решения и мне они очень не понравились.

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

Пока не знаю. Возможно, в этом нет смысла. Я рассматривал это как вариант питоньего ctypes. Только вместо ctypes можно тупо вставить сишный кусок. Наверно это навеяно latex с его окружениями. В общем, надо будет сначала посмотреть как это будет выглядеть.

dlopen()/dlsym()

Вот это будет точно.

В общем, я пока склоняюсь к кодогенерации в C. Этакий самопальный cython. llvm пока слишком круто. Может для начала начну с генерации в питон чтобы получить proof of concept.

А меня тем временем мучает навязчивая идея прикрутить lua-шные штуки к си (на манер обжектив-си со смолтолком).

есть только один способ избавиться от навязчивой идеи :)

Вариантов особо и нет, строить AST, как предлагали раньше и из него генерировать код оказалось слишком сложно

Проверку типов и прочий статический анализ на чём делать? Source-to-source оптимизации? В граф преобразовывать и graph based оптимизации как проводить? В SSA сворачивать чтобы дальше продолжать или LLVM отдавать из чего? Source location к чему привязывать? Ну и это только на тему expressions - а вокруг ещё есть система данных, классов, модулей, пакетов, etc - их анализ без построения представления тоже не очень - IDE что-нибудь полезное отдавать? Тулзы для анализа / генерации кода?

сейчас вроде бы никто так и не делает

Да вроде бы все так и делают.

есть только один способ избавиться от навязчивой идеи :)

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

А так же возможность вводить свои операторы

Есть ещё такое, типа

the_≈ operator_with ⟦_⟧ : Int → Int → String → Int
the n ≈ operator m with ⟦ xs ⟧ = n + m + length xs

test = the 2 ≈ operator 3 with ⟦ "12345" ⟧
-- test => 10

Заставляет писать 1 + 2 вместо 1+2, потому что последнее считается за отдельное имя «1+2» (которое тоже можно определить).

Вот слушайте, зачем вы все это пишете, серьезно? Показать свою крутость? Ну никто же не сомневатется, тут пол-лора промышленно пишут трансляторы не приходя в сознание, по 5 штук только до обеда. Только внезапно выясняется, что в Питоне 15 лет не было AST, в ПХП нет вообще, в Руби вроде бы как есть, только они его стесняются назвать AST.

Я же описываю объективную реальность, мало кто это осиливает для крупных проектов, но все рассказывают Как Должно Быть. То есть я не сомневаюсь что если взять в тиобе топ 20 трансляторов, в некоторых будет встречаться в разных концентрациях то что вы написали, но что с остальными? Почему те же лоровцы не шлют патчи, не проводят разъяснительную работу?

Это риторические вопросы, очевидно же что это сложно и мало кому нужно. То есть для проектов с сотнями человеко-лет какой-то рисерч, оптимизации, вся эта обвязка уже как-то встречается, но для языков которые в состоянии proof of concept и пишутся одним автором это как-то бессмысленно, вам не кажется? Хочется сделать как можно проще и быстрее

То есть я понимаю, что у нас просто разные фокусы, когда я пишу «все» - это реализации языков программирования в штуках, там AST и все эти сложности в следовых количествах, натурально. Когда вы пишете «все» - это оказывается какой-нибудь гцц, кланг, Java, C# или еще что-то, во что вбухано огромное количество ресурсов и тысячи человеко-лет или какая-то маргинальщина, которая не делает ничего полезного но на слуху и напичкана bleeding edge технологиями

Важно верифицировать, что преобразования определены над ровно тем AST, что выдает парсер и что сам парсер корректное дерево создает.

http://docs.racket-lang.org/reference/contracts.html

примитивный
слабые средства для описания преобразований над AST
в качестве target только сам Racket
Довольно тормозной
мало с чем совместимый рантайм

Обоснуй.

Coq. Смотреть на CompCert.

И чем оно лучше Racket?

Обоснуй.

Достаточно уже обосновал.

И чем оно лучше Racket?

Строгой типизацией и верифицируемостью. Вот когда напишут нечно подобное CompCert на Racket, тогда еще раз на него посмотрю. А сейчас этот инструмент не для меня.

http://docs.racket-lang.org/reference/contracts.html

Вообще нерелевантно. Это никак не поможет вывести тип AST из декларативного определения парсера, и проверить, что рекурсивный visitor действительно понимает именно это AST, и при этом не пропускает никаких веток дерева.

Я же описываю объективную реальность

Это ты-то? Ты ж некомпетентен.

мало кто это осиливает для крупных проектов

Даже игрушечные язычки делаются через AST. Потому что это просто и удобно. Смотри на тот же Kaleidoscope.

Только внезапно выясняется, что в Питоне 15 лет не было AST,

Было. Просто не называли так.

в ПХП нет вообще,

ПХП вообще говно, слепленное криворукими недоумками.

в Руби вроде бы как есть, только они его стесняются назвать AST.

Это их личные проблемы. Ничего проще, чем AST, быть не может.

Это риторические вопросы, очевидно же что это сложно и мало кому нужно.

Ты дебил. Это самая простая архитектура, какая может быть.

Я же описываю объективную реальность

В past perfect?

но для языков которые в состоянии proof of concept и пишутся одним автором это как-то бессмысленно, вам не кажется? Хочется сделать как можно проще и быстрее

Ну вот мне и кажется, что с AST проще :) На первой странице была ссылка на компилятор ML на OCaml в 2000 loc - что там сложного?

гцц, кланг, Java, C#

Типа того.

А древний питон написанный на сишке это же совсем другое дело - ТС ничего не мешает взять высокоуровневый язык, библиотеки и сделать правильно и, главное, удобно - разбирать в представление с которым можно работать (а он за public/private/protected хочет следить, например) это же явно проще.

А древний питон написанный на сишке

Кстати, да, сишки всякие не особо подходят для работы с AST. Нужны или языки, где нативные деревья (Лисп и ему подобные) или языки с полноценными ADT.

Прежде чем продолжать нести чушь про «сложность» AST, посмотри на эти тупейшие примеры:

http://llvm.org/docs/tutorial/OCamlLangImpl1.html

http://www.meta-alternative.net/calc.pdf

http://min-caml.sourceforge.net/paper.pdf

Достаточно уже обосновал.

Даже не начал.

Строгой типизацией

У Racket строгая типизация.

верифицируемостью

http://docs.racket-lang.org/reference/contracts.html

У Racket строгая типизация.

НЕТ. У Racket нет поддержки алгебраических типов данных.

http://docs.racket-lang.org/reference/contracts.html

Ты тупой? Контракты ничем не помогут.

спасибо, познавательно

вывести тип [...] из [...] определения

Зачем?

рекурсивный visitor

Что имеется в виду?

Это никак не поможет [...] проверить, что рекурсивный visitor действительно понимает именно это AST, и при этом не пропускает никаких веток дерева.

Создаем контакт: «именно это AST». Декларируем, что «рекурсивный visitor» должен «принимать» объект, который не нарушает этот контракт. Все.

Зачем?

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

Создаем контакт: «именно это AST».

Как? ADT же не поддерживаются.

Декларируем, что «рекурсивный visitor» должен «принимать» объект, который не нарушает этот контракт. Все.

Не все. Я еще не упомянул, что вывести структуру этого visitor-а без определения типа нельзя. А без этого придется писать много ненужного boilerplate кода.

http://llvm.org/docs/tutorial/OCamlLangImpl1.html

ух ты, вот это интересно, спасибо.

Не видел вменяемого гибрида ООП и функциональщины.

LINQ в С# сильно невменяемый? а так Scala, F#

Там еще вариант того же самого на C++ есть (но на OCaml значительно проще):

http://llvm.org/docs/tutorial/LangImpl1.html

ещё глянь: http://www.ffconsultancy.com/ocaml/hlvm/

. Я рассматривал это как вариант питоньего ctypes. Только вместо ctypes можно тупо вставить сишный кусок.

можно же

http://heim.ifi.uio.no/~kent-and/software/Instant/doc/Instant.html

и да, библиотека сама конвертнет входные/выходные параметры из сишных в питоньи. плюс есть поддержка numpy

И еще пример с LLVM:

http://www.meta-alternative.net/templateC-0.0.1.zip

INQ в С# сильно невменяемый? а так Scala, F#

C# и F# это не линукс. Можно заморочится с mono, но не хотелось бы его тянуть. Scala толком не видел, поверю на слово.

Да и интересно just for fun что-либо сделать.

И еще:

http://bloggingmath.wordpress.com/haskell-compiler-series/

можно же

я догадывался что извращенцев на свете много :).

Хочу свой костыль. Потому что глядя на то что генерирует swig мне хочется плакать.

C# и F# это не линукс. Можно заморочится с mono, но не хотелось бы его тянуть.

Зря. Mono отличный runtime, для just for fun намного лучше LLVM. В нем полно батареек, мощный GC, библиотеки на все случаи жизни, простая стековая машина (вместо сложной SSA в LLVM). Я вообще не понимаю, почему на ЛОРе столько негатива в адрес Mono.

кстати, а само MBase на какую версию .NET расчитано?

НЕТ.

Да. ftp://gatekeeper.research.compaq.com/pub/DEC/SRC/research-reports/SRC-045.pdf page 3

У Racket нет поддержки алгебраических типов данных.

Обоснуй.

Ты тупой?

А ты?

Контракты ничем не помогут.

Обоснуй.

Строгой типизацией и верифицируемостью

Только не strong - racket тоже strong, - а static, но в racket тоже есть typed диалект, так что тут нужно задать вопрос про то какой логике изоморфна система типов typed/racket и какими свойствами она обладает (по части моделей других систем и моделей самой системы). С Coq всё (inria.fr) известно, соответственно, всё что пишется на Coq пишется с оглядкой на CoIC + исходный набор аксиом и далее по феншую типы = теоремы/утверждения и программы = доказательства/свидетели в строгом смысле.

Обоснуй.

Покажи пример ADT в Racket.

С mono 2.10 работает, на винде с 4.0 вроде тоже.

Что имеется в виду?

Exhaustiveness - покрытие по ветвям control flow (ADT в частности).

ппц ссылок накидали, чтива хватит на год...

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

Contract Violations напомнят тебе о чем ты забыл.

Как?

Легко. Любой предикат - это контракт. Можно, например, создать контракт «отсортированный список отсортированных списков».

структуру этого visitor-а
вывести структуру этого visitor-а

Что это и зачем?

Делается легко, называется машина Маркова. Состоит из трех циклов, условия и подстановки (обычно три малых цикла).

Что это и зачем?

Допустим, у тебя есть AST Си-подобного языка. И нужно написать pass, который переименует согласно какому-то правилу все идентификаторы в теле каждой функции.

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