Почему массивы начинаются с нуля

Самое очевидное объяснение: индекс — это смещение относительно начала массива. Так элементы массива легче адресовать в памяти.

Проверим это на C.

#include <stdio.h> int main() {     int data[3] = {1, 2, 3};     int i = 0;     printf("Array address: %p\n", data);     do {         printf("Array[%u] = %p\n", i, (void *)(&data[i]));         i++;     } while(i < 3); }

Получим результат:

Array address: 0x7ffd7c514a6c
Array[0] = 0x7ffd7c514a6c
Array[1] = 0x7ffd7c514a70
Array[2] = 0x7ffd7c514a74

Как первый (нулевой) элемент, так и сам массив находятся по одному и тому же адресу, поскольку 0-й элемент удалён на 0 элементов от начала. Эта связь между указателями и массивами в C настолько тесная, что их даже можно рассматривать вместе.

Однако это ответ на вопрос «зачем», а не «почему». Нумеровать массивы с нуля стали не сразу. Удивительно, но история такого простого вопроса не умещается в предложении или абзаце.

Потому что так удобнее

К началу 1960-х годов сформировалось три подхода к организации структуры, которую сегодня мы называем статическим массивом:

1. Исчисление с 0. Нижняя граница массива начинается с нуля.

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

   Многие современные языки программирования имеют хоть какое-то родство с C (или им желательно заимствовать концепции из С), поэтому эта схема не вызывает никакого удивления и даже кажется стандартной.

2. Исчисление с 1. Нижняя граница массива начинается с единицы.

   Это удобно, поскольку так мы считаем объекты в реальном мире. Такое встречается, к примеру, в MATLAB или Lua — не самых низкоуровневых языках программирования.

3. Произвольные границы массива, когда нижняя граница может быть любым числом. Подобное знакомо учившим, например, Delphi.

Часто нумерацию с нуля объясняют тем, что такую традицию заложил C. Подразумевается, что до появляения указателей, структур и Unix ни один язык не начинал массивы с нуля, полагаясь на нумерацию с 1.

Не всё так однозначно. Единообразия даже у самых первых языков программирования не существовало:

1. Нумерация с нуля: LISP 1.5, APL (допускает выбор при запуске программы).
2. Нумерация с единицы: APL, Бейсик, ранний Фортран.
3. Произвольные границы: Алгол-60, затем Фортран, CPL, SIMULA, CLU, PL/1, Кобол, Паскаль, Алгол-68, JOVIAL.

Как видно, чаще всего массивы начинались не с единицы.

Конечно, это не самый сильный аргумент. Часто языки снабжались синтаксическим сахаром для нумерации с 1. К примеру, в Алголе массив V[0:3] начинается с 0, а массив V[3] — с 1.

Создатель языка APL в одноимённой книге «A Programming Language» объясняет, почему далее по тексту он будет пользоваться нумерацией элементов массива с нуля. При этом язык допускает как отсчёт с единицы, так и с нуля. Кеннет Айверсон приводит уже описанный выше аргумент о сдвигах в позиционной нумерации.

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

Потому что парусные регаты мешали вычислениям

В 1967 году Мартин Ричардс впервые реализует компилятор своего детища — BCPL (Basic Combined Programming Language). Этот язык программирования был призван исправить проблемы созданного в начале шестидесятых языка CPL путём отказа от технологий, затрудняющих компиляцию.

Первый компилятор BCPL был написан для операционной системы CTSS машины IBM 7094 Массачусетского технологического института. На тот момент компьютеры — это уже не целые комнаты и электронные лампы, но всё ещё огромные шкафы с транзисторами и консоли управления без экранов. Ресурсов серии 7090 хватило, чтобы запустить американца в космос. Но мощность измерялась в тысячах машинных слов, микросекундах тактов и килофлопсах, а цена — в миллионах долларов.

В пятидесятых и шестидесятых IBM выдавала институту щедрые скидки на свои научные компьютеры или даже предоставляла их бесплатно. В 1963 году в МТИ поставили IBM 7094. На компьютер уговор был такой: 8 часов в сутки получают специалисты института, 8 часов — другие колледжи и университеты Новой Англии, а третью смену отдавали самой IBM для личных нужд.

На этом особенности не кончались. Несколько раз в год IBM обсчитывала регаты: президент IBM соревновался в заплыве на больших яхтах в проливе Лонг-Айленд, и каждое из судов получало очки гандикапа по специальной сложной формуле. Когда в вычислительный центр приходило задание, операторам полагалось всё бросить и запустить вычисления этих очков.

Машинный зал с установленным компьютером IBM 7094 в Колумбийском университете США, фотография из архива университета

Вообще, и без этого был шанс не получить результат вычислений. Изначально 7094 работал в режиме пакетной обработки. Вспомогательная система на IBM 1401 загружала пакет задач с перфокарт на ленту, а затем запускала задачи одну за другой и записывала результаты для последующей печати. Для каждой задачи приводилась оценка времени. Если задача выходила за пределы отпущенного, её принудительно прерывали.

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

Впрочем, конкретно эта версия — лишь гипотеза Майка Хойе. Ей нет никаких подтверждений от собствено Ричардса или хотя бы упоминаний в литературе. Мартин Ричардс в переписке с Хойе лишь приводит общие соображения о том, что он хотел достичь близости к машинному коду, поэтому указатель p и p + 0 — это одна и та же переменная. Ни на какие яхты Ричардс не жалуется.

К тому же, на момент появления первого компилятора BCPL уже была готова операционка Compatible Time-Sharing System. В ней на одной машине с разделением времени компьютер выполняет одну задачу за один раз, но с оптимизацией ввода и вывода, чтобы паузы одного пользователя заполнялись работой других. Это уже не былая пакетная обработка задач.

Точно известно, что в дальнейшем BCPL значительно повлиял на все современные языки программирования.

В 1969 году Кен Томпсон урезал функциональность BCPL до языка B. В дальнейшем, для развития операционной системы Unix, Деннис Ритчи улучшил B добавлением функций PDP-11, в результате чего и получился C. Полвека спустя список языков, на которые оказал влияние C, занимает в «Википедии» целую страницу.

В языке BCPL v!5 и 5!v совпадают, поскольку являются указателем на !(v+5) или !(5+v). Аналогично, в C v[5] эквивалентно 5[v].

Потому что так предложил Дейкстра

В 1982 году Эдсгер Дейкстра опубликовал статью «Почему нумерация должна начинаться с нуля». В ней он низверг как нумерацию с единицы, так и произвольные границы индексов. Очевидно, что Дейкстра — не человек, который легко поддаётся влиянию C, но также он раскритиковал Алгол-60, своё собственное детище, и Паскаль.

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

Если необходимо записать интервал натуральных чисел 2, 3, …, 12 без опухоли из точек, возможны четыре варианта:

1. 2 ⩽ i < 13
2. 2 < i ⩽ 12
3. 1 < i ⩽ 12
4. 1 < i < 13

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

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

Аналогично, для верхней границы Дейкстра рекомендует использовать <, поскольку так удобнее для записи подпоследовательностей нулевого размера — иначе верхняя граница рискует не оказаться натуральным числом.

Затем статья делает вывод, что из соображений простоты для последовательности из N членов предпочтительнее диапазон 0 ⩽ i < N, а не 1 ⩽ i < N+1.

Куда менее известный документ — это полушуточная техническая заметка от 1 апреля 1980 года IEN 137 под названием «О святых войнах и призыв к миру» [On Holy Wars and a Plea for Peace].

В заметке Дэнни Коэн приводит интересный аргумент: в системе счисления с основанием b при отсчёте с нуля первые b ^ N неотрицательных чисел представляются ровно N цифрами. Например, если речь про двоичную запись, то 2 ^ 3 = 8, и восьмой элемент массива будет иметь номер 111₂, а не 1000₂. Понятно, что с такими преобразованиями легко бы мог справиться компилятор.

Потому что так более элегантно

Это объяснение может раздражать субъективностью. Соображения о красоте у каждого свои и совпадать не обязаны. Но авторы языков программирования — тоже люди со своими предпочтениями.

В конце восьмидесятых Гвидо ван Россум при создании Python как учёл свой предыдущий опыт с языком ABC, так и задумал привлечь аудиторию хакеров от мира Unix и C.

С 1983 года Гвидо работал в Центре математики и информатики в Амстердаме над реализацией языка ABC. Проект ставил целью создать язык программирования, пригодный для обычных людей, но не настолько ужасно реализованный, как Бейсик. Нумерация массивов в ABC начиналась с единицы. Такой же схемы придерживались другие знакомые Россуму языки — Алгол, Фортран и Паскаль.

В 1991 году выходит Python, где нумерация начинается с нуля, а не единицы. Получилось так в результате долгих размышлений.

Одна из причин — слайсы. Чаще всего при создании слайса используются операции «получить первые n элементов» и «начиная с i, получить следующие n элементов». При этом первый случай эквивалентен i == первый индекс. Гвидо посчитал, что лучше, если обе операции возможны без лишней головной боли в виде коррекции +1 и −1.

Если первый элемент имеет номер 1, то возможно указывать первый элемент и число элементов, которые нужно получить. Россум уже был знаком с подобным по ABC и вполне мог бы положиться на этот опыт.

Тем не менее автора Python очаровал синтаксис слайсов полуоткрытого интервала, если нумерация начинается с нуля: a[:n] (или a[0:n]) и a[i:i+n]. К примеру, строку a легко разбить на три части a[:i], a[i:j] и a[j:].

Заметим, что в воспоминаниях Гвидо не приводит призывы гениев информатики, практики других языков или принципы, заложенные мастодонтами компьютерных вычислений шестидесятых. Зато слово «элегантность» в пяти абзацах его объяснения встречается 3 раза.

Так почему же массивы начинаются с нуля?

Так исторически сложилось.

По материалам блогов Альберта Козловски, Майка Хойе, Гвидо ван Россума, Хиллеля Уэйна и ответа Хойе.