Простейший пример обратных продолжений в Scheme без явной мутации

Question

Я написал небольшой интерпретатор Scheme на C # и понял, что так, как я его реализовал, было очень легко добавить поддержку правильных продолжений.

Итак, я добавил их ... но хочу "доказать", что они так, как я их добавил, верны.

Мой интерпретатор Scheme, однако, не поддерживает "изменяющее" состояние - все неизменно.

Так что было довольно легко написать модульный тест, чтобы раскрыть продолжения "вверх":

AssertEqual(Eval("(call/cc (lambda (k) (+ 56 (k 3))))"), 3);

Тем не менее, я также хочу написать модульный тест, который демонстрирует, что если продолжение «ускользает», то это тоже работает:

AssertEqual(Eval("(call/cc (lambda (k) k))", <some continuation>);

Но, конечно, вышесказанное будет просто проверять, что "я получил продолжение" ... не то чтобы это действительно действительное продолжение.

Все примеры, которые я могу найти, всегда заканчиваются использованием "set!" продемонстрировать сбежавшее продолжение.

Какой простейший пример Scheme, демонстрирующий правильную поддержку обратных обращений, не полагаясь на мутацию?

Можно ли использовать обратные продолжения без мутаций? Я начинаю подозревать, что это не так, потому что вы можете использовать его только для того, чтобы снова выполнить те же вычисления ... что бессмысленно, если нет побочных эффектов. Поэтому у Хаскелла нет продолжений?

Answer 1

Я не знаю, является ли это самым простым, но вот пример использования обратных продолжений без какого-либо вызова set! или подобного:

(apply
  (lambda (k i) (if (> i 5) i (k (list k (* 2 i)))))
  (call/cc (lambda (k) (list k 1))))

Это должно оценить 8.

Немного интереснее:

(apply
  (lambda (k i n) (if (= i 0) n (k (list k (- i 1) (* i n)))))
  (call/cc (lambda (k) (list k 6 1))))

, который вычисляет 6! (то есть, он должен быть равен 720).

Вы можете сделать то же самое с let*:

(let* ((ka (call/cc (lambda (k) `(,k 1)))) (k (car ka)) (a (cadr ka)))
      (if (< a 5) (k `(,k ,(* 2 a))) a))

(Человек, подсветка синтаксиса stackoverflow массово не работает на схеме.)

Answer 2

Я думаю, что вы правы - без мутаций обратные продолжения не делают ничего, чего не могут прямые продолжения.

Answer 3

Функциональные темы:

Вы можете использовать рекурсивный цикл для обновления состояния без мутаций. включая состояние следующего продолжения, которое будет называться. Теперь это сложнее, чем в других приведенных примерах, но все, что вам действительно нужно, это цикл thread-1 и main. Другой поток и функция «update» предназначены для того, чтобы показать, что продолжения можно использовать для более чем тривиального примера. Кроме того, чтобы этот пример работал, вам нужна реализация с именованным let. Это можно перевести в эквивалентную форму, созданную с помощью операторов define.

Пример:

(let* ((update (lambda (data) data))                ;is identity to keep simple for example
       (thread-1                                    
         (lambda (cc)                               ;cc is the calling continuation
           (let loop ((cc cc)(state 0))
             (printf "--doing stuff       state:~A~N" state)
             (loop (call/cc cc)(+ state 1)))))      ;this is where the exit hapens
       (thread-2
         (lambda (data)                             ;returns the procedure to be used as 
           (lambda (cc)                             ;thread with data bound
             (let loop ((cc cc)(data data)(state 0))
               (printf "--doing other stuff state:~A~N" state)
               (loop (call/cc cc)(update data)(+ state 1)))))))
  (let main ((cur thread-1)(idle (thread-2 '()))(state 0))
    (printf "doing main stuff    state:~A~N" state)
    (if (< state 6)
        (main (call/cc idle) cur (+ state 1)))))

Какие выходы

doing main stuff    state:0
--doing other stuff state:0
doing main stuff    state:1
--doing stuff       state:0
doing main stuff    state:2
--doing other stuff state:1
doing main stuff    state:3
--doing stuff       state:1
doing main stuff    state:4
--doing other stuff state:2
doing main stuff    state:5
--doing stuff       state:2
doing main stuff    state:6

Answer 4

Вот лучшее, что я придумал:

AssertEqual(Eval("((call/cc (lambda (k) k)) (lambda (x) 5))", 5);

Не удивительно, но это обратное продолжение, которое я затем "вызываю" с помощью фактической функции, которую я хочу вызвать, функции, которая возвращает число 5.

А, и я также придумал это как хороший пример для юнит-теста:

AssertEqual(Eval("((call/cc call/cc) (lambda (x) 5))", 5);

Я согласен с Джейкобом Б. - Я не думаю, что это так полезно без изменяемого состояния ... но все равно был бы заинтересован в контрпримере.