2.6. ИСТОРИЯ И БИБЛИОГРАФИЯ

Линейные списки и прямоугольные массивы информации, содержащиеся в последовательных ячейках памяти, широко использовались с первых дней появления компьютеров с хранимой программой, и в самых ранних работах по программированию приведены базовые алгоритмы для прохождения этих структур. [См., например, J. von Neumann, Collected Works 5, 113-116 (написана в 1946 году); М. V. Wilkes, D. J. Wheeler, S. Gill, The Preparation of Programs for an Electronic Digital Computer (Reading, Mass.: Addison-Wesley, 1951), subroutine V-1. Обратите особое внимание па работу Конрада Зусе (Konrad Zuse) Berichte der Gesellschaft fur Mathematik und Datenverarbeitung 63 (Bonn, 1972), написанную в 1945 году. Зусе первым создал нетривиальные алгоритмы для работы со списками динамически изменяемой длины.] До появления индексных регистров работа с последовательными линейными списками выполнялась при помощи арифметических операций над самими машинными командами, и использование такой арифметики стало одним из самых ранних обоснований создания компьютеров, в которых программа разделяла с обрабатываемыми данными общее пространство памяти.

Технологии, позволяющие линейным спискам переменной длины занимать последовательные адреса памяти таким образом, чтобы при необходимости их можно было сдвигать в ту или иную сторону, как описано в разделе 2.2.2, были, по-видимому, гораздо более поздним открытием. Д. Данлэп (j, Dunlap) из Digitek Corporation разработал такие технологии до 1963 года в связи с созданием ряда компилирующих программ. Примерно в то же время данная идея независимо возникла при создании компилятора COBOL в IBM Corporation и набора связанных с ним подпрограмм, называвшегося CITRUS, который впоследствии использовался в различных компьютерах. Технологии оставались неопубликованными до тех пор, пока не были независимо разработаны Яном Гарвиком (Jan Garwick) из Норвегии; см. BIT 4 (1964), 137-140.

Идея размещения линейного списка не в последовательных ячейках памяти, видимо, появилась в связи с разработкой компьютеров с устройствами храпения информации на магнитных барабанах. После выполнения команды из ячейки п такой компьютер обычно не был готов к работе с командой из следующей ячейки п+1, так как барабан уже прошел эту точку. В зависимости от выполняющейся команды наиболее благоприятным местом расположения следующей команды может оказаться, например, ячейка п + 7 или п -f 18, и при оптимальном размещении команд быстродействие машины может увеличиться в 6-7 раз. [Обсуждение интересных задач, относящихся к оптимальному расположению команд, можно найти в статье автора этой книги в JACM 8 (1961), 119-150.] Поэтому в каждой машинной команде появлялось дополнительное адресное поле, служившее связью со следующей командой. Такая идея, названная "адресация 1-1-1", обсуждалась в работе John Mauchly, Theory and Techniques for the Design of Electronic Computers 4 (U. of Pennsylvania, 1946), Lecture 37. В ней в зачаточной форме содержится понятие связанного списка, хотя так часто использовавшиеся нами в этой главе операции динамической вставки и удаления оставались неизвестными. Другое раннее упоминание о связях в программах приведено в меморандуме Г. П. Лана (Н. Р. Lubn) (1953 г), в котором для внешнего поиска предлагалось применять "цепочки" (см. раздел 6.4).

Реально технологии использования связанной памяти родились, когда А. Нью-велл (А. Newell), Д. К. Шоу (j. С. Shaw) и Г. А. Саймон (Н. А. Simon) начали свои исследования эвристическ<:}го решения задач с помощью компьютера. Весной 1956 года для написания программ поиска доказательств в математической логике они разработали первый язык обработки списков - IPL-II. (IPL означает Information Processing Language - язык обработки информации.) Это была система, использующая указатели и включающая важные концепции наподобие списка свободного пространства, однако концепция стека тогда еще не была достаточно разработана. Созданный годом позже IPL-III включал команды для помещения в стек и выборки из стека в качестве важных основных операций. [Подробнее о IPL-II речь идет в IRE Transactions IT-2 (September, 1956), 61-70; Proc. Western Joint Сотр. Conf. 9 (1957), 218-240. Материалы no IPL-III впервые появились в виде конспекта лекций в Университете штата Мичиган летом 1957 года.]

Работа Ньювелла, Шоу и Саймона привлекла многих исследователей к использованию связанной памяти, которую в то время часто называли по первым буквам фамилий авторов NSS-памятью, но, в основном, для решения задач, связанных с моделированием человеческого мышления. Постепенно эти технологии стали базовыми инструментами программирования. Первая статья, описывающая эффективность связанной памяти для выполнения "приземленных" задач, была опубликована Д. В. Карром П1 (J. W. Сагг Ш) в САСМ 2,2 (February, 1959), 4-6. В ней Карр указал, что связанными списками легко манипулировать на обычных языках программирования без привлечения изощренных подпрограмм или интерпретирующих систем. [См. также С. А. Blaauw, "Indexing and control-word techniques", IBM J. Res. and Dev. 3 (1959), 288-301.]

Сначала для связанных таблиц использовались узлы из одного слова, но около 1959 года постепенно различные коллективы убедились в преимуществах узлов из нескольких последовательных слов и "многосвязных" списков. Первой статьей, посвяш,енной сугубо этой идее, была статья D Т. Ross, САСМ 4 (1961), 147-150. В то время для того, что в настоящей главе мы называем узлом, автором указанной статьи использовался термин "плекс" (plex), хотя позднее он употреблял это слово в другом смысле-для описания класса узлов в комбинации с алгоритмами их прохождения.

Обозначения для ссылки на поле в узле, в основном, бывают двух видов: имя поля либо предшествует обозначению указателя, либо следает за ним. Таким образом, то, что в данной главе записывается как "INFO(P)", некоторые авторы записывают как "Р. INFO". Во время создания этой главы обе записи, пожалуй, встречались одинаково часто. Запись, принятая в настояш,ей книге, имеет то достоинство, что она непосредственно транслируется на языки FORTRAN, COBOL и подобные, если определить массивы INFO и LINK и использовать в качестве индекса Р. Кроме того, представляется естественным использовать обозначения математической функции для описания атрибутов узла. Заметьте, что "INFO(P)" произносится как "INFO от Р", как принято в математике - f{x) вербально передсьется как "/ от х". Альтернативное обозначение "Р.INFO" менее естественно, поскольку имеет тенденцию к подчеркиванию Р, хотя и может быть прочитано как "Р-е INFO". Причина, по которой INFO(P) кажется более предпочтительным способом записи, по-видимому, заключается в том, что Р - переменная, а INFO имеет конкрет-

ный смысл при использовании записи. По аналогии можно рассматривать вектор А = у1[2], ..., yl[l6o]) как узел, имеющий 100 полей с именами 1,2,..., 100. Теперь на второе поле в цаших обозначениях можно сослаться как "2(Р)", где Р указывает на вектор А; но если ссылаться на j-й элемент вектора, то более естественно записать "A[j]", помещая переменную "j" второй. Точно так представляется более подходящей запись INFO(P) с переменной "Р" на втором месте*.

Возможно, первыми, кто увидели в концепциях стека ("последним вошел - первым вышел"; last-in-first-out) и очереди ("первым вошел - первым вышел"; first-in-first-out) важные объекты изучения, были бухгалтеры, заинтересованные в упрощении процесса начисления подоходных налогов. Обсуждение методов LIFO и FIFO при составлении прайс-листов можно найти в любом учебнике среднего уровня для бухгалтеров [см., например, С. Р. and W. J. Schlatter, Cost Accounting (New York: Wiley, 1957), Chapter 7]. В середине 40-х годов А. М. Тьюринг (А. М. Turing) разработал механиз.м стека, названный реверсивной памятью, для связывания подпрограмм, локальных переменных и параметров. Тьюринг использовал для принятых ныне понятий "добавление в стек" и "снятие со стека" (push/pop) понятия "закапывать" (bury) и "откапывать" (disinter/unbury) (см. ссылки в разделе 1.4.5). Несомненно, простые применения стеков, расположенных в последовательных адресах памяти, в програм.мировании с первых дней были обычным делом, поскольку стек представляет собой интуитивно понятную и естественную концепцию. Программирование стеков в связанном виде появилось впервые в IPL, как упоминалось выше; и.мя "стек" происходит из терминологии IPL (хотя в IPL имелся более официальный термин "pushdown list") и независимо введено Э. В. Дейкстрой (Е. W. Dijkstra) [Numer. Math. 2 (1960), 312-318]. Термин "дек" (deque) был введен Э. Ю. Швеппе (Е. J. Schweppe) в 1966 году.

Происхождение Щ1клических списков и списков с двойными связями не ясно. Вероятно, эти идеи многим показались естественными. Важным фактором в популяризации этих технологий было существование основанных на них систем общего назначения для обработки списков [см. Knotted List Structures, САСМ 5 (1962), 161-165, и Symmetric List Processor, CACM 6 (1963), 524-544, Й. Вейзенбаума (J. Weizenbaum)]. Айвен Сэтерленд (Ivan Sutherland) ввел в использование независимые двусвязные списки в больших узлах в своей системе Sketchpad (Ph. D. thesis, Mass. Inst, of Technology, 1963).

С первых "компьютерных" дней многие квалифицированные программисты независимо разработали различные методы адресации и прохождения многомерных массивов информации. Таким образом была рождена еще одна часть неопубликованного компьютерного фольклора. Обзор этой темы можно найти в работе Н. Hellerman, САСМ 5 (1962), 205-207 [см. также J. С. Gower, Сотр. 3. 4 (1962), 280-286].

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

* Аргументация автора безупречна, но... "меняется все в наш век перемен" и место FORTRAN и COBOL заняли языки С-(-f, Pascal и Java (а также Visual Basic и многие другие), в которых полна смысла именно запись Р.INFO - "поле INFO структуры Р" (или "записи" и т. п. - название варьируется в зависимости от языка программирования). Что же касается аналогии с массивом, то в том же С или C--f на элементы массива а[] можно ссылаться и как на a[j], и как на j [а] . - Прим. перев.