A sada malo o C makroa ...

Šta najviše smeta C++-ašima u C-u. Pa makroi, i onda su ih prvo nazvali štetnim i lošim i zamenili nekim drugim mehanizmima (na sličan način štetnim, po meni). Da ne ulazim sada u tu priču, pokušaću da pokažem neke stvari koje se mogu uraditi standardnim makroima u C-u. Ovog puta izbeći cu priču o x-makroima, koga zanima neka pogleda https://en.wikipedia.org/wiki/X_Macro.

U jednoj od brojnih razmena misljenja sa dragim Mrkijem (uvek nesto naučim posle bar dva minuta priče sa njim) došli smo do retoričkog pitanja: Kako razrešavas u C-u a->b->c->d->e, ali da vrati NULL ako je bilo koji od a, a->b, a->b->c, a->b->c->d baš NULL. Prva ideja sa nekom funkcijom koja bi ... pa ček kako ćes funkciji proslediti ime? Ne ide. Ajde da napišemo konkretno neki kod, pa da vidimo kako bi to moglo da se ulepša, generalizuje, makroizuje.

if
(
  a == NULL ||
  a->b == NULL ||
  a->b->c == NULL ||
  a->b->c->d == NULL
)
  result = NULL;
else
  result = a->b->c->d->e;

Prvo što primećujem je da možemo ovu pitalicu da zamenimo sa omiljenim tenarnim ?:, ali ajde pre toga da razvijem gomilu or-ova. Zašto, pa eto, iskustvo mi govori da to treba uraditi :).

if(a == NULL)
  result = NULL;
else if(a->b == NULL)
  result = NULL;
else if(a->b->c == NULL)
  result = NULL;
else if(a->b->c->d == NULL)
  result = NULL;
else
  result = a->b->c->d->e;

Sada možemo da iskoristomo ?: i dobijemo izraz, koji se može koristiti, pa i dodeliti u neki result:

(a == NULL ? NULL : (a->b == NULL ? NULL : (a->b->c == NULL ? NULL : (a->b->c->d == NULL ? NULL : a->b->c->d->e))))

Kako bi bilo lepo da ovo mozemo da pozovemo recimo sa N(a, b, c, d, e). Eh, steta sto C makroi nisu tako moćni. Ili možda jesu?

Šta primećujem, da ako bi uzeli prva dva argumenta (a i b), zatim proverili da li je a jednako NULL pa vratili ili NULL ili rekurzivni poziv (umesto prva dva argumenta imamo a->b i ostatak). Treba još da obezbedimo izlazak iz rekurzije, što je jednostavno, kada ima samo dva argumenta zaustavi se tu. Ali ono sto je teži deo posla, to je sto C makroi ne podržavaju rekurziju. Šta uraditi?

Ajde da napišemo nekoliko funkcija, dogovorimo se da svaka poziva prehodnu, nazovimo ih N_2, N_3, N_4, ... dokle tako, pa ajde da se dogovorimo i da kazemo da nikada neće biti vise od 16 promenljivih u ovom nizu. Da ispišemo te makroe, barem do N_5:

#define N_2(a, b) (a == NULL ? NULL : a->b)
#define N_3(a, b, c) (a == NULL ? NULL : N_2(a->b, c))
#define N_4(a, b, c, d) (a == NULL ? NULL : N_3(a->b, c, d))
#define N_5(a, b, c, d, e) (a == NULL ? NULL : N_4(a->b, c, d, e))

Odlično, probamo sa gcc -E (prepuštam vama da proverite, ja verujem sebi, za sada :) ). Radi! Dobro, može ovako da se ispiše do N_16, pa i do N_100 ako zatreba i eto. Nije baš praktično, moramo da pozovemo tačnu funkciju, i složeno je za pisanje. Pa ajde da optimizujemo nekako. Primetimo da sve posle trećeg argumenta samo ponavljamo, dakle super, moze moja omiljena forma: ellipsis. Ne znam da li ste primetili, ali ja baš volim ellipsis ...

#define N_2(a, b, ...) (a == NULL ? NULL : a->b)
#define N_3(a, b, ...) (a == NULL ? NULL : N_2(a->b, __VA_ARGS__))
#define N_4(a, b, ...) (a == NULL ? NULL : N_3(a->b, __VA_ARGS__))
#define N_5(a, b, ...) (a == NULL ? NULL : N_4(a->b, __VA_ARGS__))

Ah, kako me nervira ovo ponavljanje oblika (x == NULL ? NULL : y), zameniću ga makrom _N. O istom trošku dodaću i N_0 i N_1, neka se nadju, zatrebaće možda.

#define _N(x, y) (x == NULL ? NULL : y)
#define N_0(...) NULL
#define N_1(a, ...) a
#define N_2(a, b, ...) _N(a, a->b)
#define N_3(a, b, ...) _N(a, N_2(a->b, __VA_ARGS__))
#define N_4(a, b, ...) _N(a, N_3(a->b, __VA_ARGS__))
#define N_5(a, b, ...) _N(a, N_4(a->b, __VA_ARGS__))

Ovo već liči na nešto, kada bi mogli nekako da izračunamo broj argumenata zadatih makrou i pozovemo odgovarajući makro. Nešto oblika:

#define N(...) N_##NUMBER(__VA_ARGS__)(__VA_ARGS__)

Na žalost, ne postoji ništa što moze da izracuna broj argumenata, osim da to sami ne napišemo kao makro. A i tada, nece doci do zamene, pa ajde da ubacimo koji makro više (više ćete saznato o tome kada naučite kako makroi rade, i kada/kako vrše zamenu):

#define N__(n, ...) N_##n(__VA_ARGS__)
#define N_(n, ...) N__(n, __VA_ARGS__)
#define N(...) N_(NUMBER(__VA_ARGS__), __VA_ARGS__)

Sve je to lepo, ali i dalje nam nedostaje makro NUMBER koji računa koliko je bilo argumenata.

Ideja je jednostavna, ako iza __VA_ARGS__ navedemo redom brojeve, pa uzmemo neki na fiksnoj poziciji i dobićemo duzinu. Naravno treba namestiti da lepo radi.

#define NUMBER_(x5, x4, x3, x2, x1, n, ...) n
#define NUMBER(...) NUMBER_(__VA_ARGS__, 5, 4, 3, 2, 1)

Ovo računa broj argumenata samo do duzine 5, ali eto, lako se da produžiti. Ne radi za prazan ulaz, ali i to se može srediti vezivanjem __VA_ARGS__ za prethodni argument. Na žalost to nije deo standarda, ali naravno gcc to guta, nadam se da će uskoro i to da prihvate u standardu. Naime x, ##__VA_ARGS__ će se razviti u samo x (nema zareza) ako je __VA_ARGS__ prazno, inace normalno se radi konkatenacija.

#define NUMBER_(x, x5, x4, x3, x2, x1, n, ...) n
#define NUMBER(...) NUMBER_(x, ##__VA_ARGS__, 5, 4, 3, 2, 1, 0)

Ha, imamo sve, sada možemo da spojimo, i da proširimo do recimo 16:

#define NUMBER_(x, x16, x15, x14, x13, x12, x11, x10, x9, x8, x7, x6, x5, x4, x3, x2, x1, n, ...) n
#define NUMBER(...) NUMBER_(x, ##__VA_ARGS__, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
#define _N(x, y) (x == NULL ? NULL : y)
#define N_0(...) NULL
#define N_1(a, ...) a
#define N_2(a, b, ...) _N(a, a->b)
#define N_3(a, b, ...) _N(a, N_2(a->b, __VA_ARGS__))
#define N_4(a, b, ...) _N(a, N_3(a->b, __VA_ARGS__))
#define N_5(a, b, ...) _N(a, N_4(a->b, __VA_ARGS__))
#define N_6(a, b, ...) _N(a, N_5(a->b, __VA_ARGS__))
#define N_7(a, b, ...) _N(a, N_6(a->b, __VA_ARGS__))
#define N_8(a, b, ...) _N(a, N_7(a->b, __VA_ARGS__))
#define N_9(a, b, ...) _N(a, N_8(a->b, __VA_ARGS__))
#define N_10(a, b, ...) _N(a, N_9(a->b, __VA_ARGS__))
#define N_11(a, b, ...) _N(a, N_10(a->b, __VA_ARGS__))
#define N_12(a, b, ...) _N(a, N_11(a->b, __VA_ARGS__))
#define N_13(a, b, ...) _N(a, N_12(a->b, __VA_ARGS__))
#define N_14(a, b, ...) _N(a, N_13(a->b, __VA_ARGS__))
#define N_15(a, b, ...) _N(a, N_14(a->b, __VA_ARGS__))
#define N_16(a, b, ...) _N(a, N_15(a->b, __VA_ARGS__))
#define N__(n, ...) N_##n(__VA_ARGS__)
#define N_(n, ...) N__(n, __VA_ARGS__)
#define N(...) N_(NUMBER(__VA_ARGS__), __VA_ARGS__)

Ah, a pa zato sam definisao N_0 i N_1 ... sada je i meni jasno :). Ostaje da sami proverite da li radi i da krenete da ozbiljno razmi[ljate o makroima u C-u.

P.S. Ako ste dokoni, uradite na slican nacin makro MAP(f, ...) koji na niz argumenata primenjuje (makro) f().

A sada malo sed-a

Svako ko je uzeo da uči shell scripting, pre ili kasnije upozna magičnu komandu sed. Malo ko zna sta znači njeno ime, kako je nastala, ali to je nešto što već može da se nadje svuda po netu. Uglavnom svi koriste kao u sledećem primeru

echo mama | sed 's/m/t/g'

Na stranu što to može da se uradi i nekom drugom jednostavnijom komandom (mislim na ovaj konkretni primer). Ali tu staje prica oko sed-a. Oni malo napredniji nauče sed komandu d, pa napišu nešto ovako:

last | sed '1,10\!d'

Dobro, možda im nije zatrebala sva ta genijalnost koju nosi u sebi komanda sed. A sada pravi razlog ovog posta.

Pre neki dan videh na facebook-u ovaj strip:

i u mom redovnom ..., da kažemo lošem ponašanju gde nipodaštavam one koji znaju manje od mene (znam da nije lepo, ali eto trudim se da ih prodrmam :) ) dodjemo do toga da

rm -rf /

neće da radi. Zašto, prosto postoji u samom kodu za rm komandu zaštita koja ne dozvoljava da argument bude / kao i neki alternativni načini zadavanja slash-a.

I naravno kako sam vec drčan, postavih zadatak: obrisati sve diskove ali iz sed-a :). Pre sam već koristio sed da pronadje apsolutnu putanju pozvanog shell skripta (molim one koji se bave jezikom da se ne uzbudjuju, znam da je plurale tantum, ali ne ide mi da kazem shell skripte kada je samo jedna skripta :) ). To se nalazi na mom sajtu kao primer lepog sed-a:

#!/bin/sh
echo $0|sed -e"
      \|^/|!{h
      s|.*|pwd|;e
    G;s|\n|/|};:x
      s|/[^/]*/\.\./|/|
      s|/\./|/|
      s|//|/|
      s|^/\.\.||;tx
      s|/[^/]*$||"

E sada, ako sam rekao da može, onda moram to i da pokažem. Evo ga sed-a koji prikazuje aktivne stalne diskove na sistemu, naravno ne brišem ih, ne želim da budem destruktivan, zaustavio sam se kod toga da ih samo prikaže:

#!/usr/bin/sed -f
1{s|.*|find /sys/block -type l|;e
s|/sys/block/||g;H;:l g;/^\n/!b e;s|^\n\([a-z0-9]*\).*$|cat /sys/block/\1/uevent|;e
/DEVTYPE=disk/!b n;g;s|^\n\([a-z0-9]*\).*$|cat /sys/block/\1/capability|;e
/^50$/!b n;g;s|^\n\([a-z0-9]*\).*$|cat /sys/block/\1/removable|;e
/^0$/!b n;g;s|^\n\([a-z0-9]*\).*$|cat /sys/block/\1/size|;e
/^0$/b n;g;s|^\n\([a-z0-9]*\).*$|\1|;p;:n g;s|^\n[a-z0-9]*\(.*\)$|\1|;h;b l;:e q}

Neću objašnjavati kako tačno radi, to prepuštam onima koji žele da uče, ali ukratko ovaj sed simulira shell i koristi find i cat komande, kao i /sys filesystem. Po startovanju trazi enter da bi zapoceo rad.

Eto, možda će neko sada posvetiti više vremena tome da prouči sed.

A ja, pokušaću da implementiram neku igricu jednostavnu u sed-u.

Malo JavaScript-a

Ima jedna čudna priča o meni i znanju nekih tehnologija. Šta god uradio u istoj, ja kažem da je ne znam :). Recimo da sam shvatam da ne znam dovoljno. Jedna od tih tehnologija koju "ne znam" je JavaScript.

Tokom mog razvitka igrao sam se svačim u JavaScript-u, ali na kraju sam rešio da koristim JavaScript klase koje kontrolišu neke HTML elemente (ah, koja mudrost, sigurno postoji gomila framewokr-ova koji to isto omogućavaju, ali ja volim da se ipak sam igram). Ono što želim da uradim je sledeće: u HTML-u imam nekoliko DIV-ova, svaki od njih treba da sadrži i kontroliše nezavisni brojac. To jest treba da ispiše u DIV-u trenutnu vrednost brojača, da ponudi mogućnost reseta i mogućnost inkremenisanja tog brojača. Naravno brojači treba da budu nezavisni.

Nikakva mudrost, napravimo DIV, smestimo BUTTON koji okida neku JavaScript funkciju i eto. Mogu reći da je to dovoljno dobro, sve dok ne poželite da dodate novi brojač (mozda dinamički ...). Od jednom imamo malo kopiranja koda i tu može doći do problema. Zato ja idem drugim putem. Kada se učita HTML, ja ću da povežem DIV i neki objekat odgovarajuće klase. Ta klasa ce da ispiše sve što treba i da održava svoju instancu brojača. Problem nastaje kod samog ispisa onclick="this.increment()". To neće raditi jer se this odnosi na konkretan HTML element. Moramo nekako da prosledimo globalno ime kojom pristupamo odredjenoj instanci:

function Counter(name, draw_id)
{
  this.name = name;
  this.draw_id = draw_id;

  this.draw = function()
  {
    var html =
      'Name: '+this.name+'<br/>'+
      'Count: '+this.count+'<br/>'+
      '<button onclick="'+this.name+'.reset();">Reset</button><br/>'+
      '<button onclick="'+this.name+'.increment();">Increment</button>';
    document.getElementById(this.draw_id).innerHTML = html;
  };

  this.reset = function()
  {
    this.count = 0;
    this.draw();
  };

  this.increment = function()
  {
    this.count++;
    this.draw();
  };

  this.reset();
}

function init()
{
  c1 = new Counter('c1', 'd1');
  c1.increment();

  c2 = new Counter('c2', 'd2');
  c2.increment();
  c2.increment();

  c3 = new Counter('c3', 'd3');
  c3.increment();
  c3.increment();
  c3.increment();
}

Ovaj primer možete ovde videti: http://www.chupcko.org/blog/counter_1.html.

Šta mi se ovde ne svidja? Dva puta moramo da napišemo ime, jednom kao promenljivu, a jednom kao string. Kada bi mogli nekako ... nešto ... I tu se setim jednog malog trika, dodajem na kraju klase sledeće:

  window[this.name] = this;

I sada možemo da inicijalizujemo samo sa:

function init()
{
  new Counter('c1', 'd1');
  c1.increment();

  new Counter('c2', 'd2');
  c2.increment();
  c2.increment();

  new Counter('c3', 'd3');
  c3.increment();
  c3.increment();
  c3.increment();
}

Ovaj primer možete ovde videti: http://www.chupcko.org/blog/counter_2.html.

Kada bi mogli nekako da dobijemo za neku instancu neke klase u JavaScript-u njegovo ime ... Pa ček, JavaScript ima nešto mnogo lepo, možemo uz pomoć Object.prototype da dodajemo nove funkcije koje važe za sve objekte. Ideja je da dodamo dve funkcije, neka se jedna $id i neka vraća neki id instance objekta. A druga $name koja vraća ime (u kojem naravno dominira spomenuti id). Sve to zatvoreno u closure (zbog globalne promenljive koja se koristi za id), i uz malo keširanja:

(
  function()
  {
    var _id = 0;
    Object.prototype.$id = function()
    {
      if(typeof this.$_id === 'undefined')
      {
        this.$_id = _id;
        _id++;
      }
      return this.$_id;
    };
    Object.prototype.$name = function()
    {
      if(typeof this.$_name === 'undefined')
      {
        this.$_name = '$$_'+this.$id();
        window[this.$_name] = this;
      }
      return this.$_name;
    };
  }
)();

function Counter(draw_id)
{
  this.draw_id = draw_id;

  this.count = undefined;

  this.draw = function()
  {
    var html =
      'Name: '+this.$name()+'<br/>'+
      'Count: '+this.count+'<br/>'+
      '<button onclick="'+this.$name()+'.reset();">Reset</button><br/>'+
      '<button onclick="'+this.$name()+'.increment();">Increment</button>';
    document.getElementById(this.draw_id).innerHTML = html;
  };

  this.reset = function()
  {
    this.count = 0;
    this.draw();
  };

  this.increment = function()
  {
    this.count++;
    this.draw();
  };

  this.reset();
}

function init()
{
  var c1 = new Counter('d1');
  c1.increment();

  var c2 = new Counter('d2');
  c2.increment();
  c2.increment();

  var c3 = new Counter('d3');
  c3.increment();
  c3.increment();
  c3.increment();
}

Ovaj primer možete ovde videti: http://www.chupcko.org/blog/counter_3.html.

I na kraju malo ulepšano: http://www.chupcko.org/blog/counter_4.html.

Naravno sve ovo može i na drugi način, ali ostaviću vama da ga sami pronadjete (igranje DOM-om :) ).

Sortiranje ...

Naravno većina je pomislila da ću pričati nesto o algoritmima sortiranja. Neću, pokušaću da napišem program koji sortira nekoliko promenljivih. Konkretno 3 :).

Poučen negativnim iskustvom izbora mladih programera, a bogami i starijih, uz ideju Dušana Milanova počeo sam da na intervijuima zadajem zadatak da se napiše mali program za sortiranje tri promenljive. Recimo da imate tri celobrojne promenljive a, b i c i da želite da po zavrsetku programa/algoritma/koda važi da je a <= b <= c. Hoce reći da ih sortirate u neopadajući niz :).

Svačega sam se naslušao, neću ni da pokušavam da se setim svega toga. Zar vam deluje to kao težak zadatak ako mislite da se bavite programiranjem?
Ispada da jeste težak zadatak za mnoge. Ako mislite da ste programer, prestanite sa čitanjem ovde i pokušajte da sami napravite neku svoju verziju.

Pa da krenemo, po meni sortiranje tri promenljive je dosta složeno, pa bi ja da prvo uradimo sortiranje dve promljive:

void sort2(int* a, int* b)
{
  if(*a > *b)
    swap(a, b);
}

Naravno sada možemo da koristeći sort2 uradimo sort3:

void sort3(int* a, int* b, int* c)
{
  sort2(a, b);
  sort2(a, c);
  sort2(b, c);
}

Da li je to bilo teško? Po meni je dosta logično. sort2 je nekako intutivan, neću ni da pokušam da ga opravdam. sort3 je ono što bi prvo uradili i napisali, da uredimo svakog sa svakim. Naravno pitanje je da li to može bolje?

Ajde da prvo analiziramo ovaj kod, uzmimo da su a, b i c iz skupa {2, 3, 5} i različiti (što ne 4, eto iz hira, uzeo sam proste brojeve):

a	b	c	swaps
2	3	5	0
2	5	3	1
3	2	5	1
3	5	2	2
5	2	3	2
5	3	2	3

Uvek će biti 3 poredjenja, ali brojimo swapove, jedino ono na kraju mi ne pije vodu, ocigledno da moze samo sa jednim swapom.
Gde je problem? Za prvi sort2 treba izabrati nešto što je neminovno, ali što ne moze pokvariti redosled. Ako bi izabrali da prvo uradimo sort2(a, c) nećemo puno pokvariti. Dakle sada je progam ovakav:

void sort3(int* a, int* b, int* c)
{
  sort2(a, c);
  sort2(a, b);
  sort2(b, c);
}

Pogledajmo sada koliko će biti swapova:

a	b	c	swaps
2	3	5	0
2	5	3	1
3	2	5	1
3	5	2	2
5	2	3	2
5	3	2	1

Ovo sada već deluje optimalno po broju swapova, ali kako stoje stvari sa brojem poredjenja. Može se uraditi sa minimalno 2 poredjenja a ne uvek sa 3. Doduše izgubićemo optimalnopst po broju swapova. Kako znamo da ćemo izgubiti optimalnost po broju swapova, pa tako što poredjenje a i c mora doći na kraju. Dva prva poredjenja koja moramo da izvršimo su a sa b i b sa c. Ako nam je poredjenje skupo, primenićemo recimo:

void sort3(int* a, int* b, int* c)
{
  sort2(a, b);
  if(*b > *c)
  {
    swap(b, c);
    sort(a, b);
  }
}

Doduše opet u nekim slučajevima imamo testiranje viška, recimo za slučaj 2, 5, 3. Koje je rešenje, pa i nema ga :). Najbolje što možemo je da napustimo ovaj lep koncpet svodjenja sort3 na sort2 i napisemo mrežu testova.

void sort3(int* a, int* b, int* c)
{
  if(*a < *b)
  {
    /* a < b */
    if(*b < *c)
    {
      /* a < b && b < c => a, b, c */
    }
    else
    {   
      /* a < b && c < b */
      if(*a < *c)
      {
        /* a < b && c < b && a < c => a, c, b */
        swap(b, c);
      }
      else
      {
        /* a < b && c < b && c < a => c, a, b */
        swap(a, c);
        swap(b, c);
      }
    }
  }
  else
  {
    /* b < a */
    if(*a < *c)
    {
      /* b < a && a < c => b, a, c */
      swap(a, b);
    }
    else
    {
      /* b < a && c < a  */
      if(*b < *c)
      {
        /* b < a && c < a && b < c => b, c, a */
        swap(a, b);
        swap(b, c);
      }
      else
      {
        /* b < a && c < a && c < b => c, b, a */
        swap(a, c);
      }
    }
  }
}

Šta je sada zanimljivo, i dalje imamo utisak da može bolje, ali eto ja ne znam kako. Po broju swapova ne može, to je to, ali nekada imamo suvišne testove, recimo za slučaj 5, 3, 2. Ovaj kod je već dosta složen i nepregeldan. Da li je bolje ostaviti sladak i fin kod ili ići na totalnu optimizaciju.

I ovde stajem. Za razmišljanje je sledeće: kako uraditi sort4 recimo. Naravno koristeći sort2 i sort3 :). Za one baš napredne, nadjite paralelu izmedju raznih algoritama sortiranja i raznih realizacija sort4 (sortn). Možda o tome nekada.

P.S. Inače, većina zna, nisam baš neki pristalica C++, ali često čujem kako je std::sort iz C++ brži od qsort u C-u. Jeste, istina je, ne baš zbog toga što je C++ brži/bolji/moćniji jezik od C-a, nego zato što std::sort koristi introsort i direktno ugradjuje funkciju za komparaciju za razliku od qsort koji koristi quick sort i pozivanje funkcije za komparaciju :).

Da krenemo ...

Ovaj blog  će generalno biti posvećen programiranju, za sada na srpskom, bez nešto previše mudrosti. Više kao mesto gde ću da se hvalim svojim nekim glupostima. Koga ne zanima, neka samo produži dalje, kritike neću da gledam :).

Svi vi koji ste gledali moj sajt, očekujte tako nešto i ovde.