Стиль прохождения продолжения - композиция функций

Я изучаю 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-y способ сделать это?

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


function-composition haskell lisp continuation-passing racket
person Dan Burton    schedule 07.03.2011    source источник

Ответы (1)


arrow_upward
9
arrow_downward

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

Шаги в CPSing:

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

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

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

;compose two CPS functions
(define (compose/k f g k)
  (k (lambda (x k)
       (g x (lambda (y)
              (f y k))))))
person John Clements    schedule 07.03.2011