Talen en automaten/2011-12/producten/Clojure

Clojure

Jan Groothuijse

Talen en automaten 2011-12

13:50 B

Jan Groothuijse  e-mail  cursuspagina

Bestand:Jan Groothuijse.jpg

Beschrijving

Clojure is een Lisp dialect dat op een JVM uitgevoerd kan worden. Clojure legt de nadruk op functioneel programmeren. Clojure heeft een redelijk simpele syntax, zo is zelfs de constructie om een functie in de global scope te maken eigenlijk een global functie die een naam en anonieme functie als argumenten heeft. De declaratie van deze anonieme functie is gelukkig wel een echte taal constructie.

Regulier?

Clojure is niet regulier, dat gaan we bewijzen door middel van het Pomp lemma. Omdat we bewijzen dat het pomp lemma niet voor de gehele taal geld, hoeven we slechts een plaats aan te wijzen waar het niet geld, en kunnen we volstaan door een deel van de grammatica te nemen.

Ik neem hiervoor een if statement: "(if condition then-expr else-expr)", in Clojure is het else-expr statement optioneel, dus om een heel compact voorbeeld te krijgen haal ik het even weg: L = (if condition then-expr). De then-expr mag echter ook weer if statements bevatten, dus de volgen code zou (triviaal maar) correct zijn: (if (true) (if (true) 1)) In de then-expr van de nested if, zouden nog meer if statements genest kunnen worden. Van belang is dat het statement begint met 'if(' en eindigt met ')'. Laat k het aantal states zijn van de DFA om voor de taal L. Laat z een string zijn die in L zit, waarvan de lengte groter is dan k. z moet afbreekbaar zijn in de componenten uvw, waarbij v herhaalbaar moet zijn. Als we echter naar de expressie kijken, dan zien we dat er geen v te vinden is die herhaalbaar is, omdat een nieuwe v midden in de oude v geplaatst moet worden en niet achterelkaar geconcateneerd mag worden. Dit betekent dat de condities van het pomp lemma voor regulieren talen niet gehaald worden door deze taal en dat betekent dat deze taal niet regulier is.

Contextvrij?

Om aan te tonen dat de taal een context vrije taal is, wil ik er een context-vrije grammatica voor maken. Het probleem is dat deze taal redelijk wat bagage blijkt te hebben. De syntax is voor een groot deel geleend van LISP, een taal die al bestaat sinds de jaren 50. Maar om op de JVM te werken en gebruik te kunnen maken van java's bibliotheken moesten er wat dingen aan toegevoegd worden. Voor dit werkstuk heb ik besloten een klein deel van de taal vast te leggen in een leesbare grammatica; in de hoop dat dan zichtbaar word dat de grammatica kan worden uitgebreid zonder context-vrijheid te verliezen, voor de diverse apparte syntax die ik nu weglaat. De weggelaten syntax houdt zich bezig met macro's en interoperabiliteit met java objecten, escapen van strings, octale en hexadecimale declaratie van getallen, floating points maps, locking, interning en het toevoegen van metadata.

 Stm  -> (Exp) | ;COMMENT
 Exp  -> Call | Form | Lit | Exp Exp
 Lit  -> BOOL | INT | STR | nill
 Call -> NAME Args | NAME
 Args -> VAL | VAL Args

 Form -> Def | If | Do | Let | Quote | Var | Fn | Loop | Recur | Throw | Try | Mo_en
 Def  -> def NAME Exp | def NAME [Prms]
 If   -> if Exp Exp | if Exp Exp Exp
 Do   -> do Exp
 Let  -> let Vec Exp
 Var  -> var NAME
 Fn   -> fn NAME Exp | fn NAME Prms Exp
 Loop -> loop Vec Exp
 Recur-> recur Exp
 Throw-> throw Exp
 Try  -> try Exp Exp Exp | try Exp Exp
 Prms -> NAME | NAME Prms
 Vec  -> [Vec2]
 Vec2 -> EXP | EXP Vec2

 NAME -> a-Z(a-Z0-9*)
 BOOL -> true | false
 INT  -> 0-9*
 STR  -> "(.*)"

Versimpeld voorbeeld grammatica voor Clojure

Links

[1] [2] [3] [4]