„Adatszerkezetek”
tantárgy , 1. félév
1. előadás’2009
(vázlat)
1. Adatok jellemzői
1.1. Azonosító
Az a jelsorozat, amellyel hivatkozhatunk a tartalmára, amely által módosíthatjuk tartalmát.
Például:
|
i, j, n, a |
– változók nevei (szimbolikus nevek) |
|
p, -128, 3.14, "Eredmény=", IGAZ |
– konstansokat azonosító jelsorozat |
|
Megjegyzés: |
x |
:= |
x+1 |
|
|
címhivatkozás |
|
értékhivatkozás |
|
|
vagy |
|
|
|
|
Feldolgoz(x) |
– |
eljáráshívásnál
nem látszik, hogy x az adat címét vagy értékét jelenti |
|
|
Eljárás
Feldolgoz(Változó x:TX): |
– |
Ez
már világos beszéd! |
1.2. Hozzáférési jog
Adatokat módosítani, illetve értéküket lekérdezni, használni lehet; eszerint egy adat hozzáférés szempontjából négyféle lehet:
|
|
módosítható |
lekérdezhető |
|
|
Független |
Nem |
Nem |
Független |
|
Input |
Nem |
Igen |
Konstans |
|
Output |
Igen |
Nem |
Virgin |
|
I/O |
Igen |
Igen |
Változó |
|
Háttértár-adat |
|
|
Memória-adat |
1.3. Kezdőérték
A születéskor hozzárendelt érték. Változóknál deklarációban kaphat értéket, vagy eleve van típushoz rendelt kezdőérték, esetleg speciális ’nem definiált’ érték[1], s így akkor mód van hivatkozás ellenőrzésre is (virgin)!
1.4. Hatáskör
A programszöveg azon tartománya, amelyben az adathoz a hozzáférés lehetséges.
Gondoljunk a blokkstruktúrájú programozási nyelvek egymásba ágyazódó adatdeklarációira! Így beszélhetünk: globális és lokális (sőt saját) adatokról.
A hatáskört „színezi” a láthatóság kérdése: ha egy adat azonosítója megegyezik egy olyan adatéval, amelynek hatáskörébe esik, akkor azt elérhetetlenné teszi a saját hatáskörében, hiszen az adott név alatt neki van elsősége. Ez az ún. „luk a hatáskörben” jelenség.
|
Példa: |
|
… Konstans … Eljárás
E1(Változó x:TX2): … |
1.5. Élettartam
A futási időnek az az intervalluma, amelyben az adat azonosítója mindvégig ugyanazt az objektumot jelöli.
Meggondolandó a az élettartam hatáskörrel való kapcsolata! Globális –azaz a legfelsőbb szinten deklarált–, lokális –pl. egy eljárásban vagy függvényben deklarált– adatok hatásköre és élettartama bizonyos értelemben azonos, amíg a „dinamikus” –azaz futásközben, a programozó döntése szerint születő és megszűnő– adatok esetében már nincs meg az előbbi pontos párhuzam. L. később!)
1.6. Értéktípus
Az adatoknak az a tulajdonsága, hogy értékei mely halmazból származnak (értékhalmaz) és tevékenységeknek (eljárások, függvények, operátorok) mely „készlete, amely létrehozza, felépíti, lerombolja és részekre bontja”, alkalmazható rá (asszociált műveletek).
2. Az értéktípus
2.1. Az értéktípusról általánosságban
Összetettség (strukturáltság) szempontjából:
- skalár (vagy strukturálatlan)
- összetett (más szóval strukturált)
Adatstrukturálási módok:
|
→ |
|||
|
→ |
Rekord |
||
|
(Megkülönböztetett) egyesítés |
→ |
Alternatív rekord |
|
|
Halmazképzés |
2A |
→ |
Halmaz |
|
Iterált-képzés |
A* |
→ |
Sorozatfélék |
2.2. Az asszociált műveletek osztályozása
Az asszociálható műveleteket csoportosítjuk:
- értékadás (azonos típusúak közötti adatmozgatás: másolatkészítés, értékmegosztás),
|
Példa: |
|
… Eljárás
Eltol(Változó p:TPont;Konstans
D:TPont): … |
· típusátviteli függvények:
o Konstrukciós műveletek (strukturált érték létrehozása)
|
Példa: |
|
… |
o Szelekciós operációk
|
Példa: |
|
… |
o Azonosság és más relációk
|
Példa: |
|
… Típus Konstans
SNapEn= … |
|
Példa: |
|
… Konstans |
o Min és Max típusoperátor, amelyek értelemszerűen csak rendezett típusok esetén léteznek. Nem keverendő össze az adatokra (nem típusokra!) alkalmazandó függvényekkel!
|
Példa: |
|
… Konstans |
- Sorszám- (vagy Rend-) függvény
|
Példa: |
|
… |
o
Be/Ki műveletek (konverzió az
input/output és belsőábrázolás között)
|
Példa: |
|
… |
- Transzformációs
(a típuson értelmezett, a típusra képező függvények)
|
Példa: |
|
… |
3. Egyszerű Adattípusok
Alábbiakban definiáljuk az „eredendően” szerkezetnélküli ún. skalár típusokat, megadva ezek értékhalmazát, a hozzátapadó műveletek, relációk halmazát. Két típus „lóg ki” ezek közül. A szöveg (string) és a mutató típus. A szöveg típust azért soroljuk ide, mert a programozási nyelvek majd mindegyike fölkínálja, s így hozzátartozik az ún. elemi (natív) típusokhoz, másrészt abban jócskán eltér a későbbiekben tárgyalt összetettektől (s így oda még kevésbé illik), hogy elemeinek típusa nem választható meg szabadon. A mutató típus valóban szerkezet nélküli, hisz értékhalmaza a memóriacímek egy részhalmaza (ezért tárgyaljuk itt), de az is kétségtelen, hogy oly szorosan tapad valamely összetett típushoz, amely címét tartalmazza, hogy anélkül értelme sem lenne bevezetni.
A tárgyalt típusokról a következőket adjuk meg:
- Értékhalmaz
- Kezdőérték,
amit az ilyen típusú objektum létrejövetelekor kap.[3]
- Asszociált
műveletek
- (s esetleg) tipikus ábrázolása(i)
- (s néhány esetben) példa.
A rövid leírás kedvéért időnként alkalmazni fogjuk a Típ jelölést az éppen tárgyalt típusra való hivatkozásra. (Értelemszerűen akkor, amikor a típus nevét a programozó feladata megadni.) Származtatott típus esetén pedig gyakorta a TB az ún. bázistípusra (amelyből kiindulunk) utal.
3.1. Elemi adattípusok
3.1.1. Egész
|
Értékhalmaz |
-32768..32767 Ì
Z |
|
Kezdőérték |
0 |
|
Műveletek |
+, –, *, Div (egészosztás), Mod, - (unáris mínusz), ^ (pozitív egészkitevős
hatványozás) =, <, ≤, ≥, >, ≠ |
|
Ábrázolás |
ún. (16-bites) kettes komplemens kódú |
Megjegyzés:
A
programozási nyelvek többféle értékhalmazzal is felkínálnak efféle típusokat.
Pl. a Turbo Pascal megkülönböztet BYTE, SHORTINT (8 bites); INTEGER, WORD
(16-bites); LONGINT (24 bites)… Ennek ellenére nem tartjuk fontosnak az
algoritmikus nyelvben ezeket megkülönböztetni, annál is kevésbé, mert ha kell,
a „szélsőséges értékeire” tudunk hivatkozni a Min’Egész és Max’Egész
típusfüggvénnyel anélkül, hogy letennénk a voksunkat bármelyik konkrét
értékhalmaz mellett.
3.1.2. Valós
|
Értékhalmaz |
???..??? Ì
R |
|
Kezdőérték |
0.0 |
|
Műveletek |
+ , – , *
, /, -
(unáris mínusz), ^ =,
<, ≤,
≥, >,
≠ |
|
Ábrázolás |
ún. lebegőpontos
ábrázolás (pontosabb lenne, ha e típust racionálisnak neveznénk,
mert csak racionális számot képes ábrázolni), vagy |
Megjegyzések:
Vegyük észre, hogy ugyanazok a műveleti jelek most –ha hasonló jelentéssel is, de– mégsem egészen ugyanazzal a jelentéssel bírnak. (Polimorfizmus.)
Itt már föl sem vállaltuk az értékhalmaz pontosítását, mivel ez sokkal inkább implementációfüggő, mint az egész számoké.
3.1.3. Logikai
|
Értékhalmaz |
Hamis..Igaz Í L |
|
Kezdőérték |
Hamis |
|
Műveletek |
nem, és,
vagy =, <,
≤, ≥, >, ≠ |
|
Ábrázolás |
0 ≡ Hamis,
–1 ≡ Igaz – azaz (valamely) egész típusra visszavezetés; |
3.1.4. Karakter
|
Értékhalmaz |
0..255 -kódú jelek |
|
Kezdőérték |
Min’Karakter |
|
Műveletek |
Karakter(.) – Karakter:
Egész→Karakter =, <,
≤, ≥, >, ≠ |
|
Ábrázolás |
Valamely kódrendszer szerinti kód, mint előjelnélküli szám. (Fix bitszámú kód.) |
Megjegyzés:
Sokfajta kód rendszer létezik (legismertebbek: ASCII, UNICODE). Többségük fix bitszámú (ASCII 8 bites, UNICODE 16 bites), de elképzelhető változó bitszámmal dolgozó is. (L. Huffman-kódolás.)
3.1.5. (Absztrakt)Felsorolástípus
|
Értékhalmaz |
(konstans1, konstans2, ... , konstansN) (Típ jelölje a típus azonosítóját) |
|
Kezdőérték |
Min’Típ vagy NemDef |
|
Műveletek |
Következő(Típ-típusbeli
érték), – Következő: Típ→Típ
U
{NemDef} =, <,
≤, ≥, >, ≠ (a felsorolás sorrendje egyben rendezés
is) |
|
Ábrázolás |
A minimálisan szükséges bitszámú (»log2(Számosság’Típ)) kód, mint előjelnélküli szám. |
Megjegyzések:
Az értékhalmazban szereplő, ismétlődés nélküli, szimbolikus nevek (a típus konstansai) nem lehetnek más típus (pl. egy másik felsorolástípus) értékhalmazában, ez a feltétel amiatt szükséges, mert a fordítóprogram így mindig egyértelműen el tudja dönteni a konstans „hovatartozását”. Természetesen „…” nem szerepelhet a felsorolásban, mivel a fordítónak nincsenek „előzetes elképzelései” arról, hogy mik lehetnének ott a felsorolásban.
Mindazon típusokat, amelyek értékkészletét konstansainak egyszerű fölsorolásával adhatunk vagy adhatnánk meg diszkrét típusnak hívjuk. Tehát ilyen az Egész, a Logikai, a Karakter, de lehet bármilyen –a program írója által kreált– absztrakt konstansokat tartalmazó fenti absztrakt felsorolástípus is.
|
Típus |
3.1.6. (Rész)Intervallumtípus
Csak diszkrét típusból származtatható egyszerű típus. Jelöljük a bázistípust TB-vel.
|
Értékhalmaz |
konstans1..konstans2 Í TB |
|
Kezdőérték |
Min’Típ vagy NemDef |
|
Műveletek |
TB-vel megegyező műveletek (korlátozva persze az értékhalmazra) |
|
Ábrázolás |
TB-vel megegyező ábrázolás |
|
Példa: |
|
Típus
|
Megjegyzések:
1. Érdekes anomáliára vezet a Sorszám és Típ típuskonstrukciós függvény következetes bevezetése. Miért?
2. Ha a diszkrétségtől eltekintünk, kiterjeszthető a Valósakra is az intervallumtípus-képzés. Ez persze csak azzal a többlettel képzelhető el, hogy egy lépésközt is megadunk a származtatáshoz (amelyre vannak persze elvárások).
3. További általánosítás lehetséges: nem első és utolsó elem által meghatározott része egy értékhalmaznak, hanem valamilyen (predikátummal definiált) tulajdonságnak eleget tevő elemeinek részhalmaza.
|
Példa: |
|
Típus |
3.1.7. Szövegtípus
|
Értékhalmaz |
MaxHossz darabnyi jelből álló karakterláncok
halmaza Ì Karakter* |
|
Kezdőérték |
’’ azaz üres-szöveg (Min’Szöveg) |
|
Műveletek |
+, Hossz(.), Balrész(.),
Jobbrész(.), Jele(.) := =, <,
≤, ≥, >, ≠ |
|
Ábrázolás |
Rekord(hossz:Egész,
jel:Tömb(1..MaxHossz:Karakter)) – Pascal-stílusú |
3.2. Mutató típusok
Az alcímbeli többes szám jogos, mert valójában tetszőleges (többnyire összetett) típushoz, mint bázistípushoz (TB) szervesen tartozhat egy-egy ilyen típus. Egy konkrét mutató típusú objektum csak egyfajta (nevezetesen TB-típusú) elemek kezdőcímeit hordozhatja. E szigorúság oka: az ellenőrizhetőség, biztonságosság.
|
Értékhalmaz |
Memóriacím, amely
valamely TB-típusú elem kezdőcíme, vagy Sehova |
|
Kezdőérték |
Sehova |
|
Műveletek |
Lefoglal(Változó m:Típ, Konstans e:TB) – az eljárás létrehoz a memóriában egy TB-elemet, amelynek értéke éppen ’e’, és a címét teszi ’m’-be; ha nincs elegendő hely, akkor ’m’-be Sehova érték kerül. Elhagyható a kezdőértéket definiáló paraméter, ekkor a TB-beli iniciális értékű elem keletkezik. Típ(Konstans m:Típ):TB – a függvény az ’m’-beli címnél kezdődő TB-elemet adja vissza értékként Felszabadít(Változó m:Típ) – az eljárás felszabadítja a memória ’m’-ben lévő címtől kezdődő TB-elemnyi tartományát, majd ’m’-be a Sehova érték kerül. := =
|
|
Ábrázolás |
Memóriacím |
Megjegyzések:
A Lefoglal művelet fent taglalt szemantikája is indokolja a szigorú típusosság kívánalmát!
A Pascal-beli Lefoglal művelet, a New, nem foglalkozik kezdőértékadással, sőt a helyfoglalás sikertelenségét sem közli a Sehova, vagyis a Nil értékkel. A Felszabadít, Dispose művelet sem törli a mutatót.
|
Példa: |
|
… Változó
[vajon milyen értékek vannak a bk(2..MaxN) elemekben; |
4. Összetett adattípusok – típuskonstrukciók
Helyesebb összetett típusok helyett típuskonstrukciókról beszélni, mivel valahány összetevő típusból hozunk létre, konstruálunk egy újat; s az ilyeneket létrehozni képes eszközöket típuskonstrukciós eszközöknek hívni.
Többnyire nem magától értetődő az ilyen struktúrák rendezése, ezért sem a Min’, sem a Max’ típusfüggvényt nem jelezzük. (Megjegyezzük: természetesen nem elképzelhetetlen –sőt!–, hogy utólag valamilyen rendezést rájuk is definiáljuk. Erről később még szó esik.)
A korábbi szokásos mondanivalók mellé bekerül a „konstrukció”, amelyben tisztázzuk az alkalmazás szintaxisát.
Rövidítés miatt a bázistípusokat sorszámozzuk és így jelöljük: TB1, TB2, …
4.1. Összetett típusok osztályozásai
A bázistípusok sokfélesége szerint –
- Heterogén (rekord, alternatív rekord)
- Homogén (sorozatfélék: tömb, lista…, halmaz; rekurzív típusok: lista, fa; gráf…)
Rákövetkezési reláció az elemei között –
- Nincs (értelmetlen: rekord, alternatív rekord; lehetne, de nincs: halmaz)
- Egyértelmű, kivéve a szélső elemeket (sorozatfélék: tömb, lista,…)
- Többszörös (rekurzív típusok közül a fa; gráf)
4.2. Rekord
|
Konstrukció |
Rekord(mező1: TB1, mező2: TB2 …) |
|
Értékhalmaz |
TB1´TB2´… |
|
Kezdőérték |
Az egyes
komponensekhez tartozó kezdőérték.
|
|
Műveletek |
Típ(Konstans m1: TB1, m2: TB2 …) – létrejön egy Típ típusú konstans m1, m2… mezőértékekből (konstrukciós operáció) objTip.mezői:TBi – a „szokatlan” szintaxisú művelet értéke az adott Típ típusú objektum (objTip) mezői mezőjének értéke… (szelekciós operáció) objTip.mezői:TBi:=ei – a „szokatlan” szintaxisú értékadás eredménye az adott Típ típusú objektum (objTip) mezői mezőjének értékül adja ei-t… := =, ≠ Be:, Ki: |
|
Ábrázolás |
A mezők folytonos memóriaterületre képezve, a felsorolás sorrendjében. |
4.3. Alternatív rekord
Olyan rekordféléről van szó, amelynek valamely mezőjétől (mezőitől) függ további mezőinek típusbesorolása.
|
Konstrukció |
Rekord( |
|
Értékhalmaz |
TB1´…TBK´…È(i=1..m)TBi,1´…TBi,ki |
|
Kezdőérték |
A nem
egyértelműsége miatt NemDef.
|
|
Műveletek |
A rekordhoz hasonlóan. |
|
Ábrázolás |
A mezők folytonos memóriaterületre képezve, a felsorolás sorrendjében, a hosszat a leghosszabb alternatívával számolva. |
|
Példa: |
|
… Típus
Függvény Kontroll(Konstans n:TNem Típus
TSzemSzám=Rekord(
TSzemély=Rekord( Konstans |
4.4. (Hatvány-)Halmaz
Csak diszkrét (többnyire nagyon is korlátozott számosságú) típusnak definiálhatjuk a hatványhalmaz-típusát.
|
Konstrukció |
Halmaz(TB) (Min’Típ=Æ..Max’Típ=TB-értékhalmaz,
a tartalmazás alapján rendezve) |
|
Értékhalmaz |
TB* |
|
Kezdőérték |
Üres halmaz
|
|
Műveletek |
Î (eleme), Ç (metszet), È (egyesítés), \ (különbség), Æ vagy Üres (üres halmaz létrehozás), Üres? (logikai értékű függvény) := =, < (Ì), ≤ (Í), ≥ (Ê), > (É), ≠ Be:, Ki: |
|
Ábrázolás |
Tömb(TB:Logikai) – azaz bitvektor az adott elem tartalmazása vagy nem tartalmazása szerint; Lista(TB) – tartalmazott elemeinek felsorolása [l. később] |
|
Példa: |
|
… Változó Konstans |
4.5. Tömb
|
Konstrukció |
Tömb(TIndex : TElem) |
|
Értékhalmaz |
TElemSzámoság(TIndex) |
|
Kezdőérték |
TElem
típus kezdőértékei
|
|
Műveletek |
objTip(i)
(a Típ típusú objTip tömb i. TElem típusú eleme), := =, ≠ |
|
Ábrázolás |
Az elemek folytonos memóriaterületre képezve, növekvő index sorrendben. (L. később) |
5. Sorozattípusok
Sorozattípusnak hívjuk azt a típust, amely
- homogén (azaz elemei egyetlen bázistípushoz tartoznak),
- egyértelmű rákövetkezési reláció van elemei között (az adott elemét legfeljebb egy elem követheti),
- egyetlen olyan eleme van, amelyet nem előz meg másik, s egyetlen olyan, amelyet nem követ.
5.1. Sorozatműveletek
5.2. Sorozatok ábrázolásának lehetőségei
|
|
6.
A
modul mint a típusmegvalósítás kerete
6.1
Mi a
típus?
Amit már tudunk – „statikus kellékek”
- Értékhalmaz
- Műveletgarnitúra
Miket kell megadni ahhoz, hogy mondhassuk: a típust „teljesen” ismerjük?
A statikus kellékeken, ismereteken túl:
- Szignatúra – milyen dolgokkal manipulál a művelet (értelmezési tartomány), s mit állít elő (értékkészlet)?
- A műveletek „(együtt)működése” – hogyan függnek össze a műveletek transzformációi (axiómák)?
Mit értünk a típus megvalósítása alatt?
Annak definiálását, hogy milyen leképezést valósítanak meg az egyes műveletek (szemantika-definíció), és hogyan lehet „megszólítani” őket (szintaktika-definíció):
- Definiálhatjuk csak a kapcsolatukat, egymásra hatásukat, axiómák megadásával. (Algebrai specifikáció)
- Definiálhatjuk az egyes műveletek „egyedi” leképezésének megadásával. Ez az export modul feladata, amely tartalmazza a szignatúrákat és –esetleg– az elő-utófeltételeket. (Algoritmikus specifikáció)
- Rögzíthetjük az egyes műveleteket „egyedi” megvalósításukkal, amelyben már figyelembe vesszük a típus már rögzített ábrázolását. Ez a reprezentációs-implementációs modul feladata.
A fenti 2-3.-at egyaránt vonatkoztathatjuk algoritmusra és konkrét programozási nyelvre. A következő („6.3. A modul”) fejezetben mi az algoritmikus nyelvünket bővítjük ki úgy, hogy kezelhető legyen benne e kérdéskör. Mivel nem állunk meg a puszta elmélet síkján tisztázzuk azt is („7. A modulfogalom és a Pascal nyelv” fejezetben), hogy az általunk használt lingua franca, a Pascal programozási nyelv, milyen lehetőséget ad mindehhez.
6.2. A típus algebrai specifikációjáról
Röviden utalunk a nyelv azon kiegészítésére, amelyben tisztázni fogjuk „globális” elvárásainkat az adott típussal szemben. Ezt a legabsztraktabb elképzelést formálisan egy algebrai alapú nyelven írjuk le, az alábbi keretben:
|
Szintaktikai „minta” |
Magyarázat |
|
Típus TípusKonstrukció(paraméterek): Asszociált műveletek: Operáció(értelmezési
tartomány): Értékkészlet … |
A
definiálandó típuskonstrukció „alkalmazási sablona” (feje). Operációinak
szignatúrája (értelmezési tartománya, értékkészlete) |
|
Axiómák: Jelölések: objektum:
Típus(paraméterek) = … 1o … az
axióma informális szövege ... a
formalizált axióma 2o … |
Az
operációk kapcsolatát leíró axiómák, és a bennük fölhasznált objektumok
„deklarációi”.
|
Mint a példából is kiderül, alkalmazunk néhány konvenciót, amelyet most –az idő rövidsége miatt– nem taglalunk. (A részletekhez lásd a Típus-specifikációkban.)
Visszatérő példa legyen a hét napjainak típusa! Nézzük ennek egy lehetséges algebrai leírását! Megjegyzem: a példa nem „tipikus” bizonyos értelemben, mivel a napok típusa egy konkrét típus, így nem tudunk élni a fenti típus-specifikálási „nyelvezet” paraméterezési szolgáltatásaival.
|
Példa: |
|
Típus TNap: Hétfő,Kedd,Szerda,Csütörtök, Axiómák: a:TNap n:Egész 0o A minimális érték a Hétfő, a maximális a Vasárnap, a típus számossága 7. Számosság=7 Ù Min=Hétfő Ù Max=Vasárnap 1o Létrehozás utáni értéke Hétfő. a=Létrehoz Þ a=Hétfő 2o Lerombolás után nincs értelme a műveletek (a Létrehoz kivételével) alkalmazásának. Következő(Lerombol(a))=NemDef Ù … 3o Nem létezik Hétfőt megelőző és Vasárnapot követő. Előző(Hétfő)=NemDef Ù Következő(Vasárnap)=NemDef 4o A Következő és Előző műveletek egymás inverzei. $Előző(a) Þ Következő(Előző(a))=a Ù $Következő(a) Þ Előző(Következő(a))=a 5o A Sorszám és TNap műveletek egymás inverzei. nÎ[0..Számosság) Þ Sorszám(TNap(n))=n Ù 6o A fenti felsorolás sorrendjében növekvően rendezettek. Következő(Hétfő)=Kedd Ù Következő(Kedd)=Szerda … 7o A
Hétfő sorszáma Sorszám(Hétfő)=0 Ù Sorszám(Vasárnap)=6 Állítás:
Sorszám(a)Î[0..Számosság); és a
Sorszám(a)=a fenti felsorolásbeli pozíciója + 1. Bizonyítás: Nyilvánvaló. 8o A
felsorolásban előbb szereplő kisebb, mint bármely a<b Û Sorszám(a)<Sorszám(b)[5]… |
- Figyeljük meg a következőket! A Létrehoz értelmezési tartomány nélküli függvény, amely a „semmiből” kreálja meg az adott típusú adatot; a Lerombol pedig értékkészlet nélküli, amivel épp a többi, „normális” függvény ezután történő alkalmazhatatlanságát fejeztük ki. Ezt nyomatékosítjuk a 2o axiómával is.
- Lehetséges, hogy a Létrehoz és Lerombol műveletekre a későbbiek során explicite nem lesz szükségünk. Ez a helyzet az ún. statikus adatoknál, amelyekre az a jellemző, hogy a deklarációk által automatikusan jönnek létre, s így a programozónak nincs „gondja” sem a létrehozással, sem a lerombolással. (Érdemes meggondolni, mikor kerül sor e két művelet végrehajtására a blokk-struktúrájú nyelvek –pl. a Pascal– esetén.)
- A NemDef egy típusfüggetlen konstans, ami akkor képződik, amikor valamilyen tiltott művelet végrehajtására kerülne sor. Ha egyszer NemDef érték jött ki, akkor arra alkalmazva bármely operációt, az eredmény NemDef marad (implicit error-axióma).
- Nyilvánvaló, hogy a 2-8o axiómák feltételéül meg kellett volna fogalmaznunk, hogy az ott szereplő objektum létezik (objektumok léteznek), azaz létrehoztuk korábban. Ezt implicite föltételeztük.
- A 6o axióma párjaként megfogalmazható „Előző-rendezési axiómát” következmény-állításként illeszthetjük a rendszerbe. (Most nem tesszük meg.)
6.3. A modul
Elsőként a programozói felületet leíró, ún. export modul szintaxisát adjuk meg:
ExportModul TípusNév(InputParaméterek):
[most következnek az exportálandó fogalmak „értelmes” csoportosításban:]
Típus
[ritkán van
ilyenre szükség]
Tip1,Tip2,... [csak azonosítók felsorolása!]
Konstans
[ritkán van
ilyenre szükség]
Kons1,Kons2,...[a TípusNév típus néhány
kiemelendő konstansa]
[az
alábbi részben soroljuk föl a típushoz tartozó tevékenységek „fejsorait”
és működésüket leíró elő-utófeltételeket]
Függvény Fv1(FormParam): FvTip1
Ef: …
Uf: …
Függvény Fv2(FormParam): FvTip2
Ef: …
Uf: …
…
Eljárás Elj1(FormParam)
Ef: …
Uf: …
Eljárás Elj2(FormParam)
Ef: …
Uf: …
…
Operátor Op1(FormParam): OpTip1
Ef: …
Uf: …
Operátor Op2(FormParam): OpTip2
Ef: …
Uf: …
…
Modul
vége.
Megjegyzések:
- A „fő fogalom”, a TípusNév, külön megadás híján is látszódó fogalom lesz.
- Az InputParaméterek lehetnek típust jellemző konstansok, de –típuskonstrukció esetén– típusok is. (Szokás e paramétereket ’generic parameter’-nek nevezni.)
- Az elő-utófeltételek időnként elhagyhatók. (Pl. ha ezeket csak az ábrázolás ismeretében lehet értelmesen megfogalmazni, ami e pillanatban még nem ismert.)
- A modulfej egyben a felhasználás „mintájául” is szolgál (l. az alábbi példát).
|
Példa: |
|
ExportModul
Tömb(Típus TIndex : Típus TElem): A fenti definíció után a felhasználás
szintaxisa:
|
- Az egyes exportált fogalmak csoportosításra semmilyen megkötés nincs: sem sorrendjére, sem arra, hogy hány „darabba” különítjük el őket. (Tehát lehet több konstans, típus vagy más csoport is.)
- Kerülni kell a változók exportálását. Ui. veszélyes, ha a rátámaszkodó programnak lehetősége van a reprezentált adatokkal közvetlen kapcsolatba kerülni. Ha ilyen igény merülne föl, akkor definiálni kell külön erre a célra tevékenységeket (eljárásokat, függvényeket, operátorokat).
Ki fogjuk egészíteni az algebrai specifikáció műveletkészletét továbbiakkal is: egyenlőség-vizsgálattal, értékadással, beolvasás és kiírás műveletekkel, valamint a hibás elvégzés tényét rögzítő hiba-flag-et kezelő függvénnyel. (Ezek nélkül ugyanis felhasználhatatlan eszköz maradna a legtöbb típus, vagy mindenegyes esetben a programozónak külön kellene jól-rosszul ezekkel a műveletekkel kiegészítenie.) Mindezt annak ellenére tesszük, hogy sok esetben a programozási nyelvek nem adnak mindegyikre (pl. a „típusos” be/ki-re) módot.
Egy-két típusnál szokatlan lehet valamely létrehozó, ill. leromboló művelet használatának explicit felkínálása, mivel a programozási nyelvek legtöbb implementációja automatikusan gondoskodik a létrehozásról. (Pl. Tömb, Táblázat, Statikus gráf.) A leírás teljességére való törekvés, illetve az esetleges „hagyományostól” eltérő ábrázolás lehetővé tétele mégis indokolttá tehetik ezt.
|
Példa: |
|
ExportModul TNap: [kiindulási alap az algebrai leírás] Operátor Min:TNap Operátor Max:TNap Operátor Számosság:Egész Függvény Következő(Konstans
x:TNap):TNap Függvény
Előző(Konstans x:TNap):TNap Függvény Sorszám(Konstans
x:TNap):Egész Függvény TNap(Konstans x:Egész):TNap
Infix Operátor
Egyenlő(Konstans x,y:TNap):Logikai Infix Operátor LegyenEgyenlő(Változó
x:TNap Infix Operátor Kisebb(Konstans
x,y:TNap):Logikai Operátor
Be(Változó x:TNap) Operátor Ki(Konstans x:TNap) Függvény Hibás?(Változó x:TNap):Logikai az előfeltétele nem teljesült)
az adott TNap típusú (x) adatra; majd inicializálódik a hiba-flag] Modul vége. |
Megjegyzések:
· A Létrehoz és Lerombol műveleteket kihagytuk az algoritmikus specifikációból. Ezzel eltértünk az algebrai specifikációtól. Ok: statikusan kívánjuk megvalósítani e felsorolástípust, építünk a blokk-struktúrájú nyelvek adatlétrehozó, -leromboló mechanizmusainak létére. (Gondoljon az eljárás-/függvény-paraméterekre és a lokális adatok kezelésére!) A Létrehoz-axióma persze még fel kell bukkanjon a megvalósításban a szükséges kezdőérték megadása miatt.
· A Min, Max és Számosság konstansokat (prefix) 0-változós operátorként definiáltuk, s nem konstansként, mert alkalmazásuk speciális szintaxisú (típusparaméterű). Vegyük észre, hogy ezek a konstansok minden rendezett, illetőleg véges típus esetén értelmesek. Így a használó program szintjén való megkülönböztetés érdekében olyan szintaxist kell hozzájuk rendelni, amely lehetővé teszi a típushoz kapcsolást. Ilyen probléma nem vetődik föl a többi (Hétfő, Kedd stb.), natív konstanssal kapcsolatban. (Ez a magyarázata a Min’Típus, Max’Típus, illetve a Számosság’Típus különleges szintaxisának.)
|
Példa: |
|
… … |
· Látható, hogy akkurátusan törekedtünk –bármi áron is!–, hogy az utófeltételekben ne nyúljunk vissza más művelethez, csak saját „hatáskörben” definiáltuk az elvárásokat. Ha ezt az elvet nem tartottuk volna tiszteletben, akkor egyszerűen meg lehetett volna fogalmazni a := és = operátorok utófeltételét. Például:
Egyenlő.Uf: x=y Û Sorszám(x)=Sorszám(y).
Ekkor azonban könnyen előadódhatna az a helyzet, hogy egymásra kölcsönösen hivatkozva specifikáljuk őket, ami egy logikailag értelmezhetetlen specifikációt eredményezne.
· Az értékadás és az értékazonosság operációkról feltesszük, hogy bitről-bitre történő másolást, illetőleg azonosságvizsgálatot jelent, ezért nem tartjuk fontosnak feltételekkel körülbástyázni. Másrészt, ha ezt formálisan is le akarnánk írni, vissza kellene nyúlni (esetleg bit-szintű) reprezentációig, amit effajta specifikációnál elkerülendőnek tekintünk.
· Az időnként felbukkanó „…” folytatás jelzése formálisan megengedhetetlen, azonban itt csupán egy példáról van szó, így megelégedtünk a kitalálható folytatás jelzésével.
· Fölvethető kérdés: mennyire ugyanarról szól a kétféle specifikáció. Valóban ez külön vizsgálandó, sőt bizonyítandó probléma.
· A „Be:” és „Ki:” operátorok működésénél két problémát kell tudni formalizálni:
1. a külvilággal való kapcsolatét (amely karakteres alapú),
2. Szöveg↔TNap transzformációét.
Az 1. általános megoldására bevezettünk két függvényt. Az Input megadja azt a szöveget, amelyet a beolvasó utasítás talál az input-pufferben; az Output szimbolizálja az output-puffer állapotát (azt a szöveget, amely kiíródik a végrehajtás során, pl. a képernyőre). Így a 2. probléma már kezelhetővé vált, hisz az adat és transzformáltja is egy-egy memóriabeli objektumban csücsül. Fel kell figyelnünk a szöveges és a „belsőállapotú” konstansok merev megkülönböztetésére (’hétfő’≠ Hétfő…)!
· Operátornak azt az alprogramot nevezzük, amely az eljárástól vagy függvénytől eltérő szintaxissal építhető be a programba (azaz hívható). Lehet Infix, ekkor a két operandus közé illeszkedik, lehet Prefix, ekkor megelőzi az egyetlen paraméterét, ill. Postfix esetben követi. S lehet „egyéni” szintaxisa, ekkor a Másnéven kulcs-szónál adhatjuk meg ezt. A leggyakoribb eset a Prefix, ezért ezt a minősítőt elhagyhatjuk.
· Egyik-másik operátornál „meglepő” a paraméter hozzáférési joga. A várható konstans helyett változó lett azért, mert a végrehajtás során hiba következhet be, amely által az „állapota” kényszerűen és szándékunk ellenére megváltozik. (Következő, Előző… Hibás?. Nagyjából azoknál, amelyeknél nem üres az előfeltétel, tehát van „esélye” a hibás használatnak. Pontosan azoknál, amelyeknek bármi köze is van a hiba-flag-hez.)
Folytassuk a megvalósítást betetéző fogalommal, a reprezentációs-implementációs modullal, röviden a modullal! Ennek feladata, hogy amit eddig elterveztünk, azt kidolgozza: azaz tisztázza, hogy
- miként ábrázolható a típusbeli érték a memóriában, vagy bárhol (reprezentáció) és
- hogyan valósíthatók meg az egyes műveletek, figyelembe véve a választott ábrázolást (implementáció).
A modul-szintaxis a következő:
Modul TípusNév(InputParaméterek):
Reprezentáció
…
[a
típusábrázoláshoz szökséges adatleíró „kellékek”:
konstansok,
saját típusok,
a
változó-deklarációs rész már magának a típusnak a „mezőit” határozza meg]
Implementáció
[itt
szerepelnek az export-modulban „megjósolt”
tevékenységek
működésének részletezése…]
Függvény Fv1(FormParam): FvTip1
Ef: …
Uf: …
…
Függvény Fv2(FormParam): FvTip2
Ef: …
Uf: …
…
Eljárás Elj1(FormParam)
Ef: …
Uf: …
…
Eljárás Elj2(FormParam)
Ef: …
Uf: …
…
Operátor Op1(FormParam): OpTip1
Ef: …
Uf: …
…
Operátor Op2(FormParam): OpTip2
Ef: …
Uf: …
…
Inicializálás
[egy ilyen típusú adat létrehozása az itt leírt utasításokkal történik]
Modul
vége.
Megjegyzések:
·
Az egyes műveletek egyedi specifikációját
jelentő elő-utófeltétel párok, amennyiben megegyeznek az exportmodulbelivel,
nyilván elhagyhatók. Természetesen „értelmesen” igazítva a reprezentációhoz,
újabb biztonsági támpontul szolgálhat a fejlesztéshez. (Ekkor persze újabb
feladatként járul az eddigiek mellé, hogy ezek következését az „elődjükből” be
kell látni:
operációExportmodul.Ef
Þ operációModul.Ef Ù operációModul.Uf
Þ operációExportModul.Uf.)
A visszatérő példánk egy lehetséges moduljának töredékét tervezzük meg az alábbiakban. A reprezentációs döntésünk, hogy legyen minden TNap adatnak legyen egy hiba-flag-je.
|
Példa: |
|
Modul TNap: [kiindulási
alap az export modul] Változó Konstans Implementáció Operátor Min:TNap Min:=Hétfő Operátor Max:TNap Max:=Vasárnap Operátor Számosság:Egész Számosság:=7 Függvény Következő(Konstans
x:TNap):TNap Ha felsKód=6 akkor Következő.hiba:=Igaz Függvény Előző(Konstans x:TNap):TNap … Függvény Sorszám(Konstans
x:TNap):Egész … Függvény TNap(Konstans x:Egész):TNap … Infix Operátor Egyenlő(Konstans
x,y:TNap):Logikai Infix Operátor LegyenEgyenlő(Változó
x:TNap Infix Operátor Kisebb(Konstans
x,y:TNap):Logikai
Operátor Be(Változó x:TNap): Operátor Ki(Konstans x:TNap): … Függvény Hibás?(Változó x:TNap):Logikai … Inicializálás felsKód:=0;
hiba:=Hamis Modul
vége. |
Megjegyzés:
- Figyeljünk föl rá, hogy az utófeltételben sok esetben nem rögzítjük a hiba-flag értékét! Ez szándékos: ha hibás volt a művelet előtt, maradjon is az (implicit error-axióma), ha hibás eredményre vezet, akkor persze állítódjon át garantáltan Igaz-ra.
- A kisebb operátor utófeltétele az ExportModul-beli specifikáció „elvárt” párja. Ha azonban a specifikációhoz nyúlunk vissza (8o axióma), akkor jóval egyszerűbbet kapunk: Kisebb(x,y) Û x.felsKód<y.felsKód.
- Vegyük észre: az inicializálásban éppen az 1o axióma szerint jártunk el. A többieknél is, csak azoknál nem ennyire „látványosan”.
- Időnként attól a konvenciónktól eltérünk, hogy a típus reprezentációjában szereplő komponensekre (felsKód, hiba) nem a rekordnál szokásos mezőhivatkozásos jelöléssel tesszük meg (x.felsKód helyett csupán felsKód), az a magyarázata, hogy az adott operációnál nem lenne egyértelmű, hogy melyik ilyen típusú adat valamely komponenséről van éppen szó. Pl. a Következő operációban „szóba kerül” két TNap típusú objektum is: a kiindulásul szolgáló x paraméter és az eredményt jelentő.
7. A
modulfogalom és a Pascal nyelv
- Unit – önálló fordítási egység, amely lehetne a típus „zárt”, lefordított kerete. Zárt és lefordított Þ paraméterezni már nem lehet, többször fordítani viszont nem kell.
- Include-állomány – forrásprogram-töredék, amelyben a megvalósított típus „dolgai” találhatók, de bizonyos részek nem definiáltak benne, pl. a paraméterei, így „részt vesz” minden fordításban annak ellenére, hogy benne esetleg nincs változás;
- Objektum – olyan „rekord-szerű képződmény”, amely egységbe zárja a típus két kellékét: az értékhalmazt és a műveleteit; mindezt úgy teszi, hogy akár része lehet a fejlesztendő programnak, akár kiemelhető unit-ba vagy include-állományba (azok minden előnyével és hátrányával).
Az nyilvánvaló, hogy a Pascal-ban
- nincs operátordefiniálási lehetőség, helyette vagy function-t vagy procedure-t kell használni;
- csak egyszerű értéket szolgáltató függvényeket lehet definiálni (használni), ezért ilyenek gyanánt alkalmasan átalakított procedure-öket kell definiálni. Az átalakítás persze igencsak mechanikus, ahogy az alábbi példa mutatja:
|
Algoritmikus |
Þ |
Pascal |
|
Operátor
Min:TNap |
Þ |
Procedure Min(Var minKi:TNap); |
1. a FreePascal-ban az előbbi korlátozást már feloldották, ui. record-értékű függvény definiálható;
2. a Min’TNap / Max’TNap implementálása elhagyható, ui. létezik a típusokhoz egy Low / High típusargumentumú függvény. Így a Min’TNap / Max’TNap kódolása történhet ily módon is:
|
Algoritmikus |
Þ |
FreePascal |
|
…Min’TNap… |
Þ |
…Low(TNap)… |
7.1. Unit
· A unit szintaxisa igazodik a Pascal nyelvhez, így túl sok magyarázatra nincs szükség. Annyit elöljáróban: a unit egyesíti az exportmodul (Interface-rész) és a modul (Implementation-, inicializáló rész) fogalmat.
Unit TipusNev;{InputParaméterek}
Interface
…
{a
kívülről láttatandó fogalmak:
unit-ok,
konstansok, típusok, változók; eljárások
és függvények fejsorai}
…
Implementation
…
{az
elrejthető reprezentációs dolgok:
unit-ok,
konstansok, változók, típusok, „saját”
eljárások és függvények;
az
exportált eljárások és függvények törzsükkel
együtt}
…
Begin
…
{a
típus adatainak inicializálását végző utasítások}
…
End.
Megjegyzések:
- A program végrehajtása azzal kezdődik, hogy az összes hozzászerkesztett unit (Begin és End.-je közé tett) inicializáló utasításai egyszer s mindenkorra végrehajtódnak. Azaz nincs mód arra, hogy ha több adott (valamely unit-ban megvalósított) típusú adat van a programban, akkor azok mindegyike külön-külön inicializálódjék. Ezért sokszor be kell vezetni egy további műveletet inicializálás céllal, és rá kell bízni a programozóra, hogy a deklaráció után és az első felhasználás előtt használja is.
- Mivel nincs mód paraméterezésre, ezért ellenáll mindenféle „általánosításnak”. A fenti kommentben levő InputParaméterek csak a fejlesztőnek szolgáltatnak információt arról, hogy mik azok a fogalmak, amelyek, ha lehetséges volna, paraméterként funkcionálhatnának.
- A unit neve és a befoglaló fájl neve azonos kell, legyen!
- Felhasználása: a „hívó” program Uses utasítása sorolja föl a felhasznált összes unitot.
- Ha ugyanaz az azonosító több hivatkozott modulban is előfordul (vagy magában a hivatkozó programban), akkor fölvethető a kérdés: melyikre mi módon lehet hivatkozni. A válasz: minősített azonosító alkalmazása, azaz a unitnév + pont + azonosító.
|
Például: írható saját ClrScr eljárás, amelyben építhetünk
a Crt unit hasonló nevű eljárására: |
|
… … Begin ClrScr(’Ügyes kis program’); |
Az alábbi példa bemutatja, hogyan lehet a TNap típust unit-tal megvalósítani. A Pascal nyelv fentebb említett kellemetlen vonásai miatt a TNap-értékű függvényeket procedure-ökkel helyettesítettük. (FreePascal-ban szebben is megvalósíthatjuk. Gyakorlásul tegyük is meg!)
Megjegyzések:
- Sajnálatos módon a sajátos Pascal logika miatt olyanok is belekerülnek az Interface részbe, amelyeket ténylegesen nem szeretnénk exportálni. (TNapK a TNap „belső struktúrája”…)
- A TNap típus felhasználását a következő példa mutatja.
|
Példa: |
|
Program AProgram; Begin … End. |
Egy más elvű megoldást is találhatunk, ami azonban nem a modulból, hanem az exportmodulból indul ki. Ötlete a következő: a napok absztrakt felsorolását egészítsük ki egy további, pl. NemDef-fel elkeresztelt értékkel. Az előbbi TNapK és TNap kettőse helyett ábrázoljuk így:
Típus
TNapK=(Hétfő, Kedd, Szerda, Csütörtök, Péntek,
Szombat, Vasárnap, NemDef)
Változó érték:TNapK
Ekkor egyszerű értéktípusúak lesznek az eleddig rekord-típusú értéket szolgáltató függvények. Pl.:
Függvény Következő(Konstans
x:TNap):TNap
Ef: x¹Vasárnap
Uf: Következő(x)= Következő(érték) [érték=TNapK(x)!]
Ha
érték=Vasárnap akkor Következő:=NemDef
különben Következő:=Következő(érték)
Függvény vége.
Figyelem: itt semmi rekurzió nincs. Hiszen a definiálandó Következő függvény paraméterének a típusa TNap, amíg a felhasznált Következőé TNapK.
A Pascal-megfeleltetés úgyszólván problémamentes:
Interface
Type
TNapK=(Hetfo,Kedd,Szerda,Csutortok,
Pentek,Szombat,Vasarnap,NemDef);
{a TNap=Record ertek:TNapK End helyett:}
TNap=TNapK;
Procedure Inic(Var x:TNap);
…
Function Kovetkezo(Var x:TNap):TNap;
…
Implementation
…
Procedure Inic(Var x:TNap);
{Ef: –
Uf: x=Hetfo}
Begin
x:=Hetfo
End;
…
Function Kovetkezo(Var x:TNap):TNap;
{Ef: x<>Vasarnap
Uf: x=Hetfo Þ Kovetkezo(x)=Kedd
ES …}
Begin
If x=Vasarnap then Kovetkezo:=NemDef
else Kovetkezo:=Succ(x)
End;
…
7.2. Kódtöredék automatikus beillesztése
A unitok nyilvánvaló hátrányát igyekszik kiküszöbölni az „állomány automatikus beillesztés” lehetősége. A lényeg: a Pascal fordítóprogramot „rávesszük”, hogy a kódtöredéket tartalmazó fájlt a befoglaló program adott pontján illessze be. Ennek módja: {$i töredék-fájlnév} direktíva az adott helyen.
|
Példa: |
|
Legyen az alábbi töredék a TNap.inc nevű fájlban: {TNap Type Const
Procedure Inic(Var x:TNap);
Begin … Procedure Kovetkezo(Const
x:TNap; Var kovetkezoKi:TNap); Begin … A felhasználás: Program
AProgram; Begin End. |
Megjegyzés:
- A fenti példából sajnos nem látszik a leglényegesebb különbség: a „kvázi paraméterezhetőség”. A későbbiek során azonban számos példa lesz a unit paraméter-problémájára.
7.3. Objektum-osztály
Objektum, helyesebben objektum-osztály fogalma számunkra azzal az előnnyel jár, hogy a programon belül megvalósíthatjuk a megfelelő típusfogalmat, azaz az értékhalmaz és művelethalmaz egységét, egységbezárását (encapsulation).[7] A szintaxisáról elegendő ennyit tudni:
…
Type
TipusNev=Object
…
{mező-deklarációk, amit itt az objektum
attribútumainak vagy tulajdonságainak hívnak}
…
{a
típus műveleteinek, metódusainak fejsorai következnek:}
Constructor EljC(…); {elhagyható}
Destructor EljD(…); {elhagyható}
Procedure Elj1(…);
…
Function Fv1(…):TFv1;
…
End;
{a
típus műveleteinek kifejtése:}
Constructor TipusNev.EljC(…);
…
Begin
…
End;
Destructor TipusNev.EljD(…);
…
Begin
…
End;
Procedure TipusNev.Elj1(…);
…
Begin
…
End;
…
Function TipusNev.Fv1(…):TFv1;
…
Begin
…
End;
…
Var
a,b,c:TipusNev;
…
Begin
…
a.EljC(…);
{az a objektum
konstruktorának „hívása” a
létrehozás kedvéért}
a.Elj1(…);
{az a objektum
Elj1 műveletének „hívása”}
…
Megjegyzések:
- Az objektum-osztály (értsd: objektum-típus) definíciójában felhasználható minden korábban definiált típus, így akár „paraméterezhető” is.
- Semmi akadálya annak, hogy az osztály definícióját külön include-állományba kiemeljük, s ezzel biztosítsuk a könnyű újrafelhasználást (reusability).
|
Példa: |
|
Legyen a töredék az alábbi, ONap.inc nevű fájlban: {Osztály ONap[8] Type Type End; Constructor ONap.Inic; Procedure ONap.Min(Var
minKi:ONap); … Function ONap.Szamossag:Word; Procedure ONap.Kovetkezo(Var
kovetkezoKi:ONap); … A felhasználás: Program
AProgram; Begin End. |
Tartalom
Adatszerkezetek
tárgy , 1. félév 1. előadás’2009 (vázlat)
2.1.
Az értéktípusról általánosságban
2.2.
Az asszociált műveletek osztályozása
4.
Összetett adattípusok – típuskonstrukciók
4.1.
Összetett típusok osztályozásai
5.2.
Sorozatok ábrázolásának lehetőségei
6. A
modul mint a típusmegvalósítás kerete.
6.2.
A típus algebrai specifikációjáról
7. A
modulfogalom és a Pascal nyelv