Jak możesz zrobić coś użytecznego bez stanu zmiennego?

265

Czytałem ostatnio wiele rzeczy na temat programowania funkcjonalnego i rozumiem większość z nich, ale jedyną rzeczą, której po prostu nie mogę zawinąć, jest kodowanie bezstanowe. Wydaje mi się, że uproszczenie programowania poprzez usunięcie stanu zmiennego jest jak „uproszczenie” samochodu poprzez usunięcie deski rozdzielczej: gotowy produkt może być prostszy, ale powodzenia w interakcji z użytkownikami końcowymi.

Prawie każda aplikacja użytkownika, o której myślę, zawiera stan jako podstawową koncepcję. Jeśli napiszesz dokument (lub wpis SO), stan zmienia się z każdym nowym wejściem. Lub jeśli grasz w grę wideo, istnieje mnóstwo zmiennych stanu, zaczynając od pozycji wszystkich postaci, które mają tendencję do ciągłego poruszania się. Jak możesz zrobić coś przydatnego bez śledzenia zmian wartości?

Za każdym razem, gdy znajduję coś, co omawia ten problem, jest napisany bardzo technicznie funkcjonalnie, który zakłada ciężkie tło FP, którego nie mam. Czy ktoś zna sposób na wyjaśnienie tego komuś, kto dobrze i dobrze rozumie kodowanie imperatywne, ale kto jest kompletnym n00b po stronie funkcjonalnej?

EDYCJA: Jak dotąd wiele odpowiedzi próbuje mnie przekonać o zaletach niezmiennych wartości. Rozumiem tę część. To ma sens. Nie rozumiem, w jaki sposób możesz śledzić wartości, które muszą się zmieniać i ciągle zmieniać, bez zmiennych zmiennych.

Mason Wheeler
źródło
2
Zobacz to: stackoverflow.com/questions/844536/…
Sasha Chedygov
1
Osobiście uważam, że to siła i pieniądze. Obowiązuje prawo malejących zwrotów. Jeśli jesteś dość silny, może nie być zachęty, aby stać się nieco silniejszym, ale praca nie jest bolesna (a niektórzy ludzie robią to z pasją). To samo dotyczy globalnego stanu zmiennego. Osobiście wolę zaakceptować fakt, że w miarę rozwoju umiejętności kodowania dobrze jest ograniczyć ilość globalnego stanu zmiennego w moim kodzie. Może nigdy nie będzie idealny, ale dobrze jest dążyć do minimalizacji globalnego stanu zmienności.
AturSams,
Podobnie jak w przypadku pieniędzy, zostanie osiągnięty punkt, w którym zainwestowanie w nie więcej czasu, nie będzie już bardzo przydatne, a inne priorytety staną się na szczycie. Jeśli na przykład osiągniesz jak największą siłę (według mojej metafory), może to nie służyć żadnemu pożytecznemu celowi, a nawet stać się ciężarem. Ale dobrze jest nadal dążyć do tego możliwie nieosiągalnego celu i inwestować w niego umiarkowane zasoby.
AturSams,
7
W skrócie, w FP funkcje nigdy nie modyfikują stanu. W końcu zwrócą coś, co zastąpi obecny stan. Ale stan nigdy nie jest modyfikowany (mutowany) na miejscu.
jinglesthula
Istnieją sposoby na uzyskanie stanu bez mutacji (używając stosu z tego, co rozumiem), ale to pytanie jest w pewnym sensie nieistotne (nawet jeśli jest świetne). Ciężko mówić o zwięźle, ale oto post, który, mam nadzieję, odpowiada na twoje pytanie medium.com/@jbmilgrom/… . TLDR polega na tym, że semantyka nawet stanowego programu funkcjonalnego jest niezmienna, jednak obsługiwane są przebiegi komunikacyjne czarno-białe funkcji programu.
jbmilgrom

Odpowiedzi:

166

Lub jeśli grasz w grę wideo, istnieje mnóstwo zmiennych stanu, zaczynając od pozycji wszystkich postaci, które mają tendencję do ciągłego poruszania się. Jak możesz zrobić coś przydatnego bez śledzenia zmian wartości?

Jeśli jesteś zainteresowany, oto seria artykułów opisujących programowanie gier za pomocą Erlanga.

Prawdopodobnie nie spodoba ci się ta odpowiedź, ale nie dostaniesz funkcjonalnego programu, dopóki go nie użyjesz. Mogę wysłać próbki kodu i powiedzieć „Tutaj, nie widzisz ” - ale jeśli nie rozumiesz składni i zasad leżących u podstaw, twoje oczy po prostu się gapią. Z twojego punktu widzenia wygląda na to, że robię to samo co język imperatywny, ale po prostu ustanawiam wszelkie granice, aby celowo utrudnić programowanie. Z mojego punktu widzenia po prostu doświadczasz paradoksu Blub .

Na początku byłem sceptyczny, ale kilka lat temu wskoczyłem na funkcjonalny pociąg programistyczny i zakochałem się w nim. Sztuką programowania funkcjonalnego jest umiejętność rozpoznawania wzorców, określonych przypisań zmiennych i przenoszenia stanu imperatywnego na stos. Na przykład pętla for staje się rekurencją:

// Imperative
let printTo x =
    for a in 1 .. x do
        printfn "%i" a

// Recursive
let printTo x =
    let rec loop a = if a <= x then printfn "%i" a; loop (a + 1)
    loop 1

Nie jest bardzo ładna, ale mamy ten sam efekt bez mutacji. Oczywiście, gdy tylko jest to możliwe, lubimy całkowicie zapętlać i po prostu je wyodrębnić:

// Preferred
let printTo x = seq { 1 .. x } |> Seq.iter (fun a -> printfn "%i" a)

Metoda Seq.iter wyliczy kolekcję i wywoła anonimową funkcję dla każdego elementu. Bardzo przydatny :)

Wiem, że drukowanie liczb nie jest imponujące. Możemy jednak zastosować to samo podejście do gier: przytrzymaj cały stan na stosie i utwórz nowy obiekt z naszymi zmianami w wywołaniu rekurencyjnym. W ten sposób każda klatka jest bezstanową migawką gry, przy czym każda klatka po prostu tworzy zupełnie nowy obiekt z pożądanymi zmianami dowolnych bezstanowych obiektów wymagających aktualizacji. Pseudokod tego może być:

// imperative version
pacman = new pacman(0, 0)
while true
    if key = UP then pacman.y++
    elif key = DOWN then pacman.y--
    elif key = LEFT then pacman.x--
    elif key = UP then pacman.x++
    render(pacman)

// functional version
let rec loop pacman =
    render(pacman)
    let x, y = switch(key)
        case LEFT: pacman.x - 1, pacman.y
        case RIGHT: pacman.x + 1, pacman.y
        case UP: pacman.x, pacman.y - 1
        case DOWN: pacman.x, pacman.y + 1
    loop(new pacman(x, y))

Wersje imperatywna i funkcjonalna są identyczne, ale wersja funkcjonalna wyraźnie nie wykorzystuje stanu zmiennego. Kod funkcjonalny utrzymuje cały stan na stosie - miłą rzeczą w tym podejściu jest to, że jeśli coś pójdzie nie tak, debugowanie jest łatwe, wszystko czego potrzebujesz to ślad stosu.

Skaluje się do dowolnej liczby obiektów w grze, ponieważ wszystkie obiekty (lub kolekcje powiązanych obiektów) mogą być renderowane we własnym wątku.

Prawie każda aplikacja użytkownika, o której myślę, zawiera stan jako podstawową koncepcję.

W językach funkcjonalnych zamiast mutować stan obiektów, po prostu zwracamy nowy obiekt z pożądanymi zmianami. Jest bardziej wydajny niż się wydaje. Na przykład struktury danych są bardzo łatwe do przedstawienia jako niezmienne struktury danych. Na przykład stosy są niezwykle łatwe do wdrożenia:

using System;

namespace ConsoleApplication1
{
    static class Stack
    {
        public static Stack<T> Cons<T>(T hd, Stack<T> tl) { return new Stack<T>(hd, tl); }
        public static Stack<T> Append<T>(Stack<T> x, Stack<T> y)
        {
            return x == null ? y : Cons(x.Head, Append(x.Tail, y));
        }
        public static void Iter<T>(Stack<T> x, Action<T> f) { if (x != null) { f(x.Head); Iter(x.Tail, f); } }
    }

    class Stack<T>
    {
        public readonly T Head;
        public readonly Stack<T> Tail;
        public Stack(T hd, Stack<T> tl)
        {
            this.Head = hd;
            this.Tail = tl;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Stack<int> x = Stack.Cons(1, Stack.Cons(2, Stack.Cons(3, Stack.Cons(4, null))));
            Stack<int> y = Stack.Cons(5, Stack.Cons(6, Stack.Cons(7, Stack.Cons(8, null))));
            Stack<int> z = Stack.Append(x, y);
            Stack.Iter(z, a => Console.WriteLine(a));
            Console.ReadKey(true);
        }
    }
}

Powyższy kod konstruuje dwie niezmienne listy, dołącza je razem, aby utworzyć nową listę, i dołącza wyniki. Nigdzie w aplikacji nie jest używany żaden stan zmienny. Wygląda trochę nieporęcznie, ale to tylko dlatego, że C # jest pełnym językiem. Oto równoważny program w F #:

type 'a stack =
    | Cons of 'a * 'a stack
    | Nil

let rec append x y =
    match x with
    | Cons(hd, tl) -> Cons(hd, append tl y)
    | Nil -> y

let rec iter f = function
    | Cons(hd, tl) -> f(hd); iter f tl
    | Nil -> ()

let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
let y = Cons(5, Cons(6, Cons(7, Cons(8, Nil))))
let z = append x y
iter (fun a -> printfn "%i" a) z

Nie wymaga modyfikacji w celu tworzenia i manipulowania listami. Prawie wszystkie struktury danych można łatwo przekonwertować na ich funkcjonalne odpowiedniki. Napisałem tutaj stronę , która zapewnia niezmienne implementacje stosów, kolejek, stosów lewaków, czerwono-czarnych drzew, leniwych list. Żaden fragment kodu nie zawiera żadnego stanu podlegającego zmianom. Aby „mutować” drzewo, tworzę zupełnie nowy z nowym węzłem, który chcę - jest to bardzo wydajne, ponieważ nie muszę robić kopii każdego węzła w drzewie, mogę ponownie użyć starych w moim nowym drzewo.

Korzystając z bardziej znaczącego przykładu, napisałem również ten parser SQL, który jest całkowicie bezstanowy (a przynajmniej mój kod jest bezstanowy, nie wiem, czy podstawowa biblioteka leksykalna jest bezstanowa).

Programowanie bezstanowe jest tak samo wyraziste i potężne, jak programowanie stanowe, wymaga jedynie odrobiny praktyki, aby nauczyć się, jak zacząć myśleć bezpaństwowo. Oczywiście „programowanie bezstanowe, gdy to możliwe, programowanie stanowe tam, gdzie to konieczne” wydaje się być mottem najbardziej nieczystych języków funkcjonalnych. Nie ma nic złego w spadaniu na rzeczy zmienne, gdy funkcjonalne podejście po prostu nie jest tak czyste ani wydajne.

Julia
źródło
7
Podoba mi się przykład Pacmana. Ale to może rozwiązać jeden problem tylko po to, aby podnieść inny: Co jeśli coś innego zawiera odniesienie do istniejącego obiektu Pacman? Wtedy nie będzie zbierane śmieci i zastępowane; zamiast tego otrzymujesz dwie kopie obiektu, z których jedna jest nieprawidłowa. Jak poradzisz sobie z tym problemem?
Mason Wheeler,
9
Oczywiście musisz stworzyć nowe „coś innego” z nowym obiektem Pacmana;) Oczywiście, jeśli pójdziemy tą drogą za daleko, w końcu za każdym razem coś się zmieni. Lepsze podejście opisano tutaj ( prog21.dadgum.com/26.html ): zamiast obiektów aktualizować siebie i wszystkie swoje zależności, o wiele łatwiej jest przekazywać komunikaty o ich stanie do pętli zdarzeń, która obsługuje wszystkie aktualizacja. Dzięki temu znacznie łatwiej jest zdecydować, które obiekty na wykresie wymagają aktualizacji, a które nie.
Juliet
6
@Juliet, mam jedną wątpliwość - w moim absolutnie imperatywnym sposobie myślenia rekursja musi się w pewnym momencie skończyć, w przeciwnym razie doprowadzisz do przepełnienia stosu. W rekurencyjnym przykładzie Pacmana, w jaki sposób stos jest trzymany w ryzach - czy obiekt jest domyślnie wyskakujący na początku funkcji?
BlueStrat
9
@BlueStrat - dobre pytanie ... jeśli jest to „wywołanie ogonowe” ... tj. Wywołanie rekurencyjne jest ostatnią rzeczą w funkcji ... to system nie musi generować nowej ramki stosu ... może wystarczy ponownie użyć poprzedniego. Jest to powszechna optymalizacja funkcjonalnych języków programowania. en.wikipedia.org/wiki/Tail_call
reteptilian
4
@MichaelOsofsky, podczas interakcji z bazami danych i interfejsami API, zawsze istnieje „świat zewnętrzny”, który ma stan do komunikowania się. W takim przypadku nie możesz przejść w 100% funkcjonalny. Ważne jest, aby ten „niefunkcjonalny” kod był izolowany i abstrakcyjny, aby istniał tylko jeden wpis i jedno wyjście do świata zewnętrznego. W ten sposób możesz zachować resztę kodu.
Chielt
76

Krótka odpowiedź: nie możesz.

Więc co to za zamieszanie związane z niezmiennością?

Jeśli dobrze znasz język imperatywny, to wiesz, że „globały są złe”. Czemu? Ponieważ wprowadzają (lub mogą potencjalnie wprowadzać) pewne bardzo trudne do rozplątania zależności w kodzie. I zależności nie są dobre; chcesz, aby Twój kod był modułowy . Części programu nie wpływają na inne części w jak najmniejszym stopniu. I FP doprowadza cię do świętego Graala modułowość: bez skutków ubocznych w ogóle . Po prostu masz swoje f (x) = y. Wstaw x, wyjmij. Brak zmian w x lub cokolwiek innego. FP sprawia, że ​​przestajesz myśleć o stanie i zaczynasz myśleć w kategoriach wartości. Wszystkie twoje funkcje po prostu otrzymują wartości i tworzą nowe wartości.

Ma to kilka zalet.

Po pierwsze, brak efektów ubocznych oznacza prostsze programy, łatwiejsze do uzasadnienia. Nie martw się, że wprowadzenie nowej części programu zakłóci i spowoduje awarię istniejącej, działającej części.

Po drugie, sprawia, że ​​program można w prosty sposób zrównoleglać (sprawna równoległość to inna sprawa).

Po trzecie, istnieją pewne możliwe zalety wydajności. Powiedz, że masz funkcję:

double x = 2 * x

Teraz wpiszesz wartość 3 w, a otrzymasz wartość 6 w. Każdego razu. Ale możesz to zrobić również w trybie rozkazującym, prawda? Tak. Problem polega jednak na tym, że w trybie rozkazującym możesz zrobić jeszcze więcej . Mogę zrobić:

int y = 2;
int double(x){ return x * y; }

ale mógłbym też

int y = 2;
int double(x){ return x * (y++); }

Kompilator imperatywny nie wie, czy będę miał skutki uboczne, czy nie, co utrudnia optymalizację (tzn. Podwójne 2 nie muszą być za każdym razem 4). Funkcjonalny wie, że tego nie zrobię - dlatego może optymalizować za każdym razem, gdy zobaczy „podwójne 2”.

Teraz, mimo że tworzenie nowych wartości za każdym razem wydaje się niezwykle marnotrawstwem dla złożonych typów wartości w zakresie pamięci komputera, nie musi tak być. Ponieważ jeśli masz f (x) = y, a wartości xiy są „w większości takie same” (np. Drzewa, które różnią się tylko kilkoma liśćmi), to xiy mogą współdzielić części pamięci - ponieważ żadna z nich nie ulegnie mutacji .

Więc jeśli ta niezmienna rzecz jest tak wspaniała, dlaczego odpowiedziałem, że nie można zrobić nic użytecznego bez stanu zmiennego. Bez mutacji cały program byłby gigantyczną funkcją f (x) = y. To samo dotyczy wszystkich części twojego programu: po prostu funkcje i funkcje w „czystym” sensie. Jak powiedziałem, oznacza to f (x) = y za każdym razem. Na przykład readFile („myFile.txt”) musiałby za każdym razem zwracać tę samą wartość ciągu. Niezbyt przydatne.

Dlatego każdy FP zapewnia pewne środki do mutowania stanu. „Czyste” języki funkcjonalne (np. Haskell) robią to przy użyciu nieco przerażających pojęć, takich jak monady, podczas gdy „nieczyste” (np. ML) pozwalają na to bezpośrednio.

I oczywiście, języki funkcjonalne są dostarczane z wieloma innymi dodatkami, które zwiększają wydajność programowania, takimi jak funkcje pierwszej klasy itp.

oggy
źródło
2
<< readFile („myFile.txt”) musiałby zwracać tę samą wartość ciągu za każdym razem. Nie jest zbyt przydatny. >> Myślę, że jest przydatny, dopóki ukrywasz globalny system plików. Jeśli weźmiesz to za drugi parametr i pozwolisz innym procesom zwrócić nowe odniesienie do systemu plików za każdym razem, gdy zmodyfikują go za pomocą fileystem2 = write (system plików 1, fd, pos, „string”), i pozwól wszystkim procesom na wymianę odniesień do systemu plików , możemy uzyskać znacznie czystszy obraz systemu operacyjnego.
węgorz ghEEz
@eelghEEz, to jest to samo podejście, które Datomic stosuje do baz danych.
Jason
1
+1 za jasne i zwięzłe porównanie paradygmatów. Jedną z sugestii jest to, int double(x){ return x * (++y); }że bieżąca nadal będzie mieć 4, chociaż nadal ++ybędzie
miało niezadeklarowany
@eelghEEz Nie jestem pewny alternatywy, naprawdę, czy ktoś jeszcze? Aby wprowadzić informacje do (czysto) kontekstu FP, „wykonujesz pomiar”, np. „W znaczniku czasu X temperatura wynosi Y”. Jeśli ktoś prosi o temperaturę, może domyślnie oznaczać X = teraz, ale nie może prosić o temperaturę jako uniwersalną funkcję czasu, prawda? FP zajmuje się stanem niezmiennym i musisz stworzyć stan niezmienny - ze źródeł wewnętrznych i zewnętrznych - ze stanu zmiennego. Wskaźniki, znaczniki czasu itp. Są przydatne, ale prostopadłe do zmienności - podobnie jak VCS mają same kontrolować wersję.
John P,
29

Zauważ, że stwierdzenie, że programowanie funkcjonalne nie ma „stanu”, jest nieco mylące i może być przyczyną zamieszania. Zdecydowanie nie ma „stanu zmiennego”, ale nadal może mieć manipulowane wartości; po prostu nie można ich zmienić na miejscu (np. musisz utworzyć nowe wartości ze starych wartości).

Jest to rażące nadmierne uproszczenie, ale wyobraź sobie, że masz język OO, w którym wszystkie właściwości klas są ustawione tylko raz w konstruktorze, wszystkie metody są funkcjami statycznymi. Nadal możesz wykonywać prawie dowolne obliczenia, stosując metody pobierające obiekty zawierające wszystkie wartości, których potrzebują do swoich obliczeń, a następnie zwracające nowe obiekty z wynikiem (być może nawet nową instancję tego samego obiektu).

Przetłumaczenie istniejącego kodu na ten paradygmat może być „trudne”, ale dzieje się tak, ponieważ naprawdę wymaga zupełnie innego sposobu myślenia o kodzie. Jako efekt uboczny w większości przypadków masz dużo okazji do równoległości za darmo.

Dodatek: (Jeśli chodzi o edycję sposobu śledzenia wartości, które należy zmienić)
Będą one oczywiście przechowywane w niezmiennej strukturze danych ...

Nie jest to sugerowane „rozwiązanie”, ale najłatwiejszym sposobem, aby przekonać się, że to zawsze zadziała, jest zapisanie tych niezmiennych wartości w strukturze podobnej do mapy (słownika / tablicy mieszającej), kluczowanej „nazwą zmiennej”.

Oczywiście w praktycznych rozwiązaniach zastosowałbyś bardziej rozsądne podejście, ale pokazuje to ten najgorszy przypadek, jeśli nic innego nie zadziałałoby, możesz „zasymulować” stan zmienny za pomocą mapy, którą przenosisz przez drzewo wywołań.

jerryjvl
źródło
2
OK, zmieniłem tytuł. Twoja odpowiedź wydaje się jednak prowadzić do jeszcze gorszego problemu. Jeśli będę musiał odtworzyć każdy obiekt za każdym razem, gdy coś w jego stanie się zmieni, poświęcę cały mój procesor na tworzenie innych obiektów. Myślę tutaj o programowaniu gier, w którym na ekranie (i poza ekranem) porusza się wiele rzeczy, które muszą być w stanie ze sobą współdziałać. Cały silnik ma ustawioną liczbę klatek na sekundę: wszystko, co zamierzasz zrobić, musisz zrobić w liczbie X milisekund. Z pewnością jest lepszy sposób niż ciągłe recykling całych przedmiotów?
Mason Wheeler,
4
Piękno polega na tym, że przypisywanie dotyczy języka, a nie implementacji. Za pomocą kilku sztuczek możesz mieć przypisany stan w języku, podczas gdy implementacja faktycznie zmienia ten stan. Zobacz na przykład monadę ST Haskella.
CesarB
4
@Mason: Chodzi o to, że kompilator może znacznie lepiej zdecydować, gdzie jest bezpieczna (wątek) zmienić stan w miejscu niż ty.
jerryjvl
Uważam, że w przypadku gier należy unikać niezmiennych elementów, w których prędkość nie ma znaczenia. Podczas gdy niezmienny język może dla ciebie zoptymalizować, nic nie będzie szybsze niż modyfikowanie pamięci, które procesory robią szybko. Jeśli więc okaże się, że jest 10 lub 20 miejsc, w których potrzebujesz imperatywu, myślę, że powinieneś po prostu całkowicie unikać niezmienności, chyba że możesz modulować to dla bardzo oddzielnych obszarów, takich jak menu gry. Szczególnie logika gier może być niezłym miejscem do zastosowania niezmiennego, ponieważ uważam, że świetnie nadaje się do wykonywania złożonego modelowania czystych systemów, takich jak reguły biznesowe.
LegendLength
@LegendLength zaprzeczasz sobie.
Ixx
18

Myślę, że istnieje niewielkie nieporozumienie. Czyste programy funkcjonalne mają stan. Różnica polega na sposobie modelowania tego stanu. W czystym programowaniu funkcjonalnym stanem manipulują funkcje, które przyjmują pewien stan i zwracają następny stan. Sekwencjonowanie przez stany jest następnie osiągane przez przekazanie stanu przez sekwencję czystych funkcji.

W ten sposób można modelować nawet globalny stan zmiennych. Na przykład w Haskell program jest funkcją od świata do świata. To znaczy, przechodzisz przez cały wszechświat , a program zwraca nowy wszechświat. W praktyce jednak musisz jedynie wchodzić w te części wszechświata, którymi naprawdę interesuje się twój program. Programy zwracają sekwencję działań, które służą jako instrukcje dla środowiska operacyjnego, w którym działa program.

Chciałeś zobaczyć to wyjaśnione w kategoriach programowania imperatywnego. OK, spójrzmy na naprawdę proste programowanie imperatywne w funkcjonalnym języku.

Rozważ ten kod:

int x = 1;
int y = x + 1;
x = x + y;
return x;

Dość standardowy kod imperatywny. Nie robi nic interesującego, ale można to zilustrować ilustracją. Myślę, że zgodzisz się, że w grę wchodzi tu państwo. Wartość zmiennej x zmienia się w czasie. Teraz zmieńmy nieco notację poprzez wynalezienie nowej składni:

let x = 1 in
let y = x + 1 in
let z = x + y in z 

Umieść nawiasy, aby wyjaśnić, co to oznacza:

let x = 1 in (let y = x + 1 in (let z = x + y in (z)))

Widzicie więc, stan jest modelowany przez sekwencję czystych wyrażeń, które wiążą wolne zmienne następujących wyrażeń.

Przekonasz się, że ten wzór może modelować dowolny stan, nawet IO.

Apokalipsa
źródło
Czy to trochę jak monada?
CMCDragonkai
Rozważ to: A jest deklaratywne na poziomie 1 B jest deklaratywne na poziomie 2, uważa A za konieczne. C jest deklaratywne na poziomie 3, uważa B za konieczne. Gdy zwiększamy warstwę abstrakcji, zawsze uważa ona języki na warstwie abstrakcji za bardziej konieczne niż ona sama.
CMCDragonkai
14

Oto, w jaki sposób piszesz kod bez stanu zmiennego : zamiast zmieniać stan w zmienne zmienne, umieszczasz go w parametrach funkcji. Zamiast pisać pętle, piszesz funkcje rekurencyjne. Na przykład ten kod imperatywny:

f_imperative(y) {
  local x;
  x := e;
  while p(x, y) do
    x := g(x, y)
  return h(x, y)
}

staje się tym kodem funkcjonalnym (składnia podobna do schematu):

(define (f-functional y) 
  (letrec (
     (f-helper (lambda (x y)
                  (if (p x y) 
                     (f-helper (g x y) y)
                     (h x y)))))
     (f-helper e y)))

lub ten kod Haskellisha

f_fun y = h x_final y
   where x_initial = e
         x_final   = loop x_initial
         loop x = if p x y then loop (g x y) else x

Co do tego, dlaczego programiści funkcjonalni lubią to robić (o co nie pytałeś), im więcej kawałków twojego programu jest bezstanowych, tym więcej jest sposobów na łączenie kawałków bez niczego . Siła bezpaństwowego paradygmatu nie polega na bezpaństwowości (lub czystości) per se , ale na zdolności, jaką daje ci pisanie potężnych funkcji wielokrotnego użytku i łączenie ich.

Dobry samouczek z wieloma przykładami można znaleźć w artykule Johna Hughesa Dlaczego programowanie funkcjonalne ma znaczenie .

Norman Ramsey
źródło
13

To tylko różne sposoby robienia tego samego.

Rozważ prosty przykład, taki jak dodanie liczb 3, 5 i 10. Wyobraź sobie, że możesz to zrobić, najpierw zmieniając wartość 3, dodając 5, a następnie dodając 10 do tego „3”, a następnie wyprowadzając bieżącą wartość „ 3 "(18). Wydaje się to absurdalnie śmieszne, ale w rzeczywistości jest to sposób, w jaki często odbywa się programowanie imperatywne oparte na stanie. Rzeczywiście, możesz mieć wiele różnych „3”, które mają wartość 3, ale są różne. Wszystko to wydaje się dziwne, ponieważ jesteśmy tak głęboko zakorzenieni w, bardzo rozsądnie, przekonaniu, że liczby są niezmienne.

Pomyśl teraz o dodaniu 3, 5 i 10, gdy przyjmujesz wartości za niezmienne. Dodajesz 3 i 5, aby uzyskać kolejną wartość, 8, a następnie dodajesz 10 do tej wartości, aby uzyskać jeszcze jedną wartość, 18.

Są to równoważne sposoby robienia tego samego. Wszystkie niezbędne informacje istnieją w obu metodach, ale w różnych formach. W jednym informacja istnieje jako stan oraz w zasadach zmiany stanu. Z drugiej strony informacje istnieją w niezmiennych danych i definicjach funkcjonalnych.

Klin
źródło
10

Spóźniłem się do dyskusji, ale chciałem dodać kilka punktów dla osób, które mają problemy z funkcjonalnym programowaniem.

  1. Języki funkcjonalne zachowują dokładnie te same aktualizacje stanu, co języki imperatywne, ale robią to, przekazując zaktualizowany stan do kolejnych wywołań funkcji . Oto bardzo prosty przykład podróży w dół linii liczbowej. Twój stan to Twoja bieżąca lokalizacja.

Najpierw sposób rozkazujący (w pseudokodzie)

moveTo(dest, cur):
    while (cur != dest):
         if (cur < dest):
             cur += 1
         else:
             cur -= 1
    return cur

Teraz funkcjonalny sposób (w pseudokodzie). Opieram się mocno na operatorze trójskładnikowym, ponieważ chcę, aby ludzie z niezbędnego pochodzenia mogli faktycznie czytać ten kod. Jeśli więc nie używasz operatora trójskładnikowego (zawsze unikałem go w moich bezwzględnych dniach), oto jak to działa.

predicate ? if-true-expression : if-false-expression

Możesz połączyć wyrażenie trójskładnikowe, umieszczając nowe wyrażenie trójskładnikowe zamiast wyrażenia fałszywego

predicate1 ? if-true1-expression :
predicate2 ? if-true2-expression :
else-expression

Mając to na uwadze, oto wersja funkcjonalna.

moveTo(dest, cur):
    return (
        cur == dest ? return cur :
        cur < dest ? moveTo(dest, cur + 1) : 
        moveTo(dest, cur - 1)
    )

To jest trywialny przykład. Gdyby to poruszało ludzi w świecie gry, musiałbyś wprowadzić efekty uboczne, takie jak narysowanie aktualnej pozycji obiektu na ekranie i wprowadzenie odrobiny opóźnienia w każdym wywołaniu w zależności od tego, jak szybko obiekt się porusza. Ale nadal nie potrzebujesz stanu zmiennego.

  1. Lekcja jest taka, że ​​języki funkcjonalne „mutują”, wywołując funkcję z różnymi parametrami. Oczywiście to tak naprawdę nie mutuje żadnych zmiennych, ale w ten sposób uzyskuje się podobny efekt. Oznacza to, że musisz przyzwyczaić się do myślenia rekurencyjnego, jeśli chcesz programować funkcjonalnie.

  2. Nauka rekurencyjnego myślenia nie jest trudna, ale wymaga zarówno praktyki, jak i zestawu narzędzi. Ta niewielka część książki „Naucz się języka Java”, w której użyli rekurencji do obliczenia silni, nie ją wycina. Potrzebujesz zestawu umiejętności, takich jak tworzenie iteracyjnych procesów z rekurencji (dlatego rekurencja ogona jest niezbędna dla funkcjonalnego języka), kontynuacji, niezmienników itp. Nie zrobiłbyś programowania OO bez wiedzy o modyfikatorach dostępu, interfejsach itp. To samo do programowania funkcjonalnego.

Moje zalecenie to zrobić Mały Schemer (zauważ, że mówię „rób”, a nie „czytaj”), a następnie wykonaj wszystkie ćwiczenia w SICP. Kiedy skończysz, będziesz miał inny mózg niż na początku.

Just Another Justin
źródło
8

W rzeczywistości dość łatwo jest mieć coś, co wygląda jak stan zmienny, nawet w językach bez tego stanu.

Rozważ funkcję z typem s -> (a, s). Tłumaczenie ze składni Haskella oznacza funkcję, która pobiera jeden parametr typu „ s” i zwraca parę wartości typów „ a” i „ s”. Jeśli sjest to typ naszego stanu, ta funkcja przyjmuje jeden stan i zwraca nowy stan, a być może także wartość (zawsze możesz zwrócić „unit” aka (), co jest swego rodzaju odpowiednikiem „ void” w C / C ++, jako „ a” rodzaj). Jeśli połączysz kilka wywołań funkcji tego typu (przywracanie stanu z jednej funkcji i przekazywanie jej do następnej), masz stan „zmienny” (w rzeczywistości jesteś w każdej funkcji, tworząc nowy stan i porzucając stary) ).

Łatwiej jest to zrozumieć, jeśli wyobrażasz sobie zmienny stan jako „przestrzeń”, w której wykonuje się twój program, a następnie pomyśl o wymiarze czasu. W chwili t1 „przestrzeń” jest w pewnym stanie (powiedzmy na przykład, że pewne miejsce w pamięci ma wartość 5). W późniejszym momencie t2 jest w innym stanie (na przykład lokalizacja pamięci ma teraz wartość 10). Każdy z tych „wycinków” jest stanem i jest niezmienny (nie można cofnąć się w czasie, aby je zmienić). Z tego punktu widzenia przeszedłeś od pełnej czasoprzestrzeni ze strzałką czasową (stan zmienny) do zestawu wycinków czasoprzestrzeni (kilka niezmiennych stanów), a twój program traktuje każdy wycinek jako wartość i oblicza każdy z nich z nich jako funkcja zastosowana do poprzedniej.

OK, może nie było to łatwiejsze do zrozumienia :-)

Może się wydawać, że użyteczne jest jawne przedstawienie całego stanu programu jako wartości, którą należy utworzyć tylko po to, aby została odrzucona w następnej chwili (zaraz po utworzeniu nowej). W przypadku niektórych algorytmów może to być naturalne, ale gdy tak nie jest, istnieje inna sztuczka. Zamiast stanu rzeczywistego można użyć stanu fałszywego, który jest niczym więcej niż znacznikiem (nazwijmy typ tego fałszywego stanu State#). Ten fałszywy stan istnieje z punktu widzenia języka i jest przekazywany jak każda inna wartość, ale kompilator całkowicie go pomija podczas generowania kodu maszynowego. Służy jedynie do zaznaczenia sekwencji wykonania.

Załóżmy na przykład, że kompilator udostępnia nam następujące funkcje:

readRef :: Ref a -> State# -> (a, State#)
writeRef :: Ref a -> a -> State# -> (a, State#)

Tłumaczenie z tych deklaracji podobnych do Haskella, readRefotrzymuje coś, co przypomina wskaźnik lub uchwyt do wartości typu „ a” i fałszywego stanu, i zwraca wartość typu „ a” wskazaną przez pierwszy parametr i nowy fałszywy stan. writeRefjest podobny, ale zmienia zamiast tego wskazaną wartość.

Jeśli wywołasz, readRefa następnie przekażesz fałszywy stan zwrócony przez writeRef(być może z innymi wywołaniami niezwiązanych funkcji w środku; te wartości stanu tworzą „łańcuch” wywołań funkcji), zwróci zapisaną wartość. Możesz zadzwonić writeRefponownie z tym samym wskaźnikiem / uchwytem i zapisze w tej samej lokalizacji w pamięci - ale ponieważ koncepcyjnie zwraca nowy (fałszywy) stan, (fałszywy) stan jest nadal możliwy do przypisania (nowy został „utworzony” „). Kompilator będzie wywoływał funkcje w kolejności, w jakiej musiałby je wywoływać, gdyby istniała zmienna stanu rzeczywistego, którą trzeba było obliczyć, ale jedynym stanem, który istnieje, jest pełny (zmienny) stan rzeczywistego sprzętu.

(Ci, którzy znają Haskell zauważy I uprościć wiele rzeczy, pominięte i kilka ważnych szczegółów. Dla tych, którzy chcą zobaczyć więcej szczegółów, zapoznać się Control.Monad.Statez mtl, i na ST si IO(aka ST RealWorld) monad).

Możesz się zastanawiać, dlaczego robisz to w taki okrągły sposób (zamiast po prostu mieć zmienny stan w języku). Prawdziwą zaletą jest to, że poprawiłeś stan swojego programu. To, co wcześniej było niejawne (stan twojego programu był globalny, pozwalając na działania takie jak działanie na odległość ) jest teraz jawne. Funkcje, które nie odbierają i nie zwracają stanu, nie mogą go modyfikować ani na niego wpływać; są „czyste”. Co więcej, możesz mieć osobne wątki stanu, a przy odrobinie magii typu można je wykorzystać do osadzenia obliczeń imperatywnych w czystym, nie czyniąc go nieczystym ( STmonada w Haskell jest zwykle używana do tej sztuczki; State#wspomniałem powyżej jest fakt GHC użytkownika State# s, używane przez jego wdrażania STiIO monady).

CesarB
źródło
7

Programowanie funkcjonalne pozwala uniknąć stanu i podkreślafunkcjonalność. Nigdy nie ma czegoś takiego jak brak stanu, chociaż stan może być czymś niezmiennym lub upieczonym w architekturze tego, z czym pracujesz. Rozważ różnicę między statycznym serwerem WWW, który po prostu ładuje pliki z systemu plików, a programem, który implementuje kostkę Rubika. Pierwszy z nich zostanie zaimplementowany w zakresie funkcji zaprojektowanych do przekształcenia żądania w żądanie ścieżki do pliku w odpowiedź z zawartości tego pliku. Praktycznie żaden stan nie jest potrzebny poza drobną konfiguracją („stan” systemu plików jest tak naprawdę poza zakresem programu. Program działa w ten sam sposób, niezależnie od stanu plików). W tym ostatnim trzeba jednak modelować kostkę i implementację programu, w jaki sposób operacje na tej kostce zmieniają jej stan.

Jherico
źródło
Kiedy byłem bardziej antyfunkcyjny, zastanawiałem się, jak to może być dobre, gdy coś takiego jak dysk twardy jest zmienny. Wszystkie moje klasy c # miały zmienny stan i mogły bardzo logicznie symulować dysk twardy lub dowolne inne urządzenie. Podczas gdy funkcjonalność była niezgodna między modelami a rzeczywistymi maszynami, które modelowali. Po tym, jak zagłębiłem się w funkcjonalność, zdałem sobie sprawę, że korzyści, które możesz uzyskać, mogą znacznie przewyższyć ten problem. A gdyby fizycznie było możliwe wynalezienie dysku twardego, który sam się utworzyłby, byłby rzeczywiście użyteczny (tak jak robi to już dziennikowanie).
LegendLength
5

Oprócz wspaniałych odpowiedzi udzielanych przez innych, pomyśl o klasach Integeri StringJavie. Instancje tych klas są niezmienne, ale to nie czyni ich bezużytecznymi tylko dlatego, że ich instancji nie można zmienić. Niezmienność daje pewne bezpieczeństwo. Wiesz, że jeśli użyjesz instancji String lub Integer jako klucza do a Map, klucza nie można zmienić. Porównaj to z Dateklasą w Javie:

Date date = new Date();
mymap.put(date, date.toString());
// Some time later:
date.setTime(new Date().getTime());

Po cichu zmieniłeś klucz na swojej mapie! Praca z niezmiennymi obiektami, takimi jak Programowanie Funkcjonalne, jest o wiele czystsza. Łatwiej jest zrozumieć, jakie skutki uboczne występują - żaden! Oznacza to, że jest to łatwiejsze dla programisty, a także dla optymalizatora.

Eddie
źródło
2
Rozumiem to, ale to nie odpowiada na moje pytanie. Pamiętając, że program komputerowy jest modelem jakiegoś rzeczywistego zdarzenia lub procesu, jeśli nie możesz zmienić swoich wartości, to jak możesz modelować coś, co się zmienia?
Mason Wheeler,
Cóż, z pewnością możesz robić użyteczne rzeczy za pomocą klas Integer i String. To nie tak, że ich niezmienność oznacza, że ​​nie można mieć stanu zmiennego.
Eddie,
@Mason Wheeler - Zrozumienie, że rzecz i jej stan to dwie różne „rzeczy”. To, czym jest Pacman, nie zmienia się od czasu A do czasu B. Gdzie Pacman się zmienia. Przechodząc od czasu A do czasu B, otrzymujesz nową kombinację stanu Pacman + ... który jest tym samym Pacman, innym stanem. Stan niezmieniony ... inny stan.
RHSeeger
4

W przypadku wysoce interaktywnych aplikacji, takich jak gry, Functional Reactive Programming jest twoim przyjacielem: jeśli możesz sformułować właściwości świata gry jako zmienne w czasie wartości (i / lub strumienie zdarzeń), jesteś gotowy! Te formuły będą czasem nawet bardziej naturalne i odsłaniające intencje niż mutowanie stanu, np. W przypadku poruszającej się kuli można bezpośrednio użyć znanego prawa x = v * t . Co więcej, tak napisane reguły gry komponują się lepiej niż abstrakcje obiektowe. Na przykład w tym przypadku prędkość piłki może być wartością zmienną w czasie, która zależy od strumienia zdarzeń składającego się z zderzeń piłki. Aby uzyskać więcej konkretnych rozważań dotyczących projektowania, zobacz Tworzenie gier w wiązach .

thSoft
źródło
4

Przy użyciu kreatywności i dopasowania wzorców powstały bezpaństwowe gry:

oraz toczące się dema:

i wizualizacje:

Paul Sweatte
źródło
3

W ten sposób FORTRAN działałby bez WSPÓLNYCH bloków: pisałbyś metody, które miały przekazane wartości i zmienne lokalne. Otóż ​​to.

Programowanie obiektowe zbliżyło nas do stanu i zachowania, ale był to nowy pomysł, kiedy po raz pierwszy zetknąłem się z nim z C ++ w 1994 roku.

Rany, byłem inżynierem funkcjonalnym, kiedy byłem inżynierem mechanikiem i nie wiedziałem o tym!

duffymo
źródło
2
Nie zgadzam się z tym, że można to przypisać OO. Języki przed OO zachęcały do ​​stanu sprzężenia i algorytmów. OO właśnie zapewniło lepszy sposób zarządzania tym.
Jason Baker,
„Zachęcony” - być może. OO sprawiają, że jest to wyraźna część języka. Możesz robić enkapsulację i ukrywanie informacji w C, ale powiedziałbym, że języki OO znacznie to ułatwiają.
duffymo
2

Pamiętaj: języki funkcjonalne są kompletne w Turingu. Dlatego każde przydatne zadanie, które można wykonać w języku imperatywnym, można wykonać w języku funkcjonalnym. Pod koniec dnia myślę jednak, że można powiedzieć o podejściu hybrydowym. Języki takie jak F # i Clojure (i jestem pewien, że inne) zachęcają do bezpaństwowego projektowania, ale pozwalają na zmienność w razie potrzeby.

Jason Baker
źródło
To, że dwa języki są kompletne, nie oznacza, że ​​mogą wykonywać te same zadania. Oznacza to, że mogą wykonywać te same obliczenia. Brainfuck jest ukończony, ale jestem całkiem pewien, że nie może komunikować się przez stos TCP.
RHSeeger
2
Jasne, że może. Biorąc pod uwagę taki sam dostęp do sprzętu jak powiedzmy C, może. To nie znaczy, że byłoby to praktyczne, ale istnieje możliwość.
Jason Baker
2

Nie możesz mieć czysto funkcjonalnego języka, który byłby użyteczny. Zawsze będzie poziom zmienności, z którym będziesz musiał sobie poradzić, IO jest jednym z przykładów.

Pomyśl o językach funkcjonalnych jako o innym używanym narzędziu. Jest dobry dla niektórych rzeczy, ale nie dla innych. Podany przykład gry może nie być najlepszym sposobem na użycie funkcjonalnego języka, przynajmniej ekran będzie miał zmienny stan, z którym nie można nic zrobić z FP. Sposób, w jaki myślisz o problemie i rodzaj problemów, które rozwiązujesz za pomocą FP, będzie inny niż te, do których przywykłeś w programowaniu imperatywnym.

W górę.
źródło
1

Używając wielu rekurencji.

Kółko i krzyżyk w F # (język funkcjonalny.)

Spencer Ruport
źródło
Oczywiście rekurencję ogona można zaimplementować bardzo skutecznie, ponieważ kompilatory mogą przekształcić ją w pętlę.
Eddie,
-3

To jest bardzo proste. Możesz użyć tyle zmiennych, ile chcesz w programowaniu funkcjonalnym ... ale tylko wtedy, gdy są to zmienne lokalne (zawarte w funkcjach). Więc po prostu zawiń swój kod w funkcjach, przekaż wartości między tymi funkcjami (jako przekazane parametry i zwrócone wartości) ... i to wszystko!

Oto przykład:

function ReadDataFromKeyboard() {
    $input_values = $_POST[];
    return $input_values;
}
function ProcessInformation($input_values) {
    if ($input_values['a'] > 10)
        return ($input_values['a'] + $input_values['b'] + 3);
    else if ($input_values['a'] > 5)
        return ($input_values['b'] * 3);
    else
        return ($input_values['b'] - $input_values['a'] - 7);
}
function DisplayToPage($data) {
    print "Based your input, the answer is: ";
    print $data;
    print "\n";
}

/* begin: */
DisplayToPage (
    ProcessInformation (
        GetDataFromKeyboard()
    )
);
nieznany z nazwiska
źródło
John, co to za język?