Il sogno della programmazione dichiarativa [chiuso]

Ci sono alcune ottime risposte. Proverò a contribuire alla discussione.

Sul tema della programmazione dichiarativa e logica in Prolog, c'è il grande libro "The Craft of Prolog" di Richard O ' Keefe. Si tratta di scrivere programmi efficienti usando un linguaggio di programmazione che ti permetta di scrivere programmi molto inefficienti. In questo libro, mentre si discute delle implementazioni efficienti di diversi algoritmi (nel capitolo "Metodi di programmazione"), l'autore adotta il seguente approccio:

• definisce il problema in inglese
• scrivere una soluzione di lavoro che sia il più dichiarativa possibile; di solito, questo significa praticamente esattamente quello che hai nella tua domanda, basta correggere Prolog
• da lì, prendi provvedimenti per perfezionare l'implementazione per renderla più veloce

L'osservazione più illuminante (per me) che sono riuscito a fare mentre ho lavorato su questi:

Sì, la versione finale dell'implementazione è molto più efficiente della specifica "dichiarativa" con cui l'autore ha iniziato. È ancora molto dichiarativo, succinto e facile da capire. Quello che è successo nel frattempo è che la soluzione finale cattura le proprietà del problema a cui la soluzione iniziale era ignara.

In altre parole, mentre implementavamo una soluzione, abbiamo usato la maggior parte delle nostre conoscenze sul problema che possiamo. Confronto:

Find a permutation of a list such that all elements are in ascending order

a:

Merging two sorted lists will result in a sorted list. Since there might be sublists that are already sorted, use these as a starting point, instead of sublists of length 1.

Un piccolo accenno: una definizione come quella che hai dato è attraente perché è molto generale. Tuttavia, non posso sfuggire alla sensazione che ignori intenzionalmente il fatto che le permutazioni sono, beh, un problema combinatorio. Questo è qualcosa che già conosciamo ! Questa non è una critica, solo un'osservazione.

Per quanto riguarda la vera domanda: come andare avanti? Bene, un modo è quello di fornire tanta conoscenza sul problema che stiamo dichiarando al computer.

Il miglior tentativo che io conosca per risolvere veramente il problema è presentato nei libri scritti da Alexander Stepanov, "Elementi di programmazione" e "Dalla matematica alla programmazione generica" . Purtroppo non sono in grado di riassumere (o anche di comprendere appieno) tutto in questi libri. Tuttavia, l'approccio consiste nel definire algoritmi di librerie e strutture dati efficienti (o persino ottimali), a condizione che tutte le proprietà rilevanti dell'input siano conosciute in anticipo. Il risultato finale è:

• Ogni trasformazione ben definita è un perfezionamento dei vincoli già esistenti (le proprietà note);
• Consentiamo al computer di decidere quale trasformazione è ottimale in base ai vincoli esistenti.

Per quanto riguarda il motivo per cui non è ancora successo, beh, l'informatica è un campo molto giovane, e stiamo ancora affrontando apprezzando veramente la novità di gran parte di esso.

PS

Per darti un'idea di cosa intendo per "perfezionare l'implementazione": prendi ad esempio il semplice problema di ottenere l'ultimo elemento di una lista, in Prolog. La soluzione dichiarativa canonica è:

last(List, Last) :-
    append(_, [Last], List).

Qui, il significato dichiarativo di append/3 è:

List1AndList2 is the concatenation of List1 and List2

Poiché nel secondo argomento a append/3 abbiamo una lista con un solo elemento, e il primo argomento è ignorato (il carattere di sottolineatura), otteniamo una divisione dell'elenco originale che scarta la parte anteriore dell'elenco ( List1 nel contesto di append/3 ) e richiede che la parte posteriore ( List2 nel contesto di append/3 ) sia effettivamente una lista con un solo elemento: quindi, è l'ultimo elemento.

La implementazione effettiva fornito da SWI-Prolog , tuttavia, afferma:

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

Questo è ancora ben dichiarativo. Leggi dall'alto verso il basso, dice:

The last element of a list only makes sense for a list of at least one element. The last element for a pair of the tail and the head of a list, then, is: the head, when the tail is empty, or the last of the non-empty tail.

Il motivo per cui viene fornita questa implementazione è di aggirare i problemi pratici relativi al modello di esecuzione di Prolog. Idealmente, non dovrebbe fare la differenza quale applicazione viene utilizzata. Allo stesso modo, avremmo potuto dire:

last(List, Last) :-
    reverse(List, [Last|_]).

The last element of a list is the first element of the reversed list.

Se vuoi fare il pieno di discussioni inconcludenti su ciò che è buono, Prolog dichiarativo, basta leggere alcune domande e risposte nel Tag Prolog su Stack Overflow .

Le lingue logiche lo fanno già. Puoi definire l'ordinamento in modo simile a come lo stai facendo.

Il problema principale sono le prestazioni. I computer potrebbero essere bravi a calcolare molte cose, ma sono intrinsecamente stupidi. Ogni decisione "intelligente" che un computer potrebbe fare è stata programmata da un programmatore. E questa decisione di solito non viene descritta da come appare il risultato finale, ma da come raggiungere, passo dopo passo, questo risultato finale.

Immagina la storia di un Golem . Se provi a dargli un comando astratto, nel migliore dei casi, lo farà in modo inefficiente e nel peggiore dei casi, farà del male a se stesso, a te oa qualcun altro. Ma se descrivi ciò che vuoi nel più grande dettaglio possibile, ti garantiamo che l'attività sarà completata in modo efficace ed efficiente.

È compito del programmatore decidere quale livello di astrazione utilizzare. Per l'applicazione che stai facendo, vai ad alto livello e descrivi in modo astratto e prendi il colpo di performance o vai basso e sporco, trascorri 10 volte più tempo su di esso, ma ottieni un algoritmo che è 1000 volte più performante?

Oltre a l'eccellente punto di Euphoric , vorrei aggiungere che stiamo già utilizzando linguaggi dichiarativi molti posti in cui funzionano bene, vale a dire che descrivono uno stato che non è suscettibile di cambiare o richiedere qualcosa per cui il computer può effettivamente generare un codice efficiente da solo:

• HTML dichiara il contenuto di una pagina Web.

• Il CSS dichiara come dovrebbero apparire i vari tipi di elementi in una pagina web.

• Ogni database relazionale ha una lingua di definizione dei dati che dichiara quale sia la struttura del database.

• SQL è molto più vicino a dichiarativo che imperativo, dal momento che tu dici ciò che vuoi vedere e il pianificatore di query del database calcola come effettivamente farlo accadere.

• Si potrebbe sostenere che la maggior parte dei file di configurazione (.vimrc, .profile, .bashrc, .gitconfig) utilizzano un linguaggio specifico del dominio che è in gran parte dichiarativo

Le astrazioni perdono

È possibile implementare un sistema dichiarativo in cui si dichiara ciò che si desidera e il compilatore o l'interpretatore calcola un ordine di esecuzione. Il vantaggio teorico è che ti libera dal dover pensare al "come" e non devi dettagliare questa implementazione. Tuttavia, in pratica per l'uso generico, devi ancora pensare al "come" e scrivere tutti i tipi di trucchi tenendo a mente come verrà implementato, altrimenti il compilatore può (e spesso lo farà) scegliere un'implementazione che sarà molto, molto, molto lento (per esempio n operazioni dove n sarebbe sufficiente).

Nel tuo particolare esempio, otterrai un algoritmo di ordinamento A - non significa che ne otterrai uno buono o anche abbastanza usabile. La definizione data, se implementata letteralmente (come probabilmente un compilatore sarebbe) produce un link che è inutilizzabile per dataset più grandi - è tecnicamente corretto, ma ha bisogno di un'eternità per ordinare un migliaio di numeri.

Per alcuni domini limitati è possibile scrivere sistemi che quasi sempre fanno bene a capire una buona implementazione, ad esempio SQL. Per l'elaborazione generica che non funziona particolarmente bene, è possibile scrivere sistemi, ad esempio, in Prolog, ma è necessario visualizzare in che modo esattamente le dichiarazioni verranno convertite in un ordine di esecuzione imperativo alla fine e che perderà gran parte delle dichiarazioni dichiarative previste vantaggi di programmazione.

La decidibilità computazionale è la ragione più importante per cui la programmazione dichiarativa non è stata così facile come sembra.

Molti problemi che sono relativamente facili da dichiarare si sono dimostrati indecidibili o hanno una complessità NP-completa da risolvere. Ciò si verifica spesso quando prendiamo in considerazione le classi negative e la classificazione, la numerabilità e la ricorsione.

Vorrei esagerare con alcuni domini noti.

Decisione su quale classe CSS usare richiede conoscenza e considerazione di tutte le regole CSS. L'aggiunta di nuove regole potrebbe invalidare tutte le altre decisioni. Le classi CSS negative sono intenzionalmente non aggiunte alla lingua, a causa di problemi NP-completi, ma la mancanza di classi negative complica le decisioni di progettazione CSS.

All'interno di un ottimizzatore di query (SQL), c'è il problema orribile di decidere in quale ordine unirsi, quali indici utilizzare e quale memoria allocare a quali risultati temporanei. Questo è un noto problema NP-completo e complica la progettazione del database e la formulazione di query. Per formularlo in modo diverso: quando si progetta un database o una query, il progettista deve conoscere le azioni e l'ordine delle azioni che è probabile che richieda l'ottimizzatore di query. Un ingegnere esperto ha bisogno di conoscere l'euristica utilizzata dai principali fornitori di database.

I file di configurazione sono dichiarativi, ma alcune configurazioni sono difficili da dichiarare. Ad esempio, per configurare correttamente le funzionalità è necessario tenere conto del controllo delle versioni, della distribuzione (e della cronologia delle implementazioni), delle eventuali sostituzioni manuali e possibili conflitti con altre impostazioni. Per validare correttamente una configurazione potrebbe diventare un problema NP-completo.

Il risultato è che queste complicazioni sorprendono i principianti, rompono la "bellezza" della programmazione dichiarativa e fanno sì che alcuni ingegneri cerchino altre soluzioni. La migrazione di ingegneri inesperti da SQL a NoSQL potrebbe essere stata innescata dalle complessità sottostanti dei database relazionali.

Abbiamo una differenza nella dichiaratività dei linguaggi di programmazione che viene utilizzata per la verifica della logica digitale.

Normalmente la logica digitale è descritta al livello di trasferimento del registro (RTL) in cui il livello logico dei segnali tra registri è definito. Per verificare che stiamo aggiungendo sempre più le proprietà definite in modo più astratto e dichiarativo.

Uno dei sottoinsiemi linguistici / linguistici più dichiarati è chiamato PSL per la lingua delle specifiche di proprietà. Quando si verifica un modello RTL di un moltiplicatore in cui, ad esempio, tutte le operazioni logiche di spostamento e aggiunta su più cicli di clock richiedono da specificare; puoi scrivere una proprietà nel modo assert that when enable is high, this output will equal the multiplication of these two inputs after no more than 8 clock cycles . La descrizione PSL può quindi essere controllata insieme all'RTL in una simulazione, oppure il PSL può essere formalmente provato per la descrizione RTL.

Il modello PSL più dichiarativo costringe a descrivere lo stesso comportamento della descrizione RTL, ma in un modo sufficientemente diverso che può essere automaticamente verificato rispetto all'RTL per vedere se sono d'accordo.

Per lo più il problema è come modellate i dati; e la programmazione dichiarativa non sta aiutando qui. Nelle lingue imperative hai già un sacco di librerie che fanno un sacco di cose per te, quindi hai solo bisogno di sapere cosa chiamare. In un modo particolare si potrebbe considerare questa programmazione dichiarativa (probabilmente il miglior esempio per questo è Stream API in Java 8 ). Avendo questo, l'astrazione è già stata risolta e la programmazione dichiarativa non è necessaria.

Inoltre, come è stato detto, i linguaggi di programmazione logica fanno già esattamente quello che vuoi. Si potrebbe dire che il problema è rappresentato dalle prestazioni, ma con l'hardware e la ricerca di oggi in quest'area, le cose possono essere migliorate per essere pronte per l'uso in produzione; in realtà Prolog è usato per roba di IA, ma credo solo dal mondo accademico.

Si noti che si applica ai linguaggi di programmazione generici. Per le lingue specifiche di dominio, le lingue dichiarative sono molto migliori; SQL è probabilmente l'esempio migliore.

Sembrerebbe qualcosa del genere .. {(qualunque cosa = > leggi un file e chiama un url) | chiama un url & leggi un file} Tuttavia, queste sono azioni da eseguire e, di conseguenza, lo stato del sistema cambia, ma ciò non è ovvio dalla fonte.

I dichiaranti possono descrivere una macchina a stati finiti e le sue transizioni. L'FSM è come l'opposto dei dichiarativi senza azioni, anche se l'unico l'azione è di cambiare stato allo stato successivo.

Il vantaggio di usare questo metodo è che le transizioni e le azioni possono essere specificato da predicati che si applicano a più transizioni, piuttosto che a una sola.

So che sembra un po 'strano, ma nel 2008 ho scritto un programma generatore che usa questo metodo e il C ++ generato è da 2 a 15 volte tanto quanto la fonte. Ora ho oltre 75.000 righe di C ++ da 20.000 righe di input. Due cose vanno con questo: coerenza e completezza.

Coerenza: non possono esistere due predicati che possono essere veri allo stesso tempo azioni incoerenti, come x = 8 e x = 9, né diversi stati successivi.

Completezza: viene specificata la logica per ogni transizione di stato. Questi possono essere difficili da controllare per i sistemi con N sottostati, con > 2 ** N stati, ma ci sono interessanti metodi combinatori che possono verificare tutto. Nel 1962 scrissi la fase 1 di un ordinamento di sistema per le macchine 7070, usando questo tipo di generazione di codice condizionale e debug combinatorio. Delle 8.000 linee del genere, il numero di bug dal giorno della prima versione per sempre era pari a zero!

La fase due del genere, 12.000 linee, ha avuto oltre 60 errori nei primi due mesi. C'è molto altro da dire su questo, ma funziona. Se le case automobilistiche usassero questo metodo per controllare il firmware, non lo vedremmo i fallimenti che vediamo ora.

Non tutto può essere rappresentato in modo dichiarativo.

Spesso, vuoi esplicitamente per controllare il flusso di esecuzione

Ad esempio, seguendo lo pseudo-codice: %codice% Come lo descriveresti in modo dichiarativo?

Certo, ci sono probabilmente alcuni modi esotici per farlo. Come monadi . Ma questi di solito sono più ingombranti, complicati e molto meno intuitivi della loro parte procedurale.

Tutto si riduce al fatto che "interagire" con il tuo ambiente / sistema è non dichiarativo. Tutto ciò che riguarda I / O è procedurale per essenza. Devi dire esattamente quando e cosa dovrebbe accadere, e in quale ordine.

Il dichiarativo è ottimo per tutto ciò che è puramente correlato al calcolo. Come una funzione gigante, inserisci X e ottieni Y. È grandioso. Un esempio è HTML, l'input è di testo, l'output è quello che vedi nel tuo browser.