call/cc in Lua - Möglich?

Question

Der Wikipedia-Artikel zum Thema Fortsetzung sagt:
„In jeder Sprache, die unterstützt Schließungen, ist es möglich, Programme im Continuation-Passing-Stil zu schreiben und Call/CC manuell implementieren."

Entweder ist das wahr und ich muss wissen, wie es geht, oder es ist nicht wahr und diese Aussage muss korrigiert werden.

Wenn dies zutrifft, zeigen Sie mir bitte, wie man call/cc in Lua implementiert, da ich nicht weiß, wie.

Ich denke, ich könnte call/cc manuell implementieren, wenn Lua die Funktion coroutine.clone wie erläutert hätte Hier.

Wenn Schließungen nicht ausreichen, um call/cc zu implementieren, was wird dann noch benötigt?

Der folgende Text ist optionale Lektüre.
P.S.:Lua verfügt über One-Shot-Fortsetzungen mit seiner Coroutine-Tabelle.Eine coroutine.clone-Funktion würde es mir ermöglichen, sie zu klonen, um sie mehrmals aufzurufen, wodurch call/cc effektiv möglich wäre (es sei denn, ich verstehe call/cc falsch).Allerdings gibt es diese Klonfunktion in Lua nicht.Jemand im Lua-IRC-Kanal schlug vor, dass ich die Pluto-Bibliothek (sie implementiert die Serialisierung) verwende, um eine Coroutine zu marsalieren, sie zu kopieren und sie dann zu entmarshalieren und erneut zu verwenden.Während das wahrscheinlich funktionieren würde, bin ich mehr an der theoretischen Implementierung von call/cc interessiert und daran, herauszufinden, welche Funktionen eine Sprache tatsächlich mindestens haben muss, um ihre manuelle Implementierung zu ermöglichen.

EDIT 1: Ok Leute, helft mir hier, das hat lange gedauert, weil ich kein Schema kenne, aber ich habe mir etwas ausgedacht, das uns helfen sollte.Bitte schauen Sie sich die Codes unten an.Das erste ist ein Programm in Scheme, das zweite ist dasselbe Programm, aber in Lua.
Hoffentlich hilft uns das weiter.Ich glaube, das sind wir sehr schließen.

P.S.:Diese Beispiele stammen aus dem ersten Beispiel der Wikipedia-Artikel zu CallCC. Schemaversion

(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-Version

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

Ich verwende DrScheme und Lua für Windows – für alle, die helfen möchten, sind dies zwei einfach herunterzuladende und zu installierende Tools, die einfach funktionieren.

Answer 1

Es gibt zwei Voraussetzungen, um call/cc gemäß dem Wikipedia-Zitat manuell zu implementieren:

1. Die Sprache muss Abschlüsse unterstützen
2. Sie müssen Ihr Programm im Continuation-Passing-Stil (CPS) schreiben.

Ich vermute, dass Ihnen #2 nicht gefallen wird.

So schreiben Sie Ihr Programm im Continuation-Passing-Stil:

1. Jede Funktion muss ein Fortsetzungsargument annehmen
2. Funktionen müssen zurückkehren, indem sie ihre Fortsetzung aufrufen

Also, verwenden k Als Name des Fortsetzungsarguments würde eine Funktion wie folgt aussehen:

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

Die oberste Ebene könnte verwenden print als seine Fortsetzung, so beschwörend multiplyadd auf oberster Ebene würde so aussehen:

multiplyadd(print, 2, 4, 1)

Mit diesem Gerüst könnten wir call/cc definieren als

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

Beachten Sie das oben Gesagte multiplyadd eigentlich betrügt seitdem * Und + sind nicht im CPS.Es ist sehr mühsam, alle Operatoren in CPS-Form hinzuzufügen, alle Lua-Bibliotheksfunktionen durch CPS-Äquivalente zu ersetzen und Ihren gesamten Code in CPS zu übersetzen/generieren;sehen Details hier.

Answer 2

Ich denke, Sie haben den Teil über das Schreiben Ihres Programms im kontinuierlichen Passstil vergessen.Sobald Sie dies getan haben, ist Call/CC trivial (in Lua oder in einer anderen Sprache), da die Fortsetzung ein expliziter Parameter für alle Funktionen ist (Call/CC enthalten).

PS:Neben Schließungen benötigen Sie auch geeignete Schwanzaufrufe zum Programm zum Fortsetzung des Passing -Stils.

Answer 3

Beantwortung der Frage zu Plänen für Call/CC in Lua:Es gibt keine Pläne für einen Anruf/CC in Lua.Das Erfassen einer Fortsetzung ist entweder zu teuer oder erfordert eine Codeanalyse, die weit über die Möglichkeiten des Lua-Compilers hinausgeht.Es besteht auch das Problem, dass Lua-Fortsetzungen Teile in C enthalten können.

Mit Coroutinen können wir jedoch bereits call/cc1 in Lua implementieren (One-Shot-Fortsetzungen).Das reicht für viele Verwendungszwecke von Fortsetzungen aus.

Answer 4

Der Schlüsselsatz ist

Es ist möglich, Programme in zu implementieren Continuation-Passing-Stil

(Hervorhebung von mir.) Sie tun dies, indem Sie reguläre Programme im „Direct-Style“ nehmen und sie durch eine Programmtransformation namens „Continuation-Passing-Style“ (CPS) umwandeln CPS-Transformation.Der Schlüssel liegt in der CPS-Transformation call/cc ist eine einfache Funktion.

Dies ist für Programmierer nicht praktikabel. Die CPS-Transformation hat zwei Verwendungszwecke:

• Als theoretische Idee zum Studium von Sprachmerkmalen, insbesondere Kontrolloperatoren
• Als Durchgang in einem Compiler, der CPS als Zwischensprache verwendet

Sie möchten nicht annähernd CPS-Transformationen für Lua-Code durchführen, insbesondere nicht von Hand.

Answer 5

es ist möglich:TypeScript-zu-Lua-Compiler https://github.com/roblox-ts/roblox-ts + Call-CC in JS https://github.com/zaoqi/callcc.js/blob/master/callcc.js

Answer 6

Hier ist mein CPS-Konvertierungsschema. Übergeben Sie es einfach an jede Funktion, die Sie konvertieren möchten.

(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)))