Jezička laboratorija u Raketu (3. deo)

Autor: Luka Hadži-Đokić

Da se podsetimo: u prethodnom delu ovog serijala, pozabavili smo se leksičkom i sintaksnom analizom. Veći deo posla pod haubom uradio je brag paket, u obliku lexer-srcloc funkcije koju smo koristili u izradi leksera i u obliku #lang brag jezika za izražavanje gramatike i automatsko generisanje abstraktnog sintaksnog stabla na osnovu nje.

Ono što sada imamo jesu tri datoteke ili modula našeg prevodioca. U fascikli libre-lang nalaze se lexer.rkt, tokenizer.rkt i parser.rkt. U njima smo definisali određene funkcije, ali, iako smo prošli kroz nekoliko primera, te funkcije još uvek nismo pokrenuli i isprobali. Vreme je da napravimo testove.

U direktorijumu tests, možemo napraviti datoteku lexer-test.rkt i početi sa radom.

[code]#lang racket
(require libre-lang/lexer brag/support rackunit)

(define (lex str)
 (apply-lexer libre-lexer str))[/code]

Opet programiramo u raketu, pa to naznačavamo sa #lang racket i uvozimo nekoliko potrebnih paketa. Lekser koji smo već napravili, brag/support, koji nam je poznat, i rackunit – paket za jedinično testiranje (eng. unit testing).

Onda definišemo pomoćnu funkciju lex koja primenjuje naš lekser na nisku koju joj prosledimo.

Ostatak programa je pravolinijski.

[code](check-equal? (lex "") empty)

(check-equal?
 (lex "// komentar\n")
 (list (srcloc-token (token ‘COM "// komentar")
      (srcloc ‘string 1 0 1 10))
  (srcloc-token (token "\n" #:skip? #t)
      (srcloc ‘string 1 10 11 1))))

(check-equal?
 (lex "print")
 (list (srcloc-token (token "print" "print")
      (srcloc ‘string 1 0 1 5))))

(check-equal?
 (lex "42")
 (list (srcloc-token (token ‘INTEGER 42)
      (srcloc ‘string 1 0 1 2))))

(check-equal?
 (lex "\"Zdravo svete!\"")
 (list (srcloc-token (token ‘STRING "Zdravo svete!")
      (srcloc ‘string 1 0 1 15))))

(check-equal?
 (lex "identifikator")
 (list (srcloc-token (token ‘ID ‘identifikator)
      (srcloc ‘string 1 0 1 10))))[/code]

Sastoji se iz nekoliko provera funkcijom check-equal?, kojima upoređujemo rezultat funkcije lex nad nekom niskom sa listom tokena koju hoćemo da dobijemo. Tokeni su upakovani u strukturu srcloc-token, koja čuva i lokaciju lekseme. Lokacija nam za sada nije bitna, ali kasnije ćemo moći da je iskoristimo kako bismo pravilno označili greške u programima na našem jeziku.

Sada možemo pokrenuti ove testove komandom:

[code]raco test tests[/code]

Testovi za parser i testovi za ekspander, koji ćemo praviti u ovom delu, konstruišu se na sličan način, i možete ih naći u Githab repozitorijumu projekta.

Prođimo kroz primer sa kraja prethodnog dela.

[code][init foo 42+7*7][/code]

lekserom i parserom pretvara se u sledeći S-izraz:

[code](libre-prog (libre-init foo (libre-sum
      (libre-sum (libre-prod 42)) "+" (libre-prod
      (libre-prod (libre-prod 7) "*" 7) "*" 7))))[/code]

Taj S-izraz je, po svojoj sintaksi, poptuno validan izraz u Raketu. Međutim, u Raketu nisu unapred definisane funkcije libre-prog, libre-init, libre-sum i libre-prod. U ekspanderu ćemo uraditi baš to.

Dok radimo na ovom delu prevodioca, od velike koristi biće nam Raketov makro (eng. macro) sistem. Makro služi da se (u vreme kompilacije) jedan S-izraz zameni drugim S-izrazom. Na primer, funkciju sabiranje, možemo definisati ovako:

[code](define (sabiranje x y)
 (+ x y))[/code]

Kada pokrenemo program, definiše se funkcija ili procedura sabiranje, koja prima 2 argumenta i sabira ih. Možemo je i isprobati u REPL-u.

[code]> (sabiranje 5 6)
11[/code]

Međutim, takođe možemo sabiranje uz pomoć makroa pretvoriti u validan Raket izraz.

[code](define-syntax sabiranje
 (syntax-rules ()
  [(sabiranje) 0]
  [(sabiranje x y) (+ x y)]
  [(sabiranje x …) (+ x …)]))[/code]

Sada se svaki izraz koji odgovara nekom od šablona koje smo definisali u okviru makroa sabiranje pretvara u odgovarajući Raket izraz. Prednost makroa leži u činjenici da se makroi „primenjuju” u vreme prevođenja, umesto kada pokrenemo program. To nam u opštem slučaju može ubrzati izvršavanje programa (jer smo deo izvršavanja uradili u toku prevođenja), ali nam i, zbog informacija koje su dostupne u vreme prevođenja, otvaraju mogućnosti koje u vreme izvršavanja nemamo.

U našem ekspanderu koristićemo malo moćniji konstruktor makroa – syntax-case.

Pogledajmo, na primer, makro za libre-sum, definisan u datoteci expander.rkt:

[code](define-syntax (libre-sum caller-stx)
 (syntax-case caller-stx ()
  [(libre-sum x) (syntax-protect (syntax/loc caller-stx x))]
  [(libre-sum x "+" y) (syntax-protect (syntax/loc caller-stx (+ x y)))]
  [(libre-sum x "-" y) (syntax-protect (syntax/loc caller-stx (- x y)))]
  [else
   (syntax-protect (raise-syntax-error
    ‘sum-error
   (format "wrong operator in: ~a" caller-stx)))]))[/code]

Sa caller-stx označavamo sintaksni objekat koji analiziramo. Ako je on oblika (libre-sum x), pretvaramo ga (uz syntax-protect i syntax-loc kojima opet čuvamo podatke o lokaciji izraza) u x. Ako je oblika (libre-sum x “+” y), pretvaramo ga u (+ x y) i slično u slučaju oduzimanja. Ako je oblika koji se razlikuje od nekog od ova tri, vraćamo sintaksnu grešku funkcijom raise-syntax-error.

Na sličan način definišemo i libre-prod, za množenje i deljenje, kao i libre-bool, za operacije poređenja.

Za ispisivanje na standardni izlaz uz pomoć libre-print, makro izgleda ovako:

[code](define-syntax (libre-print caller-stx)
 (syntax-case caller-stx ()
  [(libre-print) (syntax-protect (syntax/loc caller-stx (void)))]
  [(libre-print x y …) (syntax-protect (syntax/loc caller-stx
      (begin
      (displayln x)
      (libre-print y …))))]
  [else
   (syntax-protect (raise-syntax-error
    ‘print-error
    (format "wrong calling pattern in: ~a" caller-stx)))]))[/code]

Ukoliko pozovemo libre-print bez argumenata, ne ispisuje se ništa, što postižemo vraćanjem izraza (void). Ukoliko imamo više od jednog argumenta, prvo štampamo prvi uz pomoć displayln, pa onda pozivamo libre-print na ostatak argumenata. Time dobijamo validnu rekurzivnu definiciju makroa.

Kako bismo implementirali while petlju, moramo je „prevesti” na rekurzivni oblik.

[code](define-syntax (libre-while caller-stx)
 (syntax-case caller-stx ()
   [(libre-while test stmts …) (syntax-protect (syntax/loc caller-stx
       (let loop ()
       (when test
       stmts …
       (loop)))))]
   [else
    (syntax-protect (raise-syntax-error
    ‘while-error
    (format "wrong calling pattern in: ~a" caller-stx)))]))[/code]

Privremeno smo definisali funkciju loop, koju pozivamo iznova dok god se test izračunava na tačno.

libre-if je u odnosu na libre-while malo jednostavnije, jer u Raketu imamo funkciju if.

[code](define-syntax (libre-if caller-stx)
 (syntax-case caller-stx ()
  [(libre-if test s1) (syntax-protect (syntax/loc caller-stx
       (if test s1 (void))))]
  [(libre-if test s1 s2) (syntax-protect (syntax/loc caller-stx
       (if test s1 s2)))]
  [else
   (syntax-protect (raise-syntax-error
    ‘if-error
  (format "wrong calling pattern in: ~a" caller-stx)))]))[/code]

Preostale su nam još dve stvari – libre-init i libre-prog. Prvo moramo da odlučimo kako da čuvamo informacije o promenljivim vrednostima. [init foo 42] upisuje 42 u promenljivu foo. Postoji nekoliko rešenja za ovaj problem. Međutim, u okviru Raketa, on je već rešen. Možemo ovo da iskoristimo i naše promenljive prosto definišemo kao Raket promenljive. Jasno, koristićemo postojeću Raket funkciju define, ali nam to ostavlja još jedan nerešen problem. Za razliku od define, našom init naredbom možemo da „inicijalizujemo” ili definišemo promenljivu, ali i da promenimo njenu vrednost. U Raketu se za menjanje vrednosti prethodno definisane promenljive koristi funkcija set!. Zato ćemo init prevoditi u set!, ali nam je potrebno da sve promenljive koje koristimo unapred definišemo. To ćemo uraditi uz pomoć funkcije begin-for-syntax, koja se izvršava pre nego što makro sistem počne sa radom.

[code](begin-for-syntax
  (require racket/list)
  (define (syntax-flatten stx)
   (let* ([stx-unwrapped (syntax-e stx)]
     [maybe-pair (and (pair? stx-unwrapped) (flatten stx-unwrapped))])
   (if maybe-pair
     (append-map syntax-flatten maybe-pair)
     (list stx))))

 (define (find-unique-ids stmts)
  (remove-duplicates
   (for/list ([stx (in-list (syntax-flatten stmts))]
       #:when (syntax-property stx ‘libre-id))
    stx)
   #:key syntax->datum)))[/code]

Definišemo pomoćnu funkciju syntax-flatten, koja „poravnava” sintaksni objekat i vraća običnu listu. Nad takvom strukturom lako možemo da definišemo funkciju find-unique-ids, koja prolazi kroz listu i traži sve elemente sa sintaksnim svojstvom libre-id. Kada nam je ta funkcija definisana, možemo napraviti poseban makro libre-module-begin na sledeći način:

[code](define-syntax (libre-module-begin caller-stx)
  (syntax-case caller-stx ()
   [(libre-module-begin (libre-prog stmts …))
    (with-syntax ([(ids …) (find-unique-ids #'(stmts …))])
    #'(#%module-begin
     (define ids 0) …
     (begin stmts …)))]))[/code]

#%module-begin je početna tačka programa, pa mi definišemo svoju, libre-module-begin, koja prvo pronalazi sve jedinstvene identifikatore, a zatim pretvara (libre-prog stmts …) u

[code](define ids 0)
(begin stmts …)[/code]

Sada možemo lako napraviti i makro za libre-init.

[code](define-syntax (libre-init caller-stx)
 (syntax-case caller-stx ()
   [(libre-init id ",s") (syntax-protect (syntax/loc caller-stx
       (set! id (read-line (current-input-port) ‘any))))]
   [(libre-init id ",i") (syntax-protect (syntax/loc caller-stx
       (set! id (inexact->exact
         (string->number
         (read-line (current-input-port) ‘any))))))]
   [(libre-init id expo) (syntax-protect (syntax/loc caller-stx
        (set! id expo)))]
   [else
    (syntax-protect (raise-syntax-error
     ‘init-error
      (format "wrong calling patern in: ~a" caller-stx)))]))[/code]

Ukoliko je drugi argument ,s, učitavamo string sa standardnog ulaza. Ukoliko je drugi argument ,i, učitavamo broj sa standardnog ulaza. Ukoliko je neki izraz, vrednost promenljive menjamo u vrednost tog izraza.

Sada kada smo sve potrebne makroe definisali, ostalo je da omogućimo njihovo korišćenje van datoteke expander.rkt.

[code](provide libre-init
   libre-print
   libre-while
   libre-if
   libre-sum
   libre-prod
   libre-bool
    #%top-interaction
    #%app
   #%datum
   (rename-out [libre-module-begin #%module-begin]))[/code]

Kako bismo mogli konačno da počnemo da programiramo u našem jeziku, treba da u datoteci main.rkt povežemo sve različite delove našeg prevodioca i napravimo modul reader, koji će Raket prevodilac prepoznati kao čitač našeg jezika.

[code]#lang racket
(require "parser.rkt" "tokenizer.rkt" syntax/strip-context)

(define (read-syntax path port)
  (define parse-tree (parse path (make-tokenizer port path)))
  (strip-context
  #//(module libre-lang-mod libre-lang/expander
     #,parse-tree)))

(module+ reader
 (provide read-syntax))[/code]

Time smo napisali i poslednju liniju koda za ovaj kompajler. Sada možemo da instaliramo naš projekat komandom

[code]raco pkg install[/code]

u terminalu. Isprobajmo onaj program za računanje faktorijala iz prvog dela:

[code]#lang libre-lang
[print "Upisite broj:"] // Ovaj program izracunava faktorijal broja sa standardnog ulaza
[init foo ,i]
[init bar foo-1]
[if foo > 0 [while bar > 0
    [init foo foo*bar]
    [init bar bar-1]]]
[if foo > 0 [print foo] [print "Broj je manji od 0"]][/code]

Naravno, ni sam jezik, ni prevodilac koji smo sada napravili, nije savršen. Fale neke vrlo korisne naredbe kao što je break za izlazak iz petlje, operacije nad niskama, drugi tipovi podataka, logički operatori and, or i not, funkcije, i mnogi drugi konstrukti koji se uzimaju zdravo za gotovo u „pravim” programskim jezicima. Neka od ovih poboljšanja je teže implementirati od ostalih, ali se uglavnom svode na ista tri koraka – dodavanje pravila u lekser, dodavanje pravila u parser i dodavanje makroa u ekspander.

Ako želite da pogledate sav izvorni kod, možete naći repozitorijum na Githabu. Ostaje na vama da eksperimentišete, a ako se u nekom trenutku zaglavite, dokumentacija Raket jezika je dostupna na sledećem linku. Postoji i knjiga o pravljenju različitih jezika u Raketu koja je poslužila kao odličan referentni materijal i inspiracija za ovaj serijal.