Санкционный while: стоит ли запретить циклы вслед за goto?
Привет, Хабр! Меня зовут Артём. Я руковожу группой Scala-разработчиков в компании "Криптонит" и веду Scalabook — русскоязычную базу знаний по Scala и функциональному программированию. В ней можно найти другие мои статьи-инструкции, а также примеры кода. В этой статье предлагаю обсудить циклы и связанные с ними спорные моменты.
Одной из первых конструкций, изучаемых в программировании, является цикл. Это даже одна из первых вещей, с которой мы сталкиваемся в жизни. Мамы ласково шепчут детям: "Не можешь заснуть? А ты мысленно посчитай овечек..." И вот вы начинаете считать: "одна овечка, две овечки, три овечки, четыре..."
Вот он — наш цикл:
var lamb = 0
while true do
println(lamb)
lamb += 1
А теперь представьте, что циклы попали под санкции! Пишите вы так на своём любимом языке программирования while... и тут, бац! Ваша любимая IDE, верой и правдой прослужившая десятки лет, прошедшая вместе с вами несколько прогоревших стартапов, пару крупных корпораций, а, может быть, даже галеры (😱) подло так выдаёт: "Thank you for using ‘while’. Unfortunately, we are unable to accept 'while' from Russian sources due to export policy at this time. Thank you for continuing to use ‘while’..." Теперь вы понимаете, что ощущали селебрети, когда запретили Instagram?! Да, кстати, в Scala вполне возможно на уровне компиляции запретить использование while. И ни одна душа в мире проекте не получит подсанкционный хамон while!
Чем плох while?
Рассмотрим повторяющееся вычисление:
дано исходное состояние;
выполняем проверку состояния;
если проверка успешна, то изменяем состояние (или не меняем в случае бесконечного цикла) и возвращаемся в пункт 2;
иначе возвращаем результат.
Конструкция while:
def factorialCycle(n: Int): Int = // Исходное состояние
var acc = 1 // Исходное состояние
var i = n // Исходное состояние
while i > 0 do // Проверка состояния
acc *= i // Изменение состояния
i -= 1 // Изменение состояния
acc // Результат
Давайте попробуем переписать цикл с помощью хвостовой рекурсии:
@annotation.tailrec
def factorialTailrec(n: Int, acc: Int = 1): Int = // Начальное состояние
if n <= 0 then acc // Проверка состояния и результат
else factorialTailrec(n - 1, n * acc) // Изменение состояния и возврат к проверке
А если не видно разницы, то...
Давайте присмотримся: рекурсия знает своё состояние, а цикл — нет. При использовании рекурсии мы можем этим состоянием манипулировать.
Зная состояние, мы можем прервать рекурсию и когда захотим — продолжить, мы можем разбить рекурсию на части, вычисляя каждую отдельно. С циклом такой фокус не пройдет: мы либо вычисляем его полностью, либо ничего. Мы не можем его остановить, потому что потом придется все начинать сначала. У цикла неявное состояние.
Вот ещё несколько важных отличий:
Невозможность ленивых вычислений — конструкции while по своей сути строгие — они должны вычислять условие и выполнять тело цикла. Рекурсивные функции могут быть ленивыми и генерировать бесконечные структуры данных. Например, список простых чисел.
Отсутствие композиции — результат вычисления while — его побочный эффект. Трудно скомбинировать несколько циклов while в более сложную операцию, так как циклы не возвращают значений.
И даже если кто-то укажет, что в Scala под капотом у хвостовой рекурсии находится всё тот же императивный цикл, то можно ответить, что всё заканчивается байт-кодом, но это не означает, что все должны изучать Ассемблер.
Одна из самых больших проблем в программировании — чётко сформулировать задачу, поэтому появляются абстракции, понижающие уровень сложности. Кто-то опять может заметить, что в ФП абстракция абстракцией погоняет (одна эпопея с монадами чего стоит), но это, опять же, — вопрос границ. Мы ограничиваем использование — запрещаем использовать goto, чтобы сделать код надёжнее и предсказуемее. То же самое и с while с его неявным состоянием!
Так может стоит совсем отказаться от циклов и запретить while, как «вредную» конструкцию? Может быть, это следующая ступень эволюции после отхода от goto?!
goto на минималках
Кажется, что циклы были всегда и развивались вместе с языками программирования. В самых первых компьютерах программирование велось с помощью машинных кодов и ассемблеров. Циклы организовывались с помощью условных и безусловных переходов. Разработчики вручную сравнивали значения и "прыгали" на начало блока кода, если условие выполнялось. Это был "дедушка" всех циклов.
начало_цикла:
... (тело цикла) ...
CMP AX, BX ; Сравнить регистр AX и BX
JNE начало_цикла ; Перейти к началу, если не равны
В конце 1950-х пришло осознание, что программы, написанные с помощью частых переходов, становятся сложными для понимания и поддержки — непредсказуемый control flow. Это привело к развитию структурного программирования. Язык Алгол (ALGOL) стал революционным. Его разработчики (среди которых были такие мэтры, как Фридрих Бауэр, Джон Бэкус, Эдсгер Дейкстра и другие) стремились создать язык, удобный для описания алгоритмов. Именно в ALGOL 60 впервые появилась чёткая и ясная конструкция цикла while. Эта конструкция стала фундаментальным прорывом. Она позволяла выражать намерение программиста ("повторять, пока истинно условие") прямо и без использования оператора перехода GOTO.
В качестве побочного эффекта это породило целую войну среди тех, кто ненавидит goto и всячески ратует за его запрет в языках программирования, и теми, кто считает использование goto оправданным — например, в качестве выхода из вложенных циклов или примитивного обработчика исключений. Не хочу вставать на чью-либо сторону, хотя сам в последний раз пользовался безусловным переходом почти двадцать лет назад (мне просто приставили пистолет к затылку), но выскажу своё мнение.
Как мне кажется, циклы возникли как ответная реакция на бездумное распространение goto, в качестве попытки упростить control flow. Возможность перехода в любую точку заманчива, но требует от разработчика держать в голове большой контекст — это довольно сложно. Циклы резко сужают возможности goto, оставляя лишь несколько переходов: переход на следующий статус, выход из цикла (break), досрочный переход на следующую итерацию (continue).
Ключевую роль в этом процессе сыграл Эдсгер Дейкстра, опубликовавший знаменитое письмо "Go To Statement Considered Harmful", которое стало манифестом структурного программирования: давайте резко ограничим использование goto только лишь через концепцию циклов! После этого началась долгая борьба за запрет goto. В большинстве современных языков программирования goto нет: безусловный переход эволюционировал в циклы.
Рекурсия и итерация
Помимо циклов есть ещё один способ повторения действий — рекурсия. Математическая концепция рекурсии и итерации (циклов) существовала задолго до появления компьютеров. Ещё в 1930-х годах Алонзо Чёрч и Алан Тьюринг заложили теоретический фундамент вычислений, который неявно включал в себя идею повторения действий. Хотя непосредственно о циклах в этих работах не говорится, тезис Чёрча — Тьюринга устанавливает, что все вычислимые функции могут быть вычислены с помощью рекурсии (λ-исчисление Чёрча) или итерации (машины Тьюринга), подразумевая их эквивалентность в вычислительной сложности. С тех пор опубликовано много работ, доказывающих эквивалентность хвостовой рекурсии и итерации: [McCarthy J., (1960); Bird R.S. (1998); Wand M. (1980); Appel A.W. (1992)]
В функциональных языках основная конструкция для повторяющихся действий — это рекурсия, в императивных языках — итерация. В частности в Scala, компилятор автоматически преобразует хвостовую рекурсию в итерацию.
Рекурсия более чётко разделяет состояние от его изменения.
Это может быть метод:
@tailrec
def loop(начальное состояние) =
изменение состояния
... или специализированный метод, типа свёртки fold, reduce и т. д.:
def fold(начальное состояние)(изменение состояния)
Итерация и рекурсия изоморфны друг другу. То есть, между итерацией и рекурсией существует взаимно однозначное соответствие. Любой алгоритм, который можно реализовать с помощью цикла (итерации), можно реализовать и с помощью рекурсии. Мы можем переписать итерацию на рекурсию и обратно.
Например, у нас есть итеративный подсчёт суммы:
def sumIter(number: Array[Int]): Int =
var sum = 0
var i = 0
while i < number.length do
sum += number(i)
i += 1
sum
берём то, что находится до объявления цикла — исходное состояние — и переносим в параметры хвостовой рекурсии;
переносим условие выполнения итерации в качестве условия выхода из рекурсии;
возвращаем аккумулятор — то, что находится после всех итераций цикла;
в ином случае обновляем состояние.
def sumRec(number: Array[Int]): Int =
@annotation.tailrec
def loop(i: Int, sum: Int): Int =
if i == number.length then sum
else loop(i + 1, sum + number(i))
loop(0, 0)
Это работает и в обратную сторону:
параметры рекурсии выносим в исходное состояние перед циклом;
условие выхода переносим в условие выполнение цикла;
аккумулятор переносим после цикла;
условие else — это тело цикла.
Что дальше?
Мы хотим понять и обозреть всё, но не всё нам доступно — есть определённая граница. Опытные разработчики её видят: как написано в комментарии, и goto тоже может использоваться с умом — в качестве выхода из вложенных циклов или примитивного обработчика исключений. Тоже самое и с while — опытный разработчик разберётся, когда использовать рекурсию, а когда — итерацию. Но для разработчиков, только начинающих свой путь, в качестве точки развития можно предложить чаще использовать рекурсию. К тому же, в ФП существуют свои паттерны с рекурсией, как в GoF — например, свёртка и генерация последовательностей (fold и unfold).
Об этом расскажем в одной из следующих статей, а пока… давайте запретим while! Разрешим им пользоваться только Senior Pomidor Developer-ам и прочим заслуженным личностям. Проблема while состоит в том, что он бесконечно расширяем в части своего неявного состояния, и многим разработчикам может не хватить опыта увидеть момент, когда состояние стало слишком сложным. Поэтому, если вдруг циклы попадут под санкции аналогично goto, то, может, это и к лучшему?
P.S.
А теперь без шуток: пока писал статью, я реально забыл сигнатуру while в Scala. Мне даже пришлось гуглить, как же он всё-таки пишется. А ведь когда-то я, дитя ООП, даже представить себе не мог программирование без while. Вот времена были, вот нравы…
Рекомендуемая литература:
McCarthy, J. (1960). «Recursive functions of symbolic expressions and their computation by machine» — одна из первых работ, показывающая как рекурсивные функции могут быть вычислены итеративно
Bird, R.S. (1998). «Introduction to Functional Programming using Haskell» — содержит формальные доказательства эквивалентности хвостовой рекурсии и итерации
Wand, M. (1980). «Continuation‑based program transformation strategies» — предлагает методы преобразования рекурсивных программ в итеративные с использованием продолжений (continuations)
Appel, A.W. (1992). «Compiling with Continuations» — практические аспекты преобразования рекурсии в итерацию в компиляторах