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

[x871kx6167ss7]

Da er sommerens programmeringsprosjekt i gang, og i år er det en scheme-kompilator som skal lages. Planen er at kompilatoren skal kompilere r7rs-scheme til llvm-platformen.

 

Har holdt på noen dager nå. Veldig kort oppsummert så er status:

• Datatyper: funksjoner, fixnums, tegn, strenger og par
• IO fra stdin/stdout
• Parseren gjenkjenner og evnt. omformer (tar dog ikke hensyn til skop): define, set, lambda, quote, and, or, cond, let, let* og begin.
• Generelt dårlig kode (~2700 linjer inkl. kommentarer osv)
• Ingen optimaliseringer
• Treg kompilering
• Ingen GC
• CPS-konvertering + beta-redusering av administrative redexer.

Planen er som nevnt å skrive en frontend for LLVM. For øyeblikket så genererer kompilatoren LLVM-assembly, men det vil etter hvert være naturlig å bruke FFI for å koble seg direkte til LLVM-bibliotekene. En av fordelene med å koble seg direkte inn på LLVM er at kompileringen blir mer dynamisk. Jeg har ikke tenkt til å støtte eval eller runtime-load med det første.

 

Unnskyldningen for at koden er stygg er at implementasjonen jeg bruker for å bootstrape kompilatoren er begrenset, og støtter så vidt meg bekjent ikke r7rs-lignende moduler. Målet mitt er derfor å utvide kompilatoren slik at den kan kompilere selv selv. Når det er gjort, så skal jeg implementere moduler, og så blir det oppryddning.

 

Det som mangler før kompilatoren (i sin nåværende tilstand) skal kunne kompilere seg er: call-with-values, open-input-port, close-input-port (og read må modifiseres) og command-line.

 

Roadmap for øyeblikket er ca:

1. Kompilerer seg selv (det nevnt ovenfor)
2. (Subset) av r7rs moduler
3. Liten opprydding
4. Enkel GC
5. define-syntax/syntax-rules

 

Kode: https://github.com/peterbb/compiler

Tråd for kommentarer: Link til kommentartråd

Endret 27. juni 2011 av peterbb

[x871kx6167ss7]

Dagens arbeid har gått med på å lete etter en bug i koden som kompilatoren produserer. Jeg har jo testet kompilatoren min med diverse småprogrammer som tilsynelatende har fungert helt fint. Men jeg bestemte meg for å legge til "implementasjoner" av de funksjonene som manglet for at kompilatoren skulle kunne kompilere selv. "Implementasjonene" ser sånn ut:

(define (foo . args) (error "foo not implemented"))

 

Med det på plass, så var planen at kompilatoren skulle kompilere seg selv, og jeg håpte at den ville stoppe opp forholdsvis tidlig når en av de "uimplementerte" funksjonene ble kalt. Det skjedde dog ikke... Jeg fikk «segment fault», noe som jeg ikke forventer at skal skje når man kjører et scheme-program.

 

Måten jeg implementerer de innebygde funksjonene på er at jeg skriver de helt basale funksjonene (som cons, car, set-car!, string-ref, make-string, + osv) i llvm-assembly. Men de gjør ingen typesjekking. Så f.eks. "%car" vil prøve å ta car av et par, men den sjekker ikke om det faktisk er et par, og følgelig vil uttrykket "(%car 0)" lese null-pekeren og kræsje programmet. Så kompilatoren vil lese inn en fil ("prelude.scm") før den kompilerer den faktiske koden. Den filen inneholder f.eks. definisjoner for map, og også wrapper-funksjoner sånn som:

(define (car x)
 (%assert-pair "car" x)
 (%car x))

Hvor "%assert-pair" også er implementert i prelude.scm, og sjekker at x faktisk er et par, hvis ikke skriver den ut en feilmelding. Jeg tenkte da at det var en av disse stub-funksjonene som det var noe feil med. Etter en del feilsøking uten nytte, så bestemte jeg meg for å legge til typesjekking i de innebygde funksjonene som er skrevet i llvm (det vil uansett være nyttig for å oppdage feil tidlig, siden de blir brukt i koden som kompilatoren genererer), men det hjalp ikke, så da måtte jeg lete andre steder.

 

En ting jeg tenkte kunne være kilden til problemet var at malloc ikke gav meg 8-byte-aligned addresser, dog det var heller ikke problemet. Addressene må være 8-byte-aligned siden jeg lagrer typeinformasjon i de tre laveste bitene av et maskinord. Kan si mer om det en annen gang.

 

Etter å ha lastet inn core-filen i gdb, så sa stack tracet at segment faulten oppsto inne i malloc. Jeg følte meg ganske sikker på at alle funksjonen som modifiserte minne var riktige, så syntes det var litt rart.

 

Det første cluet får jeg når jeg kjører koden med lli (JIT for llvm-bytekode). lli kræsjet også med en segfault, men når jeg så på stack tracen til core-filen, så var stacken sprengt. Siden jeg kompilerer koden til CPS (continuation-passing form) så burde ikke stacken brukes i det hele tatt (evnt. bare for å lagre midlertidlige variabler og kall på primitiver). Det medfører at koden som kompilatoren gir fra seg så sånn her ut:

define private protected cc 10 void @lambda-XXX(i64 %env, i64%arity) noreturn {
  ... enkel kode (uten kall på funksjoner med untak av "primitive"
  ... f.eks.: %tmp = call i64 @get-car(%t_obj %env)
  ... osv
  tail call cc 10 void @apply(i64 %proc, i64 %arg-count, i64 %arg-list) noreturn
  unreachable
}

 

Poenget med tail call optimalisering (TCO) er at kallet på apply helt til slutt kan gjenbruke stack framen til funksjonen som holder på å kjøre. Siden alle funksjonene er på den formen, så trengs det bare en stack frame.

 

Det er to problemer med den koden (som nå er fikset):

 

1) llvm forstår ikke at den kan utføre TCO siden det står "unreachable" i stede for "ret void". Selv synes jeg at den burde forstå det. Men det gjorde den altså ikke.

 

2) De primitive funksjonene (sånn som get-car) bruker "standard c calling convetion (ccc). Det kan se ut til at det er problematisk å blande sammen ccc med "cc 10" (som er en kall-konvensjon i utgangspunktet lagt til for Haskell, og den har mulighet for TCO). Uten at jeg vet det for sikkert, så kan det virke som om innholdet i registrene ikke ble lagret når jeg kalte på primitive (med ccc). Jeg endret til "fastcc" som er en annen kall-konvensjon som støtter TCO, og det fungerer nå.

 

Når jeg kjører den kompilerte kompilatoren (altså kjører kompilatoren min, som er kompilert av min kompilator kjørende på host-implementajsonen), så vil den stoppe opp før den rekker å gjøre så veldig mye fornuftig med meldingen "a.out in malloc(): error: out of memory" (kjører filen med MALLOC_OPTIONS=X, som gjør at det skjer i stede for at null returneres).

 

Det kan se ut til at gc må flyttes lengere opp på roadmapet.

 

edit: Teksten har kanskje ikke den beste settningsoppbyggningen nå "midt på natten". Takk for kommentar, Torbjørn (dog den burde vært i kommentartråden ).

Endret 29. juni 2011 av peterbb

[torbjørn marø]

Høres ut som om du koser deg. Stå på!