21

Wikipedia 关于Continuation的文章说：
“在任何支持闭包的语言中，都可以以连续传递风格编写程序并手动实现 call/cc。”

要么是真的，我需要知道如何去做，要么是不正确的，需要纠正这种说法。

如果这是真的，请告诉我如何在 Lua 中实现 call/cc，因为我看不到如何。如果 Lua 有 coroutine.clone 函数，

我想我可以手动实现 call/cc 。 如果闭包不足以实现 call/cc 那么还需要什么？

下面的文字是可选的阅读。
PS：Lua 的协程表有一次性延续。coroutine.clone 函数将允许我克隆它以多次调用它，从而有效地使 call/cc 成为可能（除非我误解了 call/cc）。然而，该克隆功能在 Lua 中不存在。Lua IRC 频道上有人建议我使用 Pluto 库（它实现序列化）来编组一个协程，复制它，然后解组它并再次使用它。虽然这可能可行，但我更感兴趣的是 call/cc 的理论实现，以及找到一种语言为了允许其手动实现而需要具备的实际最小功能集是什么。

编辑1：好的，大家帮帮我，这花了我很长时间，因为我不知道任何Scheme，但我想出了一些可以帮助我们的东西。请看下面的代码。第一个是 Scheme 中的程序，第二个是同一个程序，但在 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



路亚版

-- 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...



我正在使用适用于 Windows 的 DrScheme 和 Lua - 对于任何想要帮助解决这些问题的人来说，这两个工具易于下载和安装，并且可以正常工作。

4

6 回答 6

18

根据维基百科的引用，手动实现 call/cc 有两个先决条件：

  1. 语言必须支持闭包
  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)

有了这个脚手架，我们可以将 call/cc 定义为

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

请注意，上述内容multiplyadd实际上是作弊，因为*并且+不在 CPS 中。以 CPS 形式添加所有运算符，将所有 Lua 库函数替换为 CPS 等效项，并将所有代码转换/生成到 CPS 是非常繁琐的；在此处查看详细信息。

于 2010-05-13T16:28:08.997 回答
17

我猜你忘记了以连续传递风格编写程序的部分。一旦你这样做了， call/cc 是微不足道的（在 Lua 或任何其他语言中），因为延续将是所有函数的显式参数（包括 call/cc）。

PS：除了闭包之外，您还需要适当的尾调用以继续传递样式的程序。

于 2010-05-13T16:04:12.657 回答
8

回答有关 Lua 中 call/cc 计划的问题： Lua 中没有 call/cc 计划。捕获一个延续要么太昂贵，要么需要一些代码分析，远远超出了 Lua 编译器的能力。还有一个问题是 Lua 延续可能包含 C 中的部分。

然而，使用协程，我们已经可以在 Lua 中实现 call/cc1（一次性延续）。这对于延续的许多用途来说已经足够了。

于 2010-05-14T16:56:09.723 回答
2

关键短语是

可以以延续传递风格实现程序

（强调我的。）您可以通过使用常规的“直接样式”程序并通过称为CPS 转换的程序转换将它们转换为连续传递样式 (CPS) 来做到这一点。关键是CPS变换call/cc是一个简单的函数。

这对程序员来说是不切实际的。 CPS 变换有两个用途：

  • 作为研究语言特征，尤其是控制算子的理论思想
  • 作为使用 CPS 作为中间语言的编译器的传递

您不想在 Lua 代码上进行 CPS 转换，尤其是手动转换。

于 2010-05-13T21:27:49.330 回答
0

有可能：TypeScript-to-Lua 编译器https://github.com/roblox-ts/roblox-ts + JS 中的 call-cc https://github.com/zaoqi/callcc.js/blob/master/callcc。 js

于 2019-07-29T12:01:06.077 回答
-2

这是我的 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)))
于 2011-11-21T16:29:15.770 回答