OCAML継続パススタイル

Question

私はOCAMLと継続的なパススタイル関数を書くことを試みますが、Kの追加の引数に渡すために必要な価値を非常に混乱させました

たとえば、リストのすべての要素が偶数である場合、trueを返す再帰関数を書くことができます。

だからそれは似ています

let rec even list = .... 

CPSでは、関数をパスするために1つの引数を追加する必要があることを知っています。

let rec evenk list k = .... 

しかし、私はこのKに対処する方法と、これが正確にどのように機能するのかわからない

たとえば、この均等な機能の場合、環境は次のように見えます

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

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

Answer 1

継続 k 結果を取る関数です evenk 「計算の残りの部分」を実行し、「答え」を生成します。答えがどのようなタイプで、「残りの計算」が意味するものは、CPSを使用しているものによって異なります にとって. 。 CPSは一般にそれ自体が目的ではありませんが、何らかの目的を念頭に置いて行われます。たとえば、CPSの形では、制御オペレーターを実装したり、テールコールを最適化したりするのは非常に簡単です。あなたが何を達成しようとしているのか分からずに、あなたの質問に答えるのは難しいです。

単に直接的なスタイルから継続パススタイルに変換しようとしている場合、それが価値がある場合、あなたが気にするのは答えの価値だけで、継続がほぼ正しいのでアイデンティティ関数を渡すことだけです。

良い次のステップは、実装することです evenk CPSを使用します。簡単な例をやります。ダイレクトスタイルの関数がある場合

let muladd x i n = x + i * n

そして、CPSプリミティブを想定している場合 mulk と addk, 、書くことができます

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

そして、あなたは最初にマルプティプレーションが行われ、それからそれが「続き」であることがわかります k', 、これが追加され、最後にそれがあります continues と k, 、発信者に戻ります。重要なアイデアは、その体内でです muladdk 私は新鮮な継続を割り当てました k' これは、マルチプリADD関数の中間点を表します。あなたを作るために evenk 作業少なくとも1つのそのような継続を割り当てる必要があります。

これが役立つことを願っています。

Answer 2

CPSでプレイしたときはいつでも、継続に渡されたものは、通常、発信者に戻るものです。この単純なケースでは、優れた「直観潤滑剤」は、継続「リターン」に名前を付けることです。

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

使用法の例： "偶数[2; 4; 6; 8] id ;;"。

Answer 3

の呼び出しがあるので evenk 正しい（アイデンティティ関数を使用 - 継続パススタイルを通常のスタイルに効果的に変換する）、私は難易度が定義することであると仮定します evenk.

k ノーマンが言ったように、計算の残りの部分を表し、最終的な値を生成する継続関数です。だから、あなたがする必要があることはの結果を計算することです v の even その結果を渡します k, 、戻ってきます k v ただではなく v.

Answer 4

継続的なパススタイルで書かれていないかのように、あなたの関数の結果を入力として与えたいと思います。

リストが整数のみを持っているかどうかをテストする関数は次のとおりです。

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

それでは、それを継続的に書きましょう cont:

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

結果を計算し、渡します result継続に...