LINUX.ORG.RU

Вопрос по Continuations

 ,


1

3

Всем привет!
Продолжаю пилить свою r5rs, дошло дело до continuations.
Пишу на java, поэтому выбирать средства для манипуляций со стеком особо не приходится: есть только Exceptions.

Соответственно, делаю примерно так, как сделано в Kawa:
https://www.gnu.org/software/kawa/internals/complications.html

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

Например, этот кусок кода работает правильно (взят с Вики):

(define (f return)
  (return 2)
  3)

(display (f (lambda (x) x))) ; displays 3

(display (call-with-current-continuation f)) ; displays 2

Далее, это тоже работает:
(define (cc) (call-with-current-continuation (lambda (cc) (cc cc))))

(cc) ;; => #<continuation>

А вот это уже не работает:
(define (cc) (call-with-current-continuation (lambda (cc) (cc cc))))
((cc) display) ;; должно выводить #<procedure:display>

((cc) display) кидает CalledContinuation exception.
И вот тут я не понимаю, что я должен с этим делать.
Kawa пишет:


If it is “our” continuation, return the value passed to the continuation; otherwise re-throw it up the stack until we get a matching handler.


Что значит «our»?
Даже если я оберну ту строчку, в которой кидается CalledContinuation в try-catch и буду ловить CalledContinuation, то что мне потм с ним делать?

PS: ying-yang puzzle тоже не работает: выводит первые два символа, потом тоже кидает CalledContinuation, с которым тоже не знаю что делать.

★★★★★

try ты пишешь вместо '(call-with-c...c...)',

Procedure proc = (Procedure) arg1; // это твоя (lambda (cc) (cc cc))
Continuation cont = new Continuation (); // our continuation
try {                           //
      return proc.apply1(cont); // это call-with-c-c
    }                           // тут ты в лямбду передаёшь cc оно же cont
catch (CalledContinuation ex)
  {
    if (ex.continuation != cont) // проверяешь, если киданутое continuation -- то самое, которое ты пережовал в лямбду
// our значит == cont, которое создано перед try
          throw ex;  // Если нет, кидаешь дальше.
    return ex.value; // Если да -- возвращаешь значение
  }
finally
  {
    cont.mark_invalid();
  }

Bad_ptr ★★★★ ()
Последнее исправление: Bad_ptr (всего исправлений: 2)
Ответ на: комментарий от Bad_ptr

Ну этот код я понимаю, все просто и вполне очевидно.
Проблема в том, что оно не работает (у меня) в некоторых случаях.
А именно, например, ying yang puzzle: ex.value (в try-catch блоке) может вернуть не значение, а другой continuation.
Этот continuation спокойно возвращается в место вызова (evaluator) и возвращается как результат вычислений.
Правильно ли это?

kovrik ★★★★★ ()
Ответ на: комментарий от Bad_ptr

Немного перефразирую предыдущий пост:

ying-yang puzzle:

>(let* ((yin
         ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
    (yin yang))

@*
core.procedures.continuations.CalledContinuation
	at core.procedures.continuations.Continuation.apply(Continuation.java:24)
	at core.procedures.continuations.Continuation.apply(Continuation.java:7)
	at core.evaluator.Evaluator.evlis(Evaluator.java:143)
	at core.evaluator.Evaluator.evalIter(Evaluator.java:51)
 	at core.evaluator.Evaluator.eval(Evaluator.java:31)
	at core.Repl.repl(Repl.java:80)


Т.е. первые два символа выводятся правильно, потом ex.value возвращает Continuation (который extends Procedure, как и в Kawa), evaluator пытается его выполнить, он кидает CalledContinuation exception.

kovrik ★★★★★ ()

Сейчас смайлодаун придёт и всё объяснит.

anonymous ()
Ответ на: комментарий от Bad_ptr

ying-yang puzzle не работает в kawa из-за того, что оно не знает про let*. Может оно как-то подключается отдельно, хз, я с Кавой почти не работал.
В Racket/Guile/Chicken все работает.

Но, попробовал переделать puzzle вот так:

(define (yin   cc) (display #\@) cc (call/cc (lambda (c) c)))
(define (yang  cc) (display #\*) cc (call/cc (lambda (c) c)))
(yin yang) ;; => @#<continuation>

Результат похож на мой (для оригинального ying yang).
Если такой же (переделанный) вариант выполняю у себя - результат совпадает.

В общем, не до конца понимаю:
1) то ли это ограничения continuations, если их через exception'ы делать
2) то ли это у меня криво сделаны continuations
3) то ли у меня что-то другое неправильно сделано (например, let*) и проявляется в таких редких случаях

kovrik ★★★★★ ()
Ответ на: комментарий от Bad_ptr

Лучше даже забыть про ying yang и рассмотреть простой вариант:

(define (cc) (call-with-current-continuation (lambda (cc) (cc cc))))

((cc) display) 

;; =>
CalledContinuation{value=#<procedure:display>, continuation=#<continuation>}
	at core.procedures.continuations.Continuation.apply(Continuation.java:24)
> 	at core.procedures.continuations.Continuation.apply(Continuation.java:7)
	at core.evaluator.Evaluator.evlis(Evaluator.java:142)
	at core.evaluator.Evaluator.evalIter(Evaluator.java:53)
	at core.evaluator.Evaluator.eval(Evaluator.java:27)
	at core.Repl.repl(Repl.java:80)
А должно выводить:
#<procedure:display>

kovrik ★★★★★ ()
Ответ на: комментарий от kovrik

оно не знает про let*

А про просто let оно знает? Если да, то сделай вложенный let.

А должно выводить: #<procedure:display>

Так лови этот эксепшн на самом высоком уровне и выводи, не?)

Bad_ptr ★★★★ ()
Ответ на: комментарий от kovrik

Вот результат kawa'ы

#|kawa:3|# (let ((yin((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c)))))
#|.....4|# (let ((yang ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
#|.....5|# (yin yang)))
kawa.lang.GenericError: implementation restriction: continuation can only be used once
	at kawa.lang.Continuation.apply(Continuation.java:24)
	at gnu.mapping.CallContext.runUntilDone(CallContext.java:227)
	at gnu.expr.ModuleExp.evalModule2(ModuleExp.java:350)
	at gnu.expr.ModuleExp.evalModule(ModuleExp.java:212)
	at kawa.Shell.run(Shell.java:283)
	at kawa.Shell.run(Shell.java:196)
	at kawa.Shell.run(Shell.java:183)
	at kawa.repl.processArgs(repl.java:714)
	at kawa.repl.main(repl.java:820)
@*
#|kawa:6|#
Bad_ptr ★★★★ ()
Последнее исправление: Bad_ptr (всего исправлений: 1)

((cc) display) кидает CalledContinuation exception.

В общем, у тебя продолжения одноразовые. Повторно нельзя выполнять. Думаю, в Java многоразовые и не получится сделать, кроме как интерпретатором.

monk ★★★★★ ()
Ответ на: комментарий от Legioner

Надо кусок после continuation-а обернуть в Runnable и вызывать его сколько угодно раз.

Так этот кусок неограничен. В kawa заменили continuation исключением. То есть его можно вызвать только изнутри callcc.

А как на Java реализовать

cont c1;
public Object g(cont c) {
  c1 = c;
}
callcc(g);
....
// 100500 строк кода
....
if(cond1)
  c1(0); // внезапно 100500 строк кода выполнились заново
...
// ещё код
...
if(cond2)
  c1(0); // и снова выполнились 100500 строк кода
я не представляю. Да, с1(0) должно быть можно вызвать из из другой функции и вообще из другого объекта. При этом должен повториться весь код от вызова callcc(g) до места вызова с1(0).

Если это возможно, то в Java можно сделать goto.

monk ★★★★★ ()
Ответ на: комментарий от monk
Runnable c1;
public void g(Runnable c) {
  c1 = c;
}
Runnable tmp1 = () -> {
  ....
  // 100500 строк кода
  ....
  if(cond1)
    c1.run(); // внезапно 100500 строк кода выполнились заново
  ...
  // ещё код
  ...
  if(cond2)
    c1.run(); // и снова выполнились 100500 строк кода
};
g(tmp1); // callcc(g);
tmp1();

т.е. весь кусок кода после callcc заключается в замыкание. callcc вызывается с указателем на это замыкание и потом оно само вызывается.

Legioner ★★★★★ ()
Последнее исправление: Legioner (всего исправлений: 2)
Ответ на: комментарий от Legioner

Нет. Не забывай, что продолжение имеет собственный стек. В случае с замыканием после c1.run() возврат произойдёт в то же замыкание, а в случае продолжения --- туда, откуда был вызван код с call/cc.

Jini ★★ ()

Без копирования стека полноценных продолжений не получится. По твоей ссылке прямо так и написано:

Scheme continuations “capture” the current execution state. They can be implemented by copying the stack, but this requires non-portable native code. Kawa continuations are implemented using Java exceptions, and can be used to prematurely exit (throw), but not to implement co-routines (which should use threads anyway).

(Я не согласен с последним утверждением в скобках.) Возьми схему и попробуй написать сопроцедуру на продолжениях, тогда станет понятно в чём проблема и как продолжения работают. Если хочешь, могу показать свой код, но здесь проще понять сделав самостоятельно, чем разобрав чужое решение.

Jini ★★ ()
Ответ на: комментарий от linearisation

Не знаю. Дополнительные расходы будут, но, вообще, медленно --- понятие относительное.

Jini ★★ ()
Ответ на: комментарий от linearisation

Если делать свой стек, то будет очень медленно, потеряется Java interop, поменяется java calling convetions, да и очень муторно будет.
ИМХО лучше ограниченные продолжения.

kovrik ★★★★★ ()
Ответ на: комментарий от monk

В Kawa они явно помечают продолжения как invalid:
The method mark_invalid marks a continuation as invalid, to detect unsupported invocation of cont after callcc returns.

Как я понимаю, этот mark_invalid у них сделан просто для удобства, если продолжения не помечать как invalid, то повторно их использовать все равно нельзя будет, так?

Думаю, в Java многоразовые и не получится сделать, кроме как интерпретатором.

Так у меня интерпретатор. Можно про это подробнее?

kovrik ★★★★★ ()
Ответ на: комментарий от Bad_ptr

Ну, вроде как и сделал, вроде даже работает, но все равно не уверен, что сделал правильно.

В callcc мы создаем новое продолжение, там же ловим CalledContinuation, проверяем, наше ли это продолжение, помечаем его как invalid, возвращаем результат.

Проблема возникает тогда, когда результатом является другое продолжение: мы его возвращаем, evaluator его пытается выполнить (ибо это Procedure), оно кидает CalledContinuation.
Но мы уже вышли из callcc, следовательно, некому ловить этот CalledContinuation. Отсюда и ошибка, которая у меня вылезала (см. выше).

Как ты и предложил, на самом верхнем уровне я обернул все в try-catch и ловлю там CalledContinuation. Но что с ним потом делать? Вернуть значение - без проблем. Но как проверить, является ли он valid или нет?

Изначально я сделал так:

...
} catch (CalledContinuation cc) {
  if (!cc.getContinuation().isValid()) {
    throw new RuntimeException("implementation restriction: continuation can only be used once");
  }
  return cc.getValue();
}


Но такой continuation всегда будет invalid, потому что мы его всегда помечаем как invalid в finally блоке в callc.

Переделал под тот случай, когда value является продолжением:

...
} catch (CalledContinuation cc) {
  if (cc.getValue() instanceof Continuation && !((Continuation)cc.getValue()).isValid()) {
    throw new RuntimeException("implementation restriction: continuation can only be used once");
  }
  return cc.getValue();
}


Такой вариант работает точно так же, как и в Kawa, но:

1) Не уверен в том, что так правильно. Как-то подозрительно выглядит.
2) Все же, хочется сделать многоразовые продолжения, если возможно (видимо нет)

kovrik ★★★★★ ()
Ответ на: комментарий от kovrik

1) Не уверен в том, что так правильно. Как-то подозрительно выглядит.

Ну скорее всего не надо ничего ловить, всё же.
Вот это

(define (cc) (call-with-current-continuation (lambda (cc) (cc cc))))
((cc) display)

В kawa тоже приводит к непойманному исключению.

2) Все же, хочется сделать многоразовые продолжения, если возможно (видимо нет)

Да, судя по всему это будет сложно.

Bad_ptr ★★★★ ()
Ответ на: комментарий от Bad_ptr

Я проверяю продолжения на 3х примерах:

;; example 1
(define (f return)
  (return 2)
  3)
(display (f (lambda (x) x))) ; displays 3
(display (call-with-current-continuation f)) ; displays 2

;; example 2
(define (cc) (call-with-current-continuation (lambda (cc) (cc cc))))
((cc) display)

;; example 3
(let* ((yin  ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
    (yin yang))


Ожидаю, что первый выведет 3 2, второй выведет #<procedure:display> (но это уже не точно, раз ты говоришь, что в Kawa оно не работает), третий выведет @*, а потом кинет exception.

Методом тыка сделал callcc таким же, как и в Kawa, а на верхнем уровне ловлю CalledContinuation таким образом:
...
} catch (CalledContinuation cc) {
  // насколько я понимаю, этот if срабатывает тогда, когда кто-то пытается повторно выполнить уже выполненное продолжение (возвращая его в качестве value другого продолжения, которое уже invalid)
  if (cc.getValue() instanceof Continuation && !((Continuation)cc.getValue()).isValid()) {
    throw new RuntimeException("implementation restriction: continuation can only be used once");
  }
  // если мы попали сюда, значит продолжение уже было выполнено в callcc (поэтому оно invalid) поэтому просто возвращем значение
  if (!cc.getContinuation().isValid()) {
    return cc.getValue();
  }
  // продолжение все еще valid, кидаем наверх
  throw cc;
}


При таком подходе, все 3 примера работают как надо.
Но, сам понимаешь, выглядит крайне подозрительно.
Возможно, пока сделаю как в Kawa.

kovrik ★★★★★ ()
Ответ на: комментарий от Bad_ptr

Откатился до Kawa'вской версии продолжений :(

Почитаю еще вот это:
https://www.politesi.polimi.it/bitstream/10589/108685/3/2015_07_Bernardini.pdf
http://icooolps.loria.fr/icooolps2007/Papers/Dragos_Cunei_Vitek_icooolps2007.pdf

Может что-нибудь получится.

Всем большое спасибо за помощь!

kovrik ★★★★★ ()
Последнее исправление: kovrik (всего исправлений: 1)
Ответ на: комментарий от Bad_ptr

Возник еще вопрос:
везде пишут, что call/cc - обычная процедура.

Но я не совсем понимаю, как ее можно реализовать в виде обычной процедуры. Ведь applicative call-by-value order предполагает, что мы сначала вычисляем все аргументы процедуры, а потом передаем их ей.

Но в случае call/cc, при вычислении аргументов оно может кинуть CalledContinuation, так? Или я что-то не понимаю?

kovrik ★★★★★ ()

Когда мне в моей реализации интерпретатора схемо-диалекта на Java надоели постоянные джавовские стековерфлоу, я в конце концов написал свой итеративный эвалюатор с собственным стеком. Продолжения не делал (потому что не понял их, зачем они нужны, да еще если большой ценой), но насколько я понимаю, имея итеративный эвалюатор с собственным управляемым стеком, реализовать их не проблема.

Ivana ()
Ответ на: комментарий от Ivana

Это немного не то. У меня StackOverflow не возникает, потому что я Tail Call Optimization реализовал. И с джававским стеком и calling conventions оно прекрасно дружит и работает.
А вот продолжения - не очень.

kovrik ★★★★★ ()
Ответ на: комментарий от kovrik

Это немного не то. У меня StackOverflow не возникает, потому что я Tail Call Optimization реализовал.

Я тоже сначала ТСО реализовал. Когда наедитесь StackOverflow от нехвостовых вызовов, может тоже придете к этому варианту - и будет самое то.

Ivana ()
Ответ на: комментарий от kovrik

Но в случае call/cc, при вычислении аргументов оно может кинуть CalledContinuation, так?

Нет. Аргумент у call/cc один — это функция. call/cc вызывает эту функцию и передаёт ей текущее продолжение как аргумент.

monk ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.