Эволюция программирования прошла тернистый путь от прямого управления процессорными инструкциями до абстрактных математических концепций. В данном материале ведущий канала Computerphile подробно анализирует историческое противостояние и технические различия между циклами и рекурсией. Рассматривая развитие языков от ассемблера до Fortran и Algol, автор показывает, как сугубо теоретическая идея превратилась в фундаментальный инструмент промышленной разработки.
⏳ От ассемблера к DO-циклам: Как Fortran изменил программирование 0:00
В середине XX века программирование находилось на низком организационном уровне. В 1940-х и начале 1950-х годов разработчики использовали исключительно ассемблер или чуть более продвинутые макроассемблеры. Эти инструменты позволяли упаковывать небольшие последовательности низкоуровневых команд в макросы, которые затем вызывались по мере необходимости.
Переломным моментом стало появление языков высокого уровня, способных предложить абстракции для повторяющихся действий. Одним из первопроходцев в этой области стал язык Fortran. Несмотря на то, что его официальная спецификация была опубликована в 1965 году, разработка началась почти на десять лет раньше. Язык был создан Джоном Бэкусом (John Backus) и его большой командой в недрах корпорации IBM в 1950-х годах.
Fortran создавался как специализированный инструмент для инженерных и научных расчетов. При детальном рассмотрении его структура все еще сильно напоминала ассемблер. Вместо привычного современным программистам термина «for loop» (цикл for), команда Бэкуса использовала обозначение «do loop» (цикл do).
Механика работы такого цикла в Fortran существенно отличалась от синтаксиса современных языков семейства C:
- Программист упаковывал последовательность инструкций и указывал компилятору повторять их.
- Повторение выполнялось до тех пор, пока выполнение не доходило до строки со специальной числовой меткой (например, меткой 180).
- По достижении метки управление возвращалось в начало цикла для инкрементирования счетчика.
Числовые метки (будь то 180 или 72) зависели исключительно от внутренней системы нумерации, выбранной разработчиком. Переменная-счетчик автоматически инкрементировалась при каждом шаге (например, от 1 до 10). Для инженеров, привыкших к ассемблеру, такой переход на чуть более высокий уровень абстракции казался невероятно комфортным.
🕸 Матрицы и глубина: Сила и ограничения вложенных циклов 3:18
Возможности циклов значительно расширялись за счет их вложенности. Ни в ассемблере, ни в Fortran не было ограничений, препятствующих созданию цикла внутри другого цикла. Ведущий приводит пример структуры, где внешний цикл оперирует переменной J (от 1 до 20), а внутренний — переменной I (от 1 до 10).
В такой конфигурации для каждого шага внешнего цикла внутренний пробегает весь спектр своих значений. В результате программа последовательно обрабатывает 200 различных локаций памяти. Подобный подход идеально подходил для работы с двумерными массивами (матрицами), состоящими из целых или вещественных чисел. Огромный пласт вычислений в физике, химии и особенно в инженерном деле опирается именно на такие матричные структуры. Даже закоренелые приверженцы ассемблера признавали удобство этой абстракции при решении тяжелых научных задач.
Однако перед создателями компиляторов встал вопрос: насколько глубоко можно вкладывать циклы друг в друга? По предположению автора видео, ранние компиляторы Fortran вряд ли позволяли программистам опускаться глубже 10 уровней вложенности. Со временем лимиты росли:
- Ранние версии компилятора GCC для языка C имели ограничение примерно в 32 уровня.
- Современные стандарты C++ позволяют компилировать вложенные циклы глубиной до 256 уровней.
Подобная глубина необходима для многомерных задач. С математической точки зрения, если внешний цикл выполняется $N$ раз и внутренний выполняется $N$ раз, мы получаем вычислительную сложность порядка $N^2$. Добавление третьего уровня превращает задачу в кубическую ($N^3$). Вложенные циклы позволяют справляться со многими многомерными полиномиальными и экспоненциальными проблемами, если их размерность укладывается в доступные лимиты компилятора.
🤯 Культурный шок 60-х: Функция Аккермана против циклов 6:12
Казалось бы, лимита в 256 уровней вложенности должно хватить для любой мыслимой задачи. Однако в 1960-х годах теоретики компьютерных наук начали посещать лекции математиков, занимавшихся вопросами вычислимости по Гёделю. Для практикующих инженеров того времени это стал настоящий культурный шок. Математические теории о рекурсивных функциях, которые раньше казались программистам оторванными от реальности, внезапно обрели колоссальное значение.
Главным камнем преткновения стала функция Аккермана, названная в честь Вильгельма Аккермана, ученика знаменитого Давида Гильберта. Эта функция разработана в рамках академического вызова: найти нечто настолько глубоко рекурсивное, что его невозможно выразить через простые циклы.
Математически функции делятся на два типа:
- Примитивно рекурсивные — простые структуры (например, факториал или последовательность Фибоначчи), которые без труда можно реализовать с помощью обычного цикла.
- Общерекурсивные (общекомпонируемые) — структуры вроде функции Аккермана, где подпрограммы вызывают сами себя настолько сложным и запутанным образом, что стандартные циклы перед ними пасуют.
Обычный инженер мог легко посчитать факториал пяти ($5 \times 4 \times 3 \times 2 \times 1$) в цикле. Но когда теоретики в 1960-х годах попытались рассчитать функцию Аккермана с помощью доступного им инструментария Fortran, они столкнулись с непреодолимым барьером.
👢 Грязные сапоги Fortran и триумф Algol 7:46
Ключевая проблема заключалась в том, что оригинальный Fortran не поддерживал рекурсию на уровне пользователя. Программист мог написать функцию и заставить её вызывать саму себя. Ожидалось, что при каждом новом вызове система будет создавать изолированную область памяти для данных — то, что в современной терминологии называется стековым фреймом (stack frame). По мере глубокого погружения в рекурсию эти фреймы должны накапливаться друг над другом, а при выходе — удаляться.
Однако Fortran работал иначе. Архитектура языка выделяла ровно один стековый фрейм на подпрограмму. Как иронично отмечает ведущий, при попытке рекурсивного вызова функция просто «топталась своими грязными сапогами» по своей же единственной области данных, затирая предыдущие значения. Вместо корректного расчета функции Аккермана программа выдавала абсолютный мусор.
Это привело к осознанию жесткой необходимости внедрения полноценной рекурсии в языки программирования для решения сложных нелинейных задач. Настоящую славу на этом поприще завоевал язык Algol. Его подпрограммы могли корректно вызывать сами себя, изолируя данные каждого шага. Для функции Аккермана (пусть даже для ее скромных начальных значений) Algol работал чрезвычайно медленно, но он выдавал правильный, математически точный результат.
🛠 Секрет компилятора: Зачем разработчикам Fortran понадобилась рекурсия 10:11
Функция Аккермана служит отличным академическим полигоном, подобно гоночному треку для проверки максимальной скорости автомобиля. Однако в повседневной жизни программы редко сталкиваются с задачами столь экстремальной сложности. Где же рекурсия средней, «нетривиальной» сложности нашла свое реальное практическое применение?
Ответ оказался парадоксальным: в самих компиляторах. Джон Бэкус и его команда, создавая Fortran в середине 1950-х годах, принципиально не дали пользователям явный инструмент рекурсии. Но, как позже признавался сам Бэкус в своих статьях, в процессе написания компилятора они обнаружили, что им жизненно необходим этот механизм. Разработчики IBM были вынуждены фактически изобрести рекурсию изнутри, чтобы их продукт вообще мог функционировать.
Необходимость рекурсии в компиляторах обусловлена самой природой синтаксиса языков программирования:
- Даже базовые арифметические выражения обладают рекурсивной структурой из-за вложенности скобок.
- Программа может содержать конструкции вида «скобки внутри скобок, внутри других скобок», умноженные на внешние коэффициенты.
- Компилятор обязан точно определять приоритет операций и глубину вложенности, чтобы выдать верный математический результат.
Пользователи регулярно пытались дестабилизировать компиляторы, подсовывая им выражения с экстремальной вложенностью скобок для проверки их отказоустойчивости. Справиться с разбором такого синтаксического дерева с помощью обычных плоских циклов было невероятно трудно. К 1960 году, с появлением Algol, как академическое сообщество, так и рядовые разработчики окончательно сошлись во мнении: умеренная рекурсия — более сложная, чем факториал, но более приземленная, чем функция Аккермана — обязана быть базовой частью любого развитого языка программирования.
