Kuş-Meertens biçimciliği - Bird–Meertens formalism

Kuş-Meertens biçimciliği (BMF) bir hesap için programları türetmek itibaren özellikler (içinde işlevsel programlama bir eşitlik muhakeme süreci ile. Tarafından tasarlandı Richard Bird ve Lambert Meertens işlerinin bir parçası olarak IFIP Çalışma Grubu 2.1.

Bazen yayınlarda BMF olarak anılır, Backus-Naur formu. Şaşkınlıkla şu şekilde de anılır: Squiggolselam olarak Algol Bu, WG 2.1'in de görevindeydi ve kullandığı "dalgalı" semboller nedeniyle. Daha az kullanılan, ancak aslında ilk önerilen bir varyant adı, SQUIGOL.

Temel örnekler ve gösterimler

Harita bir listenin her elemanına belirli bir işlevi uygulayan iyi bilinen ikinci dereceden bir işlevdir; BMF'de yazılır ${displaystyle *}$ :

{displaystyle f * [e_ {1}, noktalar, e_ {n}] = [f e_ {1}, noktalar, f e_ {n}].}

Aynı şekilde, azaltmak bir listeyi tek bir değere daraltan bir işlevdir. ikili operatörün tekrarlanan uygulaması. BMF ile yazılmış / yazılmıştır. ${displaystyle oplus}$ nötr elemanlı uygun bir ikili operatör olarak e, sahibiz

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

Bu iki operatörü ve ilkelleri kullanma ${displaystyle +}$ (her zamanki ekleme olarak) ve ${displaystyle + !!! +}$ (liste birleştirme için), bir listenin tüm öğelerinin toplamını kolayca ifade edebiliriz ve düzleştirmek işlev olarak ${displaystyle {m {toplam}} = + /}$ ve ${displaystyle {m {flatten}} = + !!! + /}$ , içindenoktasız stil. Sahibiz:

{displaystyle {m {toplam}} [e_ {1}, noktalar, e_ {n}] = + / [e_ {1}, noktalar, e_ {n}] = 0 + e_ {1} + noktalar + e_ {n } = toplam _ {k} e_ {k}.}

{displaystyle {m {düzleştir}} [l_ {1}, noktalar, l_ {n}] = + !!! + / [l_ {1}, noktalar, l_ {n}] = [,] + !!! + ; l_ {1} + !!! + noktalar + !!! +; l_ {n} = {ext {tüm listelerin birleştirilmesi}} l_ {k}.}

Türetilmesi Kadane algoritması

Kullanılan kanun örnekleri
Harita tanıtım kanunu
Promosyon yasasını katlayın
Genelleştirilmiş Horner kuralı
Lemma tara
Katlamalı tarama füzyon yasası

Benzer şekilde, yazı ${displaystyle cdot}$ için fonksiyonel kompozisyon ve ${displaystyle land}$ için bağlaç, bir listenin tüm öğelerinin bir yüklemi karşıladığını test eden bir işlev yazmak kolaydır pbasitçe ${displaystyle {m {tümü}} p = (arazi /) cdot (p *)}$ :

{displaystyle {egin {hizalı} {m {tümü}} p [e_ {1}, noktalar, e_ {n}] & = (arazi /) cdot (p *) [e_ {1}, noktalar, e_ {n} ] & = arazi / (p * [e_ {1}, noktalar, e_ {n}]) & = arazi / [p e_ {1}, noktalar, p e_ {n}] & = p e_ {1 } kara noktaları yer p e_ {n} & = forall k. p e_ {k} .son {hizalı}}}

Bird (1989), verimsiz, anlaşılması kolay ifadeleri ("spesifikasyonlar"), cebirsel manipülasyon yoluyla verimli ilgili ifadelere ("programlar") dönüştürür. Örneğin, " ${displaystyle mathrm {max} cdot mathrm {map}; mathrm {sum} cdot mathrm {segs}}$ "," maksimum segment toplam algoritması "nın neredeyse gerçek bir çevirisidir,^[1] ancak bu işlevsel programı bir boyut listesinde çalıştırmak ${displaystyle n}$ zaman alacak ${displaystyle {mathcal {O}} (n ^ {3})}$ Genel olarak. Bird bundan yola çıkarak, zaman içinde çalışan eşdeğer bir işlevsel programı hesaplar. ${displaystyle {mathcal {O}} (n)}$ ve aslında işlevsel bir sürümüdür Kadane algoritması.

Türetme, hesaplama karmaşıklıkları ile resimde gösterilmiştir.^[2] mavi ile verilen hukuk uygulamaları ve kırmızıyla gösterilen hukuk uygulamaları kanun örnekleri üzerine tıklanarak açılabilir. [göstermek]; tamsayı sayıları, toplama, eksi ve çarpma listelerini kullanırlar. Bird'ün kağıdındaki notasyon, yukarıda kullanılandan farklıdır: ${displaystyle mathrm {harita}}$ , ${displaystyle mathrm {concat}}$ , ve ${displaystyle mathrm {foldl}}$ karşılık gelmek ${displaystyle *}$ , ${displaystyle mathrm {flatten}}$ ve genelleştirilmiş bir versiyonu ${displaystyle /}$ sırasıyla yukarıda ${displaystyle mathrm {inits}}$ ve ${displaystyle mathrm {kuyruklar}}$ hepsinin listesini hesapla önekler ve son ekler argümanlarının sırasıyla. Yukarıdaki gibi, işlev bileşimi " ${displaystyle cdot}$ ", en düşük olan bağlayıcı öncelik. Örnek durumlarda, listeler yuvalama derinliğine göre renklendirilmiştir; bazı durumlarda, yeni işlemler geçici olarak tanımlanır (gri kutular).

Homomorfizm lemması ve paralel uygulamalara uygulamaları

Bir işlev h listelerde bir liste homomorfizm ilişkisel bir ikili operatör varsa ${displaystyle oplus}$ ve tarafsız eleman ${displaystyle e}$ öyle ki aşağıdakiler geçerlidir:

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

homomorfizm lemma şunu belirtir h bir homomorfizmdir ancak ve ancak bir operatör varsa ${displaystyle oplus}$ ve bir işlev f öyle ki ${displaystyle h = (oplus /) cdot (f *)}$ .

Bu lemma için büyük ilgi çekici bir nokta, yüksek derecede türetmeye uygulanmasıdır. paralel hesaplama uygulamaları. Gerçekten, bunu görmek önemsizdir ${displaystyle f *}$ oldukça paralel bir uygulamaya sahiptir ve ${displaystyle oplus /}$ - en açık şekilde ikili ağaç olarak. Böylece herhangi bir liste homomorfizmi için hparalel bir uygulama var. Bu uygulama, listeyi farklı bilgisayarlara atanan parçalara böler; her biri sonucu kendi parçasında hesaplar. Ağdan geçen ve sonunda tek bir yerde birleştirilen bu sonuçlardır. Listenin çok büyük olduğu ve sonucun çok basit bir tür olduğu her uygulamada - örneğin bir tamsayı - paralelleştirmenin faydaları kayda değerdir. Bu temeli Harita indirgeme yaklaşmak.

Ayrıca bakınız

Referanslar

^ Nerede ${displaystyle mathrm {max}}$ , ${displaystyle mathrm {toplam}}$ , ve ${displaystyle mathrm {segs}}$ belirli bir listenin en büyük değerini, toplamını ve tüm segmentlerinin (yani alt listeler) listesini döndürür.
^ Bir satırdaki her ifade, maksimum segment toplamını hesaplamak için çalıştırılabilir bir işlevsel programı belirtir.

Lambert Meertens (1986). "Algoritmalar: Matematiksel bir aktivite olarak programlamaya doğru.". J.W. de Bakker; M. Hazewinkel; J.K. Lenstra (editörler). Matematik ve Bilgisayar Bilimleri, CWI Monographs Cilt 1. Kuzey-Hollanda. s. 289–334.
Lambert Meertens; Richard Bird (1987). "Algoritmalar Üzerine Bir Kitapta Bulunan İki Alıştırma" (PDF). Kuzey-Hollanda.
Richard S. Bird (1989). "Program Hesaplaması için Cebirsel Kimlikler" (PDF). Bilgisayar Dergisi. 32 (2): 122–126. doi:10.1093 / comjnl / 32.2.122.
Richard Bird; Oege de Moor (1997). Cebir Programlama, International Series in Computing Science, Cilt. 100. Prentice Hall. ISBN 0-13-507245-X.

Cole, Murray (1993). "Paralel Programlama, Homomorfizmaları Listeleme ve Maksimum Segment Toplamı Problemi". Paralel Hesaplama: Trendler ve Uygulamalar, PARCO 1993, Grenoble, Fransa. sayfa 489–492.

[1] Nerede ${displaystyle mathrm {max}}$ , ${displaystyle mathrm {toplam}}$ , ve ${displaystyle mathrm {segs}}$ belirli bir listenin en büyük değerini, toplamını ve tüm segmentlerinin (yani alt listeler) listesini döndürür.

[2] Bir satırdaki her ifade, maksimum segment toplamını hesaplamak için çalıştırılabilir bir işlevsel programı belirtir.

[1]

[2]