На странице «Продвинутая схема: некоторые непослушные биты» говорится:
Продолжения - это мощная конструкция потока управления, из которой может быть получена почти любая другая структура потока управления [...].
Я думал, что схемы call/cc, связанные (*) с оператором J Питера Лэндена, могут быть использованы для реализации любой известной структуры потока управления?
Что касается «структуры потока управления», то я специально думаю об их описании в Википедии , например, об исключениях, сопрограммах, зеленых нитях и так далее.
В частности, есть ли примеры структур управления потоками, которые нельзя реализовать с помощью call/cc?
(*) Мне не удалось выкопать какую-либо бумагу, в которой говорится, что call/ccона так же мощна, как оператор J. Статья Феллайзена (которую я не читал и, по общему признанию, испытываю проблемы с ее полным пониманием) исследует это и, похоже, приходит к выводу, что, хотя они находятся в разных классах сложности, они формально эквивалентны.
(Также обратите внимание, что я обновил вопрос, основываясь на комментариях ниже)
Обновить
Основываясь на превосходном ответе @Neel ниже, я посмотрел сайты, комментирующие ограниченные и неограниченные продолжения , и действительно кажется, что call/cc, будучи неограниченным, этого недостаточно. Между тем, кажется, что первоклассные продолжения с разделителями (вроде shift/reset) могут использоваться для выражения любой структуры потока управления.
call/ccне могут выражать исключения в отсутствие состояния . (Как продолжает Тилеке, исключения могут быть реализованы путем передачи двух продолжений, одного для программы и другого для обработчика исключений, но для этого требуется больше, чем простоcall/cc.)amb-оператор и так далее.Ответы:
В этом ответе я возьму слово «выразимый» в значении «макроэкспрессируемый» в смысле Феллайзена, 1991 г. « О выразительной силе языков программирования» . (Интуитивно понятно, что языковая функция может быть выражена макросом, если вы можете определить ее как преобразование локального источника, без использования преобразования всей программы.)
При таком определении ответ будет отрицательным : элемент управления с разделителями не может быть выражен макросом в лямбда-исчислении + call / cc. Для выражения управляющих операторов с разделителями используйте call / cc. Чтобы реализовать разделители управления (часть сброса смещения / сброса), вам необходимо некоторое состояние для имитации меток продолжения, по существу, для кодирования стека для имитации динамического времени жизни меток продолжения.
Однако контроль с разделителями является универсальным эффектом в следующем смысле. В своей докторской диссертации , Анджей Filinski показал , что любой выразим побочный эффект является кодируемым с использованием либо разграниченные продолжений, или вызова / см и одну ячейки состояния. Грубо говоря, «выраженный побочный эффект» - это любой эффект, монадический тип которого может быть определен в терминах типов языка программирования.
Удивительно, но эта идея кажется довольно интересной на практике. За последнее десятилетие Гордон Плоткин и Джон Пауэр выступили за идею использования алгебраической семантики теорий эффектов : идея заключается в том, что вы задаете интересующие вас побочные эффекты и уравнения, которые вы ожидаете, что они удовлетворят, а затем вы можете получить семантику, взяв свободную монаду за эту теорию.
Матия Претнар и Андрей Бауэр взяли этот математический подход, а затем реализовали его на своем языке Eff, чтобы изобрести новую языковую конструкцию, называемую «обработчиками эффектов»: вы можете написать код, который использует набор императивных функций, а затем дать императивным функциям семантику написав набор обработчиков, которые говорят, как реализовать каждую эффективную операцию.
источник