О модели программы
Чтобы иметь программу, мы должны сначала составить ее. Когда она у нас появится, мы должны будем ее выполнять (если ее изготовление имело хоть какой-то смысл). В этом разделе мы будем уделять мало внимания действиям по составлению и выполнению программы, а попытаемся рассматривать программу как статический объект. Мы хотим рассматривать ее как объект со сложной структурной организацией, и основной вопрос состоит в следующем: какие типы структур мы предусматриваем и почему. Надеемся, что в конце концов добьемся такой структуры программ, которая окажется идеальной и для процесса составления, и для последующего ее выполнения. Разумеется, я всегда помню об этих процессах, но здесь мне не хочется их обсуждать; в частности, я не хочу затрагивать методологические вопросы (продвигаться ли "снаружи внутрь" или наоборот) и вообще не собираюсь заниматься здесь проблемами реализации программ.
Коль скоро нас интересует программа сама по себе, то основным предметом обсуждения становится, по-видимому, наше желание, чтобы программа была записана именно так, как мы ее понимаем и как хотели бы объяснять ее другим людям. Однако без дальнейших уточнений все это выглядит пустыми отеческими поучениями; поэтому я попытаюсь внести больше ясности.
Рассмотрим очень простое вычисление, в котором можно выделить три различных действия, выполняемых последовательно, например ввод данных, обработка (т. е. собственно вычисление) и вывод результатов. Одним из способов представления такой программы является длинная цепочка операторов:
begin
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . end
Вводя для наглядности метки, получаем такую форму записи:
begin начало ввода: . . . . . . . . . . . начало обработки: . . . . . . . . . . . начало вывода: . . . . . . . . . . . end
При такой записи мы, читая текст, знаем, что нас ждет впереди.
Еще лучше писать так:
begin ввод: begin . . . . . . . . . . . . . . end; обработка: begin . . . . . . . . . . . . . . end; вывод: begin . . . . . . . . . . . . . . end; end
Здесь метки рассматриваются не столько как указатели точек в тексте программы, сколько как названия областей (ограниченных парами скобок begin-end), которые следуют за этими метками, или же как названия трех действий, на которые разложено вычисление. Однако если мы принимаем такую точку зрения, то три "метки" все равно остаются комментариями, т. е. пояснительным фоном для пользы любознательных читателей, тогда как мне хотелось бы рассматривать их как неотъемлемую часть программы. Для меня желательно, чтобы текст моей программы как-то отражал тот факт, что вычисление было разложено на последовательные три действия, независимо от того, как будут выглядеть эти действия при детальном рассмотрении. Это можно сделать, выписав где-то "текстуальную" последовательность из трех (абстрактных) операторов
ввод; обработка; вывод
в предположении, что последовательность выполнения этих трех действий будет на самом деле управляться данной текстуальной последовательностью. Причем дальнейшая конкретизация этих трех действий будет задана "где-то еще", возможно, по отдельности, и уж во всяком случае без соблюдения относительного порядка.
Итак, если бы замкнутые подпрограммы не были изобретены более чем двадцать лет тому назад, то сейчас было бы самое время ввести их! Другими словами, мы возвращаемся к привычным понятиям, и настолько привычным, что многие читатели даже испытывают разочарование. Лично я его не испытываю, так как нет ничего зазорного в том, чтобы придерживаться проверенного метода все время, пока он удовлетворяет нас. Однако нам следует ясно осознать те преимущества, которые мы хотим из него извлечь; в случае необходимости мы должны доработать его, и, наконец, нам надлежит четко установить правила его использования. Поэтому я позволю себе дать обзор понятия подпрограммы с тем большим основанием, что мое мнение об этом понятии изменилось в течение последнего года.
Впервые я познакомился с понятием замкнутой подпрограммы в связи с системой EDSAC [Wilkes М. V.
, Wheeler D. J., Gill S., The Preparation of Programsfor an Electronic Digital Computer; with Special Reference to the EDSAC and the use of a Library of Subroutins, Addison-Wesley Press, 1951.], где понятие подпрограммы служило основой библиотеки стандартных программ. В те времена конструирование машинной аппаратуры было рискованным делом, и многие стандартные программы служили для расплаты и без того малой памятью и временем счета за несовершенство электронных схем; если в машинном коде не предусматривалась операция деления, то обзаводились подпрограммами деления. Однако, как ни странно, я не припоминаю, чтобы какие-то подпрограммы получили признание как средство "перестройки" имеющейся машины в более удобную. Мне не помнится также, чтобы в те времена пользователи проектировали и строили подпрограммы, отражая в них анализ своих задач. Преимущественно дело сводилось к стандартным программам, по отношению к которым пользователь выступал только в роли потребителя. В конечном счете я видел в них главным образом средство сокращения длины программы. Вся же программа в целом по-прежнему воспринималась как действие в рамках единой однородной памяти в пространстве состояний команд; весь счет оставался единым последовательным процессом, выполняемым одним процессором.
В последующие годы я прочел много курсов программирования, истово проповедуя это учение, и часто объяснял, как при обращении передается адрес возврата и как затем выполнение подпрограммы начинается с установки "связи", т. е. команды возврата в конце подпрограммы. Теперь я склонен считать, что основная программа имеет свой собственный счетчик команд, который сразу же продолжает продвигаться после завершения выполнения подпрограммы, и уж, конечно, не стану рассматривать "застывшее значение" этого счетчика как параметр, передаваемый подпрограмме. (Прежняя концепция все еще довлеет над структурой многих машин. Мы встречались с машинами, в которых при обращении к подпрограмме связь запоминается по "адресу нуль" в подпрограмме, тогда как первая выполняемая команда подпрограммы подразумевается по "адресу один"; при такой организации затруднена реализация реентерабельности и рекурсивных подпрограмм.
Даже в текущем десятилетии встречаются машины, которые при прерывании запоминают "состояние" прерванной программы в ячейках, соответствующих прерывающей, а не прерываемой программе!)
Десятью годами позже, когда появился АЛГОЛ-60, декорации переменились, и мы перестали говорить о замкнутых подпрограммах: отныне мы называли их "процедурами". Они по-прежнему воспринимались программистами как очень удобное средство сокращения текста программы; однако программисты все чаще и чаще начинали использовать их в целях структурной организации с таким расчетом, чтобы приспособление программы к ожидаемым изменениям постановки задачи могло свестись к замене одного или нескольких тел процедур или же к изменению некоторых фактических параметров в каком-то обращении к процедуре. Но основным новшеством явилось понятие локальных переменных.
Это понятие получило отражение в двух важных аспектах. Первым было понятие "области действия", т. е. идея о том, что не все переменные одинаково доступны на протяжении всей программы: локальные переменные процедуры не доступны вне тела этой процедуры, так как вне процедуры они не имеют никакого смысла. Только самой процедуры касается, какие локальные переменные нужны ей для выполнения стоящей перед ней задачи; основной программе нет до этого дела, и понятие "области действия" рационально отражает тот факт, что основную программу можно (и нужно!) представлять себе вне связи с этими локальными переменными. Мы можем не вполне одобрять принятые в языке АЛГОЛ-60 конкретные правила образования областей действия, но нам следует признать, что это был весьма значительный шаг в правильном направлении.
Второй аспект новизны определялся тем фактом, что процедуры могут использоваться рекурсивно, а точнее говоря, тем, что процедуре разрешается обращаться к самой себе прямо или косвенно. В прошлом многие горячо оспаривали оправданность этой возможности. Насколько я могу судить, теперь пыл этих страстей уже утих. Возражения против рекурсивных процедур всегда сводились к ссылкам на потерю эффективности: нереентерабельная программа могла бы выполняться гораздо более эффективно.
Однако с появлением мультипрограммирования возник дополнительный стимул для гибкой организации памяти. И если даже еще существуют вычислительные машины, в которых нереентерабельная программа может выполняться гораздо эффективнее, а за применение рекурсивных подпрограмм приходится расплачиваться слишком дорогой ценой, то я беру на себя смелость утверждать, что теперь следует называть такую машину старомодной. Если мы пользуемся рекурсивной процедурой, то должны четко осознавать разницу между ее статическим текстом и динамическим выполнением. Одно дело - текст процедуры и совсем другое - множество обрабатываемых ею в данное время локальных переменных.
Все это хорошо, но теперь настало время поговорить о недостатках (не знаю уж, назовете ли вы их лингвистическими или логическими). Локальные переменные "создаются" при входе в процедуру и "ликвидируются" при выходе из нее. Именно это автоматическое регулирование времени существования переменных, относящихся к выполнению процедуры, позволяет нам реализовывать (рекурсивные) процедуры с помощью стека (т. е. организации памяти по принципу "последним пришел - первым ушел"). То обстоятельство, что относящиеся к выполнению процедуры локальные переменные существуют только во время этого выполнения, делает невозможной "закулисную" передачу информации от одного выполнения процедуры к другому.
Чтобы обойти эту трудность, ввели понятие "own" (собственная переменная), но это не решило проблему: в случае рекурсии становится весьма сомнительной реальная польза от собственных переменных, а кроме того, нет возможности написать набор процедур с общими собственными переменными. (Мы можем прибегнуть к моделированию, описав такие переменные во внешнем блоке, объемлющем описания данных процедур, но тогда эти переменные станут слишком доступными в силу определения области действия, а, следовательно, их уже нельзя считать "закулисными"). Отсюда следует вывод - совсем не новый и разделяемый многими - о том, что понятие "own" в том виде, как оно введено в АЛГОЛе-60, следует признать неудачным и что мы должны искать новые способы регулирования и описания времени существования, доступности и идентичности локальных переменных.
Я недоволен понятием процедуры еще и потому, что оно по-прежнему представляется в первую очередь средством сокращения текста программы (впрочем, в случае рекурсии длина текста может оказаться неизвестной).
Семантика обращения к процедуре описывается с помощью известного "правила копирования": обращение к процедуре должно пониматься как сокращенное обозначение, поскольку семантика гласит, что следует заменить это обращение копией текста тела процедуры (с надлежащим согласованием идентификаторов и с подстановкой параметров), после чего модифицированный текст будет выполняться той же машиной, которая выполняет основную программу. Внешне это выглядит так, что единый текст программы должен выполняться единственной последовательной машиной. И именно эта картина единственной машины перестает удовлетворять меня.
Я хочу считать, что основная программа выполняется своей собственной, предназначенной только для нее машиной, снабженной подходящим набором команд применительно к соответствующим переменным и управляемой с помощью собственного счетчика команд. Короче говоря, должно иметься все необходимое для того, чтобы наша основная программа могла решить задачу, если в нашем распоряжении находится такая машина. Такая точка зрения позволяет опираться на тот факт, что правильность основной программы может обсуждаться и доказываться независимо от наличия этой (возможно, все же умозрительной) машины. Нам только необходимо иметь описание этой машины, достаточное для того, чтобы правильно понимать выполнение рассматриваемой основной программы.
Лично для меня понятие умозрительной машины - это порождение моего абстрактного мышления, и в этом смысле я не вижу принципиального отличия от обычного способа понимания программы, написанной на так называемом языке высокого уровня., когда мы не знаем, как выполняются различные виды операций (наподобие умножения и вычитания), и не знаем таких несущественных деталей, как система счисления, применяемая в аппаратуре, обеспечивающей в конечном итоге выполнение программы.
Разумеется, на самом деле такой идеальной машины не существует, и поэтому наша следующая задача - структурно аналогичная исходной задаче - состоит в том, чтобы запрограммировать моделирование машины "верхнего уровня".
Программируя такое моделирование, мы должны так организовать структуры данных, чтобы предусмотреть все разнообразие состояний машины верхнего уровня; более того, нам нужен набор алгоритмов, каждый из которых обеспечивает выполнение некой инструкции из системы команд машины верхнего уровня. И наконец, в машине "нижнего уровня" могут иметься некоторые частные переменные, введенные только для ее надобностей и не имеющие никаких аналогов в рамках машины верхнего уровня. Однако весь этот комплекс программ пишется для машины, которая, по всей видимости, не будет физически существовать, и поэтому следующим этапом будет моделирование ее с помощью программ для машины еще более низкого уровня и так далее до тех пор, пока мы наконец не получим программу, которую можно выполнить с помощью имеющегося у нас машинного оборудования.
Если мы преуспели в построении своей программы по такому плану, то мы тем самым расположили эту программу на нескольких слоях. Каждый программный слой должен пониматься совершенно независимо от других в предположении, что имеется машина, соответствующая выполнению этого слоя. В то же время функция каждого слоя состоит в моделировании машины, которая соответствовала бы ближайшему более высокому уровню. Почему выбрана именно эта модель? Каких преимуществ мы рассчитываем добиться с ее помощью? Я попытаюсь перечислить эти преимущества.
(1) Как отмечалось в разделе "Первый пример поэтапного составления программы", наш программистский опыт убедительно свидетельствует о том, что организация различных слоев, соответствующих разным уровням абстракции, очень помогает составлению программы.
(2) Есть основания надеяться, что многие модификации программ могут быть теперь представлены заменой одной (умозрительной) машины другой подходящей машиной.
(3) Можно надеяться, что эта модель позволит нам лучше справляться с проблемами, которые возникают, когда нужно модифицировать программу во время ее работы. Если машина на некотором уровне остановлена между двумя своими командами, то все машины нижних уровней полностью отключены и могут быть заменены, тогда как для каждой машины верхнего уровня следует считать, что произошло прерывание во время выполнения команды, а их состояние нужно рассматривать как переходное.
В последовательностной машине допускается интерпретация состояния только в промежутках между выполнением команд, и описанная нами иерархия машин, у каждой из которых имеется свой собственный счетчик команд (подсчитывающий именно ее команды), оказывается более удобной, если мы хотим применительно к каждому конкретному моменту решать, какие интерпретации справедливы. Для обычного языка программирования, где прогресс вычислений измеряется однородной мерой, скажем с точностью до одного оператора, мы испытываем некоторую беспомощность, когда сталкиваемся с вопросом, какие интерпретации справедливы в те или иные моменты.
(4) Можно надеяться, что эта модель поможет нам даже справиться (частично или полностью) с проблемами, возникающими после обнаружения некоторой функциональной некорректности. (Недавно я участвовал в проектировании и разработке одной системы мультипрограммирования, и чуть ли не больше всего нам досаждала наша полная неспособность оценить (механически) границы области бедствия, когда какая-то ячейка памяти выдавала сигнал ошибки по четности. Единственная защитная реакция, которую мы смогли реализовать, состояла в немедленном прекращении работы машины, и вряд ли таким решением можно гордиться.) (5) Эта картина иерархического расслоения машин выявляет одну из опасностей чрезмерного применения принципа "разделяй и властвуй", когда различные компоненты программируются настолько независимо друг от друга, что возникает дублирование работы (или что-нибудь похуже). Говоря, что слой содержит набор программ для некоторой умозрительной машины, мы подчеркиваем этим подразумеваемое наличие общего фонда примитивных подпрограмм для этого набора. Разделение работы - хорошая вещь, но нужно это делать так, чтобы суметь потом связать концы с концами.
