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

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

4 голосов
/ 07 марта 2011

Я изучаю 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 или других функциональных языках вполне подходят.

1 Ответ

9 голосов
/ 07 марта 2011

Преобразование в стиле продолжения может быть частичным или полным. Обычно вы работаете с системой, в которой определенные примитивы (+, - и т. Д.) Застряли в не-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))))))
...