Generikus programozás
17 October 2008 (ELTE programming haskell) (5 comments)A héten Rinus Plasmeijer tartott vendégelőadást a generikus programozásról funkcionális nyelvekben, bemutatva a Clean azon nyelvi elemeit, amivel explicit szupportálja ezt. Encsé a lelkemre kötötte, hogy blogjam meg, miről is van szó.
Kiinduló "Hello World"-ként tekintsük az alábbi Haskell kódot, benne két, strukturális rekurzióval definiált ekvivalenciavizsgálatot listákra és fákra:
data Tree a b ≔ Leaf a | Branch b (Tree a b) (Tree a b)
instance (Eq a) ⇒ Eq (List a) where
Cons x xs = Cons y ys ≔ x = y ∧ xs = ys
⊥ = ⊥ ≔ ↓
instance (Eq a, Eq b) ⇒ Eq (Tree a b) where
Branch x xt1 xt2 = Branch y yt1 yt2 ≔ x = y ∧ xt1 = yt1 ∧ xt2 = yt2
⊥ = ⊥ ≔ ↓
Kellően messziről nézve a fenti két függvény láthatóan megegyezik. Az általános (mondhatnám, generikus) ötlet éppen az, hogy a strukturális rekurziót mint patternt nyelvi elemmé emeljük.
A mostani tárgyaláshoz vizsgáljuk azt a leegyszerűsített világot, ahol csak algebrai típusok léteznek: két típuskonstrukciós műveletünk az unió és a direktszorzat. Ekkor tetszőleges típus reprezentálható három művelet kifejezéseként: E az elágazás; P a (kételemű) pár; U (unit) pedig az egység, a struktúra levelei. Pl. Haskellben egyszerűen bevezethető három, a fenti műveleteket reprezentáló típus, és azokkal könnyedén leírható például a fenti két adatszerkezetünk:
data E a b ≔ L a | R b
data P a b ≔ P a b
type List' a ≔ E U (P a (List a))
type Tree' a b ≔ E a (P b (P (Tree a b) (Tree a b)))
Az okosság ott van, hogy így az algebrai típusok általános leírását beemeltük a nyelvbe, és már le tudjuk írni a strukturális rekurziót, mint generikus egyenlőségvizsgálat-műveletet:
instance (Eq a, Eq b) ⇒ Eq (E a b) where
R x = R y ≔ x = y
⊥ = ⊥ ≔ ↓
instance (Eq a, Eq b) ⇒ Eq (P a b) where
Mármost könnyen mozoghatunk a valódi típus és a generikus reprezentáció között:
fromList Nil ≔ L U
fromList (Cons x xs) ≔ R (P x xs)
toList :: List' a → List a
toList (L U) ≔ Nil
toList (R (P x xs)) ≔ Cons x xs
fromTree :: Tree a b → Tree' a b
fromTree (Leaf x) ≔ L x
fromTree (Branch x xt1 xt2) ≔ R (P x (P xt1 xt2))
toTree :: Tree' a b → Tree a b
toTree (L x) ≔ Leaf x
toTree (R (P x (P xt1 xt2))) ≔ Branch x xt1 xt2
... és már csak egy kis összedrótozás kell ahhoz, hogy megkapjuk az egyenlőségvizsgálat implementációját a két konkrét típusunkra:
instance (Eq a, Eq b) ⇒ Eq (Tree a b) where
A fentiek kifejtése után az előadás szólt még arról, hogy milyen segítséget ad a Clean a fentihez hasonló programozáshoz (nyilván a fenti List', Tree' típusokat és a konverziós műveleteket ilyenkor a fordító generálja), ilyenkor tehát a fenti példában csak az U, E és P típusokra kell megírnunk a további típusokra generikusan implementálandó függvényünket.
Sajnos ezekután az utolsó két előadás már csak az iTask nevű workflow-manager webes alkalmazásról szólt, ami bár érdekes dolgokat csinál, de valójában már semmi köze nem volt az eredeti témához (főleg mivel, az eredeti ígérettel ellentétben, végül nem tért ki az előadás arra, hogy az iTask belsejében hogyan és mik vannak generikusan implementálva).
Lőry 2008-10-20 12:53:32
Ha jól látom, a Tree' definíciójából hiányzik egy P betű, ugye?
cactus 2008-10-21 09:10:18
Az csak azért volt, hogy figyeltek-e :))
Good catch, kijavítottam. Köszi-köszi!
bkil (http://bkil.blogspot.com/) 2009-08-07 22:20:38
Hát igen, ilyenek ezek a reklámelőadások...
Amúgy én találtam még benne néhány elírást. :)
* Az "R x = R y..." sor alatt egyenlőségi reláció csúszott be definiáló helyett.
* "P x1 x2" sorban 'és' körüli két tokent cserélni
* :: List/Tree helyett List a/Tree a b
Ez az előadáson vetített fóliák papiros lejegyzetelésének bepötyögése tán? :) Azt látom, hogy eddig nem volt kipróbálva, mivel a fordító a fentiekért (és Lőry észrevételéért is) mind kiabált! :D És mit használtunk színezésre?
cactus 2009-08-09 11:28:02
Köszi, javítottam.
Abba inkább ne menjünk bele, hogy ezt hogy írtam. A fóliákról nem jegyzeteltem, ezt utólag (azthiszem, valami unalmasabb előadáson) rekonstruáltam. Viszont lusta voltam valami proper toolchaint keríteni vagy készíteni, úgyhogy az lett hogy beírtam Emacsbe egy .hs file-ba az egészet, azt htmlize-buffer-rel kiírtam egy színes HTML-be, aztán azt elkezdtem kézzel átírni hogy normálisabb notáció legyen benne, mint a béna szöveges alapú. Mindeközben bekerült rengeteg elírás, hiszen nem volt roundtrip hogy a fordíthatóságot még ellenőrizni tudjam...
bkil (http://bkil.blogspot.com/) 2009-08-09 21:08:20
Az szép teljesítmény akkor, ha fejből ment az egész! Tetszenek az új vesszős elnevezések, de még mindig... :D
./generic2.hs
runhugs: Error occurred
ERROR "./generic2.hs":45 - Not enough arguments for type synonym "Tree'"
...
A Tree konstruktor ugye két argumentumú.
fromTree :: Tree a b -> Tree' a b
toTree :: Tree' a b -> Tree a b
Pár megán elfér az egész fejlesztőrendszer amennyiben beelégszünk a Hugs interpreterrel, és ebben már OpenGL és társai is benne vannak! Én is ezt használom (azért van mellette egy kis GHC6 is, mert elfér).
W1n-re a mini installere flopis!!
http://cvs.haskell.org/Hugs/pages/downloading.htm
És comment feed lesz esetleg valamikor? :D