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

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

Итак, я добавил их... но хочу «доказать», что то, как я их добавил, правильно.

Однако мой интерпретатор схемы не поддерживает «мутирующее» состояние — все неизменно.

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

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

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

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

Но, конечно, приведенное выше просто проверит, что «у меня есть продолжение»… а не то, что это на самом деле действительное продолжение.

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

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

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


functional-programming haskell continuations scheme
person Paul Hollingsworth    schedule 11.06.2009    source источник

Ответы (4)


arrow_upward
8
arrow_downward

Я не знаю, самый ли это простой, но вот пример использования обратных продолжений без какого-либо вызова 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 сильно не работает по схеме.)

person Daniel Martin    schedule 11.06.2009
comment
Эй, это аккуратно! Я думаю... Мне нужно понять, что же он теперь делает!!! ;-) - person Paul Hollingsworth; 12.06.2009
comment
ОК, теперь я понял... Это очень умно! И это демонстрирует фактическое использование: зацикливание без явной рекурсии. - person Paul Hollingsworth; 12.06.2009
comment
Правильно. Конечно, любой, кто знаком с комбинатором Y, скажет вам, что для этого не нужны продолжения, но, может быть, я смогу придумать что-то не столь очевидное. - person Daniel Martin; 12.06.2009
comment
да, я узнал все о комбинаторе Y - на самом деле, одним из моих первых тестов был факториал, в котором использовался комбинатор Y. Завтра мне придется попробовать ваш пример, чтобы увидеть, работает ли мой интерпретатор... - person Paul Hollingsworth; 12.06.2009
comment
о, и только что обнаружил, что они действительно очень связаны: Вычисления/продолжения.html#fix-callcc - person Paul Hollingsworth; 12.06.2009
comment
Вы будете рады узнать, что ваш тест работает! [Тест] public void TestFactorialBackwardsCallCC() { // Спасибо Дэниелу Мартину: // stackoverflow.com/questions/983776/ // Вычисление 6! без явной рекурсии, а используя продолжение e.StackEval((apply (lambda (kin) (if (eq? i 0) n (k (list k (- i 1) (* in))))) (call/cc (лямбда (k) (список k 6 1)))), 720); } - person Paul Hollingsworth; 12.06.2009

arrow_upward
2
arrow_downward

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

person Jacob B    schedule 11.06.2009

arrow_upward
0
arrow_downward

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

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

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

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

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

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

person Paul Hollingsworth    schedule 11.06.2009

arrow_upward
0
arrow_downward

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

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

Пример:

(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
person Anandamide    schedule 24.04.2016