Попробуем написать разными способами программу, реализующую циклическое вычисление, заключающееся в печати последовательных чисел от n1 до n2. Предметом нашего внимания будет способ завершения цикла. Поскольку для иллюстрации мы будем использовать язык Scheme, как один из наиболее концептуальных в области теории вычислений, то для реализации цикла используем рекурсию, как единственный циклический механизм в этом языке. Впрочем, для большинства наших способов мы будем указывать на аналоги в других языках, предполагающие использование императивных операторов цикла.

Все примеры даны в синтаксисе Gambit Scheme.

1. Завершение рекурсивной цепочки по условию

Самый банальный способ выхода из рекурсии.

(define (f n1 n2)
  (cond
   ((> n1 n2) #!void)
   (else (pp n1) (f (+ n1 1) n2))))

Здесь мы определили функцию f с параметрами n1 и n2 – началом и концом диапазона пробегаемых в цикле значений. На каждом шаге мы проверяем, не превысило ли значение n1 величину n2, и если да, то возвращаем пустое значение функции f (так как вся её полезная работа заключается в побочном эффекте). Если же нет, то печатаем значение n1 при помощи функции pp (pretty-print), и рекурсивно вызываем себя с новым, увеличенным значением n1. Так как это хвостовая рекурсия, то по правилам языка Scheme она будет преобразована в машинном коде в эквивалентный циклический переход и не вызовет дополнительных затрат на рост стека.

В императивных языках аналогом этого способа будет обычный оператор цикла с переменной цикла, пробегающей значения от n1 до n2.

2. Жёсткий выход из программы

Так иногда пишут начинающие программисты.

(define (f n1 n2)
  (when (> n1 n2)
    (exit))
  (pp n1)
  (f (+ n1 1) n2))

На каждом шаге мы смотрим, не превысили ли мы конечное значение, и если да, то останавливаем работу программы (заодно завершается интерпретатор Scheme, и мы вываливаемся в командную строку операционной системы). Если этого не произошло, далее продолжается безусловная рекурсия.

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

3. Исключительная ситуация

Более облагороженным вариантом предыдущего способа является выход через возбуждение и перехват исключительной ситуации.

(define (f n1 n2)
  
  (define (inner n1 n2)
    (when (> n1 n2)
      (raise "Отмучался, бедолага"))
    (pp n1)
    (inner (+ n1 1) n2))
  
  (with-exception-catcher
    (lambda (e) #!void)
    (lambda () (inner n1 n2))))

Здесь уже появляется много лишней писанины, связанной с особенностями синтаксиса Scheme, но в целом всё прозрачно, и в императивных языках будет примерно так же. В нашей функции f мы объявляем обработчик исключительных ситуаций, который возвращает пустое значение при возникновении исключения e, и в его контексте вызываем дополнительную внутреннюю функцию inner. Эта внутренняя функция крутит рекурсию, а в нужный момент возбуждает исключительное состояние при помощи вызова raise.

Формально здесь всё правильно, но правила хорошего тона не рекомендуют использовать исключительные ситуации для реализации нормального хода выполнения программы.

4. Убийство

Ещё одной вариацией на предыдущую тему является выход через убийство процесса (нитки).

(define (f n1 n2)
  
  (define (inner n1 n2)
    (when (> n1 n2)
      (thread-terminate! (current-thread)))
    (pp n1)
    (inner (+ n1 1) n2))
  
  (thread (lambda () (inner n1 n2)))
  #!void)

Внешняя функция f запускает внутреннюю функцию inner внутри отдельного процесса. Когда приходит нужный момент, этот процесс убивает сам себя, узнав свой собственный идентификатор при помощи функции current-thread.

В императивных языках – то же самое.

Написано, конечно, очень вычурно и непрактично, но нужно отметить, что это первый из способов, позволяющих также при необходимости завершать наше вычисление снаружи, асинхронно.

5. Ленивые вычисления

Определим функцию-генератор, лениво вычисляющую бесконечную последовательность значений, и воспользуемся ею.

(define (f n1 n2)
  
  (define (generator n1)
    (pp n1)
    (cons n1 (delay (generator (+ n1 1)))))
  
  (do ((value
        (generator n1)
        (force (cdr value))))
      ((>= (car value) n2) #!void)))

Здесь для простоты использован макрос do, представляющий собой реализацию оператора цикла поверх хвостовой рекурсии. Функция generator генерирует и печатает бесконечный список, начиная с n1, каждый элемент которого содержит голову – очередное требуемое нам значение – и хвост – ссылку на ленивое вычисление остальных элементов списка. Для блокировки немедленного вычисления хвоста используется форма delay. Вызывающая функция fперебирает элементы нашего ленивого списка, возвращённого генератором, разблокируя их вычисление по одному при помощи формы force. Как только мы доходим до нужного места, цикл прекращается и возвращает пустое значение.

Этот вариант примечателен тем, что сама (бесконечная) рекурсия находится внутри – в функции generator, а условие выхода из неё – снаружи, в вызывающей функции f.

В императивных языках обычно не поддерживаются ленивые вычисления в общем виде, но во многих из них есть готовые генераторы.

6. Смена динамического контекста

В этом варианте используется механизм продолжений, специфичный для Scheme.

(define (f n1 n2)
  
  (define (inner cc n1 n2)
    (when (> n1 n2)
      (cc #!void))
    (pp n1)
    (inner cc (+ n1 1) n2))
  
  (call/cc
   (lambda (cc)
     (inner cc n1 n2))))

Здесь происходит следующее. Функция f при помощи формы call/cc запоминает свой динамический контекст в переменной cc и в этом контексте вызывает функцию inner, передавая ей контекст cc в качестве одного из параметров. Функция inner крутит рекурсию и в один прекрасный момент обнаруживает, что пора выходить. Тогда она вызывает переданный ей контекст cc, что приводит к возврату управления в точку вызова call/cc и продолжению работы программы дальше (то есть в конец программы) с результатом в виде пустого значения, переданного cc.

Некоторым отдалённым аналогом call/cc в императивных языках является оператор goto. Он, однако, никак не управляет контекстом, поэтому в большинстве языков выход из функции/процедуры при помощи goto запрещён. В языке Си имеются функции setjmp/longjmp , которые позволяют осуществить такой выход, но они не выполняют освобождение других ресурсов, кроме стека.

На базе call/ccв Scheme реализуется также очень интересная техника недетерминированного программирования, о которой рассказывалось в одной из предыдущих публикаций. Недетерминированное программирование не выделено в отдельный пункт, так как внутри по существу находится call/cc.

7. Смена лексического контекста

Возможно, это самый парадоксальный способ.

(define (f n1 n2)
  (when (>= n1 n2)
    (set! f (lambda (n1 n2) #!void)))
  (pp n1)
  (f (+ n1 1) n2))

Здесь функция f меняет значение своего собственного имени в его лексическом контексте, заменяя свой код другим. И тогда очередной шаг бесконечной рекурсии становится вызовом по тому же имени нового тела функции, которое сразу же завершается. Причём, если рекурсия не является хвостовой, то дальше мы будем возвращаться вверх по стеку инстансов старого определения функции.

Такой способ, конечно, возможен только в динамических языках.

Особый цинизм можно придать этому трюку, если смену значения имени f вынести в вызывающую функцию, выполняющуюся асинхронно в отдельном процессе (это возможно, поскольку имя внутренней функции принадлежит лексическому контексту объемлющей функции). Тогда внутри f останется только самая натуральная бесконечная рекурсия. Это по характеру применения напоминает способ с убийством процесса, но механизм здесь совершенно другой.

Заключение

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