Deklaratív programozás - Tippek ZH-ra és vizsgára

← Vissza az előző oldalra – Deklaratív programozás

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:

1. Alapstruktúra alakra hozzuk mindkét oldalt.
2. 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.