Combinazioni combinatore e coda di chiamata Y

Question

Combinazioni combinatore e coda di chiamata Y

#1 da (3 voti)
#2 da (0 voti)

20

La definizione di un combinatore Y in F # è

let rec y f x = f (y f) x

f si aspetta di avere come primo argomento una continuazione per i sottoproblemi ricorsivi. Usando y f come continuazione, vediamo che f sarà applicato alle chiamate successive come possiamo sviluppare

let y f x = f (y f) x = f (f (y f)) x = f (f (f (y f))) x etc...

Il problema è che, a priori, questo schema preclude l'utilizzo di qualsiasi ottimizzazione di chiamata di coda: infatti, potrebbe esserci qualche operazione in sospeso nelle f, nel qual caso non possiamo semplicemente mutare il frame di stack locale associato a f.

Quindi:

da un lato, utilizzando il combinatore Y è necessaria una continuazione diversa diversa dalla funzione stessa.
sull'altro per applicare il TCO, vorremmo non avere alcuna operazione in sospeso in f e solo chiamare f stessa.

Sai in quale modo quei due potrebbero essere riconciliati? Come una Y con un accumulatore o una Y con un trucco CPS? O un argomento che dimostra che non c'è modo di farlo?

recursion f# tail-call continuation

posta nicolas 26.12.2012 - 19:08

fonte

2 risposte

Leggi altre domande sui tag recursion f# tail-call continuation

Quali strumenti elettronici per la mappatura della trama degli utenti puoi consigliare? [chiuso] L'open source non è dannoso per gli sviluppatori stessi? [chiuso]

score 3 · Answer 1

Do you know of any way in which those two could be reconciled?

No, e a ragione, IMHO.

Il combinatore Y è un costrutto teorico ed è necessario solo per eseguire il calcolo del lambda completo (ricorda, non ci sono loop nel calcolo lambda, né i lambda hanno nomi che potremmo usare per la ricorsione).

Come tale, il combinatore Y è davvero affascinante.

Ma : nessuno in realtà usa il combinatore Y per la ricorsione effettiva! (Tranne forse per divertimento, per mostrare che funziona davvero.)

Ottimizzazione della chiamata di coda, OTOH, è, come dice il nome, un'ottimizzazione. Non aggiunge nulla all'espresività di un linguaggio, è solo a causa di considerazioni pratiche come lo stack space e le prestazioni del codice ricorsivo a cui ci teniamo.

Quindi la tua domanda è: c'è il supporto hardware per la riduzione della beta? (La riduzione Beta è come le espressioni lambda sono ridotte, lo sai.) Ma nessun linguaggio funzionale (per quanto ne so) compila il suo codice sorgente in una rappresentazione di espressioni lambda che saranno ridotte in fase beta al runtime.

score 0 · Answer 2

Non sono completamente sicuro di questa risposta, ma è la migliore che potrei inventare.

Il combinatore y è intrinsecamente pigro, in lingue rigorose la pigrizia deve essere aggiunta manualmente tramite extra lambda.

let rec y f x = f (y f) x

La tua definizione sembra richiedere pigrizia per terminare, o l'argomento (y f) non finirebbe mai di valutare e dovrebbe valutare se f lo ha usato o meno. Il TOC in un contesto pigro è più complicato e inoltre il risultato di (y f) è la composizione di una funzione ripetuta senza applicazione con x . Non sono sicuro che questo necessiti di memoria O (n) dove n è la profondità della ricorsione, ma dubito che potresti ottenere lo stesso tipo di TOC che è possibile con qualcosa di simile (passando a Haskell perché non lo so davvero F #)

length acc []    = acc
length acc (a:b) = length (acc+1) b

Se non lo sai già, la differenza tra foldl e foldl' in Haskell potrebbe far luce sulla situazione. foldl è scritto come sarebbe fatto in un linguaggio desideroso. Ma invece di essere TOC, in realtà è peggio di foldr perché l'acculatore memorizza un thunk potenzialmente enorme che non può essere parzialmente valutato. (Questo è legato al motivo per cui sia foldl che foldl 'non funzionano su liste infinite.) Così nelle versioni più recenti di Haskell è stato aggiunto foldl' che forza la valutazione dell'accumulatore ogni volta che la funzione ricorre per garantire che non ci sia un enorme thunk creato. Sono sicuro che il link può spiegare meglio di me.