online - Clojure: ¿Cuál es exactamente la posición de la cola para que se repita?

clojure vs scala

Question

Cuál es la definición precisa de "posición de la cola" para recurrir en clojure. Pensaría que sería el último elemento en una expresión S de bucle, pero en el siguiente ejemplo me parece que la Expresión S que comienza con (si ...) está en la posición final, es decir ([PALABRA CLAVE LOOP] [ESTATUTOS VINCULANTES] [SI ESTÁ DECLARACIÓN]).

(= __
  (loop [x 5
         result []]
    (if (> x 0)
      (recur (dec x) (conj result (+ 2 x)))
      result)))

código tomado de http://www.4clojure.com/problem/68

Pregunta estrechamente relacionada: ¿Cómo puedo llamar recurrir en un condicional en Clojure?

Answer 1

Solo para complementar la excelente respuesta de Paul anterior, The Joy of Clojure (ed1) proporciona una tabla (Tabla 7.1) que muestra exactamente dónde está la posición de la cola en varias formas / expresiones, que he reproducido a continuación. Busque dónde aparece la palabra "cola" en cada forma / expresión:

|---------------------+-------------------------------------------+---------------| | Form | Tail Position | recur target? | |---------------------+-------------------------------------------+---------------| | fn, defn | (fn [args] expressions tail) | Yes | | loop | (loop [bindings] expressions tail) | Yes | | let, letfn, binding | (let [bindings] expressions tail) | No | | do | (do expressions tail) | No | | if, if-not | (if test then tail else tail) | No | | when, when-not | (when test expressions tail) | No | | cond | (cond test test tail ... :else else tail) | No | | or, and | (or test test ... tail) | No | | case | (case const const tail ... default tail) | No | |---------------------+-------------------------------------------+---------------|

Answer 2

La posición de cola es una posición de la cual una expresión devolvería un valor. No hay más formularios evaluados después de evaluar la forma en la posición de la cola.

Considera este ejemplo de The Joy of Clojure

(defn absolute-value [x]
  (if (pos? x)
      x        ; "then" clause 
      (- x)))  ; "else" clause

Toma un solo parámetro y lo nombra x. Si x ya es un número positivo, entonces se devuelve x; De lo contrario se devuelve el opuesto de x. La forma if está en la posición de cola de la función porque lo que devuelva, la función completa volverá. La x en la cláusula "entonces" también está en una posición de cola de la función. Pero la x en la cláusula "else" no está en la posición de cola de la función porque el valor de x se pasa a la función -, no se devuelve directamente. La cláusula else en su conjunto (- x) está en una posición de cola.

Del mismo modo en la expresión

(if a
    b
    c)

tanto b como c están en posiciones de cola, porque cualquiera de ellos podría devolverse desde la instrucción if.

Ahora en tu ejemplo

(loop [x 5
       result []]
  (if (> x 0)
    (recur (dec x) (conj result (+ 2 x)))
    result)))

la forma (if ...) está en la posición de cola de la forma (loop ...) y tanto la forma (recur ...) como la forma de result están en la posición de cola de la forma (if ...) .

Por otro lado en la pregunta que vinculaste.

(fn [coll] (let [tail (rest coll)]
             (if (empty tail)
                 1
                 (+ 1 (recur tail)))))

el recur no está en posición de cola porque el (+ 1 ...) se evaluará después de (recur tail) . Por lo tanto el compilador de Clojure da un error.

La posición de la cola es importante porque puede usar la forma recur desde la posición de la cola. Los lenguajes de programación funcionales usualmente recurren a lo que los lenguajes de programación de procedimientos logran mediante bucles. Pero la recursión es problemática, ya que consume espacio en la pila y la recursión profunda puede provocar problemas de acumulación de stack (además de ser lenta). Este problema generalmente se resuelve mediante la optimización de la llamada de cola (TCO) , que elimina la persona que llama cuando la llamada recursiva ocurre en la posición de cola de una función / forma.

Debido a que Clojure está alojado en la JVM y la JVM no es compatible con la optimización de la cola de llamadas, se necesita un truco para hacer la recursión. La forma recur es ese truco, le permite al compilador Clojure hacer algo similar a la optimización de la cola de llamadas. Además, verifica que la recur encuentre en una posición de cola. El beneficio es que puede asegurarse de que la optimización realmente ocurra.