Jak działają funkcjonalne języki programowania?

92

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

Lazer
źródło
możliwy duplikat stackoverflow.com/questions/1916692/ ...
Chris Conway
4
To dobre pytanie, ponieważ na poziomie systemowym komputer potrzebuje stanu, aby był użyteczny. Obejrzałem wywiad z Simonem Peyton-Jonesem (jednym z twórców Haskella), w którym powiedział, że komputer, na którym działało tylko oprogramowanie całkowicie bezpaństwowe, może osiągnąć tylko jedno: stać się gorącym! Wiele dobrych odpowiedzi poniżej. Istnieją dwie główne strategie: 1) Stwórz nieczysty język. 2) Stwórz przebiegły plan abstrakcji, co robi Haskell, zasadniczo tworząc nowy, nieco zmieniony Świat zamiast modyfikować stary.
szkodzi
14
Czy SPJ nie mówił tam o skutkach ubocznych, nie o stanie? Czyste obliczenia mają wiele stanów ukrytych w powiązaniach argumentów i stosie wywołań, ale bez efektów ubocznych (np. I / O) nie mogą zrobić nic użytecznego. Te dwa punkty są naprawdę całkiem różne - jest mnóstwo czystego, stanowego kodu Haskella, a Statemonada jest bardzo elegancka; z drugiej strony IOto brzydki, brudny hack używany tylko niechętnie.
CA McCann
4
Camccann ma rację. W językach funkcjonalnych jest mnóstwo stanów. Jest po prostu wyraźnie zarządzany, a nie „straszna akcja na odległość”, jak w językach imperatywnych.
TYLKO MOJA poprawna OPINIA
1
Może być tu trochę zamieszania. Być może komputery potrzebują efektów, aby były użyteczne, ale myślę, że pytanie dotyczy języków programowania, a nie komputerów.
Conal

Odpowiedzi:

80

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

Antal Spector-Zabusky
źródło
6
To, co zawsze mnie przekonuje o Haskellu (którego dokonałem i odważnie się staram się go nauczyć), to brzydota składni. To tak, jakby wzięli najgorsze fragmenty każdego innego języka, wrzucili do wiadra i wściekle poruszyli. A ci ludzie będą wtedy narzekać na, co prawda (miejscami), dziwną składnię C ++!
19
Neil: Naprawdę? Właściwie uważam składnię Haskella za bardzo czystą. Jestem ciekawy; o czym konkretnie masz na myśli? (Co jest warte, C ++ też mi nie przeszkadza, z wyjątkiem konieczności zrobienia > >w szablonach.)
Antal Spector-Zabusky
6
Na moje oko, chociaż składnia Haskella nie jest tak czysta, jak, powiedzmy, Scheme, nie zaczyna się porównywać do ohydnej składni, no cóż, nawet najładniejszego z języków nawiasów klamrowych, z których C ++ jest jednym z najgorszych . Przypuszczam, że bez względu na smak. Nie sądzę, żeby istniał język, który każdemu odpowiada składniowo.
CA McCann
8
@NeilButterworth: Podejrzewam, że Twoim problemem jest nie tyle składnia, co nazwy funkcji. Gdyby funkcje takie jak >>=lub $miały więcej, zamiast wywoływały bindi apply, kod haskell wyglądałby znacznie mniej jak perl. Chodzi mi o to, że główna różnica między składnią haskell a składnią schematu polega na tym, że haskell ma operatory wrostków i opcjonalne pareny. Gdyby ludzie powstrzymali się od nadużywania operatorów wrostków, haskell wyglądałby podobnie jak schemat z mniejszą liczbą parenów.
sepp2k
5
@camcann: No cóż, ale miałem na myśli: podstawowa składnia schematu to (functionName arg1 arg2). Jeśli usuniesz functionName arg1 arg2pareny, będzie to składnia haskell. Jeśli zezwolisz na operatory wrostkowe o arbitralnie okropnych nazwach, otrzymasz, arg1 §$%&/*°^? arg2co jeszcze bardziej przypomina haskell. (Przy okazji tylko się drażnię, lubię haskell).
sepp2k
23

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

Norman Ramsey
źródło
4
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.
Conal
1
@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 Ramsey
3
Jak rozumiem, artykuł „Awkward Squad” porzuca próbę uogólnienia prostego modelu denotacyjnego IO, tj. World -> (a,World)(Popularnego i trwałego „mitu”, o którym mówiłem), a zamiast tego podaje operacyjne wyjaśnienie. Niektórzy ludzie lubią semantykę operacyjną, ale pozostawiają mnie całkowicie niezadowolonego. Proszę zobaczyć moją dłuższą odpowiedź w innej odpowiedzi.
Conal
+1 To pomogło mi znacznie lepiej zrozumieć monady IO, a także odpowiedzieć na pytanie.
CaptainCasey
Większość kompilatorów Haskell faktycznie definiuje IOjako RealWorld -> (a,RealWorld), ale zamiast reprezentować rzeczywisty świat, jest to tylko abstrakcyjna wartość, która musi zostać przekazana i ostatecznie zostanie zoptymalizowana przez kompilator.
Jeremy List
19

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.

Conal
źródło
Dzięki za dłuższą odpowiedź. Myślę, że może zrobili mi pranie mózgu przez naszych nowych zarządców operacyjnych. Ruchy lewicowe i prawostronne, i tak dalej, umożliwiły udowodnienie kilku użytecznych twierdzeń. Czy widziałeś jakiś model denotacyjny, który ci się podoba, który wyjaśnia niedeterminizm i współbieżność? Nie mam.
Norman Ramsey
1
Podoba mi się, jak World -> PowerSet [World]ostro ujmuje niedeterminizm i współbieżność w stylu przeplotu. Ta definicja domeny mówi mi, że mainstreamowe współbieżne programowanie imperatywne (w tym Haskell) jest nie do opanowania - dosłownie wykładniczo bardziej złożone niż sekwencyjne. Wielka szkoda, jaką widzę w IOmicie Haskella, przesłania tę nieodłączną złożoność, demotywując jej obalenie.
Conal
Chociaż widzę, dlaczego World -> (a, World)jest zepsuty, nie jestem pewien, dlaczego zamiana World -> PowerSet [(a,World)]poprawnie modeluje współbieżność itp. Wydaje mi się to sugerować, że programy IOpowinny działać w czymś w rodzaju monady listy, stosując się do każdego zwróconego elementu zestawu przez IOdziałanie. czego mi brakuje?
Antal Spector-Zabusky
3
@Absz: Po pierwsze, mój sugerowany model World -> PowerSet [(a,World)]się nie zgadza. Spróbujmy World -> PowerSet ([World],a)zamiast tego. PowerSetdaje zbiór możliwych wyników (niedeterminizm). [World]to sekwencje stanów pośrednich (nie monada listy / niedeterminizmu), pozwalające na przeplatanie (planowanie wątków). I ([World],a)nie jest całkiem w porządku, ponieważ umożliwia dostęp aprzed przejściem przez wszystkie stany pośrednie. Zamiast tego zdefiniuj użycie, World -> PowerSet (Computation a)gdziedata Computation a = Result a | Step World (Computation a)
Conal
Nadal nie widzę problemu z World -> (a, World). Jeśli Worldtyp naprawdę obejmuje cały świat, to zawiera również informacje o wszystkich procesach działających jednocześnie, a także „losowe ziarno” wszystkich niedeterminizmu. Rezultatem Worldjest świat z czasem zaawansowany i dokonana pewna interakcja. Jedynym prawdziwym problemem z tym modelem wydaje się być to, że jest on zbyt ogólny, a jego wartościami Worldnie można konstruować i manipulować nimi.
Rotsor
17

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.

PJT
źródło
@tuckster: Wcześniej wiele razy studiowałem rachunek lambda ... i tak, artykuł o AlligatorEggs ma dla mnie sens. Ale nie jestem w stanie odnieść tego do programowania. Dla mnie w tej chwili rachunek labda jest jak oddzielna teoria, która po prostu istnieje. W jaki sposób pojęcia rachunku lambda są używane w językach programowania?
Lazer
3
@eSKay: Haskell to rachunek lambda z cienką warstwą cukru syntaktycznego, aby wyglądał bardziej jak normalny język programowania. Języki z rodziny Lisp są również bardzo podobne do nietypowego rachunku lambda, który reprezentuje Jaj aligatora. Sam rachunek lambda jest zasadniczo minimalistycznym językiem programowania, czymś w rodzaju „asemblera programowania funkcjonalnego”.
CA McCann
@eSKay: Dodałem trochę o tym, jak to się wiąże z kilkoma przykładami. Mam nadzieję, że to pomoże!
PJT
Jeśli zamierzasz odjąć od mojej odpowiedzi, czy mógłbyś zostawić komentarz wyjaśniający dlaczego, abym mógł spróbować poprawić moją odpowiedź. Dziękuję Ci.
PJT
14

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

sigfpe
źródło
8

(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);
}
kennytm
źródło
Albo po prostu computeSumOfSquares min max = sum [x*x | x <- [min..max]];-)
fredoverflow
@Fred: Rozumienie listy to tylko cukier składniowy (a następnie musisz szczegółowo wyjaśnić monadę listy). A jak wdrażasz sum? Rekursja jest nadal potrzebna.
kennytm
3

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 .

Shaun
źródło
9
I pamiętaj, że nie ma nic w tym, Stateani Monadco umożliwia stan, ponieważ oba są zdefiniowane za pomocą prostych, ogólnych, funkcjonalnych narzędzi. Po prostu wychwytują odpowiednie wzorce, więc nie musisz tak bardzo odkrywać koła.
Conal
1

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

sepp2k
źródło
@ sepp2k: dlaczego, jaka jest szkoda w ich zmianie?
Lazer
@eSKay jeśli nie możesz zmienić zmiennych, wiesz, że zawsze są takie same. Ułatwia to debugowanie, zmusza do tworzenia prostszych funkcji wykonujących tylko jedną rzecz i bardzo dobrze. Bardzo pomaga również podczas pracy ze współbieżnością.
Henrik Hansen
9
@eSKay: Programiści funkcjonalni uważają, że stan zmienny stwarza wiele możliwości dla błędów i utrudnia wnioskowanie o zachowaniu programów. Na przykład, jeśli masz wywołanie funkcji f(x)i chcesz zobaczyć, jaka jest wartość x, po prostu musisz przejść do miejsca, w którym zdefiniowano x. Gdyby x było zmienne, musiałbyś również rozważyć, czy jest jakiś punkt, w którym można by zmienić x między jego definicją a jego użyciem (co jest nietrywialne, jeśli x nie jest zmienną lokalną).
sepp2k
6
Nie tylko programiści funkcjonalni nie ufają zmiennym stanom i efektom ubocznym. Niezmienne obiekty i separacja poleceń / zapytań są dobrze postrzegane przez wielu programistów OO i prawie każdy uważa, że ​​zmienne globalne zmienne to zły pomysł. Języki takie jak Haskell idą dalej w myśl, że większość ...
CA McCann
5
@eSKay: Nie chodzi o to, że mutacja jest szkodliwa, tylko o to, że okazuje się, że jeśli zgodzisz się uniknąć mutacji, pisanie kodu, który jest modułowy i wielokrotnego użytku, staje się znacznie łatwiejsze. Bez współdzielonego stanu mutowalnego sprzężenie między różnymi częściami kodu staje się wyraźne i znacznie łatwiej jest zrozumieć i utrzymać projekt. John Hughes wyjaśnia to lepiej niż ja; pobierz jego artykuł Why Functional Programming Matters .
Norman Ramsey