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?