jak zarządzać czystym funkcjonalnym językiem programowania bez instrukcji przypisania?

Czytając słynny SICP, stwierdziłem, że autorzy raczej niechętnie przedstawiają oświadczenie o przypisaniu do Schematu w Rozdziale 3. Czytam tekst i rozumiem, dlaczego tak się czują.

Ponieważ Scheme jest pierwszym funkcjonalnym językiem programowania, o którym coś wiem, jestem trochę zaskoczony, że niektóre funkcjonalne języki programowania (nie oczywiście Scheme) mogą obejść się bez zadań.

Użyjmy przykładu z książki bank account. Jeśli nie ma instrukcji przypisania, jak można to zrobić? Jak zmienić balancezmienną? Pytam o to, ponieważ wiem, że istnieje kilka tak zwanych czysto funkcjonalnych języków i zgodnie z pełną teorią Turinga, to też trzeba zrobić.

Nauczyłem się C, Java, Python i często używam zadań w każdym napisanym przeze mnie programie. To naprawdę otwierające oczy doświadczenie. Naprawdę mam nadzieję, że ktoś może krótko wyjaśnić, w jaki sposób unika się zadań w tych funkcjonalnych językach programowania i jaki głęboki wpływ (jeśli w ogóle) ma na te języki.

Powyższy przykład znajduje się tutaj:

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds")))

Zmieniło to balanceBy set!. Dla mnie to bardzo przypomina klasową metodę zmiany członka klasy balance.

Jak powiedziałem, nie znam funkcjonalnych języków programowania, więc jeśli powiedziałem coś złego na ich temat, śmiało to zaznaczam.

Jeśli nie ma instrukcji przypisania, jak to zrobić? Jak zmienić zmienną bilansową?

Nie można zmieniać zmiennych bez pewnego operatora przypisania.

Pytam o to, ponieważ wiem, że istnieje kilka tak zwanych czysto funkcjonalnych języków i zgodnie z pełną teorią Turinga, to też trzeba zrobić.

Nie do końca. Jeśli język jest kompletny, oznacza to, że może obliczyć wszystko, co może obliczyć każdy inny kompletny język Turinga. Nie oznacza to, że musi mieć wszystkie funkcje, które mają inne języki.

Nie jest sprzecznością, że kompletny język programowania Turinga nie ma możliwości zmiany wartości zmiennej, o ile dla każdego programu, który ma zmienne zmienne, możesz napisać równoważny program, który nie ma zmiennych zmiennych (gdzie „równoważny” oznacza że oblicza to samo). W rzeczywistości każdy program można tak napisać.

Jeśli chodzi o twój przykład: w czysto funkcjonalnym języku po prostu nie byłbyś w stanie napisać funkcji, która zwraca inne saldo konta przy każdym wywołaniu. Ale nadal będziesz mógł przepisać każdy program, który korzysta z takiej funkcji, w inny sposób.

Ponieważ poprosiłeś o przykład, rozważmy imperatywny program, który używa twojej funkcji wycofania (w pseudo-kodzie). Ten program pozwala użytkownikowi na wypłatę z konta, wpłatę na konto lub sprawdzenie kwoty pieniędzy na koncie:

account = make-withdraw(0)
ask for input until the user enters "quit"
    if the user entered "withdraw $x"
        account(x)
    if the user entered "deposit $x"
        account(-x)
    if the user entered "query"
        print("The balance of the account is " + account(0))

Oto sposób na napisanie tego samego programu bez użycia zmiennych zmiennych (nie zawracam sobie głowy referencyjnie przezroczystym IO, ponieważ nie chodziło o to):

function IO_loop(balance):
    ask for input
    if the user entered "withdraw $x"
        IO_loop(balance - x)
    if the user entered "deposit $x"
        IO_loop(balance + x)
    if the user entered "query"
        print("The balance of the account is " + balance)
        IO_loop(balance)
    if the user entered "quit"
        do nothing

 IO_loop(0)

Tę samą funkcję można również napisać bez użycia rekurencji, używając zagięcia nad danymi wejściowymi użytkownika (co byłoby bardziej idiomatyczne niż rekurencja jawna), ale nie wiem, czy znasz już fałdy, więc napisałem to w sposób, który nie wykorzystuje niczego, czego jeszcze nie wiesz.

Masz rację, że wygląda bardzo podobnie do metody na obiekcie. To dlatego, że w zasadzie to jest to. lambdaZadaniem jest zamknięcie, które ciągnie zmiennej zewnętrznej balancedo jej zastosowania. Posiadanie wielu zamknięć, które zamykają się na te same zewnętrzne zmienne (zmienne) i wiele metod na tym samym obiekcie, to dwie różne abstrakcje do robienia dokładnie tego samego, i jedno z nich można zaimplementować w kategoriach drugiego, jeśli zrozumiesz oba paradygmaty.

Sposób, w jaki czysto funkcjonalne języki radzą sobie ze stanem, jest oszukiwaniem. Na przykład w Haskell, jeśli chcesz odczytać dane wejściowe z zewnętrznego źródła (co jest oczywiście niedeterministyczne i niekoniecznie da ten sam wynik dwa razy, jeśli go powtórzysz), używa sztuczki monadowej, aby powiedzieć „mamy dostałem inną udawaną zmienną, która reprezentuje stan całej reszty świata , i nie możemy zbadać jej bezpośrednio, ale odczyt danych wejściowych jest czystą funkcją, która przyjmuje stan świata zewnętrznego i zwraca deterministyczne dane wejściowe, które dokładnie ten stan zawsze będzie renderować plus nowy stan świata zewnętrznego. ” (To oczywiście uproszczone wyjaśnienie. Czytanie, jak to naprawdę działa, poważnie złamie ci mózg.)

Lub w przypadku problemu z kontem bankowym, zamiast przypisywać nową wartość do zmiennej, może zwrócić nową wartość jako wynik funkcji, a następnie osoba dzwoniąca musi sobie z tym poradzić w funkcjonalny sposób, na ogół poprzez odtworzenie dowolnych danych która odwołuje się do tej wartości w nowej wersji zawierającej zaktualizowaną wartość. (To nie jest tak nieporęczna operacja, jak mogłoby się wydawać, jeśli dane są skonfigurowane z odpowiednią strukturą drzewa).

„Operatory wielokrotnego przypisania” to jeden przykład funkcji językowej, która ogólnie ma skutki uboczne i jest niezgodna z niektórymi przydatnymi właściwościami języków funkcjonalnych (takimi jak leniwa ocena).

Nie oznacza to jednak, że przypisanie ogólnie jest niezgodne z czystym funkcjonalnym stylem programowania (patrz na przykład niniejsza dyskusja ), ani nie oznacza to, że nie można zbudować składni, która pozwala na działania, które wyglądają jak przypisania w ogóle, są wdrażane bez skutków ubocznych. Tworzenie takiej składni i pisanie w niej wydajnych programów jest jednak czasochłonne i trudne.

W twoim konkretnym przykładzie masz rację - zestaw! operator to zadanie. To nie wolny operator efektem ubocznym, i jest to miejsce, gdzie przerwy Scheme z czysto funkcjonalnego podejścia do programowania.

Ostatecznie, każdy język czysto funkcjonalny będzie musiał zerwać z czysto funkcjonalne podejście kiedyś - zdecydowana większość przydatnych programów zrobić mieć skutki uboczne. Decyzja o tym, gdzie to zrobić, jest zwykle kwestią wygody, a projektanci języków będą starali się dać programistom najwyższą elastyczność w podejmowaniu decyzji, gdzie należy zerwać z czysto funkcjonalnym podejściem, stosownie do ich programu i dziedziny problemów.

W czysto funkcjonalnym języku programowałby obiekt konta bankowego jako funkcję transformatora strumienia. Obiekt jest uważany za funkcję od nieskończonego strumienia żądań od właścicieli kont (lub kogokolwiek) do potencjalnie nieskończonego strumienia odpowiedzi. Funkcja rozpoczyna się od początkowego salda i przetwarza każde żądanie w strumieniu wejściowym, aby obliczyć nowe saldo, które jest następnie przekazywane do wywołania rekurencyjnego w celu przetworzenia pozostałej części strumienia. (Pamiętam, że SICP omawia paradygmat transformatora strumieniowego w innej części książki).

Bardziej rozbudowana wersja tego paradygmatu nazywa się „funkcjonalnym programowaniem reaktywnym” omawianym tutaj na StackOverflow .

Naiwny sposób robienia transformatorów strumieniowych ma pewne problemy. Możliwe jest (w zasadzie dość łatwe) pisanie błędnych programów, które utrzymują wszystkie stare żądania, marnując miejsce. Co ważniejsze, możliwe jest uzależnienie odpowiedzi na bieżące żądanie od przyszłych wniosków. Obecnie trwają prace nad rozwiązaniem tych problemów. Neel Krishnaswami jest siłą stojącą za nimi.

Zastrzeżenie : Nie należę do kościoła czystego programowania funkcjonalnego. W rzeczywistości nie należę do żadnego kościoła :-)

Nie można uczynić programu w 100% funkcjonalnym, jeśli ma on zrobić coś pożytecznego. (Jeśli skutki uboczne nie są potrzebne, cała myśl mogłaby zostać zredukowana do stałego czasu kompilacji). Podobnie jak w przykładzie wycofania możesz uczynić większość procedur funkcjonalnymi, ale w końcu będziesz potrzebować procedur, które mają skutki uboczne (wkład użytkownika, wyjście do konsoli). To powiedziawszy, możesz uczynić większość swojego kodu funkcjonalnym, a ta część będzie łatwa do przetestowania, nawet automatycznie. Następnie tworzysz kod niezbędny do wykonania operacji wejścia / wyjścia / bazy danych / ..., który wymagałby debugowania, ale utrzymanie większości kodu w czystości nie będzie zbyt trudne. Wykorzystam twój przykład wypłaty:

(define +no-founds+ "Insufficient funds")

;; functional withdraw
(define (make-withdraw balance amount)
    (if (>= balance amount)
        (- balance amount)
        +no-founds+))

;; functional atm loop
(define (atm balance thunk)
  (let* ((amount (thunk balance)) 
         (new-balance (make-withdraw balance amount)))
    (if (eqv? new-balance +no-founds+)
        (cons +no-founds+ '())
        (cons (list 'withdraw amount 'balance new-balance) (atm new-balance thunk)))))

;; functional balance-line -> string 
(define (balance->string x)
  (if (eqv? x +no-founds+)
      (string-append +no-founds+ "\n")
      (if (null? x)
          "\n"
          (let ((first-token (car x)))
            (string-append
             (cond ((symbol? first-token) (symbol->string first-token))
                   (else (number->string first-token)))
             " "
             (balance->string (cdr x)))))))

;; functional thunk to test  
(define (input-10 x) 10) ;; define a purly functional input-method

;; since all procedures involved are functional 
;; we expect the same result every time.
;; we use this to test atm and make-withdraw
(apply string-append (map balance->string (atm 100 input-10)))

;; no program can be purly functional in any language.
;; From here on there are imperative dirty procedures!

;; A procedure to get input from user is needed. 
;; Side effects makes it imperative
(define (user-input balance)
  (display "You have $")
  (display balance)
  (display " founds. How much to withdraw? ")
  (read))

;; We need a procedure to print stuff to the console 
;; as well. Side effects makes it imperative
(define (pretty-print-result x)
  (for-each (lambda (x) (display (balance->string x))) x))

;; use imperative procedure with atm.
(pretty-print-result (atm 100 user-input))

Można zrobić to samo w prawie każdym języku i uzyskać te same wyniki (mniej błędów), chociaż może być konieczne ustawienie zmiennych tymczasowych w ramach procedury, a nawet mutowanie elementów, ale to nie ma znaczenia tak długo, jak procedura faktycznie działa funkcjonalnie (same parametry determinują wynik). Wierzę, że staniesz się lepszym programistą w dowolnym języku po tym, jak zaprogramujesz trochę LISP :)

Przypisanie jest niepoprawną operacją, ponieważ dzieli przestrzeń stanu na dwie części, przed przypisaniem i po przypisaniu. Powoduje to trudności ze śledzeniem, jak zmienne są zmieniane podczas wykonywania programu. Następujące rzeczy w językach funkcjonalnych zastępują zadania:

1. Parametry funkcji powiązane bezpośrednio z wartościami zwracanymi
2. wybieranie różnych obiektów do zwrotu zamiast modyfikowania istniejących obiektów.
3. tworzenie nowych leniwych wartości
4. wymieniając wszystkie możliwe obiekty, nie tylko te, które muszą znajdować się w pamięci
5. bez skutków ubocznych