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

Question

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

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

Так что это нравится

let rec even list = .... 

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

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' который обозначает промежуточную точку в функции MultiPly-Add. Сделать ваш 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;;

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