Programowanie funkcjonalne - niezmienność

Próbuję zrozumieć, jak radzić sobie z niezmiennymi danymi w FP (konkretnie w F #, ale inne FP też są w porządku) i przełamać stary nawyk pełnego myślenia o stanie (styl OOP). Część wybranej odpowiedzi na pytanie tutaj powtórzyło moje poszukiwanie wszelkich zapisów dotyczących problemów, które są rozwiązywane przez stanowe reprezentacje w OOP z niezmiennymi w FP (Na przykład: Kolejka z producentami i konsumentami). Wszelkie uwagi lub linki są mile widziane? Z góry dziękuję.

Edycja : Aby jeszcze bardziej wyjaśnić pytanie, w jaki sposób niezmienne struktury (np. Kolejka) będą współdzielone w wielu wątkach (np. Producent i konsument) w FP

Chociaż czasami jest to wyrażane w ten sposób, programowanie funkcjonalne¹ nie zapobiega stanowym obliczeniom. To, co robi, zmusza programistę do wyraźnego określenia stanu.

Na przykład, weźmy podstawową strukturę jakiegoś programu, używając kolejki rozkazującej (w pewnym pseudojęzycznym języku):

q := Queue.new();
while (true) {
    if (Queue.is_empty(q)) {
        Queue.add(q, producer());
    } else {
        consumer(Queue.take(q));
    }
}

Odpowiednia struktura z funkcjonalną strukturą danych kolejki (wciąż w języku imperatywnym, aby rozwiązać jedną różnicę na raz) wyglądałaby następująco:

q := Queue.empty;
while (true) {
    if (q = Queue.empty) {
        q := Queue.add(q, producer());
    } else {
        (tail, element) := Queue.take(q);
        consumer(element);
        q := tail;
    }
}

Ponieważ kolejka jest teraz niezmienna, sam obiekt się nie zmienia. W tym pseudokodzie qsama jest zmienną; przypisania q := Queue.add(…)i q := tailniech wskazują na inny obiekt. Interfejs funkcji kolejki zmienił się: każda musi zwrócić nowy obiekt kolejki wynikający z operacji.

W języku czysto funkcjonalnym, tj. W języku bez skutków ubocznych, musisz wyraźnie zaznaczyć wszystkie państwa. Ponieważ producent i konsument prawdopodobnie coś robią, ich stan musi również znajdować się w interfejsie dzwoniącego.

main_loop(q, other_state) {
    if (q = Queue.empty) {
        let (new_state, element) = producer(other_state);
        main_loop(Queue.add(q, element), new_state);
    } else {
        let (tail, element) = Queue.take(q);
        let new_state = consumer(other_state, element);
        main_loop(tail, new_state);
    }
}
main_loop(Queue.empty, initial_state)

Zauważ, że teraz każdy stan jest jawnie zarządzany. Funkcje manipulowania kolejką przyjmują kolejkę jako dane wejściowe i tworzą nową kolejkę jako dane wyjściowe. Producent i konsument również przechodzą przez swój stan.

Programowanie współbieżne nie tak dobrze pasuje do wnętrza programowania funkcyjnego, ale bardzo dobrze pasuje wokół programowania funkcyjnego. Chodzi o to, aby uruchomić kilka oddzielnych węzłów obliczeniowych i pozwolić im wymieniać wiadomości. Każdy węzeł uruchamia program funkcjonalny, a jego stan zmienia się, gdy wysyła i odbiera komunikaty.

Kontynuując przykład, ponieważ istnieje jedna kolejka, jest ona zarządzana przez jeden konkretny węzeł. Konsumenci wysyłają do tego węzła komunikat w celu uzyskania elementu. Producenci wysyłają do tego węzła komunikat o dodaniu elementu.

main_loop(q) =
    consumer->consume(q->take()) || q->add(producer->produce());
    main_loop(q)

Jedynym „uprzemysłowionym” językiem, który ma właściwą współbieżność3 jest Erlang . Nauka języka Erlang jest zdecydowanie drogą do oświecenia⁴ na temat równoczesnego programowania.

Wszyscy teraz przechodzą na języki wolne od efektów ubocznych!

¹ _{Termin ten ma kilka znaczeń; tutaj myślę, że używasz go do programowania bez skutków ubocznych, i to jest znaczenie, którego również używam.}
² _{Programowanie ze stanem niejawnym jest programowaniem imperatywnym ; orientacja obiektu jest kwestią całkowicie ortogonalną.}
³ _{Zapalne, wiem, ale mam na myśli. Wątki z pamięcią współdzieloną to język asemblera współbieżnego programowania. Przekazywanie wiadomości jest znacznie łatwiejsze do zrozumienia, a brak efektów ubocznych naprawdę świeci, gdy tylko wprowadzisz współbieżność.}
⁴ _{A pochodzi od kogoś, kto nie jest fanem Erlanga, ale z innych powodów.}

Stanowe zachowanie w języku FP jest realizowane jako transformacja ze stanu poprzedniego do nowego. Na przykład kolejka byłaby transformacją z kolejki i wartości do nowej kolejki z kolejkowaną wartością. Dequeue byłoby transformacją z kolejki na wartość i nową kolejką z usuniętą wartością. Konstrukty takie jak monady zostały opracowane w celu abstrakcyjnego przekształcenia tego stanu (i innych wyników obliczeń) w użyteczny sposób

... problemy rozwiązywane przez reprezentacje stanowe w OOP z niezmiennymi w FP (Na przykład: Kolejka z producentami i konsumentami)

Twoje pytanie brzmi „problem XY”. W szczególności koncepcja, którą cytujesz (w kolejce z producentami i konsumentami) jest w rzeczywistości rozwiązaniem, a nie „problemem”, jak to opisujesz. Wprowadza to trudność, ponieważ prosisz o czysto funkcjonalną implementację czegoś, co z natury jest nieczyste. Więc moja odpowiedź zaczyna się od pytania: jaki problem próbujesz rozwiązać?

Istnieje wiele sposobów wysyłania wyników przez wielu producentów do jednego wspólnego konsumenta. Być może najbardziej oczywistym rozwiązaniem w języku F # jest uczynienie konsumenta agentem (alias MailboxProcessor) i przekazanie producentom Postswoich wyników do agenta konsumenta. To korzysta z kolejki wewnętrznie i nie jest czysta (wysyłanie wiadomości w F # jest niekontrolowanym efektem ubocznym, nieczystością).

Jest jednak całkiem prawdopodobne, że podstawowym problemem jest coś więcej niż wzorzec zbierania rozproszonego z programowania równoległego. Aby rozwiązać ten problem, możesz utworzyć tablicę wartości wejściowych, a następnie Array.Parallel.mapnad nimi i zebrać wyniki za pomocą szeregowego Array.reduce. Alternatywnie możesz użyć funkcji z PSeqmodułu do równoległego przetwarzania elementów sekwencji.

Powinienem również podkreślić, że w myśleniu stanowym nie ma nic złego. Czystość ma zalety, ale z pewnością nie jest panaceum i powinieneś także zdawać sobie sprawę z jej wad. Rzeczywiście, właśnie dlatego F # nie jest czysto funkcjonalnym językiem: więc możesz używać zanieczyszczeń, gdy są one preferowane.

Clojure ma bardzo dobrze przemyślaną koncepcję państwa i tożsamości, która jest ściśle związana ze współbieżnością. Niezmienność odgrywa ważną rolę, wszystkie wartości w Clojure są niezmienne i można do nich uzyskać dostęp poprzez odniesienia. Referencje to coś więcej niż proste wskazówki. Zarządzają dostępem do wartości i istnieje wiele ich rodzajów o różnej semantyce. Odwołanie można zmodyfikować, aby wskazywało na nową (niezmienną) wartość, a taka zmiana z pewnością ma charakter atomowy. Jednak po modyfikacji wszystkie pozostałe wątki nadal działają na pierwotnej wartości, przynajmniej dopóki nie uzyskają dostępu do odwołania.

Gorąco polecam przeczytanie doskonałego artykułu o stanie i tożsamości w Clojure , który wyjaśnia szczegóły znacznie lepiej niż mogłem.