Ocaml continuazione stile di passaggio

Question

Sono nuovo di OCaml e provando a scrivere un proseguimento passando funzione di stile, ma piuttosto confuso che valore ho bisogno di passare in ulteriore argomento su k

Ad esempio, posso scrivere una funzione ricorsiva che restituisce vero se tutti gli elementi della lista è anche, altrimenti false.

quindi è come

let rec even list = .... 

il CPS, so che ho bisogno di aggiungere un argomento per passare la funzione così come

let rec evenk list k = .... 

ma non ho idea di come affrontare questo ke come funziona esattamente questo lavoro

per esempio per questa funzione, anche, sguardi d'ambiente come

val evenk : int list -> (bool -> ’a) -> ’a = <fun>

evenk [4; 2; 12; 5; 6] (fun x -> x)  (* output should give false *)

Answer 1

Il k continuazione è una funzione che prende il risultato da evenk ed esegue "il resto del calcolo" e produce la "risposta". Che tipo la risposta è e che cosa si intende per "il resto del calcolo" dipende da ciò che si sta utilizzando CPS per . CPS non è generalmente fine a se stessa, ma è fatto con uno scopo in mente. Ad esempio, in forma CPS è molto facile da implementare operatori di controllo o alle chiamate coda ottimizzare. Senza sapere che cosa si sta cercando di realizzare, è difficile rispondere alla tua domanda.

Per quello che vale, se si sta semplicemente cercando di convertire da stile diretto allo stile continuation che passa, e tutto quello che interessa è il valore della risposta, passando la funzione identità come la continuazione è di destra.

Un buon passo successivo sarebbe quello di implementare evenk utilizzare CPS. Farò un esempio più semplice. Se ho la funzione-stile diretto

let muladd x i n = x + i * n

e se presumo primitive CPS mulk e addk, posso scrivere

let muladdk x i n k =
  let k' product = addk x product k in
  mulk i n k'

E vedrete che il mulptiplication è fatta per prima, allora "continua" con k', che fa l'add, e, infine, che con continues k, che restituisce al chiamante. L'idea fondamentale è che all'interno del corpo di muladdk ho assegnato una k' continuazione fresca che significa un punto intermedio nella funzione moltiplicazione add. Per rendere il vostro lavoro evenk si dovrà destinare almeno uno di questi continuazione.

Spero che questo aiuta.

Answer 2

Ogni volta che ho giocato con CPS, la cosa passò al seguito è solo la cosa che normalmente tornare al chiamante. In questo semplice caso, un bel "intuizione lubrificante" è dare un nome alla continuazione "ritorno".

let rec even list return =
  if List.length list = 0
    then return true
    else if List.hd list mod 2 = 1
      then return false
      else even (List.tl list) return;;

let id = fun x -> x;;

Utilizzo

Esempio:. "anche [2, 4, 6, 8] id ;;"

Answer 3

Dal momento che hai l'invocazione di evenk corretta (con la funzione identità - convertire efficacemente la continuazione-passing-style torna allo stile normale), suppongo che la difficoltà è nel definire evenk

.

k è la funzione prosecuzione rappresenta il resto del calcolo e produrre un valore finale, come detto Norman. Allora, che cosa è necessario fare è calcolare il risultato di v di even e passare quel risultato a k, tornando k v piuttosto che solo v.

Answer 4

Si vuole dare come input il risultato della funzione, come se non fosse scritto con prosecuzione stile che passa.

Questa è la funzione che verifica se un elenco ha interi, anche se solo:

(* val even_list : int list -> bool *)
let even_list input = List.for_all (fun x -> x mod 2=0) input

Ora scriviamo con una cont seguito:

(* val evenk : int list -> (bool -> 'a) -> 'a *)
let evenk input cont =
  let result = even_list input in
  (cont result)

Si calcola il risultato vostra funzione, e passare resultto la continuazione ...