call/cc в Lua - возможно?
В статье Википедии о продолжении говорится:
"На любом языке, который поддерживает замыкания, можно писать программы в стиле продолжения передачи и вручную реализовывать call/cc ".
Либо это правда, и мне нужно знать, как это сделать, либо это не так, и это утверждение необходимо исправить.
Если это правда, пожалуйста, покажите мне, как реализовать call/cc в Lua, потому что я не вижу как.
Я думаю, что смог бы реализовать call/cc вручную, если бы у Lua была функция coroutine.clone, как описано здесь.
Если замыканий недостаточно для реализации call/cc, что еще нужно?
Текст ниже является необязательным чтением.
PS: у Lua есть одноразовые продолжения с таблицей сопрограмм. Функция coroutine.clone позволила бы мне клонировать ее, чтобы вызывать ее несколько раз, таким образом, эффективно делая возможным вызов / cc (если я неправильно понимаю call/cc). Однако эта функция клонирования не существует в Lua. Кто-то на IRC-канале Lua предложил мне использовать библиотеку Плутона (она реализует сериализацию), чтобы упорядочить сопрограмму, скопировать ее, а затем разархивировать и использовать снова. Хотя это, вероятно, сработает, меня больше интересует теоретическая реализация call/cc и поиск фактического минимального набора функций, которые должен иметь язык, чтобы обеспечить его ручную реализацию.
РЕДАКТИРОВАТЬ 1: Хорошо, люди, помогите мне здесь, это заняло у меня много времени, потому что я не знаю никакой Схемы, но я придумал что-то, что должно помочь нам. Пожалуйста, посмотрите на коды ниже. Первая - это программа на схеме, вторая - та же программа, но на Lua.
Надеюсь, это поможет нам. Я считаю, что мы очень близки.
PS: Эти примеры взяты из первого примера в статье в Википедии о 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 - для тех, кто хочет помочь, есть два легко загружаемых и устанавливаемых инструмента, которые просто работают.
5 ответов
Есть две предпосылки для ручной реализации call/cc согласно цитате из Википедии:
- язык должен поддерживать замыкания
- Вы должны написать свою программу в стиле продолжения передачи (CPS)
Я подозреваю, что вам не понравится #2.
Чтобы написать программу в стиле продолжения:
- Каждая функция должна принимать аргумент продолжения
- Функции должны возвращаться, вызывая их продолжение
Итак, используя k в качестве имени аргумента продолжения функция будет выглядеть так:
function multiplyadd(k, x, y, z) return k(x * y + z) end
Верхний уровень может использовать print как его продолжение, так ссылаясь multiplyadd на верхнем уровне будет выглядеть так:
multiplyadd(print, 2, 4, 1)
С помощью этого леса мы можем определить call/cc как
function callcc(k,f) return f(k,k) end
Обратите внимание, что выше multiplyadd на самом деле читы с * а также + не в CPS. Очень утомительно добавлять все операторы в форме CPS, заменять все функции библиотеки Lua эквивалентами CPS и переводить / генерировать весь ваш код в CPS; подробности смотрите здесь.
Я думаю, вы забыли часть о написании вашей программы в стиле продолжения прохождения. Как только вы это сделаете, call/cc станет тривиальным (на Lua или на любом другом языке), так как продолжение будет явным параметром для всех функций (включая call/cc).
PS: помимо замыканий, вам также нужны правильные хвостовые вызовы для программы в стиле продолжения передачи.
Отвечая на вопрос о планах для call/cc в Lua: Планов для call/cc в Lua нет. Получение продолжения либо слишком дорого, либо требует некоторого анализа кода, выходящего далеко за рамки возможностей компилятора Lua. Также существует проблема в том, что Lua-продолжения могут включать части в C.
Однако с сопрограммами мы уже можем реализовать call/cc1 в Lua (однократное продолжение). Этого достаточно для многих продолжений.
Ключевая фраза
Возможна реализация программ в стиле продолжения
(Выделение мое.) Вы делаете это, беря обычные программы "прямого стиля" и преобразуя их в стиль передачи продолжения (CPS) с помощью преобразования программы, называемого преобразованием CPS. Ключ в том, что преобразование CPS call/cc это простая функция.
Это не практично для программистов. Преобразование CPS имеет два использования:
- Как теоретическая идея для изучения особенностей языка, особенно управляющих операторов
- Как проход в компиляторе, который использует CPS в качестве промежуточного языка
Вы не хотите приближаться к выполнению CPS-преобразований в коде Lua, особенно вручную.
Это возможно: компилятор TypeScript-to-Lua https://github.com/roblox-ts/roblox-ts + call-cc в JS https://github.com/zaoqi/callcc.js/blob/master/callcc.js
Вот мой 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)))