Czy ktoś może wyjaśnić laikiem, czym jest język funkcyjny?

Question

Powiel możliwe:
Functional programming and non-functional programming

Obawiam Wikipedia nie przyniósł mi dalej. Dziękujemy

PS: Ten miniony wątek jest również bardzo dobre, jednak jestem zadowolony spytałem znowu to pytanie jako nowe odpowiedzi były świetne - dzięki

Functional programming and non-functional programming

Answer 1

Najpierw naucz co Turing machine jest (z wikipedia).

Maszyna Turinga to urządzenie, które manipuluje symbolami na pasku taśmy zgodnie z tabelą reguł. Pomimo swojej prostoty, maszyna Turinga może być dostosowana do symulacji logiki dowolnego algorytmu komputerowego i jest szczególnie przydatna w wyjaśnianiu funkcji procesora wewnątrz komputera. To jest około Lamda calculus. (z Wikipedii).

W logice matematycznej i informatyki, Rachunek lambda, także napisany jako X-rachunku, to formalny system studiowania obliczalne rekurencyjnych funkcji, a la teoria obliczalności i zjawisk pokrewnych, takich jak zmienna wiązania i zmiany.

Funkcjonalne języki programowania używają jako podstawowego modelu obliczeń, rachunku lambda, podczas gdy wszystkie inne języki programowania używają maszyny Turinga jako podstawowego modelu obliczeń. (Cóż, technicznie rzecz biorąc, powinienem powiedzieć, że języki programowania funkcjonalnego vr.s imperative programming - języki w innych paradygmatach używają innych modeli, na przykład SQL używa modelu relacyjnego, Prolog używa modelu logicznego, i tak dalej. języki, o których ludzie myślą podczas omawiania języków programowania są albo funkcjonalne, albo konieczne, więc pozostanę przy łatwym ogólności.)

Co mam na myśli przez "podstawowy model obliczeń"? Cóż, wszystkie języki można wymyślić w dwóch warstwach: jednej, pewnym rdzeniowym języku Turinga, a następnie warstwach abstrakcji lub cukru syntaktycznego (w zależności od tego, czy je lubisz, czy nie), które są zdefiniowane w kategoriach podstawy Turinga. kompletny język. Podstawowym językiem imperatywnych języków jest wariant klasycznego modelu obliczeniowego maszyn Turinga, który można nazwać "językiem C". W tym języku pamięć jest zbiorem bajtów, z których można odczytać i zapisywać, i masz jeden lub więcej procesorów, które odczytują pamięć, wykonują proste operacje arytmetyczne, rozgałęzienia na warunkach i tak dalej. Tak rozumiem podstawowy model obliczania tych języków to Maszyna Turinga.

Podstawowym modelem obliczeń dla języków funkcjonalnych jest Lambda Calculus, a to pokazuje się na dwa różne sposoby. Pierwsza, jedna rzecz, którą robi wiele języków funkcjonalnych, to jednoznaczne napisanie swoich specyfikacji w postaci tłumaczenia na rachunek lambda, aby określić zachowanie programu napisanego w języku (jest to znane jako "denotacyjna semantyka").I sekund, prawie wszystkie funkcjonalne języki programowania implementują swoje kompilatory do używania jawnego języka pośredniego typu-lambda-Haskell ma Core, Lisp i Schemat mają ich "desugared" reprezentację (po zastosowaniu wszystkich makr), Ocaml (Objective Categorical Abstract Machine Language) ma to staroświecka reprezentacja pośrednia, i tak dalej.

Więc czym jest ten rachunek lambda, o którym mówiłem? Cóż, podstawową ideą jest to, że aby wykonać dowolne obliczenia, potrzebujesz tylko dwóch rzeczy. Pierwszą rzeczą, której potrzebujesz, jest funkcja abstrakcji - definicja nienazwanego, pojedynczego argumentu, funkcji. Alonzo Church, który jako pierwszy zdefiniował rachunek lambda, użył raczej niejasnej notacji do zdefiniowania funkcji jako grecka litera lambda, po której następuje jednoznakowa nazwa argumentu funkcji, po którym następuje kropka, po której następuje wyrażenie, które było Ciało funkcji. Tak więc funkcja tożsamości, która dała jakąkolwiek wartość, po prostu zwraca tę wartość, wyglądałaby jak "λx.x" zamierzam użyć trochę bardziej czytelnego dla człowieka podejścia - Zamieniam znak λ na słowo " fun ", kropka z" -> ", i pozwól spacji i zezwól na nazwy wieloznakowe. Mogę więc napisać funkcję tożsamości jako "fun x -> x", lub nawet "fun what -> cokolwiek". Zmiana zapisu nie zmienia podstawowej natury. Zauważ, że jest to źródło nazwy "wyrażenie lambda" w językach takich jak Haskell i wyrażenia Lisp, które wprowadzają nienazwane lokalne funkcje.

Jedyną rzeczą, którą możesz zrobić w rachunku Lambda, to wywoływanie funkcji. Wywołujesz funkcję, stosując argument do niej. Podążę za standardową konwencją, że aplikacja to tylko dwie nazwy z rzędu - więc f x stosuje wartość x do funkcji o nazwie f. Możemy zastąpić f innym wyrażeniem, w tym wyrażeniem Lambda, jeśli chcemy - i możemy. Kiedy zastosujesz argument do wyrażenia, zamienisz aplikację na treść tej funkcji, zastępując wszystkie wystąpienia nazwy argumentu z dowolną wartością. Tak więc wyrażenie (fun x -> x x) y staje się y y.

Teoretycy dokładali wszelkich starań, aby precyzyjnie określić, co rozumieją przez "zastąpienie wszystkich wystąpień zmiennej wartością stosowaną", i mogą bardzo długo zastanawiać się, jak dokładnie to działa (rzucanie takich terminów jak "alfa"). zmieniając nazwę "), ale w końcu wszystko działa dokładnie tak, jak tego oczekujesz. Wyrażenie (fun x -> x x) (x y) staje się (x y) (x y) - nie występuje dezorientacja między argumentem x w funkcji anonimowej i x w zastosowanej wartości. Działa to nawet na wielu poziomach - wyrażenie (fun x -> (fun x -> x x)) (x x)) (x y) staje się najpierw (fun x -> x x) ((x y) (x y)), a następnie ((x y) (x y)) ((x y) (x y)). X w najgłębszej funkcji (“(fun x -> x x)”) jest innym x niż pozostałe x.

Jest całkowicie uzasadnione myślenie o zastosowaniu funkcji jako manipulacji ciągami. Jeśli mam (zabawne x -> jakieś wyrażenie) i stosuję do niego jakąś wartość, to wynik jest po prostu pewnym wyrażeniem, w którym wszystkie x zostały zastąpione tekstowo "pewną wartością" (z wyjątkiem tych, które są zasłonięte przez inny argument).

Na marginesie dodaję nawiasy w razie potrzeby, aby ujednoznacznić elementy, a także usuwam je tam, gdzie nie są potrzebne. Jedyna różnica, jaką tworzą, to grupowanie, nie mają żadnego innego znaczenia.

To wszystko, co jest, również na rachunku Lambda. Nie, naprawdę, to wszystko - tylko abstrakcja anonimowej funkcji i zastosowanie funkcji. Widzę, że masz wątpliwości co do tego, więc pozwól, że omówię niektóre z twoich obaw.

Najpierw określiłem, że funkcja przyjmuje tylko jeden argument - w jaki sposób masz funkcję, która wymaga dwóch lub więcej argumentów? Łatwo - masz funkcję, która przyjmuje jeden argument i zwraca funkcję, która przyjmuje drugi argument.Na przykład, skład funkcji można zdefiniować jako fun f -> (fun g -> (fun x -> f (g x))) - odczytać jako funkcję, która przyjmuje argument f, i zwraca funkcję, która pobiera argument g i zwraca funkcję, która przyjmuje argument x i powrót f (g x).

Więc w jaki sposób reprezentujemy liczby całkowite, używając tylko funkcji i aplikacji? Łatwo (o ile nie jest to oczywiste) - na przykład numer jeden jest funkcją fun s -> fun z -> s z - biorąc pod uwagę funkcję "następczyni" i "zero" z, jeden jest następcą do zera. Two is fun s ->fun z -> s s z, następca następcy do zera, trzy to fun s -> fun z -> s s s z i tak dalej.

Aby dodać dwie liczby, powiedzmy x i y, znowu jest proste, jeśli jest subtelne. Funkcja dodawania to tylko fun x -> fun y -> fun s -> fun z -> x s (y s z). To wygląda dziwnie, więc pozwól mi przeprowadzić Cię przez przykład, aby pokazać, że tak jest, w rzeczy samej - dodajmy cyfry 3 i 2. Teraz trzy to tylko (fun s -> fun z -> s s s z), a dwa to tylko (fun s -> fun z -> s s z), więc otrzymujemy (każdy krok ma zastosowanie jeden argument do jednej funkcji, w przypadkowej kolejności):

(fun x -> fun y -> fun s -> fun z -> x s (y s z)) (fun s -> fun z -> s s s z) (fun s -> fun z -> s s z) 

(fun y -> fun s -> fun z -> (fun s -> fun z -> s s s z) s (y s z)) (fun s -> fun z -> s s z) 

(fun y -> fun s -> fun z -> (fun z -> s s s z) (y s z)) (fun s -> fun z -> s s z) 

(fun y -> fun s -> fun z -> s s s (y s z)) (fun s -> fun z -> s s z) 

(fun s -> fun z -> s s s ((fun s -> fun z -> s s z) s z)) 

(fun s -> fun z -> s s s (fun z -> s s z) z) 

(fun s -> fun z -> s s s s s z) 

I na koniec otrzymamy zaskakujące odpowiedzi na następcę następca następcy następcy następcy do zera, znany bardziej potocznie pięciu . Dodatek działa poprzez zastąpienie zero (lub gdzie zaczynamy liczenie) wartości x z y value- zdefiniowanie mnożenia, my zamiast diddle z pojęciem „następcy”:

(fun x -> fun y -> fun s -> fun z -> x (y s) z) 

Zostawię go aby upewnić się, że powyższy kod robi

Wikipedia says

programy rozkazujący tendencję do podkreślania serię kroków podjętych przez program w przeprowadzeniu akcji, podczas gdy programy funkcjonalne mają tendencję do emphas ize skład i układ funkcji, często bez określania wyraźnych kroków. Prosty przykład ilustruje to dwoma rozwiązaniami dla tego samego celu programowania (obliczanie liczb Fibonacciego). Najważniejszym przykładem jest C++.

// Fibonacci numbers, imperative style 
int fibonacci(int iterations) 
{ 
    int first = 0, second = 1; // seed values 

    for (int i = 0; i < iterations; ++i) { 
     int sum = first + second; 
     first = second; 
     second = sum; 
    } 

    return first; 
} 

std::cout << fibonacci(10) << "\n"; 

wersja funkcjonalna (w Haskell) ma inny klimat do niego:

-- Fibonacci numbers, functional style 

-- describe an infinite list based on the recurrence relation for Fibonacci numbers 
fibRecurrence first second = first : fibRecurrence second (first + second) 

-- describe fibonacci list as fibRecurrence with initial values 0 and 1 
fibonacci = fibRecurrence 0 1 

-- describe action to print the 10th element of the fibonacci list 
main = print (fibonacci !! 10) 

---

See this PDF also

Answer 2

(A) Programowanie funkcyjne opisuje rozwiązania mechanicznie. Użytkownik definiuje maszynę, która jest ciągle wyprowadzana poprawnie, np. z Caml:

let rec factorial = function 
    | 0 -> 1 
    | n -> n * factorial(n - 1);; 

(B) programowanie proceduralne opisuje rozwiązania czasowo. Opisujesz serię kroków, aby przekształcić dane dane wejściowe w odpowiednie dane wyjściowe, np. Java:

int factorial(int n) { 
    int result = 1; 
    while (n > 0) { 
    result *= n--; 
    } 
    return result; 
} 

funkcjonalny język programowania chce zrobić (a) cały czas. Dla mnie największą namacalną wyjątkowością czysto funkcjonalnego programowania jest bezpaństwowość: nigdy nie deklarujesz zmiennych niezależnie od tego, do czego są używane.