Lua での call/cc - 可能ですか?

https://stackoverflow.com/questions/2827620

26-09-2019
|

質問

ウィキペディアの記事では、継続言います：
「サポートされている言語であれば、 クロージャ, 、継続渡しスタイルでプログラムを書くことが可能です。 call/cc を手動で実装する."

それは真実であり、その方法を知る必要があるか、それとも真実ではなく、その発言を修正する必要があるかのどちらかです。

これが本当なら、Lua で call/cc を実装する方法がわからないので、その方法を教えてください。

説明したように、Lua に coroutine.clone 関数があれば、call/cc を手動で実装できると思います。ここ.

call/cc を実装するのにクロージャだけでは不十分な場合、他に何が必要でしょうか?

以下のテキストは任意で読むことができます。
追記：Lua のコルーチンテーブルにはワンショットの継続があります。coroutine.clone 関数を使用すると、クローンを作成して複数回呼び出すことができるため、実質的に call/cc が可能になります (call/cc を誤解していない限り)。ただし、そのクローン作成機能は Lua には存在しません。Lua IRC チャネルの誰かが、Pluto ライブラリ (シリアル化を実装している) を使用してコルーチンをマーシャリングし、コピーし、アンマーシャリングして再度使用することを提案しました。それはおそらく機能するでしょうが、私は call/cc の理論的な実装と、手動実装を可能にするために言語に必要な実際の最小機能セットが何かを見つけることにもっと興味があります。

編集1: わかりました、皆さん、ここで私を助けてください。私はスキームを何も知らないので、これには長い時間がかかりましたが、私たちを助けるはずのものを思いつきました。以下のコードを見てください。1 つ目は Scheme のプログラムで、2 つ目は同じプログラムですが Lua です。
これが私たちの助けになれば幸いです。私たちはそうだと信じています とても 近い。

追記：これらの例は、最初の例から抜粋されたものです。 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...

私は Windows 用の DrScheme と Lua を使用しています。これらをサポートしたい人のために、これら 2 つの簡単にダウンロードしてインストールできるツールを紹介します。

解決

Wikipedia の引用によると、call/cc を手動で実装するには 2 つの前提条件があります。

言語はクロージャをサポートする必要があります
プログラムは継続渡しスタイル (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を含む）。

追伸：閉鎖に加えて、継続的なパススタイルでプログラムするための適切なテールコールも必要です。

Lua での call/cc の計画に関する質問への回答:Lua では call/cc の予定はありません。継続をキャプチャするにはコストがかかりすぎるか、Lua コンパイラーが実行できる範囲をはるかに超えるコード分析が必要になります。Lua の継続には C の部分が含まれる可能性があるという問題もあります。

ただし、コルーチンを使用すると、Lua で call/cc1 をすでに実装できます (ワンショット継続)。継続の多くの用途にはこれで十分です。

キーフレーズは

でプログラムを実装することが可能です 継続渡しスタイル

(強調は私です。) これを行うには、通常の「直接スタイル」プログラムを取得し、それを継続渡しスタイル (CPS) と呼ばれるプログラム変換によって変換します。 CPS変換. 。重要なのは、次の CPS 変換です。 call/cc は単純な関数です。

これはプログラマにとって現実的ではありません。 CPS 変換には 2 つの用途があります。

言語機能、特に制御演算子を研究するための理論的アイデアとして
CPS を中間言語として使用するコンパイラのパスとして

特に手動ではなく、Lua コードで CPS 変換を実行することには近づきたくありません。

それが可能だ：TypeScript から Lua へのコンパイラー https://github.com/roblox-ts/roblox-ts + jsのcall-cc 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)))

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow