О расплате машинной памятью за ускорение вычислений
В нынешних последовательных вычислительных машинах (я пишу эти строки весной 1969 г.) можно выделить два основных компонента: активный (процессор) и пассивный (память). Активный компонент должен быть быстрым, а пассивный должен быть большим. Далее мы будем рассуждать в предположении, что это разделение функций сохранится еще довольно долго, так что имеет смысл изучать вытекающие из него следствия.
С точки зрения программиста, машинная память и время счета это два различных ресурса, и я считаю, что именно программист (а не система) должен нести ответственность за их распределение, т. е. за разделение между ними необходимой нагрузки. Данный раздел посвящен разбору следствий этой обязанности программиста. Мы не собираемся рассматривать конкретные методы оценки нагрузок, т. е. давать количественные критерии, которыми программист руководствовался бы при своем выборе. Вместо этого мы изучим логическую связь между различными вариантами, которые волен выбирать сам программист.
Замечание. Не исключено, что этот выбор частично может быть возложен на систему. Однако во всех сколько-нибудь нетривиальных случаях проектирование распределения и установление эквивалентности требуют, по-видимому, математической изобретательности программиста. Все попытки автоматизировать этот род интеллектуальной деятельности выходят за рамки этой работы.
В простейшем случае мы имеем дело с вычислением, при котором регулярно требуется значение "ФУН(арг)", где "ФУН" - заданная вычислимая функция, определенная для текущих значений одной или нескольких хранимых в памяти переменных под общим названием "арг". При варианте программы A запоминается только значение арг, а значение ФУН(арг) вычисляется всякий раз, когда оно понадобится. При варианте B вводится дополнительная переменная, скажем фун, назначение которой состоит в том, чтобы хранить значение "ФУН(арг)", соответствующее текущему значению арг.
Если вариант A содержит
арг:= ... (т. е. присваивание значения арг)
то вариант B будет содержать
арг:= ...; фун : = ФУН(арг)
Этим обеспечивается сохранение отношения
фун = ФУН (ар г)
В результате выполнения этого отношения всякий раз, когда вариант A требует вычисления ФУН(арг), вариант B обратится к текущему значению переменной фун. Вариант B может быть предпочтен варианту A по двум причинам. Если значение ФУН(арг) требуется чаще, чем происходит перевычисление арг, то вариант B потребовал бы меньше времени счета. В случае необходимости этот прием может быть развит путем введения еще одной (на этот раз логической) функции "фун текущ", указывающей, выполняется ли отношение "фун = ФУН(арг)". В таком случае присваивание нового значения арг связывается с выполнением
фун текущ:=false
Всякий раз, когда требуется значение ФУН(арг), мы проверяем значение этой логической переменной и получаем ответ, следует ли перевычислять заново ФУН(арг). Если да, то вычисляемое значение присвоится переменной фун, а переменная "фун текущ" в соответствии со своим смыслом получит новое значение true. Назовем этот последний вариант программы именем C. Очевидно, что все три программы эквивалентны с точки зрения получаемых окончательных результатов и отличаются только в тех местах, где вариант A перевычисляет арг или использует значение ФУН(арг). Разумеется, ниоткуда не следует, что вариант B или C должен быть получен из варианта A автоматически. Однако весьма часто ситуация оказывается не столь простой, и теперь мы переходим к рассмотрению второй причины для введения такой переменной "фун". Часто бывает очень неудобно вычислять ФУН(арг) "из ничего" для произвольных значений арг, тогда как гораздо легче посчитать, как изменяется значение ФУН(арг) при данном изменении значения арг. В таких случаях корректировка значения "фун" ближе отражает существо функциональной зависимости, чем это подразумевается действием
арг:= ......; фун:=ФУН(арг)
Часто такая возможность бывает близко связана не только с существом функциональной зависимости, но также и с "историей переменной арг" в процессе счета! Мы наблюдали впечатляющий пример в программе табулирования простых чисел (см.
При тщательном изучений выяснилось, что существовала вторая комбинаторная головоломка, причем можно было установить взаимно однозначное соответствие между решениями этих двух задач. Если бы я решал вторую комбинаторную задачу, то нашел бы, что "фун" и "арг" поменялись ролями! В рамках традиционного программирования, которое не способствует выявлению таких функциональных зависимостей, обе, головоломки могли бы, вероятно, быть решены с помощью одинаковых программ, тогда как я изготовил две программы с различной структурной организацией. И я полагаю, что поступил правильно, так как единая программа для обеих головоломок требовала бы различных доказательств ее правильности в зависимости от того, какую головоломку предполагается решать, а это оборачивается некоторой несправедливостью, если мы хотим также, чтобы наше понимание вычислений отражалось в структуре наших программ.
раздел "Первый пример поэтапного составления программы") в связи с введением переменной ord, которая функционально зависит от j, а точнее говоря, представляет минимальное значение, удовлетворяющее условию
p[ord]2>j
причем корректировка ord оказалась весьма удобной операцией благодаря тому, что значения j монотонно возрастали со временем. Мне бы хотелось, чтобы в процессе понимания программ легко распознавались такие дополнительные переменные, хранящие избыточную информацию, даже если при этом функциональная зависимость несколько неопределенна, как в случае таблицы "крат" из того же примера. Я склонен рассматривать такие программы как некие оптимизированные конкретизации более абстрактной программы, даже если достигаемая введением дополнительных переменных оптимизация играет существенную роль в обеспечении эффективности программы. С точки зрения эффективности такая дополнительная переменная может оказаться настолько важной, что утратой чувства реальности обернулась бы попытка рассуждать на таком уровне, где мы абстрагируемся от наличия этой переменной. Способ обращения с такой дополнительной переменной часто оказывается существом алгоритма, и именно здесь мы часто пожинаем плоды своей математической изобретательности. Дело в том, что, хотя возможность хотя бы одной такой оптимизирующей конкретизации является существенной для изготовления практичной программы, часто при более внимательном изучении выясняется, что даже на самом низком уровне имеется выбор между различными оптимизирующими конкретизациями.
Замечание. Я вспоминаю одну программу, где дополнительная информация была настолько избыточной, что можно было бы не только вывести значение "фун" из "арг", но и наоборот. Зависимость между "фун" и "арг" неожиданно оказалась симметричной, и я был всерьез озадачен: с какой это стати я обращаюсь с ними столь несимметрично. Программа, о которой идет речь, порождала все решения комбинаторной головоломки.
