Ligue/CC em Lua - Possível?
-
26-09-2019 - |
Pergunta
O artigo da Wikipedia sobre Continuação diz:
"Em qualquer idioma que suporta fechamentos, é possível escrever programas no estilo de passagem de continuação e Implementar manualmente chamado/cc."
Ou isso é verdade e eu preciso saber como fazê -lo ou não é verdadeiro e essa afirmação precisa ser corrigida.
Se isso for verdade, mostre -me como implementar a chamada/cc em Lua porque não consigo ver como.
Acho que seria capaz de implementar a chamada/CC manualmente se Lua tivesse a função coroutina. aqui.
Se os fechamentos não forem suficientes para implementar a chamada/CC, o que mais é necessário?
O texto abaixo é leitura opcional.
PS: Lua tem continuações de um tiro com sua tabela de coroutina. Uma função coroutine.Clone me permitiria cloná -la para chamá -la várias vezes, tornando efetivamente a chamada/CC (a menos que eu não entenda a chamada/CC). No entanto, essa função de clonagem não existe em Lua. Alguém no canal Lua IRC sugeriu que eu usasse a biblioteca Plutão (ele implementa a serialização) para marcar uma coroutina, copiá -la e depois soltá -la e usá -la novamente. Embora isso provavelmente funcione, estou mais interessado na implementação teórica do Call/CC e ao encontrar qual é o conjunto mínimo real de recursos que um idioma precisa ter para permitir sua implementação manual.
Editar 1: Ok, pessoal, me ajude aqui, isso levou muito tempo porque não conheço nenhum esquema, mas criei algo que deve nos ajudar. Por favor, olhe para os códigos abaixo. O primeiro é um programa em esquema, o segundo é o mesmo programa, mas em Lua.
Espero que isso nos ajude. Eu acredito que somos muito perto.
PS: esses exemplos são tirados do primeiro exemplo em O artigo da Wikipedia no calcc.
Versão do 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
Versão 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...
Estou usando o DRSCHEME e o Lua para o Windows - para quem deseja ajudar essas são duas ferramentas fáceis de baixar e instalar que apenas funcionam.
Solução
Existem dois pré -requisitos para implementar manualmente a chamada/cc de acordo com a citação da Wikipedia:
- o idioma deve apoiar o fechamento
- Você deve escrever seu programa no estilo de passagem de continuação (CPS)
Eu suspeito que você não vai gostar do #2.
Para escrever seu programa no estilo de passagem de continuação:
- Cada função deve assumir um argumento de continuação
- As funções devem retornar chamando sua continuação
Então, usando k
Como o nome do argumento de continuação, uma função seria:
function multiplyadd(k, x, y, z) return k(x * y + z) end
O Toplevel pode usar print
como sua continuação, tão invocando multiplyadd
no nível superior seria:
multiplyadd(print, 2, 4, 1)
Com esse andaime, poderíamos definir chamada/cc como
function callcc(k,f) return f(k,k) end
Observe que o acima multiplyadd
Na verdade, trapaceia desde então *
e +
não estão no CPS. É muito tedioso adicionar todos os operadores no formulário CPS, substituir todas as funções da biblioteca Lua por equivalentes de CPS e traduzir/gerar todo o seu código para o CPS; Vejo detalhes aqui.
Outras dicas
Acho que você esqueceu a parte de escrever seu programa no estilo de passagem de continuação. Depois de fazer isso, a chamada/CC é trivial (em Lua ou em qualquer outro idioma), pois a continuação será um parâmetro explícito para todas as funções (ligue/CC incluído).
PS: Além do fechamento, você também precisa de chamadas de cauda adequadas para programar no estilo de passagem de continuação.
Respondendo à pergunta sobre os planos de chamada/CC em Lua: não há planos para chamada/CC em Lua. A captura de uma continuação é muito cara ou exige algum análise de código muito além do que o compilador da Lua pode fazer. Há também o problema de que as continuações da Lua podem incluir peças em C.
Com as coroutinas, no entanto, já podemos implementar a chamada/CC1 em Lua (continuação de um tiro). Isso é bom o suficiente para muitos usos das continuações.
A frase -chave é
É possível implementar programas em estilo de passagem de continuação
(Ênfase mina.) Você faz isso levando programas regulares de "estilo direto" e convertendo-os em estilo de passagem de continuação (CPS) por uma transformação do programa chamada de CPS se transforma. A chave é que a transformação do CPS de call/cc
é uma função simples.
Isso não é prático para programadores. A transformação do CPS tem dois usos:
- Como uma idéia teórica para estudar recursos de linguagem, especialmente operadores de controle
- Como um passe em um compilador que usa o CPS como uma linguagem intermediária
Você não quer ir nem perto de fazer transformações do CPS no código Lua, especialmente não manualmente.
É possível: compilador digital para lua https://github.com/roblox-ts/roblox-ts + Call-CC em JS https://github.com/zaoqi/callcc.js/blob/master/callcc.js
Aqui está o meu CPS-convert em esquema, basta passar por todas as funções que você deseja converter.
(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)))