GradientTop
PC
Vodeći IT časopis u Srbiji
PC #35 > Programiranje
ARHIVA BROJEVA | O ČASOPISU | POSTANI SARADNIK | PRETRAGA
nopreview
Iz C-a u Javu
Zoran Budimlić
Programeri su se radovali Javi, ali sada treba platiti račun - traži se automatsko prevođenje iz C++-a...
- PC #35 u prodaji po ceni od 110 din
broj

Iz C-a u Javu

Java je objektno orijentisan modularan jezik, sa bezbednim tipovima podataka, ugrađenim sistemom sigurnosti za izvršavanje preko Interneta, mehanizmom prekida i nedostatkom pokazivača i eksplicitne alokacije i dealokacije memorije, što olakšava traženje grešaka u programu. Iako je odluka o prevođenju iz C-a u Javu jedna od vrlo retkih (sa programerske tačke gledišta), pametnih odluka koje menadžeri donose, sam posao prebacivanja milijardi linija C koda (koliko autor slobodno procenjuje da se nalazi u svetu) nije nimalo lak.

Na tri načina

Postoje tri načina pristupa ovom problemu. Prvi bi bio redizajniranje „od nule“ i ponovo programiranje softvera koji je napisan u C-u. Dugoročno, ovo je najbolje rešenje, jer omogućava najlakše održavanje i proširenje postojećeg softvera u budućnosti, naročito ako verujete da su Java programi lakši za održavanje i proširenje nego ekvivalentni C programi. Nažalost, ova opcija je preskupa – samo nekoliko kompanija i to na nekoliko (uglavnom manjih) projekata mogu sebi da priušte ovu opciju.

Drugi je pisanje Java „omotača“ (wrappers) oko postojećih rutina u C-u i njihovo pozivanje iz Jave na taj način. Ovo je najbrže i najjeftinije rešenje koje donekle rešava problem nadograđivanja, pošto se dodatni softver može pisati u Javi. Nažalost, problem održavanja ostaje netaknut, a u neku ruku i pogoršan, pošto bi inženjeri morali da budu specijalisti za oba jezika, kao i za specifične probleme koji se pojavljuju samo na „granicama“ prilikom poziva rutina iz Jave u C i obrnuto. Uz to, opcija odustaje od sigurnosti i prenosivosti, što su glavni razlozi upotrebe Jave.

Treći bi bio pisanje alata koji bi (polu)automatski prebacivao C kod u Javu. Ovo je jeftino (CPU ciklusi su u principu mnogo jeftiniji nego programersko vreme), ali nažalost ne i tako brzo rešenje. Problem je što takve alatke trenutno ne postoje, a ako ih i ima, kvalitet proizvedenog Java koda nije na zavidnom nivou. U daljem tekstu prvenstveno ćemo se pozabaviti ovim pristupom, odnosno problemima i mogućim rešenjima koji nastaju njegovom primenom.

Pokazivači i reference

Teoretičari iz oblasti računarske tehnike mogu vas ubeđivati da je pomenuti problem rešen: Tjuring je odavno dokazao da se program napisan u bilo kojem računarskom jeziku (u ovom slučaju to je C), može konvertovati u bilo koji drugi jezik, ako ciljni jezik može da simulira Tjuringovu mašinu. Kako je to sa Javom očigledan slučaj (ja ne znam konkretno nijedan simulator za Tjuringovu mašinu u Javi, ali bi me jako začudilo da na Internetu ne postoji bar nekoliko takvih) – ako smatrate da bi taj pristup bio dovoljno dobar, možete slobodno preskočiti ostatak ovog teksta.

Ovde ćemo se baviti praktičnom stranom problema: kako postići da program napisan u C-u, koji sabira brojeve od 1 do 1000, kada se konvertuje u Javu i izvrši u vašem browser-u, ne potraje „letnji dan do podne“, koliko autor slobodno procenjuje da bi izvršavanje „Tjuringove verzije“ potrajalo. Osnovni cilj nam je da rezultujući program što više liči na ono što bi programer napisao da mu je na raspolaganju bila Java umesto C-a.

Jedan od najvećih problema sa kojim se pisac jedne ovakve alatke susreće je nedostatak pokazivača u Javi, što je ujedno jedna od njenih prednosti. Java ne razume pojam direktno adresirane memorije, sva memorija se automatski zauzima (kada se instancira objekat, na primer) i oslobađa (kada nestane memorije, pa garbage collector oslobodi prostor koji su zauzimali objekti koji se više ne koriste). Umesto pokazivača, Java ima reference, koje se mogu posmatrati kao vrsta pokazivača sa prilično ograničenim mogućnostima.

Postoje bitne razlike između pokazivača i referenci u Javi. Pre svega, aritmetika pokazivača, onakva kakva je dozvoljena u C-u, ne postoji u Javi. Na primer, u C-u možete da napišete:

int a[10] = {0,1,2,3,4,5,6,7,8,9};
int* p = a;
p += 15;
foo(*p);

Iz ovog primera se direktno vidi zašto je ova osobina pokazivača opasna: dodavanjem 15 na vrednost pokazivača se izlazi van okvira alociranog niza i vrednost na koju p ukazuje je nedefinisana. U Javi ovako nešto nije moguće; jedini način da se pristupi nizu je preko odgovarajuće promenljive, što bi u našem slučaju rezultovalo pozivanjem foo(a[15]), dakle prekida prilikom izvršavanja programa.

Java je strogo tipizirani jezik; sve konverzije tipova su podložne proveri prilikom prevođenja i izvršavanja, pa česta konstrukcija koja se javlja u C-u nije dozvoljena:

int a[10];
double* p;
p = (double)a;
foo(p[3]);

Ovakav način pisanja programa je čest izvor grešaka koje je teško pronaći. Javin sistem tipova neće dozvoliti uzajamnu konverziju proizvoljnih tipova, pa ekvivalent gornjem programu napisan u Javi ne bi mogao ni da se prevede.

U Javi ne postoji mogućnost dobijanja adrese nekog objekta ili skalarne promenljive kao u C-u. Ovo je jedan od najčešćih uzroka grešaka u programu, tzv. „visećih referenci“ kao što je:

int* foo(){
int result;
   result = compute(...);
      return (&result); }

U ovom slučaju funkcija foo() vraća pokazivač na promenljivu result; na prvi pogled sve je ispravno. Ali, result je lokalna promenljiva funkcije foo(), pa se ona alocira na steku pre izvršavanja funkcije, što znači da se okvir oslobađa nakon izvršavanja funkcije foo(). Rezultat poziva foo() će neko vreme pokazivati na korektnu vrednost, jer se taj prostor na steku ne „uništava“ već se samo proglašava slobodnim – sve dok ne bude pozvana neka druga funkcija koja će upisati svoje podatke na to mesto. Pošto u Javi ne postoji način da dobijete adresu nekog objekta ili promenljive, ne postoji ni način da se formira „viseća referenca“.

Sve ove osobine idu u prilog Javi, jer obavezuju programera na disciplinovanije programiranje, ali otežavaju konverziju C-a u Javu. Mnogo veća „sloboda“ koju omogućavaju pokazivači u C-u mora nekako da se prevede u ograničen kontekst referenci u Javi, što nije lak zadatak.

Blok Model

Jedan od najočiglednijih pristupa ovom problemu bi bio da se sve promenljive čija se adresa koristi u C-u „obaviju“ u objekte u Javi. Definišemo klasu Block, koja će predstavljati osnovnu strukturu podataka koji se alociraju u memoriji. Podaci koji nas interesuju u C-u su skalarne promenljive (int, long, float, double) pokazivači i strukture. Za ove tipove podataka definišemo klase izvedene od Block: IntB, LongB, FloatB, DoubleB, PointerB i StructB. Ako sačuvamo parcijalno uređenje između blokova koje bi odgovaralo njihovom uređenju u memoriji koju C alocira, omogućićemo jednostavan pristup promenljivima, kao i mehanizam za aritmetiku pokazivača, što se lepo vidi na primeru sa slike 1 i Java programa sa slike 2.

Alociranje niza a je pretvoreno u alociranje niza a_, koji sadrži objekte tipa IntB – svaki od njih je blok koji odgovara po jednom elementu originalnog niza a, i svaki od njih je alociran na heap-u. Sam niz a je predstavljen kao StructB blok, pa se poziv funkcije sum izvršava pošto se kreira pokazivač na strukturu a. Blok PointerB je objekat koji „razume“ aritmetiku pokazivača, „meta“ pokazivača se čuva u promenljivoj target, a metodi increment(), decrement() menjaju tu vrednost – poziv increment() će promeniti vrednost target sa bloka IntB(1) na blok IntB(2).

Iako je ovaj način vrlo jednostavan za implementaciju i omogućava generalnu konverziju C-a u Javu, uključujući aritmetiku pokazivača, uzimanje adrese promenljivih i konverziju tipova pokazivača (čak i void* tip), metod je jako neefikasan. Metoda ne omogućava iskorišćavanje postojećeg modela za nizove u Javi, koji bi bio najprirodniji i najefikasniji način da se dati program konvertuje (slika 3).

Naravno, ovakav (napredniji) sistem mora strogo da vodi računa o tome da se nizovi iz C-a korektno prepoznaju, da se u originalnom C programu nigde ne uzima adresa od elemenata datog niza, da ne postoji slanje podnizova niza koji se konvertuje kao novih nizova i slično.

Poziv po referenci

Jedna od jako čestih primena pokazivača u C-u je implementacija call-by-reference (poziv po referenci) pozivanja procedura i funkcija. Tako funkcija može da menja vrednost promenljive. U Javi se po referenci pozivaju samo objekti i nizovi – ne postoji direktan način da se promenljive osnovnih tipova (int, float...) prenesu po referenci. Da bi se problem efikasno rešio, treba naći sve promenljive u programu kojima se uzima adresa i pretvoriti ih u objekte. U Javi već postoje klase koje opisuju objektnu verziju osnovnih tipova: Integer, Float... Na slici 4 je originalni C kod, a na slici 5 „prevod“.

Za svaku promenljivu koja se šalje funkciji preko poziva po referenci mora se alocirati objekat koji će sadržati vrednost te promenljive. Promenljiva koja se odnosi na taj objekat u Javi preuzima ulogu pokazivača. Dati primer se dodatno optimizuje ako se za „kontejnere“ koji sadrže konvertovane promenljive ne koriste ugrađene klase koje već postoje u Javi, već definišemo nove klase za osnovne tipove podataka, koje će imati javno (public) dostupne promenljive. Tim promenljivima se pristupa direktno, umesto da se pozivaju metodi setValue() i getValue(); tako naredbe (1) i (2) sa slike 5 postaju var.val++ i ptr.val++ respektivno.

public final class Int {
   public Int(int val) {
      This.val = val; }
   public int val; }

Drugi način da se prevede poziv po referenci je da se koriste jednoelementni nizovi umesto objekata:

int[] var = new int[1];
int[] ivar = new {5};
var[0] = 3;
var[0]++;
f (var);
int[] ptr = var;
ptr[0]++;
f (ptr);

Konverzija nizova

Konverzija nizova je posebno značajna, pošto se u većini računski intenzivnih programa nizovi eksploatišu do maksimuma. Konvertor mora biti u stanju da prepozna upotrebu pokazivača u C-u za pristup nizovima i da to prevede u Java nizove. Da bismo dozvolili proizvoljan pristup elementima niza (kreiranje podnizova), uvodimo dodatnu strukturu podataka koja pored Java reference na niz sadrži i trenutnu vrednost indeksa niza, koja odgovara trenutnoj vrednosti pokazivača u C-u. Na slici 6 je originalni C program koji koristi podnizove, a na slici 7 njegov Java ekvivalent.

Kreiranje pokazivača na podniz konvertovanog niza postiže se kreiranjem novog objekta IntPointer. Nema dupliranja podataka niza a: sve je jedinstveni niz, a svi kreirani pokazivači tipa IntPointer će sadržati samo referencu na a. Ovde je moguća još jedna optimizacija da bi se izbeglo indirektno adresiranje kroz objekte tipa IntPointer: umesto kreiranja takvog objekta, mogu se kreirati dve lokalne promenljive. Jedna od njih će sadržati referencu na niz a, a druga trenutni indeks.

Postoji suštinska razlika u načinu na koji Java i C predstavljaju višedimenzionalne nizove. Dok su u C-u višedimenzionalni nizovi u stvari samo sintaksni oblik, u Javi su višedimenzionalni nizovi zaista predstavljeni kao nizovi nizova. Prilikom konovih nizova iz C-a u Javu moramo simulirati C-ov način pristupa ovakvim nizovima, kao na slikama 8 i 9.

Sve to proizvodi Java program koji je značajno manje čitljiv nego originalni C program, ali je u pitanju žrtva koju moramo da prihvatimo. Ako analiza programa pokaže da nema „sumnjivih“ kreiranja pokazivača u podnizove kreiranih nizova, moguće je kreirati Java multidimenzionalne ekvivalente originalnim C-ovim nizovima.

Toliko o konverziji C-a u Javu; problem je daleko od potpuno rešenog, metode koje smo ovde opisali pokrivaju samo neke od poteškoća na koje bi konvertor naišao. C je jako „prljav“ jezik, koji programerima dozvoljava mnoge stvari zbog kojih se kasnije često kaju; navedimo kao primer union tipove i pokazivače na funkcije. Ako se rešite na implementaciju ovakvog konvertora, morali biste voditi računa i o mnogim drugim „sitnicama“. A imali bi i konkurenciju: pacevm.dac.pace.edu/~ny971734/c2j.html opisuje jedan od takvih projekata.

Potpuno automatski konvertor C-a ili C++-a u Javu, koji ne bi zahtevao intervencije programera, i ne bi postavljao ograničenja - tek treba napisati. Srećno!

slika 1

Main() {
   Int a[4] = {1,2,3,0};
   Printf("%d
", sum(a)); }
int sum(int *a) {
   int s = 0;
   while(*a !=0)
      s += *(a++);
      return s; }

slika 2

Main() {
   IntB[] a_ = {new IntB(1),
   new IntB(2), new IntB(3),
   new IntB(0)};
   StructB a=new StructB(a_);
   System.out.println
     (sum(new PointerB(a)));
}
int sum(PointerB a) {
   int s = 0;
   while (((IntB) a.target).
         val != 0) {
     s+=((IntB)a.target).val;
     a.increment();
   }
   return s; }

slika 3

Main() {
  intB a = {1, 2, 3, 0};
  System.out.println(sum(a)); }
int sum(int[] a) {
   int a_i = 0;
   int s = 0;
   while (a[a_i] != 0) {
      s += a[a_i ++]; }
      return s; }

slika 6

int a[5];
int *p = a;
p++;
*p = 5;
p[2] = 10;
foo (&(p[3]));
return p;

slika 7

public class IntPointer {
   public IntPointer
      (int[] a, int i) {
      this.a = a;
      this.i = i; }
   public int[] a;
   public int i;
}
int[] a = new int[5];
IntPointer p =
   new IntPointer(a,0);
p.i++;
p.a[p.i] = 5;
p.a[p.i+2] = 10;
foo (new IntPointer(a,p.i+3));
return(new IntPointer(p,p.i));

slika 4

int var;
int ivar = 5;
var = 3;
var++;
f (&var);
int *ptr = &var;
(*ptr)++;
f (ptr);

slika 5

Integer var=new Integer();
Integer ivar=new Integer(5);
var.setValue(3);
var.setValue((var.getValue())++); f (var);
Integer ptr = var;
ptr.setValue((ptr.getValue())++);
f (ptr);

slika 8

int a[3][4];
int b[3][4] = {{1,2},{3},{4,5,6,7}};
a[1][2] = b[2][1];
int *p = a;
int *q = b[2];

slika 9

int[] a = new int[3*4];
int[] b = {1,2,0,0,3,0,0,0,4,5,6,7};
a[1 * 4 + 2] = b[2 * 4 + 1];
int[] p = a; int[] q = b;
int q_i = 2*4;

SLEDEĆI TEKST U PC #35
nopreview
Uvodnik
Dejan Ristanović


.

PC
Twitter Facebook Feed Newsletter