Что является примером продолжения, не реализованного как процедура?

15

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

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

Чтобы помочь моему пониманию, можно ли привести пример на функциональном языке, где продолжение выражено более абстрактно, чем функция? Я знаю, что Scheme позволяет вам получить текущее продолжение первоклассным способом (call / cc), но даже в этом случае кажется, что процедура с одним аргументом, переданная в call / cc, просто получает текущее продолжение в форме другого Процедура аргумента, к которой функция call / cc'd может применить свой результат.

Дэвид Кауден
источник
Возможно пересечение продолжений и нефункционализации как: продолжения могут быть преобразованы в структуры данных посредством нефункционализации; может быть интересной областью, чтобы смотреть.
Дэн Д.
@DanD. у вас есть предложения по интересной литературе, которую я могу прочитать? Эта тема звучит полезно.
Дэвид Кауден,

Ответы:

11

ТЛ; др; Типом является главной абстракцией над продолжением


Продолжением является тип его входов и выходов.

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

Вы можете инкапсулировать это замыкание в тип, такой как Contтип в Haskell, где вы получаете абстракцию монады как «абстракцию более высокого уровня», и есть другие формы абстракции над продолжениями, которые вы получаете, когда вы смотрите на продолжение как на тип вместо просто процедура , например

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

Закрытие против Процедуры

В конце дня вы в основном правы; продолжение - это «процедура», хотя я бы скорее назвал это закрытием. Часто продолжения лучше всего выражать как замыкания первого класса, которые окружают связанную среду. В чистом функциональном языке вы можете сказать, что это не особенно разумно, потому что у вас нет ссылок; это верно, но вы можете заключить значения, и одно присваивание делает вложение значения и ссылки в одно и то же. Это рождает в Хаскеле:

(\x -> \y -> insideYIcanAccess x (and y))

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

Поэтому я бы сказал, что более точно описать продолжение как: замыкание, используемое определенным образом.


Вывод

На вопрос "Возможно ли продолжение каким-либо образом, кроме процедуры?" Нет. Если у вас нет функций первого класса, вы действительно не можете иметь продолжения как таковые (да, указатели на функции считаются функциями первого класса, так что в качестве альтернативы может быть достаточно произвольного доступа к памяти).

Теперь вопрос «Есть ли способы выразить продолжение более абстрактным способом, чем процедура?» Выражение его как типа дает вам гораздо большую абстракцию, позволяя вам обрабатывать продолжение в самых общих чертах, так что вы можете взаимодействовать с продолжением многими другими способами, а не просто выполнять его.

Джимми Хоффа
источник
1
Это обобщает: «Продолжением может быть что угодно, что позволит вам получить результат остальной части программы». Поскольку это обычно требует наличия некоторого кода (остальной части программы), большинство языков используют функции. Теоретически вы можете построить продолжение из чего угодно. Во время продолжения преобразования в моих компиляторах я использовал частично заполненные деревья.
Даниэль Гратцер
1
Частично заполненные деревья @jozefg представляют собой правильное представление вычислений в виде выражений, но в конце дня фактический код, который пишется, представляет собой своего рода выражение, которое не может быть однозначно отличным от процедуры, как я понимаю. Кроме того, частично заполненные деревья являются представлением компилятора; представление разработчиков, как ожидается, представляет собой вычислительное выражение, нормативное с синтаксисом и семантикой языка, которое представляется 99% разработчиков как «процедура», «функция» или иным образом. Ты думаешь с точки зрения разработчика компилятора хе
Джимми Хоффа
2

Один пример, который вам может понравиться, это сопрограммы. Например, сопрограммы из Lua или итераторы / генераторы из Python или C # по мощности похожи на однократные продолжения (продолжения, которые можно вызывать только один раз), но это продолжение явно не превращается в функцию. Вместо этого у вас есть способы продвинуть сопрограмму до следующего выражения «yield».

Например, рассмотрим следующую программу на Python:

def my_iterator():
   yield 1
   yield 2
   yield 3

def main():
   it = my_iterator()
   x = it.next()
   y = it.next()
   z = it.next()
   print x + y + z

Это похоже на следующую программу Javascript с явными обратными вызовами:

function my_iterator()
  return function(cb1){
    cb1(1, function(cb2){
      cb2(2, function(cb3){
        cb3(3, function(cb4){
          throw "stop iteration";
        });
      });
    });
  });
}

function main(){
   var getNext1 = my_iterator();
   getNext1(function(x, getNext2){
      getNext2(function(y, getNext3){
         getNext3(function(z, getNext4){
            console.log(x + y + z);
         });
      });
   });
}

Пример Javascript довольно шумный, потому что каждый шаг должен возвращать следующее продолжение в дополнение к возвращаемому значению (в Python отслеживает продолжение внутри ите

hugomg
источник