Reflection și obiecte dinamice

În cele ce urmează vreau să prezint un exemplu de lucru cu obiecte dinamice folosind Reflection. Nu ține atât de mult de compilatoare cât de interpretoare, unde, pe baza unor șiruri de caractere, instanțiem obiecte și facem apeluri de metode.

Avem clasa System.Type care încapsulează informații despre tipuri, precum și clasele ConstructorInfo și MethodInfo derivate din MethodBase care încapsulează informații despre constructori, respectiv metode, clase pe care le găsim în namespace-ul System.Reflection.

Pentru a crea de exemplu o instanță a clasei StringBuilder și a concatena două șiruri de caractere, avem următoarele linii de cod:

ConstructorInfo ci = Type.GetType("System.Text.StringBuilder").GetConstructor (Type.EmptyTypes);
object test = ci.Invoke(null);

MethodInfo mi = test.GetType().GetMethod("Append", new Type[] { typeof(string) });
mi.Invoke(test, new object[] { "Hello " });
mi.Invoke(test, new object[] { "World!" });

Console.WriteLine(test);

Se observă că, din punct de vedere al compilatorului de C#, StringBuilder nu apare decât într-un șir de caractere iar obiectul utilizat este de tipul de bază object. Prima instrucțiune întoarce o instanță ConstructorInfo ce corespunde constructorului fără parametri a clasei StringBuilder. Metoda statică Type.GetType returnează instanța System.Type corespunzătoare tipului identificat printr-un șir de caractere. GetConstructor primește ca parametrii un vector de tipuri care reprezintă tipurile argumentelor – în cazul nostru nu avem argumente așa că folosim Type.EmptyTypes care este, de fapt, echivalent cu new Type[0] dar ne scutește de instanțiere.

Invoke apelează metoda cu o listă de argumente, null în cazul nostru și întoarce un obiect (System.Object). Am creat astfel dinamic o instanță StringBuilder.

Similar, luăm instanța System.Type corespunzătoare obiectului – test.GetType() - și apelăm GetMethod care primește un nume de metodă și o listă de argumente. Căutăm metoda Append cu un singur argument de tip string.

Aici, la apelul Invoke trebuie să precizăm și instanța cu care apelăm metoda (obiectul test) și argumentele.

Ultima linie va afișa pe ecran “Hello World!”.

Dacă snippet-ul de mai sus pare încă destul de hard-coded, putem, în locul lui, introduce următoarele:
un dicționar care să rețină instanțele pe care le-am creat, o metodă pentru a construi obiecte și o metodă pentru apeluri astfel:

private static Dictionary objects = new Dictionary();

public static void Create(string name, string type)
{
    ConstructorInfo ci = Type.GetType(type).GetConstructor(Type.EmptyTypes);
    object obj = ci.Invoke(null);

    objects.Add(name, obj);
}

public static void Call(string name, string method, params string[] arguments)
{
    // Aici construim tipurile pe baza argumentelor
    Type[] args = new Type[arguments.Length];

    for (int i = 0; i < args.Length; i++)
    {
        // Doar tipul string
        args[i] = Type.GetType("System.String");
    }

    MethodInfo mi = objects[name].GetType().GetMethod(method, args);
    mi.Invoke(objects[name], arguments);
}

Metoda Create primește ca argumente un nume de variabilă și un tip și apelează constructorul fără parametri al tipului, metoda Call primește numele variabilei, numele metodei și o listă de argumente de tip string. M-am limitat în exemplu la constructori fără parametri și metode ce primesc argumente string nu pentru că Reflection nu mi-ar permite mai mult, doar că, pentru a determina alte tipuri doar pe baza unor string-uri am avea nevoie de un parser (care să determine, de exemplu, că “10.5″ e de tip float).

Acum putem scrie “Hello World!” astfel:
 
static void Main(string[] args)
{
    Create("test", "System.Text.StringBuilder");
    Call("test", "Append", "Hello ");
    Call("test", "Append", "World!");

    Console.WriteLine(objects["test"]);
}

Și nu numai:

static void Main(string[] args)
{
    Create("test", "System.Text.StringBuilder");
    Call("test", "AppendFormat", "{0} {1}!", "Hello", "World");

    Console.WriteLine(objects["test"]);
}

Astfel se crează obiecte și se apelează metode dinamic utilizând Reflection. Desigur, se pot face multe altele – de exemplu putem seta valori la diferite atribute ale obiectelor instanțiate. Un dezavantaj ar fi timpul de execuție – codul compilat (MSIL) rulează mult mai repede decât apelurile Invoke dar pentru un interpretor aceasta ar fi una din posibilitățile de implementare.

Jos stilourile

Astăzi am terminat de făcut ultimele modificări la lucrarea de licenţă. Pentru cine vrea să citească pe scurt despre construirea compilatoarelor sau doar să vadă un model de lucrare de licenţă, îi dau drumul pe internet: Generarea de cod executabil pe platforma .NET

Conţinut: teoria pe scurt (expresii regulate, automate finite, gramatici, parsere, tabele de simboluri, arbori abstracţi de sintaxă, optimizări, generare de cod), despre .NET Framework (platforma, CLR, assembly, metadata, MSIL, Reflection, Reflection.Emit) şi descrierea aplicaţiei cu snippet-uri de cod. Nu e detaliat pentru că ţinta a fost 60 de pagini, nu să scriu propriul Dragon Book. Despre punctele mai interesante pe care le-am identificat în faza de R&D am scris şi aici câteva posturi.

Introducerea şi concluziile sunt abureli că deh, aşa trebuie. Dacă ar fi fost să fiu cinstit, motivaţia a fost să văd cum se face şi dacă pot să fac. Am învăţat că nu e imposibil şi, pentru că a trebuit să peticesc în diferite locuri, am să ştiu data viitoare să fac mai bine. Dezvoltare ulterioară nu va fi – eventual mă apuc de altul de la zero.

Codul sursă îl voi pune pe net undeva, cândva. Deocamdată am observat că WordPress nu mă lasă să fac upload decât la un număr limitat de tipuri de fişiere.

Sper să fie de folos cuiva.

Două tehnici de optimizare

Am să vorbesc puțin despre optimizări, mai exact optimizări independente de mașină. Domeniul optimizărilor este foarte vast și aceste optimizări fac de obicei diferența dintre un compilator bun și unul foarte bun. După cum spuneam într-un post anterior, problema optimizării e NP completă și se utilizează algoritmi care produc cod relativ bun într-un timp rezonabil.

Compilatorul pe care îl dezvolt efectuează doar două astfel de optimizări: constant folding și dead code elimination.

Constant folding presupune înlocuirea expresiilor cu operanzi constanți (expresii ce pot fi calculate în timpul compilării) cu rezultatul lor. De exemplu, expresiei

i = (2 + 3) * 5

îi corespunde în arborele abstract de sintaxă un nod expresie binară cu operatorul * vând copii (operanzi) un nod expresie binară cu operatorul + și un nod constantă întreagă cu valoarea 5. Nodul expresie binară cu operatorul + are copii două noduri constantă întreagă cu valorile 2, respectiv 3.

Parcurgând arborele în postordine, putem procesa nodurile expresie binară cu regula – dacă ambii operanzi sunt constante, înlocuiește nodul expresie binară cu nodul constantă întreagă cu valoarea egală cu rezultatul operației. Astfel, ajungând la nodul cu operatorul +, acesta se înlocuiește cu nodul constantă întreagă având valoarea 5 (2 + 3). Din moment ce arborele e parcurs în postordine, nodul cu operația * este procesat ulterior, iar în momentul în care e procesat, și acesta are operanzi două constante astfel că expresia se reduce la un singur nod constantă întreagă cu valoarea 25.

i = 25

Desigur, operațiile ce se pot evalua la compile-time nu sunt neapărat aritmetice. Pot fi concatenări de string-uri, operații logice, egalități etc.

Pe lângă nodurile expresie binară, compilatorul mai procesează în același mod și nodurile expresie unară (expresii cu un singur operand ca minus unar și negare logică), precum și nodurile typecast. Un nod typecast conține tipul rezultat în urma cast-ului, având un singur copil (operand), ce poate fi o constantă, o expresie etc. Expresiei

(int)10.2

îi corespunde nodul typecast ce conține tipul int și un copil, nodul constantă rațională 10.2. Aceste două noduri pot fi înlocuite cu nodul constantă întreagă rezultat în urma evaluării cast-ului. Astfel, în urma unei singure parcurgeri a arborelui, toate expresiile cu operanzi constanți sunt înlocuite cu câte o singură constantă. În implementarea mea, parcurgerea arborelui nu se face exclusiv pentru optimizare astfel că, în același pas, se execută și alte evaluări. Desigur, această optimizare se poate face și pe alte tipuri de reprezentări intermediare.

Alte optimizări (pe care nu le-am implementat) ce merg mână în mână cu constant folding sunt constant propagation și utilizarea identităților algebrice. Constant propagation presupune identificarea variabilelor a căror valoare, într-un anumit punct, poate fi determinată la compile time. De exemplu, pentru

i = 2
j = i + 5

putem determina că valoarea lui i este 2 în momentul efectuării adunării, astfel că i poate fi înlocuit cu constanta întreagă 2, constant folding reducând expresia la

j = 7

eliminând astfel referirea unei variabile și o operație de adunare. Utilizarea identităților algebrice presupune transformarea expresiilor în expresii echivalente ce presupun mai puține operații, de exemplu pentru

j = 2 + i + 4

unde i nu este constant, nodurile din arborele abstract de sinatxă ar fi un nod expresie binară cu operatorul + având copii un nod constantă întreagă 2 și un nod expresie binară cu operatorul + având copii un nod referire la variabilă (i) și un nod constantă întreagă cu valoarea 4. Din moment ce valoarea lui i nu poate fi determinată, constant propagation nu se aplică iar constant folding nu poate identifica nici o expresie având ambii operanzi constanți. Expresia se poate însă rescrie ca

j = i + 2 + 4

care se poate reduce la

j = i + 6

O altă optimizare implementată este, după cum ziceam, dead code elimination. Cea mai evidentă optimizare a procesului este eliminarea din arbore a propozițiilor ce apar după un return. Evaluarea se face la nivel de bloc de cod, unde un bloc de cod este mulțimea propozițiilor cuprinse între două acolade, între begin și end etc. Trebuie avut în vedere însă că nu orice instrucțiune return din cod va fi întotdeauna executată. Dacă aceasta se găsește de exemplu în cadrul unui loop while, se poate întâmpla să nu se îndeplinească condiția de execuție a loop-ului niciodată, deci codul de după loop va fi executat chiar dacă există un return. Codul din interiorul loop-ului ce urmează instrucțiunea return poate fi însă eliminat. Astfel, parcurgând arborele în postordine, se marchează ca noduri ce ies din funcție instrucțiunile return, nodurile ce reprezintă blocuri ce conțin o astfel de instrucțiune și nodurile ce reprezintă construcții branching (if-else), unde e întâlnită o instrucțiune return pe ambele branch-uri. Când se procesează părinții acestor noduri, dacă părinții sunt noduri bloc (noduri ce au ca și copii propoziții), se elimină din arbore toate nodurile care urmează după un nod propoziție marcat ca nod ce iese din funcție. De exemplu

{
    if (a == b)
        return a;
    else
        return b;
    a = b + 5;
    Console.WriteLine(a);
}

poate fi echivalat cu

{
    if (a == b)
        return a;
    else
        return b;
}

Alte optimizări dead code elimination sunt înlocuirea unei construcții if-else, în cazul în care expresia ce reprezintă condiția poate fi evaluată la compile time, cu ramura if (dacă expresia e evaluată la compile time ca adevărată), cu ramura else (dacă e evaluată ca falsă). În cazul în care expresia e evaluată ca falsă și nu există o ramură else, se elimină din arbore toată construcția. Pentru loop-urile while, unde condiția poate fi evaluată la compile time ca falsă, se elimină din arbore întreg loop-ul. Pentru loop-urile do-while, unde condiția poate fi evaluată la compile time ca falsă, se înlocuiește loop-ul cu corpul său (eliminându-se astfel verificarea condiției) – deoarce se știe sigur că acesta va fi executat o singură dată.

do
{
    a = a + 1;
} while (0);

devine

a = a + 1;

Există multe alte optimizări, cum ar fi common subexpression elimination, loop invariant code motion, function inlining etc. despre care nu voi vorbi aici. Un punct bun de start este Dragon Book.

Îmi cer scuze că am prezentat structurile arborescente în cuvinte și nu cu desene dar în ultimele zile am desenat o mulțime de arbori pentru lucrarea de licență și mi-a ajuns

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!

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.