Стиль передачи продолжения Ocaml
Я плохо знаком с 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 *)
3 ответа
Продолжение 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 ', который выполняет сложение, и, наконец, продолжается с помощью k , который возвращается вызывающему. Ключевая идея состоит в том, что в теле muladdk я выделил новое продолжение k ', которое обозначает промежуточную точку в функции умножения-сложения. Чтобы ваш эвенк заработал, вам нужно выделить хотя бы одно такое продолжение.
Надеюсь, это поможет.
Так как вызов evenk правильный (с функцией идентификации - эффективное преобразование стиля передачи продолжения обратно в нормальный стиль), я предполагаю, что сложность составляет в определении эвенка .
k - функция продолжения, представляющая оставшуюся часть вычислений и производящую окончательное значение, как сказал Норман. Итак, что вам нужно сделать, это вычислить результат v of даже и передать этот результат в k , вернув kv , а не просто против .
Всякий раз, когда я играл с 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 ;;».