возвращаться в законное хвостовое положение - PullRequest
Новая
       16

возвращаться в законное хвостовое положение

0 голосов
/ 18 апреля 2020

recur следует вызывать в хвостовой позиции, и я предполагаю, что он эффективно действует как нерекурсивный квази-l oop.

Рассматривается ли expr-1 или 2 в правильном положении хвоста, но нет ни одного из expr-3 до 8 в следующих блочных структурах mimi c? Иначе как рассуждать и идентифицировать его, прежде чем прибегать к следам и ошибкам? 

(defn foo [x]
 (if cond-expr-1
  (recur expr-1)
  (recur expr-2)))

(defn bar [x]
 (if cond-expr-2
  (fn-1 (recur expr-3))
  (fn-2 (recur expr-4))))

(defn baz [x]
 (if cond-expr-3
  (if cond-expr-4  
    (recur expr-5)
    (recur expr-6))
  (if cond-expr-5  
    (recur expr-7)
    (recur expr-8))))

Ответы [ 2 ]

2 голосов
/ 18 апреля 2020

Выражение находится в хвостовой позиции, если больше ничего не нужно оценивать в текущей функции, следующей за этим выражением. В вашем случае все вызовы recur в foo и baz находятся в хвостовой позиции, и поэтому обе функции будут хорошо компилироваться.

В bar, однако, ни один из вызовов recur будет разрешено, потому что ни expr-3, ни expr-4 не находятся в хвостовой позиции. Есть вызовы функций, которые используют результат каждого вызова recur в качестве аргумента, то есть вызов функции логически следует за вызовом recur, и, таким образом, recur не находится в хвостовой позиции.

Это Нельзя сказать, что вы не можете написать bar, чтобы сделать рекурсивный вызов сам по себе, но вы должны кодировать его явно, как в: 

(defn bar [x]
 (if cond-expr-2
  (fn-1 (bar expr-3))
  (fn-2 (bar expr-4))))

Это абсолютно разрешено, НО эти рекурсивные вызовы из bar будет использовать пространство стека, что означает, что если функция вызывает себя рекурсивно достаточно раз, вам не хватит места в стеке. recur (и хвостовая рекурсия в целом) полезны, поскольку не требуют вызова функции в традиционном смысле - вместо этого (логически здесь) аргумент функции в стеке заменяется новым аргументом, и код переходит вернуться к началу функции, поэтому пространство стека не используется. Конечно, это означает, что исходный аргумент при первом вызове функции потерян.

Другие версии Lisp не используют ключевое слово recur. Когда эти версии Lisp обнаруживают, что функция вызывает себя рекурсивно, они делают то же самое определение "хвостовой позиции", которое делает Clojure, и, если они находят, что вызов находится в хвостовой позиции, они выполняют ту же процедуру "replace-the-arguments-and-jump" "logi c Clojure делает, в то время как если они обнаруживают, что вызов не находится в хвостовой позиции, они испускают код для выполнения" реального "рекурсивного вызова, а не для сбоя компиляции. Преимущество Clojure состоит в том, что для разработчика становится очень очевидным, будет ли вызов скомпилирован как хвост-рекурсивный вызов (ветвь) или нет.

1 голос
/ 18 апреля 2020

В случае expr-3 и expr-4 это аргумент функции, и поэтому он не находится в хвостовой позиции.

Вызов recur в основном похож на goto или return оператор, оба из которых нельзя использовать внутри списка аргументов функции.

Поскольку выражение if не является функцией (это «специальная форма»), проблема не возникает, поскольку со списком аргументов функции.

Вот сравнение между loop/recur и более императивным подходом, использующим while: 

(ns tst.demo.core
  (:use tupelo.core tupelo.test))

(defn fib-recur
  [arg]
  (assert (and (int? arg) (pos? arg)))
  ; initialize state vars
  (loop [N      arg
         result 1]
    (if (zero? N)
      result
      ; compute next state vars
      (let [N-next      (dec N)
            result-next (* result N)]
        (recur N-next result-next))))) ; jump to top of loop with next state vars

(defn fib-while
  [arg]
  (assert (and (int? arg) (pos? arg)))
  ; initialize state vars
  (let [state (atom {:N      arg
                     :result 1})]
    (while (pos? (:N @state)) ; must use newest state value for N in test
      ; compute next state vars
      (let [N          (:N @state)
            result     (:result @state)
            state-next {:N      (dec N)
                        :result (* result N)}]
        (reset! state state-next))) ; save new state & jump to top of loop
    (:result @state)))

(dotest
  (is= 120 (fib-recur 5))
  (is= 120 (fib-while 5)))
...