de diplom a utilizarea - ntnu · cont in ut executabil, precum si faptul c ma sina virtual ja v a...
TRANSCRIPT
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
Cuprins
2
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
� 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
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
� �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
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
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
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
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
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
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
� 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
� 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
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
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
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
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
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
{ 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
{ 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
{ 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
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
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
~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
~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
...
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
(~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
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
� 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
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
}
...
}
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
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
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
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
{ 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
� 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
� 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
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
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
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
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
Anexa A
Exemple programe
43
Anexa B
Listing programe
44
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