Jakie algorytmy można wyrazić za pomocą całkowitego języka funkcjonalnego z operatorami równoległych danych?

Wyobraź sobie funkcjonalny język programowania, którego jedynymi typami danych są skalary numeryczne i dowolne zagnieżdżenia tablic. W języku nie ma żadnych możliwości nieograniczonej iteracji, dlatego następujące elementy są niedozwolone:

• wyraźne pętle (i tak niewiele zużyć bez skutków ubocznych)
• rekurencja
• arbitralne funkcje pierwszej klasy (bez kombinatora y)

Język ma jednak:

• funkcje najwyższego poziomu
• leksykalnie skalowane niech wiązania
• rozgałęziony przepływ kontrolny
• typowe skalarne funkcje matematyczne i logiczne
• jakiś prosty konstruktor tablic, taki jak fill (n, x), który tworzy tablicę n-elementową o identycznych wartościach x
• co najważniejsze: ograniczony zestaw operatorów wyższego rzędu, które wykonują iterację o strukturze równoległej (np. mapuj, zmniejszaj, skanuj, wszystkie pary).

Bardziej szczegółowo na temat operatorów równoległych danych:

• y = mapa (f, x) => y [i] = f [i]
• y = zmniejsz (f, a, x) => y = f (a, f (y [p [0]], f (y [p [1]], ...))) dla pewnej permutacji p
• y = skan (f, a, x) => y [i] = zmniejsz (f, a, y [0 ... i-1])
• y = wszystkie pary (f, x, y) => y [i, j] = f (x [i], y [j])

Moglibyśmy mieć także innych operatorów, ale aby się zakwalifikować, powinni mieć wielomianowy czas działania, być możliwym do wdrożenia w ramach rozsądnego modelu obliczeń równoległych danych i używać w większości przestrzeni wielomianowej.

Oczywiście istnieją pewne konstrukty, których nie można wyrazić w tym języku, takie jak:

while f(x) > tol:
    x <- update(x)   

Co możemy wyrazić w tym systemie? Czy ograniczamy się tylko do wyszukiwania problemów w FP? Czy możemy uchwycić wszystkie algorytmy wielomianowe? Czy istnieje jakiś minimalny zestaw operatorów dla tej klasy?

Możesz przyjrzeć się staremu językowi programowania NESL, który poważnie podchodził do tych pomysłów. Język opiera się na operacjach na kolekcjach, zasadniczo listach i listach list itd., Ale myślę, że drzewa i wykresy były również brane pod uwagę, za pomocą trudnych kodowań. Niektóre badania przeprowadzone w tym projekcie (w połowie lat 90.) mogą pomóc w udzieleniu odpowiedzi na twoje pytanie. Praca doktorska (dostępna jako książka) Guy E. Blelloch. Modele wektorowe dla obliczeń równoległych do danych. MIT Press, 1990 może dostarczyć niektórych odpowiedzi. Minęło trochę czasu, odkąd na to spojrzałem.

Prace wykonane w ramach formalizmu Bird-Meertens (BMF) również należą do tej kategorii, podobnie jak język Charity . Na stronie wikipedii Charity napisano, że język nie jest kompletny Turinga, ale może wyrażać funkcję Ackermanna, co oznacza, że ​​jest czymś więcej niż prymitywnym rekurencyjnym. Zarówno BMF, jak i Charity angażują operatorów takich jak fałdy i skany (katamorfizmy, anamorfizmy itp.) I mają swoje korzenie w teorii kategorii.

Krótka, nieprecyzyjna odpowiedź brzmi: możesz wyrazić całkiem sporo.

Moja druga odpowiedź wskazywała na błędy w obecnym języku. W tej odpowiedzi podam więcej szczegółów na temat problemów związanych ze współistnieniem fałd i rozwinięć w całym języku. Następnie zaproponuję rozwiązanie i pokażę, że wszystkie problemy w P (a nawet wiele innych) można rozwiązać w tym rozszerzonym języku.

Złożenie w całości języka pochłania listy:

fold :: (a -> b -> b) -> b -> List a -> b

Rozkładanie w całym języku generuje strumienie, które są potencjalnie nieograniczone:

unfold :: (b -> Maybe (a, b)) -> b -> Stream a

Niestety listy i strumienie żyją w różnych światach, więc operatorów tych nie można skomponować. Potrzebujemy częściowej korespondencji:

stream :: List a -> Stream a
list :: Int -> Stream a -> List a

Operator strumienia osadza listę w strumieniu ograniczonym. Funkcja listy wyodrębnia pierwsze n elementów (lub mniej, jeśli strumień kończy się wcześniej) na listę. Mamy zatem następujące równanie:

for all xs :: List a, xs == list (length xs) (stream xs)

Jako optymalizację wydajności możemy całkowicie odciąć strumienie jako pośrednią strukturę danych:

unfoldList :: Int -> (b -> Maybe (a, b)) -> b -> List a

Naszkicuję teraz dowód, że to (wraz z innymi operatorami sugerowanymi już w pierwotnym pytaniu) pozwala nam symulować dowolny algorytm wielomianowy.

Z definicji język L znajduje się w P, gdy istnieje maszyna Turinga M i wielomian p, tak że o członkostwie x w L można decydować, uruchamiając M co najwyżej p (n) iteracji, gdzie n = | x |. Standardowym argumentem stan taśmy maszyny w iteracji k można zakodować za pomocą listy długości co najwyżej 2k + 1, nawet jeśli taśma maszyny jest nieskończona.

Pomysł polega teraz na przedstawieniu przejścia M jako funkcji z list do list. Wykonanie maszyny zostanie wykonane poprzez rozwinięcie stanu początkowego za pomocą funkcji przejścia. To generuje strumień list. Założenie, że L jest w P oznacza, że ​​nie musimy szukać dalej niż elementy p (n) w strumieniu. W ten sposób możemy skomponować rozwijanie, list p(n)aby uzyskać skończoną listę. Na koniec składamy go, aby sprawdzić, czy odpowiedź na problem decyzyjny brzmi „tak”, czy „nie”.

Mówiąc bardziej ogólnie, pokazuje to, że ilekroć mamy algorytm, którego czas zakończenia może być ograniczony przez funkcję obliczalną w języku, możemy go zasymulować. To sugeruje również, dlaczego czegoś takiego jak funkcja Ackermanna nie można symulować: jest ona związana, więc występuje problem z kurczakiem i jajami.

To bardzo żywiołowy język. Spróbuj zaprogramować funkcję silni:

fact 0 = 1
fact n = n * fact (n-1)

Problem polega na tym, że twój język ma tylko fałdy, ale nie rozwija się. Naturalnym sposobem wyrażania silni jest skomponowanie rozwijania n do listy [1, 2, ..., n] ze składaniem, które rozrywa go podczas mnożenia.

Czy naprawdę interesuje Cię ten konkretny język lub ogólnie programowanie funkcjonalne w ogóle? Oczywiste jest, że Twój język może co najwyżej wyrażać algorytmy wielomianowe. System F (polimorficzny rachunek lambda) może z łatwością wyrażać potwory, takie jak funkcja Ackermanna. Nawet jeśli interesują Cię algorytmy czasu wielomianowego, często potrzebujesz super-wielomianowej przestrzeni łokciowej, aby wyrazić je naturalnie.

Edycja: Jak zauważa Dave, NESL jest jednym z najważniejszych języków programowania z równoległymi danymi, ale jest bardzo daleki od całości (nawet nie próbuje). Rodzina APL miała równoległą ścieżkę ewolucji i ma całkowity podzbiór algebraiczny (unikaj operatorów stałoprzecinkowych). Jeśli twoje pytanie koncentruje się na całościowości, David Turner napisał kilka dobrych artykułów w tej dziedzinie, choć nie specjalnie na temat programowania równoległego danych.