Code Lake

Ce ne mai tine ocupati..

2007-04-28T00:25:00.000+03:00

In ultimul timp am avut un program destul de incarcat, asa ca Rascal nu a primit prea multa atentie. Marti am fost la o sesiune de comunicari Microsoft (unde atat Laur cat si eu am primit cate un Windows Vista -- jucarii noi :D). Apoi am pierdut putin timp cu vLite. E uimitor sa vezi cum un kit de windows de patru giga scade pana la 950 de mega (si as mai fi economisit ceva, dar mi-a fost mila sa scot suportul pentru natural speech la search).

In cea de-a doua parte a saptamanii ne-am ocupat cu organizarea etapelor judetene ale concursurilor InfoEduatie si CIA (care vor avea loc in aceeasi zi). Mai multe detalii aici. Asa ca am fost a toate liceele importante, am discutat cu profesorii si inca nu am apucat sa facem un barem. Cu putin noroc o sa ne ocupam de Rascal in weekendul asta.

Pana la urmatorul post, bucurati-va de semi-vara pe care ne-a oferit-o incalzirea globala.

Cum se scrie un compilator (4)

2007-04-21T16:14:00.000+03:00

Acum ceva timp v-am promis un articol in care sa vorbesc despre similitudinile dintre evaluarea de expresii si realizarea unui parser. Iata ca azi continui aceasta serie.

Parser-ul nostru de expresii pleca de la o idee simpla: la fiecare pas, el stia la ce sa se astepte si actiona in consecinta, in functie de token-ul nou citit. Nu am putea gandi la fel si in cazul unui parser pentru un intreg program? Haideti sa vedem (in liniile urmatoare, token-urile dintre paranteze drepte sunt optionale, acoladele indica repetitii, iar bara verticala indica o lista de alternative):

Un program (Rascal) contine doua tipuri de declaratii pe nivelul superior: variabile si functii.
Functiile sunt marcate prin "[entry] func", pe cand restul declaratiilor trebuie sa fie variabile.
O declaratie de variabila are forma " as [ := ]".
O declaratie de functie are forma "[entry] func ([{ as }]): | none", fiind urmata pe linia urmatoare de catre un bloc de instructiuni.
Expresiile au o forma asemanatoare cu cea data in post-ul trecut.
Un bloc de instructiuni poate fi vid, poate contine apeluri de functii, atribuiri sau instructiuni de control.
etc.

Daca studiem cu atentie o lista asemanatoare cu cea de mai sus, observam ca la fiecare moment putem spune ce structura urmeaza, in functie de ceea ce am intalnit si de starea curenta.

In aceste conditii, putem refolosi algoritmul din post-ul trecut, introducand mai multe stari pe langa cele de expresie, termen si factor. In acelasi timp, vom folosi cateva structuri de date in care memoram informatii despre variabilele si functiile declarate pana la momentul curent. Intr-adevar, efectuarea a doua treceri ar permite folosirea in programe a functiilor nedeclarate inca (vezi problemele asemanatoare din Pascal, C/C++, etc.), dar cred ca implementarea unei treceri preliminare va fi lasata pentru o "versiune" ulterioara.

Chiar daca articolul de astazi a fost nici prea lung, nici prea substantial, nu voi post-a cod deoarece acesta este destul de complex pentru a-l rescrie in momentul de fata; intr-un articol viitor voi vorbi ori despre IL si generarea de cod, ori voi aduce mai multe amanunte referitoare la memorarea informatiilor colectate de-a lungul compilarii.

Cateva lamuriri

2007-04-21T11:58:00.000+03:00

Am zis ca revin ieri. Am avut putina treaba si nu am putut sa scriu, dar iata astazi articolul promis. Si amanarea asta a fost una de bun augur pentru ca intre timp am facut cateva schimbari la compilator care vor face articolul mai interesant.
Dupa cum spunea si Laur incercam sa scriem compilatorul fara sa ne agatam prea tare de teorie. Fara limbaje formale, fara automate, folosind intuitia. Dar cat de buna este ideea? Sa luam un exemplu practic: scannerul din compilator. Scannerul este componenta care transforma secvenele de caractere citite din fisier in lexeme/atomi lexicali pe care ii poate intelege parserul. Asadar, transformam secventele de caractere in siruri. Cum? Simplu, citind caracter cu caracter din fisier si respectand cateva reguli construim atomii lexicali (stringuri). Destul de intuitiv, nu? Dar sa vedem despre ce reguli discutam:

Spatiile albe (blankuri): nu au nici o semnificatie (cu mici exceptii) pentru parser deci trebuie sa le eliminam. Exceptiile sunt caracterul tab si caracterul newline, care sunt importante pentru Rascal, dar nu si pentru majoritatea compilatoarelor.
Separatorii: caractere precum "(", ")", ":", etc. Ele despart secvente de caractere mai lungi (cuvinte cheie, idetificatori, constante sir de caracter si numere).
Identificatorii: secvente de caractere care pot fi cuvinte cheie, nume de variabile, etc.

Pe baza regulilor algoritmul scannerului este destul de simplu (nici nu trebuie sa fie complicat):

cat timp caracterul curent este blank
   ignoram

daca avem in caracterul curent un separator
   daca in caracterul curent se afla "
       citim constanta sir de caractere
   // Intr-un mod similar se fac verificarile
   // pentru <>, <=, >=, :=
   altfel
       iesim din scanner

daca avem cifra
   citim numar
altfel
   citim idetficator

Algoritmul de mai sus are cateva neajunsuri. Unul ar fi ca nu ia in seama caracterele nepermise in codul sursa al programuli scris in Rascal (%, #, $, etc) si cel de-al doilea ca lucreaza foarte mult cu stringuri. "<>" este un string si toate celelalte lexeme de asemenea. Poate ca nu pare un lucru rau la prima vedere, dar pentru aproximativ 50.000 de linii de cod numarul stringurilor alocate de compilator ajunge la 700.000 si ocupa circa 40 de mega de RAM! Clar abordarea noastra nu era buna. Atunci ne-am intors catre teoria, care spune ca este bine sa mapezi lexemele pe constante. Asta inseamna ca fiecarui terminal din gramatica ii corespunde o valoare numerica. Parserul nu va mai lucra cu stringuri (cu exceptia identificatorilor si a constanteor de tip sir de caractere) ci cu numere intregi.

Update

Dupa optimizarile de mai sus numarul de alocari a scazut de la 700.000 la 200.000 si compilatorul a ajuns sa compileze 77.000 de linii de cod pe secunda. Destul de rapid as zice.

In concluzie, nu este deloc o idee rea sa citesti cate ceva inainte sa te apuci sa implementezi, cu conditia sa nu te pierzi intr-atat de mult in documentatie incat sa nu mai poti iesi ;)

Good old times

2007-04-20T00:01:00.000+03:00

Iata primele doua programe scrise in Rascal (da, sunt executabile):

entry func EnterSandman(): none
   a as int32
   b as int32
   n as int32

   a := 0
   b := 1
   n := 20
   for i := 2 to n + 1
       write(a)
       c as int32 := a + b
       a := b
       b := c

Tema pentru voi: ghiciti ce face programul de mai sus :).

Iar cel de-al doilea:

entry func GhicesteNumarul(): none
   raspuns as int32
   start as int32 := 0
   stop as int32 := 100

   writeline("Ganditi-va la un numar intre 0 si 100...")
   write("Apasati 0 cand v-ati ales un numar. ")
   readline(raspuns)

   gasit as bool := false

   do
       write("Numarul dvs. este mai mic, mai mare sau egal cu ")
       mijloc as int32 := (start + stop) / 2
       write(mijloc)
       write(" ? (-1, 0, 1) ")
       readline(raspuns)

       if raspuns = -1
           stop := mijloc - 1
       elseif raspuns = 1
           start := mijloc + 1
       elseif raspuns = 0
           gasit := true
       else
           writeline("Nu inteleg decat -1, 0 sau 1!")
   while start <= stop and not gasit                 

   if not gasit                              
       writeline("M-ai mintit, nu ma mai joc :(")               
   else                              
       writeline("Am ghicit, asa e ca sunt bun?")

Go, Rascal!

Revin maine cu un post mai detaliat.

("On"|"Off"),"toppic".

2007-04-15T23:05:00.000+03:00

Pentru cei interesati de teoria compilatoarelor o sa postez linkul catre cartea lui Niklaus Wirth: Compiler Construction. De ce tocmai cartea lui? Pentru ca nu te lovesti de un zid de limbaje formale, automate finite si alte cele. Este explicata logic, clar si cu multe exemple de cod (in Oberon).

Rascal lives

2007-04-15T20:25:00.000+03:00

Cam asta era statusul lui Laur zilele trecute si nu se insela. Rascal e mai viu ca niciodata. Si din ce in ce mai destept: a invatat sa compare si sa numere. Da, ati ghicit, am trecut la generarea de cod. Miercuri noapte (ca doar noaptea se programeaza cel mai bine) am inceput (de fapt Laur a inceput, eu am asistat in mare parte) generatorul de cod. In postul trecut ne intrebam ce metoda sa alegem (ILASM, Reflection.Emit, Cecil sau IL). Am hotarat ca cea mai buna variabta este Reflection.Emit. Asta pentru ca este parte din .net, deci nu avem nevoie de o librarie externa, ca in cazul Cecil, si este mai eleganta decat generarea de ILASM, pentru ca nu o sa mai avem devoie de il assembler. Nu, nu o sa generam IL.

Daca, in legatura cu Cecil, ma plangeam ca nu are documentatie, pentru Reflection e destula, nu asta e problema.. Doar ca e laconica uneori. Macar e mai bine decat nimic. Asa ca prin "trial and error" in vreo 4 ore nedormite Rascal a invatat sa adune. Urmatoarea zi a invatat sa compare, iar ieri a invatat sa numere. Cu alte cuvinte stim: if, while, do si for. Mai e ceva de lucru, dar lucrurile nu arata deloc rau.

Din bucataria Rascalului

2007-04-06T00:33:00.000+03:00

Ne apropiem din ce in ce mai mult de faza a doua a dezvoltarii compilatorului: generarea de cod. Pentru ca Laur nu a terminat inca seria de articole dedicata parserului nu o sa intru in detalii. Tinta compilatorului fiind platforma .net stim doar ceea ce vrem: un executabil care sa ruleze pe platforma Microsoft. Cum ajungem acolo insa e partea interesanta. O prima alternativa ar fi sa generam cod ILASM si sa folosim il-assemblerul pentru generarea executabilului. In fond il-assemblerul vine cu platforma .net, deci o sa il avem la indemana. Desi nu pare tocmai elegant este o tehnica destul de intalnita. ILASM este un limbaj puternic si flexibil, dar extrem de complex. Daca nu ma credeti aruncati o privire peste specificatii. Descurajator, nu? Ei bine, o a doua posibilitate, mult mai .. hm .. accesibila, ar fi sa folosim libraria Cecil, o librarie dezvoltata de Jb Evain pentru emiterea de cod IL. Este destul de completa din cate imi spune Laur. Ca alternativa am putea folosi System.Reflection din .net, dar nu e la fel de completa ca si Cecil. Bineinteles, am putea sa generam si IL direct, dar tinem la sanatatea noastra mintala si preferam sa nu ne gandim la varianta asta.

Inainte de ideea unui assembly pentru .net a fost o alta, mult mai atragatoare: implementarea unei masini virtuale pentru Rascal. Da, o masina virtuala. De ce? Pentru ca numai in felul asta Rascal ar putea sa isi respecte filosofia pana la capat. Deocamdata o sa fim nevoiti sa o "adaptam" la principiile .net-ului. Asta pentru ca o masina virtuala nu este cel mai usor lucru de scris. Mai ales una performanta. Am spus "deocamdata" pentru ca decizia initiala a fost sa terminam prima versiune a limbajului. Dupa versiunea 1.0 o sa luam deciziile legate de directia in care se va dezvolta limbajul si daca vom implementa sau nu o masina virtuala (in functie de cat de dureroasa e experienta generarii de cod).
Sper ca Laur sa ierte asincronismul postului (am spus cam multe pentru un singur post). Pana data viitoare, numai bine.

Cum se scrie un compilator (3)

2007-04-04T22:47:00.000+03:00

V-am promis ca voi continua cu un articol despre structura unui parser. Incerc sa fac asta acum, desi nu ajuta nici oboseala, nici durerea de dinti, nici faptul ca Rascal nu se simte prea bine :).

Am spus la un moment dat ca limbajele de programare se pot imparti in mai multe categorii, in functie de tipul de parser ce poate fi folosit pentru a le recunoaste. Rascal face si el parte dintr-una din aceste categorii, aceeasi cu cea a limbajului C (si, eventual, C++) -- totusi, nu voi da numele acesteia, deoarece am promis o serie de post-uri fara astfel de "notiuni teoretice", notiuni pe care am de gand sa le introduc intr-un mod mai subtil.

Sa luam un limbaj foarte simplu (nu neaparat "limbaj de programare" in sensul standard): cel al expresiilor aritmetice formate cu operatorii *, +, -, constante, variabile si paranteze. O expresie corecta in acest limbaj este "(1-2)---3*a". Vom incerca sa gasim o metoda prin care putem deterimina corectitudinea (apartenenta la limbajul nostru a) unei astfel de expresii. Eu, cel putin, cunosc doua modalitati de a realiza acest lucru.

Prima necesita utilizarea a doua stive: una pentru operanzi (constante si variabile) si una pentru operatori. Acestora le putem asocia diferite prioritati: parantezele au prioritatea cea mai mica, apoi urmeaza adunarea si scaderea pe acelasi nivel, incheiand cu inmultirea. Vom parcurge expresia de la stanga la dreapta, procesand cate un token. Daca intalnim un operand, il punem in stiva, iar daca intalnim un operator, comparam prioritatea acestuia cu prioritatea celui din varful stivei. Daca este mai mare, il adaugam, daca nu, efectuam ultima operatie (extragem operanzii necesari din varful stivei operanzilor, apoi adaugam la aceasta rezultatul). Efectuarea operatiei nu este neaparat necesara, dar trebuie memorat numarul de elemente din aceasta. Daca avem destula grija si tinem cont de anumite cazuri particulare (cum ar fi "-" unar) si eventual incadram expresia initiala cu paranteze pentru a avea o structura unitara, ne putem indeplini scopul propus.

A doua metoda foloseste si ea o stiva, dar una implicita. Ideea pare un pic mai naturala -- sa privim expresia "de la distanta": vedem o suma de termeni (deoarece adunarile si scaderile se efectueaza ultimele), asemanatoare cu ... + ... - ... + .... Pare atunci firesc sa definim expresia ca fiind o suma de termeni. Dar ce este un termen? Simplu: un produs de factori: ... * ... * ..., etc. Si ce este un factor? Au ramas constantele, variabilele, parantezele si operatorul minus unar. Se observa ca prin coborarea in aceasta ierarhie se ajunge la "prioritati" mai mari.

Vom incerca sa explicitam observatiile acestea intr-un mod mai formal:


Expresie := Termen ['+'|'-' Termen]*
Termen := Factor ['*' Factor]*
Factor := Constanta | Variabila | '+' Factor | '-' Factor
          | '(' Expresie ')'

Unde "|" inseamna alternativa, iar "*" inseamna repetarea expresiei precedente de un numar oarecare de ori. Aspectul factorilor poate parea bizar, dar sa ne amintim de legatura dintre nivelul in ierarhie si prioritate: operatorii unari, parantezele si constantele/variabilele sunt "evaluate" primele, trecandu-se apoi la produse, respectiv sume.

Priviti bine cele trei linii de mai sus. Vreau sa le intelegeti. Trebuie sa le intelegeti, pentru ca vom aborda in mod similar problema verificarii sursei unui program.

Le-ati inteles? Ok. Va cred, in fond :).

Atunci n-ar trebui sa va mire faptul ca propun o solutie recursiva de evaluare. Plecam din Expresie, in care citim un Termen; apoi, in functie de token-ul curent (care trebuie sa fie +, - sau sfarsit de fisier), continuam sau nu cautarea termenilor. Termen va apela Factor, iar Factor se va intoarce direct (variabila sau constanta), se va autoapela (operator unar) sau va apela Expresie (paranteza deschisa), si va astepta o paranteza inchisa.

Parerea mea, cel putin, este ca a doua varianta este mai naturala si mai explicita; este, oarecum, si mai lenta, datorita apelurilor recursive. Este si varianta folosita in Rascal :). (Dar nu va faceti griji pentru viteza: Rascal poate, la ora actuala, sa verifice aproape 35000 de linii pe secunda, pe un calculator destul de vechi). Putem, totusi, deosebi cele doua modalitati: una foloseste o stiva explicita si face operatii in varful acesteia, pe cand a doua pleaca de la o descriere naturala si foloseste apeluri recursive.

Dar sa revenim la expresiile noastre aritmetice: putem scrie un program care sa le verifice? Fireste. Studiati cu atentie codul: desi poate parea ciudat la prima vedere, nu am facut decat sa transpun cele discutate aici.

Data viitoare voi vorbi despre cum putem aplica aceeasi metoda la programe intregi.

Compiler Design and Implementation

2007-04-03T20:55:00.000+03:00

On this blog we will post a series of articles on the theme of compilers. It was intended to be written in Romanian, but due to a number of visits from other countries we think it's better to ask whether anyone else is interested in this subject. If so, please post a comment on this page.

Cum se scrie un compilator (2)

2007-04-02T21:55:00.000+03:00

In articolul trecut am promis ca voi scrie despre analiza lexicala. Ce reprezinta ea? Fiecare limbaj (nu neaparat de programare) are un set de simboluri care pot fi folosite, un alfabet. Trebuie tinut cont, totusi, de faptul ca o insiruire de astfel de "semne"/simboluri nu are (inca/neaparat) un sens asociat ei. Dar cunoasterea acestora este necesara pentru intelegerea limbajului in cauza.

In cazul nostru, vom sari peste cateva etape si vom considera ca alfabetul limbajului Rascal este format din unitati carora le poate fi asociat, direct sau nu, un inteles: de exemplu, nu vom considera o litera ca element acestuia, ci un cuvant. Cum arata ele in cazul limbajului Rascal?

O serie de cuvinte-cheie: "entry", "func", "as", "return", "ref" (parametru transmis prin referinta), etc.
Operatori: ":=" (atribuire), "+", "-", "*", "/", "mod", "or", "<=", "<>" (diferit) si in continuare.
Delimitatori: ";" (sfarsitul unei instructiuni, este optionala), "," (delimitator folosit in lista de variabile), "(" si ")" (pentru expresii, respectiv apeluri de functie).
Tipuri de date: "bool", tipuri intregi de forma "int8", "uint16", ... (prefixul "u" insemnand "unsigned"), poate chiar tip caracter sau string.
Constante: "42", "0", "true", "false", eventual caracter, string sau numar real.
Identificatori: acestia pot fi nume de functii sau variabile; am ales o structura clasica, acestia fiind siruri de caractere ce pot incepe cu litera sau underscore ("_"), continuandu-se apoi cu caractere ce nu sunt folosite ca operatori sau delimitatori. Nu am acordat mare atentie acestui fapt, asa ca, in versiunea actuala, Rascal accepta identificatori continand caractere precum diez, semn de exclamare sau dolar.

Abordarea noastra este, cred, mai clara decat cea clasica (in care fiecare caracter este prelucrat separat, cuvintele cheie si operatorii mai lungi de un caracter fiind formate intr-o faza ulterioara).

Iata cum a fost implementat tokenizer-ul din Rascal.

[Imi cer scuze pentru faptul ca am recurs la un site extern si am pus o bucata atat de mare si neatragatoare de cod, dar nu stiu cum a facut Alex codul lui sa arate atat de bine. Poate ca le voi schimba un pic mai tarziu.]

Se pot observa cateva particularitati ale codului pe care il folosim:

Este scris in limbajul C#: am luat aceasta decizie deoarece C# este un limbaj puternic si care se preteaza scrierii rapide de cod. Nu vom folosi prea multe particularitati ale acestuia, exemplul cel mai important ar fi tipul de date string (disponibil in C++ ca std::string, CString, etc.), acesta fiind urmat de colectiile generice de date (un analog ar fi std::vector din STL). Atributul "DebuggerStepThrough" poate fi ignorat, el ajutandu-ne doar la depanarea programului (cred ca numele ii indica destul de clar semnificatia).
Avem cateva functii ajutatoare care compara un string sau caracter cu cateva constante (cuvinte cheie, delimitatori, etc.). O parte din codul acesta ar putea fi "infrumusetat", o recunoastem.
Functia principala este ReadToken(). Aceasta citeste cate un token (unitate careia i se poate atribui un sens) din fisier, face niste verificari pentru a ignora comentariile (momentan doar comentarii ce incep prin "//" si se termina la sfarsitul liniei) si pentru a returna "<=" sau ceva asemanator (si nu "<") atunci cand este cazul.
Rezultatul este memorat in variabila token; sfarsitul fisierului va fi anuntat printr-un sir vid.

Cam la atat se rezuma partea de analiza lexicala. Pentru a testa acest cod, putem scrie o bucla simpla care citeste cate un token si il afiseaza, pana la terminarea fisierului. Avand la intrare un fisier cu continutul:

func foo(): none

entry func main(number as int32, count as int32): none
x as int8
a as int8 := 1 shl 2 shl 7 shl 3 shr 2
a := 1*x/2/a/x
foo()
y as bool

, programul va afisa:


Token: func
Token: foo
Token: (
Token: )
Token: :
Token: none
Token:

Token:

Token: entry
Token: func
Token: main
Token: (
Token: number
Token: as
Token: int32
Token: ,
Token: count
Token: as
Token: int32
Token: )
Token: :
Token: none
Token:

Token:
Token: x
Token: as
Token: int8
Token:

Token:
Token: a
Token: as
Token: int8
Token: :=
Token: 1
Token: shl
Token: 2
Token: shl
Token: 7
Token: shl
Token: 3
Token: shr
Token: 2
Token:

Token:
Token: a
Token: :=
Token: 1
Token: *
Token: x
Token: /
Token: 2
Token: /
Token: a
Token: /
Token: x
Token:

Token:
Token: foo
Token: (
Token: )
Token:

Token:
Token: y
Token: as
Token: bool
Token:

. Iata cat de usor a fost sa impartim un fisier in token-uri. Continuarea, adica felul in care avem de gand sa le folosim, intr-un articol viitor.

PS: Daca aveti sugestii sau remarcati un greseli in codul aratat, sunteti rugati sa ne anuntati.

Cum se scrie un compilator (1)

2007-04-02T21:10:00.000+03:00

In ultimul timp, programatorii au ajuns sa ia compilatoarele pe care le folosesc "for granted". Nu vom spune daca asta e un lucru bun sau nu, dar trebuie sa amintim vremurile in care programele erau scrise in limbaj de asamblare sau chiar in cod masina.

Gata, le-am amintit.

Lasand gluma la o parte, este firesc sa ne intrebam cum functioneaza un compilator. Raspunsul? Dupa cum vom vedea, raspunsul este (si trebuie sa fie) "simplu".

Luati o carte despre compilatoare sau un curs de limbaje formale si veti putea citi despre simnboluri terminale si neterminale, productii, ierarhia Chomsky, gramatici mai mult sau mai putin senzitive la context, automate, parser-e LL, LR sau LALR. Si poate ca dupa ce ati rasfoit respectivele materiale veti pune o singura intrebare: "Si totusi, cum functioneaza un compilator?".

Seria de articole pe care o incep azi se doreste a fi o incercare de raspuns la aceasta intrebare. Va fi, oare, o reusita? Nu stiu. Dar sper ca va putea fi un punct de plecare pentru cei interesati.

Sa incepem, asadar, discutia despre compilatoare. Lasand la o parte impartiri mai fine, un compilator are doua parti esentiale:

Parser-ul, care analizeaza codul sursa, il verifica de erori si pastreaza sau deduce unele informatii semantice.
Generatorul de cod, care foloseste informatiile obtinute de parser pentru a genera cod mai mult sau mai putin executabil (cod nativ, cod pentru o masina virtuala). Fireste, in cazul interpretoarelor, aceasta parte se ocupa de executarea instructiunilor.

In aceste articole vom analiza o modalitate de implementare a celor doua parti prin prisma experientei obtinute din implementarea unui compilator pentru limbajul Rascal. A se nota ca, in momentul de fata, compilatorul nostru este departe de a fi definitivat. Nu garantam, deci, nimic in privinta corectitudinii sau a functionalitatii codului pe care il vom prezenta, si nici in privinta unei eventuale finalitati.

In articolul urmator voi vorbi despre analiza lexicala, partea de baza a unui parser.

Extra, extra, read all about it!

2007-03-31T00:47:00.000+03:00

Iata o mostra de cod compilabil:

// Variabila globala.
foo as int;

//
// Functia principala.
//

entry func main(number as int, count as int): none
    k as word;
            l as quad;
        m as word;
    j as bool := 1 < 2 or 3 < 4;

func foo(number as unsigned quad): none
    q as unsigned quad;

Da, nu e tocmai ce am aratat in primul post, dar nici atat de mult nu mai e. Ce stie compilatorul in momentul asta? Intr-o ordine aleatorie:

Functii.
Parametri de functii.
Variabile.
Tipuri de date.
Blocuri delimitate de taburi ('\t'). Mai exact, un bloc este definit prin nivelul lui de indentare. Iesirea din bloc se face la intalnirea unui nivel de indentare mai mic. In bucata anterioara de cod blocurile sunt dupa cum urmeaza: blocul 1 (care este chiar blocul principal al functiei) ce contine variabilele k si j, cat si parametrii number si count; blocul 2 ce contine variabila l; blocul 3 ce contine variabila m;
Scopuri de variabile. Parametrii unei functii nu pot fi "umbriti" in interiorul ei indiferent de blocul in care se face declaratia. Daca in exemplul de cod anterior am declara number in orice bloc am primi eroarea: InvalidIdentifier: Identifier "number" redeclared on line [...].
Comentarii pana la sfarsitul liniei.
Expresii -- inca in lucru.

Ce o sa modificam in curand:

Tipurile de date. Deocamdata Rascal are urmatoarele tipuri de date: private readonly string[] typeList = { "bool", "byte", "word", "int", "quad" }; Tipurile intregi sunt dupa marime: byte = 1, word = 2, int = 4, quad = 8 octeti. Toate sunt cu semn. Modificatorul unsigned permite folosirea bitului de semn pentru reprezentarea valorii. Dar din alte limbaje utilizatorul este obisnuit cu byte si word ca fiind unsigned in mod implicit. Tipul quad nu este foarte cunoscut. S-ar putea ca pe viitor sa avem nume conventionale cu semnificatii deja cunoscute e.g: byte si word sa fie unsigned, sa intorducem long ca modificator si sa scoatem quad, etc.

La ce lucram acum:

Expresii. Tot ce tine de partea de expresii, atribuiri, verificari de tipuri, etc.

Si acum un mic bonus: primul screenshot cu Rascal.

Output cu verbosity de debug (2). Eroarea este cea de redeclarare a lui "number", care este parametru.

Operatii pe biti fara anestezie

2007-03-30T13:08:00.000+03:00

Cum or sa arate operatorii pe biti in Rascal? Am putea sa ii pastram pe cei logici, dar sintaxa ar fi ambigua (atat pentru compilator cat si pentru programator). Inchipuiti-va ca trebuie sa intretineti un program care arata asa:

if not not a > 0 and b and c > 1 or d or 3 = 4
    writeline("Conditia e indeplinita");

In C# secventa de mai sus s-ar scrie:

if (!(~a > 0) && ((b & c) > 1) || ((d | 3) == 4))
    Console.WriteLine("Conditia e indeplinita");

Asa ca ideea de a folosi un singur set de operatori si pentru operatiile pe biti si pentru cele logice nu este una grozava. In plus ne-ar ajuta si in implementare (am reusi sa evitam ambiguitatile din gramatica).

EB ::= TB ["or" | "xor" TB]*
TB ::= FB ["and" FB]*
FB ::= R
R ::= E ["<" | "<=" | ">" | ">=" | "=" | "<>" E]
E ::= T ["or" | "xor" | "+" | "-" T]*
T ::= F ["and" | "shr" | "shl" | "*" | "/" F]*
F ::= "true" | "false" | varb | funcb | num | var | func |
"+" F | "-" F | "not" F | (EB)

Asta e gramatica (BNF) pe care o facuse Laur cand ne gandeam sa pastram acelasi set de operatori. La prima vedere pare in regula, dar daca luam in calcul conditia de ambiguitate enuntata de Niklaus Wirth (creatorul Pascalului si al limbajelor ce l-au succedat: Modula si Oberon) in lucrarea sa Compiler Construction:

"We call a syntactic class ambiguous if it can be attributed several structures. A language is ambiguous if it contains at least one ambiguous syntactic class (construct)."

observam ca gramatica este ambigua. De ce? Pentru ca odata intalnit simbolul "not" nu o sa stim in ce clasa sintactica sa trecem: Factor (F) sau Factor boolean (FB).

"Si ce e atat de rau la o gramatica ambigua?" va puteti intreba. Ca raspuns o sa dau tot un citat din lucrarea mai sus mentionata:

"These (ambiguous sentences) may enrich spoken languages; ambiguous programming languages, however, are simply useless."

Daca nu am folosi aceeasi operatori pentru expresiile booleene si cele aritmetice am putea evita problema de mai sus. Insa ne lovim de o alta problema: ce operatori putem folosi ca sa pastram expresivitatea limbajului? Initial am fost tentat de operatorii din C (&,|,^,!), dar, dupa cum spunea si Laur, nu sunt tocmai in spiritul limbajului Rascal. Ce sintaxa putem alege pentru operatori atunci?

Din toate variantele la care ne-am gandit cred ca cea mai reusita este prefixarea operatorilor logici cu termenul "bit" e.g: bitand, bitor, etc. Dar nu este cea mai fericita alegere pentru estetica limbajului.

Mai jos sunt cateva variante la care m-am gandit in dimineata asta si pe care le voi discuta cu Laur putin mai tarziu:



if not bitInvert 1 > 2 bitXor 3
;

if not ~1 > 2 ^ 3
;

if not (~)1 > 2 (^) 3
;

if not |1 > 2 \/ 3
;

if not bitnot 1 > 2 bitxor 3
;

if not [bitwise] not 1 > 2 [bitwise] xor 3
;

if not [not 1] > [2 xor 3]
;

if not {not 1} > {2 xor 3}
;

if not ~iNV 1 > 2 ~XOR 3
;

if not <inv> 1 > 2 <xor> 3
;

if not /inv/ 1 > 2 /xor/ 3
;

if not .inv. 1 > 2 .xor. 3
;

if not |inv 1| > |2 xor 3|
;

if not $inv 1 > 2 $xor 3
;

if not inv: 1 > 2 xor: 3
;

if not .inv 1 > 2 .xor 3
;

if not `inv` 1 > 2 `xor` 3
;

if not _inv_ 1 > 2 _xor_ 3
;

Nu cred ca va fi prea incantat de majoritatea (sincer, nici eu nu sunt). Voi ce parere aveti?

Rascal

2007-03-26T15:14:00.000+03:00

Ce este Rascal? Deocamdata este doar o colectie de fisiere C#. Poate ca o intrebare mai buna ar fi: ce o sa fie Rascal? O sa fie un limbaj de programare usor de folosit, dezvoltat pentru .NET.

De ce Rascal? Initial, proiectul avea ca scop implementarea unui compilator de Pascal pentru platforma .NET. Insa exista proiecte similare si nu e prea distractiv sa reinventezi roata. Asa ca am luat decizia sa dezvoltam un limbaj nou, care sa incorporeze conceptele care ni s-au parut interesante in limbajele de programare pe care le-am intalnit poana acum. Si, totusi, de ce Rascal? Pentru ca R este dupa P in alfabet, iar Qascal nu e tocmai un nume reusit.

Daca vom integra toate conceptele care ne plac (si pe care stim sa le implementam) in limbaj, nu va iesi un soi de sorcova imposibil de folosit? Speram sa nu se intample asta. Intrebarea pe care ne-am pus-o initial a fost: "Noi am programa in limbajul asta?". O sa incercam ca indiferent de modificarile pe care le aducem raspunsul sa ramana "Da".

Dar cum arata limbajul? Ce sintaxa are? Inca lucram la ea, adaugam fetureuri si le modificam pe cele existente pe masura ce proiectul se maturizeaza. Exemplul urmator este cel de la care am plecat cand am inceput sa lucram la compilator:


//
// Citeste count numere de la tastatura si intoarce o lista
// formata din ele.
//
func ReadNumbers (count as byte): int list
   numbers as int list;
   number as int;

   for i := 1 to count
       write ("n = ");
       readline (number);

       numbers := list(numbers, number);

   return numbers;

//
// Main function
//
// empty(), head() si tail() sunt predicate predefinite
// care lucreaza pe liste.
//
entry func main (args as string list): none
   countNumbers as byte;
   myNumbers as int list;

   write ("How many numbers? ");
   readline (countNumbers);

   myNumbers := ReadNumbers (count: countNumbers);

   while not empty (myNumbers)
       if hd := head (myNumbers) mod 2 = 0
           writeline (hd);
           myNumbers := tail (myNumbers);

Cateva trasaturi speciale sunt marcarea functiei de intrare in program folosind cuvantul cheie entry, tipul none, care este similar tipului void din C, parametri cu nume si demarcarea blocurilor pe baza indentarii.

In urmatoarele posturi o sa discutam despre decizii de design si despre implementare pe masura ce o sa dezvoltam compilatorul si limbajul. O sa fie un blog viu, o imagine dinamica a proiectului in care speram sa aratam cum ia forma un limbaj de programare.