Jak działają funkcjonalne języki programowania?

Jeśli funkcjonalne języki programowania nie mogą zapisać żadnego stanu, w jaki sposób robią proste rzeczy, takie jak czytanie danych wejściowych od użytkownika? W jaki sposób „przechowują” dane wejściowe (lub przechowują jakiekolwiek dane?)

Na przykład: w jaki sposób ta prosta rzecz w C mogłaby przełożyć się na funkcjonalny język programowania, taki jak Haskell?

#include<stdio.h>
int main() {
    int no;
    scanf("%d",&no);
    return 0;
}

(Moje pytanie zostało zainspirowane tym znakomitym postem: „Wykonywanie w królestwie rzeczowników” . Przeczytanie go pozwoliło mi lepiej zrozumieć, czym dokładnie jest programowanie obiektowe, jak Java implementuje je w skrajny sposób i jak funkcjonalne języki programowania są kontrast.)

Jeśli funkcjonalne języki programowania nie mogą zapisać żadnego stanu, w jaki sposób robią proste rzeczy, takie jak odczytywanie danych wejściowych od użytkownika (mam na myśli, jak je „przechowują”) lub przechowywanie jakichkolwiek danych w tym zakresie?

Jak już wiesz, programowanie funkcjonalne nie ma stanu - ale to nie znaczy, że nie może przechowywać danych. Różnica polega na tym, że jeśli napiszę oświadczenie (Haskell) w stylu

let x = func value 3.14 20 "random"
in ...

Mam gwarancję, że wartość xjest zawsze taka sama w ...: nic nie może tego zmienić. Podobnie, jeśli mam funkcję f :: String -> Integer(funkcję pobierającą ciąg znaków i zwracającą liczbę całkowitą), mogę być pewien, że fnie zmodyfikuje ona swojego argumentu, nie zmieni żadnych zmiennych globalnych, nie zapisze danych do pliku i tak dalej. Jak powiedział sepp2k w komentarzu powyżej, ta niezmienność jest naprawdę pomocna w rozumowaniu o programach: piszesz funkcje, które zwijają, zwijają i niszczą twoje dane, zwracając nowe kopie, abyś mógł je połączyć w łańcuch, i możesz być pewien, że żadne z tych wywołań funkcji może zrobić wszystko, co jest „szkodliwe”. Wiesz, że tak xjest zawsze xi nie musisz się martwić, że ktoś napisał x := foo bargdzieś pomiędzy deklaracjąx i jego zastosowanie, bo to niemożliwe.

A co, jeśli chcę odczytać dane wejściowe od użytkownika? Jak powiedział KennyTM, chodzi o to, że nieczysta funkcja jest czystą funkcją, która jako argument przekazuje całemu światu i zwraca zarówno wynik, jak i świat. Oczywiście nie chcesz tego robić: po pierwsze, jest to okropnie niezgrabne, a po drugie, co się stanie, jeśli ponownie wykorzystam ten sam obiekt świata? Więc to jest w jakiś sposób abstrakcyjne. Haskell obsługuje to z typem IO:

main :: IO ()
main = do str <- getLine
          let no = fst . head $ reads str :: Integer
          ...

To mówi nam, że mainjest to akcja IO, która nic nie zwraca; wykonanie tej czynności oznacza uruchomienie programu Haskell. Zasada jest taka, że ​​typy we / wy nigdy nie mogą uciec od akcji we / wy; w tym kontekście wprowadzamy tę akcję za pomocą do. W ten sposób getLinezwraca an IO String, co można sobie wyobrazić na dwa sposoby: po pierwsze, jako działanie, które po uruchomieniu tworzy napis; po drugie, jako ciąg, który jest „skażony” przez IO, ponieważ został otrzymany w sposób nieczysty. Pierwsza jest bardziej poprawna, ale druga może być bardziej pomocna. <-Bierze StringOUT IO Stringi przechowuje je w str-ale skoro jesteśmy w działaniu IO, musimy owinąć go wykonać kopię zapasową, więc to nie może „uciec”. Następny wiersz próbuje odczytać liczbę całkowitą ( reads) i pobiera pierwsze udane dopasowanie (fst . head); to wszystko jest czyste (bez IO), więc nadajemy mu nazwę let no = .... Możemy wtedy użyć obu noi strw .... W ten sposób przechowujemy nieczyste dane (z getLinedo str) i czyste dane ( let no = ...).

Ten mechanizm pracy z IO jest bardzo potężny: pozwala oddzielić czystą, algorytmiczną część programu od nieczystej strony interakcji użytkownika i wymusić to na poziomie typu. Twoja minimumSpanningTreefunkcja prawdopodobnie nie może zmienić czegoś w innym miejscu w kodzie, napisać wiadomości do użytkownika i tak dalej. To jest bezpieczne.

To wszystko, co musisz wiedzieć, aby używać IO w Haskell; jeśli to wszystko, czego chcesz, możesz zatrzymać się tutaj. Ale jeśli chcesz zrozumieć, dlaczego to działa, czytaj dalej. (Pamiętaj, że te rzeczy będą specyficzne dla Haskella - inne języki mogą wybrać inną implementację).

Więc to prawdopodobnie wydawało się trochę oszustwem, w jakiś sposób dodając nieczystości do czystego Haskella. Ale tak nie jest - okazuje się, że możemy zaimplementować typ IO całkowicie w czystym Haskellu (o ile otrzymamy RealWorld). Idea jest taka: akcja IO IO typejest tym samym, co funkcja RealWorld -> (type, RealWorld), która przyjmuje świat rzeczywisty i zwraca zarówno obiekt typu, jak typei zmodyfikowany RealWorld. Następnie definiujemy kilka funkcji, abyśmy mogli używać tego typu bez szaleństwa:

return :: a -> IO a
return a = \rw -> (a,rw)

(>>=) :: IO a -> (a -> IO b) -> IO b
ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw'

Pierwsza z nich pozwala nam mówić o akcjach IO, które nic nie robią: return 3jest to akcja IO, która nie pyta o rzeczywisty świat i po prostu zwraca 3. >>=Operator, wymawiane „bind”, pozwoli nam uruchomić działania IO. Wyodrębnia wartość z akcji IO, przekazuje ją i świat rzeczywisty przez funkcję i zwraca wynikową akcję IO. Zauważ, że >>=wymusza naszą zasadę, że wyniki działań IO nigdy nie mogą uciec.

Możemy następnie przekształcić powyższe mainw następujący zwykły zestaw aplikacji funkcji:

main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ...

Skok środowiska mainuruchomieniowego Haskell zaczyna się od inicjału RealWorldi gotowe! Wszystko jest czyste, ma po prostu fantazyjną składnię.

[ Edycja: Jak wskazuje @Conal , nie jest to właściwie to, czego Haskell używa do wykonania IO. Ten model zepsuje się, jeśli dodasz współbieżność lub rzeczywiście w jakikolwiek sposób, aby świat zmienił się w środku akcji IO, więc Haskell nie mógłby użyć tego modelu. Jest dokładna tylko dla obliczeń sekwencyjnych. Dlatego może się zdarzyć, że IO Haskella jest trochę uniku; nawet jeśli nie jest, z pewnością nie jest aż tak elegancki. Obserwacja Per @ Conal, zobacz, co mówi Simon Peyton-Jones w Tackling the Awkward Squad [pdf] , sekcja 3.1; przedstawia coś, co mogłoby oznaczać alternatywny model wzdłuż tych linii, ale potem porzuca go ze względu na jego złożoność i przyjmuje inną taktykę.]

Ponownie, to wyjaśnia (prawie), jak IO i ogólnie zmienność działają w Haskell; jeśli to wszystko, co chcesz wiedzieć, możesz przestać czytać tutaj. Jeśli potrzebujesz ostatniej dawki teorii, czytaj dalej - ale pamiętaj, że w tym momencie odeszliśmy naprawdę daleko od twojego pytania!

A więc ostatnia rzecz: okazuje się, że ta struktura - typ parametryczny z returni >>=- jest bardzo ogólna; Nazywa się to monadą i dozapisem returni >>=działa z każdym z nich. Jak widziałeś tutaj, monady nie są magiczne; magiczne jest to, że dobloki zamieniają się w wywołania funkcji. RealWorldTyp jest jedynym miejscem widzimy żadnej magii. Typy takie jak [], konstruktor list, są również monadami i nie mają nic wspólnego z nieczystym kodem.

Wiesz już (prawie) wszystko o pojęciu monady (poza kilkoma prawami, które muszą być spełnione i formalną definicją matematyczną), ale brakuje ci intuicji. W Internecie jest absurdalna liczba samouczków monad; Podoba mi się ten , ale masz opcje. Jednak to prawdopodobnie nie pomoże ; jedynym prawdziwym sposobem na uzyskanie intuicji jest połączenie ich używania i przeczytania kilku samouczków we właściwym czasie.

Jednak nie potrzebujesz tej intuicji, aby zrozumieć IO . Zrozumienie monad w całości jest wisienką na torcie, ale możesz już teraz użyć IO. Możesz go użyć po tym, jak pokazałem ci pierwszą mainfunkcję. Możesz nawet traktować kod IO tak, jakby był w nieczystym języku! Pamiętaj jednak, że istnieje podstawowa reprezentacja funkcjonalna: nikt nie oszukuje.

(PS: Przepraszam za długość. Poszedłem trochę daleko.)

Wiele dobrych odpowiedzi, ale są one długie. Spróbuję udzielić pomocnej, krótkiej odpowiedzi:

• Języki funkcyjne umieszczają stan w tych samych miejscach co C: w nazwanych zmiennych oraz w obiektach przydzielonych na stercie. Różnice są takie, że:

  • W języku funkcjonalnym „zmienna” otrzymuje swoją wartość początkową, gdy wchodzi w zakres (poprzez wywołanie funkcji lub wiązanie let) i ta wartość nie zmienia się później . Podobnie, obiekt przydzielony na stercie jest natychmiast inicjowany z wartościami wszystkich jego pól, które nie zmieniają się później.

  • „Zmiany stanu” obsługiwane nie przez mutowanie istniejących zmiennych lub obiektów, ale przez wiązanie nowych zmiennych lub przydzielanie nowych obiektów.

• IO działa podstępem. Obliczenie powodujące efekt uboczny, które generuje ciąg, jest opisywane przez funkcję, która przyjmuje World jako argument i zwraca parę zawierającą ciąg i nowy World. Świat zawiera zawartość wszystkich dysków, historię każdego wysłanego lub odebranego pakietu sieciowego, kolor każdego piksela na ekranie i tym podobne. Kluczem do tej sztuczki jest to, że dostęp do świata jest ściśle ograniczony

  • Żaden program nie może zrobić kopii świata (gdzie byś to umieścił?)

  • Żaden program nie może odrzucić świata

  Dzięki tej sztuczce istnieje jeden, niepowtarzalny Świat, którego stan ewoluuje w czasie. System czasu wykonywania języka, który nie jest napisany w języku funkcjonalnym, implementuje obliczenia o skutkach ubocznych, aktualizując unikalny świat w miejscu zamiast zwracać nowy.

  Ta sztuczka została pięknie wyjaśniona przez Simona Peytona Jonesa i Phila Wadlera w ich przełomowym artykule „Imperative Functional Programming” .

Zrywam komentarz do nowej odpowiedzi, aby dać więcej miejsca:

Napisałem:

O ile mogę powiedzieć, ta IOhistoria ( World -> (a,World)) jest mitem, gdy zastosujemy ją do Haskella, ponieważ ten model wyjaśnia tylko czysto sekwencyjne obliczenia, podczas gdy IOtyp Haskella obejmuje współbieżność. Przez „czysto sekwencyjny” rozumiem, że nawet świat (wszechświat) nie może zmieniać się między początkiem a końcem imperatywnego obliczenia, inaczej niż w wyniku tego obliczenia. Na przykład, gdy komputer się zacina, mózg itp. Nie może. Współbieżność może być obsługiwana przez coś podobnego World -> PowerSet [(a,World)], co pozwala na niedeterminizm i przeplot.

Norman napisał:

@Conal: Myślę, że historia IO ładnie uogólnia się na niedeterminizm i przeplot; jeśli dobrze pamiętam, w artykule „Awkward Squad” jest całkiem dobre wyjaśnienie. Ale nie znam dobrego artykułu, który jasno wyjaśniałby prawdziwy paralelizm.

@Norman: Uogólnia w jakim sensie? Sugeruję, że model denotacyjny / wyjaśnienie zwykle podawane, World -> (a,World)nie pasuje do Haskella, IOponieważ nie uwzględnia niedeterminizmu i współbieżności. Może istnieć bardziej złożony model, który pasuje, na przykład World -> PowerSet [(a,World)], ale nie wiem, czy taki model został opracowany i pokazany jako odpowiedni i spójny. Osobiście wątpię, by można było znaleźć taką bestię, biorąc pod uwagę, że IOjest ona wypełniona tysiącami importowanych przez FFI imperatywnych wywołań API. I jako taka IOspełnia swój cel:

Otwarty problem: IOmonada stała się synonimem Haskella. (Ilekroć czegoś nie rozumiemy, wrzucamy to do monady IO.)

(Z wykładu Simona PJ w POPL, Noszenie koszuli z włosami Noszenie koszuli z włosami: retrospektywa o Haskellu .)

W sekcji 3.1 książki Tackling the Awkward Squad Simon wskazuje na to, co nie działa type IO a = World -> (a, World), w tym „Podejście nie skaluje się dobrze, gdy dodamy współbieżność”. Następnie proponuje możliwy model alternatywny, a następnie rezygnuje z próby wyjaśnień denotacyjnych, mówiąc

Jednak zamiast tego przyjmiemy semantykę operacyjną, opartą na standardowym podejściu do semantyki rachunków procesów.

To niepowodzenie w znalezieniu precyzyjnego i użytecznego modelu denotacyjnego jest przyczyną, dla której postrzegam Haskell IO jako odejście od ducha i głębokie korzyści z tego, co nazywamy „programowaniem funkcjonalnym” lub co Peter Landin bardziej szczegółowo nazwał „programowaniem denotacyjnym” . Zobacz komentarze tutaj.

Programowanie funkcjonalne wywodzi się z rachunku lambda. Jeśli naprawdę chcesz zrozumieć programowanie funkcjonalne, odwiedź http://worrydream.com/AlligatorEggs/

Jest to „zabawny” sposób nauki rachunku lambda i wprowadzający Cię w ekscytujący świat programowania funkcyjnego!

Jak znajomość Lambda Calculus jest pomocna w programowaniu funkcjonalnym.

Zatem Lambda Calculus jest podstawą wielu rzeczywistych języków programowania, takich jak Lisp, Scheme, ML, Haskell, ...

Załóżmy, że chcemy opisać funkcję, która dodaje trzy do dowolnego wejścia, aby to zrobić, napisalibyśmy:

plus3 x = succ(succ(succ x)) 

Przeczytaj „plus3 to funkcja, która zastosowana do dowolnej liczby x daje następcę następcy następcy x”

Zauważ, że funkcja, która dodaje 3 do dowolnej liczby, nie musi mieć nazwy plus3; nazwa „plus3” jest po prostu wygodnym skrótem do nazwania tej funkcji

(plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

Zauważ, że używamy symbolu lambda dla funkcji (myślę, że wygląda trochę jak aligator, zgaduję, że stąd wziął się pomysł na jajka aligatora)

Symbol lambda to Alligator (funkcja), a x to jego kolor. Możesz również myśleć o x jako o argumencie (funkcje Lambda Calculus mają tak naprawdę mieć tylko jeden argument), reszta możesz myśleć o nim jako o treści funkcji.

Rozważmy teraz abstrakcję:

g ≡ λ f. (f (f (succ 0)))

Argument f jest używany w pozycji funkcji (w wywołaniu). Nazywamy funkcję wyższego rzędu ga, ponieważ przyjmuje inną funkcję jako dane wejściowe. Możesz myśleć o innych wywołaniach funkcji f jako „ jajach ”. Biorąc teraz dwie funkcje lub „ aligatory ”, które stworzyliśmy, możemy zrobić coś takiego:

(g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) 
= ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0)))
 = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0)))))
 = (succ (succ (succ (succ (succ (succ (succ 0)))))))

Jeśli zauważysz, zobaczysz, że nasz λ f Alligator zjada nasz λ x Alligator, a następnie λ x Alligator i umiera. Następnie nasz aligator λ x odradza się w jajach aligatora λ f. Następnie proces się powtarza, a aligator λ x po lewej stronie zjada teraz drugi aligator λ x po prawej.

Następnie możesz użyć tego prostego zestawu reguł „ aligatorów ” jedzących „ aligatory ” do zaprojektowania gramatyki i tak narodziły się funkcjonalne języki programowania!

Możesz więc zobaczyć, czy znasz rachunek Lambda, zrozumiesz, jak działają języki funkcjonalne.

Technika obsługi stanu w Haskell jest bardzo prosta. I nie musisz rozumieć monad, żeby sobie z tym poradzić.

W języku programowania ze stanem zazwyczaj gdzieś przechowywana jest pewna wartość, wykonywany jest kod, a następnie jest przechowywana nowa wartość. W językach imperatywnych stan ten znajduje się gdzieś „w tle”. W (czystym) języku funkcjonalnym podajesz to wyraźnie, więc jawnie piszesz funkcję, która przekształca stan.

Więc zamiast mieć stan typu X, piszesz funkcje, które odwzorowują X na X. To wszystko! Przechodzisz od myślenia o stanie do myślenia o tym, jakie operacje chcesz wykonać na stanie. Następnie można łączyć te funkcje w łańcuchy i łączyć je razem na różne sposoby, tworząc całe programy. Oczywiście nie jesteś ograniczony tylko do mapowania X na X. Możesz pisać funkcje, które przyjmują różne kombinacje danych jako dane wejściowe i zwracają różne kombinacje na końcu.

Monady są jednym z wielu narzędzi pomagających w organizacji tego. Ale monady w rzeczywistości nie są rozwiązaniem problemu. Rozwiązaniem jest myślenie o transformacjach stanu zamiast o stanie.

Działa to również z I / O. W efekcie dzieje się tak: zamiast pobierać dane wejściowe od użytkownika z jakimś bezpośrednim odpowiednikiem scanfi gdzieś je przechowywać, zamiast tego piszesz funkcję, aby powiedzieć, co zrobiłbyś z wynikiem scanf, gdybyś go miał, a następnie przekazać to funkcji do I / O API. Dokładnie tak się dzieje >>=, gdy używasz IOmonady w Haskell. Nie musisz więc nigdzie przechowywać wyników operacji we / wy - wystarczy napisać kod, który powie, jak chcesz go przekształcić.

(Niektóre języki funkcyjne dopuszczają nieczyste funkcje).

W przypadku języków czysto funkcjonalnych interakcja w świecie rzeczywistym jest zwykle uwzględniana jako jeden z argumentów funkcji, na przykład:

RealWorld pureScanf(RealWorld world, const char* format, ...);

Różne języki mają różne strategie odciągania świata od programisty. Na przykład Haskell używa monad do ukrycia worldargumentu.

Ale czysta część samego języka funkcjonalnego jest już kompletna w Turingu, co oznacza, że ​​wszystko, co można zrobić w C, jest również wykonalne w Haskell. Główna różnica w stosunku do języka imperatywnego polega na tym, że zamiast modyfikować stany w miejscu:

int compute_sum_of_squares (int min, int max) {
  int result = 0;
  for (int i = min; i < max; ++ i)
     result += i * i;  // modify "result" in place
  return result;
}

Włączasz część modyfikującą do wywołania funkcji, zwykle zamieniając pętle w rekurencje:

int compute_sum_of_squares (int min, int max) {
  if (min >= max)
    return 0;
  else
    return min * min + compute_sum_of_squares(min + 1, max);
}

Język funkcjonalny może uratować stan! Zwykle po prostu zachęcają lub zmuszają cię do wyrażenia tego wprost.

Na przykład sprawdź State Monad Haskella .

może się przydać, programowanie funkcji dla reszty z nas

haskell:

main = do no <- readLn
          print (no + 1)

Możesz oczywiście przypisywać rzeczy do zmiennych w językach funkcjonalnych. Po prostu nie możesz ich zmienić (więc w zasadzie wszystkie zmienne są stałymi w językach funkcyjnych).