Abstract Syntax Trees

După ce am scris despre tabelele de simboluri, am să scriu şi despre restul arborelui şi tipurile de noduri care apar. În primă instanţă, nodurile se împart în două categorii: noduri declarative şi non-declarative. În momentul generării codului, pe baza nodurilor declarative se generează metadata iar pe baza nodurilor non-declarative se generează instrucţiuni IL.

Tabelele de simboluri conţin doar noduri declarative. Nodurile declarative sunt noduri care descriu, de exemplu, o clasă (nume, părinte, interfeţe implementate, vizibilitate etc.) sau o metodă (nume, parametri, tip întors, modificatori gen virtual, static etc.). Dacă pentru generarea codului se foloseşte Reflection.Emit, acestor noduri le corespund obiecte de tipul TypeBuilder, MethodBuilder şi aşa mai departe. Nodurile declarative pot conţine atât alte noduri declarative (un nod care descrie o clasă conţine noduri care descriu membrii clasei) cât şi noduri non-declarative (un nod care descrie o metodă conţine noduri care descriu instrucţiunile din corpul metodei). Tabelele de simboluri rezolvă referinţele căutând în nodurile declarative pe care le conţin.

Nodurile non-declarative reprezintă instrucţiunile din corpurile metodelor. Folosind Reflection.Emit, aceste noduri folosesc un ILGenerator pentru a emite instrucţiuni. Nodurile se împart la rândul lor în două categorii: noduri statement şi noduri expression. Nodurile statement nu întorc valori, cele expression întorc întotdeauna o valoare. De exemplu, dacă în codul pe care vrem să-l compilăm avem

x = 100 + 5;

partea din AST corespondentă expresiei 100 + 5 este formată din trei noduri de tip expresie. Un nod expresie este de tipul BinaryExpression (expresie cu 2 termeni), care descrie operaţia (adunare) şi conţine două noduri expresie, câte unul pentru fiecare operand. În cazul nostru, operanzii sunt de tip IntLiteral, adică o expresie constantă care întoarce o valoare de tip întreg. La nivelul expresiilor se face type-checking şi se construiesc conversiile implicite. De exemplu, pentru

x = 100 + 0.5;

Avem o constantă de tip int şi una de tip double. Atunci adăugăm în AST un nod, între nodul BinaryExpression şi nodul IntLiteral, care se ocupă de conversia din int în double. Apare întrebarea de ce să folosim trei noduri pentru o expresie atât de simplă? Păi expresia a fost doar un exemplu pe când tipurile de noduri rămân aceleaşi. Pentru expresia

100 + 5 + 10

avem nodul BinaryExpression care descrie prima adunare şi cei doi operanzi: IntLiteral (100) şi BinaryExpression (+) care conţine la rândul lui două noduri IntLiteral (5 şi 10). După cum vedem, astfel se pot reprezenta expresii oricât de complexe. Parserul se asigură că arborele va fi construit ţinând cont de prioritatea operatorilor (înmulţiri înainte de adunări, etc.). Exemplu de tip de expresii sunt: literale (constante literale), expresii unare (expresii care au doar un operand: negarea logică, minus unar), expresii binare (expresii cu doi operanzi: adunări, scăderi, comparaţii, şi logic, sau logic etc.), apeluri de metode (metodele care întorc void sunt excepţii, în rest toate metodele întorc o valoare deci sunt considerate expresii), indexeri aplicaţi matricilor şamd.

Pornind de la o clasă abstractă Expression, derivăm toate tipurile de noduri ce descriu expresii.

abstract class Expression
{
    public Type returnType;
    public abstract void Evaluate();
    public abstract void Emit(ILGenerator ilGen);
}

Avantajul acestei reprezentări este că fiecare expresie conţine noduri Expression, deci nu este nici o problemă dacă un parametru al unei metode este o constantă, o împărţire sau un apel la o altă metodă, cât timp moşteneşte clasa Expression. Arborele este parcurs de două ori: prima oară se face o evaluare, apelând recursiv metoda Evaluate (aici se verifică referinţele şi compatibilitatea tipurilor), apoi se emite codul, apelând recursiv metoda Emit. Parametrul ilGen este dat de nodul declarativ al metodei, folosind MethodBuilder.GetILGenerator(). Dacă avem de exemplu un tip de nod care descrie o adunare (simplific aici, de obicei acest tip de nod descrie toate operaţiile binare), AddExpression:

class AddExpression : Expression
{
    public Expression leftOperand;
    public Expression rightOperand;

    public override void Evaluate()
    {
        leftOperand.Evaluate();
        rightOperand.Evaluate();

        if (leftOperand.returnType != rightOperand.returnType)
            ...
    }

    public override void Emit(ILGenerator ilGen)
    {
        leftOperand.Emit(ilGen);
        rightOperand.Emit(ilGen);
        ilGen.Emit(OpCodes.Add);
    }
}

După cum se vede, operanzii pot fi orice fel de expresie, atât timp cât tipurile returnate sunt compatibile. După cum scriam şi într-un post mai vechi, .NET foloseşte o stivă pentru a evalua expresiile, şi astfel ne asigurăm că stiva este echilibrată. leftOperand.Emit lasă o valoare de tip leftOperand.returnType pe stivă. rightOperand.Emit lasă la rândul lui o valoare de tip rightOperand.returnType. Instrucţiunea add consumă cele două valori şi pune pe stivă rezultatul adunării. Astfel AST-ul poate fi construit incremental, adaugându-se diferite tipuri de noduri pentru diferite tipuri de expresii rând pe rând până când putem evalua orice expresie ce poate să apară în limbajul nostru.

Celălalt tip de noduri, statement, se deosebeşte de expresii prin faptul că nu întoarce o valoare. Statement sunt toate construcţiile limbajului diferite de expresii. De exemplu construcţia condiţională if-else este reprezentată ca

if (expression) statement else statement

Practic, nodul conţine un nod de tip expresie şi două noduri de tip statement. La fel şi construcţia while:

while (expression) statement

De fapt şi blocurile de cod sunt tot statements: un nod de tip statement care conţine o listă de noduri de tip statement. Avân ca părinte comun clasa abstractă Statement, avem din nou avantajul de a putea trata în acelaşi fel o construcţie de tip

if (expression)
{
    statement;
    statement;
    statement;
}

şi una de tip

if (expression) statement;

Practic, orice construcţie a unui limbaj poate fi considerată fie expresie, fie propoziţie. Există câteva excepţii, construcţii ce pot fi atât expresie, cât şi propoziţie. Un apel de funcţie, de exemplu

Console.ReadLine();

lasă pe stivă o valoare doar că, în unele cazuri, valoarea nu se consumă. Dat fiind tipul de nod CallExpression care apelează o funcţie şi îi întoarce valoarea, soluţia este construirea unui tip de nod CallStatement care conţine un nod CallExpression. În momentul generării codului, CallStatement apelează metoda de generare a codului ce corespunde nodului CallExpression şi mai adaugă instrucţiunea pop, pentru a goli stiva.

Un alt exemplu sunt atribuirle care, la unele limbaje pot fi considerate expresii. În Pascal avem

x := 10;

statement, care nu poate fi folosit ca expresie. În alte limbaje, precum C sau C#, avem, pe lângă

x = 10;

ca statement, expresii ca

if ((x = Console.ReadLine()) == "")

Aceste expresii se tratează în mod diferit deoarece .NET, la nivelul IL, nu se lasă nimic pe stivă după o atribuire. În acest caz, dat fiind tipul de nod AssignementStatement, construim nodul de tip AssignementExpression care adaugă instrucţiunea dup după evaluarea expresiei din dreapta semnului “=”. Dup duplică valoarea din vârful stivei astfel încât, după ce este consumată odată de atribuire, valoarea rămâne pe vârful stivei pentru următoarea expresie.

Cam aşa ar trebui să arate un AST. Evaluarea şi generarea codului se fac recursiv, pornind de la tabela de simboluri, evaluând şi generând nodurile declarative, apoi nodurile non-declarative.

Happy compiling!

Rezolvarea şahului

Până revin cu nişte posturi plictisitoare despre construirea compilatoarelor, mi-am amintit de o problemă interesantă despre care am discutat mai demult cu un prieten, anume rezolvarea jocului de şah. Construirea unui graf orientat cu nodurile reprezentând toate poziţiile care pot apărea pe tablă şi muchiile reprezentând mutările, se poate dezvolta un algoritm care să poată determina, încă de la prima mutare, un final avantajos al partidei (eu susţin că este remiză, prietenul cu care discutam susţine că albul va câştiga).

Dacă stăm să ne gândim la numărul de ramificaţii posibile la fiecare mutare, problema pare NP-completă. Totuşi, în cazul şahului, spaţiul problemei este finit. Nu există un n care, dacă creşte, să crească şi timpul de soluţionare a problemei. Din câte am înţeles, există aproximativ 10^49 poziţii posibile, un număr extrem de mare dar un număr finit. Având suficient spaţiu de stocare şi suficientă putere de procesare, se poate determina o soluţie optimă pentru jocul de şah. Ce ar presupune asta? Ar fi practic imposibil ca un om să învingă un calculator la acest joc. Ştim că Deep Blue l-a bătut pe Kasparov, dar a fost un meci strâns, cu victorii câştigate atât de campion cât şi de computer. Dacă şahul s-ar rezolva, nici un om n-ar mai putea învinge, indiferent de capacitate, un calculator şi chiar şi o partidă jucată de două calculatoare s-ar termina cu o remiză.

Numărul 10^49 este un număr imens, într-adevăr, şi acesta ar fi doar numărul de noduri al grafului. Numărul de muchii (mutări posibile) ar fi şi mai mare, însă, dacă e să cred predicţiile pe care le-am tot auzit în ultima vreme – cum că peste vreo 10 ani un computer va avea puterea de procesare a creierului uman şi că peste 20 de ani un computer va avea puterea de procesare a întregii rase umane – atunci sunt convins că în timpul vieţii mele şahul va fi rezolvat.

Food for thought: şahul, “jocul regilor”, vechi de câteva secole, cu nenumărate cărţi scrise despre el, teorii, campioni şi campionate, redus la o succesiune predeterminată de mutări cu un final cunoscut de la început de un algoritm de căutare exhaustivă (adică brute force, nimic fancy). Eu zic că în maxim 30 de ani. Aşa că mai jucaţi acum, cât timp mai este distractiv

“The Empire Strikes Back”

Am asistat vineri la o prezentare din cadrul IT Fest numită Revoluţia Free şi Open Source Software, prezentare care a fost practic o oră de campanie anti Microsoft. De prost gust şi slab argumentat. De exemplu, întreabă tipul “câţi de aici mai folosesc încă Internet Explorer?”. Eu am folosi câţiva ani buni Mozilla, dar am trecut de vreun an la IE7 şi din câte am văzut, IE8 va rupe. Mie personal îmi place mai mult, interfaţa e construită mult mai intelegient, spaţiul de afişare al paginilor este mai mare, dar nu vreau să intru în detalii… Nu contează de ce folosesc eu IE în loc de Mozilla. Asta nu mă face mai prost sau mai prost informat decât cei care folosesc Mozilla, mai ales că eu am încercat ambele browsere şi am văzut plusuri şi minusuri la amândouă. Un argument al prezentatorului nostru a fost: “Până la IE6 inclusiv, Microsoft nu a implementat x şi y standarde, IE7 nu ştiu că nu l-am folosit niciodată”. Deci treceţi la Mozilla. Foarte convingător.

Am asistat la o mulţime de prezentări susţinute de Microsoft şi acolo este o cu totul şi cu totul altă abordare. Dacă vrei să convingi lumea să încerce ceva, prezinţi plusurile produsului, nu arunci cu noroi în produse concurente. Microsoft nu poate să facă asta pentru că are imaginea corporaţiei de menţinut dar asta e irelevant. Am văzut prezentări de produse Microsoft susţinute de comunităţi ca RONUA unde, până la urmă, se poate zice orice, dar nimeni nu a zis chestii de genul “Oracle e naşpa deci folosiţi SQL Server”.

Da, eu folosesc produsele Microsoft, dar nu îi consider pe cei care folosesc platforme Linux proşti sau că au penisul mic. E o chestie de mentalitate pe care o găsesc supărătoare la “linuxişti”, care de multe ori consideră că dacă ai un Windows sau foloseşti VS nici nu au ce discuta cu tine. E o copilărie. Şi nu vorbesc în necunoştinţă de cauză. Au trecut prin compul meu sisteme de operare de la o distribuţie Red Hat care a apărut într-un număr al revistei Chip acum mulţi, mulţi ani, până la distribuţia de Ubuntu care se dă gratis pe CD. Am folosit şi Mozilla şi Eclipse şi multe altele. Pur şi simplu am preferat să rămân la ce folosesc acum şi nu vreau să încep discuţii de genul care e mai tare. Până la urmă software-ul e o unealtă pe care o foloseşti ca să atingi un scop şi toate produsele au puncte tari şi puncte slabe.

În fine, “prezentarea” mi-a lăsat un gust amar. Şi nu critic (nici nu am făcut-o şi nici nu o voi face) utilizatorii altor platforme, critic mentalitatea. Până la urmă ne împărţim în programatori, administratori şi arhitecţi nu în Imperiul cel Rău şi rebeli.

Symbol Tables

Abstract Syntax Trees sunt folosiţi pentru reprezentarea intermediară a codului despre care vorbeam în postul trecut. Menţionez că există şi alte modele de reprezentare intermediară şi că tipul de AST pe care îl prezint este cel folosit de mine dar în nici un caz bătut în cuie.

În primul rând, există tabelele de simboluri. Tabelele de simboluri conţin declaraţii de clase, metode, variabile etc. din codul sursă, toate acestea fiind considerate simboluri. O tabelă de simboluri este sociată fiecărui scope. Un scope este o porţiune de program care poate conţine astfel de declaraţii. În C# de exemplu, un namespace are un scope care conţine declaraţii de clase, structuri, interfeţe etc. Clasele au de asemenea un scope care conţine declaraţii de metode, câmpuri etc. Metodele au la rândul lor un scope unde sunt declaraţi parametrii şi variabilele locale. Scope este şi zona cuprinsă între “{” şi “}”, deoarece o variabilă declarată acolo nu mai poate fi referită după “}”. În momentul construirii AST-ului (în timpul parsingului), de fiecare dată când se identifică un scope, se crează o nouă tabelă de simboluri apoi toate declaraţiile din scope-ul respectiv sunt introduse în tabelă. Tabelele conţin şi o referinţă la tabela imediat superioară (tabela asociată unei metode de exemplu are o referinţă spre tabela asociată clasei).

Cum sunt folosite tabelele de simboluri? Pentru a rezolva o referinţă, de exemplu

int a = 2;
Console.WriteLine(a);

atât pentru apelul Console.WriteLine cât şi pentru variabila a este cerută referinţa de la tabela de simboluri asociată scope-ului (şi metodele şi variabilele sunt simboluri). În exemplul de mai sus, a este rezolvat imediat deoarece există în tabela de simboluri asociată blocului de cod. Ce se întamplă cu apelul, din momente ce Console.WriteLine nu este declarat aici? În caz că tabela nu poate rezolva referinţa, se foloseşte de referinţa spre tabela superioară, cerându-i acesteia să o rezolve. Cererea se propagă în sus până este rezolvată sau se ajunge la un nod care nu are referinţă spre un nod superior (cel mai “de sus”). Dacă nici ultimul nod nu conţine simbolul, înseamnă că referinţa este invalidă.

Desigur, nu toate tabelele de simboluri pot conţine toate tipurile de declaraţii, de exemplu tabela de simboluri asociată unui bloc de cod cuprins între “{” şi “}” nu poate conţine declaraţii de clase dar expune metodele pentru a rezolva o referinţă la o clasă şi trimite pur şi simplu cererea la tabelul superior.

Nodul care stă la bază (care nu mai are referinţă spre o altă tabelă superioară), expune aceleaşi metode de rezolvare a referinţelor dar nu conţine declaraţii. În schimb, acest nod caută simbolurile în assembly-urile externe referite de program. În exemplul de mai sus, Console.WriteLine se află în namespace-ul System din assembly-ul mscorlib.dll. Desigur, compilatorul trebuie să ştie ce assembly-uri externe sunt folosite.

Practic, avem o clasă abstractă care reprezintă o tabelă de simboluri cu metodele pentru a rezolva referinţe:

abstract class Scope
{
  public Scope parent; 
  public abstract Symbol Solve(Reference reference);
}

şi clase derivate din ea care implementează metodele de rezolvare şi conţin declaraţii.

class GlobalScope : Scope
{
  private Assembly[] referencedAssemblies; 

  public GlobalScope(Assembly[] referencedAssemblies)
  {
    parent = null;
    this.referencedAssemblies = referencedAssemblies;
  } 

  public override Symbol Solve(Reference reference)
  {
    // Căutare în referinţe
    ...
  }
}

class SomeScope : Scope
{
  private List<Symbol> symbols;  

  public SomeScope(Scope parentScope)
  {
    parent = parentScope;
  } 

  public void AddSymbol(Symbol symbol)
  {
    // Adăugare simbol
    ...
  }

  public override Symbol Solve(Reference reference)
  {
    // Căutare în symbols
    ...
    if (result != null)
      return result;
    else
      return parent.Solve(reference);
  }
}

Desigur, codul este schematic, dar cam aşa ar trebui să arate tabelele de simboluri care stau, de fapt, la “rădăcina” AST-ului.

Aşa se explică şi vizibilitatea variabilelor, pentru întrebările de la cursul de C gen

int a;

void test(int a)
{
  printf("%d", a);
}

Care a e referit? E referit primul a mergând de jos în sus şi căutând în tabelele de simboluri – aici e argumentul, deoarece acesta aparţine scope-ului asociat funcţiei pe când variabila globală aparţine scope-ului asociat fişierului.

Compilatoare 101

Dacă tot m-am apucat să scriu despre compilatoare, voi scrie câte ceva şi despre lucrurile de bază. Începând cu începutul, compilatorul este un program care “traduce” un limbaj într-un alt limbaj. Asta presupune, în primul rând, analiza unui text (set de comenzi, instrucţiuni etc.) scrise în limbajului sursă şi, în al doilea rând, emiterea textului echivalent în limbajul destinaţie.

De fapt, privit la un nivel înalt, compilatorul este format din două părţi: front-end şi back-end. Front-end-ul se ocupă cu procesarea input-ului, back-end-ul cu emiterea output-ului. Există şi o reprezentare intermediară, independentă de limbajele de intrare şi ieşire, care păstrează doar semantica (înţelesul) input-ului şi din care se generează output-ul.

Concret, front-end-ul analizează input-ul din punct de vedere lexical, sintactic şi semantic. Analiza lexicală presupune descompunerea textului sursă în unităţi atomice numite tokens. Pentru snippet-ul de cod

public class Program { }

token-ii sunt “public”, “class”, “Program”, “{” şi “}”. Totuşi, analiza lexicală nu înseamnă doar “spargerea” textului după spaţii. De exemplu în textul

Console.WriteLine("Hello World!");

“Hello World!” este un singur token. Treburile se complică dacă luăm un string care conţine în caracterul “, cum ar fi "Let's start with \"Hello World!\"", care este, de fapt, tot un singur token. În plus, tot analizatorul lexical “aruncă” comentariile din cod, care nu necesită o procesare ulterioară. Token-ii aceptaţi sunt definiţi riguros, (de obicei cu ajutorul expressilor regulate). Dacă întâlnim un caracter ilegal în codul sursă, de exemplu §, analizatorul lexical semnalizează o eroare. Analizatorul lexical se mai numeşte şi lexer. De fapt, ne putem gândi la procesul efectuat ca la identificarea tuturor cuvintelor dintr-o propoziţie şi verificarea că aceste cuvinte sunt corecte.

Problema este că, din punct de vedere al lexer-ului, următorul snippet este perfect corect:

class } Program public {

Acesta poate fi spart în tokens, chiar dacă nu exprimă o construcţie validă a limbajului. Cuvintele există, chiar dacă formează o propoziţie fără subiect şi fără predicat. Aici vine rândul analizatorului sintactic, care se mai numeşte şi parser. Limbajele de intrare au întotdeauna o gramatică, adică diferite construcţii specifice care sunt acceptate, restul fiind identificate ca greşite. Parserul ştie că “public” este un modificator de vizibilitate care poate să apară doar înaintea anumitor construcţii (declaraţii de clase, de metode etc.) şi nu oriunde (de exemplu în corpul unei metode). Despre cum funcţionează exact un parser nu voi vorbi aici deoarece sunt foarte multe de spus, destul de reţinut că, după analiza sintactică, ajungem la reprezentarea intermediară. Construcţia

public class Program { }

va fi reprezentată intern ca “Declaraţie de clasă, cu numele Program, vizibilitate publică şi fără conţinut“, deci se păstrează sensul, dar token-ii nu mai sunt relevanţi. “{” de exemplu ajută parserul să înţeleagă unde începe conţinutul clasei dar nu are nici un înţeles semantic. Ultima analiză efectuată este cea semantică. De exemplu construcţia

public class A : A { }

este formulată corect din punct de vedere sintactic, doar că nu are sens din punct de vedere logic. O analogie ar fi o propoziţie formulată corect, cu subiect şi predicat, dar care nu are sens. Analiza semantică asigură că input-ul este bun şi din acest punct de vedere, deci se poate traduce în limbajul de output. Aici intră o mulţime de verificări, de exemplu dacă se execută operaţii doar între tipuri compatibile de date, dacă funcţiile întorc întotdeauna un rezultat, dacă nu se folosesc variabile înainte de a fi iniţializate etc. După analiza semantică avem o reprezentare internă a input-ului validat şi aici se încheie treaba front-end-ului.

Back-end-ul preia forma internă şi o transformă în limbajul destinaţie. Mai mult, optimizează codul rezultat. Optimizările sunt de două feluri – independente de limbaj şi dependente de limbaj. Un exemplu de optimizare ar fi constant folding. De exemplu expresia

a = 2 * 3.14 * r

care presupune două operaţii de înmulţire poate fi transformată în

a = 6.28 * r

care presupune o singură operaţie de înmulţire. Compilatorul determină care expresii pot fi calculate static (adică nu depind de variabile a căror valoare este necunoscută în momentul respectiv) şi le înlocuieşte cu rezultatul expresiei. Un alt exemplu ar fi înlocuirea subexpressilor comune. De exemplu

c = a + b * x
d = a + b * y

se poate înlocui cu

t = a + b
c = t * x
d = t * y

reducând din nou numărul de operaţii necesare. Problema optimizării este NP-Completă, adică nu se poate dezvolta un algoritm (deocamdată ) care să garanteze că pentru orice input, output-ul rezultat este optim. După efectuarea acestor optimizări, se emite codul şi se aplică optimizările dependente de limbaj. Un exemplu, în CIL, ar fi instrucţiunea

ldc_i4 0

ldc_i4 pune pe stivă întregul (pe 32 de biţi) specificat. Instrucţiunea în sine are 8 biţi plus întregul specificat 32 de biţi (chiar dacă este 0), deci 40 de biţi. Aceasta poate fi înlocuită cu

ldc_i4_0

instrucţiune care pune întregul 0 pe stivă, aceasta din urmă ocupând doar 8 biţi. Într-adevăr, pe platforma .NET nu sunt necesare multe optimizări dependente de cod deoarece runtime-ul are grijă de asta în momentul rulării.

Aceştia sunt paşii făcuţi de un compilator pentru generarea codului şi, de fiecare dată când apelaţi “build” sau “run”, codul sursă trece prin toate aceste transformări până se transformă în executabil.

CLR, Metadata și IL

Am să încerc să explic, pe scurt, cum funcționează CLR-ul (Common Language Runtime). Se știe că un assembly .NET (executabil sau bibliotecă) conține metadata și instrucțiuni IL – eu cel puțin am auzit asta la toate prezentările de .NET Framework la care am asistat – doar că nu se prea știe cu ce se mănâncă cele două.

Metadata e strâns legată de partea declarativă a aplicațiilor. Orice tip, metodă, variabilă etc. are o intrare în tabelul de metadata. Acestea pot fi descoperite folosind Reflection. De exemplu, clasa MethodInfo, reprezintă metadata asociată unei metode. Pentru a vedea metodele unei clase, de exemplu System.Console, folosind Reflection, avem:

using System;
using System.Reflection;
class Program
{
  public static void Main()
  {
    Type consoleType = Type.GetType("System.Console");

    foreach (MethodInfo methodInfo in ConsoleType.GetMethods())
    {
      Console.WriteLine(methodInfo.Name);
    }
  }
}

Metadata pentru o metodă are informații despre nume, atribute, parametri, return type și multe altele.

IL – Intermediate Language – sunt instrucțiunile executate de runtime. Setul de instrucțiuni este destul de mic (în jur de 200 de instrucțiuni) și lucrează cu o stivă. Orice instrucțiune consumă un număr de elemente de pe stivă și adaugă un număr de elemente pe stivă. Această caracteristică se numește delta-stack. În cazul în care un program încearcă să consume de pe stivă mai multe elemente decât există, sau lasă pe stivă elemente când aceasta ar trebui să fie goală, CLR-ul termină aplicația cu excepția InvalidProgramException. Unele instrucțiuni așteaptă și un metadata token. Un apel de funcție, de exemplu, așteaptă, după instrucțiunea call, token-ul funcției. Token-ul este de fapt adresa din tabela de metadata a funcției. Compilat, codul devine bytecode – instrucțiunile sunt reprezentate de intregi pe 8 sau 16 biți.

Să luăm de exemplu următoarea linie de cod C#:
Console.WriteLine("Hello World");

Tradus în limbaj de asamblare, linia arată astfel:
ldstr "Hello World"
call void [mscorlib]System.Console::WriteLine(string)

ldstr pune pe stivă string-ul ”Hello World”. call folosește token-ul pentru a ști ce funcție să apeleze – în cazul nostru WriteLine care așteaptă un string. WriteLine consumă string-ul de pe stivă și, la ieșire, lasă stiva goală.

Dacă vrem să adăugăm și un ReadLine după, avem
Console.WriteLine("Hello World");
Console.ReadLine();

În limbaj de asamblare, putem încerca:
ldstr "Hello World"
call void [mscorlib]System.Console::WriteLine(string)
call string [mscorlib]System.Console::ReadLine()

Dacă rulăm codul de mai sus ne vom trezi cu un InvalidProgramException. De ce? Păi ReadLine pune pe stivă un string, chiar dacă noi îl folosim doar ca să așteptăm un ENTER. String-ul respectiv rămâne acolo și dezechilibrează stiva. Ce trebuie făcut în astfel de situații? Folosim instrucțiunea pop. Pop ”aruncă” ultimul element de pe stivă.
ldstr "Hello World"
call void [mscorlib]System.Console::WriteLine(string)
call string [mscorlib]System.Console::ReadLine()
pop

O carte foarte bună despre acest subiect este Expert .NET 2.0 IL Assembler (eu lucrez cu .NET 2.0, nu am trecut încă la 3.5 ). E clar că oricine are de gând să scrie un compilator având ca target .NET trebuie să înțeleagă ce este metadata, care sunt instrucțiunile IL și la ce să se aștepte de la ele.

O altă unealtă grozavă este ildasm, care vine cu .NET Framework. ildasm înseamnă IL Disassembler, cu care se pot dezasambla diferite programe și se pot vedea instrucțiunile generate de compilatoare.

Signature matching

O problemă interesantă de care m-am lovit lucrând la compilator e signature matching. Mai exact, determinarea funcției care va fi apelată de o expresie tip function call. Ce înseamnă asta? Păi în .NET avem method overloading, deci același nume de funcție poate, pentru diferiți parametri, să facă diferite lucruri. Funcții extrem de overloaded sunt, de exemplu, Console.WriteLine (19 funcții în una). Când eu compilez System.Console.WriteLine(”Hello World!”), trebuie să știu să aleg din cele 19 funcții pe cea care ia ca parametru un string. Când vorbesc de signature matching mă refer la a decide care dintre n funcții cu același nume trebuie apelată, nu la a găsi funcțiile cu numele respectiv.

Primul lucru pe care îl putem face este să egalăm tipul parametrilor pe care îi pasăm funcției față de tipul așteptat – adică e pasat (string), se așteaptă (string) – avem match. Acesta este exact match – odată întâlnit, nu mai trebuie testate celelalte funcții. Totuși, un algoritm de signature matching trebuie să țină cont și de: typecast implicit, upcast, typecast implicit definit de programator.

Typecast implicit: avem funcția (double), îi facem un apel (20) – unde 20 este integer literal, adică int. Deci trebuie să decidem dacă apelul (int) e OK pentru funcția (double). Tipul int poate fi convertit implicit în double, deci apelul e corect, trebuie doar adăugat typecastul (compilatorul adaugă întotdeauna typecast-urile implicite). Deci vom transforma (20) în ((double)20). Dacă găsim și o semnătură (int), desigur o vom considera mai bună, dar dacă nu, merge și (double).

Upcast: avem funcția (object), îi facem un apel (”Hello world”) – adică (string). Din moment ce string este un object, apelul este corect. Mai mult, dacă avem A derivat din object și B derivat din A, facem un apel (B) și găsim semnăturile (object) și (A), trebuie să luăm funcția cu semnătura (A) - adică cea mai de jos clasă din ierarhie.

Typecast implicit definit de utilizator: în multe limbaje, se pot defini typecast-uri implicite. De exemplu în C#, pentru clasa mea A, pot defini un typecast implicit în int astfel:
class A
{
  public static implicit operator int(A instance)
  {
    return 0;
  }
}

Metoda de mai sus transformă implicit un obiect de tip A în int (în zero, dar asta e neesențial). Deci pentru un apel (A), dacă găsim o funcție (int), există o conversie implicită – ((int)A).

Problema ce poate să apară este apelul ambiguu, adică: nu se poate decide, pentru un apel (int, int), între semnăturile (int, double) și (double, int). La fel și (int, int, int), pentru (int, double, double) și (double, int, int). De observat că, deși a doua funcție este mai apropiată de apel, necesitând transformarea unui singur parametru, apelul rămâne ambiguu. De fapt regula este următoarea:

Pentru fiecare parametru, se verifică transformările în ordinea în care le-am prezentat mai sus (typecast implicit, upcast, typecast implicit definit de utilizator). 

O funcție este preferată față de alte funcții dacă, pentru fiecare parametru, necesită cel mult același număr de transformări ca celelalte funcții și are cel puțin un parametru care necesită mai puține transformări.

Tocmai de aceea nu se poate decide între (int, double, double) și (double, int, int) pentru apelul (int, int, int). Deși a doua funcție necesită mai puține transformări (de fapt nu necesită transformări) pentru parametrii int, necesită o transformare pentru primul parametru, pe care funcția (int, double, double) nu îl necesită.

 Cam asta ar fi filozofia din spatele signature matching-ului.

Old news

Wow, cât timp a trecut și nu am mai blogat nimic… Nici nu știu cu ce să încep. Am terminat cu sesiunea (cu bine, for a change), înca una și gata! Am demisionat de la IMO, unde nu consider că există condiții de muncă pentru developeri profi - de la management aiurea până la codebase a la coding horror și de la nerecunoașterea meritelor până la inexistența unui career path. Aveam de gând să plec după licență dar nu am mai rezistat.

Momentan îmi dedic timpul muncind “din greu” la proiectul de licență, propriul meu compilator având ca target platforma .NET. Deocamdată am reușit să transform

begin
  System.Console.WriteLine("Hello World!");
end

in executabil, deci am trecut de primul milestone

Am fost la “pre-lansarea” Windows Server 2008, SQL Server 2008 si Visual Studio 2008 organizată de RONUA si IT Board Timișoara. O grămadă de chestii interesante. Aștept lansările oficiale luna asta. Nu înțeleg de ce Heroes Happen Here, titlul oficial dat de Microsoft lansării, a fost tradus in România în “Magicienii Prind Viață Aici”. Eu voiam să fiu erou nu magician Magician sunt deja, dar asta e deja altă poveste, făcută de Wizards of the Coast.

Am mai scris un articol mic pentru CodeGuru despre un efect drăguț obținut cu DWM API. De fapt am făcut un wrapper peste aproape tot API-ul in .NET (mai puțin partea de Frame Data). Foarte drăguț Desktop Window Manager…

Deocamdată închei aici și incerc să bloghez mai consistent în viitorul apropiat.