A program belső univerzuma

Már említettem, hogy amikor programozunk, akkor egy elképzelt univerzumban mozgunk, ott hozunk létre mindenféle lényeket. Talán az egyetlen nehézsége az egész folyamatnak, hogy ezt az univerzumot a folyamat során nem látjuk, de muszáj elképzelnünk. Például tegyük fel, hogy olyan programot akarunk írni, amiben két képzeletbeli játékos egymással sakkozik. Akkor a programnak létre kell hoznia a két játékost, a maguk tudásával és képességeivel, és aztán felváltva megkérni őket, hogy lépjenek a képzeletbeli sakktáblán. De mi, akik mindezt megalkotjuk, ebből semmit sem látunk, csak adatokat kezelünk valamilyen módon, és ezek az adatok határoznak meg mindent, a tudásukat és képességeiket, meg az eseményeket, amik majd a program futásakor megtörténnek.

Hol lakik a program?

Hol laknak ezek a nem látható lények? Természetesen majd a számítógépben fognak lakni, amikor a programot elindítjuk, közelebbről a számítógép memóriájában, amit egy nagy adattároló térnek fogunk elképzelni (bár a valóságban ez is bonyolultabb, több részből tevődik össze). A memóriának az a lényege, hogy a programok töltik meg adatokkal, és a programok tudják kiolvasni belőle az adatokat, és amikor egy program befejezi a futását, akkor a hozzá tartozó adatok végleg eltűnnek. 

Persze tárolhatunk adatokat adathordozókon is (merevlemezen stb.), és az ilyen adatok a program futása, sőt a gép kikapcsolása után is megmaradhatnak, de ezt egyelőre hagyjuk, tekintsük extra lehetőségnek, amit majd szintén fogunk használni. Bármilyen képzeletbeli lény, amit megalkotunk, és annak bármilyen része valamilyen adatnak fog megfelelni valahol a gép memóriájában. Úgy is mondhatjuk, hogy ezek az adatok ábrázolják (reprezentálják) a lényeinket. Legalább két dolgot tudnunk kell róluk, hogy használni tudjuk őket: először is azt, hogy hol vannak, hogyan találhatjuk meg őket, másodszor pedig azt, hogy hogyan ábrázolják a lényeket, hogyan kell értelmeznünk őket.

Ami a tárolás helyét illeti, az a valóságban egy címnek felel meg (úgy képzelhetjük el, mint egy sorszám, mondjuk egy rekesz vagy postafiók száma), de a programokban mi általában valamilyen nevetelnevezést fogunk használni minden adatunk azonosítására, és a neveket mi fogjuk adni nekik. Ami pedig az ábrázolás módját illeti, azt is nekünk kell kitalálnunk. Általában elég sok fejtörésbe szokott kerülni, hogy egy-egy képzeletbeli lény praktikus, később minden szempontból jól használható ábrázolását kitaláljuk.

A belső univerzum persze nemcsak a memóriából (és a benne tárolt lényeinkből) áll. Talán a legfontosabb, hogy ha körbenézünk, találunk mindenféle perifériát – így hívnak mindent, ami a külvilággal kapcsolatban van: billentyűzet, képernyő, adathordozók stb. Ezekkel muszáj időnként kapcsolatba lépni, hogy legyen egyáltalán valami külső jele annak, amit a programunk csinál (ehhez ki kell bocsátania mindenféle jeleket), illetve hogy kívülről befolyásolni tudjuk a működését (ehhez meg kintről be kell olvasnia mindenféle jeleket). És a memórián meg a perifériákon kívül is sok minden van még a számítógépben, bár ezekkel közvetlenül csak ritkán lesz dolgunk. Például van benne egy operációs rendszer. Ez valójában egy csomó program, amit nem mi írtunk, de ezek annyira fontos és hasznos feladatokat látnak el, hogy nélkülük a mi programunk se tudna futni. Az a jó bennük, hogy szinte észrevétlenül teljesítik minden kívánságunkat. Például az ő közvetítésükkel tudunk kapcsolatba lépni a perifériákkal (meg magával a processzorral is, ami az összes szükséges számítást elvégzi).

Hogyan ábrázolható a pikk ász?

Grafika: Tóth Róbert Jónás

Vegyünk egy példát az ábrázolásra. Tegyük fel, hogy valamilyen kártyajátékkal kapcsolatos programon dolgozunk, rendes, 52 lapos francia kártyával. Ehhez minimum az kell, hogy egy kártyapakli lapjait ábrázoljuk. Számtalan lehetőség van, például használhatunk egy-egy számot egy-egy lap ábrázolására, így 52 számra van szükségünk (1-től 52-ig, vagy inkább 0-tól 51-ig, ez a szokás). De mivel fontos lesz, hogy melyik lap melyik színhez tartozik (treff, káró, kőr vagy pikk), és mi az értéke (2-től 10-ig, plusz bubi, dáma, király, ász), ezt is ábrázolnunk kell. Többféleképpen is eljárhatunk, például megtehetjük, hogy nem egy, hanem két számot használunk minden lap ábrázolásához: az első szám 0 és 3 között lesz, és a lap színét ábrázolja (0 = treff, 1 = káró, 2 = kőr, 3 = pikk), a második pedig 0 és 12 között, ez a lap értékének felel meg. Egyébként ha ügyesek vagyunk, nincs is szükségünk 52 számpárra, mert abban is megegyezhetünk, hogy a 0-tól 51-ig terjedő számokból olvassuk ki a színt és a lap értékét. Például úgy vesszük, hogy 0-tól 12-ig vannak a treff lapok (növekvő értékűek), 13-tól 25-ig a káró lapok (szintén növekvő értékkel), 26-tól 38-ig a kőr lapok, és 39-től 51-ig a pikkek. Így nem kell számpárokkal bajlódnunk, viszont néha el kell osztanunk a lapok sorszámát 13-mal, és akkor a hányados egész értéke adja meg a kártya színét, az osztás maradéka pedig az értékét. Például a 28 sorszámú lap színe kőr (mert a 28/13 egész értéke 2 = kőr), értéke pedig 4-es (mert a 28/13 osztás maradéka 2, és a lapértékeket 0-tól számozzuk: a 0 a 2-es lapot, az 1 a 3-as lapot, a 2 pedig a 4-es lapot ábrázolja).

Azt láttuk tehát, hogy a francia kártyapakli 52 lapját sokféleképpen ábrázolhatjuk, a lényeg az, hogy egyértelmű legyen az ábrázolás, és hogy minden lap ábrázolásából könnyen le tudjuk olvasni a színét és az értékét. Akár egy-egy számmal, akár egy-egy számpárral, akár más módon ábrázolunk egy-egy lapot, a memóriában 52 ilyen egység fog megfelelni a paklinak. Ezeket nyilván egyetlen helyen fogjuk tartani, lesz az egész paklinak egyetlen címe a memóriában, és tudni fogjuk, hogy az ott kezdődő 52 egységnyi hely (ún. tömb, angolul: array) ezt a célt szolgálja, és csak erre szabad használnunk. Miért van szükségünk arra, hogy ténylegesen jelen legyen ez az 52 egység a memóriában? Azért, mert például minden kártyajátékban szerepet játszik az, hogy a lapokat néha megkeverjük, amit muszáj valahogy ábrázolnunk. A legegyszerűbb ezt úgy ábrázolni, hogy a keverés után ugyanebben az 52 nagyságú tömbben lesz ugyanez az 52 adat (vagyis a lapok ábrázolása), csak más, össze-vissza sorrendben. A keverés utáni sorrend ábrázolására nincs sokkal egyszerűbb módszer, mint ez.

Program = adat + algoritmus

Edsger Dijsktrától származik az a meghatározás, hogy a program nem más, mint adatok és algoritmusok összessége (és ez van a címében Niklaus Wirth híres könyvének is). Például a francia kártyás példánkban eddig két adatszerkezetünk van: a kártyalapok és maga a pakli (amiben a lapok egy bizonyos sorrendben vannak). És lesz két algoritmusunk is: az egyik, ami egy kártyalap ábrázolásából kihámozza a lap színét és értékét, és a másik, ami összekeveri egy pakli lapjait.

Ahogy az ábrázolás is nagyon sokféle lehet, különböző célokra különböző ábrázolásokat használhatunk, meg az is lehet, hogy mindegy, melyiket használjuk, ugyanígy egy-egy algoritmust is sokféleképpen megfogalmazhatunk, és néha számít, hogy melyiket választjuk, néha pedig nem. Például milyen lehet egy kártyakeverő algoritmus? Tegyük most félre ezt a kérdést, hogy hogyan lehet véletlenszerűen választani egy-egy lapot egy pakliból, vagy véletlenszerű helyet találni egy lapnak a pakliban. Ehhez olyan programra van szükség, ami képes véletlenszerű (angolul: randomszámokat előállítani, és azzal most nem foglalkozunk, hogy ez hogyan lehetséges. Tegyük fel, hogy hozzáférünk ilyen programhoz, és azt használjuk a virtuális kártyakeveréshez. De hogyan?

Hogy algoritmusra is lássunk példát, elmondok egy megoldást (nyilván más megoldások is vannak). Csináljunk helyet a memóriában az összekevert paklinak (ehhez ugye egy 52 egységnyi tömbre lesz szükségünk). Ezek után „rendeljünk” a külső programunktól egy véletlenszerű számot 0 és 51 között, és a kapott számnak megfelelő lapot tegyük az első helyére ennek az előkészített tömbnek. Ezután távolítsuk el a kiválasztott lapot az eredeti paklinkból, ami így már csak 51 lapból áll, vagyis egy 51 egységnyi tömböt foglal el. Ezután pedig ismételgessük a fenti eljárást még ötvenszer: kérjünk egy véletlenszerű számot 0 és 50, aztán 0 és 49 között, és így tovább, a kapott lapot tegyük az előkészített tömb második, harmadik stb. helyére, és mindig távolítsuk el a kiválasztott lapot az eredeti pakliból, ami aztán már csak 50, 49 stb. egységnyi tömböt foglal el. A végén marad egyetlen lapunk az eredeti pakliból (itt már nincs szükségünk több véletlen számra), ezt rakjuk az előkészített tömbünk utolsó helyére, és készen vagyunk.

A sorozat a jövő héten folytatódik. A szerző nyelvész, az MTA Nyelvtudományi Intézetének főmunkatársa.

Ott van a nyelved hegyén, de nem tudod kimondani? Nem vagy egyedül!

Mindannyiunkkal előfordul, hogy egy-egy teljesen hétköznapi szó kimegy a fejünkből, de már majdnem eszünkbe jut. A jelenség utalhat valami komoly bajra is, de nem kell rögtön aggódni: teljesen normális, hogy már megint tepsiütőnek hívtad a serpenyőt, sőt, ha tornáztatod egy kicsit az agyad, még jót is tehet az, ha egy szó a nyelved hegyén van, mégsem tudod kimondani.

Mit üzennek egymásnak a növények?

A növények olyan fokú kémiai diverzitást állítanak elő, amit talán most még felfogni sem vagyunk képesek. Parádi István, az ELTE TTK Növényélettani és Molekuláris Növénybiológiai Tanszék egyetemi adjunktusának előadása a márciusi Budapest Science Meetupon.