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

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

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.