Каковы особенности продолжений, на которые опирается Раку (до)?

Question

Topi c ограниченных продолжений почти не обсуждалась среди энтузиастов языков программирования в 1990-х и 2000-х годах. Недавно он вновь стал одним из основных в дискуссиях о языках программирования.

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

Дословное цитирование (с поправкой на форматирование) из онлайн-сообщения ^[1] написано лицом, руководящим работой по добавлению продолжений в JVM:

• Asymmetri c: Когда продолжение приостанавливается или завершается, выполнение возвращается звонящему (Continuation.run()). Симметричные c продолжения не имеют понятия вызывающего. Когда они уступают, они должны указать другое продолжение для передачи выполнения. Ни симметричные c, ни asymetri c продолжения не являются более мощными, чем одно другое, и каждое из них может использоваться для моделирования другого.

• Stackful : продолжение может быть приостановлен на любой глубине в стеке вызовов, а не в той же подпрограмме, где начинается разделенный контекст, когда продолжение не имеет стека (как в случае C#). Т.е. у продолжения есть свой собственный стек, а не просто один фрейм подпрограммы. Стекированные продолжения более эффективны, чем бесстековые. тело определенного исполняемого файла), а не все состояние выполнения вплоть до main(). Разграниченные продолжения строго более мощные, чем неограниченные (http://okmij.org/ftp/continuations/undelimited.html), последнее считается «практически бесполезным» (http://okmij.org/ftp/continuations/against-callcc.html).

• Мультипросмотр : продолжения могут быть вложенными, и в любом месте стека вызовов любое из включающих продолжений может быть приостановлено. Это похоже на вложение блоков try / catch и генерирование исключения определенного типа, которое раскручивает стек до ближайшего улова , который его обрабатывает , а не только до ближайшего улова. Примером вложенных продолжений может быть использование Python -подобного генератора внутри виртуального потока. Код генератора может выполнять блокирующий вызов ввода-вывода, который приостанавливает продолжение включающего потока, а не только генератор: https://youtu.be/9vupFNsND6o?t=2188

• One- shot / non-reentrant : Каждый раз, когда мы продолжаем приостановленное продолжение, его состояние изменяется, и мы не можем продолжать его из одного и того же состояния приостановки несколько раз (т.е. мы не можем go вернуться назад во времени). Это отличается от реентерабельных продолжений, где каждый раз, когда мы приостанавливаем их, возвращается новый неизменяемый объект продолжения, который представляет конкретную точку приостановки. Т.е. продолжение - это единичный момент времени, и каждый раз, когда мы продолжаем его, мы go возвращаемся в это состояние. Реентерабельные продолжения строго более мощные, чем невозвратные; то есть они могут делать то, что строго невозможно с помощью всего лишь одноразового продолжения.

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

Продолжения Aiui не раскрываются напрямую в Raku, поэтому, возможно, правильным ответом, связанным с Raku (в отличие от Rakudo), будет «нет продолжений». Но мне это непонятно, поэтому в дальнейшем, в котором я описываю то, что, я надеюсь, может быть в ответе, если мне очень повезет, я сделаю вид, что имеет смысл поговорить о них в контексте обоих Раку. и Ракудо как два разных мира.

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

• "Как" 100 лет " язык дизайн , Raku текущая лежащая в основе semanti c [выполнение?] модель требует , как минимум, одноразовых продолжений, разделенных несколькими подсказками, без стека.

• Теоретически c pov, дизайн Raku может никогда расширяться, чтобы требовать, чтобы продолжения были клонируемыми, но теоретически может расширяться, чтобы они были сложены .

• Rakudo реализует требуемую в настоящее время семантику продолжения.

• MoarVM имеет встроенную поддержку этой семантики и может реально отслеживать теоретически возможные расширения требований, если конструкция Raku когда-либо расширится.

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

(Или что-то вроде того.)

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

PS. Спасибо @Larry, который понимал вещи достаточно глубоко, чтобы знать, что продолжения должны быть частью картины; Стефану О'Риру за его вклад, включая начальные реализации того, что я считаю одноразовым продолжением с разделителями и несколькими подсказками; и jnthn за воплощение мечты в реальность.

Сноски

¹ Ведется работа по внедрению продолжений в качестве первоклассной конструкции для JVM. Ключевой движущей силой этих усилий является Рон Пресслер. Вышесказанное основано на сообщении, которое он написал в ноябре .

Answer 1

Rakudo использует продолжения в качестве стратегии реализации для двух функций:

• gather / take - для реализации ленивых итераторов
• Делает await в пуле потоков не -blocking

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

• Stackful - да, потому что нам нужно уметь take или await на любой глубине в стеке вызовов относительно gather или работы l oop рабочего пула потоков. Например, вы можете написать алгоритм рекурсивного обхода графа внутри gather, а затем take каждого обнаруженного узла. Для await это основная разница между await и await Raku, как видно на многих других языках: вам не нужно полностью рефакторировать стек вызовов.
• с разделителями - да. Операция сброса продолжения устанавливает тег (или «приглашение»), и когда мы выполняем операцию управления продолжением, мы разрезаем стек по этому разделителю. Я не могу представить, как бы вы реализовали задействованные функции Raku без их разделения.
• Мульти-подсказка - да, это необходимо, потому что вы можете повторять один источник данных, предоставленный a gather внутри другой реализации gather или await внутри gather.
• Asymmetri c - после того, как продолжение было принято , выполнение продолжается после инструкции reset. В случае await мы go и находим другую задачу в очереди рабочих задач, а в случае take мы возвращаемся в метод pull-one итератора и можем вернуть взятое значение. Я думаю, что этот подход хорошо подходит для языка, где только некоторые функции используют продолжения.
• Одноразовый / без повторного входа - да, и, по крайней мере, в MoarVM безопасность памяти среды выполнения зависит от этого свойства. Это обеспечивается операцией сравнения и замены atomi c, поэтому, если бы два потока участвовали в гонке для вызова продолжения, только один мог бы добиться успеха. Никакие функции Raku не нуждаются в дополнительной сложности, которую подразумевают повторные продолжения.
• Cloneable - нет, потому что это не требуется для функций Raku. Теоретически это не так уж плохо, чтобы реализовать в MoarVM, говоря «да, мы можем это сделать», но я подозреваю, что это вызывает много вопросов, например «насколько глубоко должно быть клонировано». Если вы просто клонируете все записи вызова и тому подобное, вы все равно будете использовать Scalar контейнеры, Array s и c. между клонами.

Насколько я понимаю - хотя я слежу за этим издалека - продолжения JVM, по крайней мере, частично нацелены на то же пространство дизайна, что и механизм Raku await, и поэтому Я был бы удивлен, если бы они не предоставили то, что нужно Раку. Это явно упростило бы компиляцию кода Raku в JVM (в настоящее время он выполняет глобальное преобразование CPS, как и генерацию кода, что, как ни странно, оказалось проще, чем я ожидал), и почти наверняка он будет работать намного лучше, потому что преобразование требуется вероятно, скрывает довольно много вещей с точки зрения JIT-компилятора.

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