call/cc a Lua - Possibile?

Question

L'articolo di Wikipedia su Continuazione dice:
"In qualsiasi lingua che supporti chiusure, è possibile scrivere programmi in stile passaggio continuo e implementare manualmente call/cc."

O è vero e devo sapere come farlo oppure non è vero e l'affermazione deve essere corretta.

Se questo è vero, mostrami come implementare call/cc in Lua perché non riesco a vedere come.

Penso che sarei in grado di implementare call/cc manualmente se Lua avesse la funzione coroutine.clone come spiegato Qui.

Se le chiusure non sono sufficienti per implementare call/cc, cos'altro è necessario?

Il testo seguente è una lettura facoltativa.
PS:Lua ha continuazioni one-shot con la sua tabella coroutine.Una funzione coroutine.clone mi consentirebbe di clonarlo per chiamarlo più volte, rendendo così possibile call/cc (a meno che non fraintenda call/cc).Tuttavia quella funzione di clonazione non esiste in Lua.Qualcuno sul canale IRC Lua mi ha suggerito di utilizzare la libreria Pluto (implementa la serializzazione) per effettuare il marshalling di una coroutine, copiarla, quindi annullarne il marshalling e riutilizzarla.Anche se probabilmente funzionerebbe, sono più interessato all'implementazione teorica di call/cc e a trovare qual è l'effettivo insieme minimo di funzionalità che un linguaggio deve avere per consentirne l'implementazione manuale.

MODIFICA 1: Ok gente, aiutatemi, mi ci è voluto molto tempo perché non conosco nessuno schema, ma ho trovato qualcosa che dovrebbe aiutarci.Si prega di guardare i codici qui sotto.Il primo è un programma in Scheme, il secondo è lo stesso programma ma in Lua.
Speriamo che questo ci aiuti.Credo che lo siamo molto vicino.

PS:Questi esempi sono presi dal primo esempio in poi l'articolo di Wikipedia su CallCC. Versione dello schema

(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

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

Sto usando DrScheme e Lua per Windows: per chiunque voglia dare una mano, questi sono due strumenti facili da scaricare e installare che funzionano.

Answer 1

Esistono due prerequisiti per implementare manualmente call/cc secondo la citazione di Wikipedia:

1. la lingua deve supportare le chiusure
2. devi scrivere il tuo programma in stile passaggio di continuazione (CPS)

Sospetto che non ti piacerà il numero 2.

Per scrivere il tuo programma in stile passaggio continuo:

1. Ogni funzione deve accettare un argomento di continuazione
2. Le funzioni devono restituire chiamando la loro continuazione

Quindi, usando k come nome dell'argomento di continuazione, una funzione sarebbe simile a:

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

Il livello superiore potrebbe utilizzare print come sua continuazione, così invocante multiplyadd al livello più alto sarebbe simile a:

multiplyadd(print, 2, 4, 1)

Con questa impalcatura potremmo definire call/cc come

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

Si tenga presente quanto sopra multiplyadd in realtà tradisce da allora * E + non sono in CPS.È molto noioso aggiungere tutti gli operatori nel formato CPS, sostituire tutte le funzioni della libreria Lua con equivalenti CPS e tradurre/generare tutto il codice in CPS;Vedere dettagli qui.

Answer 2

Immagino che tu abbia dimenticato la parte sulla scrittura del tuo programma in stile continuazione.Una volta che lo fai, Call/CC è banale (in LUA o in qualsiasi altra lingua), poiché la continuazione sarà un parametro esplicito per tutte le funzioni (Call/CC incluso).

PS:Oltre alle chiusure, hai anche bisogno di chiamate di coda adeguate per programmare in stile continuazione.

Answer 3

Rispondendo alla domanda sui piani per call/cc in Lua:Non ci sono piani per call/cc a Lua.Catturare una continuazione è troppo costoso o richiede un'analisi del codice ben oltre ciò che può fare il compilatore Lua.C'è anche il problema che le continuazioni di Lua possono includere parti in C.

Con le coroutine, tuttavia, possiamo già implementare call/cc1 in Lua (continuazioni one-shot).Questo è abbastanza buono per molti usi delle continuazioni.

Answer 4

La frase chiave è

È possibile implementare programmi in stile di passaggio di continuazione

(Il corsivo è mio.) Puoi farlo prendendo normali programmi di "stile diretto" e convertendoli in stile a passaggio di continuazione (CPS) mediante una trasformazione del programma chiamata Trasformazione CPS.La chiave è che il CPS si trasforma di call/cc è una funzione semplice.

Questo non è pratico per i programmatori. La trasformazione CPS ha due usi:

• Come idea teorica per studiare le caratteristiche del linguaggio, in particolare gli operatori di controllo
• Come passaggio in un compilatore che utilizza CPS come linguaggio intermedio

Non vuoi avvicinarti nemmeno lontanamente alle trasformazioni CPS sul codice Lua, soprattutto non a mano.

Answer 5

è possibile:Compilatore da TypeScript a Lua https://github.com/roblox-ts/roblox-ts + Call-CC in JS https://github.com/zaoqi/callcc.js/blob/master/callcc.js

Answer 6

Ecco il mio schema di conversione cps, passagli semplicemente tutte le funzioni che desideri convertire.

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