название кодогенератора

по теме: про кодогенераторы.

зачем нужен MetaOcaml довольно наглядно расказывается в «A Gentle Introduction to Multi-stage Programming» by Walid Taha. там это MSP многостадийное приводится как пример именно program generation на MetaOcaml, с примерами реализации простого недоязычка в качестве DSL типа паскалеподобного где есть Program, Declaration переменных, базовые операции вызов функции, +-*/ и Ifz(expr==0,then,else). правда, этот недоязычок скорее функциональный (то есть переменные могут быть функциями как first class object). кстати, вот вам и различия между Lisp-1 и Lisp-2 – единое namespace, first class environment для символов функций и символов переменных или разное.

учитывая сиё объяснение «чем Multi-Stage Programming» лучше например макросов лиспа" для кодогенерации в плане Program generation – мне именно эта статья хорошо объяснила.

если коротко. вот есть например бестиповое лямбда исчисление в лиспах.

макросы состоят из quote, unquote, splice. и можно как бы заморозить вычисления в макросе через quote, и частично разморозить и вычислить только то что нужно, именно в том порядке, в каком нужно через ,` и @.

c другой стороны, с типизацией не всё хорошо. если макрос использовать для кодогенерации, хотелось бы иметь зарание какие-то гарантии типа гигиены – но только для того что макрос развернётся не только в синтаксически корректное но и в семантически корректное и в well-typed.

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

что предлагают взамен в Multi-Stage Programming, MSP.

вводятся операции Bracket вместо quote, Escape вместо unquote+Splice и ещё операция Run.

если макросы лиспа на выхлопе берут AST бестипового лямбда-исчисления и преобразуют его в другой AST бестипового, частично и в нужном порядке через unquote + splice что-то вычисляя, то в MSP AST типизированный. то есть, поскольку используется MetaOcaml поверх базового Ocaml то на зависимых типах типизированном лямбда-исчислении легко выражается типизированный AST:

REPL> let a = 1+2;;
val a : int = 3
REPL> let b = .<1+2>.;;
val b : int code = .<1+2>.

вместо лиспового

(setf a (+ 1 2) )    ;; eager eval +expr
(setf b (list '+ 1 2) )  ;; lazy delayed eval +expr
(setf c (eval b) )   

то есть int code тип b в окамле гарантирует well-typed, а в лисповой форме имеем в общем случае динамику и/или что-то гарантировать можем каким-то code walker-ом.

поскольку типизированное лямбда-исчисление, то int code разных можно ограничить так, чтобы разворачивалось в семантически и синтаксически корректное.

то есть далее в примере если

REPL> let b = .<.~a  * .~a >. ;;
val b : int code = .<(1 + 2) * (1 + 2)>.

то получаем конструирование AST типизированного гарантированно синтаксически корректного и well-typed подвыражения вместо лисповых бестиповых макр (где простой подстановка S-expr чуть лучше чем просто строки, тоже моноиды гомогенных типов: строки, S-выражения).

получается что вот это b типа code of int здесь – моноид гетерогенных типов, типизированная лямбда функция.

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

вот так строится окружение как first-class environment :

exception Yikes
let env0 = fun x -> raise Yikes let fenv0 = env0
let ext env x v = fun y -> if x=y then v else env y

let rec eval1 e env fenv =
match e with
Int i -> i
| Var s -> env s
| App (s,e2) -> (fenv s)(eval1 e2 env fenv)
| Add (e1,e2) -> (eval1 e1 env fenv)+(eval1 e2 env fenv)
| Sub (e1,e2) -> (eval1 e1 env fenv)-(eval1 e2 env fenv)
| Mul (e1,e2) -> (eval1 e1 env fenv)*(eval1 e2 env fenv)
| Div (e1,e2) -> (eval1 e1 env fenv)/(eval1 e2 env fenv)
| Ifz (e1,e2,e3) -> if (eval1 e1 env fenv)=0
then (eval1 e2 env fenv)
else (eval1 e3 env fenv)

let rec peval1 p env fenv=
match p with
Program ([],e) -> eval1 e env fenv
|Program (Declaration (s1,s2,e1)::tl,e) ->
let rec f x = eval1 e1 (ext env s2 x) (ext fenv s1 f)
in peval1 (Program(tl,e)) env (ext fenv s1 f)

если рассматривается для исходного DSL языка типа

type exp = Int of int | Var of string | App of string * exp
| Add of exp * exp | Sub of exp * exp
| Mul of exp * exp | Div of exp * exp
| Ifz of exp * exp * exp
type def = Declaration of string * string * exp
type prog = Program of def list * exp

AST типизированный вида

Program ([Declaration
("fact","x", Ifz(Var "x",
Int 1,
Mul(Var"x",
(App ("fact", Sub(Var "x",Int 1))))))
],
App ("fact", Int 10))

Ifz ЕМНИП, уже достаточно, чтобы реализовать какой-то 0ISC, упрощённый RISC.

в общем, занятные аналогии.

мне тут вот что подумалось: вот есть реализация оберона odc на основе Ocaml : Oxford_Oberon-2_compiler.

там на окамле емакс реализовали, ну и оберон ЕМНИП в байткод окамловый транслируется, с его динамической подгрузкой.

любопытно, если на этом Multi-Staged Programming написать реализацию оберона как многостадийные метаинтерпретаторы/метакомпиляторы синтаксически, семантически и well-typed скодогенерированных программ как такого вот типизированного AST вместо бестипового – наверное, такая реализация оберона будет ещё проще, нагляднее и понятнее.

плюс там в самом начале пример что что-то автоматически сможет соптимизировать.

на любопытные мысли наталкивает, в общем. сравнение какого-то лиспа с окамлем с оберонами. плюс к этому окамлю затем тот же LLVM прикрутить можно.

а какой у тебя опыт с окамлем, как ощущения?

Ну вот как от этой мешанины разнотипных скобок не плеваться?

а круче всего, ЕМНИП, было реализовано в InterLisp. там [ синоним для (, но ] синоним для )....)=)*, то есть – закрывает ВСЕ предыдущие закрытые скобки, и для top-level форм можно было поставить в конце только один ] чтобы всю эту кучу скобок закрыть автоматически.

плюс они там написали структурный редактор S-выражений.

внезапно, ещё один наткнулся на InterLisp : топик на лоре

и опять огораживаете от анонимусов, редиски эдакие.

Опыт с окамлем совсем небольшой, не могу делать каких-то суждений. Нужно было просто кое-что в существующей программке подправить. В целом спасибо, на примеры погляжу. А, не это про игры примеры, а мне про веб надо. Насчёт типизированных макросах - внутри SBCL скрыто ещё 2 или 3 вида макросов, которые работают на разных этапах, что-то типа def-ir1-transform. Они расширяются на соответствующих этапах работы компилятора. Там всё это хрупко, но на каком-то этапе и типы могут подключаться. Причём делаются некоторые приятные вещи, которые без них, рамками просто CL, не делаются. Про multi-stage пока нет ресурсов осиливать, прошу прощения.

кабачковый генератор. Мощно. Солидно.

Видите ли, Делириум… Хотя, Делириум звучит как то пафосно, я буду звать вас Диля. Так вот, Дилечка, причем здесь кабачки, скажите? Это сугубо технический ресурс.

Владимир 123

Кабачки, тов. Володин, тут притом, что они большие ;-)

Если у вас кабачок достаточно большой, как на моей грядке, мы может заскочить в гости к Binkledum и поболтать на нетехнические темы о линуксе. Примерно до понедельника ;) Ему будет приятно провести время со своими лучшими друзьями.

Владимир 123

Витька, а вы пишете на Go?

Владимир 123

Ген переводишь на русский – получается род. Питон – Каа. Си плюс плюс – эсхаха. Получается каасхахарод.

Нет

Да, Витюн, это вам не баклажаны садить …

Владимир 123