Come convertire in stile CPS GCD calcolo di utilizzare la continuazione Monade

Question

Consideriamo la seguente implementazione della monade Continuazione, per i calcoli in stile CPS rendimento e numero intero:

module Cont : sig 
    type 'a t = ('a -> int) -> int 
    val return : 'a -> 'a t 
    val bind : 'a t -> ('a -> 'b t) -> 'b t 
    val callCC: (('a -> 'b t) -> 'a t) -> 'a t 
end = struct 
    type 'a t = ('a -> int) -> int 

    let return x = 
    fun cont -> cont x 

    let bind m f = 
    fun cont -> m (fun x -> (f x) cont) 

    let callCC k = 
    fun cont -> k (fun x -> (fun _ -> cont x)) cont 
end 

Come possiamo riscrivere il CPS- implementazione di stile del calcolo gcd (vedi How to memoize recursive functions?) e in particolare la memoizzazione per sfruttare il monito Cont?

Dopo aver definito

let gcd_cont k (a,b) = 
    let (q, r) = (a/b, a mod b) in 
    if r = 0 then Cont.return b else k (b,r) 

ho cercato di utilizzare il tipo di risolutore di darmi spunto circa il tipo che la funzione Memoizzazione dovrebbe avere:

# let gcd memo ((a,b):int * int) = 
    Cont.callCC (memo gcd_cont (a,b)) (fun x -> x) 
;; 
    val gcd : 
    (((int * int -> int Cont.t) -> int * int -> int Cont.t) -> 
    int * int -> (int -> 'a Cont.t) -> int Cont.t) -> 
    int * int -> int = <fun> 

Tuttavia non potrebbe trasformare questo suggerimento in un implementazione effettiva. Qualcuno è in grado di farlo? La logica alla base dell'utilizzo di "callCC" nella funzione di memoizzazione è che se si trova un valore nella cache, allora questa è una condizione di uscita anticipata.

Answer 1

Mi sembra che il problema sia che nella sua risposta allo How to memoize recursive functions?, Michael ha definito lo stile CPS quello che non è lo stile CPS. In stile CPS, l'argomento di continuazione aggiuntivo k viene utilizzato ogni volta che si desidera restituire un valore, il valore viene quindi applicato a k.

Questo non è proprio quello che vogliamo qui, e non quello che implementa:

let gcd_cont k (a,b) = 
    let (q, r) = (a/b, a mod b) in 
    if r = 0 then b else k (b,r) 

Qui, k non viene utilizzato per la restituzione (b viene restituito direttamente), è usato invece di eseguire una chiamata ricorsiva. Questo risolve la ricorsione: all'interno di gcd_cont, si può pensare a k come gcd_cont stesso, proprio come se fosse stato utilizzato let rec. Successivamente, gcd_cont può essere trasformato in una vera funzione ricorsiva utilizzando un combinatore punto fisso, che fondamentalmente "alimenta a se stessa":

let rec fix f x = f (fix f) x 
let gcd = fix gcd_cont 

(questo è equivalente alla funzione call che Michael definisce)

L' la differenza con la definizione di gcd utilizzando direttamente un let rec è che la versione con ricorsione non svolta consente di "strumentare" le chiamate ricorsive, poiché la ricorsione stessa viene eseguita dal combinatore del punto di fissazione. Questo è ciò che vogliamo per la memoizzazione: vogliamo solo eseguire la ricorsione se il risultato non è nella cache. Quindi la definizione di un combinatore memo.

Se la funzione è definita con let rec, la ricorsione viene chiusa contemporaneamente alla definizione della funzione, pertanto non è possibile strumentare i siti di chiamata ricorsivi per inserire la memoizzazione.

Come nota a margine, le due risposte fondamentalmente attuare la stessa cosa: l'unica differenza è il modo in cui implementare la ricorsione nel Combinator punto fisso: punto fisso combinatore di Michael utilizza let rec, uno di Jackson utilizza un riferimento, vale a dire "il nodo di Landin" - un modo alternativo per implementare la ricorsione, se hai riferimenti nella tua lingua.

Quindi, per concludere, direi che l'implementazione nella monade della continuazione non è realmente possibile/non ha realmente senso, poiché la cosa non era CPS in primo luogo.