OCaml style de passage de continuation

Question

Je suis nouveau à OCaml et tryin écrire une fonction de style qui passe la continuation mais assez confus quelle valeur je dois passer dans k argument supplémentaire sur

par exemple, je peux écrire une fonction récursive qui renvoie true si tous les éléments de la liste est encore, sinon faux.

est comme

let rec even list = .... 

sur CPS, je sais que je dois ajouter un argument pour passer la fonction donc comme

let rec evenk list k = .... 

mais je n'ai aucune idée comment faire face à ce k et comment cela fonctionne exactement

par exemple pour cette fonction même, ressemble comme environnement

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

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

Answer 1

Le k de continuation est une fonction qui prend le résultat de evenk et réalise « le reste du calcul » et produit la « réponse ». Quel type la réponse a et ce que vous entendez par « le reste du calcul » dépend de ce que vous utilisez CPS pour . CPS est généralement pas une fin en soi, mais se fait avec un but à l'esprit. Par exemple, sous forme CPS, il est très facile à mettre en œuvre les opérateurs de contrôle ou d'optimiser les appels de la queue. Sans savoir ce que vous essayez d'accomplir, il est difficile de répondre à votre question.

Pour ce qu'il vaut la peine, si vous essayez simplement de convertir style direct au style de passage de continuation, et tout ce que vous aimez est la valeur sur de la réponse, en passant la fonction d'identité comme la continuation est à peu près juste.

Une bonne étape suivante consisterait à mettre en œuvre à l'aide evenk CPS. Je vais faire un exemple plus simple. Si j'ai la fonction de style direct

let muladd x i n = x + i * n

et si je suppose que les primitives de la SCP mulk et addk, je peux écrire

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

Et vous verrez que le mulptiplication est fait en premier, il « continue » avec k', qui fait l'ajouter, et enfin que continues avec k, ce qui revient à l'appelant. L'idée principale est que, dans le corps de muladdk I donné une nouvelle continuation k' qui représente un point intermédiaire de la fonction de multiplication-addition. Pour faire votre travail de evenk vous devrez allouer au moins une continuation.

J'espère que cette aide.

Answer 2

Chaque fois que je l'ai joué avec CPS, la chose est passé à la poursuite est juste la chose que vous reviendriez normalement à l'appelant. Dans ce cas simple, un joli « lubrifiant intuition » est de nommer la suite « retour ».

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

Exemple d'utilisation:. "Même [2; 4; 6; 8] id ;;"

Answer 3

Puisque vous avez l'invocation de evenk correcte (avec la fonction d'identité - convertir efficacement le passage de continuation de style plutôt le style normal), je suppose que la difficulté réside dans la définition evenk

.

k est la fonction de poursuite représente le reste du calcul et produire une valeur finale, en tant que dit Norman. Donc, ce que vous devez faire est de calculer le résultat de v de even et passer ce résultat à k, retour k v plutôt que v.

Answer 4

Vous voulez donner en entrée le résultat de votre fonction comme si elle n'a pas été écrit avec un style qui passe de continuation.

Voici votre fonction qui teste si une liste a uniquement des nombres entiers même:

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

Maintenant, nous allons l'écrire avec une suite cont:

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

Vous calculez le résultat de votre fonction, et passez resultto la suite ...