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

26

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.

Gnijuohz
źródło
1
Jeśli chodzi o naukę czysto funkcjonalnego języka: niekoniecznie zaleciłbym zrobienie tego od razu. Jeśli nauczysz się Haskell, oprócz nauki pisania programów bez zmiennych, będziesz musiał także dowiedzieć się o lenistwie i sposobie, w jaki Haskell wykonuje IO. To może być trochę dużo naraz. Jeśli chcesz nauczyć się pisać programy bez stanu zmiennego, prawdopodobnie najłatwiejszym sposobem byłoby po prostu napisanie kilku programów schematu bez użycia set!lub innych funkcji, które kończą się na !. Gdy poczujesz się z tym dobrze, przejście na czysty FP powinno być łatwiejsze.
sepp2k

Odpowiedzi:

21

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.

sepp2k
źródło
Rozumiem twój punkt widzenia, ale zobaczmy, że chcę stworzyć program, który również symuluje konto bankowe i może również robić te rzeczy (wypłaty i depozyty), czy jest więc jakiś prosty sposób?
Gnijuohz
@Gnijuohz Zawsze zależy od tego, jaki problem dokładnie próbujesz rozwiązać. Na przykład, jeśli masz saldo początkowe oraz listę wypłat i depozytów i chcesz poznać saldo po tych wypłatach i depozytach, możesz po prostu obliczyć sumę depozytów minus suma wypłat i dodać ją do salda początkowego . Tak byłoby w kodzie newBalance = startingBalance + sum(deposits) - sum(withdrawals).
sepp2k
1
@Gnijuohz Do mojej odpowiedzi dodałem przykładowy program.
sepp2k
Dziękujemy za czas i wysiłek włożony w pisanie i przepisywanie odpowiedzi! :)
Gnijuohz
Dodałbym, że użycie kontynuacji może być również środkiem do osiągnięcia tego w schemacie (o ile można przekazać argument do kontynuacji?)
dader51
11

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).

Mason Wheeler
źródło
Naprawdę jestem zainteresowany naszą odpowiedzią i przykładem Haskella, ale z powodu braku wiedzy na ten temat nie mogę w pełni zrozumieć ostatniej części twojej odpowiedzi (cóż, także drugiej części :()
Gnijuohz
3
@Gnijuohz Ostatni akapit mówi, że zamiast tego b = makeWithdraw(42); b(1); b(2); b(3); print(b(4))możesz po prostu zrobić, b = 42; b1 = withdraw(b1, 1); b2 = withdraw(b1, 2); b3 = withdraw(b2, 3); print(withdraw(b3, 4));gdzie withdrawjest po prostu zdefiniowane jako withdraw(balance, amount) = balance - amount.
sepp2k
3

„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.

Blueberryfields
źródło
„Ostatecznie każdy czysto funkcjonalny język będzie musiał kiedyś zerwać z czysto funkcjonalnym podejściem - ogromna większość przydatnych programów ma skutki uboczne” To prawda, ale mówisz o robieniu IO i tym podobnych. Wiele przydatnych programów można napisać bez zmiennych, które można modyfikować.
sepp2k
1
... a przez „ogromną większość” przydatnych programów masz na myśli „wszystko”, prawda? Trudno mi nawet wyobrazić sobie istnienie jakiegokolwiek programu, który można rozsądnie nazwać „użytecznym”, który nie wykonuje operacji wejścia / wyjścia, co wymaga działań niepożądanych w obu kierunkach.
Mason Wheeler,
@MasonWheeler Programy SQL nie wykonują operacji wejścia / wyjścia jako takich. Często zdarza się, że pisze się kilka funkcji, które nie wykonują operacji we / wy w języku, który ma REPL, a następnie po prostu wywołuje je z REPL. Może to być całkowicie przydatne, jeśli twoja grupa docelowa jest w stanie korzystać z REPL (szczególnie jeśli twoją grupą docelową są ty).
sepp2k
1
@MasonWheeler: tylko jeden, prosty kontrprzykład: koncepcyjne obliczenie n cyfr liczby pi nie wymaga żadnych operacji we / wy. To „tylko” matematyka i zmienne. Jedynym wymaganym wejściem jest n, a zwracana wartość to Pi (do n cyfr).
Joachim Sauer
1
@ Joachim Sauer ostatecznie będziesz chciał wydrukować wynik na ekranie lub w inny sposób zgłosić go użytkownikowi. I początkowo będziesz chciał skądś załadować jakieś stałe do programu. Tak więc, jeśli chcesz być pedantyczny, wszystkie przydatne programy muszą w pewnym momencie wykonać IO, nawet jeśli są to trywialne przypadki, które są ukryte i zawsze ukryte przed programistą przez środowisko
blueberryfields
3

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 :-)

Uday Reddy
źródło
Chyba należysz do jakiejś świątyni? :-P
Gnijuohz
1
Świątynia wolnego myślenia. Nie ma tam kaznodziejów.
Uday Reddy,
2

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 :)

Sylwester
źródło
+1 za obszerny przykład i realistyczne objaśnienia dotyczące części funkcjonalnych i nieczystych części funkcjonalnych programu oraz wskazujące, dlaczego FP ma jednak znaczenie.
Zelphir Kaltstahl
1

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
tp1
źródło
Wydaje się, że nie dotyczy to postawionego pytania. Jak programujesz obiekt konta bankowego w czysto funkcjonalnym języku?
Uday Reddy,
to tylko funkcje przekształcające się z jednego konta bankowego do drugiego. Kluczem jest to, że gdy takie transformacje się zdarzają, nowe obiekty są wybierane zamiast modyfikować istniejące.
tp1
Po przekształceniu jednego rekordu konta bankowego w inny chcesz, aby klient wykonał następną transakcję na nowym rekordzie, a nie na starym. „Punkt kontaktowy” dla klienta musi być stale aktualizowany, aby wskazywał na bieżący rekord. To podstawowa idea „modyfikacji”. „Obiekty” kont bankowych nie są zapisami kont bankowych.
Uday Reddy,