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

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

Молча - берёшь и делаешь, вопрос не очень понятен. Если забыть про продолжения, в чём проблема реализации той же схемы на стандартном стеке? И работать будет шустро, если проводить escape анализ и по максимуму размещать данные на стеке.

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

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

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

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

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

Какая разница, стек то мутабелен.

(print 1) - в стек сунули единичку, вызвали print, вернулись (print 2) - в стек сунули двойку, которая ПЕРЕПИСАЛА единичку, вернулись.

если (print 1) стек свой сохранит в продолжении и не скопирует, то второй вызов print испортит его. А данные все иммутабельны, да.

Молча - берёшь и делаешь

Фреймы замыканий нельзя хранить в «обычном» стеке. Так что если у тебя есть замыкания - у тебя _уже_ спагетти-стек в том или ином варианте реализации.

Если забыть про продолжения, в чём проблема реализации той же схемы на стандартном стеке?

См. выше.

И работать будет шустро, если проводить escape анализ и по максимуму размещать данные на стеке.

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

Разница в том, что при вызове новой функции у тебя процессорные кеши потеряет все данные, которые в нём были загружены.

С чего вдруг он их должен потерять?

И при возврате из функции он опять всё потеряет.

Ты выдумываешь.

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

Он и учитывает уже лет 30 как. Любой производительный сборщик учитывает локальность данных, иначе толку от такого сборщика ноль, начерта он нужен, если не дает выигрыша в производительности по сравнению с маллоком?

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

Там и ФВП с ГЦ нет.

Стек на раздельных фреймах ведь не только для call/cc нужен. Например, в имеющихся binutils, libc и gcc раздельный стек (-fsplit-stack) был реализован для того, чтобы поддерживать горутины в Go. Просто потому, что иначе крайне трудно работать со стеком в многопоточных приложениях.

Какая разница, стек то мутабелен.

Стек - это и есть соответствующие данные. Нету таких операций, которые могут поменять стек.

(print 1) - в стек сунули единичку, вызвали print, вернулись (print 2) - в стек сунули двойку, которая ПЕРЕПИСАЛА единичку, вернулись.

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

Это семантика ГЦ, и так в любом абсолютно языке с ГЦ. И продолжения тут не при чем совершенно - если у тебя аллоцировано замыкание, удерживающее указатель на единичку (на рем с единичкой, если быть более корректным), то никакая двойка не может эту единичку перезаписать.

Разница в том, что при вызове новой функции у тебя процессорные кеши потеряет все данные, которые в нём были загружены.

Если я правильно помню, он умеет загружать и выгружать отдельные страницы памяти, на x86 по крайней мере. Даже если аллокатор будет выделять память под стек из разных мест, перерасход будет не смертельный.

it = WalkerIterator.new(map, [1,2,3,4,5])

Круто! Значит, не только в Scheme нормальные продолжения. В ruby всё круто, но производительность бы ещё подтянули. Хотя бы до уровня SBCL/Racket

Фреймы замыканий нельзя хранить в «обычном» стеке. Так что если у тебя есть замыкания - у тебя _уже_ спагетти-стек в том или ином варианте реализации.

Я знаю как минимум один способ реализации замыканий, который прекрасно дружит с обычным стеком. Замыкание это указатель на код + массив указателей на значения (константные значения небольшого размера можно засунуть вместо указателя в эту таблицу). Соответственно ссылки на замкнутые переменные из кода замыкания компилируются как косвенная адресация через эту таблицу.

С чего вдруг он их должен потерять?

Потому что первый фрейм у тебя по адресу 0x123000 и при обращении к стеку у тебя кеш забьётся значениями из этого адреса (и близких к нему, если фрейм большой). Ты вызываешь любую функцию, тебе выдаётся адрес фрейма 0x987000 и у тебя из кеша вылетают куча линий, которые были рядом с прошлым стеком и кеш забивается новыми данными. У тебя эта новая функция практически сразу сделала return и тебе опять надо кеш забивать старыми данными.

Там и ФВП с ГЦ нет.

Java, Go, D - есть. Да и тот же Haskell говорят может работать довольно быстро. Для Scheme когда то был компилятор Stalin, который генерировал быстрый код. И там, если мне память не изменяет, как раз были какие то оговорки с continuations.

Это ты Олега цитируешь?

Замыкание это указатель на код + массив указателей на значения (константные значения небольшого размера можно засунуть вместо указателя в эту таблицу). Соответственно ссылки на замкнутые переменные из кода замыкания компилируются как косвенная адресация через эту таблицу.

И что изменилось? Тот же спагетти-стек.

Потому что первый фрейм у тебя по адресу 0x123000 и при обращении к стеку у тебя кеш забьётся значениями из этого адреса (и близких к нему, если фрейм большой). Ты вызываешь любую функцию, тебе выдаётся адрес фрейма 0x987000

С чего адрес второго фрейма будет далеко от первого? Он сразу за ним будет, как и в случае программного стека.

и у тебя из кеша вылетают куча линий, которые были рядом с прошлым стеком и кеш забивается новыми данными.

С чего бы вылетать тем линиям, которые только загрузились? Вылетят линии с наименьшим приоритетом. И это явно не линии последнего фрейма.

Java, Go, D - есть.

Там нету замыканий.

Да и тот же Haskell говорят может работать довольно быстро.

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

Java, Go, D - есть.

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

Да

Только у хацкеля не C-like стек.

Подозреваю, что это у него от опыта работы с cl-cont, который действительно тормозной, да еще и неполный. Он перемалывает все, что надо и не надо. Даже циклы переписывает в CPS до мельчайших подробностей. Неполный потому, что не дружит с рестартами и обработкой исключений (сложная тема сама по себе). В общем, продолжения - это слабое место Common Lisp.

Что касается Haskell, то никаких проблем не заметил. Тут и обработка исключений (я имею ввиду самописные, а не стандартный Cont), и дружественность к многопоточности. Плюс удобный монадический интерфейс. Потом довольно шустро у меня бегают. Только в путь! Самые приятные впечатления.

Нет, это не от опыта, а это просто констатация факта, что первоклассные (неограниченные) продолжения есть только в scheme и (как выяснилось) ruby, и больше нигде.

это ж Олег, там производительность это последняя вещь, которая повлияет на «considered harmful»

http://okmij.org/ftp/continuations/implementations.html

Мне показалось, что ему не понравилась скорость, а cl-cont слишком усердно все превращает в CPS, из-за чего продолжения в Common Lisp медленнее, чем в других языках, где они тоже могут не являться первоклассными сущностями.

Да, вообще, по фигу на это, первоклассные или нет. В том же Haskell за монадическим интерфейсом продолжения почти ничем не отличаются от того же IO. Конечно, рекурсивные вычисления не получатся (не MonadFix), но исключения обработать в продолжениях можно подобно IO, да еще можно такие вычисления прерывать, чего IO как бы не умеют (зеленые потоки - отдельная тема).

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

Дык в undelimited проблем нет вообще никаких, см. ContT, в scheme есть delimited - про которые серия статей по ссылке и там же ссылка на пакет на хакадже, delim-cc если не ошибаюсь.

Дык в undelimited проблем нет вообще никаких, см. ContT

Насколько я понял, это библиотечная фича, а как библиотечная фича может добавить то, что должно быть на уровне языка? К тому же я нигде не нашел вообще, что ContT какое то отношение к undelimited.

зачем на уровне языка должно быть то, что является библиотечной фичей, про ContT, например, тут: https://www.haskell.org/haskellwiki/Library/CC-delcont#Undelimited_continuations ?

Ты понимаешь, что такое, на уровне языка? Давай возьмем пример попроще. Допустим, у нас в языке есть циклы, но нет механизма выхода из цикла (так же в языке нет goto, catch/throw и никаких конструкций, обеспечивающих нелокальные выходы). Как ты можешь запилить механизм такого выхода средствами языка? Исполнитель строит свой стек под ковром, у тебя нет никаких средств повлиять на него. Какая библиотечная фича, нахрен, может изменить эту ситуацию? Библиотека — это обычные выражения этого же языка, а чтобы запилить что-то подобное, нужен нижний уровень — уровень исполнителя.

Мне показалось, что ему не понравилась скорость, а cl-cont слишком усердно все превращает в CPS, из-за чего продолжения в Common Lisp медленнее, чем в других языках, где они тоже могут не являться первоклассными сущностями.

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

Можешь написать на Haskell аналог Почему first-class продолжения есть только в scheme? (комментарий) (или с Ruby: Почему first-class продолжения есть только в scheme? (комментарий)) и попробовать передать в него стандартный map?

В случае Common Lisp + cl-cont не сработает (из mapcar нельзя сохранить продолжение). Или мне придётся перекомпилировать пакет CL с подключенным cl-cont (после чего всё тормозить будет просто адово и не факт, что вообще получится).

ContT является delimited

There is a standard way to transform a program written normally (or in a monadic style, as above) into a program in which continuations, represented as functions, are passed around explicitly (known as the CPS transform), and this is what Cont/ContT does

...

However, continuations in Scheme are not implemented as they are in Haskell. In Haskell, continuation using code is tagged with a monadic type, and one must use runCont(T) to run such computations, and the effects can't escape it. In Scheme, continuations are native, and all code can capture them, and capturing them captures not 'the rest of the Cont(T) computation,' but 'the rest of the program.' And if the interactive loop is written in Scheme, this includes the loop itself, so programs run within the session can affect the session itself.

нерелеватный пример.

ну и хорошо

Undelimited and delimited continuations also differ in expressiveness, and this difference has been proven. First-class delimited continuations can express any expressible computational effect, including exceptions and mutable state. To be precise, any effect that can be emulated by transforming the whole program (into the state-passing--style, into an Either-returning style, etc.) can be expressed with first-class delimited continuations without the global transformation, see Filinski's ``Representing Monads." In contrast, first-class undelimited continuations cannot express raising and catching of exceptions. Furthermore, first-class undelimited continuations, even when aided by exceptions, cannot express mutable state. The limited expressiveness of undelimited continuations has been proven by Hayo Thielecke, see the reference and the abstract below.

Мне честно казалось, что у схемки именно delimited и это бонус, а его вона как.. нет на самом деле

In contrast, first-class undelimited continuations cannot express raising and catching of exceptions.

;;This establishes the throw function
(define throw (lambda (x) (display "No try clause is active!") (newline)))

;;establishes syntax for a "try" block
(define-syntax try
  (lambda (x)
    (syntax-case x (catch)
      (
       (try expression (catch exception exception-handler-expression))
       (syntax
         (let* (
                (old-throw throw)
                (retval
                  (call-with-current-continuation
                    (lambda (k-exit)
                      (let (
                            (error-handler
                              (lambda (exception)
                                (k-exit exception-handler-expression))))
                           (set! throw error-handler)
                           expression)))))
               (set! throw old-throw)
               retval))))))

;;Short test suite

;Function that throws an error
(define (test-function)
  (throw 'ERROR))

;Function that does not throw an error
(define (test-function-2)
  (display "No error is generated.")
  (newline))

;Test out our try block
(try (test-function) (catch e (begin (display "Exception!  e is: ") (display e) (newline))))
(try (test-function-2) (catch e (begin (display "Exception!  e is: ") (display e) (newline))))

In contrast, first-class undelimited continuations cannot express raising and catching of exceptions.

А мужики-то не знают:

(define-syntax try
  (syntax-rules ()
        ((_ handler throw chunk)
         (call/cc (lambda (catch)
                (let ((throw (lambda (exc) (catch (handler exc)))))
                  chunk))))))

(define (div p q)
  (try 
    ;; Error processing
    (lambda (error) (printf "Error: ~s~n" error) error)

    ;; Error my be thrown with keyword "throw"
    throw

    ;;Actual code to run
     (if (= q 0)
    ;; Oh noes, error!
        (throw "Division by zero")
    ;; All ok, do the work
     (/ p q))))

Furthermore, first-class undelimited continuations, even when aided by exceptions, cannot express mutable state.

Этот пассаж вообще не понял/ Почему first-class продолжения есть только в scheme? (комментарий) — это не mutable state?

Или всё это не про нормальные продолжения а про какие-то Хаскелопроблемы?

Мне честно казалось, что у схемки именно delimited и это бонус

delimited по твоей ссылке http://okmij.org/ftp/continuations/implementations.html реализуется в полсотни строк кода через undelimited call/cc

undelimited = delimited, т.к. достаточно тривиально выражаются друг через друга, это вобщем-то факт общеизвестный, так что цитаты твои написаны безграмотным дебилом.

Ну и главную проблему delimeted cps-based продолжений monk упомянул - взаимодействие между transformed и не transformed кодом.

достаточно тривиально выражаются друг через друга, это вобщем-то факт общеизвестный

Если delimited не могут захватить продолжение целиком, то как же через них можно выразить undelimited?

Если delimited не могут захватить продолжение целиком, то как же через них можно выразить undelimited?

(shift program ...)

Тебе же никто не мешает установить точку захвата на границе всей программы.

Генераторы в python разве не тоже самое?

Ты так говоришь, как быдто я не читаю то, на что ссылаюсь.

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

Нет.

Хотя бы до уровня SBCL/Racket

тонко

Тебе же никто не мешает установить точку захвата на границе всей программы.

Только если у тебя пересобрана через CPS вся стандартная библиотека.

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

Реализовать на Haskell? Для этого там есть ленивые списки.

В Haskell это должно быть так

gen = walkerToIterator map [1,3,5,7]

main = do
  i <- gen
  putStr i  -- должно вывести 1
  i <- gen
  putStr i  -- должно вывести 3
  i <- gen
  putStr i  -- должно вывести 5

Сможешь написать walkerToIterator ?

все реализуется через другое и есть в нормальных языках

Не всё. В Common Lisp есть cl-cont (которые преобразует в CPS), но толку от него нет, так как стандартная библиотека (map*, loop, ...) не в CPS. Соответственно, из них нельзя запоминать продолжения.

Поэтому, если есть call/cc, то delimited реализуется тривиально. А наоборот (есть delimited, надо сделать call/cc) — почти невозможно.

Go

Там нету замыканий.

А это что?

Оно в go работает, емнип, так же как в шарпах с джавами.

Почему тут второго входа в if нет? http://ideone.com/qsYp1X guile?

http://pasterack.org/pastes/77156

Значит в guile какие-то особенный продолжения?

http://docs.racket-lang.org/reference/module.html

On invocation, imported modules are instantiated in the order in which they are required into the module (although earlier instantiations or transitive requires can trigger the instantiation of a module before its order within a given module). Then, expressions and definitions are evaluated in order as they appear within the module. Each evaluation of an expression or definition is wrapped with a continuation prompt (see call-with-continuation-prompt) for the default prompt tag and using a prompt handler that re-aborts and propagates its argument to the next enclosing prompt.

в модуле каждое top-level определение оборачивается в continuation prompt, так что продолжение любого top-level expression из модуля = empty continuation.

нет, в guile видимо каждое top-level выражение тоже оборачивается в continuation prompt.

Могу, но сейчас не буду :) Еще раз напоминаю, что можно создать ячейку cons в любой монаде, если, ну, очень нужны побочные эффекты прямо во время вычисления, а дальше все просто.