call/cc в Lua - возможно?

Question

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

Либо это правда, и мне нужно знать, как это сделать, либо это неверно, и это утверждение нужно исправить.

Если это правда, пожалуйста, покажите мне, как реализовать call/cc в Lua, потому что я не вижу, как это сделать.

Я думаю, что смогу реализовать call/cc вручную, если у Lua была функция coroutine.clone, как описано here.

Если закрытие недостаточно для реализации call/cc, то что еще нужно?

Текст ниже является необязательным.
P.S .: Lua имеет одноразовые продолжения со своим сопрограммным столом. Функция coroutine.clone позволила бы мне клонировать ее, чтобы называть ее несколько раз, тем самым эффективно делая вызов/cc возможным (если я неправильно понимаю call/cc). Однако эта функция клонирования не существует в Lua. Кто-то из канала IRA Lua предложил использовать библиотеку Pluto (она реализует сериализацию), чтобы маршалить сопрограмму, скопировать ее, а затем отключить ее и снова использовать. Хотя это, вероятно, будет работать, меня больше интересует теоретическая реализация call/cc и в поиске того, что является фактическим минимальным набором функций, которые должен иметь язык, чтобы обеспечить его ручную реализацию.

EDIT 1: Ok люди, помогите мне здесь, это заняло у меня много времени, потому что я не знаю ни одной схемы, но я придумал что-то, что должно помочь нам. Пожалуйста, ознакомьтесь с приведенными ниже кодами. Первая - это программа на Схеме, вторая - та же самая программа, но в Lua.
Надеюсь, это поможет нам. Я считаю, что мы очень близко.

P.S .: Эти примеры взяты из первого примера на the Wikipedia article on CallCC. Схема версия

(define call/cc call-with-current-continuation) 

; callcc CPS-transformed (thanks to the people from the #scheme channel at freenode.net) 
(define cpscallcc 
    (lambda (consumer k) 
    (let ((cc (lambda (result) (k result)))) 
     (consumer cc k)))) 

; this is the continuation we will use to display the "returned" values 
(define main-continuation 
    (lambda (result) 
    (display "--> ") 
    (display result) 
    (newline))) 

; define f function non-CPS 
(define (f return) 
    (return 2) 
    3) 

; these are my past attempts at defining a CPS f function 
;(define (cps-f return k) 
; (k (return 2)) 3) 
;(define (cps-f return k) 
; (k (lambda() 
;  (return 2) 
;  3))) 

; this is what I came up with - I'm not sure if this is correctly CPS-transformed but I  believe so 
(define (cps-f return k) 
    (return 2) 
    (k 3)) 

; call the non-CPS f function 
(display (f (lambda (x) x))) ; displays 3 
(newline) 

; call the non-CPS f function with call/cc (I don't understand what this does) 
(display (call/cc f)) ; displays 2 
(newline) 

; now call the CPS version of the f function 
(cps-f (lambda (x) x) main-continuation) ; displays --> 3 

; now call the CPS version of the f function with the CPS version of call/cc 
(cpscallcc cps-f main-continuation) ; displays --> 2 but then it also displays --> 3 afterwards -> I'm not sure why it displays the 3 afterwards, as it should only display the 2 just like the non-CPS versions above 

Lua версия

-- callcc CPS-version 
cpscallcc = function(consumer, k) 
    local cc = function(result) 
     return k(result) -- ?or k(result) 
    end 
    return consumer(cc, k) -- ?or return consumer(cc,k) 
end 

-- define f function non-CPS 
f = function(ret) 
    ret(2) 
    return 3 
end 

-- define f function CPS-version (again, not sure this is correct) 
cps_f = function(ret, k) 
    ret(2) 
    k(3) 
end 

-- call the non-CPS f function 
print(f(function(x) return x end)) 

-- we cant call the non-CPS f function with callcc because 
-- Lua doesnt have callcc, but the line below displays the correct expected output (maybe by accident) 
--cpscallcc(f, print) 

-- now call the CPS version of the f function 
cps_f(function(x) return x end, print) -- displays 3 

; now call the CPS version of the f function with the CPS version of call/cc 
cpscallcc(cps_f, print) -- displays 2 and then 3 just like the Scheme version!! 
-- so apparently the translation from Scheme to Lua is correct... 

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

Answer 1

Есть две предпосылки, чтобы вручную осуществить вызов/куб.см за Википедии цитаты:

1. язык должен поддерживать CLOSURES
2. вы должны написать программу в продолжение прохождения стиля (CPS)

Я подозреваю, что вам не понравится # 2.

Чтобы написать программу в продолжение прохождения стиле:

1. Каждая функция должна взять продолжение аргумент
2. функции должны возвращать путем вызова их продолжение

Таким образом, используя k в качестве имени аргумент продолжения, функция будет выглядеть так:

function multiplyadd(k, x, y, z) return k(x * y + z) end 

Интерактивная система может использовать print как его продолжение, поэтому применение multiplyadd на высшем уровне будет выглядеть следующим образом:

multiplyadd(print, 2, 4, 1) 

С этого леса мы могли бы определить вызов/куб.см, как

function callcc(k,f) return f(k,k) end 

Обратите внимание, что выше multiplyadd на самом деле читы с * и + не находятся в CPS. Очень утомительно добавлять всех операторов в форму CPS, заменять все библиотечные функции Lua эквивалентами CPS и транслировать/генерировать весь ваш код в CPS; см. details here.

Answer 2

Я думаю, вы забыли часть о написании своей программы в продолжении прохождения стиль. Как только вы это сделаете, call/cc тривиально (в Lua или на любом другом языке), , поскольку продолжение будет явным параметром для всех функций (call/cc ).

PS: кроме закрытия, вам также нужны правильные хвосты для продолжения программы прохождение стиля.

Answer 3

Ключевая фраза

можно осуществлять программы в продолжением прохождения стиля

(выделено мной). Вы можете сделать это, принимая регулярные программы «прямой стиль» и преобразование их в стиль продолжения прохождения (CPS) с помощью программного преобразования, называемого преобразованием CPS. Ключ состоит в том, что преобразование CPS call/cc является простой функцией.

Это не подходит для программистов. КПСА преобразование имеет два применения:

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

Вы дон Не хотите никуда приближаться, чтобы преобразовывать CPS в код Lua, особенно не вручную.

Answer 4

Отвечая на вопрос о планах по вызову/cc в Lua: в Lua нет планов по вызову/cc.Захват продолжения слишком дорогостоящий или требует некоторого кода analsis намного превосходит то, что может сделать компилятор Lua. Существует также проблема, что продолжения Lua могут включать в себя части в C.

С сопрограммами, однако, мы уже можем реализовать call/cc1 в Lua (однократные продолжения). Это достаточно хорошо для многих применений продолжений.

Answer 5

Вот мой cps-convert в схеме, просто передайте ему каждую функцию, которую вы хотите преобразовать.

(define (cps-convert function . functions) 
    # Since "help" is called at 2 different places... 
    (define (help) (error "syntax: (cps-convert f1 f2 ...)")) 
    # Single function converter 
    (define (convert func) 
    # "name" contains the function's name prefixed with "cps-" 
    (let ([name (string->symbol 
          (string-append "cps-" (symbol->string func)))]) 
     # Dirty hack to define "cps-*" in the global environment 
    `(eval '(begin 
        # Necessary to prevent the function from being evaluated 
        (define ,name #f) 
           # Magic 
        (set! ,name (lambda (k . args) (k (func args))))) 
       # Global environment 
       (interaction-environment)))) 
    # Prerequisite... Call help if condition not met 
    (if (symbol? function) 
     # function is a symbol 
     (cond 
     # If there is only one function to convert 
     [(null? functions) (convert function)] 
     # Else ensure every other "functions" are symbols and convert each 
     [(every symbol? functions) (apply convert function functions)] 
     # Oops! Condition not met! 
     [else (help)]) 
     # Else clause from previous "if" 
     (help)))