Как мы можем преобразовать программу, использующую `call/cc`, в программу, использующую функции, написанные на CPS?

Язык программирования Scheme говорит

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

Каковы общие приемы

  • преобразовать программу, использующую call/cc, в программу, использующую функции, написанные на CPS

  • преобразовать в обратном направлении?


continuations scheme continuation-passing callcc
person Community    schedule 10.08.2019    source источник
comment
Впервые я узнал о преобразовании CPS из этих слайдов churchturing.org/y/90-min- scc.pdf — преобразует исходный код в лямбда-исчислении + call/cc в простое лямбда-исчисление. Это достигается путем добавления параметра продолжения к каждой процедуре и передачи каждого вызова процедуры в продолжение.   -  person rain1    schedule 10.08.2019
comment
цель состоит в том, чтобы преобразовать любую программу в CPS. тогда call/cc становится тривиальным в преобразованной программе. -- (call/cc (lambda (k) ...)) ==› (call/cc& (lambda (k) ...) k) == ((lambda (k) ...) k). то есть (define (call/cc& lam k) (lam k)) - это определение. это простая история; Я думаю, что было несколько недавних сообщений о реализации call/cc в CPS, в схеме, попробуйте поискать их.   -  person Will Ness    schedule 10.08.2019
comment
на самом деле, это должно было быть (call/cc (lambda (k) ...)) ==› (call/cc& (lambda (k c) ...) c) == ((lambda (k c) ...) c c). то есть (define (call/cc& lam c) (lam c c)) (по схеме, где продолжение всегда передается последним аргументом (что, конечно, произвольный выбор)).   -  person Will Ness    schedule 12.08.2019

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете узнать, как реализовать преобразование передачи продолжения, здесь http://matt.might.net/articles/cps-conversion/ или из книги Compiling With Continuations автора Appel.

Обратное преобразование сложнее и имеет меньше практического применения, но о нем есть статья: Назад к стилю Direct (1994) Оливье Дэнви

person rain1    schedule 11.08.2019