Qualcuno può spiegare, in parole povere, che linguaggio funzionale?

Question

Eventuali duplicati:
Functional programming and non-functional programming

temo Wikipedia non mi ha portato alcun ulteriormente. Molte grazie

PS: Questo thread passato è anche molto buono, ma io sono contento di aver fatto questa domanda ancora una volta come le nuove risposte erano ottime - grazie

Functional programming and non-functional programming

Answer 1

prima imparare ciò che un Turing machine è (da wikipedia).

Una macchina di Turing è un dispositivo che manipola i simboli su una striscia di nastro in base a una tabella di regole. Nonostante la sua semplicità, una macchina di Turing può essere adattata per simulare la logica di qualsiasi algoritmo di computer ed è particolarmente utile per spiegare le funzioni di una CPU all'interno di un computer.

Questo è circa Lamda calculus. (da wikipedia).

In logica matematica e informatica, il lambda calcolo, scritto anche come il λ-calcolo, è un sistema formale per lo studio funzioni calcolabili ricorsive, una teoria della computabilità Los Angeles, e fenomeni correlati quali variabili vincolanti e sostituzione.

I linguaggi di programmazione funzionale utilizzano, come modello fondamentale di calcolo, il calcolo lambda, mentre tutti gli altri linguaggi di programmazione utilizzano la macchina di Turing come modello fondamentale di computazione. (Beh, tecnicamente, dovrei dire linguaggi di programmazione funzionale vr.s imperative programming lingue- poiché le lingue in altri paradigmi usano altri modelli.Ad esempio, SQL usa il modello relazionale, Prolog usa un modello logico e così via. le lingue a cui le persone effettivamente pensano quando discutono i linguaggi di programmazione sono sia funzionali che imperative, quindi mi limiterò a generalità.)

Cosa intendo per "modello di calcolo fondamentale"? Bene, tutte le lingue possono essere pensate in due strati: uno, un nucleo di Turing, una lingua completa, e poi strati di entrambe le astrazioni o zucchero sintattico (a seconda che ti piacciano o meno) che sono definiti in termini di base Turing- linguaggio completo. Il linguaggio di base per le lingue imperative è quindi una variante del classico modello di calcolo della macchina di Turing che si potrebbe chiamare "linguaggio C". In questo linguaggio, la memoria è una matrice di byte che può essere letta e scritta da, e si dispone di una o più CPU che leggono la memoria, eseguono semplici operazioni aritmetiche, derivano da condizioni e così via. Questo è ciò che intendo per il modello fondamentale del calcolo di queste lingue è la Turing Machine.

Il modello fondamentale di calcolo per i linguaggi funzionali è il calcolo Lambda, che si presenta in due modi diversi. Primo, una cosa che molti linguaggi funzionali fanno è scrivere le loro specifiche esplicitamente in termini di una traduzione al calcolo lambda per specificare il comportamento di un programma scritto nel linguaggio (questo è noto come "semantica denotazionale").E seconda, i linguaggi di programmazione quasi tutti funzionali implementano i loro compilatori di utilizzare un linguaggio- intermedio lambda-calcolo-come esplicita Haskell ha Nucleo, Lisp e Scheme hanno la loro rappresentanza “private degli zuccheri” (dopo l'applicazione di tutte le macro), Ocaml (Objective Categorical Abstract Machine Language) ha il rappresentazione intermedia lispish, e così via.

Quindi cos'è questo calcolo lambda di cui sto parlando? Bene, l'idea di base è che, per fare qualsiasi calcolo, hai solo bisogno di due cose. La prima cosa di cui hai bisogno è l'astrazione della funzione, la definizione di una funzione senza nome, a singolo argomento. La chiesa di Alonzo, che per prima definì il calcolo Lambda usò la notazione piuttosto oscura per definire una funzione come la lettera greca lambda, seguita dal nome di un carattere dell'argomento della funzione, seguito da un punto, seguito dall'espressione che era il corpo della funzione. Quindi la funzione di identità, che ha dato un qualsiasi valore, restituisce semplicemente quel valore, sembrerebbe "λx.x" Ho intenzione di usare un approccio leggermente più leggibile dall'uomo - Sostituirò il carattere λ con la parola " divertimento ", il periodo con" -> ", e consentire lo spazio bianco e consentire nomi multi-carattere. Quindi potrei scrivere la funzione di identità come "divertimento x -> x", o anche "divertente qualunque cosa -> qualsiasi cosa". Il cambiamento nella notazione non cambia la natura fondamentale. Nota che questa è la fonte del nome "espressione lambda" in linguaggi come Haskell e Lisp- espressioni che introducono funzioni locali senza nome.

L'unica altra cosa che puoi fare nel calcolo Lambda è chiamare le funzioni. Chiami una funzione applicandoti un argomento. Seguirò la convenzione standard secondo cui l'applicazione è solo i due nomi di seguito, quindi f x sta applicando il valore x alla funzione denominata f. Possiamo sostituire f con qualche altra espressione, inclusa un'espressione Lambda, se vogliamo- e possiamo Quando si applica un argomento a un'espressione, si sostituisce l'applicazione con il corpo della funzione, con tutte le occorrenze del nome dell'argomento sostituito con qualsiasi valore è stato applicato. Quindi l'espressione (fun x -> x x) y diventa y y.

I teorici hanno fatto di tutto per definire con precisione cosa intendono "sostituendo tutte le occorrenze della variabile con il valore applicato", e possono continuare a parlare di quanto esattamente funzioni (buttando in giro termini come "alfa"). rinominare "), ma alla fine le cose funzionano esattamente come te le aspetti. L'espressione (fun x -> x x) (x y) diventa (x y) (x y) - non c'è confusione tra l'argomento x all'interno della funzione anonima e lo x nel valore applicato. Funziona anche su più livelli: l'espressione (fun x -> (fun x -> x x)) (x x)) (x y) diventa la prima (fun x -> x x) ((x y) (x y)) e quindi la ((x y) (x y)) ((x y) (x y)). La x nella funzione più interna (“(fun x -> x x)”) è una x diversa dalle altre x.

È perfettamente valido pensare all'applicazione della funzione come a una manipolazione di stringhe. Se ho un (divertente x -> qualche espressione), e applico un certo valore ad esso, allora il risultato è solo qualche espressione con tutte le x sostituite testualmente con il "qualche valore" (eccetto quelle che sono ombreggiate da un altro argomento).

Come una parte, aggiungerò una parentesi dove necessario per disambiguare le cose, e anche elitarle dove non necessario. L'unica differenza che fanno è raggruppare, non hanno altro significato.

Quindi questo è tutto quello che c'è nel calcolo Lambda. No, davvero, questo è tutto, solo l'astrazione della funzione anonima e l'applicazione della funzione. Posso vedere che ne dubiti, quindi lasciatemi indirizzare alcune delle tue preoccupazioni.

In primo luogo, ho specificato che una funzione ha solo un argomento: come si dispone di una funzione che richiede due o più argomenti? Facile: si dispone di una funzione che accetta un argomento e restituisce una funzione che accetta il secondo argomento.Ad esempio, la composizione delle funzioni potrebbe essere definita come fun f -> (fun g -> (fun x -> f (g x))) - leggi che come funzione che accetta un argomento f, e restituisce una funzione che accetta un argomento g e restituisce una funzione che accetta un argomento x e restituisce f (g x).

Quindi, come rappresentiamo gli interi, utilizzando solo funzioni e applicazioni? Facilmente (se non ovviamente) - il numero uno, ad esempio, è una funzione fun s -> fun z -> s z - data una funzione "successore" e uno "zero" z, uno è quindi il successore a zero. Due è divertente s ->fun z -> s s z, il successore del successore a zero, tre è fun s -> fun z -> s s s z e così via.

Per aggiungere due numeri, ad esempio x e , è di nuovo semplice, se sottile. La funzione di aggiunta è solo fun x -> fun y -> fun s -> fun z -> x s (y s z). Sembra strano, quindi lascia che ti spieghi un esempio per dimostrare che funziona, in effetti funziona- aggiungiamo i numeri 3 e 2. Ora, tre è solo (fun s -> fun z -> s s s z) e due è solo (fun s -> fun z -> s s z), quindi otteniamo (ogni passaggio applicando un argomento di una funzione, in ordine sparso):

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

E alla fine otteniamo la risposta sorprendente del successore del successore del successore successore successore a zero, conosciuto più comunemente come cinque . Inoltre funziona sostituendo la zero (o dove si comincia a contare) del valore x con il y a valore per definire la moltiplicazione, abbiamo invece Diddle con il concetto di “successore”:

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

Lascio a di verificare che il codice di cui sopra fa

Wikipedia says

programmi imperativi tendono a sottolineare la serie di passi compiuti da un programma nella realizzazione di un'azione, mentre i programmi funzionali tendono a emphas izzare la composizione e la disposizione delle funzioni, spesso senza specificare passaggi espliciti. Un semplice esempio illustra questo con due soluzioni allo stesso obiettivo di programmazione (calcolo dei numeri di Fibonacci). L'esempio imperativo è in 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"; 

Una versione funzionale (in Haskell) ha un diverso sentire ad esso:

-- 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) programmazione funzionale descrive soluzioni meccanicamente. Definisci una macchina che viene emessa costantemente correttamente, ad es. con Caml:

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

(B) procedurale programmazione descrive soluzioni temporalmente. Descrivi una serie di passaggi per trasformare un determinato input nell'output corretto, ad es. con Java:

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

Una programmazione funzionale linguaggio vuole che tu faccia (A) per tutto il tempo. Per me, la massima unicità tangibile della programmazione puramente funzionale è statelessness: non si dichiarano mai variabili indipendentemente da ciò per cui sono utilizzate.