llamada/cc en Lua - ¿Es posible?

Question

El artículo de Wikipedia sobre Continuación dice:
"En cualquier idioma que admita cierres, es posible escribir programas en estilo de paso de continuación y implementar manualmente llamada/cc."

O eso es cierto y necesito saber cómo hacerlo o no es cierto y es necesario corregir esa afirmación.

Si esto es cierto, muéstrame cómo implementar call/cc en Lua porque no veo cómo.

Creo que podría implementar call/cc manualmente si Lua tuviera la función coroutine.clone como se explica aquí.

Si los cierres no son suficientes para implementar call/cc, ¿qué más se necesita?

El texto a continuación es de lectura opcional.
PD.:Lua tiene continuaciones one-shot con su tabla de rutinas.Una función coroutine.clone me permitiría clonarlo para llamarlo varias veces, haciendo así posible call/cc (a menos que entienda mal call/cc).Sin embargo, esa función de clonación no existe en Lua.Alguien en el canal Lua IRC sugirió que usara la biblioteca Plutón (implementa la serialización) para organizar una rutina, copiarla y luego desorganizarla y usarla nuevamente.Si bien eso probablemente funcionaría, estoy más interesado en la implementación teórica de call/cc y en encontrar cuál es el conjunto mínimo real de características que un lenguaje debe tener para permitir su implementación manual.

EDITAR 1: Ok gente, ayúdenme aquí, esto me tomó mucho tiempo porque no conozco ningún esquema, pero se me ocurrió algo que debería ayudarnos.Mire los códigos a continuación.El primero es un programa en Scheme, el segundo es el mismo programa pero en Lua.
Ojalá esto nos ayude.creo que lo somos muy cerca.

PD.:Estos ejemplos están tomados del primer ejemplo de el artículo de Wikipedia sobre CallCC. Versión del esquema

(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

versión 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...

Estoy usando DrScheme y Lua para Windows; para cualquiera que quiera ayudar, hay dos herramientas fáciles de descargar e instalar que simplemente funcionan.

Answer 1

Hay dos requisitos previos para aplicar manualmente la llamada / cc por la cita de Wikipedia:

1. los cierres de soporte de idioma debe
2. Debe escribir el programa en la continuación pasando estilo (CPS)

Sospecho que no lo hará como # 2.

Para escribir el programa en el estilo que pasa continuación:

1. Cada función debe tener un argumento continuación
2. Funciones debe devolver llamando a su continuación

Por lo tanto, el uso de k como el nombre del argumento continuación, una función se vería así:

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

El nivel superior podría utilizar print como su continuación, por lo que la invocación de multiplyadd en el nivel superior se vería así:

multiplyadd(print, 2, 4, 1)

Con ese andamiaje que podríamos definir de llamada / cc como

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

Tenga en cuenta que la anterior multiplyadd realidad engaña desde * y + no están en CPS. Es muy tedioso para añadir todos los operadores en forma de CPS, sustituir todas las funciones de la biblioteca de Lua con equivalentes de CPS, y traducir / generar todo el código de CPS; ver detalles aquí .

Answer 2

Creo que se ha olvidado la parte de escribir su programa de pasada continuidad estilo. Una vez hecho eso, llamada / cc es trivial (en Lua o en cualquier otro idioma), como la continuación será un parámetro explícito a todas las funciones (llamada / cc incluido).

PS: además de los cierres, también es necesario llamadas de cola propias a la continuación del programa en pasando estilo.

Answer 3

En respuesta a la pregunta sobre los planes de llamada / cc en Lua: No hay planes de llamada / cc en Lua. La captura de una continuación es demasiado caros o requieren algún código Análsis mucho más allá de lo que el compilador Lua puede hacer. También existe el problema de que continuaciones Lua pueden incluir partes en C.

Con corrutinas, sin embargo, ya podemos poner en práctica llamada / CC1 en Lua (continuaciones de un solo disparo). Eso es lo suficientemente bueno para muchos usos de continuaciones.

Answer 4

La frase clave es

  

Es posible implementar programas en estilo de continuación que pasa

(El subrayado es mío.) Esto se hace mediante la adopción de programas regulares "estilo" directo y convertirlos a continuación el estilo de paso (CPS) mediante una transformación del programa llamado CPS transformada . La clave es que los CPS transforman de call/cc es una función simple.

.

Esto no es práctico para los programadores Los CPS transforman tiene dos usos:

• A medida que cuenta con una idea teórica para el estudio de la lengua, especialmente el control de los operadores
• Como un paso en un compilador que utiliza CPS como un lenguaje intermedio

Usted no quiere ir en cualquier lugar cerca de CPS haciendo transforma en código Lua, especialmente no a mano.

Answer 5

es posible: Mecanografiado-a-Lua Compiler https://github.com/roblox-ts/roblox-ts + call-cc en JS https://github.com/zaoqi/callcc Js / blob / master / callcc.js

Answer 6

Aquí está mi cps-convertir en el esquema, sólo tiene que pasar cada función que desea convertir.

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