call/cc en lua-posible?

continuations callcc

Question

El artículo de Wikipedia sobre la Continuation dice:
"En cualquier lenguaje que admita cierres , es posible escribir programas en estilo de paso continuo e implementar manualmente call / cc ".

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

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

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

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 de un solo disparo con su mesa coroutine. Una función coroutine.clone me permitiría clonarla para llamarla varias veces, haciendo así posible que 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 IRC de Lua sugirió que usara la biblioteca de Plutón (implementa la serialización) para reunir a una coroutine, copiarla y luego desarmarla 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 debe tener un lenguaje para permitir su implementación manual.

EDITAR 1: Ok, gente, ayúdenme aquí, esto me llevó mucho tiempo porque no conozco ningún Esquema, pero se me ocurrió algo que debería ayudarnos. Por favor, mire los códigos a continuación. El primero es un programa en Scheme, el segundo es el mismo programa pero en Lua.
Esperemos que esto nos ayude. Creo que estamos muy unidos.

PD: Estos ejemplos se han tomado del primer ejemplo del artículo de Wikipedia sobre CallCC . Versión de 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, son dos herramientas fáciles de descargar e instalar que simplemente funcionan.

Answer 1

Aquí está mi cps-convert en esquema, solo pásale todas las funciones que desee 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)))

Answer 2

Hay dos requisitos previos para implementar manualmente call / cc según la cita de Wikipedia:

1. el idioma debe soportar cierres
2. debe escribir su programa en estilo de paso de continuación (CPS)

Sospecho que no te gustará el # 2.

Para escribir tu programa en estilo de paso continuo:

1. Cada función debe tener un argumento de continuación.
2. Las funciones deben regresar llamando a su continuación.

Entonces, usando k como el nombre del argumento de continuación, una función se vería como:

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

El nivel superior podría usar la 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 podríamos definir call / cc como

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

Tenga en cuenta que los trucos multiplyadd anteriores en realidad ya que * y + no están en CPS. Es muy tedioso agregar todos los operadores en forma de CPS, reemplazar todas las funciones de la biblioteca Lua con equivalentes de CPS y traducir / generar todo su código a CPS; Vea los detalles aquí .

Answer 3

La frase clave es

Es posible implementar programas en estilo de paso de continuación.

(Enfatice, mío). Hágalo tomando programas regulares de "estilo directo" y convirtiéndolos al estilo de paso de continuación (CPS) mediante una transformación de programa llamada transformación de CPS . La clave es que la transformación CPS de call/cc es una función simple.

Esto no es práctico para los programadores. La transformación CPS tiene dos usos:

• Como una idea teórica para estudiar las características del lenguaje, especialmente los operadores de control.
• Como un pase en un compilador que usa CPS como lenguaje intermedio

No desea ir a ninguna parte cerca de hacer transformaciones CPS en el código Lua, especialmente no a mano.

Answer 4

Respondiendo a la pregunta sobre los planes para call / cc en Lua: No hay planes para call / cc en Lua. Capturar una continuación es demasiado costoso o requiere un análisis de código más allá de lo que puede hacer el compilador de Lua. También existe el problema de que las continuaciones de Lua pueden incluir partes en C.

Sin embargo, con las rutinas, ya podemos implementar call / cc1 en Lua (continuaciones de un disparo). Eso es suficiente para muchos usos de las continuaciones.

Answer 5

Supongo que olvidaste la parte sobre escribir tu programa en estilo de paso continuo. Una vez que haga eso, call / cc es trivial (en Lua o en cualquier otro idioma), ya que la continuación será un parámetro explícito para todas las funciones (call / cc incluido).

PD: además de los cierres, también necesita llamadas de cola adecuadas para programar en estilo de paso continuo.