Конвертировать в CPS (стиль прохождения продолжения) - PullRequest
Новая
       29

Конвертировать в CPS (стиль прохождения продолжения)

8 голосов
/ 02 февраля 2012

Как мне преобразовать эти процедуры в Схеме в форму CPS? 

  1. (lambda (x y)
  ((x x) y))

  2. (lambda (x)
  (lambda (f)
    (f (lambda (y)
         (((x x) f) y))))

  3. ((lambda (x) (x x)
 (lambda (x) (x x))

* Это не домашняя работа!

Ответы [ 2 ]

24 голосов
/ 02 февраля 2012

См. Языки программирования, приложения и интерпретация , начиная примерно с главы 15. Глава 18 рассказывает о том, как сделать это автоматически, но если вы не знакомы с мыслью о выражении функции, которая выполняет "что делать" делай дальше ", вы, вероятно, захотите сначала попробовать упражнения для пальцев.

Не заставляйте кого-то делать это за вас: вы действительно захотите понять процесс и сможете сделать это вручную, независимо от Схемы или иным образом. Это особенно актуально в веб-программировании на асинхронном JavaScript, где у вас действительно нет другого выбора, кроме как выполнять преобразование.

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

Итак, если бы у нас была программа для вычисления гипотенузы треугольника: 

(define (hypo a b)
  (define (square x) (* x x))
  (define (add x y) (+ x y))

  (sqrt (add (square a)
             (square b))))

и если мы утверждаем, что единственными примитивными приложениями здесь являются *, + и sqrt, то все другие определения функций и вызовы функций должны быть переведены, например: 

(define (hypo/k a b k)
  (define (square/k x k)
    (k (* x x)))

  (define (add/k x y k)
    (k (+ x y)))

  (square/k a 
            (lambda (a^2)
              (square/k b
                       (lambda (b^2)
                         (add/k a^2 b^2
                                (lambda (a^2+b^2)
                                  (k (sqrt a^2+b^2)))))))))

;; a small test of the function.
(hypo/k 2 3 (lambda (result) (display result) (newline)))

Последнее выражение показывает, что вам в конечном итоге приходится вычислять «наизнанку» и что преобразование является повсеместным: все лямбды в исходной исходной программе в конечном итоге нуждаются в дополнительном аргументе, а все не примитивные приложения нуждаются в в качестве аргумента указать "что делать дальше".

. Внимательно посмотрите на раздел 17.2 процитированной книги: он охватывает это, а также 17.5, в котором говорится о том, почему вам нужно коснуться ВСЕХ лямбд в исходной программе, чтобы также работал регистр высшего порядка.

В качестве другого примера преобразования, примененного для случая более высокого порядка, допустим, что мы имеем: 

(define (twice f)
  (lambda (x) 
    (f (f x))))

Тогда перевод примерно такой: 

(define (twice/k f k1)
  (k1 (lambda ...)))

... потому что эта лямбда - это просто значение, которое можно передать в k1. Но, конечно, перевод должен проходить и через лямбду.

Сначала мы должны выполнить внутренний вызов f с помощью x (и помните, что все приложения, не являющиеся примитивными функциями, должны передавать соответствующее «что делать дальше!»): 

(define (twice/k f k1)
  (k1 (lambda (x k2)
        (f x (lambda (fx-val)
               ...)))))

... возьмите это значение и примените его снова к f ... 

(define (twice/k f k1)
  (k1 (lambda (x k2)
        (f x (lambda (fx-val)
               (f fx-val ...))))))

... и, наконец, вернуть это значение в k2: 

(define (twice/k f k1)
  (k1 (lambda (x k2)
        (f x (lambda (fx-val)
               (f fx-val k2))))))

;; test.  Essentially, ((twice square) 7)
(define (square/k x k) (k (* x x)))
(twice/k square/k 
         (lambda (squaresquare)
           (squaresquare 7
                         (lambda (seven^4) 
                           (display seven^4)
                           (newline)))))
0 голосов
/ 13 декабря 2015

Вам нужно выбрать, на какой уровень вы хотите / хотите CPS-преобразовать.

Если вы просто хотите (lambda (x y) ((x x) y)) в стиле с продолжением (CP), то (lambda (k x y) (k ((x x) y))) подойдет.

Если вы хотите, чтобы его аргументы обрабатывались также как в стиле CP, тогда вам нужно немного больше.

Предположим сначала, что только второй аргумент (y) находится в форме CP и, таким образом, действительно является чем-то вроде (lambda (k) (k y0)) и поэтому должен вызываться с некоторым продолжением для извлеченияего значение, тогда вам понадобится: 

(lambda (k x y)
  (y (lambda (y0) (k ((x x) y0)) )) )

Наконец, предположим, что и x, и y в стиле CP.Тогда вам понадобится что-то вроде: 

(lambda (k x y)
  (x (lambda (x0)
       (x (lambda (x1)
            (y (lambda (y0)
                 (k ((x0 x1) y0)) ))))

Здесь вы можете изменить порядок вызовов на x и y.Или, может быть, вам нужен только один вызов x, потому что вы знаете, что его значение не зависит от продолжения, с которым он вызывается.Например: 

(lambda (k x y)
  (y (lambda (y0)
       (x (lambda (x0)
            (k ((x0 x0) y0)) ))))

Другие выражения, о которых вы спрашивали, могут быть преобразованы аналогичным образом.

...