Почему first-class продолжения есть только в scheme?

А разве есть где-то не first-class продолжения?

Как-бы, да, не first.

Верней, наоборот, кроме схемы везде не first.

В рубях ещё есть, например.

Значит, руби тоже обладает неким свойством, тем же что и схема? Что это за свойство, Вы случайно не знаете? Я имею в виду, какое семантическое свойство позволяет языку иметь их, реализовать их?

Вроде как не first - это сопрограммы, а продолжения - сопрограммы являющиеся объектами первого класса.

Ты сначала скажи, что именно ты понимаешь под первоклассными продолжениями.

Да не, вроде сопрограммы реализуются с помощью first-class продожений, а не наоборот. Можно сказать, частный случай использования продолжений.

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

Я считаю, что тут понимать особо нечего. объект языка, которым можно манипулировать как любым другим объектом, наравне, например, присвоить и тд, это общее определение для любых первоклассных объектов. Поэтому, тут никто не может ничего понимать «по-своему»

Да нет. Просто first-class продолжения это как масло масляное.

Чем scheme принципиально отличается от других языков, в этом смысле?

Наличием TCO в стандарте. В реализациях Common Lisp не делают просто из вредности (с unwind-protect неясная семантика взаимодействия).

В C/C++/... есть setjmp+longjmp.

Значит, руби тоже обладает неким свойством, тем же что и схема?

Нет. В Ruby (как и в Common Lisp, Haskell, Smalltalk, ...) ограниченные продолжения. Реализованы через CPS, поэтому тормозные.

есть setjmp+longjmp.

Ну, а неограниченное goto можно считать эквивалентом first-class продолжений?

call-with-current-continuation

first-class продолжения это как масло масляное.

ТС имел в виду s/first-class/undelimited/

нет

неограниченное goto можно считать эквивалентом first-class продолжений

продолжение ещё и стек восстанавливает, а не только переходит в нужную точку.

Продолжения тяжело/невозможно реализовать эффективно.

Вот это точно неверно. Всё, что надо — прямая манипуляция стеком. Вызов продолжения в общем случае дешевле, чем переключение между потоками.

Я имею в виду, не точным эквивалентом, а то, что через него можно реализовать ту же семантику. Например, нелокальные выходы.

В Ruby […] ограниченные продолжения. Реализованы через CPS, поэтому тормозные

А где об этом можно почитать? В смысле, о деталях реализации продолжений в Ruby?

Но ведь стек можно выстроить явно, а затем сохранить в переменную, или как?

Например, нелокальные выходы.

Суть продолжения не в выходах. Для этого достаточно исключений. А, наоборот, во входе в произвольный момент вычислений. И здесь goto внутрь функции недостаточен, надо, как минимум, установить правильное состояние стека.

продолжай в таком же духе и ты реализуешь свою схемку

А, наоборот, во входе в произвольный момент вычислений.

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

В смысле, о деталях реализации продолжений в Ruby?

Я, похоже, неправ. Судя по http://ruby-doc.org/core-2.0/Continuation.html продолжения там нормальные. Проверить точно не могу, под рукой интерпретатора нет.

Большое спасибо.

стек можно выстроить явно, а затем сохранить в переменную

В большинстве языков прямого доступа к стеку нет.

Вот это точно неверно. Всё, что надо — прямая манипуляция стеком. Вызов продолжения в общем случае дешевле, чем переключение между потоками.

Вызов call/cc это копирование всего текущего стека в новую область памяти и сохранение указателя на эту область. При возвращении в стек его надо ещё раз копировать. Не забывай, что в продолжения можно возвращаться сколько угодно раз и каждый раз оно должно выглядеть одинаково.

Я имею в виду, какое семантическое свойство позволяет языку иметь их, реализовать их?

Не реализуют не потому что не могут.

http://c2.com/cgi/wiki?CallWithCurrentContinuation : «Be aware that many view CallWithCurrentContinuation not as a cool feature, but as a fatal flaw. It's like having a nuclear bomb in your garage. Cool, sure, but do you really want one? Specially when the neighbor's kids might drop in? Call-cc is the ultimate minimalism; sure, it replaces goto, block, throw, catch, etc, but not in a controlled way. It makes it impossible to, by inspection, determine how often a piece of code might be executed.»

Вызов call/cc это копирование всего текущего стека в новую область памяти и сохранение указателя на эту область.

копировать ничего не нужно, достаточно указатель сохранить.

При возвращении в стек его надо ещё раз копировать.

Не нужно. Зачем?

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

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

Вызов call/cc это копирование всего текущего стека в новую область памяти и сохранение указателя на эту область.

Переключение на другой поток — это копирование всего стека + thread-local данных + состояние регистров.

При возвращении в стек его надо ещё раз копировать.

При переключении из потока обратно — аналогично.

А можно пример схемокода, с помощью которого можно проверить?

Вот прямое переложение примера x4DA (это не совсем идиоматический Ruby-код), всё работает, как надо:

require 'continuation'

k_global = nil

my_number = 3
k = callcc { |kont| kont }
puts "The value of my_number is #{my_number}"
my_number += 1
k_global = k

if k_global.is_a? Continuation
  puts "This is the first run, k_global is a continuation"
  k_global[4]
else
  puts "This is the second run, k_global is not a continuation, it is #{k_global}"
end

__END__

Output:

The value of my_number is 3
This is the first run, k_global is a continuation
The value of my_number is 4
This is the second run, k_global is not a continuation, it is 4

Это если у тебя стек реализован не как у нормальных людей через push eax, а каждый вызов функции выделяет отдельный фрейм в куче и стек у тебя это связный список этих фреймов. Такой вариант возможен, но это в принципе ужасная производительность при вызове и возврате функций в сравнение с родным процессорным стеком. Там да, ничего копировать не надо, всё красиво, согласен. Но не взлетит, процессорный кеш любит локальность.

чего-чего?

Переключение на другой поток — это копирование всего стека + thread-local данных + состояние регистров.

Переключение на другой поток это переключения указателя на стек. thread-local данные копировать обычно не надо, опять же меняется только указатель на thread-local данные. Все состояния регистров тоже не факт, что надо копировать, зависит от реализации потоков.

А можно пример схемокода, с помощью которого можно проверить?

(define (walker->iterator walker collection)
  (define caller #f)
  (define (yield-cont)
    (walker proc collection)
    (caller #f))     
  (define (yield)
    (call/cc
     (lambda (k)
       (set! caller k)
       (yield-cont))))
  (define (proc x)
    (call/cc
     (lambda (continue)
       (set! yield-cont (lambda () (continue #f)))
       (caller x))))
  yield)

> (define gen (walker->iterator map '(1 2 3 4 5)))
> (gen)
1
> (gen)
2
> (gen)
3
> (gen)
4
> (gen)
5
> (gen)
#f

Если в получившийся walker->iterator удастся передать стандартный each, то действительно полнофункциональные. Если нет, значит require 'continuation' изменяет текущий модуль в CPS.

чего-чего?

Про Ruby я уже покаялся. На что-то ещё тоже зря наехал?

Переключение на другой поток это переключения указателя на стек.

Так вызов продолжения также всего лишь переключение указателя на стек. Вот создание продолжения чуть более дорогая операция (нужно скопировать стек до барьера, но, опять же, создать поток — дороже).

не уверен, щас почитаю, что тут понаписали. Ни и у меня тут ощущение, что щас тут начнется путаница между delimited и undelimited continuations и что же считать first-class value.

А пока, вот пара вбросов:

We argue against call/cc as a core language feature, as the distinguished control operation to implement natively relegating all others to libraries. The primitive call/cc is a bad abstraction — in various meanings of `bad' shown below, — and its capture of the continuation of the whole program is not practically useful. The only reward for the hard work to capture the whole continuation efficiently is more hard work to get around the capture of the whole continuation. Both the users and the implementors are better served with a set of well-chosen control primitives of various degrees of generality with well thought-out interactions.

и

We alert to the misconception of explicit, or first-class, undelimited continuations as ordinary functions. The confusion is wide-spread, for example, in the description and the code for the Cont monad in Haskell's monad transformer libraries. We argue for a better call/cc interface, to hopefully reduce the bewilderment commonly associated with that control operator. We describe the proper undelimited continuation monad, pointing out that Haskell's Cont is actually the monad for delimited continuations. Delimited and undelimited continuations are vastly different. Delimited continuations are isomorphic to functions, they do return the result and can be composed. We emphasize the great help of types in understanding continuations and avoiding their surprises.

Scheme's call/cc might be responsible for mistaking first-class undelimited continuations as functions: the captured undelimited continuation k in (call/cc (lambda (k) ...)) indeed looks like a function and can be applied to a value. It is not a genuine function however. The expression (k (k 1)), albeit well-formed, is meaningless. It makes as much sense to compose captured undelimited continuations as to compose abort or exit `functions.' The call/cc interface in SML is quite more helpful:

А пока, вот пара вбросов

На них мне нравятся решения в Racket: есть понятие «барьера» (до него раскручивается стандартный call/cc), есть отдельно call/cc, call-with-composable-continuation (для delimeted) и call-with-escape-continuation.

The expression (k (k 1)), albeit well-formed, is meaningless

Если k вызывает исключение, то аналогично. Исключения тоже запретим?

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

Вообще, как у нормальных людей - это именно второй вариант. Спагетти-стек в классической его форме. А как ты ФВП собрался с «обычным» стеком делать?

Такой вариант возможен, но это в принципе ужасная производительность при вызове и возврате функций в сравнение с родным процессорным стеком.

С чего это? Стек в памяти работает с абсолютно той же самой скоростью, что и «процессорный». Ну просто потому что между ними нету никакой разницы, на самом деле.

Но не взлетит

Ну что значит «не взлетит», если это стандартное, повсеместно применяемое решение, которое давным-давно взлетело, взлетает и взлетать будет?

Переключение на другой поток это переключения указателя на стек.

Ну вот именно это и происходит при вызове продолжения. Ты так и не объяснил, почему надо что-то куда-то копировать в этом случае.

е уверен, щас почитаю, что тут понаписали. Ни и у меня тут ощущение, что щас тут начнется путаница между delimited и undelimited continuations и что же считать first-class value.

Нет, тут речь скорее о том, что продолжения через CPS - это неюзабельный костыль, а не продолжения.

продолжение это ход программы после данной точки. соответственно, они есть везде

Так вызов продолжения также всего лишь переключение указателя на стек. Вот создание продолжения чуть более дорогая операция (нужно скопировать стек до барьера, но, опять же, создать поток — дороже).

После вызова продолжения оно испортит стек. Второй раз его же вызвать не получится. Поэтому при вызове продолжения надо будет копировать стек. Ну или использовать спагетти-стек (см. дискуссию с анонимусом).

Про поток я ничего не говорю, что создание потока, что переключение потока это дорогие операции. Но их никто не создаёт на каждом чихе и их поддержка не требует нестандартной реализации стека.

но не везде как first-class

После вызова продолжения оно испортит стек.

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

Ну или использовать спагетти-стек (см. дискуссию с анонимусом).

Нужен, вообще, не спагетти-стек, а имутабельность стека. То есть банальный боксинг всех мутабельных локальных переменных, в чем ничего сложного нет. И даже ничего влияющего на производительность нет - т.к. мутабельные переменные встречаются в схемке сверхредко.

Но их никто не создаёт на каждом чихе и их поддержка не требует нестандартной реализации стека.

У нас ФЯП, потому и так требуется нестандартная организация стека.

Вообще же при правильной реализации продолжения оверхед на него сравним по скорости с обычным функциональным вызовом. И даже может обгонять в определенных случаях (когда оптимизируется до гото).