Аргумент функции call/cc написан в CPS?

No.

Функции в стиле CPS ожидают других нормальных функций в качестве своих аргументов и могут вызывать их в хвостовой позиции. Эти функции ошибочно называются «продолжениями» на языке Схемы. Я предпочитаю "непредвиденные обстоятельства", чтобы устранить двусмысленность.

Функция аргумента call/cc ожидает в качестве аргумента фактическое неограниченное продолжение. Это фактическое продолжение не является функцией. Вызов его со значением возвращает это значение в контекст возврата этого продолжения, который, таким образом, сохраняется вместе с продолжением — неслыханный подвиг w.r.t. простые функции.

Вызванная хвостом функция возвращает свой результат в контекст вызывающей функции вызывающей функции.

Вызываемое продолжение возвращает предоставленное значение в контекст создающего call/cc вызова. Таким образом, это не функция. Таким образом, функция, использующая его, не написана в CPS.

Во-первых, что такое ЦПС? Стиль передачи продолжения — это способ компиляции программы, основанной на продолжениях (т. е. использующей оператор call/cc), в целевой язык, который не поддерживает продолжение, но поддерживает лексические замыкания и хвостовые вызовы (или некое подобие хвостовых вызовов, например возможность отката стека, когда он становится слишком глубоким с фактическими кадрами вызова).

Программа, преобразованная с помощью CPS, сама по себе не написана в стиле передачи продолжения. Это не должно быть; у него есть оператор call/cc, предоставляемый транслятором CPS, который дает ему доступ к текущему продолжению, где бы оно ни потребовалось.

Поскольку CPS в основном представляет собой преобразование источника в источник, его иллюстрируют и преподают с использованием написанного от руки явного CPS. Довольно часто для этого используется язык Scheme. В языке Scheme уже есть call/cc, но при экспериментировании с явно написанным от руки CPS нам приходится делать вид, что call/cc не существует. В парадигме CPS мы можем, конечно, предоставить оператор с именем my-call/cc, который построен на нашей CPS и не имеет ничего общего с базовой схемой call/cc.

В реализации языка, скомпилированного CPS, каждая процедура имеет аргумент продолжения (за необходимым исключением процедур в библиотеке основного языка). Функциональный аргумент call/cc, функция, получающая продолжение, не является исключением. Будучи процедурой в мире CPS, она должна иметь параметр продолжения, чтобы быть совместимой с вызовами процедур, передающими этот аргумент.

Процедура аргумента call/cc фактически может использовать этот аргумент продолжения и ссылку самый первый пример из Википедии демонстрирует это. Вот копия этого примера, в котором я переименовал параметр return в c, чтобы избежать путаницы:

(define (f c)       ;; function used for capturing continuation
  (c 2)             ;; invoke continuation
  3)                ;; if continuation returns, return 3.

(display (f (lambda (x) x))) ; displays 3

(display (call/cc f)) ; displays 2

Аргумент c процедуры f не обязательно должен быть продолжением; в первом вызове это просто фиктивная функция (lambda (x) x). f вызывает его, и эта функция возвращается, и тогда управление переходит к 3.

В CPS у f есть скрытый аргумент, который мы можем выявить с помощью написанного от руки CPS:

(define (f c k)
  (c 2 k)
  (k 3 k))

Когда возвращается 3, это происходит потому, что вызывается скрытое продолжение. Поскольку программа может это сделать, f должна иметь ее.

Обратите внимание, что c и k — разные продолжения! Возможно, именно здесь возникает путаница. Продолжение c является текущим продолжением вызывающей стороны, которое передается call/cc и является частью явной семантики call/cc. k является скрытым, добавленным преобразователем CPS. Это собственное продолжение f. У каждой функции есть своя функция в мире, преобразованном CPS. Согласно парадигме CPS, если f хочет вернуться, он вызывает k (именно поэтому я переименовал return в c). Если f желает продолжить приостановленный call/cc, он вызывает c.

Кстати, при автоматическом CPS k не будет буквально называться k, потому что это было бы негигиенично: программы могут свободно привязывать символ k. Это должен быть символ, сгенерированный машиной (gensym), или подвергнуть какой-либо другой форме гигиенической обработки.

Единственная функция, которая должна быть специально обработана в CPS, чтобы у них не было аргументов продолжения, — это библиотечные функции на основном языке/VM, которые должны быть доступны для языка, переведенного CPS. Когда язык, переведенный CPS, вызывает (display obj) для печати объекта, эта функция display должна быть либо переименованной оболочкой, которая может принимать аргумент продолжения (а затем игнорировать его и вызывать настоящую функцию display без него), либо вызовом display должен быть специально обработан транслятором CPS, чтобы опустить аргумент продолжения.

Наконец, почему CPS может реализовывать продолжения на языке/VM, которые изначально не предоставляют их? Причина в том, что все вызовы функций в CPS-преобразованных программах являются хвостовыми вызовами и поэтому никогда не возвращаются. Сложная часть реализации продолжений — захват всего стека вызовов, чтобы при возобновлении продолжения оно могло вернуться. Такая функция может быть добавлена ​​только на уровне языковой реализации. В 1970-х InterLisp использовал "стеки спагетти", чтобы реализовать это: фреймы стека представляют собой объекты кучи со сбором мусора, указывающие на родительские фреймы. Но что, если функции не возвращают значения? Тогда необходимость добавлять в реализацию стек спагетти отпадает. Обратите внимание, что стек спагетти никуда не делся: у нас есть нечто эквивалентное CPS, а именно цепочки захваченных лексических окружений. Продолжение — это лямбда, которая захватывает параметр k окружающей процедуры, которая сама является лямбдой, захватившей параметр k своего родителя, ... и т. д.: это цепочка окружений, похожая на стек кадры, в которых скрытые параметры k являются указателями кадров. Но базовый язык уже дал нам лексически захваченные лямбда-выражения; мы только что использовали эти лямбда-выражения, чтобы де-факто представить стек продолжения спагетти, и поэтому нам не нужно было спускаться на уровень реализации, чтобы что-то сделать.