Linguaggi di programmazione che definiscono il problema anziché la soluzione?

Question

Esistono linguaggi di programmazione progettati per definire la soluzione a un dato problema invece di definire istruzioni per risolverlo? Quindi, si definirebbe quale dovrebbe essere la soluzione o il risultato finale e l'interprete del linguaggio determinerebbe come arrivare a quel risultato. Guardando il list of programming languages, non sono sicuro di come iniziare a fare ricerche su questo.

I migliori esempi che posso attualmente pensare per aiutare a illustrare ciò che sto cercando di chiedere sono SQL e MapReduce, anche se sono entrambi tipi di mini-lingue progettati per recuperare i dati. Tuttavia, quando si scrivono istruzioni SQL o MapReduce, si sta definendo il risultato finale e il DB decide la migliore linea d'azione per arrivare al set di risultati finali.

Potrei vedere questi tipi di linguaggi, se esistono, utilizzati per elaborare molti dati o trovare soluzioni a un insieme di equazioni. Il linguaggio dei sogni potrebbe essere quello che potrebbe interpretare il problema definito, identificare quali parti sono parallelizzabili ed eseguire la soluzione su più processi/core/scatole.

Answer 1

Che dire di Declarative Programming? Estratto dall'articolo wikipedia (corsivo):

In informatica, dichiarativa programmazione è un paradigma di programmazione che esprime la logica di un computazione senza descrivere il flusso controllo. Molte lingue che applicano questo tentativo stile minimizzare o eliminare gli effetti collaterali da descrivendo ciò che il programma dovrebbe realizzare, piuttosto che descrivere come fare per realizzare esso.Questo è in contrasto con la programmazione imperativa , che richiede un algoritmo fornito esplicitamente .

Answer 2

Il più vicino a qualcosa di simile è con un linguaggio logico come Prolog. In queste lingue modellate la logica del problema ma di nuovo non è magico.

Answer 3

Sembra una descrizione di un linguaggio dichiarativo (in particolare un linguaggio di programmazione logica), il cui esempio più noto è Prolog. Non ho idea se il Prolog sia parallelizzabile, comunque.

In base alla mia esperienza, Prolog è ottimo per risolvere i problemi di soddisfazione dei vincoli (quelli in cui c'è una serie di condizioni che devono essere soddisfatte) - si definisce il set di input, si definiscono i vincoli (ad esempio, un ordine che deve essere imposto sugli input precedentemente non ordinati) - ma sono possibili casi patologici e talvolta il processo di deduzione logica richiede molto tempo per essere completato.

Se è possibile definire il problema in termini di una formula booleana, è possibile creare un solutore SAT, ma si noti che il problema 3SAT (assegnazione di variabile booleana su clausole a tre variabili) è NP-completo, e il suo primo- fratello maggiore di ordine logico, il problema della formula quantificata di Boolean (che utilizza quantificatori esistenziali e quantificatori universali) è completo a PSPACE.

Ci sono alcuni ottimi dimostratori di teoremi scritti in OCaml e in altri linguaggi FP; here sono un sacco di loro.

E ovviamente c'è sempre una programmazione lineare tramite il metodo simplex.

Answer 4

Lasciami provare a rispondere ... potrebbe essere Prolog potrebbe rispondere alle tue esigenze.

Answer 5

Queste lingue sono comunemente denominate 5th generation programming languages. Ci sono alcuni esempi sulla voce di Wikipedia a cui mi sono collegato.

Answer 6

Ci sono vari motori di regole basati su Java che consentono la programmazione dichiarativa - Drools è uno con cui ho giocato e sembra piuttosto interessante.

Answer 7

direi Obiettivo Caml (OCaml) troppo ...

Answer 8

Un sacco di lingue definire più problemi che soluzioni (non prendere questo sul serio).

Su una nota seria: un altro voto per Prolog e diversi tipi di DSL progettati per essere dichiarativi.

Answer 9

Ricordo di aver letto qualcosa sul calcolo usando DNA quando ero al college. Metterei segmenti di DNA in una soluzione che rappresentasse segmenti del problema e definirlo in modo tale che se il DNA si adattava insieme, è una soluzione valida. Quindi lascia che le proprietà delle sostanze chimiche risolvano il problema e cerchi i fili finiti che rappresentano una soluzione. Sembra un po 'come quello a cui ti stai riferendo.

Non ricordo se era teorico o era stato fatto, però.

Answer 10

Questo può sembrare irriverente, ma in un certo senso è lo stackoverflow. Dichiarate un problema e/o il risultato previsto e la comunità fornisce la soluzione, solitamente in codice.

Sembra immensamente difficile modellare i sistemi dinamici aperti su un numero finito di soluzioni. Penso che ci sia un motivo per cui la maggior parte dei linguaggi di programmazione sono indispensabili. Per non parlare dei massicci problemi di P = NP in agguato nell'oscurità che renderebbero difficile l'ingegnerizzazione di un sistema del genere.

Anche se ciò che sarebbe interessante è se esistesse una struttura formale che potesse sfruttare l'input umano per "scricchiolare i numeri" e fornire una soluzione, forse una generazione di codice imperativa. I motori di ricerca di internet e google sono una specie di strumento, ma molto primitivo.

Grandi problemi e software sono fondamentalmente solo una raccolta di piccoli problemi risolti nel codice. Quindi qualsiasi sistema che genera codice richiederebbe set di problemi abbastanza delimitati che possono essere mappati su più o meno soluzioni atomiche.

Answer 11

LINQ potrebbe anche essere considerato un altro DSL dichiarativo (aschewing l'argomento che è troppo simile a SQL). Di nuovo, dichiari come si presenta la tua soluzione e LINQ decide come trovarlo.

La bellezza di questi tipi di linguaggi è che i progetti come PLINQ (che ho appena trovato) possono sorgere intorno a loro. Check out this video with the PLINQ developers (collegamento diretto WMV) su come parallelizzare la ricerca della soluzione senza modificare il linguaggio LINQ (molto).

Answer 12

Lisp. Ci sono così tanti sistemi Lisp là fuori definiti in termini di regole e comandi non imperativi. Google ahoy ...

Answer 13

Mentre le dimostrazioni matematiche non costituiscono un linguaggio di programmazione, formano un linguaggio formale in cui si definiscono semplicemente le soluzioni (purché si consentano prove non costruttive). Certo, non è algoritmico, quindi "matematica" potrebbe non essere una risposta accettabile.