Generikus programozás
17 October 2008 (ELTE programming haskell) (18 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
ekg technician classes (http://www.school-funding-center.com/school-posting/the-overview-of-promising-and-lucrative-career-of-an-ekg-technician) 2012-01-23 09:29:20
, de még mindig... :D
./generic2.hs
ekg technician courses (http://www.distancelearninghelpers.com/education-articles/the-key-points-of-the-ekg-technician-responsibilities) 2012-01-24 09:30:33
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?
Buy facebook likes (http://www.fanbullet.com/facebook-fans) 2012-01-25 10:23:32
If you are into online sales business, you might certainly need the sales and marketing strategies. www.fanbullet.com does the same. They market your products to the most relevant audience and increase the chances of your product sales. All you need to do is buy facebook likes from www.fanbullet.com. Buy facebook likes
los angeles criminal defense lawyer 2012-01-26 05:34:03
a nyelvbe, és már le tudjuk írni a strukturális rekurziót, mint generikus egyenlőségvizsgálat-műveletet: los angeles criminal defense lawyer
auto insurance comparison quotes (http://www.compareautoinsurancefree.com/) 2012-02-01 15:09:56
There is no question that immediate hot water heating elements are good options to trust in terms of their water heating services. However, you need to know that not all kinds of this hot water heaters will work best for you.
apply for cash (http://www.mypaydayloanexperience.org/fast-payday-loans/payday-loan-same-day) 2012-02-01 20:09:35
I thought it was getting boring, but the last few posts are really good quality so I guess I’ll add you back to my daily bloglist. You deserve it my friend. :)
Martin 2012-02-02 08:03:33
Latest coach purses and sunglasses can be purchased at discounted rates from this coach outlet store. Web Design
Music Tickets On Sale (http://www.aossatickets.com/) 2012-02-02 09:27:37
D És mit használtunk színezésre?
Hire PHP Developer India (http://www.tantumitservices.com/web-development/php-development) 2012-02-02 11:29:43
I’ll add you back to my daily bloglist. You deserve it my friend. :)
horoscope (http://www.horoscopedujourgratuit.org/) 2012-02-02 12:08:54
ces of your product sales. All you need to do is buy facebook likes from www.fanbullet.com
SEO Lebanon 2012-02-02 13:11:00
gyenlőségvizsgálat-műveletet: los angeles criminal defense lawyerSEO Lebanon
cottage for rent ontario (http://cottageme.com/offers/all/canada/ontario) 2012-02-03 04:54:32
I had no trouble navigating through all the tabs as well as related info. The site ended up being truly simple to access. Excellent job..
spss help (http://www.spsshelp.org) 2012-02-03 15:39:40
had no trouble navigating through all the tabs as well as related info. The site ended up being truly simple to access. Excellent job.
New comment