¿Alguien sabe si call/cc se puede implementar con solo lambdas y cierres?¿Se puede implementar call-with-current-continuation solo con lambdas y cierres?
Parece que call/cc interrumpe el flujo del programa (como una excepción) pero las lambdas y los cierres no pueden hacer eso. Por lo tanto, creo que call/cc no se puede implementar a través de lambdas y cierres.
¿Alguna idea más?
La pregunta no es particularmente clara, ya que ¿qué significa exactamente "implementado con solo lambdas y cierres"?
En cualquier caso, las continuaciones se pueden utilizar en cualquier idioma con cierres al escribir manualmente en continuation passing style. Entonces, la traducción automática a este formulario se puede implementar ampliando el compilador, que Lisps normalmente permite a nivel de usuario a través de macros. Por ejemplo, consulte cl-cont, una biblioteca que implementa continuaciones para Common Lisp, que es un lenguaje que no las tiene incorporadas.
Continuidades eficientes y generalizadas como en Scheme es probable que se implementen en un nivel inferior directamente relacionado con el programa pila, pero esto no es un requisito, solo una optimización.
CPS solo funcionará si el idioma subyacente admite llamadas finales (que debería, en el caso de Scheme). – leppie
Generalmente cierto, pero en principio puede borrar el marco de pila manualmente devolviendo la continuación y los argumentos hacia arriba a algún bucle "CPS-driver". – Ramarren
CPS funcionará, pero el problema es que funciona * solo * para el código que usted controla (y puede CPS). Por ejemplo, lidiar con bibliotecas se vuelve difícil, ya que debe tratarlas como llamadas extranjeras, incluso si están en su idioma. (Y por cierto, esos "bucles SPC-driver" se conocen generalmente como tampolining.) –
En Scheme puede implementar call/cc usando lambdas al convertir a estilo de paso de continuación (CPS). Al convertir en CPS, cada ocurrencia de call/cc puede ser sustituido por el siguiente equivalente:
(lambda (f k) (f (lambda (v k0) (k v)) k))
donde k es la continuación ser salvado, y (lambda (v k0) (k v)) es el procedimiento de escape que restaura esta continuación (cualquiera que sea la continuación k0 que es activo cuando se llama, se descarta).
Por lo tanto, para responder a su pregunta para Scheme: sí, se puede hacer.
¿Es así como generalmente se implementa call/cc en un lenguaje de optimización de cola como Scheme? Como una macro? – Byte
No, para una compatibilidad de continuación completa (iow no single shot ones) necesitará la captura de pila y montón. Todo esto sucede en un nivel muy bajo. – leppie
@leppie Me encantaría volver a votar eso como una respuesta. –
@Frank Shearar: lo haría si realmente los hubiera implementado con éxito :) Las continuas son difíciles, ¡vamos de compras! – leppie