Programowanie funkcjonalne: właściwe pomysły na współbieżność i stan?

Zwolennicy FP twierdzili, że współbieżność jest łatwa, ponieważ ich paradygmat unika stanu zmienności. Nie rozumiem

Wyobraźmy sobie, że tworzymy wieloosobowe przemierzanie lochów (roguelike) za pomocą FP, w którym kładziemy nacisk na czyste funkcje i niezmienne struktury danych. Generujemy loch składający się z pokoi, korytarzy, bohaterów, potworów i łupów. Nasz świat jest w rzeczywistości obiektowym wykresem struktur i ich relacji. Gdy rzeczy się zmieniają, nasza reprezentacja świata jest zmieniana, aby odzwierciedlić te zmiany. Nasz bohater zabija szczura, podnosi krótki miecz itp.

Dla mnie świat (obecna rzeczywistość) niesie tę ideę stanu i brakuje mi tego, jak FP to pokonuje. Gdy nasz bohater podejmuje działania, funkcje zmieniają stan świata. Wydaje się, że każda decyzja (AI lub ludzka) musi opierać się na stanie świata takim, jak jest obecnie. Gdzie pozwolilibyśmy na współbieżność? Nie możemy mieć wielu procesów jednocześnie poprawiających stan świata, aby jeden proces nie opierał swoich wyników na jakimś wygasłym stanie. Uważam, że cała kontrola powinna odbywać się w ramach jednej pętli sterowania, abyśmy zawsze przetwarzali obecny stan reprezentowany przez nasz obecny obiektowy wykres świata.

Oczywiście są sytuacje idealnie dostosowane do współbieżności (tj. Podczas przetwarzania izolowanych zadań, których stany są od siebie niezależne).

Nie widzę przydatności współbieżności w moim przykładzie i może to być problem. Być może w jakiś sposób fałszywie przedstawiam roszczenie.

Czy ktoś może lepiej reprezentować to roszczenie?

Spróbuję wskazać odpowiedź. To nie jest odpowiedź, tylko wstępna ilustracja. Odpowiedź @ jk wskazuje na prawdziwą rzecz, zamki błyskawiczne.

Wyobraź sobie, że masz niezmienną strukturę drzewa. Chcesz zmienić jeden węzeł, wstawiając dziecko. W rezultacie otrzymujesz zupełnie nowe drzewo.

Ale większość nowego drzewa jest dokładnie taka sama jak stare drzewo. Sprytna implementacja wykorzystałaby większość fragmentów drzewa, kierując wskaźniki wokół zmienionego węzła:

Książka Okasaki jest pełna takich przykładów.

Więc przypuszczam, że możesz rozsądnie zmieniać małe części świata gry przy każdym ruchu (podnieść monetę) i tylko faktycznie zmieniać małe części struktury danych twojego świata (komórka, w której zebrano monetę). Części należące tylko do przeszłych stanów zostaną z czasem usunięte.

Prawdopodobnie bierze to pod uwagę przy projektowaniu struktury świata gier danych w odpowiedni sposób. Niestety nie jestem ekspertem w tych sprawach. Zdecydowanie musi to być coś innego niż macierz NxM, której można by użyć jako zmiennej struktury danych. Prawdopodobnie powinien składać się z mniejszych elementów (korytarzy? Poszczególnych komórek?), Które wskazują na siebie, tak jak robią to węzły drzew.

Odpowiedź 9000 to połowa odpowiedzi, trwałe struktury danych pozwalają na ponowne użycie niezmienionych części.

Być może już myślisz „hej co, jeśli chcę zmienić korzeń drzewa?” tak jak w podanym przykładzie oznacza to teraz zmianę wszystkich węzłów. To tutaj Zippers przychodzą na ratunek. Umożliwiają zmianę elementu w punkcie skupienia w O (1), a punkt skupienia można przenieść w dowolne miejsce w strukturze.

Inną kwestią związaną z zamkami błyskawicznymi jest to, że zamek błyskawiczny istnieje dla praktycznie każdego typu danych, jaki chcesz

Programy w stylu funkcjonalnym stwarzają wiele możliwości korzystania z współbieżności. Za każdym razem, gdy transformujesz, filtrujesz lub agregujesz kolekcję, a wszystko jest czyste lub niezmienne, istnieje możliwość przyspieszenia operacji dzięki współbieżności.

Załóżmy na przykład, że podejmujesz decyzje AI niezależnie od siebie i bez określonej kolejności. Nie zmieniają się, wszyscy podejmują decyzję jednocześnie, a potem świat się rozwija. Kod może wyglądać następująco:

func MakeMonsterDecision curWorldState monster =
    ...
    ...
    return monsterDecision

func NextWorldState curWorldState =
    ...
    let monsterMakeDecisionForCurrentState = MakeMonsterDecision curWorldState
    let monsterDecisions = List.map monsterMakeDecisionForCurrentState activeMonsters
    ...
    return newWorldState

Masz funkcję obliczania, co zrobi potwór w danym stanie świata, i zastosowania go do każdego potwora w ramach obliczania następnego stanu świata. Jest to naturalna czynność w funkcjonalnym języku, a kompilator może wykonać krok „zastosuj go do każdego potwora” równolegle.

W imperatywnym języku będziesz bardziej skłonny do iteracji nad każdym potworem, stosując jego efekty na całym świecie. Po prostu łatwiej to zrobić w ten sposób, ponieważ nie chcesz zajmować się klonowaniem ani skomplikowanym aliasingiem. W takim przypadku kompilator nie może wykonywać obliczeń potworów równolegle, ponieważ wczesne decyzje potworów wpływają na późniejsze decyzje potworów.

Słuchając kilku Rich Hickey rozmów - ten jeden w szczególności - łagodzi mój błąd. W jednym wskazał, że jest w porządku, że współbieżne procesy mogą nie mieć najbardziej aktualnego stanu. Musiałem to usłyszeć. Problemami z trawieniem było to, że programy faktycznie byłyby w porządku, opierając decyzje na migawkach świata, które od tego czasu zostały zastąpione nowszymi. Zastanawiałem się, w jaki sposób współbieżne PR poradziło sobie z problemem oparcia decyzji na starym państwie.

W aplikacji bankowej nigdy nie chcielibyśmy opierać decyzji na migawce stanu, która od tego czasu została zastąpiona nowszą (wystąpiło wycofanie).

Ta współbieżność jest łatwa, ponieważ paradygmat FP unika stanu zmienności, jest technicznym twierdzeniem, które nie próbuje powiedzieć nic o logicznych zaletach oparcia decyzji na potencjalnie starym stanie. FP nadal ostatecznie zmienia stan modeli. Nie można tego obejść.

Zwolennicy FP twierdzili, że współbieżność jest łatwa, ponieważ ich paradygmat unika stanu zmienności. Nie rozumiem

Chciałem poruszyć to ogólne pytanie jako ktoś, kto jest funkcjonalnym neofitą, ale przez lata działał mi na oczy w zakresie skutków ubocznych i chciałbym je złagodzić z różnych powodów, w tym łatwiejszych (a konkretnie „bezpieczniejszych, mniej podatna na błędy ”). Kiedy spoglądam na moich funkcjonalnych rówieśników i to, co robią, trawa wydaje się nieco bardziej zielona i ładniej pachnie, przynajmniej pod tym względem.

Algorytmy szeregowe

To powiedziawszy, o twoim konkretnym przykładzie, jeśli twój problem ma charakter szeregowy i B nie może zostać wykonany, dopóki A nie zostanie zakończone, koncepcyjnie nie możesz uruchomić A i B równolegle, bez względu na wszystko. Musisz znaleźć sposób na przełamanie zależności między kolejnością, jak w odpowiedzi na podstawie wykonywania równoległych ruchów przy użyciu starego stanu gry, lub użyj struktury danych, która pozwala na jej niezależną modyfikację, aby wyeliminować zależność od kolejności, jak zaproponowano w innych odpowiedziach lub coś w tym rodzaju. Ale z pewnością istnieje wiele problemów z projektowaniem koncepcyjnym, takich jak ten, w których niekoniecznie wystarczy tak łatwo napisać wszystko, ponieważ wszystko jest niezmienne. Niektóre rzeczy będą miały charakter szeregowy, dopóki nie znajdziesz sprytnego sposobu na przerwanie zależności od zamówienia, jeśli to w ogóle możliwe.

Łatwiejsza współbieżność

To powiedziawszy, istnieje wiele przypadków, w których nie udaje się ujednolicić programów, które wiążą się z efektami ubocznymi w miejscach, które mogłyby potencjalnie znacznie poprawić wydajność po prostu ze względu na możliwość, że może nie być wątkowo bezpieczny. Jednym z przypadków, w których wyeliminowanie stanu zmiennego (a ściślej zewnętrznych efektów ubocznych) jest bardzo pomocne, jak widzę, jest to, że zmienia on „może być bezpieczny dla wątku” w „zdecydowanie bezpieczny dla wątku” .

Aby uczynić to zdanie nieco bardziej konkretnym, rozważmy, że daję ci zadanie zaimplementowania funkcji sortowania w C, która akceptuje komparator i używa go do sortowania tablicy elementów. Ma to być dość ogólne, ale dam ci proste założenie, że będzie on używany w porównaniu z danymi wejściowymi o takiej skali (miliony elementów lub więcej), że bez wątpienia korzystne będzie zawsze stosowanie wielowątkowej implementacji. Czy potrafisz wielowątkowo korzystać z funkcji sortowania?

Problem polega na tym, że nie możesz, ponieważ komparatory mogą wywoływać funkcje sortowaniapowodować skutki uboczne, chyba że wiesz, jak są one implementowane (lub przynajmniej udokumentowane) dla wszystkich możliwych przypadków, co jest w pewnym stopniu niemożliwe bez zdegenerowania funkcji. Komparator mógłby zrobić coś obrzydliwego, na przykład zmodyfikować zmienną globalną wewnątrz w sposób nieatomowy. 99,9999% komparatorów może tego nie zrobić, ale nadal nie możemy wielowątkowo uogólnić tej funkcji tylko z powodu 0,00001% przypadków, które mogą powodować działania niepożądane. W rezultacie być może będziesz musiał zaoferować zarówno funkcję sortowania jednowątkowego, jak i wielowątkowego oraz przekazać odpowiedzialność programistom, którzy będą z niej korzystać, aby zdecydować, którego z nich użyć na podstawie bezpieczeństwa wątków. Ludzie mogą nadal korzystać z wersji jednowątkowej i tracić możliwość wielowątkowości, ponieważ mogą być również niepewni, czy komparator jest bezpieczny dla wątków,

Istnieje ogromna siła mózgu, która może być zaangażowana w racjonalizację bezpieczeństwa nici bez rzucania wszędzie zamków, które mogą odejść, jeśli tylko mamy twarde gwarancje, że funkcje nie spowodują skutków ubocznych na teraz i na przyszłość. I jest strach: praktyczny strach, ponieważ każdy, kto zbyt wiele razy musiał debugować warunki wyścigu, prawdopodobnie wahałby się przed wielowątkowością wszystkiego, czego nie ma 110% pewności, że jest bezpieczny dla wątków i taki pozostanie. Nawet dla najbardziej paranoicznych (z których prawdopodobnie jestem przynajmniej na granicy) czysta funkcja zapewnia poczucie ulgi i pewności, którą możemy bezpiecznie nazwać równolegle.

I to jest jeden z głównych przypadków, w których uważam to za tak korzystne, jeśli można uzyskać twardą gwarancję, że takie funkcje są bezpieczne dla wątków, które można uzyskać przy użyciu czysto funkcjonalnych języków. Po drugie, języki funkcjonalne często promują tworzenie funkcji wolnych od efektów ubocznych. Mogą na przykład zapewnić trwałe struktury danych, w których wprowadzenie dość masywnej struktury danych jest dość wydajne, a następnie wydrukowanie zupełnie nowej, z niewielką jej częścią zmienioną w stosunku do oryginału bez dotykania oryginału. Osoby pracujące bez takich struktur danych mogą chcieć modyfikować je bezpośrednio i tracić po drodze bezpieczeństwo wątków.

Skutki uboczne

To powiedziawszy, nie zgadzam się z jedną częścią z całym szacunkiem dla moich funkcjonalnych przyjaciół (których uważam za super fajnych):

[...] ponieważ ich paradygmat unika stanu zmienności.

To niekoniecznie niezmienność sprawia, że ​​współbieżność jest tak praktyczna, jak ją widzę. To funkcje, które unikają powodowania skutków ubocznych. Jeśli funkcja wprowadza tablicę do sortowania, kopiuje ją, a następnie mutuje kopię w celu posortowania jej zawartości i wysyła kopię, jest ona tak samo bezpieczna dla wątków jak ta, która działa z niezmiennym typem tablicy, nawet jeśli przekazujesz to samo wejście tablica do niego z wielu wątków. Sądzę więc, że nadal istnieje miejsce na zmienne typy w tworzeniu kodu bardzo przyjaznego dla współbieżności, że tak powiem, chociaż istnieje wiele dodatkowych korzyści dla niezmiennych typów, w tym trwałych struktur danych, których używam nie tyle ze względu na ich niezmienne właściwości, ale wyeliminuj koszty głębokiego kopiowania wszystkiego, aby stworzyć funkcje wolne od skutków ubocznych.

Często wiąże się to z koniecznością narzucenia funkcji wolnych od efektów ubocznych, takich jak tasowanie i kopiowanie dodatkowych danych, być może dodatkowego poziomu pośredniego i ewentualnie GC na części trwałej struktury danych, ale patrzę na jednego z moich znajomych, który ma 32-rdzeniowa maszyna i myślę, że wymiana jest prawdopodobnie tego warta, jeśli możemy bardziej pewnie robić więcej rzeczy równolegle.