Programmazione funzionale, dichiarativa e imperativa

Cosa significano i termini funzionali, dichiarativi e di programmazione imperativa?

Al momento della stesura di questo, le risposte votate in cima a questa pagina sono imprecise e confuse sulla definizione dichiarativa vs imperativa, inclusa la risposta che cita Wikipedia. Alcune risposte stanno confondendo i termini in modi diversi.

Fare riferimento anche alla mia spiegazione del motivo per cui la programmazione del foglio di calcolo è dichiarativa, indipendentemente dal fatto che le formule mutino le celle.

Inoltre, diverse risposte affermano che la programmazione funzionale deve essere un sottoinsieme di dichiarazioni. Su questo punto dipende se differenziamo la “funzione” dalla “procedura”. Consente di gestire prima l’imperativo e il dichiarativo.

Definizione di espressione dichiarativa

L’ unico attributo che può eventualmente differenziare un’espressione dichiarativa da un’espressione imperativa è la trasparenza referenziale (RT) delle sue sottoespressioni. Tutti gli altri attributi sono condivisi tra entrambi i tipi di espressioni o derivati ​​dalla RT.

Un linguaggio dichiarativo al 100% (cioè uno in cui ogni espressione ansible è RT) non consente (tra gli altri requisiti RT) la mutazione dei valori memorizzati, ad esempio HTML e la maggior parte di Haskell.

Definizione dell’espressione RT

RT viene spesso definito come “senza effetti collaterali”. Il termine effetti non ha una definizione precisa, quindi alcune persone non sono d’accordo sul fatto che “nessun effetto collaterale” è lo stesso di RT. RT ha una definizione precisa .

Poiché ogni sottoespressione è concettualmente una chiamata di funzione, RT richiede che l’implementazione di una funzione (cioè l’espressione (s) all’interno della funzione chiamata) non possa accedere allo stato mutabile che è esterno alla funzione (l’accesso allo stato locale mutabile è permesso). In parole povere, la funzione (implementazione) dovrebbe essere pura .

Definizione di pura funzione

Si dice spesso che una funzione pura non abbia “effetti collaterali”. Il termine effetti non ha una definizione precisa, quindi alcune persone non sono d’accordo.

Le funzioni pure hanno i seguenti attributi.

  • l’unica uscita osservabile è il valore di ritorno.
  • l’unica dipendenza di output è l’argomento.
  • gli argomenti sono completamente determinati prima di generare qualsiasi output.

Ricorda che RT si applica alle espressioni (che includono le chiamate alle funzioni) e la purezza si applica alle funzioni (implementazioni di).

Un oscuro esempio di funzioni impure che rendono le espressioni RT è la concorrenza, ma ciò accade perché la purezza viene interrotta nel livello di astrazione dell’interrupt. Non hai davvero bisogno di saperlo. Per creare espressioni RT, chiamate pure funzioni.

Attributi derivati ​​di RT

Qualsiasi altro attributo citato per la programmazione dichiarativa, ad esempio la citazione del 1999 utilizzata da Wikipedia, deriva da RT o è condiviso con la programmazione imperativa. Dimostrando così che la mia definizione precisa è corretta.

Nota, l’immutabilità dei valori esterni è un sottoinsieme dei requisiti per RT.

  • I linguaggi dichiarativi non hanno strutture di controllo in loop, ad esempio for e while , poiché a causa dell’immutabilità , la condizione del ciclo non cambierebbe mai.

  • I linguaggi dichiarativi non esprimono il stream di controllo diverso dall’ordine di una funzione nidificata (ovvero dipendenze logiche), poiché a causa dell’immutabilità , altre scelte di ordine di valutazione non modificano il risultato (vedere di seguito).

  • I linguaggi dichiarativi esprimono “passi” logici (cioè l’ordine di chiamata della funzione RT annidata), ma se ciascuna chiamata di funzione è una semantica di livello superiore (cioè “cosa fare”) non è un requisito della programmazione dichiarativa. La distinzione dall’imperativo è che a causa dell’immutabilità (cioè più in generale RT), questi “passi” non possono dipendere dallo stato mutabile, piuttosto solo dall’ordine relazionale della logica espressa (cioè l’ordine di annidamento delle chiamate di funzione, anche sottoespressioni ).

    Ad esempio, il paragrafo HTML

    non può essere visualizzato fino a quando non sono state valutate le sotto-espressioni (cioè i tag) nel paragrafo. Non esiste uno stato mutabile, solo una dipendenza di ordine dovuta alla relazione logica della gerarchia di tag (annidamento di sottoespressioni, che sono chiamate di funzione analogamente annidate ).

  • Quindi esiste l’attributo derivato dell’immutabilità (più in generale RT), che le espressioni dichiarative esprimono solo le relazioni logiche delle parti costituenti (cioè degli argomenti della funzione di sottoespressione) e non le relazioni di stato mutabili .

Ordine di valutazione

La scelta dell’ordine di valutazione delle sottoespressioni può solo dare un risultato variabile quando una qualsiasi delle chiamate di funzione non è RT (cioè la funzione non è pura), ad esempio si accede ad uno stato mutabile esterno a una funzione all’interno della funzione.

Ad esempio, date alcune espressioni nidificate, ad es. f( g(a, b), h(c, d) ) , la valutazione avida e pigra degli argomenti della funzione darà gli stessi risultati se le funzioni f , g e h sono pure .

Mentre, se le funzioni f , g e h non sono pure, la scelta dell’ordine di valutazione può dare un risultato diverso.

Nota, le espressioni nidificate sono funzioni concettualmente annidate, poiché gli operatori di espressione sono solo chiamate di funzioni mascherate da un prefisso unario, unpostfix unario o una notazione infografica binaria.

Tangenzialmente, se tutti gli identificatori, ad esempio a , b , c , d , sono immutabili ovunque, non è ansible accedere allo stato esterno al programma (cioè I / O) e non vi è alcuna interruzione del livello di astrazione, quindi le funzioni sono sempre pure.

A proposito, Haskell ha una syntax diversa, f (gab) (hcd) .

Dettagli dell’ordine di valutazione

Una funzione è una transizione di stato (non un valore memorizzabile mutabile) dall’input all’output. Per le composizioni RT di chiamate a funzioni pure , l’ordine di esecuzione di queste transizioni di stato è indipendente. La transizione di stato di ogni chiamata di funzione è indipendente dalle altre, a causa della mancanza di effetti collaterali e del principio che una funzione RT può essere sostituita dal suo valore memorizzato nella cache . Per correggere un malinteso popolare , la pura composizione monadica è sempre dichiarativa e RT , nonostante il fatto che la monade di Haskell sia probabilmente impura e quindi imperativa rispetto allo stato del World esterno al programma (ma nel senso del seguente avvertimento, il lato gli effetti sono isolati).

Valutazione stimata significa che gli argomenti delle funzioni vengono valutati prima che la funzione venga chiamata e la valutazione lazy indica che gli argomenti non vengono valutati fino a quando (e se) non vengono acceduti all’interno della funzione.

Definizione : i parametri della funzione sono dichiarati nel sito di definizione della funzione e gli argomenti della funzione vengono forniti nel sito di chiamata della funzione. Conoscere la differenza tra parametro e argomento .

Concettualmente, tutte le espressioni sono (una composizione di) chiamate di funzione, ad es. Le costanti sono funzioni senza input, gli operatori unari sono funzioni con un input, gli operatori binari sono funzioni con due input, i costruttori sono funzioni e persino le istruzioni di controllo (ad es. , while ) può essere modellato con le funzioni. L’ ordine di funzionamento di questi argomenti (non confondersi con l’ordine di chiamata della funzione nidificata) non è dichiarato dalla syntax, ad es. f( g() ) potrebbe valutare avidamente g quindi il risultato di f on g o potrebbe valutare f e solo valutare pigramente g quando il suo risultato è necessario all’interno di f .

L’avvertimento, nessun linguaggio completo di Turing (cioè che consente la ricorsione illimitata) è perfettamente dichiarativo, ad esempio la valutazione pigra introduce la memoria e l’indeterminismo temporale. Ma questi effetti collaterali dovuti alla scelta dell’ordine di valutazione sono limitati al consumo di memoria, al tempo di esecuzione, alla latenza, alla non terminazione e all’isteresi esterna, quindi alla sincronizzazione esterna.

Programmazione funzionale

Poiché la programmazione dichiarativa non può avere cicli, l’unico modo per iterare è la ricorsione funzionale. È in questo senso che la programmazione funzionale è legata alla programmazione dichiarativa.

Ma la programmazione funzionale non è limitata alla programmazione dichiarativa . La composizione funzionale può essere contrastata con la sottotipizzazione , specialmente in relazione al problema dell’espressione , in cui l’estensione può essere ottenuta aggiungendo sottotipi o decomposizione funzionale . L’estensione può essere un mix di entrambe le metodologie.

La programmazione funzionale di solito rende la funzione un object di prima class, il che significa che il tipo di funzione può apparire nella grammatica ovunque sia ansible qualsiasi altro tipo. Il risultato è che le funzioni possono immettere e operare sulle funzioni, fornendo così una separazione delle preoccupazioni enfatizzando la composizione della funzione, ovvero separando le dipendenze tra le sottocomputer di un calcolo deterministico.

Ad esempio, invece di scrivere una funzione separata (e impiegando la ricorsione anziché i cicli se la funzione deve anche essere dichiarativa) per ognuno di un numero infinito di possibili azioni specializzate che potrebbero essere applicate a ciascun elemento di una raccolta, la programmazione funzionale impiega l’iterazione riutilizzabile funzioni, ad es. map , fold , filter . Queste funzioni di iterazione introducono una funzione di azione specializzata di prima class. Queste funzioni di iterazione iterano la raccolta e chiamano la funzione di azione specializzata di input per ciascun elemento. Queste funzioni di azione sono più concise perché non hanno più bisogno di contenere le istruzioni di loop per iterare la collezione.

Tuttavia, nota che se una funzione non è pura, allora è davvero una procedura. Possiamo forse sostenere che la programmazione funzionale che usa le funzioni impure, è in realtà una programmazione procedurale. Quindi, se siamo d’accordo sul fatto che le espressioni dichiarative sono RT, allora possiamo dire che la programmazione procedurale non è una programmazione dichiarativa, e quindi potremmo sostenere che la programmazione funzionale è sempre RT e deve essere un sottoinsieme della programmazione dichiarativa.

Parallelismo

Questa composizione funzionale con funzioni di prima class può esprimere la profondità nel parallelismo separando la funzione indipendente.

Principio di Brent: il calcolo con il lavoro w e la profondità d possono essere implementati in una PRAM del processore p nel tempo O (max (w / p, d)).

Sia la concorrenza che il parallelismo richiedono anche una programmazione dichiarativa , vale a dire immutabilità e RT.

Quindi, da dove viene questa pericolosa supposizione che Parallelismo == Concurrency provenga? È una conseguenza naturale delle lingue con effetti collaterali: quando la tua lingua ha effetti collaterali ovunque, ogni volta che provi a fare più di una cosa alla volta hai essenzialmente un non-determinismo causato dall’interlacciamento degli effetti di ogni operazione . Quindi, nelle lingue con effetti collaterali, l’unico modo per ottenere il parallelismo è la concorrenza; non sorprende quindi che spesso vediamo i due confusi.

Ordine di valutazione FP

Si noti che l’ordine di valutazione influisce anche sulla terminazione e sugli effetti collaterali delle prestazioni della composizione funzionale.

Eager (CBV) e pigro (CBN) sono duelli categorici [ 10 ], perché hanno invertito l’ordine di valutazione, cioè se le funzioni esterne o interne sono rispettivamente valutate per prime. Immagina un albero capovolto, quindi valuta con interesse i suggerimenti dei rami dell’albero delle funzioni sulla gerarchia delle filiali fino al tronco della funzione di livello superiore; mentre, pigro valuta dal tronco fino alle punte del ramo. Eager non ha prodotti congiuntivi (“e”, a / k / a “prodotti” categoriali) e pigro non ha coprodotti disgiuntivi (“o”, a / k / a “somme” categoriali) [ 11 ].

Prestazione

  • desideroso

    Come con la non-terminazione, desideroso è troppo avido con la composizione funzionale congiuntiva, cioè la struttura di controllo composizionale fa il lavoro non necessario che non è fatto con pigro. Ad esempio , impaziente e inutilmente mappa l’intera lista ai booleani, quando è composta da una piega che termina sul primo elemento vero.

    Questo lavoro non necessario è la causa del preteso “fino a” un ulteriore fattore log n nella complessità temporale sequenziale di desiderosi rispetto a pigri, entrambi con funzioni pure. Una soluzione è usare i funtori (ad es. Liste) con costruttori pigri (cioè desiderosi di prodotti pigri opzionali), perché con entusiasmo l’errata correttezza proviene dalla funzione interiore. Questo perché i prodotti sono tipi costruttivi, cioè tipi induttivi con un’algebra iniziale su un punto di fissazione iniziale [ 11 ]

  • Pigro

    Come con la non-terminazione, il pigro è troppo pigro con la composizione funzionale disgiuntiva, cioè la finalità coinduttiva può avvenire più tardi del necessario, risultando in un lavoro non necessario e in un non-determinismo del ritardo che non è il caso di desideroso [ 10 ] [ 11 ] . Esempi di finalità sono le eccezioni di stato, temporizzazione, non-terminazione e runtime. Questi sono effetti collaterali imperativi, ma anche in un puro linguaggio dichiarativo (ad es. Haskell), vi è uno stato nella monade IO imperativa (nota: non tutte le monadi sono imperative!) Implicito nell’allocazione dello spazio, e il tempismo è lo stato relativo all’imperativo mondo reale. Usando il pigro anche con coprodotti desiderosi opzionali, si perde la “pigrizia” nei coprodotti interni, perché con pigro l’errata pigrizia deriva dalla funzione esterna (si veda l’esempio nella sezione Non-terminazione, dove == è una funzione esterna dell’operatore binario). Questo perché i coprodotti sono limitati dalla finalità, cioè i tipi coinduttivi con un’algebra finale su un object finale [ 11 ].

    Pigro provoca l’indeterminazione nella progettazione e nel debug delle funzioni per latenza e spazio, il cui debugging è probabilmente al di là delle capacità della maggior parte dei programmatori, a causa della dissonanza tra la gerarchia delle funzioni dichiarate e l’ordine di valutazione del runtime. Funzioni pure pigre valutate con entusiasmo, potrebbero potenzialmente introdurre una non terminazione mai vista in precedenza in fase di esecuzione. Viceversa, le pure funzioni pure valutate con il pigro, potrebbero potenzialmente introdurre in precedenza indeterminatezza di spazio e latenza inaspettata in fase di esecuzione.

Non-terminazione

In fase di compilazione, a causa del problema di Arresto e ricorsione reciproca in un linguaggio completo di Turing, non è generalmente ansible garantire la cessazione delle funzioni.

  • desideroso

    Con entusiasmo ma non pigro, per la congiunzione di Head “e” Tail , se la Head o la Tail non termina, allora rispettivamente List( Head(), Tail() ).tail == Tail() o List( Head(), Tail() ).head == Head() non è vero perché il lato sinistro no e il lato destro termina.

    Considerando che, con pigro entrambi i lati terminano. Così desideroso è troppo avido con prodotti congiuntivi e non termina (comprese le eccezioni di runtime) nei casi in cui non è necessario.

  • Pigro

    Con pigro ma non desideroso, per la disgiunzione di 1 “o” 2 , se f non termina, quindi List( f ? 1 : 2, 3 ).tail == (f ? List( 1, 3 ) : List( 2, 3 )).tail non è vero perché il lato sinistro termina e il lato destro no.

    Considerando che, con ansioso, nessuna delle due parti termina così il test di uguaglianza non viene mai raggiunto. Così pigro è troppo pigro con coprodotti disgiuntivi, e in quei casi non riesce a terminare (comprese le eccezioni di runtime) dopo aver fatto più lavoro di quanto avrebbe voluto.

[ 10 ] Continuazioni dichiarative e dualità categoriale, Filinski, sezioni 2.5.4 Un confronto tra CBV e CBN e 3.6.1 CBV e CBN nel SCL.

[ 11 ] Continuazioni dichiarative e dualità categoriale, Filinski, sezioni 2.2.1 Prodotti e coprodotti, 2.2.2 Terminale e oggetti iniziali, 2.5.2 CBV con prodotti pigri e 2.5.3 CBN con coprodotti desiderosi.

Non c’è davvero nessuna definizione ambigua e obiettiva per questi. Ecco come li definirei:

Imperativo : l’attenzione si concentra su quali passi il computer dovrebbe intraprendere piuttosto che su ciò che il computer farà (ad esempio C, C ++, Java).

Dichiarativo – L’attenzione si concentra su ciò che il computer dovrebbe fare piuttosto che su come dovrebbe farlo (ad esempio SQL).

Funzionale : un sottoinsieme di linguaggi dichiarativi che si focalizza pesantemente sulla ricorsione

imperativo e dichiarativo descrivono due opposti stili di programmazione. imperativo è il tradizionale approccio “ricetta passo dopo passo” mentre dichiarativo è più “questo è quello che voglio, ora si lavora su come farlo”.

questi due approcci si verificano durante la programmazione, anche con lo stesso linguaggio e lo stesso programma. generalmente l’approccio dichiarativo è considerato preferibile, perché libera il programmatore dal dover specificare tanti dettagli, mentre ha anche meno possibilità di bug (se descrivi il risultato che vuoi, e alcuni processi automatici ben testati possono tornare indietro da quello a definire i passaggi quindi si potrebbe sperare che le cose siano più affidabili di dover specificare ogni passaggio a mano).

d’altra parte, un approccio imperativo ti dà più controllo di basso livello – è l’approccio “micromanager” alla programmazione. e ciò può consentire al programmatore di sfruttare la conoscenza del problema per dare una risposta più efficiente. quindi non è insolito che alcune parti di un programma siano scritte in uno stile più dichiarativo, ma che le parti critiche per la velocità siano più imperative.

come puoi immaginare, il linguaggio che usi per scrivere un programma incide su quanto tu possa essere dichiarativo – un linguaggio che ha una “intelligenza” incorporata per capire cosa fare dato una descrizione del risultato che consentirà una dichiarazione molto più dichiarativa approccio rispetto a quello in cui il programmatore deve prima aggiungere quel tipo di intelligenza con il codice imperativo prima di essere in grado di build uno strato più dichiarativo in cima. quindi, ad esempio, un linguaggio come prolog è considerato molto dichiarativo perché ha, built-in, un processo che cerca risposte.

finora, noterete che non ho menzionato la programmazione funzionale . questo perché è un termine il cui significato non è immediatamente correlato agli altri due. nella sua programmazione più semplice e funzionale significa che usi le funzioni. in particolare, che si utilizza un linguaggio che supporta funzioni come “valori di prima class” – ciò significa che non solo è ansible scrivere funzioni, ma è ansible scrivere funzioni che scrivono funzioni (che scrivono funzioni che …) e passare le funzioni a funzioni. in breve: le funzioni sono flessibili e comuni come le stringhe e i numeri.

potrebbe sembrare strano, quindi, che funzionale, imperativo e dichiarativo sono spesso citati insieme. la ragione di ciò è una conseguenza dell’idea di programmazione funzionale “all’estremo”. una funzione, nel suo senso più puro, è qualcosa dalla matematica – una sorta di “scatola nera” che prende un po ‘di input e dà sempre lo stesso risultato. e questo tipo di comportamento non richiede la memorizzazione di variabili variabili. quindi se si progetta un linguaggio di programmazione il cui scopo è quello di implementare un’idea di programmazione funzionale molto pura e matematicamente influenzata, si finisce per rifiutare, in gran parte, l’idea di valori che possono cambiare (in un certo senso tecnico limitato).

e se lo fai – se limiti il ​​modo in cui le variabili possono cambiare – allora quasi per caso finisci costringendo il programmatore a scrivere programmi che sono più dichiarativi, perché gran parte della programmazione imperativa sta descrivendo come cambiano le variabili, e non puoi più Fai quello! quindi risulta che la programmazione funzionale, in particolare la programmazione in un linguaggio funzionale, tende a dare più codice dichiarativo.

per riassumere, quindi:

  • imperativo e dichiarativo sono due stili di programmazione opposti (gli stessi nomi sono usati per i linguaggi di programmazione che incoraggiano quegli stili)

  • la programmazione funzionale è uno stile di programmazione in cui le funzioni diventano molto importanti e, di conseguenza, i valori di modifica diventano meno importanti. la limitata capacità di specificare cambiamenti nei valori costringe uno stile più dichiarativo.

quindi la “programmazione funzionale” è spesso descritta come “dichiarativa”.

In poche parole:

Un linguaggio imperativo specifica una serie di istruzioni che il computer esegue in sequenza (fai questo, poi fallo).

Una lingua dichiarativa dichiara un insieme di regole su quali output dovrebbero derivare da quali input (ad esempio se si ha A, allora il risultato è B). Un motore applicherà queste regole agli input e darà un risultato.

Un linguaggio funzionale dichiara un insieme di funzioni matematiche / logiche che definiscono come l’input viene tradotto in output. per esempio. f (y) = y * y. è un tipo di linguaggio dichiarativo.

Imperativo: come raggiungere il nostro objective

  Take the next customer from a list. If the customer lives in Spain, show their details. If there are more customers in the list, go to the beginning 

Dichiarativo: cosa vogliamo ottenere

  Show customer details of every customer living in Spain 

Programmazione imperativa significa qualsiasi stile di programmazione in cui il programma è strutturato fuori dalle istruzioni che descrivono come le operazioni eseguite da un computer avverranno .

Programmazione dichiarativa significa qualsiasi stile di programmazione in cui il tuo programma è una descrizione del problema o della soluzione, ma non indica esplicitamente come verrà svolto il lavoro .

La programmazione funzionale è la programmazione valutando funzioni e funzioni di funzioni … Come programmazione (strettamente definita) funzionale si intende la programmazione definendo funzioni matematiche libere con effetti collaterali, quindi è una forma di programmazione dichiarativa ma non è l’unico tipo di programmazione dichiarativa .

La programmazione logica (ad esempio in Prolog) è un’altra forma di programmazione dichiarativa. Implica l’elaborazione decidendo se un’istruzione logica è vera (o se può essere soddisfatta). Il programma è in genere una serie di fatti e regole, vale a dire una descrizione piuttosto che una serie di istruzioni.

Il termine Riscrittura (ad esempio CASL) è un’altra forma di programmazione dichiarativa. Implica la trasformazione simbolica di termini algebrici. È completamente distinto dalla programmazione logica e dalla programmazione funzionale.

imperativo – le espressioni descrivono la sequenza di azioni da eseguire (associative)

dichiarativo – le espressioni sono dichiarazioni che contribuiscono al comportamento del programma (associativo, commutativo, idempotente, monotono)

funzionale – le espressioni hanno valore solo come effetto; la semantica supporta il ragionamento equo

Da quando ho scritto la mia risposta precedente, ho formulato una nuova definizione della proprietà dichiarativa che è riportata di seguito. Ho anche definito la programmazione imperativa come la doppia proprietà.

Questa definizione è superiore a quella che ho fornito nella mia risposta precedente, perché è succinta ed è più generale. Ma può essere più difficile da ingannare, perché l’implicazione dei teoremi di incompletezza applicabili alla programmazione e alla vita in generale è difficile per gli umani per avvolgere la loro mente.

La spiegazione citata della definizione discute il ruolo svolto dalla pura programmazione funzionale nella programmazione dichiarativa.

Tutti i tipi esotici di programmazione si inseriscono nella seguente tassonomia dichiarativa rispetto all’imperativo, poiché la seguente definizione afferma che sono duali.

Dichiarativo vs. Imperativo

La proprietà dichiarativa è strana, ottusa e difficile da catturare in una definizione tecnicamente precisa che rimane generale e non ambigua, perché è una nozione ingenua che possiamo dichiarare il significato (alias semantica) del programma senza incorrere in effetti collaterali indesiderati. Esiste una tensione intrinseca tra espressione di significato ed evitamento di effetti non intenzionali, e questa tensione deriva in realtà dai teoremi di incompletezza della programmazione e del nostro universo.

È una semplificazione eccessiva, tecnicamente imprecisa e spesso ambigua definire il dichiarativo come cosa fare e imperativo come come fare . Un caso ambiguo è il ” cosa ” è il ” come ” in un programma che emette un programma – un compilatore.

Evidentemente la ricorsione illimitata che completa un linguaggio di Turing , è analogamente anche nella semantica – non solo nella struttura sintattica della valutazione (anche nota come semantica operazionale). Questo è logicamente un esempio analogo al teorema di Gödel: ” qualsiasi sistema completo di assiomi è anche incoerente “. Ponderare la stranezza contraddittoria di quella citazione! È anche un esempio che dimostra come l’espressione della semantica non abbia un limite dimostrabile, quindi non possiamo dimostrare 2 che un programma (e analogamente la sua semantica) si fermi alias il teorema di Halting.

I teoremi di incompletezza derivano dalla natura fondamentale del nostro universo, che come affermato nella Seconda Legge della Termodynamic è ” l’entropia (alias il # delle possibilità indipendenti) tende al massimo per sempre “. La codifica e il design di un programma non sono mai finiti – è vivo! – perché cercano di rispondere a un’esigenza del mondo reale, e la semantica del mondo reale cambia continuamente e tende a maggiori possibilità. Gli umani non smettono mai di scoprire cose nuove (inclusi errori nei programmi ;-).

Per catturare precisamente e tecnicamente questa sopramenzionata nozione desiderata all’interno di questo strano universo che non ha confini (pensate che! Non ci sia “fuori” del nostro universo), richiede una definizione concisa ma ingannevolmente-non semplice che suonerà in modo errato finché non sarà spiegata profondamente.

Definizione:


La proprietà dichiarativa è dove può esistere solo una serie ansible di affermazioni in grado di esprimere ogni specifica semantica modulare.

La proprietà imperativa 3 è il duale, dove la semantica è inconsistente sotto la composizione e / o può essere espressa con variazioni di serie di affermazioni.


Questa definizione di dichiarativo è tipicamente locale in ambito semantico, il che significa che richiede che una semantica modulare mantenga il suo significato coerente indipendentemente da dove e come sia istanziata e impiegata in ambito globale . Quindi ogni semantica dichiarativa modulare dovrebbe essere intrinsecamente ortogonale a tutti i possibili altri – e non un algoritmo globale (o ai teoremi di incompletezza) o modello per la consistenza della testimonianza, che è anche il punto di ” Non è sempre meglio ” di Robert Harper, Professore di Computer Science alla Carnegie Mellon University, uno dei designer di Standard ML.

Esempi di queste semantiche dichiarative modulari includono funzioni di teoria delle categorie, ad esempio Applicative , tipizzazione nominale, spazi dei nomi, campi con nome e wrt a livello operativo di semantica, quindi pura programmazione funzionale.

Così linguaggi dichiarativi ben progettati possono esprimere più chiaramente il significato , anche se con qualche perdita di generalità in ciò che può essere express, eppure un guadagno in ciò che può essere express con coerenza intrinseca.

Un esempio della definizione di cui sopra è l’insieme di formule nelle celle di un programma di foglio di calcolo, che non dovrebbero dare lo stesso significato quando vengono spostate su diverse colonne e celle di riga, cioè gli identificatori di cella modificati. Gli identificatori di cella sono parte e non superflui del significato previsto. Quindi, ogni risultato del foglio di calcolo è unico rispetto agli identificatori di cella in un insieme di formule. La semantica modulare coerente in questo caso è l’uso di identificatori di cella come input e output di funzioni pure per le formule di celle (vedi sotto).

Hypertext Markup Language aka HTML, il linguaggio per pagine web statiche, è un esempio di un linguaggio dichiarativo altamente (ma non perfettamente 3 ) che (almeno prima di HTML 5) non aveva la capacità di esprimere un comportamento dinamico. HTML è forse la lingua più facile da imparare. Per un comportamento dinamico, un linguaggio di scripting imperativo come JavaScript veniva solitamente combinato con HTML. L’HTML senza JavaScript si adatta alla definizione dichiarativa perché ogni tipo nominale (cioè i tag) mantiene il suo significato coerente sotto la composizione all’interno delle regole della syntax.

A competing definition for declarative is the commutative and idempotent properties of the semantic statements, ie that statements can be reordered and duplicated without changing the meaning. For example, statements assigning values to named fields can be reordered and duplicated without changed the meaning of the program, if those names are modular wrt to any implied order. Names sometimes imply an order, eg cell identifiers include their column and row position— moving a total on spreadsheet changes its meaning. Otherwise, these properties implicitly require global consistency of semantics. It is generally impossible to design the semantics of statements so they remain consistent if randomly ordered or duplicated, because order and duplication are intrinsic to semantics. For example, the statements “Foo exists” (or construction) and “Foo does not exist” (and destruction). If one considers random inconsistency endemical of the intended semantics, then one accepts this definition as general enough for the declarative property. In essence this definition is vacuous as a generalized definition because it attempts to make consistency orthogonal to semantics, ie to defy the fact that the universe of semantics is dynamically unbounded and can’t be captured in a global coherence paradigm.

Requiring the commutative and idempotent properties for the (structural evaluation order of the) lower-level operational semantics converts operational semantics to a declarative localized modular semantic, eg pure functional programming (including recursion instead of imperative loops). Then the operational order of the implementation details do not impact (ie spread globally into) the consistency of the higher-level semantics. For example, the order of evaluation of (and theoretically also the duplication of) the spreadsheet formulas doesn’t matter because the outputs are not copied to the inputs until after all outputs have been computed, ie analogous to pure functions.

C, Java, C++, C#, PHP, and JavaScript aren’t particularly declarative. Copute’s syntax and Python’s syntax are more declaratively coupled to intended results , ie consistent syntactical semantics that eliminate the extraneous so one can readily comprehend code after they’ve forgotten it. Copute and Haskell enforce determinism of the operational semantics and encourage “ don’t repeat yourself ” (DRY), because they only allow the pure functional paradigm.


2 Even where we can prove the semantics of a program, eg with the language Coq, this is limited to the semantics that are expressed in the typing , and typing can never capture all of the semantics of a program— not even for languages that are not Turing complete, eg with HTML+CSS it is possible to express inconsistent combinations which thus have undefined semantics.

3 Many explanations incorrectly claim that only imperative programming has syntactically ordered statements. I clarified this confusion between imperative and functional programming . For example, the order of HTML statements does not reduce the consistency of their meaning.


Edit: I posted the following comment to Robert Harper’s blog:

in functional programming … the range of variation of a variable is a type

Depending on how one distinguishes functional from imperative programming, your ‘assignable’ in an imperative program also may have a type placing a bound on its variability.

The only non-muddled definition I currently appreciate for functional programming is a) functions as first-class objects and types, b) preference for recursion over loops, and/or c) pure functions— ie those functions which do not impact the desired semantics of the program when memoized ( thus perfectly pure functional programming doesn’t exist in a general purpose denotational semantics due to impacts of operational semantics, eg memory allocation ).

The idempotent property of a pure function means the function call on its variables can be substituted by its value, which is not generally the case for the arguments of an imperative procedure. Pure functions seem to be declarative wrt to the uncomposed state transitions between the input and result types.

But the composition of pure functions does not maintain any such consistency, because it is possible to model a side-effect (global state) imperative process in a pure functional programming language, eg Haskell’s IOMonad and moreover it is entirely impossible to prevent doing such in any Turing complete pure functional programming language.

As I wrote in 2012 which seems to the similar consensus of comments in your recent blog , that declarative programming is an attempt to capture the notion that the intended semantics are never opaque. Examples of opaque semantics are dependence on order, dependence on erasure of higher-level semantics at the operational semantics layer (eg casts are not conversions and reified generics limit higher-level semantics ), and dependence on variable values which can not be checked (proved correct) by the programming language.

Thus I have concluded that only non-Turing complete languages can be declarative.

Thus one unambiguous and distinct attribute of a declarative language could be that its output can be proven to obey some enumerable set of generative rules. For example, for any specific HTML program (ignoring differences in the ways interpreters diverge) that is not scripted (ie is not Turing complete) then its output variability can be enumerable. Or more succinctly an HTML program is a pure function of its variability. Ditto a spreadsheet program is a pure function of its input variables.

So it seems to me that declarative languages are the antithesis of unbounded recursion , ie per Gödel’s second incompleteness theorem self-referential theorems can’t be proven.

Lesie Lamport wrote a fairytale about how Euclid might have worked around Gödel’s incompleteness theorems applied to math proofs in the programming language context by to congruence between types and logic (Curry-Howard correspondence, etc).

Imperative programming: telling the “machine” how to do something, and as a result what you want to happen will happen.

Declarative programming: telling the “machine” what you would like to happen, and letting the computer figure out how to do it.

Example of imperative

 function makeWidget(options) { const element = document.createElement('div'); element.style.backgroundColor = options.bgColor; element.style.width = options.width; element.style.height = options.height; element.textContent = options.txt; return element; } 

Example of declarative

 function makeWidget(type, txt) { return new Element(type, txt); } 

Note: The difference is not one of brevity or complexity or abstraction. As stated, the difference is how vs what .

Nowadays, new focus: we need the old classifications?

The Imperative/Declarative/Functional aspects was good in the past to classify generic languages, but in nowadays all “big language” (as Java, Python, Javascript, etc.) have some option (typically frameworks ) to express with “other focus” than its main one (usual imperative), and to express parallel processes, declarative functions, lambdas, etc.

So a good variant of this question is “What aspect is good to classify frameworks today?” … An important aspect is something that we can labeling “programming style”

Focus on the fusion of data with algorithm

A good example to explain. As you can read about jQuery at Wikipedia ,

The set of jQuery core features — DOM element selections, traversal and manipulation —, enabled by its selector engine (…), created a new “programming style”, fusing algorithms and DOM-data-structures

So jQuery is the best (popular) example of focusing on a “new programming style” , that is not only object orientation, is ” Fusing algorithms and data-structures “. jQuery is somewhat reactive as spreadsheets, but not “cell-oriented”, is ” DOM-node oriented “… Comparing the main styles in this context:

  1. No fusion : in all “big languages”, in any Functional/Declarative/Imperative expression, the usual is “no fusion” of data and algorithm, except by some object-orientation, that is a fusion in strict algebric structure point of view.

  2. Some fusion : all classic strategies of fusion, in nowadays have some framework using it as paradigm… dataflow , Event-driven programming (or old domain specific languages as awk and XSLT )… Like programming with modern spreadsheets, they are also examples of reactive programming style.

  3. Big fusion : is “the jQuery style”… jQuery is a domain specific language focusing on ” fusing algorithms and DOM-data-structures “.
    PS: other “query languages”, as XQuery, SQL (with PL as imperative expression option) are also data-algorith-fusion examples, but they are islands , with no fusion with other system modules… Spring , when using find() -variants and Specification clauses, is another good fusion example.

Declarative programming is programming by expressing some timeless logic between the input and the output, for instance, in pseudocode, the following example would be declarative:

 def factorial(n): if n < 2: return 1 else: return factorial(n-1) output = factorial(argvec[0]) 

We just define a relationship called the 'factorial' here, and defined the relationship between the output and the input as the that relationship. As should be evident here, about any structured language allows declarative programming to some extend. A central idea of declarative programming is immutable data, if you assign to a variable, you only do so once, and then never again. Other, stricter definitions entail that there may be no side-effects at all, these languages are some times called 'purely declarative'.

The same result in an imperative style would be:

 a = 1 b = argvec[0] while(b < 2): a * b-- output = a 

In this example, we expressed no timeless static logical relationship between the input and the output, we changed memory addresses manually until one of them held the desired result. It should be evident that all languages allow declarative semantics to some extend, but not all allow imperative, some 'purely' declarative languages permit side effects and mutation altogether.

Declarative languages are often said to specify 'what must be done', as opposed to 'how to do it', I think that is a misnomer, declarative programs still specify how one must get from input to output, but in another way, the relationship you specify must be effectively computable (important term, look it up if you don't know it). Another approach is nondeterministic programming, that really just specifies what conditions a result much meet, before your implementation just goes to exhaust all paths on trial and error until it succeeds.

Purely declarative languages include Haskell and Pure Prolog. A sliding scale from one and to the other would be: Pure Prolog, Haskell, OCaml, Scheme/Lisp, Python, Javascript, C--, Perl, PHP, C++, Pascall, C, Fortran, Assembly

Some good answers here regarding the noted “types”.

I submit some additional, more “exotic” concepts often associated with the functional programming crowd:

  • Domain Specific Language or DSL Programming: creating a new language to deal with the problem at hand.
  • Meta-Programming : when your program writes other programs.
  • Evolutionary Programming : where you build a system that continually improves itself or generates successively better generations of sub-programs.

I think that your taxonomy is incorrect. There are two opposite types imperative and declarative. Functional is just a subtype of declarative. BTW, wikipedia states the same fact.

In a nutshell, the more a programming style emphasizes What (to do) abstracting away the details of How (to do it) the more that style is considered to be declarative. The opposite is true for imperative. Functional programming is associated with the declarative style.