Ocaml продолжение прохождения стиля

Question

Я новичок в ocaml и пытаюсь написать функцию передачи продолжения, но совершенно не понимаю, какое значение мне нужно передать в дополнительный аргумент для k

. Например, я могу написать рекурсивную функцию, которая возвращает trueесли все элементы списка четные, в противном случае - false.

поэтому на CPS это похоже на

let rec even list = .... 

, я знаю, что мне нужно добавить один аргумент для передачи функции, например

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', которое обозначает промежуточную точку в функции умножения-сложения. Чтобы ваша evenk работала, вам нужно выделить хотя бы одно такое продолжение.

Надеюсь, это поможет.

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

Пример использования: "even [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 в продолжение ...