Reflection și obiecte dinamice

31 May 2008

Î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.


DWM Managed API

25 May 2008

Desktop Window Manager was introduced with Windows Vista and it enables the Aero GUI. The library that exposes the DWM functionality is dwmapi.dll. A while ago, I wrote a C# wrapper over the library to enable WinForms applications to use the new user interface capabilities. The DWM Managed API covers most of the DWM functionality, except the frame timing API (which most developers shouldn’t need anyway).

Feel free to download, use, modify and extend it.

You can find more information on DWM (the Win32 API) here: http://msdn.microsoft.com/en-us/library/aa969540(VS.85).aspx


Stocare în nori

23 May 2008

Că tot mă plângeam ieri de limitarea impusă de WordPress la tipurile de fişiere pe care le pot încărca aici – aflu azi de pe blogul lui Tudor Galos de Windows Live SkyDrive pentru România.

5 GB storage în cloud. Trebuie doar un Live ID. Bestial. http://skydrive.live.com/

 


Jos stilourile

22 May 2008

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.


The Daily WTF

21 May 2008

M-a rugat un prieten sâmbătă să îi explic câte ceva despre diagrame UML pentru că are un proiect pentru școală și nu a prea înțeles explicațiile profesoarei. Până aici totul bine. Îl rog să îmi arate ce a făcut și îmi prezintă un class diagram pe care l-a desenat profesoara. Îmi pare foarte foarte rău că nu am diagrama, aș fi vrut să o postez (și să o trimit la www.thedailywtf.com), din păcate prietenul a avut ceva probleme cu calculatorul și a șters-o când l-a formatat. Ați mai văzut până acum un class diagram care să arate ca o pânză de păianjen? Am să încerc să descriu. Imaginați-vă vreo 10 clase dispuse într-un cerc – da, cerc - aproape toate clasele având asociații directe între ele. Nici vorbă de agregare, moștenire… Doar asociații directe după următoarele reguli: dacă o clasă moștenește altă clasă, sunt asociate direct. Dacă o clasă comunică cu o altă clasă, sunt asociate direct. Adică nu clasă, obiect… nu știu exact pentru că de obicei asta nu se reprezintă pe class diagram. Un alt element estetic al diagramei era faptul că toate asociațiile trasate erau reprezentate printr-o linie dreaptă, diagonală, nu printr-un conector în unghiuri drepte, cum fac amatorii. Așa o fi, cine sunt eu să contrazic un Conferențiar Doctor?

Aplicația era o aplicație relativ simplă ce presupunea vreo 3 tabele și vreo 2 relații între ele. Prietenul îmi spune că i-a propus doamnei să creeze o bază de date pentru asta. Greșit! Nu așa se face. Doamna profesoară sugerează utilizarea a trei baze de date, câte una pentru fiecare tip de set de date care normal ar fi reprezentat printr-un tabel. OK, se pune întrebarea – și atunci cum reprezentăm relațiile? Soluția e simplă – se folosește o clasă pentru a încărca toate informațiile din baza de date, pardon, bazele de date, în memorie la pornirea aplicației și relațiile sunt stabilite în codul sursă al aplicației. WTF!?

Și acum punchline-ul – materia este inginerie software. Pe pagina facultății, doamna profesoară are trecute la domenii de interes arhitecturi software și modelare. Am văzut că a scris și o carte despre asta.

Ce pot să zic? Mă inspiră. Acum știu că, dacă vreau, pot să scriu o carte despre istoria artei orientale sau să îmi dau doctoratul în biologie marină sau să țin un curs la Facultatea de Filosofie.


Două tehnici de optimizare

13 May 2008

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 :)


Ce am mai făcut în ultima vreme

12 May 2008

Fac un mic update personal, pentru cine interesează viața mea. În primul și cel mai important rând, m-am căsătorit. La exact un an după ce am cerut-o în căsătorie pe cea mai frumoasă, inteligentă, amuzantă, dulce persoană din lume. A fost una din cele mai frumoase zile din viața mea.

Cu facultatea am ajuns pe ultima sută de metri – mai am 2 examene și licența – abia aștept să termin. Am pierdut 16 ani din viață în minunatul sistem educațional din România, bine că închei curând.

Compilatorul pe care îl dezvolt pentru licență a ajuns în sfârșit ieri la stadiul de code complete, după ce câteva săptămâni bune nu m-am mai atins de el. Mă lăudam că l-am terminat de mai demult dar mai aveam de adăugat câteva elemente neinteresante (interpretarea parametrilor de la linia de comandă, help la linia de comandă etc.). Ieri am implementat și acestea, plus două optimizări (dead code elimination și constant folding). Acum a ajuns la stadiul final. Recunosc că ar fi necesar puțin refactoring dar nu vreau să-mi mai bat capul deocamdată. M-am apucat și de scris lucrarea de licență, lucru destul de complicat – prefer să scriu specificații tehnice și să desenez UML-uri decât să scriu definiții și să desenez arbori de sintaxă. Oricum, dacă reușesc să mențin ritmul am terminat și cu asta într-o săptămână.

M-am lăsat de fumat. Aproape o săptămână, pe urmă m-am apucat din nou. Încă de când rezolvam probleme la pregătire pentru olimpiada de informatică din liceu, soluțiile le găseam plecând de la calculator, fumând o țigară și gândindu-mă. La fel cu problemele de la Imagine Cup, de fapt, cu toate probleme. Cât timp nu am mai fumat am fost mult prea agitat și nu m-am mai putut concentra deloc. Prefer să trăiesc mai puțin la capacitate intelectuală maximă.

M-am jucat puțin în vacanță și cu XNA. Un prieten pasionat de grafică pe calculator m-a făcut curios așa că am studiat și eu câteva elemente de bază, doar că domeniul nu a reușit să mă acapareze. Totuși, din punct de veder obiectiv, XNA este ușor de folosit, elegant și inovator. Dacă vreți să-l încercați, începeți de la http://creators.xna.com/. Am ales XNA deoarece e mult mai ușor de folosit decât lucrul direct cu OpenGL sau DirectX.

Cam atât deocamdată. Urmează un post tehnic din seria compiler construction despre optimizări.