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

Циклы схемы реализованы с использованием рекурсии под капотом; такие конструкции, как 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! инструкция.

Этот вопрос на самом деле состоит из двух вопросов и путаницы.

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

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

(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, и традиционный Lisp предоставляют операторы мутации: ни один из них не является чистым функциональным языком, каким вы можете его считать. Схема ближе к тому, чтобы быть одной, но это все еще не очень близко.