reducir, o recursión explícita?

Question

Recientemente comencé a leer en On Lisp de Paul Graham con un amigo, y nos dimos cuenta de que tenemos opiniones de reducción muy diferentes: creo que expresa un cierto tipo de forma recursiva muy clara y concisamente; él prefiere escribir la recursión muy explícitamente.

Sospecho que estamos en algún contexto y en otro, pero no sabemos dónde está la línea. ¿Cuándo elige una forma sobre la otra y qué piensa al hacer esa elección?

Para ser claros acerca de lo que me refiero a reducir a la recursividad vs explícita, aquí está la misma función implementada en dos ocasiones: (? Ahora estamos Racketeers)

(defun my-remove-if (pred lst) 
    (fold (lambda (left right) 
        (if (funcall pred left) 
         right 
         (cons left right))) 
      lst :from-end t)) 

(defun my-remove-if (pred lst) 
    (if lst 
     (if (funcall pred (car lst)) 
      (my-remove-if pred (cdr lst)) 
      (cons (car lst) (my-remove-if pred (cdr lst)))) 
     '())) 

Me temo que empecé a cabo un intrigante por lo por favor, avíseme si he estropeado la sintaxis de Common Lisp. Esperemos que el punto quede claro incluso si el código es incorrecto.

Answer 1

Si tiene una opción, siempre debe expresar su intención computacional en los términos más abstractos posibles. Esto hace que sea más fácil para un lector averiguar sus intenciones, y hace que sea más fácil para el compilador optimizar su código. En su ejemplo, cuando el compilador sabe trivialmente que está realizando una operación de plegado en virtud de que lo está nombrando, también sabe trivialmente que podría paralelizar las operaciones de la hoja. Sería mucho más difícil para un compilador averiguarlo cuando se escriben operaciones de nivel extremadamente bajo.

Answer 2

Voy a hacer una pregunta ligeramente subjetiva y dar una respuesta altamente subjetiva, ya que Ira ya me dio una respuesta perfectamente pragmática y lógica. :-)

Sé que escribir cosas explícitamente es muy valorado en algunos círculos (los chicos de Python lo hacen parte de su "zen"), pero incluso cuando estaba escribiendo Python nunca lo entendí. Quiero escribir al más alto nivel posible, todo el tiempo. Cuando quiero escribir cosas explícitamente, utilizo el lenguaje ensamblador. ¡El objetivo de usar una computadora (y una HLL) es lograr que haga estas cosas por mí!

Para su ejemplo my-remove-if, al reducir uno mira bien para mí (aparte de las Esquema-ismos como fold y lst :-)). Estoy familiarizado con el concepto de reducir, así que todo lo que necesito entender es averiguar tu f(x,y) -> z. Para la variante explícita, tuve que pensarlo por un segundo: tengo que descubrir el loop yo mismo. La recursividad no es el concepto más difícil, pero creo que es más difícil que "una función de dos argumentos".

Tampoco me importa que se repita una línea completa - (my-remove-if pred (cdr lst)). Creo que me gusta Lisp, en parte porque estoy absolutamente despiadado en DRY, y Lisp me permite estar SECO en ejes que otros idiomas no lo tienen. (Podría poner otro LET en la parte superior para evitar esto, pero luego es más largo y complejo, lo cual creo que es otra razón para preferir la reducción, aunque en este punto podría estar racionalizando).

Creo tal vez los contextos en los que los chicos de Python, por lo menos, no les gusta la funcionalidad implícita serían:

• cuándo se podría esperar que nadie de adivinar el comportamiento (como frobnicate("hello, world", True) - lo que hace verdadera media?), O:
• casos en los que es razonable que la conducta implícita al cambio (como cuando el argumento True se mueve, o se elimina o sustituye con otra cosa, ya que no hay error en tiempo de compilación en los idiomas más dinámicas)

Pero reduce en Lisp falla estos dos criterios: es una abstracción bien entendida que todo el mundo sabe, y que no va a cambiar, al menos no en cualquier escala de tiempo que me preocupe.

Ahora, creo absolutamente que son algunos casos en los que me sería más fácil leer una llamada explícita a una función, pero creo que tendrías que ser muy creativo para idearlos. No puedo pensar en ninguna ocasión, porque reduce y mapcar y amigos son abstracciones realmente buenas.

Answer 3

En Common Lisp, uno prefiere las funciones de orden superior para el cruce de la estructura de datos, el filtrado y otras operaciones relacionadas sobre la recursión. Eso también lo ve en muchas funciones provistas como REDUCE, REMOVE-IF, MAP y otras.

La recurrencia de cola a) no es compatible con la norma, b) puede invocarse de manera diferente con diferentes compiladores de CL yc) el uso de recursividad de cola puede tener efectos secundarios en el código de máquina generado para el código circundante.

A menudo, para ciertas estructuras de datos, muchas de estas operaciones anteriores se implementan con LOOP o ITERATE y se proporcionan como funciones de orden superior. Existe una tendencia a preferir nuevas extensiones de lenguaje (como LOOP e ITERATE) para el código iterativo sobre el uso de recursión para iteración.

(defun my-remove-if (pred list) 
    (loop for item in list 
     unless (funcall pred item) 
     collect item)) 

Aquí es también una versión que utiliza la función Common Lisp REDUCIR:

(defun my-remove-if (pred list) 
    (reduce (lambda (left right) 
      (if (funcall pred left) 
       right 
       (cons left right))) 
      list 
      :from-end t 
      :initial-value nil))