Una función de recopilación eficiente en Common Lisp

Question

Estoy aprendiendo Lisp y he escrito la siguiente función para recopilar una lista de resultados.

(defun collect (func args num) 
    (if (= 0 num) 
    () 
     (cons (apply func args) 
     (collect func args (- num 1))))) 

Produjo una salida similar a la función de lazo incorporada.

CL-USER> (collect #'random '(5) 10) 
(4 0 3 0 1 4 2 1 0 0) 
CL-USER> (loop repeat 10 collect (random 5)) 
(3 3 4 0 3 2 4 0 0 0) 

Sin embargo, mi función Collect sopla la pila cuando intento para generar una lista de 100.000 elementos de larga

CL-USER> (length (collect #'random '(5) 100000)) 
Control stack guard page temporarily disabled: proceed with caution 

Mientras que la versión bucle no

CL-USER> (length (loop repeat 100000 collect (random 5))) 
100000 

¿Cómo puedo hacer que mi versión más eficiente en cuanto a espacio, ¿hay alternativas para el consumo? Creo que es una cola recursiva. Estoy usando sbcl. Cualquier ayuda sería genial.

Answer 1

Las implementaciones de Common Lisp no son requeridas por el estándar ANSI para hacer la optimización de la cola de llamada; sin embargo, la mayoría de los que valen la pena (incluido el SBCL) se optimizan.

Su función, por otro lado, no es la cola recursiva.Se puede convertir en uno utilizando el truco común de introducir un parámetro adicional para acumular el resultado intermedio:

 
    (defun collect (func args num) 
     (labels ((frob (n acc) 
       (if (= 0 n) 
        acc 
        (frob (1- n) (cons (apply func args) acc))))) 
     (frob num nil))) 

(La parámetros FUNC y ARGS original son eliminados en la función local ya que son constantes con recpect a ella)

Answer 2

Bueno, la alternativa a la recursividad es la iteración.

Debe saber que Common Lisp no requiere recurrencia de cola desde sus implementadores, a diferencia del esquema.

(defun mycollect (func args num) 
    (let ((accumulator '()))  ; it's a null list. 
    (loop for i from 1 to num 
     do 
     ;;destructively cons up the accumulator with the new result + the old accumulator 
     (setf accumulator     
     (cons (apply func args) accumulator))) 
    accumulator))    ; and return the accumulator 

Answer 3

No, no es cola recursiva. Ni ANSI Common Lisp dice nada al respecto, ni su código:

(defun collect (func args num) 
    (if (= 0 num) 
    () 
     (cons (apply func args) 
      (collect func args (- num 1))))) 

Si nos fijamos en el código, hay una CONS alrededor de su llamada a recoger. Este CONS recibe el valor de la llamada recursiva a COLLECT. Entonces COLLECT no puede ser recursivo de cola. Es relativamente simple reescribir su función a algo que parece recursivo de cola introduciendo una variable de acumulador. La variada literatura de Lisp o Scheme debería describir eso.

En Common Lisp la forma predeterminada para programar un cálculo iterativo es mediante el uso de una de las varias construcciones iterativas: DO, dotimes, DOLIST, LOOP, MAP, mapcar, ...

El estándar Common Lisp no lo hace proporcionar optimización de llamadas de cola (TCO). Debería especificarse qué debería hacer TCO en presencia de varias otras características del lenguaje. Por ejemplo, el enlace dinámico y las variables especiales tienen un efecto en TCO. Pero el estándar Common Lisp no dice nada sobre el TCO en general y sobre los posibles efectos del TCO. TCO no es parte del estándar ANSI Common Lisp.

Varias implementaciones Common Lisp tienen una forma de habilitar varias optimizaciones de cola de cola con modificadores de compilador. Tenga en cuenta que tanto la forma de habilitarlos como las limitaciones son específicas de la implementación.

Resumen: En Common Lisp utiliza construcciones de iteración y no recursividad.

(defun collect (func args num) 
    (loop repeat num 
     collect (apply #'func args))) 

Bonificación adicional: es más fácil de leer.