Kommentarer til Scheme-kompilator: (En gang i fremtiden) r7rs -> llvm

[x871kx6167ss7]

Dersom dere lurer på noe, eller har noe annet på hjertet, så er det bare å si i fra.

 

Link til arbeidslogg

[GeirGrusom]

Ser ut som et morsomt prosjekt. Men hva bruker du egentlig for å parse? Jeg innehar ikke noen stor forståelse av scheme, men jobber med noe lignende (dog i C#).

[x871kx6167ss7]

Det er i hvertfall to ting ved det spørsmålet som er interessant. Den ene tingen er den "praktiske" delen: det å gjøre om en strøm av tegn til et abstrakt syntakstree. Den andre tingen handler om makroer.

 

Strøm av tegn til abstrakt syntakstree:

 

Glem for et øyeblikk at vi snakker om parsing.

 

Dersom vi ser litt forenklet på det, så har scheme følgende type dataobjekter:

• Pair - Inneholder to dataobjekter. Skrives tekstlig som "(" objekt-1 "." objekt-2 ")".
• Empty-list - Tenk null-peker. Skrives "()"
• Symbol - Tenk blanding av enum og string. Ingen klar parallell i C#/Java/C som jeg kan komme på. Ser tekstlig ut som variabler i C.
• Strenger og tall - Som vanlig.

Det viktige å legge merke til her er at et dataobjekt her har en tekstlig representasjon. F.eks. så kan et par av tallene en og to representeres som "(1 . 2)". Og et par av symbolet "foo" , og paret av tallet tre og empty-list, representeres som "(foo . (3 . ()))". En siste ting å nevne om den eksterne representasjonen: "(x . (y . z))" kan forkortes til "(x y . z)", og "(x . ())" til "(x)". Så det siste eksempelet kan også skrives som "(foo 3)". Denne tekstlige representasjonen kalles s-expressions.

 

Innebygd i scheme så finnes det en funksjon som heter "read", og den leser en strøm med tegn (antatt s-expressions), også returnerer det dataobjektet som tegnene representerer.

 

Scheme- og lisp-programmer skrives som s-expressions, noe som betyr at jeg kan lese programmet ved å kalle på read (og det er det jeg gjør nå). Etter å ha lest hele programmet, så sjekker jeg at alle variabler er bundet og at alle "special forms" er riktige osv. Dette gjør jeg da ad-hoc i scheme.

 

Et eksempel på et scheme-program (eller data, dersom du har et annet perspektiv) er:

(let ((x 2))
 (+ x 1))

 

Jeg vet du har kjennskap til lambda-uttrykk i C#. Sånn her ser de ut i scheme:

(lambda (x)
  (+ x 3))

 

Og her et funksjonskall:

(+ 1 2 3)

 

Dersom du ser på det siste eksempelet, så kan du si at "det er et program som plusser sammen 1, 2 og 3". Eller så kan du si at det er en liste av fire ting, symbolet +, og tallene 1, 2 og 3. Begge svarene er like riktig, og avhenger bare om det er en kompilator/tolker eller read som ser det.

 

Det er selvfølgelig en ulempe med å bruke read: linjenummer forsvinner. Det kan nok løses på flere måter. Jeg må være ærlig å si at jeg ikke har lest/sjekket hva som er den vanlige måten å løse dette på.

 

Makroer i forhold til parsing:

 

Nå tenker du kanskje "hvorfor bruker du ikke f.eks. yacc for å lage det abstrakte syntakstreet? Da slipper man denne adhoc sjekkingen av koden.". Så vidt meg bekjent så er det ikke mulig å løse dette på en elegant måte med de verktøyene. Grunnen er markoene i scheme. For å parse scheme så må du ekspandere makroer, og for å ekspandere makroer så må man parse.

 

Dersom parseren kommer til et makro-"kall", så kan den ikke parse argumentene. Den må utvide makroen, og så kan den parse det nye uttrykket.

 

Og når en makro skal utvides, så må man ha kunnskap om strukturen til scheme-kode, på grunn av hygiene.

 

Tror det er lettest å forklare hygiene ved å vise til C sitt makro-system (som ikke er hygenisk). Eksempel:

#define swap-int-vars(x, y) do { int tmp = x; x = y; y = tmp; } while (0)

swap-int-vars(a, b) // ok
swap-int-vars(a, tmp)) // feil.

Her innfører makroen en variabel som skygger over en binding som den ikke "burde" skygge for.

 

Det motsatte er også mulig, at argumentet til makroen skygger over en variabel som makroen bruker. Begge disse problemene løses automatisk ved hygiene.

 

Jeg har enda ikke implementert makroer. Det krever noe arbeid siden scheme-makroer er skrevet i et høynivås pattern/template språk.

[xaco]

Spennende prosjekt. Lykke til. Scheme er kanskje ikke favoritt språket mitt, men noen ganger kan det bli ganske vakker kode... Liker litt syntaxen til funksjonelle programmeringsspråk.