Bird-Meertensův formalismus - Bird–Meertens formalism

The Bird-Meertensův formalismus (BMF) je počet pro odvozování programů z Specifikace (v Funkcionální programování nastavení) procesem rovnicového uvažování. Byl navržen Richard Bird a Lambert Meertens jako součást jejich práce uvnitř Pracovní skupina IFIP 2.1.

V publikacích se někdy označuje jako BMF, jako kývnutí na Backus – Naurova forma. Facetiously it is also called as Squiggol, kývnutím na ALGOL, který byl rovněž v kompetenci WG 2.1, a kvůli „klikatým“ symbolům, které používá. Méně používaný název varianty, ale ve skutečnosti první navrhovaný, je SQUIGOL.

Základní příklady a notace

Mapa je známá funkce druhého řádu, která aplikuje danou funkci na každý prvek seznamu; v BMF je psáno ${displaystyle *}$ :

{displaystyle f * [e_ {1}, tečky, e_ {n}] = [f e_ {1}, tečky, f e_ {n}].}

Rovněž, snížit je funkce, která sbalí seznam na jednu hodnotu o opakovaná aplikace binárního operátoru. Je napsán / v BMF.Taking ${displaystyle oplus}$ jako vhodný binární operátor s neutrálním prvkem E, my máme

{displaystyle oplus / [e_ {1}, dots, e_ {n}] = eoplus e_ {1} oplus dots oplus e_ {n}.}

Pomocí těchto dvou operátorů a primitiv ${displaystyle +}$ (jako obvyklý doplněk) a ${displaystyle + !!! +}$ (pro zřetězení seznamu) můžeme snadno vyjádřit součet všech prvků seznamu a zploštit funkce, jako ${displaystyle {m {sum}} = + /}$ a ${displaystyle {m {flatten}} = + !!! + /}$ , vpoint-free styl. My máme:

{displaystyle {m {sum}} [e_ {1}, tečky, e_ {n}] = + / [e_ {1}, tečky, e_ {n}] = 0 + e_ {1} + tečky + e_ {n } = součet _ {k} e_ {k}.}

{displaystyle {m {flatten}} [l_ {1}, tečky, l_ {n}] = + !!! + / [l_ {1}, tečky, l_ {n}] = [,] + !!! + ; l_ {1} + !!! + tečky + !!! +; l_ {n} = {ext {zřetězení všech seznamů}} l_ {k}.}

Odvození Kadanův algoritmus

Ukázky použitých zákonů
Zákon o propagaci mapy
Přeložte zákon o podpoře
Zobecněné Hornerovo pravidlo
Skenovat lemma
Skládací skenovací zákon

Podobně psaní ${displaystyle cdot}$ pro funkční složení a ${displaystyle land}$ pro spojení, je snadné napsat test funkce, že všechny prvky seznamu splňují predikát str, jednoduše jako ${displaystyle {m {all}} p = (land /) cdot (p *)}$ :

{displaystyle {egin {aligned} {m {all}} p [e_ {1}, dots, e_ {n}] & = (land /) cdot (p *) [e_ {1}, dots, e_ {n} ] & = země / (p * [e_ {1}, tečky, e_ {n}]) & = země / [p e_ {1}, tečky, p e_ {n}] & = p e_ {1 } přistávací body přistávací p e_ {n} & = pro všechny k. p e_ {k} .end {zarovnáno}}}

Bird (1989) algebraickou manipulací transformuje neefektivní snadno srozumitelné výrazy („specifikace“) na efektivně zapojené výrazy („programy“). Například specifikace „ ${displaystyle mathrm {max} cdot mathrm {mapa}; mathrm {sum} cdot mathrm {segs}}$ „je téměř doslovný překlad„ algoritmu součtu maximálního segmentu “,^[1] ale spuštěním tohoto funkčního programu na seznamu velikostí ${displaystyle n}$ bude to nějakou dobu trvat ${displaystyle {mathcal {O}} (n ^ {3})}$ obecně. Z toho Bird vypočítá ekvivalentní funkční program, který běží v čase ${displaystyle {mathcal {O}} (n)}$ a je ve skutečnosti funkční verzí Kadanův algoritmus.

Odvození je znázorněno na obrázku s výpočetními složitostmi^[2] uvedeny modře a aplikace právních předpisů označeny červeně. Ukázky zákonů lze otevřít kliknutím na [ukázat]; používají seznamy celých čísel, sčítání, mínus a násobení. Zápis v Bird's paper se liší od výše uvedeného: ${displaystyle mathrm {mapa}}$ , ${displaystyle mathrm {concat}}$ , a ${displaystyle mathrm {foldl}}$ odpovídají ${displaystyle *}$ , ${displaystyle mathrm {flatten}}$ a zobecněná verze ${displaystyle /}$ výše, zatímco ${displaystyle mathrm {inits}}$ a ${displaystyle mathrm {tails}}$ vypočítat seznam všech předpony a přípony jejích argumentů. Jak je uvedeno výše, funkční složení je označeno „ ${displaystyle cdot}$ ", který má nejnižší závazná přednost. V příkladech jsou seznamy obarveny hloubkou vnoření; v některých případech jsou nové operace definovány ad hoc (šedé pole).

Lemma homomorfismu a jeho aplikace na paralelní implementace

Funkce h na seznamech je seznam homomorfismus pokud existuje asociativní binární operátor ${displaystyle oplus}$ a neutrální prvek ${displaystyle e}$ tak, že platí:

{displaystyle {egin {aligned} & h [,] && = e & h (l + !!! +; m) && = h loplus h m.end {aligned}}}

The homomorfismus lemma tvrdí, že h je homomorfismus právě tehdy, když existuje operátor ${displaystyle oplus}$ a funkce F takhle ${displaystyle h = (oplus /) cdot (f *)}$ .

Velkým zájmem tohoto lemmatu je jeho aplikace na odvození vysoce paralelní implementace výpočtů. Je skutečně maličké to vidět ${displaystyle f *}$ má vysoce paralelní implementaci, stejně tak ${displaystyle oplus /}$ - nejzřejmější jako binární strom. Tedy pro jakýkoli seznam homomorfismus hexistuje paralelní implementace. Tato implementace rozdělí seznam na bloky, které jsou přiřazeny různým počítačům; každý vypočítá výsledek na svém vlastním bloku. Právě tyto výsledky procházejí sítí a jsou nakonec spojeny do jednoho. V každé aplikaci, kde je seznam enormní a výsledkem je velmi jednoduchý typ - řekněme celé číslo - jsou výhody paralelizace značné. To je základ zmenšit mapu přístup.

Viz také

Reference

^ Kde ${displaystyle mathrm {max}}$ , ${displaystyle mathrm {sum}}$ , a ${displaystyle mathrm {segs}}$ vrátí největší hodnotu, součet a seznam všech segmentů (tj. sublistů) daného seznamu.
^ Každý výraz v řádku označuje spustitelný funkční program pro výpočet maximálního součtu segmentu.

Lambert Meertens (1986). „Algoritmika: Směrem k programování jako matematické činnosti.“. V J.W. de Bakker; M. Hazewinkel; J.K. Lenstra (eds.). Matematika a informatika, CWI Monografie Svazek 1. Severní Holandsko. 289–334.
Lambert Meertens; Richard Bird (1987). „Dvě cvičení nalezená v knize o algoritmizaci“ (PDF). Severní Holandsko.
Richard S. Bird (1989). "Algebraické identity pro výpočet programu" (PDF). Počítačový deník. 32 (2): 122–126. doi:10.1093 / comjnl / 32.2.122.
Richard Bird; Oege de Moor (1997). Algebra programování, International Series in Computing Science, sv. 100. Prentice Hall. ISBN 0-13-507245-X.

Cole, Murray (1993). „Parallel Programming, List Homomorphisms and the Maximum Segment Sum Problem“. Parallel Computing: Trends and Applications, PARCO 1993, Grenoble, France. 489–492.

[1] Kde ${displaystyle mathrm {max}}$ , ${displaystyle mathrm {sum}}$ , a ${displaystyle mathrm {segs}}$ vrátí největší hodnotu, součet a seznam všech segmentů (tj. sublistů) daného seznamu.

[2] Každý výraz v řádku označuje spustitelný funkční program pro výpočet maximálního součtu segmentu.

[1]

[2]