Deklaratív programozás - Tippek ZH-ra és vizsgára forrásának megtekintése

{{Vissza|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? <br>
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)<br>
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. 
<pre>
| ?- write_canonical(e+r+7*0).
+(+(e,r),*(7,0))
</pre>
*Egyesítés*: beírjuk a bal és jobb oldalt, köztük egyenlőség jellel.
<pre>
| ?- [1+2/3, s(X)] = [A+B, s(1)|Y].
A = 1,
B = 2/3,
X = 1,
Y = []
</pre>
*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.
<pre>
| ?- [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
</pre>
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)).

-- [[PalinkasEndre|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.
-- [[HarangozoPeter|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.
<pre>
		fun f1(eleje::vege)=
						true
		  | f1(_)=
						false
</pre>
* a let lokális deklarációval lokális függvényeket is írhatunk egy függvényen belül, pl.:
<pre>
		 fun negyzetosszeg(a,b)=
				 let 
						fun negyzet(x)=x*x
				 in
						negyzet(a)+negyzet(b)
				 end
</pre>
-- [[PalinkasEndre|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&#8722;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

-- [[HarangozoPeter|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:
<pre>
  .(A, .(B, [])) = .(x, .(y, .(z, [])))
</pre>

2.) Írjuk fel őket egymás alá:
<pre>
  .(A, .(B, []		)) =
  .(x, .(y, .(z, [])))
</pre>

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:
<pre>
.(f(+(A,C),B), .(A, B)) = .(f(+(*(2,3),4), .(p, .(q, []))), Z)
</pre>

2.) Egymás alá írva:
<pre>
.(f(+(A		,C), B				 ), .(A, B)) =
.(f(+(*(2,3)),4), .(p, .(q, []))), Z		)
</pre>

Innen máris látható az egyesítés eredménye (az egyesítési algoritmust azért nem árt ismerni!)

<pre>
A = *(2,3) = 2*3
C = 4
B = .(p, .(q, [])) = [p,q]
Z = .(A, B) = .(*(2,3), .(p, .(q, []))) = [2*3, p, q]
</pre>

----

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
<pre>
.(f(+(A,C),B), .(A, B)) = .(f(+(2*3),4), [p,q]), Z)
</pre>

2.) Egymás alá írva:
<pre>
.(f(+(A	,C), B	 ), .(A, B)) =
.(f(+(2*3),4), [p,q]), Z		)
</pre>

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! :)

-- [[BartfaiViktorJeno|kronik]] - 2005.05.28.


[[Category:Infoalap]]