Как циклы реализованы в функциональных языках

Question

На функциональных языках, таких как Scheme или же Lisp существуют for а также for-all петли. тем не мение for циклы требуют мутации, так как это не новый кадр стека на каждой итерации. Поскольку мутация не доступна в этих языках явно, как эти функциональные языки реализуют свои соответствующие итеративные циклы?

Answer 1

Схемы циклов реализованы с использованием рекурсии под капотом; такие конструкции, как do это просто макросы, которые переводятся в рекурсивные процедуры. Например, этот цикл на типичном процедурном языке:

void print(int n) {
    for (int i = 0; i < n; i++) {
        display(i);
    }
}

... эквивалентно следующей процедуре на схеме; здесь вы можете видеть, что каждая часть цикла (инициализация, условие выхода, приращение, тело) имеет соответствующее выражение:

(define (print n)
  (define (loop i)     ; helper procedure, a "named let" would be better
    (when (< i n)      ; exit condition, if this is false the recursion ends
      (display i)      ; body
      (loop (+ i 1)))) ; increment
  (loop 0))            ; initialization

Вы заметили, что после вызова рекурсии больше нечего делать? компилятор достаточно умен, чтобы оптимизировать его для использования одного фрейма стека, что делает его for цикл - читайте о хвостовой рекурсии для более подробной информации. И просто чтобы уточнить, в Схеме мутация явно доступна, читайте о set! инструкция.

Answer 2

Этот вопрос действительно два вопроса, и путаница.

Итерация в схеме

В Схеме итерация реализуется путем рекурсии вместе с семантикой языка, предписывающей, что определенные виды рекурсии не потребляют память, в частности хвостовую рекурсию. Обратите внимание, что это не подразумевает мутации. Так, например, вот определение while петля я ракетка.

(define-syntax-rule (while test form ...)
  (let loop ([val test])
    (if val
        (begin
          form ...
          (loop test))
        (void))))

Как вы можете видеть рекурсивный вызов loop находится в положении хвоста и поэтому не потребляет памяти.

Итерация в традиционных Лиспах

Традиционные Лиспы не требуют устранения хвостовых вызовов и, следовательно, требуют итеративных конструкций: они обычно предоставляются языком, но обычно могут быть реализованы в терминах конструкций более низкого уровня, таких как GO TO. Вот определение while в Common Lisp, который делает это:

(defmacro while (test &body forms)
  (let ((lname (make-symbol "LOOP")))
    `(tagbody
      ,lname
      (if ,test
          (progn
            ,@forms
            (go ,lname))))))

Путаница по поводу мутации

Как в Scheme, так и в традиционных Лиспах предусмотрены операторы мутации: ни один из них не является чисто функциональными языками. Схема ближе к тому, чтобы быть единым целым, но она все еще не очень близка.