webhosting by: WebSupport.sk                                             UnlimitedHosting | CustomHosting | FreeWeb.sk
Home › zone

Hylomorfizmy v C++

ziman's picture
22 September, 2009 - 10:49 — ziman

Ľudia píšuci kód (prevažne vo funkcionálnych jazykoch) si všimli, že často majú ich programy podobný "tvar". Súvisí to tiež s posunom od execution-flow-centrického programovania k data-centrickému programovaniu. Inými slovami, kontrolné štruktúry (ako cykly a podobne) sa nahradili spracovaním dátových štruktúr vhodného tvaru. Vysvetlím na príklade.

Vezmime si jednoduchý program na výpočet faktoriálu. Klasický prístup je zhruba ako

int fac(int x)
{
  for (int i = 2; i < x; ++i)
    x *= i;
  return x;
}

zatiaľ čo ak namiesto explicitného iterovania použijeme rekurziu, program vyzerá takto:
int fac(int x)
{
  return x == 0 ? 1 : x * fac(x-1);
}

Keď si nakreslíme strom volaní faktoriálu, zistíme, že tvorí jedno "vlákno" dĺžky n -- vždy v i-tej úrovni voláme i-prvú -- tvar programu pre výpočet faktoriálu je teda lineárny.

Naproti tomu Fibonacciho čísla, v C++ vyjadriteľné napríklad ako:

int fib(int x)
{
  int a = 1, b = 1;
  while (x--) { int tmp = a + b; a = b; b = tmp; }
}

majú rekurzívny zápis
int fib(int x)
{
  return x <= 1 ? 1 : (fib(x-1) + fib(x-2));
}

Strom volaní pri vyčísľovaní tejto funkcie už nie je lineárny, ale rozvetvený binárny strom. Tvar programu Fibonacci je teda stromový.

Teraz si môžeme uvedomiť, že rekurzia vždy implicitne indukuje strom volaní, podobne ako v prípade faktoriálu a Fibonacciho čísel. Vo funkcionálnych jazykoch sa navyše miesto rekurzívneho volania funkcií často vyslovene vygeneruje dátová štruktúra vhodného tvaru a tá sa potom skolabuje, trebárs pri faktoriáli explicitne vygenerujeme zoznam a eliminujeme ho (Haskell):

fac n = product [1..n]

Tvary a spôsob spracovania týchto štruktúr sa však rôznia. Tvary zahŕňajú predovšetkým stromy a zoznamy, medzi spôsoby spracovania patrí napríklad vygenerovanie štruktúry (niečo na štýl pythonovského range), zredukovanie štruktúry (povedzme funkcia, ktorá vezme zoznam čísel a vráti ich súčin), alebo vygenerovanie-zredukovanie štruktúry (funkcia, ktorá berie n, vygeneruje zoznam čísel 1..n a vráti ich súčin).

Tie prvé, generujúce, sa nazývajú anamorfizmy (z gréckeho ana-, nahor; porovnaj anabolizmus), tie druhé, rozkladajúce, sa nazývajú katamorfizmy (z gréckeho kata-, nadol; porovnaj katabolizmus). Nuž a tie tretie, ktoré sú zjavne kompozíciou katamorfizmu a anamorfizmu, sa nazývajú hylomorfizmy (z gréckeho hylo-, drevo/strom).

Existujú ešte ďalšie *-morfizmy, ich prehľad uvádza Edward Kmett na svojom blogu.

Naším cieľom je implementovať hylomorfizmy v C++ na úrovni abstrakcie aspoň trochu sa bližiacej funkcionálnym jazykom s poriadnymi typovými systémami.</flame> Na to budeme potrebovať parametrický polymorfizmus (vyššieho rádu) a C++ nejakú nahrážku parametrického polymorfizmu ponúka v podobe šablón, aj keď iba prvého rádu. S tým si pri troche usilovnosti ale nejako vystačíme.

Začnime definíciou nejakých základných pomocných štruktúr.

/// Táto šablóna kóduje jednoparametrovú funkciu, berúcu Dom, vracajúcu Codom.
template <typename Dom, typename Codom>
struct Arrow
{  virtual Codom operator()(Dom x) = 0;
};
/// Táto štruktúra kóduje funktor.
template <typename A>
struct Functor
{  template <typename B>
  B fmap(A a) {
    return fmap(a);
  }
};

Pre načrtnutie pojmu funktor pre naše účely potrebujeme produkt (n-tica) a koprodukt (alias značkované zjednotenie).

Produkt množín/typov (typ je množina hodnôt) A1, A2, A3, .. An je množina/typ n-tíc (a1, a2, a3, .., an), kde a1 má typ A1, a2 má typ A2, a tak ďalej. Napríklad produkt int✕string✕int je množina trojíc, ktorých prvým prvkom je int, druhým string a tretím int (zároveň). Produkt sa značí operátorom ✕.

Naproti tomu koproduktom typov A1..An je typ, ktorého prvky neobsahujú *naraz* všetky hodnoty v n-tici, ale obsahuje buď hodnotu typu A1 alebo hodnotu typu A2 alebo hodnotu typu A3 atď. Koprodukt sa značí operátorom +.

Okrem toho si zaveďme typ Nil, ktorý obsahuje jedinú hodnotu, a to hodnotu s názvom Nil. Potom napríklad ak máme premennú x typu (Nil + (int ✕ string)), potom premenná x sa rovná buď Nil alebo nejakej dvojici (int, string).

Funktor je takýto výraz, len parametrizovaný. Funktor je (pre nás) zobrazenie z typu A do nejakej kombinácie jeho produktov a koproduktov. Príkladom funktora je funktor F(A) = Nil + (int ✕ A), ktorý je parametrizovaný typom A a ak doň dosadíme string, tak dostaneme to, čo už sme mali: F(string) = Nil + (int ✕ string).

A takéto dosadzovanie typov je už asi človeku povedomé -- sú to práve šablóny v C++.

Funktor musí spĺňať ešte jednu požiadavku -- má "metódu" fmap, ktorá ak máme funkciu z A do B (v našom prípade Arrow<A,B>), dokáže transformovať funktor F(A) na funktor F(B).

Zadefinujeme si zoznamový funktor ListF(A) = Nil + (Elm ✕ A):

/// List-generating functor: ListF(A) = Nil + (Elm x A)
template <typename Elm, typename A>
struct ListF : public Functor <A>
{ enum { Nil, Cons } tag; // na rozlíšenie, c~i je to Nil alebo dvojica
  Elm e; A a; // prvky dvojice
  /// "metóda" fmap pre zoznamový funktor
  template <typename B>
  ListF<Elm, B> fmap(Arrow<A,B> &fun) {
    ListF<Elm, B> result;
    result.tag = tag;
    if (tag != Nil) {
      // fmap the second argument
      result.e = e;
      result.a = fun(a);
    }
    return result;
  }
};

Tento zoznamový funktor generuje zoznamy (resp. množina zoznamov je jeho fixpointom) -- každý uzol v zozname je buď Nil alebo dvojica (prvok, zvyšok_zoznamu).

Ďalej si zadeklarujeme algebru a koalgebru

/// A coalgebra is a function F(A) -> A.
template <typename FA, typename A>
struct Coalgebra : public Arrow <A,FA>
{ };
/// An algebra is a function A -> F(A).
template <typename FA, typename A>
struct Algebra : public Arrow <FA,A>
{ };

Algebra je zobrazenie z F(A) do A, koalgebra je zobrazenie z A do F(A). Nebudem to tu príliš rozoberať, akurát poukážem na to, že algebra "eliminuje" funktoriálny obraz A-čka do A, zatiaľ čo koalgebra "generuje" z A nejaký (obvykle štrukturálne zložitejší) obraz F(A). A taký je aj ich účel v hylomorfizme -- koalgebry generujú, algebry eliminujú.

Keď máme zadefinované potrebné pojmy, môžeme pristúpiť k implementácii všeobecného hylomorfizmu:

/// Hylomorphisms.
template <typename FA, typename FB, typename A, typename B>
struct Hylo
{ /// Partially applied hylomorphism (on alg & coalg args) is a function.
  struct Arr : Arrow<A,B>
  { Coalgebra<FA,A> &coalg;
    Algebra<FA,A> &alg;
    Arr(Coalgebra<FA,A> &_coalg, Algebra<FA,A> &_alg)
      : coalg(_coalg), alg(_alg)
    { }
    virtual B operator()(A a)
    { Hylo<FA,FB,A,B> hylo;
      return hylo(coalg, alg, a);
    }
  };
  /// The body of the hylomorphism.
  virtual B operator()(Coalgebra<FA,A> &coalg, Algebra<FB,B> &alg, A a)
  {
    Arr arrow(coalg, alg);
    return alg(coalg(a).fmap(arrow));
  }
};

Trochu ukecané, ale neviem nájsť v C++ stručnejšie vyjadrenie takejto abstrakcie.

Ostáva zadefinovať faktoriálovú algebru a koalgebru:

/// Factorial ListF coalgebra -- generate numbers 1..a.
template <typename FA, typename A>
struct FacCoalg : public Coalgebra<FA,A>
{ virtual FA operator()(A a) {
    ListF<A,A> fa;
    if (a == 0) {
      // Z nuly vygenerujeme Nil.
      fa.tag = ListF<A,A>::Nil;
    } else {
      // Z iných cisel vygenerujeme (int x int).
      fa.tag = ListF<A,A>::Cons;
      fa.e = a;
      fa.a = a-1;
    }
    return fa;
  }
};
/// Factorial ListF algebra -- multiply numbers.
template <typename FA, typename A>
struct FacAlg : public Algebra<FA,A>
{ virtual A operator()(FA fa) {
    if (fa.tag == ListF<A,A>::Nil) {
      return 1;
    } else {
      return fa.e * fa.a;
    }
  }
};

Zatiaľ čo tvar funktora je zodpovedný za tvar medzištruktúry, tieto (ko)algebry sú zodpovedné za správne hodnoty vyplnené v medzištruktúre.

Napíšeme ešte klasický C++-kový interfejs k faktoriálu:

/// Plain old C++ interface for factorial.
int fac(int x) {
  FacCoalg<ListF<int,int>,int> coalg = FacCoalg<ListF<int,int>,int>();
  FacAlg<ListF<int,int>,int> alg = FacAlg<ListF<int,int>,int>();
  Hylo<ListF<int,int>, ListF<int,int>, int, int> fact;
  return fact(coalg,alg,x);
}
int main() {
  // First 10 factorials.
  for (int i = 0; i < 10; ++i)
    std::cout << fac(i) << " ";
  std::cout << std::endl;
}

Spustíme:

ziman@idefix ~ $ g++ morphism.cpp -o morphism
ziman@idefix ~ $ ./morphism
1 1 2 6 24 120 720 5040 40320 362880
ziman@idefix ~ $

Voila`.

Keď už máme hylomorfizmy a podporné štruktúry definované, je jednoduché doplniť Fibonacciho -- stačí napísať príslušný funktor, algebru, koalgebru a doplniť to celé do main-u.

/// Tree-generating functor: TreeF(A) = 1 + (A x Elm x A)
template <typename Elm, typename A>
struct TreeF : public Functor<A>
{  enum { Leaf, Branch } tag;
  Elm e;
  A left, right;
  template <typename B>
  TreeF<Elm,B> fmap(Arrow<A,B> &fun) {
    TreeF<Elm,B> result;
    result.tag = tag;
    if (tag != Leaf) {
      result.e = e;
      result.left = fun(left);
      result.right = fun(right);
    }
    return result;
  }
};

Máme funktor TreeF(A) = Nil + (A✕Elm✕A). Môžeme sa vrhnúť na (ko)algebru.
/// Fibonacci TreeF coalgebra -- generate tree of numbers.
template <typename FA, typename A>
struct FibCoalg : public Coalgebra<FA,A>
{  virtual FA operator()(A a) {
    TreeF<A,A> fa;
    if (a <= 0) {
      fa.tag = TreeF<A,A>::Leaf;
    } else {
      fa.tag  = TreeF<A,A>::Branch;
      fa.left  = a - 1;
      fa.right = a - 2;
    }
    return fa;
  }
};
/// Fibonacci TreeF algebra -- collapse tree of numbers.
template <typename FA, typename A>
struct FibAlg : public Algebra<FA,A>
{  virtual A operator()(FA fa) {
    if (fa.tag == TreeF<A,A>::Leaf)
      return 1;
    else
      return fa.left + fa.right;
  }
};

A ostáva už len dopísať klasickú C++ funkciu na intoch a doplniť to celé do mainu.
/// Plain old C++ interface for Fibonacci numbers.
int fib(int x) {
  FibCoalg<TreeF<int,int>,int> coalg = FibCoalg<TreeF<int,int>,int>();
  FibAlg<TreeF<int,int>,int> alg = FibAlg<TreeF<int,int>,int>();
  Hylo<TreeF<int,int>, TreeF<int,int>, int, int> fibs;
  return fibs(coalg,alg,x);
}
int main() {
  // First 10 factorials.
  for (int i = 0; i < 10; ++i)
    std::cout << fac(i) << " ";
  std::cout << std::endl;
  // First 10 fibs.
  for (int i = 0; i < 10; ++i)
    std::cout << fib(i) << " ";
  std::cout << std::endl;
  return 0;
}

Presvedčme sa, že to funguje:
ziman@idefix ~ $ g++ morphism.cpp -o morphism
ziman@idefix ~ $ ./morphism
1 1 2 6 24 120 720 5040 40320 362880
1 2 3 5 8 13 21 34 55 89
ziman@idefix ~ $

Cool. Podarilo sa nám teda zakódovať hylomorfizmy pomerne všeobecne v C++ (až na pár workaroundov, ktoré to trochu zneelegantňujú).

Netvrdím, že toto je najelegantnejší a najlepší spôsob, ako napísať v C++ faktoriál -- je to skôr proof-of-concept. Avšak abstrahovanie programov do rekurzívnych schém má množstvo výhod -- veľké možnosti pre kompilátor na optimalizáciu kódu, paralelizáciu, modularita, formálna verifikovateľnosť, eliminácia boilerplate kódu. Skombinujte to všetko s nejakým vhodným jazykom a šikovným kompilátorom -- a dostanete rýchle paralelné programy na málo riadkov s vysokou expresívnosťou.

A tam si myslím, že je budúcnosť.

edit: oh, zabudol som, cely kod je tu: http://openpaste.org/en/16881/

Average rating
(7 votes)

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
10 November, 2009 - 20:39 — casso
casso's picture

Re: Hylomorfizmy v C++

Ziman, vsetka cest, tento clanok som si s chutou presiel.
Ako sa tu popisalo, c++ nieje najlepsi jazyk v tomto smere ale coskoro sa to zmeni. Nova "verzia" C++ s oznacenim C++0x ma priniest znacny pokrok aj v tomto smere.

22 September, 2009 - 17:33 — vektor
vektor's picture

Re: Hylomorfizmy v C++

Uplna parada Zimane, vidno ze ten Matfyz na nieco je:) Kazdopadne jeden z najpokrocilejsich clankov na tomto serveri, aj ked v nie uplne najlepsom jazyku</flame> :)

_________________________
There is some SERIOUS sh*t going on right now!

29 October, 2009 - 10:11 — impact (not verified)

Re: Hylomorfizmy v C++

Dakujem za krasny clanok. Presne taketo clanky su potrebne, kedze ziadna kniha taketo komplexne riesenia neriesi. Dufam, ze bude pokracovanie.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
webhosting by: WebSupport.sk UnlimitedHosting | CustomHosting | FreeWeb.sk