Продолжение прохождения стиля - функция композиции

Question

Я изучаю CPS с помощью Racket, и мне удалось написать эти функции:

;lift a regular single-arg function into CPS
(define (lift/k f)
  (lambda (x k)
    (k (f x))))

;compose two CPS functions
(define (compose/k f g)
  (lambda (x k)
    (g x (lambda (y)
           (f y k)))))

Кажется, они работают правильно

(define (is-two/k x k)
  (k (= x 2)))
(define is-not-two/k (compose/k (lift/k not) is-two/k))
(is-not-two/k 3 display)
(is-not-two/k 2 display)

#t#f

Мне интересно, если эти функции все еще "истинные CPS". Я испортил "истинное" прохождение продолжения с этими функциями? Кошерно ли использовать методы составления функций в CPS? Это поощряется? Или это будет считаться "компромиссом" для этого? Есть ли более CPS-й способ сделать это?

Да, я знаю, я только что задал 5 вопросов, но основная идея, лежащая в их основе (которую я не уверен, что я правильно понимаю), та же самая. Объяснения на других языках Lisps, Haskell, Erlang или других функциональных языках вполне подходят.

Answer 1

Преобразование в стиле продолжения может быть частичным или полным. Обычно вы работаете с системой, в которой определенные примитивы (+, - и т. Д.) Застряли в не-cps-стране. К счастью, CPS работает в любом случае.

Шаги в CPSing:

• Выберите, какие функции будут примитивными.
• CPS-преобразование, так что все не примитивные функции (включая продолжения) вызываются только в хвостовой позиции.

Итак, в вашем коде ваш 'lift/k', по сути, рассматривает данную функцию как примитивную: обратите внимание, что тело файла lift / k вызывает 'f' в нехвостовой позиции. Если вы не хотите рассматривать поднятую функцию как примитив, вы должны войти и переписать ее явно.

Ваша функция 'compose' создает две функции CPSed, но сама не находится в CPS (то есть вы предполагаете, что 'compose' является примитивной. Вы, вероятно, хотите ее CPS. Обратите внимание, что, поскольку она просто сразу возвращает значение, это это просто:

;compose two CPS functions
(define (compose/k f g k)
  (k (lambda (x k)
       (g x (lambda (y)
              (f y k))))))