Programmazione logica (Unificazione) vs Comprensioni elenco (in Programmazione funzionale)

La differenza è questa:

1. La programmazione funzionale si basa su riduzione - scrittura di espressioni complesse in valori irriducibili usando le regole di riscrittura direzionali , con un senso stretto di "input" rispetto a "output";
2. La programmazione logica si basa sulla soddisfazione dei vincoli -finding soluzioni a gruppi di istruzioni da ricerca per valori che , quando collegato per le variabili 'statement', rendi queste affermazioni vere.

I.e. in Haskell you can write something like [(i,j) | i <- [1..10], j <- [5..20], j < i] and Haskell returns a list of all possible values of i and j that adhere to j < i.

Ma in Haskell il modo in cui funziona è in termini di valutazione delle applicazioni di funzione. La tua espressione ...

[(i,j) | i <- [1..10], j <- [5..20], j < i]

... è equivalente a questo in Haskell:

concatMap (\i -> concatMap (\j -> if j < i then [(i,j)] else []) [5..20]) [1..10]

Dove concatMap è una funzione standard che può essere definita in questo modo:

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap _ [] = []
concatMap f (a:as) = f a ++ concatMap f as

-- concatMap uses this function as well:
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

E nella valutazione Haskell, le equazioni che definiscono le funzioni sono sempre e solo usate in una direzione "da sinistra a destra". Per valutare un'espressione, cerchiamo le occorrenze che corrispondono ai lati della mano sinistra delle equazioni e sostituiamo le controparti del lato destro, mai il contrario. Quindi:

concatMap (\i -> concatMap (\j -> if j < i then [(i,j)] else []) [5..20]) [1..10]

-- Reduce the outermost concatMap with its definition's second equation:
==>    concatMap (\j -> if j < 1 then [(1,j)] else []) [5..20] 
    ++ concatMap (\i -> concatMap (\j -> if j < i then [(i,j)] else []) [5..20]) [2..10]

-- Reduce the first 'concatMap' with its definition's second equation:
==>    if 5 < 1 then [(1,5)] else []
    ++ concatMap (\j -> if j < 1 then [(1,j)] else []) [6..20] 
    ++ concatMap (\i -> concatMap (\j -> if j < i then [(i,j)] else []) [5..20]) [2..10]

-- Reduce '5 < 1' to 'False':
==>    if False then [(1,5)] else []
    ++ concatMap (\j -> if j < 1 then [(1,j)] else []) [6..20] 
    ++ concatMap (\i -> concatMap (\j -> if j < i then [(i,j)] else []) [5..20]) [2..10]

-- Reduce 'if False x else y' to 'y'
==>    []
    ++ concatMap (\j -> if j < 1 then [(1,j)] else []) [6..20] 
    ++ concatMap (\i -> concatMap (\j -> if j < i then [(i,j)] else []) [5..20]) [2..10]

-- Reduce the first '++' with its definition's first equation
==>    concatMap (\j -> if j < 1 then [(1,j)] else []) [6..20] 
    ++ concatMap (\i -> concatMap (\j -> if j < i then [(i,j)] else []) [5..20]) [2..10]

  .
  .
  .

Questo processo è diverso e meno potente dell'unificazione.

Ci sono due cose che stanno succedendo qui. Innanzitutto, l'unificazione è un meccanismo di implementazione . A cosa serve un meccanismo di implementazione? Quantificazione esistenziale Non sorprende che la semantica dei linguaggi di programmazione logica sia basata sulla logica. Quando fai una query in Prolog come ?- append(Xs,Ys,[1,2,3,4]) , questa è una ricerca di una prova di exists Xs, Ys. append(Xs,Ys,[1,2,3,4]) . Una dimostrazione (costruttiva) di questa proposizione sarebbe valori effettivi per Xs e Ys che soddisfano il predicato append . Un modo per trovare questa prova (e tutti gli altri) sarebbe cercarlo esaustivamente. Un modo molto più efficiente è utilizzare l'unificazione e la variabile di unificazione "raccoglierà" efficacemente una serie di vincoli e quei vincoli descriveranno l'insieme di soluzioni.

Il codice di comprensione dell'elenco corrisponde a una ricerca esaustiva. Sfortunatamente, la ricerca esauriente non è solo meno efficiente, ma ha anche alcuni problemi aggiuntivi. In primo luogo, potrebbe non riuscire a terminare o esplorare completamente lo spazio di ricerca se non implementato attentamente. In secondo luogo, non fornisce alcun mezzo per rappresentare una soluzione infinita, che non enumeri tutti i valori possibili. In Prolog, una variabile logica non associata può sostituire un insieme infinito di risultati. (Per essere chiari, però, la maggior parte dei set infiniti di risultati non può essere rappresentati solo avendo alcune variabili logiche non associate, e quindi anche Prolog inizierà semplicemente a enumerare tutti i valori possibili in quei casi. la gamma di set di soluzioni che possono essere rappresentati in modo compatto.)

Tuttavia, ignorando questi problemi, possiamo pensare alle comprensioni delle liste (che corrispondono all'uso della monade List) come incorporamento di un semplice linguaggio logico in Haskell. Esistono monadi molto più intelligenti per incorporare la programmazione logica in Haskell che usa l'unificazione come meccanismo di implementazione. Un'incarnazione più vecchia ma particolarmente piacevole è descritta in digitato Variabili logiche in Haskell .

Questo è in larga misura corretto, ma:

1. A causa della propagazione dei vincoli, un linguaggio di programmazione logica può tagliare l'esecuzione molto prima e creare un'enorme differenza di prestazioni.
2. Molti concetti sono più facili da esprimere. (Forse una questione di opinione?) Prendi l'esempio che hai dato nella citazione. Come faresti a trovare tutte le coppie di liste concatenate che ti offrono una terza lista che hai fornito?
3. È molto più semplice passare da un tipo di ricerca a un altro. Come cambieresti il codice nel mio punto 2 per controllare improvvisamente "quale lista A dovrei iniziare se voglio concatenarlo con una data B per ottenere una C data". Probabilmente molto Nella programmazione logica, in pratica, basta cambiare uno dei simboli in una variabile.