Devo evitare la ricorsione della coda in Prolog e in generale?

Question

Sto lavorando con il libro online "Learn Prolog now" per divertimento.

che sto cercando di scrivere un predicato che passa attraverso ciascun membro di una lista e aggiunge uno ad esso, con gli accumulatori. L'ho già fatto facilmente senza ricorsione della coda.

addone([],[]). 
addone([X|Xs],[Y|Ys]) :- Y is X+1, addone(Xs,Ys). 

Ma ho letto che è meglio evitare questo tipo di ricorsione per motivi di prestazioni. È vero? È considerata "buona pratica" usare sempre la ricorsione della coda? Varrà la pena di usare gli accumulatori per fare una buona abitudine?

Ho provato a modificare questo esempio in accumulatori, ma inverte l'elenco. Come posso evitare questo?

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result). 
accAddOne([],A,A). 
addone(List,Result) :- accAddOne(List,[],Result). 

Answer 1

Risposta breve: La ricorsione della coda è auspicabile, ma non esagerare.

Il tuo programma originale è come coda ricorsiva che puoi ottenere in Prolog. Ma ci sono problemi più importanti: correttezza e risoluzione.

Infatti, molte implementazioni sono più che disposti a sacrificare coda ricorsività per altre proprietà che ritengono più importante. Ad esempio steadfastness.

Ma il tuo tentativo di ottimizzazione ha un certo punto. Almeno da una prospettiva storica.

Negli anni '70, il linguaggio AI principale era LISP. E la corrispondente definizione sarebbe stata

(defun addone (xs) 
    (cond ((null xs) nil) 
    (t (cons (+ 1 (car xs)) 
     (addone (cdr xs)))))) 

non direttamente tail-ricorsiva: La ragione è la cons: In implementazioni di quel tempo, i suoi argomenti sono stati valutati prima, solo allora, potrebbe essere eseguito il cons. Quindi riscriverlo come hai indicato (e invertendo l'elenco risultante) era una possibile tecnica di ottimizzazione.

In Prolog, tuttavia, è possibile creare gli svantaggi prima di conoscere i valori effettivi, grazie alle variabili logiche. Così tanti programmi che non erano ricorsivi in ​​coda in LISP, tradotti in programmi ricorsivi in ​​coda in Prolog.

Le ripercussioni di questo possono ancora essere trovate in molti libri di testo Prolog.

Answer 2

non credo che la prima versione di addone dovrebbe portare a codice meno efficiente. È anche molto più leggibile, quindi non vedo ragioni per cui dovrebbe essere una buona pratica evitarlo.

Negli esempi più complessi, il compilatore potrebbe non essere in grado di trasferire il codice automaticamente alla coda ricorsione. Quindi potrebbe essere ragionevole riscriverlo come ottimizzazione, ma solo se è davvero necessario.

Quindi, come si può implementare una coda versione funzionante ricorsiva di addone? Può essere barare, ma partendo dal presupposto che reverse viene implementato con la coda-ricorsione (ad esempio, vedere here), quindi può essere utilizzato per risolvere il problema:

E 'estremamente goffo, però. :-)

A proposito, non riesco a trovare una soluzione più semplice. Può a causa della stessa ragione come foldr in Haskell normalmente non è definito con ricorsione della coda.

Answer 3

La procedura addOne già è coda ricorsiva.

Non ci sono punti di scelta tra la testa e l'ultima chiamata ricorsiva, perché è/2 è deterministico.

accumulatori sono a volte aggiunti per consentire ricorsione in coda, l'esempio più semplice che posso pensare è inversa/2. Ecco un'inversione ingenuo (nreverse/2), non la coda ricorsiva

nreverse([], []). 
nreverse([X|Xs], R) :- nreverse(Xs, Rs), append(Rs, [X], R). 

se aggiungiamo un accumulatore

reverse(L, R) :- reverse(L, [], R). 
reverse([], R, R). 
reverse([X|Xs], A, R) :- reverse(Xs, [X|A], R). 

ora invertire/3 è la coda ricorsiva: la chiamata ricorsiva è l'ultimo, e nessun punto di scelta è rimasto.

Answer 4

O.P. detto:

ma ho letto che è meglio evitare la ricorsione [coda] per motivi di prestazioni. È vero? È considerata "buona pratica" usare sempre la ricorsione della coda? Sarà lo sforzo degno di usare gli accumulatori per ottenere una buona abitudine?

È un'ottimizzazione piuttosto semplice convertire un costrutto coda-ricorsivo in iterazione (un ciclo). Poiché la coda (ricorsiva) chiamata è l'ultima cosa fatta, il frame dello stack può essere riutilizzato nella chiamata ricorsiva, rendendo la ricorsione, a tutti gli effetti, un loop, semplicemente saltando all'inizio del predicato/funzione/metodo /sottoprogramma. Pertanto, un predicato ricorsivo di coda non traboccherà lo stack. Il costrutto ricorsivo di coda, con l'ottimizzazione applicata, presenta i seguenti vantaggi:

• Esecuzione leggermente più veloce poiché i nuovi frame di stack non devono essere allocati/liberati; inoltre, si ottiene una migliore localizzazione di riferimento, quindi probabilmente meno paginazione.
• Nessun limite superiore della profondità di ricorsione.
• Nessuno stack overflow.

Gli svantaggi possibili?

• perdita di utili analisi dello stack. Non è un problema se TRO viene applicato solo in una versione/build ottimizzata e non in una build di debug, ma ...
• gli sviluppatori scriveranno il codice che dipende da TRO, il che significa che il codice funzionerà correttamente con TRO applicato fallirà senza TRO applicato. Ciò significa che nel caso di cui sopra (TRO solo nelle build release/ottimizzate), esiste un cambiamento funzionale tra build di debug e release, essenzialmente nel senso che la scelta delle opzioni del compilatore genera due programmi diversi dallo stesso codice sorgente.

Questo non è, ovviamente, un problema, quando lo standard linguistico richiede un'adeguata ottimizzazione della ricorsione.

Per citare Wikipedia:

chiamate di coda sono importanti perché possono essere implementate senza aggiungere un nuovo stack frame per lo stack di chiamate. La maggior parte del frame della procedura corrente non è più necessaria e può essere sostituita dal frame della coda chiamata, modificata come appropriato (simile alla sovrapposizione per i processi, ma per le chiamate di funzione ). Il programma può quindi saltare alla subroutine chiamata. La produzione di tale codice invece di una sequenza di chiamate standard viene chiamata eliminazione chiamata a coda o coda ottimizzazione chiamata.

Consulta anche:

• What Is Tail Call Optimization?
• The Portland Pattern Repository on the matter
• e anche Microsoft's MSDN

non ho mai capito il motivo per cui più lingue non implementano l'ottimizzazione ricorsione coda