de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a...

45

Transcript of de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a...

Page 1: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Universitatea "Politehnica" Bucure�stiFacultatea de Automatic�a �si Calculatoare

Proiect de diplom�a

Utilizarea continu�arilor �n compilareaprogramelor Scheme

autor: Zoran Constantinescu

coordonator: prof. Irina Athanasiu

Iunie 1997

Page 2: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Cuprins

2

Page 3: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Capitolul 1

Introducere

Lucrarea face parte dintr-un proiect mai mare, al c�arui subiect este studierea posi-

bilit�at�ilor de realizare a unui compilator al limbajului Scheme. Codul generat de com-

pilator a fost ales a � byte-code pentru ma�sina virtual�a Java.

Scheme este un limbaj de programare orientat funct�ional, apropiat de limbajele

de programare funct�ionale "moderne". El este un limbaj �nrudit cu Lisp, �nsa �n

comparat�ie cu acesta este mult mai simplu. Pe l�ng�a aceasta are meritul sust�inerii

prin funct�ii prede�nite a unor tehnici avansate de programare, cum ar �: �ntreruperea

�si continuarea proceselor de calcul, evaluarea lene�s�a a expresiilor - "lazy evaluation".

Scheme implementeaz�a mecanismul de gestiune automat�a a memoriei. Programatorul

nu se mai ocup�a de alocarea �si eliberarea de memorie pentru obiectele create �n timpul

execut�iei programului. Alocarea trebuie f�acut�a explicit, dar este treaba mediului de

execut�ie unde se va aloca obiectul, programatorul neav�nd nici un control asupra aces-

tei decizii. Eliberarea memoriei nu mai trebuie f�acut�a de loc, o procedur�a de colectare

a memoriei disponibile (garbage collector) va colecta toate obiectele ce nu mai pot �

referite prin program.

Codul rezultat �n urma compilarii a fost ales a � byte-code pentru ma�sina virtual�a

Java (Java Virtual Machine - JVM). Motivul alegerii este portabilitatea oferit�a de

Java la nivel de ��sier cu cont�inut executabil, precum �si faptul c�a �si ma�sina virtual�a

Java implementeaz�a mecanismul de garbage-collection. Astfel rularea unui program

scris pentru aceast�a ma�sin�a virtual�a este posibil�a pe orice sistem de operare pe care

poate rula un emulator al unei astfel de ma�sini virtuale. Codul generat de compilator,

�mpreun�a cu biblioteca de clase ce implementeaz�a primitivele de baz�a Scheme va putea

3

Page 4: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

� executat pe orice implementare a unei ma�sini virtuale Java.

Implement�arile de limbaj Scheme trebuie s�a suporte apelurile recursive. Aceasta

�nseamn�a c�a limbajul trebuie s�a poat�a efectua calcule iterative �n spat�iu de memorie

constant, chiar dac�a acestea s�nt descrise sintactic �n mod recursiv. In acest fel, calculele

iterative pot � descrise doar prin apeluri normale de proceduri, f�ar�a a folosi construct�ii

speciale, speci�ce limbajelor de programare clasice. Di�cultatea �n implementarea pro-

cedurilor recursive const�a �n faptul c�a, atunci c�nd este apelat�a o astfel de procedur�a,

este nevoie s�a p�astr�am operat�iile care mai trebuiesc efectuate dup�a �ntoarcerea din

procedura recursiv�a. Aceast�a informat�ie, care este folosit�a pentru controlul viitor al

calculului, se nume�ste informat�ie de control. O metod�a pentru implementarea recur-

sivit�at�ii este s�a facem explicit�a informat�ia de control. Procedurile recursive s�nt scrise

�n a�sa fel �nc�t ele nu �ntorc niciodat�a valori direct, �n schimb �ns�a paseaz�a aceste valori

unui argument care este o procedur�a. Aceste argumente speciale s�nt numite continu�ari.

Aceast�a tehnic�a este numit�a tranmitere de continu�ari CPS ("Continuation Passing

Style"). Un alt avantaj al utiliz�arii continu�arilor este posibilitatea scrierii de proceduri

care pot �ntoarce ca rezultat mai multe valori, prin pasarea lor unei continu�ari care

are mai multe argumenta. Expresiile Scheme s�nt transformate �n acest limbaj cu

transmitere de continu�ari.

Scopul proiectului curent este proiectarea �si implementarea unui generator de "byte-

code" pentru ma�sina virtual�a Java, pornind de la forma intermediar�a CPS a pro-

gramelor Scheme, simpli�cate �n prealabil.

4

Page 5: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Capitolul 2

Generalit�at�i despre compilarea

limbajului Scheme

La prima vedere, deoarece sintaxa limbajul Scheme este �n form�a pre�xat, cu paranteze,

implementarea unui compilator pentru ma�sina virtual�a Java de tip stiv�a ar � foarte

simpl�a. Scheme-ul �ns�a are o mult�ime de facilit�at�i care nu pot � implemetate printr-o

simpl�a translatare �n byte-code pentru ma�sina virtual�a.

Una din problemele implement�arii limbajului Scheme este necesitatea elimin�arii

totale a recursivit�at�i. Acest lucru �nseamn�a c�a o procedur�a Scheme recursiv�a va putea

folosi un spat�iu de memorie constant pentru efectuarea unui calcul. In limbajele cla-

sice, ca de exmplu C, Pascal, �n cazul apelului unei proceduri recursive se salveaz�a pe

stiv�a parametrii actuali, precum �si adresa de �toarcere �n subrutina apelant�a, urm�nd

ca refacerea stivei s�a se fac�a doar dup�a terminarea apelului. In acest fel se poate ajunge

destul de repede la o dep�a�sire de stiv�a. Solut�ia �n cazul limbajului Scheme este trans-

formarea programului �ntr-o form�a intermediar�a folosind ca limbaj intermediar limba-

jul cu transmitere de continu�ari CPS. O alt�a solut�ie pentru eliminarea recursivit�at�ii

ar putea � ca procedura apelat�a (recursiv�a) s�a refac�a part�ial stiva, prin �stergerea din

stiv�a a parametrilor actuali de apel a procedurii; �n acest caz trebuie totu�si p�astrat�a

adresa de revenire din funct�ie �n procedura apelant�a. In cazul implement�arii noastre a

fost aleas�a prima variant�a, folosirea limbajului intermediar CPS.

Un alt motiv pentru aceast�a alegere este legat tot de limbajul Scheme. Acesta

permite creare �si implicit folosirea de c�atre programator a continu�arilor explicite. Cu

ajutorul funct�iei call-with-current-continuation (call/cc), procesul de calcul curent poate

5

Page 6: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

� �trerupt �si salvat, put�nd � reluat apoi mai t�rziu. Cu ajutorul acestui mecanism,

�n limbajul Scheme pot � implementate: mecanismul de tratare a except�iilor, uti-

lizarea thread-urilor, folosirea back-tracking-ului. Printr-o simpl�a translatare a limbaju-

lui, acest mecanism nu ar putea � implementat. In schimb �nsa, prin folosirea limbajului

intermediar cu transmitere de continu�ari, implementarea continu�arilor devine un lucru

cert.

2.1 Arhitectura compilatorului

Compilatorul va realiza translatarea programului sursa Scheme �n program executabil

Java prin intermediul mai multor pa�si:

Scheme limbaj CPSlimbaj masina Java in fisier binar

transformare intransformare CPS

limbajmasina

Javabyte-code

simplificare + asamblare

Figura 2-1: Arhitectura compilatorului.

� transformarea limbajului Scheme �ntr-un limbaj Scheme simpli�cat, �n care s�nt

folosite doar comenzile de baz�a ale Scheme; toate constantele au tipurile speci�-

cate; toate variabilele distincte au nume diferite. Aceast�a transformare are rolul

de a simpli�ca programul pentru transformarea CPS.

� transformarea limbajului simpli�cat Scheme �ntr limbajul cu transmitere de con-

tinu�ari - CPS (Continuation Passing Style). Acest limbaj va � descris �n sectiunea

urm�atoare.

� transformarea programului din limbajul CPS obtinut, �n cod "de asamblare" pen-

tru ma�sina virtuala Java. Am ales varianta transform�arii �n limbaj de asamblare

�si nu direct �n ��sier binar .class deoarece �n acesta din urm�a exist�a ni�ste structuri

de date destul de complexe, �si ar � �ngreunat scrierea acestui modul. Am l�aat

astfel �n grija asamblorului crearea acestor structuri de date.

� transformarea codului rezultat �n byte-code de Java, respectiv crearea de ��siere

.class Java, cu ajutorul unui asamblor de byte-code Java. Pe l�ng�a crearea struc-

turilor de date necesare, acest modul face �si conversia mnemonicelor instruct�iunilor

�n byte-code-urile corespunz�atoare.

6

Page 7: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

2.2 Simpli�carea limbajului Scheme

Primul pas const�a �n aducerea programului Scheme la o form�a simpli�cat�a �n care

s�a apar�a c�t mai put�ine comenzi Scheme. Acest lucru este realizat prin transform�ari

simple la nivelul programului surs�a Scheme, rezultatul �ind tot un program Scheme,

dar ceva mai complex, �ns�a care folose�ste mai put�ine comenzi. De exemplu secvent�a:

(cond

(test_1 consec_1)

(test_2 consec_2)

...

(test_n consec_n)

(else altern. ))

va deveni �n urma simpli�c�arii:

(if test_1

consec_1

...

(if test_n

consec_n

alternat) ... )

In mod asem�an�ator se pot transforma �si alte construct�ii, limbajul Scheme simpli-

�cat rezultat av�nd doar c�teva comenzi elementare: define, if, quote, lambda, set!,

evaluare.

2.3 Limbajul intermediar CPS

Transformarea �n forma CPS are drept scop aducerea expresiilor �ntr-o form�a denumit�a

tail-form. In aceast�a form�a, funct�iile nu mai �ntorc nici un rezultat, �n schimb �ns�a

vor transmite acest rezultat unuia din parametri. Acest parametru este de fapt o

continuare. Fiecare funct�ie va prelua un num�ar de parametri, va efectua calcule, iar

rezultatul �l va pasa mai departe unei continu�ari. Fiecare funct�ie va deveni de fapt o

astfel de continuare, care va primi o valoare �si va transmite mai departe noul rezultat.

Avantajul fat��a de metoda clasic�a de apel, �n care se depune pe stiv�a adresa de �ntoarcere

din funct�ia apelat�a, este c�a nu mai avem nevoie de aceast�a adres�a. Pur �si simplu

transmitem o continuare funct�iei apelate, care la r�ndul ei va transmite rezultatul ei

7

Page 8: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

continu�arii. In felul acesta nu mai apare problema posibilit�at�iitermin�arii stivei �n urma

unor apeluri recursive repetate.

S�a consider�am ca exemplu urm�atoarea expresie Scheme:

(define list-append

(lambda (list a list b)

(if (null? list b)

list a

(cons (car list b) (list-append list a (cdr list b))))))

Aceast�a funct�ie prime�ste ca argumente dou�a liste, list a �si list b �si �ntoarce ca rezultato nou�a list�a obt�inut�a prin concatenarea celor dou�a.

(list-append '(1 2 3) '(x y z)) =) (1 2 3 x y z)

Forma echivalent�a CPS este urm�atoarea:

(define list-append-cps

(lambda (list a list b k)

(if (null? list b)

(k list a)

(list-append-cps list a (cdr list b)

(lambda (v)

(k (cons (car list b) v)))))))

Se observ�a c�a �n forma CPS, funct�ia prime�ste un nou argument k, care reprezint�a

de fapt o continuare. In acest exemplu, funct�iile null?, car �si cdr s�nt considerate

expresii simple, ceea ce �nseamn�a c�a evaluarea lor pot genera apeluri recursive. La

apelul unei astfel de funct�ii, pur �si simplu se �ntoarce rezultatul, f�ar�a a apela alte

funct�ii. Pe ramura "else" a formei CPS se observ�a c�a este creat�a o nou�a continuare, cu

ajutorul construct�iei lambda.

Pentru apelul noii forme CPS, vom avea nevoie de o nou�a construct�ie �n care s�acreem continuarea init�ial�a:

(define list-append

(lambda (list a list b)

(list-append-cps list a list b (lambda (v) v))))

8

Page 9: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Capitolul 3

Ma�sina Virtual�a Java

Ma�sina Virtual�a Java (JVM) este o ma�sin�a virtual�a implementat�a prin emulare software

pe o ma�sin�a real�a. Codul executabil pentru ma�sina virtual�a se a �a stocat �n ��siere te

tip '.class', �ecare astfel de ��sier cont�in�nd codul pentru o singur�a clas�a Java.

Datorit�a formatului compact �si e�cient al byte-code-ului exist�a implement�ari de

interpretoare pentru ma�sina virtual�a Java pentru diverse platforme �si sisteme de op-

erare. Exist�a posibilitatea realiz�a unor compilatoare �n timp real, care s�a transforme

byte-code-ul metodelor �n instruct�iuni cod ma�sin�a pentru un anumit tip de procesor pe

m�aura execut�iei metodelor respective.

Recent au ap�arut chip-uri care excut�a direct setul de instruct�iuni al ma�sinii virtuale,

elimin�nd complet necesitatea unui interpretor sau a unui complilator JIT (Just In

Time compiler). Un astfel de procesor este picoJava de la Sun Microsystems, cu o

arhitectur�a simpl�a de tip RISC, optimizat pentru vitez�a �si care funct�ioneaz�a 100 %

conform speci�cat�iilor JVM.

3.1 Arhitectura JVM

Ma�sina virtual�a este organizat�a ca o ma�sin�a stiv�a. Un emulator al unei astfel de

ma�sini cite�ste instruct�iunile din zona de cod, pe care le execut�a. In urma execut�arii

instruct�iunilor, se opereaz�a asupra stivei. Tipurile de date folosite de ma�sina virtual�a

s�nt tipurile de baz�a ale limbajului Java. Aceste tipuri s�nt: byte, short, int, long, oat,

double, char, object si returnAddress (v. tabel ??).

Aproape toate veri�c�arile pentru tipurile de baza (prima parte a tabelului) s�nt

9

Page 10: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

tip lungime descriere

byte 1-byte �ntreg cu semn �n complement fat��a de 2

short 2-byte �ntreg cu semn �n complement fat��a de 2

int 4-byte �ntreg cu semn �n complement fat��a de 2

long 8-byte �ntreg cu semn �n complement fat��a de 2

oat 4-byte real IEEE 754 simpl�a precizie

double 8-byte real IEEE 754 dubl�a precizie

char 2-byte caracter Unicode

object 4-byte referint��a la un obiect Java

returnAddress 4-byte adres�a de �ntoarcere pt. instruct�iuni jsr,ret

Tabela 3.1: Tipuri de baza Java

efectuate �n timpul compil�arii. Instruct�iunile byte-code care opereaz�a cu tipurile de

baz�a indic�a pe ling�a operat�ie �si tipurile operanzilor. De exemplu: instruct�iunea imul

va �nmult�i dou�a numere de tip integer. Nu exist�a instruct�iuni speci�ce pentru tipul

boolean, folosindu-se � loc instruct�iunile tipului integer. Pentru array-uri de tip boolean

se folosesc cele de tip byte.

Ma�sina virtual�a Java are patru registre, care s�nt folosit�i doar pentru controlul

execut�iei �si al oper�arii stivei. Ei nu s�nt folosit�i pentru transferul parametrilor sau a

valorilor de revenire, pentru aceasta utiliz�du-se stiva. Cei patru regi�strii s�nt descri�si �n

tabelul ??. Intr�arile stivei precum �si dimensiunea regi�strilor s�nt de 32 bit�i. Operanzii

de dimensiune mai mare (8 octet�i - long, double) ocup�a dou�a cuvinte consecutive.

Stiva este folosit�a pentru transmiterea parametrilor actuali metodelor �si pentru valorile

�ntoarse de acestea.

Obiectele (instant�ele de clase) create de programele Java s�nt alocate �n heap-ul

sistemului. Aceasta este zona care este supus�a colect�arii de memorie.

Fiecare metod�a a unei clase Java folose�ste un num�ar �x de variabile locale, adresate

ca ofset fat��a de registrul vars. Toate variabilele locale au dimensiunea de 32 bit�i.

Intregii �si realii dubl�a precizie se consider�a c�a ocup�a dou�a variabile locale consecutive.

Stiva operanzilor este de 32 bit�i. Aceasta este folosit�a pentru transmiterea parametrilor

metodelor �si primirea rezultatelor acestora. Pe l�ng�a aceasta, stiva este folosit�a pentru

furnizarea parametrilor operat�iilor elementare �si pentru salvarea rezultatelor operat�iilor.

O instruct�iune pentru JVM este format�a dintr-un octet, opcode speci�c�nd operat�ia,

urmat de zero sau mai mult�i operanzi, reprezent�nd parametrii sau datele utilizate de

10

Page 11: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

registru descriere

pc adresa urm�atoarei instruct�iuni

vars �nceputul zonei de variabile locale

optop v�rful stivei de operanzi

frame �nceputul �nregistr�arii de activare

Tabela 3.2: Regi�strii JVM

operat�ie.

3.2 Descrierea ��sierelor .class

Fiecare ��sier .class cont�ine codul binar compilat al unei clase Java sau a unei interfet�e

Java. Acest ��sier cont�ine toate datele despre o clas�a sau o interfat��a. Fi�sierul este privit

ca un stream de octet�i, elementele de 16, respectiv 32 bit�i �ind considerate ca grupuri

de 2, respectiv 4 octet�i a�sezat�i �n format big-endian (cu octetul semni�cativ primul).

In interiorul unui astfel de ��sier se a �a byte-code-uri, adic�a implement�ari pentru �ecare

metod�a a clasei, scrise cu setul de instruct�iuni a ma�sinii virtuale.

3.2.1 Formatul ��sierului

Formatul unui ��sier .class este urm�atorul:

ClassFile {

u4 magic;

u2 minor_version;

u2 major_version;

u2 constant_pool_count;

cp_info constant_pool[constant_pool_count - 1];

u2 access_flags;

u2 this_class;

u2 super_class;

u2 interfaces_count;

u2 interfaces[interfaces_count];

u2 fields_count;

field_info fields[fields_count];

u2 methods_count;

method_info methods[methods_count];

u2 attributes_count;

attribute_info attributes[attribute_count];

}

11

Page 12: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Semni�cat�iile c�mpurilor ��sierului s�nt urm�atoarele:

� magic - semn�atura ��sierului .class; trebuie s�a aib�a valoarea 0xCAFEBABE.

� minor version, major version - speci�c�a versiunea conpilatorului care a gen-

erat ��sierul .class respectiv. Valoarea curent�a pentrumajor version este 45, iar

pentru minor version este 3.

� constant pool count - indic�a num�arul de intr�ari �n constant pool, o tabel�a

cu toate constantele folosite �n ��sierul .class respectiv.

� constant pool - tabela cu toate constantele folosite �n ��sier. Acestea s�nt valori

ale constantelor de tip String, nume de alte clase, denumiri de metode, constante

numerice �si alte astfel de constante folosite �n structura clasei sau de byte-code.

Prima intrare din tabel�a, constant pool[0] este �totdeauna nefolosit�a de c�atre

compilator, put�nd � folosit�a de c�atre implementarea ma�sinii virtuale pentru orice

scop. Fiecare intrare din tabel�a este o intrare de lungime variabil�a, formatul

�ec�areia �ind determinat pe baza primului octet, denumit "tag byte".

� access ag - cont�ine o constant�a pentru accesul la clas�a, conform tabelului ??:

Denumire ag Valoare Folosire Descriere

ACC PUBLIC 0x0001 CMV Vizibil pentru oricine

ACC PRIVATE 0x0002 .MV Vizibil doar pentru clasa de�nit�a

ACC PROTECTED 0x0004 .MV Vizibil subclaselor

ACC STATIC 0x0008 .MV Variabila sau metoda este static�a

ACC FINAL 0x0010 CMV Nu permite alte subclase, suprascriere

sau atribuire dup�a init�ializare

ACC SYNCHRONIZED 0x0020 .M. Se folose�ste mecanismul de monitoare

(lock) la acces

ACC VOLATILE 0x0040 ..V Nu poate � optimizat folosind cache-ul

ACC TRANSIENT 0x0080 ..V Nu poate � scris sau citit de un

manager de obiecte persistente

ACC NATIVE 0x0100 .M. Implementat �n alt limbaj, nu Java

ACC INTERFACE 0x0200 C.. Este o clas�a interfat��a

ACC ABSTRACT 0x0400 CM. Nu este speci�cat corpul clasei/metodei

Tabela 3.3: Modi�catori de acces

unde C=clas�a, M=metod�a, V=variabil�a.

12

Page 13: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

� this class - este un index in constant pool, iar intrarea din tabel trebuie s�a �e

de tipul CONSTANT class, reprezent�nd denumirea clasei.

� super class - asem�an�ator lui this class, dar este denumirea clasei imediat su-

perioare; dac�a indexul este zero, atunci clasa este implicit java.lang.Object,

neav�nd clas�a superioar�a.

� interfaces count - reprezint�a num�arul de interfet�e pe care clasa respectiv�a le

implementeaz�a.

� interfaces - este o tabel�a, �ecare element al ei �ind un index �n constant pool,

care trebuie s�a �e de tipul CONSTANT class, reprezent�nd denumirea interfet�ei

implementate.

� �elds count - reprezint�a num�arul de c�mpuri implementate de explicit de clas�a,

f�ar�a a se lua �n calcul cele mo�stenite.

� �elds - �ecare valoare din aceast�a tabel�a reprezint�a o descriere a unui c�mp din

clas�a: denumirea, tipul �si eventualele atribute.

� methods count - reprezint�a num�arul de metode, statice �si dinamice, de�nite de

aceast�a clas�a.

� methods - �ecare valoare reprezint�a descrierea unei metode de�nite explicit de

aceast�a clas�a: denumirea, signatura (tipul parametrilor �si a valorii �ntoarse),

eventualele atribute. Metodele mo�stenite de clas�a nu se a �a �n aceast�a tabel�a.

� attributes count - indic�a num�arul de atribute suplimentare ale clasei.

� attributes - �ecare intrare �n tabel�a reprezint�a un atribut al clasei. Un astfel

de atribut este "Source", care speci�c�a numele ��sierului surs�a din care a fost

compilat�a clasa.

3.2.2 Structuri de date

O signatur�a este un �sir de caractere (string) care descrie tipul unei metode, al unui

c�mp sau al elementelor unui tablou (array). O signatur�a este reprezentat�a ca un �sir

de octet�i conform regululilor de mai jos:

13

Page 14: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

� signatura unui c�mp descrie tipul unui argument al unei funct�ii sau al unei

variabile:

<sign_cimp> ::= <tip_cimp>;

� signatura unei metode descrie tipul argumentelor funct�iei �si tipul rezultatului:

<sign_metoda> ::= (<sign_argumente>)<sign_rezultat>;

unde

<sign_argumente> ::= <sign_argument>*;

<sign_argument> ::= <tip_cimp>;

<sign_rezultat> ::= <tip_cimp> | V;

<tip_cimp> ::= <tip_baza> | <tip_obiect> | <tip_tablou>;

<tip_baza> ::= B | C | D | F | I | J | S | Z;

<tip_obiect> ::= L<nume_clasa>;

<tip_tablou> ::= [<dimens_optionala>]<tip_cimp>;

<dimens_optionala> ::= [0-9]*;

iar semni�cat�ia tipurilor de baz�a este urm�atoarea:

Caracter Tip Java Descriere

B byte octet cu semn

C char caracter

D double real IEEE dubl�a precizie

F oat real IEEE simpl�a precizie

I int �ntreg

J long �ntreg dubl�a precizie

S short short

Z boolean adev�arat sau fals

Lnume clasa un obiect de tipul clas�a speci�cat

tip cimp tablou

Tabela 3.4: Tipuri de baz�a

3.3 Setul de instruct�iuni

Lungimea instruct�iunilor ma�sinii virtuale Java este variabil�a. Exist�a instruct�iuni f�ar�a

nici un parametru �si instruct�iuni cu unul, doi sau mai mult�i parametri. Formatul unei

instruct�iuni este urm�atorul:

14

Page 15: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

hcod-operat�iei operand 1 operand 2 ...

lungimea codului operat�iei �ind de un octet (de aici vine �si denumirea de byte-code).

Exist�a urm�atoarele grupe de instruct�iuni:

� instruct�iuni pentru salvarea constantelor pe stiv�a: bipush, sipush, ldc1, ldc2,

ldcw, aconst null iconst m1, iconst hni, lconst hli, fconst hdi, dconst hdi;

� instruct�iuni pentru �nc�arcarea cont�inutului variabilelor pe stiv�a: iload, iload hni,

lload, lload hni, oad, oad hni, dload, dload hni, aload, aload hni;

� instruct�iuni pentru �nc�arcarea valorilor de pe stiv�a �n variabile: istore, iload hni,

lstore, lload hni, fstore, oad hni, dstore, dload hni, astore, aload hni,

iinc;

� instruct�iuni de lucru cu tablouri de obiecte (array): newarray, anewarray,

multianewarray, arraylength, iaload, laload, faload, daload, aaload,

baload, caload, saload, istore, lstore, fstore, dstore, astore, bstore,

cstore, sstore;

� instruct�iuni pentru lucrul cu stiva: nop, pop, pop2, dup, dup2, dup x1,

dup2 x1, dup x2, dup2 x2, swap;

� instruct�iuni aritmetice: iadd, ladd, fadd, dadd, isub, lsub, fsub, dsub,

imul, lmul, fmul, dmul, idiv, ldiv, fdiv, ddiv, irem, lrem, frem, drem,

ineg, lneg, fneg, dneg;

� instruct�iuni logice: ishl, ishr, iushr, lshl, lshr, lushr, iand, ior, ixor, land,

lor, lxor;

� instruct�iuni de conversie de tipuri: i2l, i2f, i2d, l2i, l2f, l2d, f2i, f2l, f2d, d2i,

d2l, d2f, int2byte, int2char, int2short;

� instruct�iuni pentru �ntoarcerea din funct�ii: ireturn, lreturn, freturn, dreturn,

areturn, return, breakpoint;

� instruct�iuni pentru transferul controlului: ifeq, ifnull, i t, i e, ifne, ifnon-

null, ifgt, ifge, if icmpeq, if icmpne, if icmplt, if icmple, if icmpgt,

if icmpge, lcmp, fcmpl, fcmpg, dcmpl, dcmpg, if acmpeq, if acmpne,

goto, jsr, ret, goto w, jsr w, ret w;

� instruct�iuni de salt bazate pe tabele de valori: tableswitch, lookupswitch;

� instruct�iuni de lucru cu c�mpurile obiectelor: put�eld, putstatic, get�eld,

getstatic;

� instruct�iuni de apel a metodelor obiectelor: invokevirtual, invokenonvirtual,

invokestatic, invokenonstatic;

� instruct�iuni pentru tratarea except�iilor: athrow;

� instruct�iuni diverse pentru lucrul cu obiecte: new, checkcast, instanceof;

� monitoare: monitorenter, monitorexit;

15

Page 16: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Capitolul 4

Generarea claselor Java pe baza

limbajului intermediar CPS

4.1 Structura programului compilat

JScmBoolean

JScmChar

JScmNumber

JScmPair

JScmString

JScmList

JScmSymbol

JScmVector

JScmLambda

JScmUnspec

Comparable

Object

Printable

implements

JScmContext

Tipuri de date

-> byte-codeTransformare CPS

Functii noi definite

JScmUser

Expresii definite in program

JScmObject

JScmTopLevel

Proceduri de baza Scheme

JScmFunc

Context global

Contexte locale

Figura 4-1: Ierarhia complet�a de clase.

Programul adus la forma intermediar�a �n limbajul CPS este transformat, a�sa cum

se va vedea mai jos, �ntr-o clas�a JScmUser. Aceast�a clas�a cont�ine toate expresiile �si

16

Page 17: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

de�nit�iile de funct�ii care apar �n programulCPS. Clasa rezultat�a va creea, �n funct�ie de

program, un num�a de obiecte. Unele dintre aceste obiecte s�nt create static, la pornirea

programului, altele s�nt create dinamic, pe parcursul execut�iei programului, �n funct�ie

de instruct�iunile executate. Aceste obiecte s�nt instant�e ale claselor care apar �n �gura

??.

Exist�a clase echivalente �ec�arui tip de dat�a Scheme. Aceste clase implementeaz�a

pe l�ng�a structurile de date necesare memor�arii datelor, �si metodele pentru accesul la

aceste date �si modi�care lor. Clasele pentru tipurile de date s�nt:

JScmBoolean, JScmChar, JScmNumber, JScmPair

JScmList, JScmString, JScmSymbol, JScmVector

Obiectele reprezent�nd instant�e ale acestor clase s�nt pe de o parte constantele care apar

�n program, iar pe de alt�a parte s�nt valorile variabilelor create pe parcursul execut�iei

programului.

O alt�a categorie de clase folosite s�nt cele pentru p�astrarea contextelor. Acestea

s�nt:

JScmContext, JScmTopLevel

Clasa JScmTopLevel va p�astra toate leg�aturile variabilelor la nivel top-level din cadrul

programului. Va exista o singur�a instant��a a acestei clase. Clasa JScmContext va �

folosit�a pentru p�atrarea contextelor locale �n cadrul apelurilor de funct�ii. Vor � create

�n mod dinamic instant�e ale acestei clase, pentru �ecare evaluare a unei expresii top-

level.

Clasa JScmFunc va cont�ine toate metodele necesare apelului de proceduri Scheme

prede�nite. Va exista o singur�a instant�a a clasei. Clasa va avea toate metodele statice,

�si nu va avea nici un c�mp.

Toate aceste clase s�nt implementate �n limbajul Java, singura except�ie �ind clasa

JScmUser, care va � creat�a de c�atre compilator, pe baza programului Scheme tranfor-

mat �n prealabil �n limbajul intermediar CPS.

4.2 Tipuri de date

Fiind un limbaj "dynamically typed", �n Scheme veri�carea tipurilor se face la execut�ie

�si nu la compilare. Limbajul intermediar CPS va � �si el la fel, cu singura except�ie

c�a toate constantele au tipurile explicit speci�cate. Din acest motiv, �n programul

17

Page 18: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

compilat vom folosi pentru toate obiectele Scheme referint�e la obiecte Java (clase

Java).

JScmBoolean

JScmChar

JScmNumber

JScmPair

JScmString

JScmList

JScmSymbol

JScmVector

JScmLambda

JScmUnspec

Comparable

Object

Printable

implements

JScmObject

Figura 4-2: Ierarhia de clase pentru tipurile de date.

Fiec�arui tip Scheme �i asociem c�te o clas�a Java, descendent�a din clasa JScmObject

(v. �gura ??).

Fiecare din aceste clase va implementa dou�a tipuri de metode:

� metode corespunz�atoare funct�iilor Scheme speci�ce tipului respectiv (ex. string-length

pentru tipul string; car, cdr pentru tipurile pair, list; etc.);

� metode corepunz�atoare funct�iilor Scheme aplicabile tuturor tipurilor (ex. char?,

number? - pentru veri�carea apartenent�ei la un anumit tip; eq?, eqv?, equal? -

pentru testarea egalit�at�ii a dou�a obiecte Scheme; etc.).

Metodele comune tuturor claselor s�nt speci�cate �n cele dou�a clase de tip interface,

pe care clasa JScmObject le implementeaz�a. Aceste dou�a clase interface s�nt:

public interface Comparable {

boolean eqP (JScmObject obj);

boolean eqvP (JScmObject obj);

boolean equalP (JScmObject obj);

}

public interface Printable {

void print ();

}

Tipurile Scheme �si clasele corespunz�atoare Java s�nt speci�cate �n tabelul ??.

Fiecare clas�a de�ne�ste un anumit tip de dat�a Scheme. Metodele implementate de

�ecare clas�a s�nt speci�ce tipului de�nit. De exemplu, metodele eq(...), eqv(...),

18

Page 19: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Tip Scheme Tip CPS Clas�a de�nit�ie tip

boolean (#t, #f) bool clasa JScmBoolean

character chr clasa JScmChar

numbers nmb clasa JScmNumber

pairs pair clasa JScmPair

list list clasa JScmList

strings str clasa JScmString

symbols id clasa JScmSymbol

vectors vect clasa JScmVector

procedures lambda clasa JScmLambda

unspeci�ed unspec clasa JScmUnspec

Tabela 4.1: Echivalent�e tipuri Scheme - tipuri Java

equal(...) vor testa egalitatea obiectului primit ca parametru cu obiectul instant�iat.

Metoda print() va tip�ari valoarea obiectului �n funct�ie de tipul acestuia, respect�nd

notat�ia Scheme. Toate metodele implementate de clasele de de�nit�ie de tipuri vor �

apelate de metode din clasa JScmFunc, care aduce aceste metode la forma cerut�a de

apelurile Scheme (subcapitolul urm�ator).

Metodele implementate de �ecare clas�a s�nt descrise mai jos:

� clasa JScmBoolean implementeaz�a tipul de dat�a boolean, cu valorile posibile

true (#t) �si false (#f). Metodele implementate de aceast�a clas�a s�nt:

{ JScmBoolean (boolean b); �! constructor

{ JScmBoolean (JScmBoolean b); �! constructor

{ boolean eqP (JScmObject obj); �! implementeaz�a predicatul de echivalent��a

eq? din Scheme;

{ boolean eqvP (JScmObject obj); �! implementeaz�a predicatul de echivalent��a

eqv? din Scheme;

{ boolean equalP (JScmObject obj); �! implementeaz�a predicatul de echivalent��a

equal? din Scheme;

{ void print (); �! metod�a pentru a��sarea valorii obiectului: #t sau #f.

� clasa JScmChar implementeaz�a tipul de dat�a caracter (char): litere, cifre, car-

actere speciale. Pentru acest tip avem metode de comparat�ie care fac diferent�iere

�ntre literele mari �si mici. Speci�cat�ia standard Scheme ([?] pag. 24) impune

urm�atoarele reguli �n stabilirea ordinii caracterelor:

{ literele mari s�nt �n ordine: (char<? n#A n#B) �ntoarce #t.

{ literele mici s�nt �n ordine: (char<? n#a n#b) �ntoarce #t.

{ cifrele s�nt �n ordine: (char<? n#0 n#9) �ntoarce #t.

{ toate cifrele preced ca ordine toate literele mari sau invers

19

Page 20: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

{ toate cifrele preced ca ordine toate literele mici sau invers

Ordinea aleas�a a fost cea dat�a de ordinea caracterelor �n Java. Metodele imple-

mentate de aceast�a clas�a s�nt:

{ JScmChar (char c); �! constructor;

{ JScmChar (JScmChar c); �! constructor;

{ boolean eq, lt, le, gt, ge (JScmChar c); �! metode pentru stabilirea unei

ordini totale a caracterelor;

{ boolean eq-ci, lt-ci, le-ci, gt-ci, ge-ci (JScmChar c); �! metode similare cu

cele de la eq, cu diferent�a c�a nu se face diferent�iere �ntre litere mari �si litere

mici;

{ boolean alpha, num, space, upper, lower (); �!metode pentru determinarea

tipului de caracter;

{ JScmNumber char2int (); �!metod�a pentru conversia unui caracter �ntr-un

obiect de tip �ntreg;

{ boolean eqP, eqvP, equalP (JScmObject obj); �! implementeaz�a predicatele

de echivalent��a Scheme: eq?, eqv?, equal?;

{ void print (); �! metod�a pentru a��sarea valorii obiectului: #hcaracteri,

sau #space, #tab, #newline, #linefeed, #return, #page, #backspace,

#rubout pentru caractere speciale.

� clasa JScmNumber implementeaz�a tipul de dat�a numeric. Au fost implemen-

tate doar numerele �ntregi. Metodele clasei s�nt:

{ JScmNumber (int n); �! constructor;

{ JScmNumber (JScmNumber n); �! constructor;

{ boolean zero, positive, negative (); �! testarea semnului;

{ boolean odd, even (); �! testarea parit�at�ii;

{ JScmNumber +, * (JScmNumber n1...nk); �! operat�ii aritmetice;

{ boolean eq, lt, le, gt, ge (JScmNumber n1...nk); �! operatori de comparare;

{ boolean eqP, eqvP, equalP (JScmObject obj); �! implementeaz�a predicatele

de echivalent��a Scheme: eq?, eqv?, equal?;

{ void print (); �! metod�a pentru a��sarea valorii obiectului: hnum�ari, de

exemplu 45.

� clasa JScmPair implementeaz�a tipul pereche cu punct (pair), care are dou�a

c�mpuri denumite car �si cdr. Metodele create de clas�a s�nt:

{ JScmPair (JScmObject car, JScmObject cdr); �! constructor;

{ JScmPair (JScmPair pair); �! constructor;

{ JScmObject car, cdr (); �! �ntorc valoarea c�mpului car, respectiv cdr;

{ JScmUnspec set car, set cdr (JScmObject obj); �! seteaz�a valoarea c�mpului

car, respectiv a c�mpului cdr;

{ JScmPair cons (JScmObject car, cdr); �! metod�a pentru crearea unui nou

obiect de tip pair;

20

Page 21: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

{ boolean eqP, eqvP, equalP (JScmObject obj); �! implementeaz�a predicatele

de echivalent��a Scheme: eq?, eqv?, equal?;

{ void print (); �! metod�a pentru a��sarea valorii obiectului: (hcari . hcdri),

de exemplu (53 . "Hello").

� clasa JScmList implementeaz�a tipul list�a; clasa are urm�atoarele metode:

{ JScmList (); �!() constructor list�a vid�a;

{ JScmList (JScmObject car, JScmList cdr); �! constructor;

{ JScmList (JScmList lst); �! constructor;

{ JScmList (JScmObject val[]); �! constructor de creare a unei liste dintr-un

array;

{ int length (); �! determin�a num�arul elementelor listei;

{ JScmObject car (); �! �ntoarce valoarea primului element al listei (c�mpului

car a listei);

{ JScmList cdr (); �! �ntoarce ca rezultat o list�a din care a fost eliminat

primul element (c�mpul |it cdr al listei);

{ boolean eqP, eqvP, equalP (JScmObject obj); �! implementeaz�a predicatele

de echivalent��a Scheme: eq?, eqv?, equal?;

{ void print (); �!metod�a pentru a��sarea valorii obiectului: (helem1i helem2i

... helemni) de exemplu (1 3 "d" 4).

� clasa JScmString implementeaz�a tipul de dat�a �sir de caractere (string). Metodele

implementate s�nt urm�atoarele:

{ JScmString (String str); �! constructor;

{ JScmString (JScmString obj); �! constructor;

{ int length (); �! ne d�a lungimea �sirului de caractere;

{ JScmChar ref (int index); �! metoda �ntoarce caracterul de pe pozit�ia

hindexi din �sir;

{ JScmUnspec set (int index, char ch); �! modi�c�a un caracter speci�cat din

�sir;

{ boolean eqP, eqvP, equalP (JScmObject obj); �! implementeaz�a predicatele

de echivalent��a Scheme: eq?, eqv?, equal?;

{ void print (); �! metod�a pentru a��sarea valorii obiectului sub forma: "S�ir

de caractere".

� clasa JScmVector implementeaz�a tipul de dat�a vector cu elemente care, spre

deosebire de marea majoritate a limbajelor de programare, pot � de tipuri diferite.

Un vector ocup�a mai pit�in loc dec�t o list�a cu acelea�si elemente, iar timpul de

accesare al unui element este mai redus pentru vector dec�t pentru list�a. Metodele

implementate s�nt urm�atoarele:

{ JScmVector (JScmObject obj[]); �! constructor;

{ JScmVector (int n); �! constructor pentru un vector cu hni elemente de

tipul unspeci�ed;

21

Page 22: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

{ JScmVector (int n, JScmObject obj); �! constructor vector cu hni elemente,

av�nd toate aceea�si valoare hobji;

{ JScmVector (JScmVector vect); �! constructor de copiere;

{ JScmList make list (); �! creaz�a o list�a din vector;

{ JScmList length (); �! �ntoarce ca rezultat num�arul de elemente din vector;

{ JScmObject ref (int index); �! metoda �ntoarce elementul de pe pozit�ia

hindexi din vector;

{ JScmUnspec set (int index, JScmObject obj); �! seteaz�a elementul de pe

pozit�ia speci�cat�a la valoarea hobji;

{ JScmUnspec �ll (JScmObject obj); �! seteaz�a toate elementele vectorului

la valoarea dat�a hobji;

{ boolean eqP, eqvP, equalP (JScmObject obj); �! implementeaz�a predicatele

de echivalent��a Scheme: eq?, eqv?, equal?;

{ void print (); �! metod�a pentru a��sarea elementelor vectorului sub forma:

#(3 4 7 "y").

� clasa JScmSymbol implementeaz�a tipul de dat�a simbol din Scheme. Metodele

implementate s�nt:

{ JScmSymbol (JScmSymbol sym); �! constructor de copiere;

{ JScmSymbol (String str); �! constructor;

{ boolean eqP, eqvP, equalP (JScmObject obj); �! implementeaz�a predicatele

de echivalent��a Scheme: eq?, eqv?, equal?;

{ void print (); �! metod�a pentru a��sarea valorii simbolului sub forma:

'hsymboli.

� clasa JScmUnspec implementeaz�a tipul de dat�a unspeci�ed din Scheme. Metodele

folosite s�nt:

{ JScmUnspec (); �! constructor;

{ boolean eqP, eqvP, equalP (JScmObject obj); �! implementeaz�a predicatele

de echivalent��a Scheme: eq?, eqv?, equal?;

{ void print (); �!metod�a pentru a��sarea valorii obiectului sub forma: #unspec.

� clasa JScmLambda implementeaz�a procedurile de�nite de utilizator (expresiile

lambda de�nite). Descrierea clasei va � explicat�a �ntr-unul din subcapitolele

urm�atoare.

4.3 Implementarea procedurilor de baz�a Scheme

Procedurile de baz�a ale limbajului Scheme s�nt implementate �n clasa JScmFunc.

Fiecare din metodele acestei clase implementeaz�a c�te una din procedurile de baz�a.

Marea majoritate a metodelor s�nt apeluri la metode din clase Java corespunz�atoare

tipurilor speci�cate mai sus, f�ac�ndu-se transformarea la sintaxa cerut�a de Scheme.

22

Page 23: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Clasa JScmFunc nu are variabile, doar metode. Pentru �ecare apel al unei astfel de

proceduri de baz�a Scheme, �n byte-code-ul generat rezult�a un apel al unei metode din

aceast�a clas�a.

De exemplu pentru procedura Scheme (string-length h�siri), metoda core-

spunz�atoare din clasa JScmFunc este:

public static JScmNumber stringslength (JScmString str) {

return new JScmNumber (str.length ());

}

Procedurile Scheme de echivalent��a, eq?, eqv? �si equal? s�nt implementate �n mod

diferit fat��a de celelelte. In funct�ie de tipul primului parametru, se face apelul metodei

corespunz�atoare eqP, eqvP sau equalP din clasa tipului respectiv.

O parte din procedurile Scheme referitoare la tipul de dat�a caracter s�nt date �n

exemplul de mai jos:

class JScmFunc {

public JScmFunc () {

}

/*======= CHAR type functions =============================*/

/* invoke copy constructor */

public static JScmChar new_char (JScmChar obj) {

return new JScmChar (obj);

}

/* R4RS essential procedure - char? */

public static JScmBoolean charP (JScmObject obj) {

return new JScmBoolean (obj instanceof JScmChar);

}

/* R4RS essential procedure - char=? */

public static JScmBoolean char_eqP (JScmObject obj1, JScmObject obj2) {

return new JScmBoolean ((obj1 instanceof JScmChar) &&

(obj2 instanceof JScmChar) &&

((JScmChar)obj1).eq ((JScmChar)obj2));

}

...

/* R4RS essential procedure - char-ci=? */

public static JScmBoolean char_ci_eqP (JScmObject obj1, JScmObject obj2) {

return new JScmBoolean ((obj1 instanceof JScmChar) &&

(obj2 instanceof JScmChar) &&

((JScmChar)obj1).eq_ci ((JScmChar)obj2));

}

...

/* R4RS essential procedure - char-alphabetic? */

public static JScmBoolean char_alphabeticP (JScmObject obj) {

23

Page 24: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

return new JScmBoolean ((obj instanceof JScmChar) &&

((JScmChar)obj).alpha ());

}

...

/* R4RS essential procedure - char-upcase */

public static JScmChar char_upcase (JScmObject chr) {

return new JScmChar (((JScmChar)chr).charUpValue ());

}

...

/* R4RS essential procedure - char->integer */

public static JScmNumber char2integer (JScmObject chr) {

return new JScmNumber (((JScmChar)chr).intValue ());

}

}

4.4 Clasa generat�a JScmUser

Aceast�a clas�a este generat�a de pe baza programului adus �n forma intermediar�a CPS.

Aceast�a clas�a va implementa �n cadrul metodelor sale codul corespunz�ator programului.

In aceast�a clas�a s�nt implementate deasemeni toate funct�iile noi de�nite de program-

ator. Modul �n care aceste funct�ii noi s�nt implementate va � explicat �n subcapitolul

urm�ator.

Structura unei astfel de clase este urm�atoarea:

class JScmUser

extends java.lang.Object

{

~1 /* constants used in the program */

Field public static JScmObject const_0

Field public static JScmObject const_1

...

/* constants for error report */

Field public static JScmObject const_err

Field public static JScmObject const_null

~2 /* class constructor */

Method void <init> ()

max_stack 1

{

aload_0

invokenonvirtual void java.lang.Object.<init> ()

return

}

24

Page 25: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

~3 /* class initializer */

Method static void init ()

max_stack 4

{

~4 /* initialize the constants */

/* constant err */

new JScmString

dup

ldc "*** not yet implemented"

invokenonvirtual void JScmString.<init> (java.lang.String)

putstatic JScmObject JScmUser.const_err

/* constant null */

new JScmString

dup

ldc "* null"

invokenonvirtual void JScmString.<init> (java.lang.String)

putstatic JScmObject JScmUser.const_null

/* constant no. 0, type NUMBER */

new JScmNumber

dup

ldc 11

invokenonvirtual void JScmNumber.<init> (int)

putstatic JScmObject JScmUser.const_0

...

return

}

~5 /* main method */

Method public static void main (java.lang.String[])

max_stack 9

{

/* initialize the class */

invokestatic void JScmUser.init()

~6 /* expressions */

/* EXPR 1 */

/* CONST NUMBER */

getstatic JScmObject JScmUser.const_0

invokevirtual void JScmObject.print()

getstatic java.io.PrintStream java.lang.System.out

invokevirtual void java.io.PrintStream.println()

...

return

25

Page 26: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

~7 /* User defined function declarations */

Object ret_addr

/* expecting 'JScmLambda' + 'ret_addr' on the stack */

call_funct:

astore ret_addr

/* expecting 'JScmLambda' on the stack */

goto_funct:

invokevirtual int JScmLambda.keyValue()

goto goto_funct_cps

/* expecting 'funct_key' + 'ret_addr' on the stack */

call_funct_cps:

astore ret_addr /* save the return address */

/* expecting 'funct_key' on the stack */

goto_funct_cps:

lookupswitch default nowhere

{

0: f_lambda_0 /* id(x) --> x function

1: f_lambda_1 /* user function 1 */

2: f_lambda_2 /* user function 2 */

...

}

nowhere:

ret ret_addr

/* identity function (continuation) */

f_lambda_0:

ret ret_addr /* return to the saved return address */

/* user function 1 */

f_lambda_1:

/* save actual parameters */

...

goto call_funct_cps

}

}

(~1) Toate constantele care apar �n programul Scheme s�nt create ca variabile

(c�mpuri) ale clasei JScmUser generate. Dac�a o constant�a apare de mai multe ori �n

cadrul programului, este creat un singur c�mp pentru clas�a care este init�ializat la val-

oarea constantei. Astfel, dac�a de exemplu �n program apare �sirul de caractere "Test"

de mai multe ori �n diferite expresii, atunci este creat un singur c�mp �n cadrul clasei:

JScmObject const x. Tipul cimpului va � JScmString, iar valoarea sa va � "Test":

26

Page 27: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

...

Field public static JScmObject const_5

...

Method static void init ()

{

...

/* constant no. 5, type STRING */

new JScmString

dup

ldc "Test"

invokenonvirtual void JScmString.<init> (java.lang.String)

putstatic JScmObject JScmUser.const_5

...

}

Deoarece pe parcursul execut�iei programului, valorile acestor constante nu pot �

modi�cate, ele vor avea �n permanent��a acelea�si valori. Din acest motiv, precum �si

pentru a avea byte-code-ul generat mai simplu, c�mpurile clasei pentru constante s�nt

de tipul static. Byte-code-ul devine mai simplu deoarece �n cazul �n care avem c�mpuri

statice, accesul la ele se face printr-o simpl�a instruct�iune:

getstatic htip c�mpi hnume c�mpi

f�ar�a a avea nevoie de nimic pe stiv�a, spre deosebire de cazul c�mpurilor nestatice, �n

care instruct�iunea de acces la c�mp are aceea�si form�a:

getfield htip c�mpi hnume c�mpi

�n schimb �ns�a, pe stiv�a trebuie s�a avem o referint��a la o instant��a a unei astfel de clase

(JScmUser).

(~2) hiniti() este metoda constructor a clasei. Singurul lui rol este de a apela

constructorul clasei p�arinte java.lang.Object.

(~3)(~4) Metoda init() este metoda de init�ializare a clasei, av�nd rolul de a init�ializa

�n mod corespunz�ator c�mpurile constante ale clasei. De exemplu, pentru o constant�a

de tip �ntreg vom avea urm�atoarea secvent��a de init�ializare:

/* constant no. 2, type NUMBER */

new JScmNumber

dup

ldc 133 /* constant value */

invokenonvirtual void JScmNumber.<init> (int)

putstatic JScmObject JScmUser.const 2

27

Page 28: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

(~5) Metoda principal�a a clasei este main(String[]). In aceast�a metod�a se a �a codul

generat corespunz�ator programului. Pentru �ecare expresie Scheme top-level este

generat�a o secvent��a de byte-code-uri echivalent�a (~6). Prin execut�ia secvet�ei respective

(�n momentul rul�arii programului pe ma�sina virtual�a) se obt�ine rezultatul evalu�arii

expresiei.

(~6) Tot �n metoda main(String[]) se a �a �si codul generat corespunz�ator funct�iilor

noi de�nite de programator. Inceputul codului �ec�arei funct�ii este etichetat, apelul

�ec�arei funct�ii �ind f�acut pe baza acestei etichete folosind o tabel�a de salt indexat�a.

4.5 Implementarea funct�iilor noi

In urma transform�ariiCPS, �ecare funzt�ie de�nit�a de utilizator va primi un parametru

suplimentar, reprezentat de o continuare. Aceast�a continuare este folosit�a pentru a-i

pasa rezultatul funct�ie.

Fiecare funct�ie compilat�a va � considerat�a ca av�nd un al doilea parametru supli-

mentar, pe l�ng�a continuare. Acesta este reprezentat de un context. Acest context va

cuprinde toate leg�arile de variabile care au fost de�nite local, pe parcursul evalu�arii

unei expresii, p�n�a �n momentul apelului funct�iei. Acest context nu va cont�ine nici una

din de�nit�iile top-level de variabile, acestea a �ndu-se �ntr-un alt obiect, JScmTopLevel.

Contextul primit de o funct�ie va � folosit pentru a a a valoarea unei variabile libere

folosite �n cadrul funct�iei. O funct�ie care prime�ste un astfel de context, va ad�auga la

acesta toate de�nit�iile locale de variabile, efectuate �n cadrul funct�iei. Noul context va

� folosit de celelalte funct�ii apelate �n mod asem�an�ator.

O clas�a context va cont�ine perechi de obiecte simbol-valoare:

JScmSymbol - JScmObject.

De�nit�ia clasei JScmContext va cont�ine dou�a metode publice pentru c�autarea, respectiv

ad�augarea unei noi perechi:

class JScmContext extends Object {

JScmSymbol ctx_syms[]; /* the symbols from context */

JScmObject ctx_vals[]; /* the values from context */

public void addSymbol (JScmSymbol sym, JScmObject val) {

public JScmObject getSymbol (JScmSymbol sym) {

}

28

Page 29: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Toate apelurile de funct�ii, �n urma transform�arii CPS, s�nt �n sub forma tail. Asta

�nseamn�a c�a ele nu mai �ntorc controlul �n funct�ia apelant�a (imediat superioar�a). Din

acest motiv clasa JScmContex nu necesit�a metode pentru �stergerea unei perechi dintr-n

context.

Forma tail permite implementarea funct�iilor recursive elimin�nd folosirea ine�cient�a

a stivei. Cu alte cuvinte apelul unei funct�ii din cadrul altei funct�ii nu se mai face cu o

instruct�iune de apel de subrutina, ci cu una de salt, de tip goto.

Astfel, de exemplu, urm�atorul cod recursiv, care respect�a forma tail:

f: /* stack=[arg1, arg2, ...] */

...

if <...>

push arg1'

push arg2'

...

call f

endif

...

return /* reface stiva, stergind argumentele primite */

poate � rescris, mai e�cient �n felul urm�ator:

f: /* stack=[arg1, arg2, ...] */

...

pop varg2

pop varg1

...

if <...>

push arg1'

push arg2'

...

goto f

endif

...

return' /* face doar intoarcerea din apelul functiei */

In setul de instruct�iuni pentru ma�sina virtual�a Java exist�a urm�atoarele instruct�iuni

pentru transferul controlului �n cadrul programului:

� invokestatic, invokevirtual, invokenonvirtual, invokeinterface pentru

apelul metodelor unei clase Java;

� jsr, ret pentru apelul unor minisubrutine a ate �n byte-code-ul unei aceleia�si

metode;

29

Page 30: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

� goto pentru salt necondit�ionat doar �n cadrul byte-code-ului unei metode.

O metod�a pentru implementarea apelurilor de funct�ii Scheme de�nite de pro-

gramator ar � ca �ecare astfel de funct�ie s�a reprezinte o metod�a distinct�a �ntr-o clas�a

Java. In acest fel, pentru �ecare apel de funct�ie trebuie generat codul corespunz�ator

unui apel de metod�a. Parametrii necesari unui apel de metod�a trebuie pu�si �naintea

apelului pe stiv�a, urm�nd care rezultatul apelului s�a �e deasemenea pus pe stiv�a �n

locul parametrilor apelului. Problema apare �n momentul �n care �ncerc�am s�a elimin�an

apelurile recursive. Stiva este ref�acut�a doar dup�a terminarea execut�iei metodei din care

s-a f�acut apelul, �n momentul execut�iei unei instruct�iuni de tip return. S�a consider�am

urm�atorul exemplu Scheme:

(define f

(lambda (x)

(if (> x 0) (f (- x 1)) 0)))

(f 1000000)

Codul corespunz�ator scris �n limbaj de asamblare ar �:

class Exemplu_1 {

...

Method public static int f (int)

max_stack 3

{

iload_0

ifle f_end

iload_0

iconst_1

isub

invokestatic int Exemplu_1.f (int)

ireturn

f_end:

iconst_0

ireturn

}

Method public static main (...)

max_stack 3

{

...

/* apel (f 1000000) */

ldc 1000000

30

Page 31: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

invokestatic int Exemplu_1.f (int)

...

}

...

}

Funct�ia f se va apela �n mod recursiv, decrement�nd de �ecare dat�a argumentul

primit. Dac�a apel�am funct�ia cu un parametru de valoare foarte mare, atunci vom

avea cu sigurant��a o dep�a�sire de stiv�a, ma�sina virtual�a semnal�nd o except�ie de tipul:

java.lang.StackOverflowError.

Solut�ia ar � s�a aducem expresia �n form�a tail, �si s�a implement�am funct�i f �n aceea�si

metod�a ca �si funct�ia apelant�a. In cazul exemplului nostru simplu, expresia Scheme

este deja �n form�a tail. Codul generat scris �n limbaj de asamblare va avea forma:

class Exemplu_1 {

...

Method public static void main (...)

max_stack 3

{

...

/* apel (f 1000000) */

ldc 1000000

jsr f_start

...

return

f_start: /* functia f */

int n

Object ret_addr

/* pop the return address and the argument from the stack */

store ret_addr

f_goto:

store n

load n /* push n onto the stack */

iload_0 /* push constant 0 onto the stack */

ifle f_end

load n

iconst_1

isub /* decrement n */

goto f_goto

f_end:

iconst_0 /* return 0 */

ret ret_addr

31

Page 32: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

}

...

}

Se observ�a c�a �n acest caz nu mai avem dep�a�sire de stiv�a, apelul recursiv �ind

�nlocuit cu salturi �n cadrul metodei.

Deci solut�ia pentru implementarea recursivit�at�ii este folosirea combinat�a a instruct�iunilor

jsr, ret, goto. Acest lucru ne oblig�a ca �ecare funct�ie Scheme (lambda de�nit�ie) s�a

reprezinte ominisubrutina, apelabil�a �e printr-o instruct�iune de tip jsr, �n cazul primu-

lui apel, �e printr-o instruct�iune de tip goto, �n cazul apelurilor recursive din cadrul

funct�iei. Toate aceste de�nit�ii de funct�ii vor trebui implementate �n cadrul aceleia�si

metode. Apelul unei astfel de funct�ii va � deci posibil doar din cadrul aceleia�si metode.

Deci un top-level Scheme va � implementat ca o clas�a cu o metoda �n care se de�nesc

toate funct�iile.

Pe linga functiile pe care le de�neste utilizatorul avem si functiile prede�nite Scheme

('R4RS essential procedure'). Acestea pot � consi- derate 'primop'-uri in transformarea

CPS, ceea ce inseamna ca apelul lor nu va folosi nici o functie de�nita de utilizator,

deci nu apare problema recursivitatii. In acest caz insa, acestea nu pot � rede�nite

in asa fel incit sa poata � eliminata recursivitatea. Pentru aceasta si aceste functii

prede�nite trebuie considerate ca 'apply'-uri in transformarea CPS. In acest caz, si

functiile rede�nite sint considerate ca functii de�nite de utilizator, bene�ciind astfel de

eliminarea recursivitatii. Functiile prede�nite Scheme sint implementate intr-o clasa

separata Java numita JScmFunc, care apeleaza metode speci�ce �ecarui tip, a ate in

clasele de de�nire a tipurilor (JScmChar, ...). Implementarea unui program Scheme

se face folosind o clasa Java cu o singura metoda. Aceasta va contine (printre altele)

secvente de cod etichetate, corespunzatoare �ecarei expresii lambda. Apelul, respectiv

saltul, unei astfel de expresii lambda se face folosind o instructiune byte-code 'lookup-

switch', saltul la urmatoarea instructiune facindu-se pe baza unei key de selectie, cheie

a ata pe stiva:

switch_jsr:

astore_x

getstatic TopLevel.local_func

getfield Lambda.lookup_key

32

Page 33: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

new Lambda

dup

invokenonstatic Lambda.<init> ()

swap

switch_goto:

lookupswitch {

k0: lambda_0

k1: lambda_1

k2: lambda_2

\ldots

}

unde Lambda va � o clasa Java care va contine cheia de salt al functiei, iar dupa caz

si variabilele libere ale functiei:

class Lambda extend java.lang.Object {

public int lookup_key;

Object free_vars[];

public Lambda () {

lookup_key = 0;

}

public void PutFreeVar (int i, Object x) {

free_vars[i] = x;

}

public Object GetFreeVar (int i) {

return free_vars[i];

}

}

Prima eticheta switch_jsr va � folosita pentru apelul unei lambda expresii din

cadrul unor expresii top-level, iar cea de-a doua switch_goto pentru apelul unei astfel

de expresii din cadrul unei expresii in forma tail-form.

33

Page 34: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Capitolul 5

Asamblarea �n byte-code

Asamblorul va realiza transformarea unui ��sier surs�a scris �n limbaj de asamblare Java

�ntr-un ��sier .class valid, cont�in�nd byte-code-ul corespunz�ator unei clase Java. Acest

��sier rezultat va trebui s�a poat�a � executat de c�atre ma�sina virtual�a Java, deci va

trebui s�a respecte formatul cerut de acesta. Asamblorul realizeaz�a crearea automat�a

a tabelei de constante (constant-pool) din ��sierul .class, calculeaz�a automat o�set-urile

pentru salturile din cadrul metodelor.

5.1 Sintaxa asamblorului

Sintaxa limbajului de asamblare este asem�an�atoare ie�sirii generate de c�atre utilitarul

javap din JDK. javap este un dezasamblor de ��siere .class, care a��seaz�a cont�inutul

unei clase Java (c�mpuri, metode, byte-code) �ntr-un format mai u�sor de �nt�eles pentru

programator.

Un ��sier cu codul de asamblare pentru o clas�a Java trebuie s�a aib�a urm�atorul

format:

[abstract] [final] [public] [interface] class nume_clasa

[extends nume_super_clasa]

[implements nume_interfata_1 [nume_interfata_2 [ ... ] ] ]

{

[declaratii_cimpuri]

[declaratii_metode]

[sourcefile nume_fisier_sursa]

}

� nume clasa este numele valid al clasei av�nd urm�atorul format:

part1[.part2[.part3[...]]]

34

Page 35: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

part1, part2, ... s�nt identi�catori reprezent�nd diferite part�i ale numelui clasei;

de exemplu java.lang.Object;

� nume super clasa este numele clasei din care clasa curent�a este descendent�a;

�n cazul �n care lipse�ste se consider�a implicit ca �ind clasa java.lang.Object;

� nume interfata i este numele unei clase care reprezint�a o interfat��a �si pe care

clasa curent�a o implementeaz�a;

� nume �sier sursa este numele ��sierului surs�a din care este generat ��sierul .class;

� declarat�iile de c�mpuri din cadrul clasei trebuie s�a aib�a urm�atorul format:

field [specificator_acces] [static] [final] [transient]

[volatile] nume_cimp [= valoare_constanta]

{ speci�cator acces speci�c�a tipul accesului la c�mpul respectiv, �si poate

avea urm�atoarele valori: private, private protected, protected, public;

{ nume c�mp este un identi�cator �si reprezint�a numele c�mpului;

{ valoare constant�a este o constant�a av�nd tipul c�mpului respectiv (unul

din tipurile de baz�a Java), �si care reprezint�a valoarea constant�a a c�mpului;

� declarat�iile de metode din cadrul clasei trebuie s�a aib�a urm�atorul format:

method [specificator_acces] [static] [abstract]

[final] [native] [synchronized]

tip_rezultat nume_metoda ( [arg1 [, arg2 [, ...] ] ] )

[throws nume_exceptie_1 [nume_exceptie_2 [...] ] ]

max_stack valoare1

[max_locals valoare2]

{

[cod_metoda]

[tabela_exceptii]

[tabela_numerotare_linii]

[tabela_variabile_locale]

}

35

Page 36: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

{ tip rezultat reprezint�a tipul rezultatului �ntors de metod�a �si poate � void

sau un tip valid: nume de clas�a, tablou (array) sau unul din tipurile de baz�a

(byte, char, double, oat, int, long, short, boolean);

{ nume metod�a este un identi�cator reprezent�nd numele metodei;

{ arg1, arg2, . . . s�nt tipuri valide reprezent�nd tipurile parametrilor metodei;

pot � urmate opt�ional de numele parametrilor;

{ nume except�ie i reprezint�a numele unei clase care este o except�ie pe care

aceast�a metod�a o poate genera;

{ valoare1 reprezint�a dimensiunea maxim�a a stivei de care metoda poate avea

nevoie;

{ valoare2 reprezint�a num�arul maxim de variabile locale de care metoda re-

spectiv�a are nevoie; dac�a nu este speci�cat, atunci asamblorul determin�a

automat num�arul de variabile locale pe baza num�arului de�nit�iilor lor din

cadrul metodei;

{ cod metod�a reprezint�a codul efectiv al metodei �si const�a �n linii de forma

a) sau b); prima form�a reprezint�a apelul unei operat�ii de tip byte-code, iar

cea de-a doua reprezint�a o de�nit�ie de variabil�a local�a �n cadrul metodei

a) [etichet�a] operat�ie

b) [etichet�a] tip variabil�a nume variabil�a local�a

etichet�a este numele unei etichete folosit�a pentru salturi �n cadrul metodei.

{ tabel�a except�ii are urm�atoarea form�a �si reprezint�a delimitarea �n cadrul

metodei a subprocedurilor de tratare a except�iilor:

exceptions

{

start_pc1 end_pc1 subr_pc1 catch_tip1

start_pc2 end_pc2 subr_pc2 catch_tip2

...

}

� start pc - etichet�a reprezent�nd �ceputul zonei din metod�a pentru care

se face tratarea except�iilor;

36

Page 37: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

� end pc - etichet�a reprezent�nd sf�r�situl zonei din metod�a pentru care se

face tratarea except�iilor;

� subr pc - etichet�a reprezent�nd adresa subrutinei de tratare a except�iilor

pentru zona speci�cat�a;

� catch tip - reprezint�a numele unei clase de tip except�ie sau valoarea 0;

{ tabel�a numerotare linii speci�c�a numerotarea liniilor surs�a echivalente

��sierului compilat �si are urm�atoarea form�a; aceast�a tabe�a este folosit�a pentru

depanarea unui ��sier .class.

linenumbertable

{

start_pc1 numar_linie_1

start_pc2 numar_linie_2

...

}

� start pc - etichet�a reprezent�nd adresa liniei numerotate;

� num�a linie - reprezint�a num�arul efectiv �n ��sierul surs�a al codului com-

pilat �ncep�nd de la adresa codului speci�cat�a;

{ tabel�a variabile locale speci�c�a zonele de de�nit�ie a variabilelor locale

localvariabletable

{

start_pc1 end_pc1 tip1 local_var1 slot_num1

start_pc2 end_pc2 tip2 local_var2 slot_num2

...

}

� start pc, end pc - etichete care delimiteaz�a zona �n care variabila

local�a local var va avea o valoare de tipul tip, av�nd slotul slot num

�n �nregistrarea de activare a metodei curente.

5.2 Facilit�at�i oferite de asamblor

Asamblorul ofer�a o mult�ime de facilit�at�i pentru u�surarea program�arii direct �n byte-code

pentru ma�sina virtual�a Java.

37

Page 38: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

� generarea automat�a a ��sierului binar .class; asamblorul genereaz�a automattoate

structurile de date folosite �ntr-un astfel de ��sier pe baza informat�iilor din ��sirul

scris �n limbaj de asamblare: tabela de constante (constant-pool), tabela de

c�mpuri a clasei, tabela de metode, tabela de except�ii pentru �ecare metod�a,

calculeaz�a signaturile;

� generarea automat�a a constant-pool-ului: unele instruct�iuni din limbajul ma�sinii

virtuale Java primesc ca parametru un o�set �n constant-pool; limbajul de asam-

blare nu permite lucrul direct cu o�set-uri �n constant-pool-ul, �n schimb �ns�a per-

mite lucrul direct cu valorile din constant-pool. Astfel, de exemplu, instruct�iunea:

new prime�ste ca parametru un o�set �n constant-pool c�atre numele unei clase,

instruct�iunea av�nd astfel o lungime de trei octet�i: primul este codul operat�iei

(187 pentru new), restul reprezent�nd o�setul pe 16 bit�i:

new h35i

In limbajul de asamblare se folose�ste direct numele clasei:

new java.lang.String,

urm�nd ca asamblorul, �n momentul gener�arii ��sierului binar s�a creeze intrarea

corespunz�atoare �n tabela de constante �si s�a genereze codul instruct�iunii folosind

o�set-ul rezultat;

� limbajul de asamblare permite programatorului s�a foloseasc�a variabile locale �n

cadrul unei metode, �n locul folosirii directe a unui index �n frame-ul Java curent.

In felul acesta este mult mai simplu pentru programator, acesta ne�ind nevoit

s�a t�in�a minte indec�si pentru variabile, ci doar numele lor, programul devenind

�si mult mai simplu de urm�arit. Astfel, �n loc s�a scriem iload 5, adic�a �ncarc�a

valoarea din variabila a 5-a pe stiv�a, putem folosi urm�atoarea secvent��a:

int variabil�a contor

...

iload variabil�a contor

� exist�a �n limbajul de asamblare exist�a dou�a noi instruct�iuni: load �si store, care

pot � folosite av�nd ca parametru o variabil�a local�a de�nit�a ca mai sus. Cele dou�a

instruct�iuni s�nt echivalente cu iload, lload, fload, dload, aload, respec-

tiv istore, lstore, fstore, dstore, astore, �n funct�ie de tipul variabilei lo-

38

Page 39: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

cale. Asamblorul, cunosc�nd tipul variabilei folosite �ntr-o astfel de instruct�iune,

genereaz�a automat instruct�iunea corespunz�atoare tipului variabilei. De exemplu

instruct�iunea

load variabil�a contor

din exemplul precedent va genera �n byte-code instruct�iunea iload. In felul acesta

programatorul nu trebuie s�a mai scrie �n program instruct�iuni diferite pentru

tipuri diferite, l�as�nd aceast�a sarcin�a �n seama asamblorului.

� limbajul de asamblare permite folosirea etichetelor pentru salturi �n cadrul unei

metode. In felul acesta, programatorul nu trebuie s�a mai calculeze manual un

o�set pentru o instruct�iune de salt, �ind sarcina asamblorului. De exmplu, �n

locul urm�atorului cod (salt dup�a instruct�iunea iload care ocup�a 2 octet�i):

goto +2

iload 20

...

se folose�ste urm�atoarea secvent��a:

goto eticheta 4

iload 20

eticheta 4:

....

Mai mult chiar, �n cazul �n care o�set-ul saltului dep�a�se�ste dimensiunea mem-

orabil�a pe un octet (-128 . . . +127), ar trebui folosit�a instruct�iunea goto w;

asamblorul ��si d�a singur seama de acest lucru, �si genereaz�a automat byte-code-ul

pentru instruct�iunea goto w, chiar dac�a a fost folosit goto.

� etichetele pot � folosite �si pentru cele dou�a instruct�iuni de salt bazate pe tabele:

tableswitch �si lookupswitch, ca �n exemplul:

ldc 7

lookupswitch default eticheta 0

f

1 : eticheta 1

5 : eticheta 2

9 : eticheta 3

g

39

Page 40: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

eticheta 0:

ldc 86

tableswitch 85 to 87 default eticheta 10

f

eticheta 11

eticheta 12

eticheta 13

g

...

5.3 Exemplu

Un exemplu de program scris �n limbaj de asamblare pentru ma�sina virtual�a Java este

urm�atorul:

class Hello2

extends java.lang.Object

{

Method public static void main (java.lang.String[])

max_stack 2

max_locals 2

{

getstatic java.io.PrintStream java.lang.System.out

ldc "Hello World!"

invokevirtual void java.io.PrintStream.println(java.lang.String)

ldc 250

invokevirtual void java.io.PrintStream.println(int)

return

}

Method void <init> ()

max_stack 2

max_locals 1

{

aload_0

invokenonvirtual void java.lang.Object.<init>()

return

}

}

Programul a��seaz�a pe ecranu �sirul de caractere "Hello World!" urmat de num�arul

�ntreg 250. Fi�sierul .class generat de asamblor �si dezasamblat cu ajutorul utilitarului

javap este redat mai jos.

40

Page 41: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

class Hello2 extends java.lang.Object {

public static void main(java.lang.String []);

/* Stack=2, Locals=2, Args_size=1 */

Hello2();

/* Stack=2, Locals=1, Args_size=1 */

Method void main(java.lang.String [])

0 getstatic #8 <Field java.lang.System.out Ljava/io/PrintStream;>

3 ldc #14 <String "Hello World!">

5 invokevirtual #16 <Method java.io.PrintStream.println(Ljava/lang/String;)V>

8 ldc #22 <Integer 250>

10 invokevirtual #23 <Method java.io.PrintStream.println(I)V>

13 return

Method Hello2()

0 aload_0

1 invokenonvirtual #24 <Method java.lang.Object.<init>()V>

4 return

}

41

Page 42: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Capitolul 6

Concluzii

Lucrarea de fat��a trateaz�a aspectele teoretice �si problemele de implementare ap�arute

�n proiectarea unui compilator pentru limbajul Scheme. Cea mai mare parte a tran-

form�arii din limbajul intermediar CPS �n byte-code pentru ma�sina virtual�a Java este

implementat�a.

Limbajul Scheme implementat este un subset al standardului de�nit �n raportul

[?]. Nu s�nt implementate dec�t numerele �ntregi, acestea �ind echivalente cu numerele

�ntregi din Java, pe 32 bit�i. Lipse�ste partea de aritmetic�a cu numere rat�ionale �si cea

cu numere reale, lucrarea �ind orientat�a mai mult spre aspecte privind posibilitatea

compil�arii limbajului Scheme, �si mai put�in pe realizarea unei implement�ari complete

a limbajului.

Dezvolt�ari ulterioare pot � f�acute �n mai multe direct�ii. Printre acestea ar � posi-

bilitate de�nirii �si folosirii direct din limbajul Scheme, utiliz�nd o sintax�a extins�a a

limbajului, a unor mecanisme de programare orientate obiect, respectiv de�nirea de

obiecte �si instant�e ale lor. In acest sens este posibil�a modi�carea compilatorului, astfel

�nc�t s�a poat�a genera clase Java noi, folosind o sintax�a corespunz�atoare.

O alt�a posibilitate de dezvoltare ar � posibilitatea instant�ierii de obiecte �si apelului

de metode ale claselor Java deja existente �ntr-un program |bf Scheme. In mod

asem�an�ator �si pentru aceasta este necesar�a extinderea sintaxei limbajului Scheme

cu elemente care s�a permit�a aceste operat�ii.

42

Page 43: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Anexa A

Exemple programe

43

Page 44: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Anexa B

Listing programe

44

Page 45: de diplom a Utilizarea - NTNU · cont in ut executabil, precum si faptul c ma sina virtual Ja v a implemen teaz mecanism ul de ... call-with-current-continuation (call/cc), pro cesul

Bibliogra�e

[1] Friedman, Daniel P.; Wand, Mitchell; Haynes, Christopher T. Essentials of Pro-

gramming Languages. MIT Press, 1992.

[2] Appel, Andrew W. Compiling with Continuations. Cambridge University Press,

1992.

[3] Clinger, William and Rees, Jonathan (Editors). Revised4 Report on the Algorith-

mic Language Scheme. Available by anonymous ftp from altdorf.ai.mit.edu.

1991.

[4] Dybvig, R. K. Three Implementation Models for Scheme. University of North

Carolina Computer Science Technical Report 87-011 [Ph.D. Dissertation], April

1987.

[5] The Java Virtual Machine Speci�cation. Release 1.0, Sun Microsystems, August

1995.

[6] The JavaTM Language Speci�cation. Release 1.0, Sun Microsystems, October

1996.

45