RFC: seriál o DSLkách

1.8.2010 19:03 | Přečteno: 1262× | pro temnou strunu | poslední úprava: 1.8.2010 19:04

Zdá se, že jsem se včera trapně prokecl… Nuže, je pravdou, že jsem na konci února tak napůl slíbil napsat pro ábíčko seriálek o DSLkách, čili Domain Specific Languages, čili česky asi nejlíp oborových jazycích (návrhy na lepší překlad?). Vzhledem k tomu, že jde o téma potenciálně velmi rozsáhlé a zpracovatelné mnoha různými způsoby, rozhodl jsem se požádat možné čtenáře o názory. Varování: tenhle zápisek se netýká koček (čtyř- ani dvounohých), filmů, tvrdého alkoholu a dokonce ani krásné literatury. Chcete to risknout?

Dobře, děkuji všem pěti lidem, kteří pokračují ve čtení. Vytvořit si vlastní minijazyk není nic extra komplikovaného, v žádném případě nejde o týdny práce, naopak to týdny práce může ušetřit. Ale – kdo se s tím má zabývat, když na průměrném softwarovém projektu se už nejmíň pět jazyků používá? A tedy: kdo bude takový seriál číst? Podle mne jde o téma dostatečně zajímavé i pro toho, kdo si žádný jazyk nikdy sám nenapíše, takže primární cílovou skupinou jsou normální programátoři, ve kterých ještě nezhasl plamen zvědavosti a zájmu o obor. Absolventi teoretické informatiky se nic nového nedozví, bušiči kódu budou pravděpodobně odrazeni už tématem samotným, ale snad je těch ostatních pořád ještě dost.

Dal jsem tedy (po šesti pivech ) dohromady takovou stručnou osnovu. Je sice plná odporných termitů, ale toho se neděste, to je jen abych já věděl. Kdyžtak v diskusi.

1. Motivace

Jaký je význam programovacího jazyka a proč psát vlastní minijazyky? Jaké to má výhody, na jaké lze narazit nevýhody a co to od programátorů vyžaduje. DSLka interní a externí. Ukázky (zpracování XML v Groovy, odpočinek v Ruby, CSS done right).

2. Úvod do interních oborových jazyků

Jak přiohnout existující jazyk k jinému způsobu vyjadřování? Které jazyky k tomu jsou a nejsou vhodné, co to od hostitelského jazyka vyžaduje a co všechno lze vyjádřit. Data jsou kód a kód jsou data. API versus jazyk.

3. Interní oborové jazyky v Javě, Groovy a Ruby

Vytváření datových stuktur přímo v jazyce. Kód je konfigurace. Deklarativní Java. Buildery v Groovy, bloky v Ruby.

4. Úvod do externích oborových jazyků – význam

Program jako strom, jeho průchod a interpretace. Sémantická analýza. Virtuální stroj, instrukční sada, zásobník. Překlad AST do instrukcí a jejich provádění.

5. Úvod do externích oborových jazyků – podoba

Struktura překladače. Formální jazyky, lexikální a syntaktická analýza. Regulární výrazy a bezkontextové gramatiky. Rekurzivní sestup.

6. Externí oborové jazyky a ANTLR

Generátory parserů. ANTLR a ANTLRWorks. Predikátové gramatiky, stromové gramatiky. Překlad a přepis.

7. Externí oborové jazyky a MPS

Meta Programming System. AST jako zdrojový kód, včetně verzování. Editor a generátor.

Je z toho snad zřejmé, že se nehodlám pouštět moc hluboko do teorie formálních jazyků (i když je to teorie náramně krásná!), ale zůstat u věcí, které jsou ihned použitelné. Nechci mít žádné díly, kde se bude jen budovat nějaký aparát, v každém díle by měl být nejmíň jeden spustitelný program (nějaké příklady mám vymyšlené, ale každý nápad v tomhle směru vítám!). Proto taky řadím sémantiku před syntaxi, pokud byste se divili.

Prozatím uvažuju, že co bod, to jeden článek, ale od externích jazyků se to začíná vcelku komplikovat a i když třeba nemám vůbec v úmyslu mluvit o LR jazycích a bottom-up parsování, horko těžko narvu syntaktickou analýzu do jediného článku. Ale to je v tuhle chvíli implementační detail.

Takže: myslíte si, že to takhle dává smysl? Něco chybí, něco přebývá? Víc teorie? Jít víc do hloubky, za cenu většího rozsahu a případné nezajímavosti pro čtenáře? Nebo raději nejdřív udělat povrchový průzkum a podle případného zájmu se do některých témat pustit hlouběji? Nebo se na to úplně vykašlat? Díky za komentáře a dotazy.

Jóóó! A nečekejte to za měsíc, jsem přece jenom zaměstnanej člověk        

Anketa

Komentáře

[disorder]

a sme si isti, ze 3. je DSL?

[Marek Bernát]

A nie je? Ak tomu dobre rozumiem, tak tam spadajú aj Lispovské makrá. A to určite DSL je.

[Marek Bernát]

Aha možno som to zle pochopil. Ak je ten zoznam jazykov v 3. vyčerpávajúci, tak sorry. Ale v tom prípade žiadam o pridanie Lispu do zoznamu A možno tiež Haskellu, ten je na DSL viac než vhodný. Samozrejme, len ak Ladíček tieto jazyky ovláda, inak by to asi nemalo zmysel

[Ladicek]

Je pár míst, kde určitě plánuju zmínit Lisp, ale příklady v něm psát nebudu. Jeden důvod jsi uvedl , druhý důvod je, že to má být pro normální lidi. Jo a Haskell, no tak to je bezpečně mimo moje znalosti i touhy, takže leda by se toho chopil někdo jiný

[Marek Bernát]

Na mňa sa nepozeraj, ja som na Haskell úplný amatér Ale mám vo feedoch pár moc zaujímavých blogov a tam sa DSL z času na čas objavujú. Čo si teraz spomínam, tak DSL pre 3D grafiku, DSL pre skriptovanie hier a naposledy ma zaujal pojem FRP (functional reactive programming), ktorému síce vôbec nerozumiem, ale videl som to niekde spomenuté pri DSL Takže rozhodne by ma potešilo keby sa tu niečo také vyskytlo. Možno sa toho chytí niektorý ábičkovský haskellista (prádza množina?).

[JS]

Dobra knizka je On Lisp, akorat musite uz Lisp znat, abyste ji mohl cist. Prestoze je uz temer 20 let stara, ukazuje, v cem Lisp umoznuje vytvareni vlastnich DSL a typicke priklady pouziti (treba kompilator dotazu nad databazi). No, mozna by neskodilo do ni alespon nakouknout, kdyz uz pisete o DSL.

[Marek Bernát]

Nemyslím si, že je potrebné ovládať Lisp. Práve naopak, prvé kapitoly sú v podstate úvod do Lispu, tie v prostriedku sa zasa až príliš do hĺbky sa tam preberajú problémy spojené s makrami. Až na konci sú zaujímavejšie príklady. Takže drvivá väčšina kapitol je neprenositeľná na iné jazyky.

Inak, nič proti tej knihe. Čisto ako literatúra o Lispe je skvelá.

[Ladicek]

Myslím, že 3. začíná slovem "interní", takže jo, docela jistí V čem přesně vidíte problém?

Jinak si teď říkám, že tenhle zápisek není moc srozumitelný, určitě ne pro ty, kteří by mohli číst ten seriál. Ale přepisovat už to holt nebudu.

[disorder]

neviem co s tou javou a groovy, ale u ruby je to len velmi flexibilna syntax, nic viac.

[Ladicek]

Ruby a Groovy jsou na tom hodně podobně, ale neřekl bych, že to je jen flexibilní syntax. Prostředky pro metaprogramování, které Ruby i Groovy nabízí, se sice asi nemůžou rovnat lispovským makrům , ale pro konstrukci DSLek jsou jako stvořené.

Java tam je jako jazyk, který sice na první pohled nemůže obsáhnout žádný jiný jazyk, ale s použitím pár fíčur (varargs, statické importy, inicializátory tříd apod.) se dá docela hezky kouzlit.

[disorder]

myslim, ze lepsie to vyjadri tento vtipny blog:

http://www.oreillynet.com/onlamp/blog/2007/05/the_is_it_a_dsl_or_an_api_ten.html

[Ladicek]

No, jo. Myslím, že někde tam mám napsáno "API versus jazyk", ale nedělal bych z toho takovou kovbojku.

[Marek Bernát]

Určite? Pokiaľ viem, tak metaprogramovanie (pomocou metatried, ktoré sú ale spracované úplne iným spôsobom než v Smalltalku) dáva dosť veľké možnosti.

[Marek Bernát]

Trochu ma sklamalo, že sa nebudeš venovať LR. To je momentálne téma, ktorá ma najviac zaujíma. Aspoň spomenúť by si ich mohol. Ale aj tak je tam kopa viac než zaujímavých oblastí, takže jedného verného čitateľa máš istého

[Ladicek]

Tak to se omlouvám, ale já vždycky považoval LR za složitou zbytečnost, a současný vývoj v parsování (LL(*), PEGy a packrat) mne v tom utvrzuje. Jsou teda i lidi, kteří LR považují za intuitivnější než LL, ale tak daleko jsem zatím fakt nedospěl

[Marek Bernát]

Takto: mne sa LL páči podstatne viac než LR. Konceptuálne je to oveľa jednoduchšie (LL človek v podstate vymyslí aj na kolene) a viem o nich už dlho. Ale mal som za to, že za a) vymyslel to Knuth b) LR(1) > LL(1) v zmysle inklúzie gramatík, c) LR je algoritmicky efektívnejšie ako LL, d) pri LL treba riešiť kopu vecí (left-recursion napr.), ktoré pri LR nie sú. Preto som sa v poslednej dobe začal trochu učiť LR. Ale súčasný vývoj v parsovaní nepoznám a ak je to tak ako hovoríš, tak mám radosť a pokojne LR oželiem (ale aj tak si myslím, že by bola škoda aspoň ich nespomenúť).

[Ladicek]

Jak říkám, jsou lidi, kteří preferujou LR, viz třeba tady. Určitě to není špatný nástroj , ale já mu prostě nikdy nepřišel na chuť. Je užitečné (skoro bych řekl nutné) to znát, když se používá LALR generátor, ale jinak si myslím, že se bez toho dá v klidu žít.

[Marek Bernát]

Ok, to mi stačí.

Btw, netušíš náhodou ktorý z nich (LL/LR) produkujú PCT v Parrote? mj41 tu totiž nedávno spomenul zaujímavý tutoriál na implementáciu kompilátora do Parrotovského bytekódu (PASM?). Spravil som si z toho pár kapitoliek a bolo to fakt fajn. A mimochodom som dospel k tomu, že Perl 6 je fakt fajn jazyk. Parrot používa jeho podmnožinu ako na špecifikáciu gramatiky, tak parsing actions nad AST. Jazyky pre Parrot sa píšu fakt jedna báseň, možno ďalší tip, ktorý by si mohol spomenúť v článku? Ale aby som sa vrátil k téme, tak celý čas rozmýšľam nad tým, čo za kompilátor tam vlastne vzniká. Nejak sa mi to nepodarilo dogoogliť, takže možno aspoň tu mi niekto dá odpoveď

[Ladicek]

Nejsem si teď jistý, jak je to s PCT, ale pokud vím, tak "rules" v Perlu 6 jsou PEGy. To je takové vylepšené LL (záleží na pořadí alternativ v pravidlu, neomezený lookahead, backtracking + memoizace), každopádně to vede na rekurzivní sestup.

Teď ještě koukám a wikibooks praví:

Grammars, typically files with a ".pg" file extension, are compiled using the Parrot Grammar Engine (PGE). PGE is an implementation of the Perl 6 rules engine for Parrot. PGE uses a Recursive Descent parser, although certain components such as expressions can be parsed using a bottom-up parser for efficiency.

[Marek Bernát]

Aha, díky

[Ondrej 'SanTiago' Zajicek]

netušíš náhodou ktorý z nich (LL/LR) produkujú PCT v Parrote?

To netusim, ale anekdota rika, ze na parsovani Perlu 7 bude treba pouzit Chart parser nebo Viterbi parser.

[Marek Bernát]

Mno, momentálne mám pocit, že ak bude vývoj podobný ako Perl 5 -> Perl 6, tak z Perlu 7 bude úplne minimalistický jazyk

[Ondrej 'SanTiago' Zajicek]

Je z toho snad zřejmé, že se nehodlám pouštět moc hluboko do teorie formálních jazyků

Osobne si myslim, ze k tomu v podstate teorie formalnich jazyku neni treba (nebo jen naproste zaklady) a ze se celkove parsovani v literature o DSL nebo o prekladacich dost precenuje. LL(1) parser napise schopnejsi programator aniz by potreboval cokoliv vedet o teorii a vic v podstate neni treba :–) . Na DSL (a programovacich jazycich ci prekladacich) je preci mnohem zajimavejsi semantika nez syntax. Tedy v prve rade jak vhodne navrhnout DSL v navaznosti na konkretni problem a v druhe rade jak to rozumne implementovat (kdyz uz mame nejak zparsovany vstup do AST). Tipuju, ze ta prvni vec je ale spis umeni nez ze by na to byla vhodna teorie (coz je asi taky duvod, proc se to bezne pri vyuce odbyva). Mozna by to bylo nejvhodnejsi vylozit formou prikladu takovych jazyku a rozborem jejich silnych a slabych stranek.

[Ladicek]

Spousta jednodušších jazyků sestává jenom z parseru, do kterého jsou doplněné nějaké akce, a na žádný AST ani nedojde. Navíc každé zpracování vstupu je vlastně triviální parser, a neuškodí vědět, jak se to dělá pořádně

[Marek Bernát]

Asi tiež neuškodí spomenúť, že úplne najjednoduchšie veci sa dajú riešiť už regulárnymi výrazmi. Pochopiteľne sa jedná o primitívne šablónovacie jazyky pre HTML

[Ondrej 'SanTiago' Zajicek]

A tez neuskodi zminit, ze samotne regularni vyrazy jsou pekny priklad DSL.

[Ladicek]

Jo jo. A jazyk pro popis gramatiky, který je na vstupu takového generátoru parseru, jakbysmet.

[Ondrej 'SanTiago' Zajicek]

a na žádný AST ani nedojde

Samozrejme, ten AST tam muze byt jen implicitne mysleny.

[Marek Bernát]

+1

Teóriu jazykov som neabsolvoval (viem čo je gramatika a približne aj ako to súvisí s automatmi a regulárnymi výrazmi, ale to je tak všetko), ale malý LL kompilátorček Lispu, som si napísal už dávno

[deda.jabko]

Osobne si myslim, ze k tomu v podstate teorie formalnich jazyku neni treba (nebo jen naproste zaklady) a ze se celkove parsovani v literature o DSL nebo o prekladacich dost precenuje.

souhlasim. osobne mi prijde problematika parsovani, jako asi nejnudnejsi pasaz z oblasti navrhu prog. jazyku.

[Marek Bernát]

A ktoré sú zaujímavejšie oblasti? Typový systém?

[Ladicek]

Typové systémy jsou určitě super, ale moc se tam onanuje s lambda kalkulem, takže já mám radši garbage collectory Ne, vážně, zdálo by se, že parsování je dávno vyřešený problém – a přesto se jím pořád spousta lidí zabývá. Já mám pocit, že jeden díl o tom, jak to udělat ručně, a jeden o tom, jak to udělat automaticky, snad není tolik. A krom toho, že to je první věc, na kterou člověk narazí, je to často taky jediná věc, kterou potřebuje (jak už jsem psal o kousek výš).

[Marek Bernát]

Parsovanie je podľa mňa základ. S tým by si mal asi začať (teda modulo texty, ktoré uvádzajú do problematiky). Kam sa vydáš ďalej, to už je na tebe. Garbage collector je užitočná vec, ale dnes už je jeden v každom virtuálnom stroji (a to zrejme kvalitnejší, než človek vyrobí na kolene), takže mi pripadá trochu zbytočné sa mu venovať. Typové systémy vyzerajú užitočnejšie, ale asi je to fakt trochu hard-core. Ešte by sa dali spomenúť optimalizácie, ale to mi pripadá zasa zbytočné, lebo to "len" zlepšuje už hotovú vec. Takže neviem, nechám sa prekvapiť s čím prídeš

[User682]

zdravim,

nemam ve zvyku pretahovat autory a ani to tady delat nebudu.

Kazdopadne, az dopisete dany serial pro abicko, tak by se u me naslo par praktickych veci, o ktere bych mel zajem a netvrvam na tom, ze musi byt zadarmo. ANTLR jsem vcelku studoval. Horsi je to s casem.

Kazdopadne Vam fandim, at to dotahnete do konce. Gramatiky nejsou jednoduche a zerou hodne casu.

Jak prakticky jste delal s antlr ?

Osobne jsem se zasekl na tom, jak rozebirat dany AST strom v Jave. Je to ale spise otazkou casu.

Vcelku by me zajimaly tyto veci:

- rozeberete ruzne typy gramatik v jednom souboru a poslete je do ruznych streamu.

- stringtemplate

- napisete gramatiku, vyjde Vam z toho AST strom. Chcete potom z tohoto stromu neco filtrovat (jen urcite elementy) a co nejmene psat.

- nahrazovani v AST stromu, prevod jednoho jazyka na druhy. Vcelku by se mi hodilo nejake klikadlo, kde naklikate na kazde strane jednu gramatiku a resite vztahy mezi nimi (mapovani).

- nadefinujete gramatiku. Presneji nadefinujete pouze typy elementu a jejich relace mezi nimi. Ale dany typ elementu musite overit pres nejakou databasi "treba" slov. To, co znate jsou ty relace mezi danymi typy elementu. Zda to je a jak ?

Takze to tak na namet a ze to ma smysl. Spise by se dalo pokecat po mailu.

gf

[Ladicek]

rozeberete ruzne typy gramatik v jednom souboru a poslete je do ruznych streamu.

Je to trochu porno, ale dá se vyjít třeba odtud: http://www.antlr.org/wiki/display/ANTLR3/Island+Grammars+Under+Parser+Control. Nikdy jsem to nedělal, ale musí to jít. Řeší to v každém lepším IDE (kombinace PHP+HTML+CSS+JavaScript+regexpy v jednom souboru musí být peklo).

stringtemplate

Hodně minimalistickej šablonovací jazyk, ale líbí se mi, že docela dobře zvládá bílé znaky. Ale není to nic než šablonovací jazyk, stejně dobře může posloužit třeba FreeMarker.

napisete gramatiku, vyjde Vam z toho AST strom. Chcete potom z tohoto stromu neco filtrovat (jen urcite elementy) a co nejmene psat.

Stromové gramatiky v ANTLR jsou docela mocné, od ANTLR 3.2 se dají přepisovat i stromy na stromy. Stačí popsat jen tu část stromu, která je zajímavá. Zase, nedělal jsem to, ale musí to jít.

nahrazovani v AST stromu, prevod jednoho jazyka na druhy. Vcelku by se mi hodilo nejake klikadlo, kde naklikate na kazde strane jednu gramatiku a resite vztahy mezi nimi (mapovani).

To musí být obecně docela šílený problém (ne-li nerozhodnutelný). Ale mám pocit, že grafické návrháře existují třeba pro XSLT ) Nicméně, to už je mimo můj záběr, nikdy jsem nad tím nepřemýšlel a tohle nestudoval.

nadefinujete gramatiku. Presneji nadefinujete pouze typy elementu a jejich relace mezi nimi. Ale dany typ elementu musite overit pres nejakou databasi "treba" slov. To, co znate jsou ty relace mezi danymi typy elementu. Zda to je a jak ?

A to už jsem ani nepochopil

[disorder]

emacs riesi kombinaciu PHP+HTML+CSS+JavaScript vratane heredoc cez nxhtml mode (mumamo - multiple major modes)

[deda.jabko]

sice si myslim, ze DSL jazyky se trochu (zbytecne) precenuji... ale urcite si to rad prectu.

[disorder]

regularne vyrazy su trochu precenovane? :)

[Ladicek]

Já vím, jak to myslí. Je pravda, že tahle zkratka je docela magická a spousta lidí si myslí, že v ní našla pověstnou stříbrnou kulku, na druhou stranu na automatizaci rutinních činností není nic špatného a DSLka jsou v automatizaci rutinních činností skvělá. No a když se povede, že skutečně vykonávanému programu rozumí i zákazník, tak to musí být nirvána Já se teda tak daleko ještě nedostal.

[disorder]

classic case of buzzword :)