Modellek és formális eszközök (Prog.Inf. Szakon) Programozási Módszertan elmélete 1. EA (Prog.Mat. Szakon)
Szendrei Rudolf
[email protected] http://people.inf.elte.hu/swap/
Tematika • Rendszerleírások aspektusai, leírások, specifikációk és modellek • Probléma, modell, követelmény, specifikáció, program • Objektumelvű programfejlesztés • Nem determinisztikus szekvenciális program, szintaxisa, szemantikája • Specifikációs módszerek • Konkurencia alapfogalmai, konkurens programok és rendszerek
Tematika • • • • • • • • •
Objektum elvű konkurens programok Konkurens és nem determinisztikus program Konkurens program szintaxisa, szemantikája Osztott nem determinisztikus programrendszer Csatorna és csatornautasítások Csatornautasítások szintaxisa, szemantikája Csatornautasítások illesztése Diszjunkt csatornák összekötése Ágensrendszerek
Irodalom Kozma László, Varga László: Szoftvertechnológia elméleti problémái. Pázmány Eötvös Kiadó, 2007, Ehring H., Mahl B.: Fundamentals of Algebraic Specification 1, 2. Module specifications and constraints. Springer-Verlag, 1990, Jacques Loeckx, Hans-Dieter Ehrich, Markus Wolf: Specification of Abstract Data Types. John Wiley and Sons, 1996, Krzysztof R. Apt, Ernst-Rüdiger Olderog: Verification of Sequential and Concurrent Program, Springer-Verlag, 1997 Willem-Paul de Roever et al.: Concurrency Verification; Introduction to Compositional and Noncompositional methods; Cambridge University Press, 2001 Mclver A., Morgan C.: Programming Methodology, Springer-Verlag, 2003
Szoftverfejlesztés, mérnöki tevékenységként
Számítástechnikai eszközök fejlődése • 1943. Neumann János ENIAC számítógépe (Ballisztikus röppályák számítására) • 1942-46. Manhattan projekt (atombomba kifejlesztése) • Műveleti sebesség és kapacitás növekedése • Hálózatok létrejötte, hálózatin keresztüli problémamegoldás • Magas szintű programnyelvek (Algol, Fortran, Cobol) • Sok programnyelv jött létre, pl. SIMULA, CLU, ADA, Prolog, LISP, C, … • Monitor a kényelmesebb grafikus kommunikációhoz • Batch operációs rendszerek kötegelt feldolgozáshoz • Mai értelemben vett operációs rendszerek megjelenése
Számítás eszközök fejlődése Magyarországon • 1956: M3-as számítógép MTA, Gépi kód. • 1960-as évek eleje: Ural számítógépek; Gépi kód; • 1960-as évek közepe: • Gler gép. Monitor; Assembly; Algol; • ICT 1905 gép. Monitor; Batch vezérlő; Assembly; Algol, Fortran, Cobol; • 1960-as évek vége: Hazai fejlesztések • TPA (DEC) gépek; operációs rendszer; • 1970-es évek. • IBM/360-as gépek; operációs rendszer; PL1; • Kisgépek, TPAI; KFKI. VIDEOTON hazai fejlesztések; • 1980-as évektől a programnyelvek sokasága: ADA; CLU; Prolog; C...
Az objektumelvű programozás megjelenése és a szoftverfejlesztés • 1. mérföldköve a SIMULA 67, mely a 60-as években jelent meg • Korábban • Vezérlés központú gépi kódú utasítások • Egyszerűbb, kisebb terjedelmű programok • Szekvenciális végrehajtás, párhuzamosság hiánya, interaktivitás hiánya • Utána • Nagy méretű programok és komplex rendszerek fejlesztése • Osztott rendszerek, párhuzamosság, aszinkron interaktivitás • Az utóbbi három évtizedben az egyetemi projektekben szerzett tapasztalatok alapján az objektum elvű megközelítés flexibilisebb a gyorsan változó követelmények mellett, mint az imperatív, funkcionális vagy logikai programozási stílus.
Objektum elvű programozás • P. Wegner: • Objektum elvű programozás • Adatabsztrakció • Absztrakt adattípus • Típusöröklődés • Objektum elvű programozási nyelvek típusrendszere • Típus:: Egyszerű Egyszerű vagy összetett • Egyszerű típus:: char, int, float, bool, … • Összetett típus:: string, vector, list, set, map, array, record, … absztrakt adattí adattípus, öröklő klődéssel szá származtatatott adattí adattípus (lá (lásd: programozá programozási nyelvek tá tárgy)
Objektumelvűség elvei napjainkban •
Osztály: (attribútumok, metódusok), mely a program struktúráltságát írja le • Felületek hozzáférésének szabályozása: láthatóság, metódusok és azok attribútumainak segítségével • Az objektumok az osztály példányaiként jönnek létre • Adatbeburkolás (encapsulation) • Adatabsztrakció, információ elrejtés • Objektumok azonosítókkal való elérése, megnevezése • Öröklődés, polimorfizmus Egyes objektum elvű programozási nyelvek megengednek többet is: Portabilitás, kód hordozhatóságának biztosítása (pl. Java)
Programfejlesztés, mint matematika •
A programfejlesztés a matematika része? •
Sok matematikát kell tanulni ahhoz, hogy egy problémát számítógép segítségével oldjunk meg? Igaz ez az állítás? 1. A számítógép a megoldás során szimbólum-manipulációt végez. 2. A számítógéppel megoldandó problémák jelentős része megfogalmazható formális matematikai leírással. 3. A programfejlesztési módszerek többnyire formálisak. 4. Intuitivitásra van szükség a módszerek használatakor. 5. Szükséges a problémák pontos leírása. 6. A megoldásnak a leírás szerint kell helyesnek lennie (formális eszközök). 7. Számos probléma számítógéppel való helyes megoldása a szimbólum-manipulációt erősíti (rendezés, keresés, gráf bejárások, programfordítás stb.)
A problé problémák kö közös jellemző jellemzője: a jó jól megfogalmazható megfogalmazható algoritmikussá algoritmikusság; tárgyuk absztrakt; Tehá Tehát matematika.
Hermann Weyl (1940) "Amikor a matematikus eljut az absztrakcióhoz, elfelejti azt, hogy a szimbólumai miket is helyettesítenek. Rendelkezésére áll egy sor operáció, amelyeket a szimbólumokkal elvégezhet, függetlenül attól, hogy ezek mit helyettesítenek". "Az informatikusnak ez kevés, mivel ő a valóságos problémát akarja megoldani. Neki azt a valóságos objektumot is figyelembe kell venni, amit a szimbólum reprezentál".
Mérnöki munka jellemzői Technológia:: módszerek, szabványok, eszközök, szervezés Módszer: • Olyan elvek halmaza, amelyek alapján kiválasztjuk és alkalmazzuk a technikát és az eszközöket. • Struktúrált programozás • Absztarkció + modularizáció; • Szintekre bontás: absztrakt (leírás)
konkrét (megvalósítás)
Módszertan: a módszerrel kapcsolatos vizsgálatok és ismeretek Programfejlesztés: leírások készítése.
Leírások 1. Domain (problémakör) leírása Annak leí leírása, amelyre a kö követelmé vetelmények vonatkozni fognak. 2. Követelmények Annak a leí leírása, amit a felhaszná felhasználó elvá elvár a program által nyú nyújtott szolgá szolgáltatá ltatásoktó soktól. 3. Specifikáció A szolgá szolgáltatá ltatások bemeneti és kimeneti kapcsolatá kapcsolatának a leí leírása. (Kí (Kívülrő lről megfigyelhető megfigyelhető viselkedé viselkedés) 4. Modell, rendszerterv Annak leí leírása, hogy milyen egysé egységek együ együttmű ttműködésén keresztü keresztül való valósulnak meg a szolgá szolgáltatá ltatások. 5. Program A szolgá szolgáltatá ltatások vé végrehajtá grehajtásának, a szolgá szolgáltatá ltatásokat eredmé eredményező nyező kiszá kiszámítások leí leírása.
Specifikációs interfész specint számítógép
Specifikációs interfész
felhasználó
(kiszámítás input-output relációja: billentyűzet, képernyő) Követelmény: interfész, mely egy közös felület a gép és a felhasználó között a rendszerben. Alapvető közös felületek: Billentyűzet: a felhasználó vezérli, a gép pedig érzékeli az adatait. Képernyő: a gép vezérli, a felhasználó pedig érzékeli a láttottakat, felhasználja.
Az interfész, mint specifikációs „tűzfal” Hard: formális rész (fejlesztő)
•
Soft: informális rész (elemző)
A tűzfal elvá elválasztja egymá egymástó stól • a rendszer-elemzőt,, aki a szá számítógépen kí kívüli vilá világ informá informális problé problémáival foglalkozik, •
a szoftver fejlesztőtől,, aki a szá számítógépes megoldá megoldással foglalkozik.
Dijkstra A funkcionális specifikáció megválasztása, annak jelölésrendszere, amellyel azt leírjuk, nem feltétlen kell, hogy világos legyen. Szerepe egy tűzfal létesítése két különböző dolog között.
Példa forgalomirányító lámpára Ügyfél igénye: A gyakorlatban felmerülő problémáját oldják meg. Probléma:
A lámpa 45 mp-ig tilost, majd 15 mp-ig szabad jelzést adjon.
számítógép
forgalmi lámpa
Specifikációs interfész { pjel, zjel }
követelmény interfész { stop, go }
Példa forgalomirányító lámpára
számítógép
forgalmi lámpa
Specifikációs interfész { pjel, zjel }
követelmény interfész { stop, go }
Az ügyfelet inká inkább a kö követelmé vetelmény interfé interfész, a szimbó szimbólumlum-manipulá manipuláció ció problé probléma érdekli: 1. Milyen felté feltételek mellett garantá garantálja a program / rendszer a szolgá szolgáltatá ltatás nyú nyújtá jtását? 2. Milyen megfigyelhető megfigyelhető hatá hatásai legyenek a szolgá szolgáltatá ltatásoknak? (felhaszná (felhasználó / ügyfé gyfél ké kérdé rdése)
A forgalomirányító lámpa követelménye forever { show only stop for 45 seconds; show only go for 15 seconds; }
Követelmény interfész Egy külvilág felé nyitott kapu, amit az ügyfél a gépen kívüli világban érzékelhet. Az ügyfelet nem érdeklik a szimbó szimbólum manipulá manipuláció ciós ké kérdé rdések vagy az elektromos jelek, csak az, hogy a lá lámpa zöld vagy piros..
A számítógép, a külvilág és a felhasználó számítógép
forgalmi lámpa
Specifikációs interfész { pjel, zjel }
követelmény interfész { stop, go } A gé gépi ré rész specifiká specifikáció ciója:
A specifiká specifikáció ció-interfé interfész a gé gépipi-, valamint a problé problématé matér kö közös ré része. Problématér::
{ Pjel; forever { wait 45 seconds; Pjel; Zjel; wait 15 seconds; Zjel; Pjel;
lá lámpa
Közösen használt fenomén:: { pjel,, zjel } }}
