Julekalenderen for i år avsluttes med et programmeringsspråk spesialdesignet for å løse Euler 1 oppgaven. Det har ikke noe navn, men er en såkalt DSL, et domenespesifikt språk. Og det er hjemmesnekret av undertegnede i ett av språkene jeg har brukt tidligere i kalenderen – nemlig Rebol.

For å finne og skrive ut summen av alle multipler av 3 eller 5 under 1000 kan jeg med dette språket skrive følgende:

100 alert to-string
101   summing [
102     Add multiples of 3 below 1000
103     Add multiples of 5 below 1000
104     ; Since numbers that are both multiples of 3 and 5
105     ; will have been added twice, we now have to subtract 
106     ; those numbers once..    
107     Subtract multiples of (3 * 5) below 1000
108   ]

Som du ser er språket nokså deklerativt; jeg deklarerer hva jeg trenger i summen min, ikke hvordan man finner tallene. Og det er en DSL blant annet fordi de semantiske reglene er anderledes i deklarasjonen enn i Rebol forøvrig.

Rebol ble ikke valgt tilfeldig for å lage dette språket. Rebol har nemlig veldig gode muligheter for parsing av både tekst og symboler, og er tilrettelagt for å lage “dialekter” (som de kaller det) internt i språket.

Parse

Den sentrale funksjonen i implementasjonen av DSL’en heter parse. Den tar som input en streng eller en blokk med kode som skal parses, og en blokk med reglene som gjelder for parsingen – selve definisjonen for språket. Regex blir blant annet helt overflødig i Rebol, fordi denne parse-funksjonen er så kraftig.

Ser du på den andre linjen i koden over så står det “summing”. Det er selve DSL-funksjonen jeg har laget, som utfører parsingen og returnerer en sum. Her er implementasjonen:

 40     {
 41       The SUMMING word is set in the global context as a 
 42       function that takes a block of instructions as an
 43       argument and returns the resulting sum.
 44     }
 45     set 'summing func [instructions] [
 46       result: 0
 47       parse compose instructions [any summing-rules]
 48       return result
 49     ]

Reglene

Regelsettet som sendes inn til parse er gjengitt nedenfor. Siden språket jeg har laget er ganske enkelt er reglene også enkle. Reglene er faktisk også skrevet i en DSL/dialekt av Rebol, som en context-free grammer ala Backus-Naur Form (BNF) – en standard måte å beskrive syntaks for parsere.

 51     {
 52       The parsing rules. These are the MAIN PART you have to
 53       grok in order to use parsing and dialects in Rebol.
 54     }
 55     summing-rules: [
 56       set operation [ 'Add | 'Subtract ]
 57       'multiples
 58       'of
 59       set multiplier integer!
 60       'below
 61       set below integer!
 62       (do-instruction) ; called when instruction has been parsed
 63     ]

Her beskriver jeg altså hvordan en instruksjon i språket mitt skal se ut. Først forventer jeg ett av symbolene Add og Subtract. Symbolet lagres i variabelen operation. Deretter forventer jeg symbolene multiples og of. Så følger en integer som jeg lagrer i multiplier, etterfulgt av symbolet below, og til slutt en ny integer som lagres i variabelen below.

Når en instruksjon har blitt matchet kjører jeg prosedyren do-instruction, som vil utføre den.

Utføre beregningene

Når do-instruction blir kalt er altså variablene operation, multiplier og below satt til verdiene som er parset. Jeg kan nå generere tallene og oppdatere result-variabelen som ble opprettet tidligere.

Jeg kjører først en for-løkke for å finne multiplene, som jeg legger inn i en liste jeg kaller temp. Deretter bruker jeg fold til å summere dem sammen. Til slutt legger jeg summen til eller trekker den fra result, avhengig av verdien av operation.

 65     {
 66       Uses the result of parsing an instruction to create
 67       the multiples and modify the result
 68     }
 69     do-instruction: has [temp] [
 70       temp: copy [] ; block to contain the multiples
 71       for x multiplier below - 1 multiplier [
 72         append temp x
 73       ]
 74       ; Sum all the multiples into temp..
 75       temp: fold func[acc x][ acc + x ] temp
 76       ; Finally, either add or subtract to/from result 
 77       result: either operation = 'Add [
 78         result + temp
 79       ] [
 80         result - temp
 81       ]
 82     ]

Og det var hele implementasjonen. Eller i alle fall alt som er viktig! Det som mangler er at jeg egentlig har wrappet DSL’en inn i et objekt, og så har jeg implementert fold selv, siden Rebol ikke har den funksjonen. Den komplette koden kan du se her.

Om jeg nå ønsket at DSL-instruksjonene skulle leve i sin egen fil, og brukt DSL-implementasjonen til å kjøre DSL-filen – som om DSL’en var et selvstendig språk – så hadde ikke de krevd mer enn et par linjer kode til.

Oppsummering

Jeg har forsøkt å vise hvor enkelt det kan være å implementere en intern DSL i et språk som legger tilrette for det. Rebol er kanskje det mest egnede språket jeg har vært borti, men Lisp-dialektene er heller ikke langt unna. I språk som har mere syntaks blir DSL’ene ofte ikke så elegante, fordi man ikke kan bryte syntaks-reglene i språket.

Og grunnen til at jeg velger å avslutte julekalenderen med en DSL er at jeg ønsker å påpeke at språk er noe man faktisk kan lage selv. Det eksisterer mange programmeringsspråk allerede – jeg har bare presentert 23 av dem – men av og til kan det være best å designe et helt nytt et for en spesifikk oppgave.

Jeg håper du satte pris på julekalenderen min i år, og takker nå for følget. Men jeg håper selvsagt du vil fortsette å ta turen innom bloggen min i det nye året. Om ikke lenge vil jeg poste en større oppsummering over hva jeg har snakket om i desember, hva jeg har lært underveis, og hva jeg vil ta med meg videre.

God Jul alle sammen!

Kategorier: DSL, Julekalender.
RSS feed for kommentarene. Tilbaketråkk.