Deklaratív programozás - Tippek ZH-ra és vizsgára
ZH how-to by TitCar
Általános tanácsok
A programozós feladatoknál (4 és 8) szerintem érdemes rászánni 2-3 percet arra, hogy alaposan átgondolja az ember, hogy mi is a feladat. Illetve nem véletlenül van megadva pár minta, hogy mit kell csinálnia a függvénynek. Amikor kész a függvényünk, próbáljunk ki egyet kettőt a minták közül prolog/sml fordítót játszva. Nem vesz el sok időt, de könnyen észre lehet venni, ha valamit elrontottunk.
Alapstruktúra alak (prolog)
Mi a különbség a [A,B] és a [A|B] lista közt?
- [A,B]: pontosan 2 elemű lista, alapstruktúra alakja: .(A, .(B, [])) ;
- [A|B]: legalább 1 elemű lista, alapstruktúra alakja: .(A, B)
Miből ered ez a különbség?
Deklaratív programozásban a lista egy elemből és az azt követő listából áll. Tehát: [A,B] lista: A elem, majd az azt követő lista, ami [B], ez a lista pedig: egy B elem és az azt követő lista, ami viszont minthogy nincs a B után semmi, üres lista kell legyen.
a+b+c alapstruktúra alakja: +(+(a,b),c)
Miért van ez így és nem például +(a, +(b,c))?
Gondoljuk csak végig, hogyan tanultuk ezt általános iskolában! először adjuk össze a-t és b-t, majd ehhez adjuk hozzá c-t.
Hogyan írjuk ezt fel jól?
Mi az első művelet amit el kell végezni?
a+b
akkor: +(a, b)
Ezután mit kell csinálni?
Hozzáadni c-t az eddigiekhez
akkor: leírjuk, ami eddig volt, majd alkalmazzuk rajt a +c-t: +(+(a,b),c)
emacsban a write_canonical(kifejezés). -el lehet alapstruktúra alakra hozatni a dolgokat. ets-ben jól be lehet gyakorolni.
Tippek a SICStus Prolog környezet használatához
Sok Prolog feladat van az ETSen, ha valami nem megy, nagy segítség lehet élőben kipróbálni.
- Alapstruktúra alakra hozás*: write_canonical(kifejezés). A végén '.' karakter áll, ezzel zárjuk le a parancsot.
| ?- write_canonical(e+r+7*0). +(+(e,r),*(7,0))
- Egyesítés*: beírjuk a bal és jobb oldalt, köztük egyenlőség jellel.
| ?- [1+2/3, s(X)] = [A+B, s(1)|Y]. A = 1, B = 2/3, X = 1, Y = []
- Program beírása*: először user módba váltunk: a [user]. paranccsal. Ezután beírkáljuk egyenként a programunk sorait. Ha végeztünk, nyomjunk
CTRL+C-t, majd írjuk be: abort. Ezzel visszaváltottunk, és már tesztelhetünk is.
| ?- [user]. % consulting user... | pf([_,_|L], L). | p(L, B, A) :- pf(L,A), length(A, H), H>B. | p([_|Xs], B, A) :- p(Xs, B, A). | | Prolog interruption (h for help)? abort % consulted user in module user, 0 msec 608 bytes % Execution aborted | ?- p([1,1,2,3,2,4,2], 2, A). A = [2,3,2,4,2] ? ; A = [3,2,4,2] ? ; A = [2,4,2] ? ; no
Ide még egy kis megjegyzést fűznék. A = [2,3,2,4,2] ? után újra hozzánk kerül az irányítás. Itt ha entert nyomunk, akkor a futás leáll. Azonban ha ';'-t írunk, ahogy a fenti példában, akkor további megoldásokat kapunk. Ha nincs több megoldás, akkor kapjuk a 'no' választ.
- Program betöltése fájlból*: File menü / Consult
- Könyvtár betöltése*: pl: use_module(library(lists)).
-- Endre - 2006.05.09.
1. feladat
itt full alap dolgokat kérdeznek általában lássuk mi mindent kell tudni! Z = 3+4. ekkor Z = 3+4. Z is 3+4 ekkor Z = 7. tehát: = jel az konyhanyelven szólva bemásolja a változóba amit megadunk neki. az is pedig kiszámolja, és a kifejezés értékét adja a változónak. erre hajaz pl.: U = 1+3 /+ U = 4. na mi is ez? U-ba bepakolja azt hogy 1+3 (és nem 4!!), majd meghiusul-e az U=4? (a /+ azt jelenti, hogy az utána levő kifejezés meghiúsul) természetesen meghiúsul, hiszen U nem 4, hanem 1+3 (kockasmile). tehát a válasz: U = 1+3. ha U is 1+3 /+ U = 4 lenne akkor a válasz: {no} ugyanis: U-ban kiszámolja 1+3 értékét, ami 4, de ezután nem hiúsul meg az U=4, tehát a komplett kifejezés sikeres, hiszen meghiúsul a meghiúsulás :D
a fentebbi listákra is szokott lenni mindig példa. pl. [H|T] = [1,2]. ekkor H = 1, ez nem vitás, viszont arra oda kell figyelni, hogy a T értéke nem 2 lesz, hanem a 2es elemet tartalamzó lista, tehát: T = [2].
újabb tipikus példa: A is C+3, C = 6. ezzel az a probléma h a prolog rengeteg dolgot tud, viszont nem tudja előre megmondani az A kiszámításakor h mit tegyen be oda, mint C hiszen annak ott még nincs értéke, azaz behelyettesítetlen változó. Tehát error-t kapunk. ugyanis a fordítós simán megeszi, mert az nme látja előre, viszont a fentiek érvényesek. ugyanez megjátszható a = : = operátorral is, mely aritmetikai egyenlőséget vizsgál: Z is 5+1, Z = : = 6 erre Z = 6. Zbe bekerült az 5+1 értéke ami 6, majd 6=6 is jó. viszont: Z = : = 6, Z is 5+1 erre errort kapunk, mert a Z = : = 6 híváskor Z még behelyettesítetlen változó, tehát nem ismeretes az aritmetikai értéke.
és még1 típus: b/2+1 = P/Q ez első ránézésre jónak tűnik: P=b, Q=2+1. és már el is vesztettünk 1 pontot :( mi a b/2+1 végrehajtási sorrendje? b/2-t számoljuk ki először, majd utána hozzáadunk 1et. ekkor viszont P=b, Q=2 kellene, hogy a / művelet végrehajtódhasson, de akkor mi a +1? :) talán az alapstruktúra alak segíthet jobban megérteni: +(/(b,2),1) illetve: /(P,Q). másszóval: akkor lehetene egyesíteni, ha a P és Q közti / művelet lenne az utolsó, azaz mondjuk be lenne zárójelezve a 2+1. tehát röviden: figyeljünk oda a különböző precedenciájú operátorokra! másik példa erre: f+k*3 = A*B.
2. feladat
A 2. feladattal remélem meg lehet bírkózni a fentiek alapján. ETS-t továbbra is ajánlom, az egyesítések és az alapstruktúra alakok gyakorlására. 1-2 óra alatt be lehet gyakorolni sztem és az első 2 feladat a zh-n 14pont... ha hozzávesszük, hogy 24től megvan a zh, talán nem is olyan veszélyes :)
3. feladat
ez mindig olyan, hogy van egy p(+lista, +int, ?int) struktúra és akkor ezen kell valamit machinálni. az a feladat tipikusan p([], _, X) alakú. (a _ azt jelenti h mindegy milyen változó van ott, nem számít. a feladatban általában valami számot írnak oda, pl.: p([], 1, X).) erre eddig csak olyayn példát láttam amire meghiúsul. annyit kell csak csinálni, h megnézzük a klózok közt van-e olyan, aminek az első paramétere []. ha nincs akkor a válasz {no}. ha van akkor meg az alábbiak érvényesek:
- kezdjünk el prolog fordítót játszani.
- próbáljuk illeszteni a bemenetet az első klózra, ha sikerült, írjuk át a paramétereket, stb. viszont ne feledjük, hogy majd a második klózra is meg kell próbálni az illesztést.
- ha nem lehet illeszteni, akkor elakadtunk azon az ágon -> visszalépés. ezeknek a nyomonkövetéséhez akár fastruktúrát is rajzolhatunk, de nem szükséges, általában annyit kell csinálni, h megnézzük illeszthető-e az első klózra, ha igen akkor kiad valami eredményt és átlép a második klózra, ami lépteti valahogyan a listát. majd megint első klóz, ha jó akkor eredmény, ha rossza, akkor csak sima léptetés a 2. klózzal. stbstb amíg az üres listához érkezünk.
- néha van olyan h az első klóz a léptető, a második az "eredménycsináló", ez annyi, mintha fordítva (jobbról balra) járnánk be a listát. tehát az eredmények szempontjából annyi a különbség h fordított sorrendben keletkeznek, ill. az f feladatban meg szokták kérdezni, h milyen sorrendben adódnak a megoldások.
az f feladatban pedig általában a valami/3 ból valami/2-t csinálnak és azt kell kikommentezni.
4. feladat
erre nemtok mit mondani, meg kell nézni pár példát, szvsz elég hasonszőrűek.
Pár alapdolog SML-hez
- smlben a listában csak azonos típusú elemek lehetnek.
- smlben ha azt írjuk, hogy: X=3+5; akkor X=8 lesz (a prologgal ellentétben, ahol ugyebár 3+5).
- a zh-hoz nem árt tudni pár alapfgv-t, ezek fel vannak írva a zh-n is h hogyan néznek ki, onnan lehet puskázni, de ha ott látod először és lövésed nincs az egészhez, akkor nem sok esélyed van rá h eltaláld a működését. pár alap fgv, amiket nem árt megnézni: map(paraméterei 1 fgv, és 1 lista, eredménye pedig a fgv alkalmazása a listára), op@, op::, op^ és az op mindenféle fajtái. Char.isAlpha (true, ha a karakter kis v nagybetű (Char.isLower, Char.isUpper)), Char.isDigit (true, ha számjegy), ord (a karakter ascii kódja), chr (az adott ascii kódú karakter), explode (stringet "szétrobbantja" karakterfüzérré), rev (megfordítja a stringet), foldr (paramétere valami egységelem és egy lista, melyen jobbról balra végigcsinálja az adott műveletet (próbáljátok ki 1 perc alatt meg lehet érteni.)), foldl (lásd foldr, csak ez balról jobbra megy), size(string hosszával tér vissza), tl (a lista farkával tér vissza), hd (ezmeg a fejével), List.filter (ezzel ilyen listaszűrési mókákat lehet csinálni), concat(egymás után rak 2 stirnget), round(realt kerekíti intre), floor(real alsóegészrészét adja (int)), div(egészosztás, intet csak ezzel lehet osztani), mod(a div maradéka), stbstb. (jó összevisszára sikerült, így jutottak eszembe.)
- az andalso és orelse használatával nem árt tisztában lenni: andalso: és művelet, de ha az első fele hamis, akkor a második felét ki sem értékeli, orelse: ha az első fele igaz, akkor a második felét szintén nem értékeli, ki, hiszen az endalso esetében a kifejezés biztosan hamis, ha már az egyik hamis, az orelse esetében biztosan igaz, ha már az egyik igaz.
-- TitCar - 2006.04.20.
Tippek a MoSML (Moscow ML) környezet használatához, program írásához
- függvény meghívása interpreterben: fuggveny(param);
- fájl betöltése: use "C:/eleresiut/fajlnev.kit"; (tehát a Windowsos MoSML-ben is perjelet használunk, nem backslasht)
- egy könyvtár betöltése pl.: load "List"; (csak akkor kell, ha interpreterben használod, tehát házi beküldésekor kommentezd ki)
- komment: (* komment *)
- egyszerű függvény szerkezete: fun fuggvenynev(param1,param2)=fuggvenytorzs
- függvény különböző paraméterekkel más-más eredményt adjon (képzeljünk egy "fun"-t a "|" helyére):
Ez a példa írja le, ha a paraméter egy lista, ami szétbontható fejre és törzsre, akkor igazat adjon vissza, minden más esetben hamisat. Itt ugyancsak figyeljünk oda arra, hogy a visszaadott érték típusa minden esetben meg kell egyezzen.
fun f1(eleje::vege)= true | f1(_)= false
- a let lokális deklarációval lokális függvényeket is írhatunk egy függvényen belül, pl.:
fun negyzetosszeg(a,b)= let fun negyzet(x)=x*x in negyzet(a)+negyzet(b) end
-- Endre - 2007.01.06.
5. feladat
hibakeresés sml-ben tipikusan annyi h nem azonos típusokra nem lehet egyenlőségvizsgálatot illetve egyéb műveleteket végezni, ugyanis sml-ben nincs automatikus típuskonverzió. pl.:
- op<(1, 2.3) : az 1 az int, a 2.3 real --> nem hasonlíthatók össze.
- "d" = #"d"] : a "d" string, a #"d" viszont char.
egy zh példa: (chr 127, 2+4 = 4*4, ~1) = ("B", 2444, ~(5−7))
- a chr 127 az egy char lesz, a "B" viszont string
- 2+4 = 4*4 : ez egy logikai kifejezés, a 2444 viszont int.
illetve tipikusan szokott lenni olyan h valamilyen fgv-t megadnak (foldr/foldl általában), abban általában az egyik hiba az h vagy fel vannak cserélve a paraméterek, vagy nem megfelelő paramétert kapnak.
6. feladat
itt sml fordítót kell játszani, pár függvénybehelyettesítés, és kész is vagyunk :) (függvényeknek tehát nem árt utána nézni!)
7. feladat
ebből 2 félével találkozni régebbi zh-kban, az egyik gyakorlatilag a 3as feladat sml változata. a másik viszont valami adattípus deklarációs valami (pl. 2003 tavasz sima zh és pótzh, ), amiről sajna fogalmam sincs h mit kell csinálni, és nem nagyon sikerül rájönnöm, ha valaki tudja írja be ide plz.
8. feladat
ehhez se nagyon tudok konkrét tippeket adni, sml függvényt kell írni. ha ismerjük a fentebb felsorolt fgv-ket akkor remélhetőleg menni fog.
Epilógus
Egyelőre ennyi, vegyétek hasznát, ha hibát találtok, javítsátok ki, mindenki csak saját felelősségére olvassa. Ez az összefoglaló a zh-ra készült, nem programozni tanít, mert azt énse tudok... :) ui. és tudom, hogy a mondatok nagybetűvel kezdődnek, de nem szeretam a shiftet nyomogatni. :D
-- TitCar - 2006.04.20.
A favágó útja
Ezt a módszert (ami némileg talán a spanyol viasz kategóriába eshetne :)) egyesítést tartalmazó gyakorlati feladatoknál lehet/érdemes használni.
Előfeltételek:
- tudjunk alapstruktúra alakra hozni
- egyesítési algoritmus ismerete és/vagy józan ész :)
Ezeknél a feladatoknál kb. biztosra lehet menni. Az alábbi módszer ellenőrzésnél marha jól tud jönni, de ha rendesen begyakorolja az ember, nyomhatja "egyből" is ;)
Lépések:
- Alapstruktúra alakra hozzuk mindkét oldalt.
- Felírjuk egymás alá őket úgy, hogy a megfelelő zárójelek egymás alá kerüljenek.
Pl. [A,B] = [x,y,z].
1.) Hozzuk alapstruktúra alakra:
.(A, .(B, [])) = .(x, .(y, .(z, [])))
2.) Írjuk fel őket egymás alá:
.(A, .(B, [] )) = .(x, .(y, .(z, [])))
Ez az utóbbi felírás rengeteget tud segíteni, pláne a bonyolultabb feladatoknál! Gyakorlatilag ránézésre látható, hogy A = x, B = y, utána viszont problémába ütközünk: []-et kellene .(z, [])-vel (azaz [z]) egyesítenünk. Ezt nyilván nem tehetjük meg (lásd egyesítési algoritmus!), így a hívás meghiúsul.
Egy komolyabb feladatot megoldva a fenti módszerrel:
[f(A+C,B),A|B] = [f(2*3+4,[p,q])Z]
1.) Alapstruktúra alak:
.(f(+(A,C),B), .(A, B)) = .(f(+(*(2,3),4), .(p, .(q, []))), Z)
2.) Egymás alá írva:
.(f(+(A ,C), B ), .(A, B)) = .(f(+(*(2,3)),4), .(p, .(q, []))), Z )
Innen máris látható az egyesítés eredménye (az egyesítési algoritmust azért nem árt ismerni!)
A = *(2,3) = 2*3 C = 4 B = .(p, .(q, [])) = [p,q] Z = .(A, B) = .(*(2,3), .(p, .(q, []))) = [2*3, p, q]
A fenti példából egyébként még egy tanulságot levonhatunk: kellő gyakorlattal a két oldal egyes részeiről azonnal látszik, hogy felesleges őket alapstruktúra alakra kibontani. Ilyenek voltak a 2*3 és a [p,q], mivel a másik oldalon egyetlen változó (C, ill. B) állt velük szemben.
Így a fenti feladatot pörgősebben és talán átláthatóbban is meg lehet oldani:
1.) Hibrid alak: :D
.(f(+(A,C),B), .(A, B)) = .(f(+(2*3),4), [p,q]), Z)
2.) Egymás alá írva:
.(f(+(A ,C), B ), .(A, B)) = .(f(+(2*3),4), [p,q]), Z )
Ugye így máris átláthatóbb a dolog ;) Persze ha azt kérik, hogy írjuk fel az alapstruktúra alakot, akkor a fenti hibrid alakért nem fognak minket szeretni... Szóval csak ügyesen! :)
-- kronik - 2005.05.28.
