Ocaml la continuación del estilo que pasa

Question

Soy nuevo en ocaml y tratando de escribir una continuación pasando función de estilo pero bastante confusa qué valor tengo que pasar a la discusión adicional sobre los k

por ejemplo, puedo escribir una función recursiva que devuelve verdadero si todos los elementos de la lista son pares, de lo contrario son falsos.

por lo que su gusto

let rec even list = .... 

en CPS, sé que tengo que añadir un argumento para aprobar la función así como

let rec evenk list k = .... 

pero no tengo ni idea de cómo hacer frente a este ky ¿Cómo funciona exactamente

por ejemplo para esta función incluso, el entorno parece

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

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

Answer 1

La continuación k es una función que toma el resultado de evenk y realiza "el resto del cálculo" y produce la "respuesta". Qué tipo tiene la respuesta y qué quiere decir con "el resto de la computación" depende de lo que esté usando CPS para. CPS generalmente no es un fin en sí mismo, pero se hace con algún propósito en mente. Por ejemplo, en el formulario CPS es muy fácil implementar operadores de control o optimizar las llamadas finales. Sin saber lo que intentas lograr, es difícil responder a tu pregunta.

Por lo que vale, si simplemente está tratando de convertir del estilo directo al estilo de continuación de paso, y lo único que le importa es el valor de la respuesta, pasando la función de identidad ya que la continuación es correcta.

Un buen paso siguiente sería implementar evenk usando CPS. Haré un ejemplo más simple. Si tengo la función de estilo directo

let muladd x i n = x + i * n 

y si asumo primitivas CPS mulk y addk, puedo escribir

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

y verá que el mulptiplication se hace primero, entonces "continúa" con k', que hace el complemento, y finalmente ese continues con k, que regresa a la persona que llama. La idea clave es que dentro del cuerpo de muladdk asigné una nueva continuación k' que representa un punto intermedio en la función de adición múltiple. Para que su trabajo evenk tenga que asignar al menos una de esas continuación.

Espero que esto ayude.

Answer 2

Dado que tiene la invocación de evenk correcta (con la función de identidad - convirtiendo efectivamente el estilo de paso de continuación al estilo normal), asumo que la dificultad está en definir evenk.

k es la función de continuación que representa el resto del cálculo y produce un valor final, como dijo Norman.Entonces, lo que necesita hacer es calcular el resultado de v de even y pasar ese resultado a k, devolviendo k v en lugar de solo v.

Answer 3

Siempre que he jugado con CPS, lo que se pasa a la continuación es lo que normalmente devolvería a la persona que llama. En este caso simple, un buen "lubricante intuitivo" es nombrar la continuación "retorno".

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;; 

Ejemplo de uso: "even [2; 4; 6; 8] id ;;".

Answer 4

Quiere dar como entrada el resultado de su función como si no estuviera escrito con el estilo de paso de continuación.

Aquí es su función que comprueba si una lista tiene solamente enteros pares:

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

Ahora vamos a escribir con una continuación cont:

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

Usted calcular el resultado de su función, y pase result a la continuación ...