Как использовать продолжения в схеме? - PullRequest
Новая
       67

Как использовать продолжения в схеме?

0 голосов
/ 22 апреля 2019

Я пытаюсь понять оператор call / cc в схеме. Я планирую реализовать это в моем JavaScript. Это мой простой код: 

(letrec ((x 0)
         (f (lambda (r)
                (set! x r)
                (display (r 20))
                (display "10"))))
   (display (call/cc f))
   (x "30"))

Мне трудно печатать 20, затем 30, а затем 10. Но это создает бесконечный цикл (он продолжает печатать 30). Как должен выглядеть этот код для отображения 3 значений, вызова для отображения 3 раза?

Можно ли создавать циклы, которые не потребляют стек с продолжениями?

Я нашел пример переполнения стека , но этот не работает совсем: 

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

замораживает интерпретатор guile со 100% процессором и выглядит ожидающим ввода.

1 Ответ

0 голосов
/ 23 апреля 2019

Преобразуете ли вы реализацию пользовательского кода в стиль передачи продолжения?В таком случае это легко peasy.call/cc это: 

(define (call/cc& f& continuation)
  (define (exit& value actual-continuation)
    (continuation value))
  (f& exit& continuation))

Глядя на ваш первый код, я думаю, что это выглядит примерно так: 

((lambda (x k)
   ((lambda (f k)
      (call/cc& f (lambda (v) ; continuation a
                    (display& v (lambda (_) ; continuation b
                                  (x "30" k))))))
    (lambda (r k)
      (set!& x r (lambda (_) ; continuation c
                   (r 20 (lambda (v) ; continuation d
                           (display& v (lambda (_) ; continuation e
                                         (display& "10" k))))))))
    k)
   0
   halt)

Вот что происходит:

  • Мы делаем x и f
  • call/cc& звонков f
  • x установлен на r (продолжение а)
  • r получаетвызывается с 20 как значение
  • продолжение c игнорируется, вместо этого отображается продолжение a с 20
  • 20, затем продолжение b вызывается
  • b с x«30»
  • продолжение k игнорируется, вместо этого вызывается продолжение a с 30
  • 30, затем вызывается продолжение b
  • перейти к вызовам b xс «30» на 3 строки вверх и продолжайте

Поэтому выведите «20», тогда «30» навсегда будет правильным результатом для этого кода. Важно отметить, что он никогда не будет display "10", поскольку он вызывает r и передает продолжение, но оно обходится до call/cc оригинального продолжения, которое является продолжениемВступление а.

Что касается реализаций.Раньше для всех реализаций Scheme было обычным делом просто преобразовывать код в стиль передачи продолжения, но сегодня более распространено делать только те части, которые требуются.Например.Ikarus не выполняет CPS, но для того, чтобы call/cc работал, он должен делать это до следующего приглашения на продолжение.

Вероятно, лучше смотреть на call/cc вначале без мутаций.например.

(+ 2 (call/cc (lambda (exit)
                (+ 3 (* 5 (exit 11))))))

Теперь это превращается в: 

(call/cc& (lambda (exit k)
            (exit 11 (lambda (v)
                       (*& 5 v (lambda (v)
                                 (+& 3 v k))))))
          (lambda (v)
            (+& 2 v repl-display)))

Теперь мы знаем, что exit вызывается, и, таким образом, все это превращается в: 

((lambda (v) (+& 2 v repl-display)) 11)

Что отображает13.Теперь наличие продолжения в качестве последнего аргумента выглядит хорошо на бумаге.В реализации, которая хочет поддерживать varargs, вероятно, лучше, чтобы продолжение было первым аргументом.

Все продолжения являются хвостовыми вызовами, и поэтому стек никогда не увеличивается.Фактически, если используется полный CPS, вам никогда не придется возвращаться.Все интересное всегда передается до следующего вызова, пока программа не остановится.

...