Что, собственно, делала программа Ады Лавлейс?

ОРИГИНАЛ: https://twobithistory.org/2018/08/18/ada-lovelace-note-g.html

История создания Microsoft — один из самых известных эпизодов в истории вычислений. В 1975 году Пол Аллен вылетел в Альбукерке, чтобы продемонстрировать интерпретатор BASIC, который они с Биллом Гейтсом написали для микрокомпьютера Altair. Поскольку никто из них не работал с Альтаиром, Аллен и Гейтс тестировали интерпретатор с помощью эмулятора, который сами написали и использовали в компьютерной системе Гарварда. Основа эмулятора — опубликованные спецификации для процессора Intel 8080. Когда Аллен запустил интерпретатор на реальном Альтаире перед человеком, который, как они с Гейтсом надеялись, купит их ПО — он понятия не имел, будет ли интерпретатор работать. Но тот работал. В следующем месяце Аллен и Гейтс официально основали компанию.

За сто лет до того, как Аллен и Гейтс написали интерпретатор BASIC, Ада Лавлейс написала и опубликовала компьютерную программу. Но та программа, в отличие от Microsoft BASIC, никогда не запускалась, потому что компьютер, для которого она предназначалась, так и не был построен.

Программу Лавлейс часто называют первой компьютерной программой в мире. Согласны не все. Оказалось, что наследие Лавлейс — один из самых жарких споров в истории вычислений. Уолтер Айзексон писал, что спор о масштабе и ценности ее вклада формирует «небольшую академическую специальность». Естественно, тот факт, что Лавлейс была женщиной, сделал спор насыщеннее. Историки ссылались на все виды источников, чтобы доказать, что уважение, оказываемое Лавлейс, либо надлежащее, либо незаслуженное. Но, похоже, на объяснение технических деталей ее публикаций они тратят меньше времени, что прискорбно, потому что технические детали — самая захватывающая часть истории. Кому бы не хотелось знать, как именно должна работать программа, написанная в 1843 году?

Справедливости ради, программу Лавлейс нелегко объяснить непрофессионалу без размахивания руками. Все из-за сложностей, которые однако и делают ее такой значимой. Считать Лавлейс «первым программистом» или нет, ее программа была специфицирована со степенью строгости, намного превосходящей все, что было раннее. Лавлейс внимательно изучила то, как операции могут быть организованы в повторяющиеся группы, тем самым изобретая цикл. Она поняла, насколько важно отслеживать состояние переменных по мере их изменения, вводя обозначения для иллюстрации этих изменений. Как программист, я поражен тем, как многое из того, что делала Лавлейс, похоже на опыт написания ПО сегодня.

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

Сумма степенного ряда

Пифагорейцы жили у берегов Средиземного моря и поклонялись числам. Одним из развлечений было создание треугольников из гальки.

Один камешек, за которым следует ряд из двух камешков, образует треугольник, содержащий три гальки. Добавьте еще один ряд из трех галек, и вы получите треугольник, содержащий шесть галек. Вы можете продолжать так, каждый раз добавляя ряд, в котором на один камешек больше, чем в предыдущем. Треугольник с шестью рядами содержит 21 гальку. Но сколько гальки в треугольнике с 423 рядами?

То, что искали пифагорейцы, было способом посчитать следующее, не делая все эти сложения:


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

1+2+3+⋯+n=n(n+1)2

Позже Архимед исследовал аналогичную проблему. Его интересовала следующая последовательность:

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

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

Подставив уравнение Пифагора для суммы первых n целых чисел и сделав некоторые рассчеты, получится следующее:

В 499 году индийский математик и астроном Ариабхата опубликовал труд, известный как Арябхатия, в котором была формула для вычисления суммы кубов:

Формула суммы первых n целых положительных чисел, возведенных в четвертую степень, не была опубликована еще 500 лет.

Вам, наверное, интересно, существует ли общий метод для нахождения суммы первых n целых чисел, возведенных в к k-ю степень. Математики тоже задавались этим вопросом. Иоганн Фаульхабер, немецкий математик и чудаковатый нумеролог, смог вывести формулы для сумм целых чисел до 17-й степени, которые опубликовал в 1631 году. Но на это могли уйти годы, и он не изложил общее решение. Блейз Паскаль, наконец, изложил общий метод в 1665 году, но он требовал знания того, как посчитать сумму целых чисел, возведенных в меньшую степень. Чтобы вычислить сумму первых n целых положительных чисел, возведенных в шестую степень, например, сначала нужно знать, как вычислить сумму первых n целых положительных чисел, возведенных в пятую степень.

Более практичное общее решение было изложено в посмертно опубликованной работе швейцарского математика Якоба Бернулли, который умер в 1705 году. Бернулли начал с вывода формул для вычисления сумм первых n натуральных чисел в первой, второй и третьей степенях. Они были в полиномиальной форме, поэтому они выглядели следующим образом:

Используя Треугольник Паскаля, Бернулли понял, что эти полиномы следуют предсказуемой схеме. По сути, Бернулли разбил коэффициенты каждого слагаемого на два множителя, один из которых он мог определить, используя Треугольник Паскаля, а второй извлечь из интересного свойства — все коэффициенты в полиноме, казалось, всегда увеличивались на один. Вычисление показателя степени, который должен быть привязан к каждому выражению, не было проблемой, поскольку оно тоже подчинялось предсказуемой схеме. Множитель каждого коэффициента, который должен был быть рассчитан с помощью правила sums-to-one, формировал последовательность, которая стала известна как числа Бернулли.

Открытие Бернулли не означало, что теперь было просто посчитать сумму первых целых n положительных чисел для любой заданной степени. Чтобы посчитать сумму первых n целых положительных чисел, возведенных в k-ю степень, вам нужно знать каждое число Бернулли до k-го числа Бернулли. Каждое число Бернулли могло быть рассчитано только в том случае, если были известны предыдущие числа Бернулли. Но вычисление длинной серии чисел Бернулли было значительно проще, чем выработка формулы каждой суммы степеней по очереди, поэтому открытие Бернулли было большим шагом вперед для математики.

Бэббидж

Чарльз Бэббидж родился в 1791 году, спустя почти столетие после смерти Бернулли. У меня всегда было какое-то смутное подозрение, что Бэббидж разработал, но не создал механический компьютер. Но я никогда не понимал, как этот компьютер должен работать. Основные идеи, как это бывает, не так сложно понять, что хорошо. Программа Лавлейс была спроектирована для работы на одной из машин Бэббиджа, поэтому нам нужно сделать еще один быстрый крюк, чтобы поговорить о том, как работают эти машины.

Бэббидж разработал две отдельные механические вычислительные машины. Его первая машина называлась «Машина различий» (Difference Engine). До изобретения карманного калькулятора люди полагались на логарифмические таблицы для вычисления произведения больших чисел. (Хороший видеоролик Numberphile о том, как это было сделано.) Большие логарифмические таблицы не сложно создать, по крайней мере теоретически, но огромное количество вычислений, которые необходимо сделать для их создания, означало, что во времена Бэббиджа они часто содержали ошибки. Бэббидж, разочарованный этим, стремился создать машину, которая могла бы механически табулировать логарифмы и, следовательно, делать это без ошибок.

Difference Engine не была компьютером, все, что она делала, — сложение и вычитание. Она использовала метод, разработанный французским математиком Гаспаром де Прони, который разбил процесс табуляции логарифмов на небольшие этапы. Эти шаги включали только сложение и вычитание, а это означало, что небольшая армия людей без каких либо способностей к математике или специального образования может быть использована для изготовления таблицы. Метод Де Прони, известный как метод разделенных разностей, может быть использован для табуляции любого полинома. Полиномы, в свою очередь, могут быть использованы для приближения логарифмических и тригонометрических функций.

Чтобы понять, как этот процесс работал, рассмотрим следующую простую полиномиальную функцию:

Метод разделенных разностей включает в себя поиск разницы между каждым последующим значением y для разных значений x. Затем обнаруживаются различия между этими различиями и, возможно, различия между этими следующими различиями, пока не появится постоянная разница. Эти различия затем могут быть использованы для получения следующего значения полинома просто путем сложения.

Поскольку указанный выше полином является только полиномом второй степени, мы можем найти постоянную разницу только после двух столбцов разностей:

Теперь, поскольку мы знаем, что постоянная разница равна 2, мы можем найти значение y, когда x равно 5 только с помощью сложения. Если мы сложим 2 и 7, последнюю запись в столбце «Diff 1», получим 9. Если мы добавим 9 к 17, последняя запись в столбце y, получим 26 — наш ответ.

Difference Engine Бэббиджа имела для каждого столбца разницы в таблице, подобной приведенной выше, физический столбец шестеренок. Каждая шестеренка была десятичным знаком, а одна целая колонка была десятичным числом. У Difference Engine было восемь столбцов шестеренок, поэтому она могла приводить в соответствие полином до седьмой степени. Первоначально столбцы были установлены со значениями, соответствующими первой строке в таблице разностей, разработанной зараннее. Затем оператор поворачивал коленчатый вал, заставляя постоянную разницу распространяться через машину, значение в каждом столбце было добавлено к следующему.

Бэббидж смог построить небольшую часть Difference Engine и использовать ее для демонстрации своих идей на вечеринках. Но даже потратив количество государственных денег, равное стоимости двух крупных военных кораблей, он так никогда и не построил всю машину. Бэббидж не мог найти никого в начале 1800-х годов, кто был способен с достаточной точностью сделать необходимое количество шестеренок. Рабочая Difference Engine не будет построена до 1990-х годов, после появления точной механической обработки. На YouTube есть отличное видео, демонстрирующее рабочий движок Difference Engine, на время предоставленный Музею истории компьютеров в Mountain View, которое стоит посмотреть даже просто, чтобы послушать чудесные звуки, которые издает машина во время работы.

Бэббидж в конце концов потерял интерес к Difference Engine, когда понял, что может быть построена гораздо более мощная и гибкая машина. Его Analytical Engine был машиной, которую мы знаем сегодня как механический компьютер Бэббиджа. Analytical Engine базировалась на тех же столбцах шестеренок, используемых в Difference Engine, но в то время как у Difference Engine было только восемь столбцов, у Analytical Engine должно было быть много сотен. Analytical Engine может быть запрограммирован с использованием перфокарт, таких как жаккардовый конвейер, и может умножать и делить, а также складывать и вычитать. Чтобы выполнить одну из этих операций, раздел машины, называемый «mill», перестраивается в соответствующую конфигурацию, считывает операнды других столбцов, используемых для хранения данных, а затем записывает результат обратно в другой столбец.

Бэббидж назвал свою новую машину Analytical Engine, потому что она была достаточно мощна, чтобы сделать что-то похожее на математический анализ. Difference Engine может приводить в соответствие многочлен, но Analytical Engine могла бы вычислить, например, коэффициенты полиномиального расширения другого выражения. Это была потрясающая машина, но британское правительство мудро отказалось финансировать ее строительство. Поэтому Бэббидж отправился за границу в Италию, чтобы найти поддержку для своей идеи.

Примечания переводчика

В Турине Бэббидж встретился с итальянским инженером и будущим премьер-министром Луиджи Менабре. Он убедил Менабре написать схему того, что могла делать Analytical Engine. В 1842 году Менабре опубликовал доклад на эту тему на французском. В следующем году Лавлейс опубликовала перевод доклада Менабре на английский.

Лавлейс, известная тогда как Ада Байрон, впервые встретила Бэббиджа на вечеринке в 1833 году, когда ей было 17, а ему 41. Лавлейс была очарована Difference Engine Бэббиджа. Она также могла понять, как это работает, потому что в детстве она обстоятельно обучалась математике. Ее мать, Аннабелла Милбанк, решила, что солидный багаж знаний в математике отвадит дикую, романтическую чувствительность, которой обладал отец Лавлейс, лорд Байрон, знаменитый поэт. После встречи в 1833 году Лавлейс и Бэббидж оставались частью одного и того же социального круга и часто писали друг другу.

Ада Байрон вышла замуж за Уильяма Кинга в 1835 году. Кинг позже стал графом Лавлейса, превратив Аду в графиню Лавлейс. Даже после рождения троих детей, она продолжила занятия математикой, используя Августа де Моргана, который открыл законы Де Моргана, в качестве наставника. Лавлейс сразу увидела потенциал аналитической машины Бэббиджа и очень хотела работать с ним, чтобы продвинуть эту идею. Друг предложил ей перевести документ Менабре для английской аудитории.

В статье Менабре был дан краткий обзор того, как работала Difference Engine, а затем показано, как Analytical Engine станет более совершенной машиной. Analytical Engine была бы настолько мощной, что могла бы «выдавать результат произведения двух чисел, каждое из которых содержит двадцать цифр, за три минуты». Менабреа привел дополнительные примеры возможностей машины, продемонстрировав, как она может решить простую систему линейных уравнений и расширить произведение двух биномиальных выражений. В обоих случаях Менабре предоставил то, что Лавлейс назвала «диаграммами развития», в которых перечислены последовательности операций, которые необходимо будет выполнить для расчета правильного ответа. Они были программами в том же смысле, что и программа Лавлейс была программой, и они были изначально опубликованы годом ранее. Но, как мы видим, программы Менабре были лишь простыми примерами возможностей. Они были тривиальны в том смысле, что не требовали каких-либо разветвлений или циклов.

Лавлейс приложила ряд заметок к ее переводу статьи Менабре. Именно здесь она внесла большой вклад в вычисления. В примечании А, которое Лавлейс приложила к первоначальному описанию Менабре Analytical Engine, Лавлейс достаточно подробно и во многих случаях используя лирические формулировки объяснила перспективы машины, способной выполнять произвольные математические операции. Она предвидела, что машина, подобная Analytical Engine, не ограничена цифрами и фактически могла бы действовать на любых объектах. Она добавила, что машина может однажды создать музыку. Это понимание было тем более примечательным, так как Менабре видел Analytical Engine прежде всего как инструмент для автоматизации «длинных и засушливых вычислений», который высвободил бы интеллектуальные способности блестящих ученых для более продвинутого мышления. Чудесная дальновидность, которую Лавлейс продемонстрировала в Примечании А — одна из основных причин того, что ее прославляют сегодня.

Другая известная заметка — примечание G. Лавлейс начинает примечание G, утверждая, что, несмотря на его впечатляющие мощности, нет никаких оснований считать, что Analytical Engine сможет думать. Эта часть примечания G — это то, что Алан Тьюринг позже назвал « Возражение Леди Лавлейс ». Тем не менее, продолжает Лавлейс, машина может делать необычные вещи. Чтобы проиллюстрировать ее способности справляться с еще более сложными проблемами, Лавлейс прилагает свою программу, вычисляющую числа Бернулли.

Полную программу в расширенном формате «диаграммы развития», которую Лавлейс объясняет в примечании D, можно увидеть здесь. Программа по сути представляет собой список операций, заданных с использованием обычных математических символов. Не похоже, что Бэббидж или Лавлейс дошли до разработки чего-либо вроде набора операционных кодов для Analytical Engine.

Хотя Лавлейс описывала метод вычисления всей последовательности чисел Бернулли до некоторого предела, программа, которую она предоставила, иллюстрировала только один шаг этого процесса. Ее программа рассчитала номер, который она назвала B7, который современные математики знают как восьмое число Бернулли. Таким образом, ее программа стремилась решить следующее уравнение:

В приведенном выше уравнении каждый член представляет собой коэффициент в формуле многочлена для суммы целых чисел с определенной степенью. Здесь эта степень равна восьми, так как восьмое число Бернулли впервые появляется в формуле для суммы целых положительных чисел в восьмой степени. Числа B и A представляют два вида множителей, обнаруженных Бернулли. B1-B7 — все разные числа Бернулли, индексированные в соответствии с индексацией Лавлейс. A0 — A5 — множители коэффициентов, которые Бернулли мог рассчитать с помощью треугольника Паскаля. Ниже приведены значения A0, A1, A3 и A5. Здесь n представляет собой индекс числа Бернулли в последовательности нечетных чисел Бернулли, начиная с первого. В программе Лавлейс n = 4.

Я создал перевод программы Лавлейс на C, что может быть проще. Сначала программа Лавлейс вычисляет A0 и результат B1A1. Затем вводит цикл, который дважды повторяется для вычисления B3A3 и B5A5, поскольку они формируются по идентичной схеме. После того, как каждый результат рассчитан, он складывается со всеми предыдущими результатами, так что к концу программы будет получена полная сумма.

Очевидно, перевод C не является точным воссозданием программы Лавлейс. Например, он объявляет переменные в стеке, тогда как переменные Лавлейс больше напоминают регистры. Но это делает очевидными «провидческие» части программы Лавлейс. Программа C содержит два цикла while, один из которых находится внутри другого. В программе Лавлейс не было циклов while, но она делала группы операций и в тексте своей заметки указывала, когда они должны повторяться. Переменная v10, в исходной программе и в C-переводе, функционирует как переменная-счетчик, которая уменьшается с каждым циклом — конструкция знакомая каждому программисту. На самом деле, помимо изобилия переменных с бесполезными именами, C-перевод программы Лавлейс вовсе не выглядит таким уж чужеродным.

Еще одна вещь, о которой стоит упомянуть, заключается в том, что перевод программы Лавлейс на C не был трудным, благодаря деталям, представленным на ее диаграмме. В отличие от таблиц Менабре, ее таблица включает столбец с надписью «Индикация изменения значения на любой переменной», что значительно облегчает отслеживание мутации состояния во всей программе. Она добавляет надстрочный индекс для каждой переменной, чтобы указать последующие значения, которые они хранят. Например, верхний индекс двух означает, что значение, используемое здесь, является вторым значением, которое было назначено переменной с начала программы.

Первый программист?

После того, как я перевел программу Лавлейс на C, мне удалось запустить ее на своем компьютере. К моему разочарованию, я продолжал получать неправильный результат. После некоторой отладки я наконец понял, что проблема не в том, что я написал. Ошибка была в оригинале!

В своей «диаграмме развития» Лавлейс дает четвертую операцию как v5 / v4. Но правильный порядок здесь — v4 / v5. Возможно, это была ошибка набора, а не ошибка в программе, разработанной Лавлейс. Тем не менее, это должно быть самая старая ошибка в вычислениях. Меня поразило, что в течение десяти минут или около того, даже не подозревая, я боролся с этой первой ошибкой.

Джим Рэндалл, еще один блоггер, который перевел программу Лавлейс на Python, отметил эту ошибку подразделения и две другие проблемы. Что говорит об Аде Лавлейс то, что ее опубликованная программа содержит незначительные ошибки? Возможно, это показывает, что она пыталась написать не просто демонстрацию, а настоящую программу. В конце концов, возможно ли действительно писать что-то большее, чем игрушечные программы, без кучи багов?

Одна статья из Википедии называет Лавлейс первой, кто опубликовал «сложную программу». Возможно, это правильный способ оценки достижений Лавлейс. Менабре опубликовал «диаграммы развития» в своей статье за ​​год до того, как Лавлейс опубликовал свой перевод. Бэббидж также написал более двадцати программ, которые никогда не публиковал. Так что не совсем верно говорить, что Лавлейс написала или опубликовалаа первую программу, хотя всегда можно обсудить, что именно представляет собой «программу». Тем не менее, программа Лавлейс была намноговпереди всего, что было опубликовано ранее. Самая длинная программа, представленная Менабре длилась 11 операций и не содержала циклов или разветвлений; Программа Лавлейс содержит 25 операций и вложенный цикл (и, следовательно, ветвление). Менабре написал следующее в конце своей статьи:

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

Ни Бэббидж, ни Менабре не были особо заинтересованы в применении Analytical Engine к проблемам, выходящим за рамки непосредственных математических задач, которые вначале побудили Бэббиджа построить вычислительные машины. Лавлейс увидела, что Analytical Engine способен на гораздо большее, чем мог вообразить Бэббидж или Менабре. Лавлейс также поняла, что «изготовление карт» не будет просто второстепенным и что это может быть сделано хорошо или сделано плохо. Это трудно ценить без понимания ее программы из примечания G и не видя усилия, которые она приложила к разработке. Но, сделав это, вы можете согласиться с тем, что Лавлейс, даже если не была самым первым программистом, то точно была первым программистом, который заслужил этот титул.