Clojure: cos'è esattamente la posizione della coda per ricorrere?

Question

Che cosa è la definizione precisa di "posizione di coda" per ricorrere in clojure. Penserei che sarebbe l'ultimo elemento in un'espressione S in loop, ma nell'esempio seguente mi sembra che l'S-Expression che inizia con (if ...) sia in posizione di coda cioè ([LOOP KEYWORD] [VINCOLAMENTI STATALI] [SE DICHIARAZIONE]). codice

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

presa da http://www.4clojure.com/problem/68

questione strettamente corrispondenti How can I call recur in an if conditional in Clojure?

Answer 1

La posizione coda è una postazione di espressione che riporta un valore da. Non ci sono più forme valutate dopo che la forma nella posizione della coda è stata valutata.

Considerate questo esempio da The Joy of Clojure

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

Ci vuole un unico parametro e lo nomina x. Se x è già un numero positivo, allora x è restituito; altrimenti viene restituito il contrario di x. Il modulo if si trova nella posizione di coda della funzione perché qualsiasi cosa restituisca, verrà restituita l'intera funzione . La x nella clausola "then" si trova anche in una posizione di coda della funzione. Ma la x nella clausola "else" non si trova nella posizione di coda della funzione poiché il valore di x viene passato alla funzione -, non viene restituito direttamente. La clausola else nel suo complesso (- x) è in una posizione di coda.

Analogamente nell'espressione

(if a 
    b 
    c) 

sia b e c sono nelle posizioni di coda, perché uno dei due potesse essere restituito dal if.

Ora nel tuo esempio

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

forma (if ...) si trova nella posizione di coda della forma (loop ...) e sia la forma e la forma (recur ...)result sono nella posizione di coda della forma (if ...).

D'altra parte nella domanda che si è collegato

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

il recur non è in posizione di coda perché il (+ 1 ...) saranno valutati dopo la (recur tail). Pertanto il compilatore Clojure dà un errore.

La posizione della coda è importante perché è possibile utilizzare la forma recur dalla posizione di coda. I linguaggi di programmazione funzionale di solito utilizzano la ricorsione per ciò che i linguaggi di programmazione procedurali realizzano mediante cicli. Ma la ricorsione è problematica, perché consuma lo stack space e la ricorsione profonda può portare a problemi di stackoverflow (oltre ad essere lenta). Questo problema viene in genere risolto con ottimizzazione chiamata coda (TCO), che elimina il chiamante quando la chiamata ricorsiva si verifica nella posizione di coda di una funzione/modulo.

Poiché Clojure è ospitato sulla JVM e la JVM non supporta l'ottimizzazione delle chiamate tail, è necessario un trucco per eseguire la ricorsione. Il form recur è quel trucco, consente al compilatore Clojure di fare qualcosa di simile all'ottimizzazione delle chiamate tail. Inoltre, verifica che recur sia effettivamente in posizione di coda. Il vantaggio è che puoi assicurarti che l'ottimizzazione avvenga effettivamente.

Answer 2

Solo per completare l'eccellente risposta di Paolo sopra, The Joy of Clojure (ed1) fornisce una tabella (Tabella 7.1) che mostra esattamente dove la posizione della coda è in varie forme/espressioni, che ho riprodotto di seguito. Cercare in cui si verifica la parola "coda" in ogni modulo/espressione:

 
|---------------------+-------------------------------------------+---------------| 
| 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   | 
|---------------------+-------------------------------------------+---------------|