шинный язык для ряда ранних компьютеров использовал трехадресный код для представления вычислений арифметических выражений; последний эквивалентен INFO, LLINK и RLINK бинарного представления дерева. В 1952 году Г. Д. Кахримани-ан (Н. G. Kahrimanian) разработал алгоритмы для дифференцирования алгебраических формул, представленных в расширенном трехадресном коде [см. Symposium on Automatic Programming (Washington, D.C.: Office of Naval Research, May, 1954), 6-14].

С тех пор древовидные структуры различных видов независимо изучались многими исследователями в связи с их применением во многих компьютерных приложениях. Однако в публикациях основные технологии для работы с деревьями (не со списками) появлялись лишь в составе описаний отдельных алгоритмов. Первый общий обзор был сделан в связи с изучением структур данных в работе К. Е. Iverson and L. R. Johnson [IBM Corp. research reports RC-390, RC-603, 1961]; см. также Iverson, A Programming Language (New York: Wiley, 1962), Chapter 3, и G. Salton, CACM 5 (1962), 103-114.

Концепция прошитых (threaded) деревьев принадлежит A. Д. Перлису (А. J. Perils) и Ч. Торнтону (С. Thornton) [САСМ 3 (1960), 195-204]. В их статье вводится также важная идея прохода деревьев в различных порядках и приводятся многочисленные примеры алгоритмов алгебраических манипуляций. К сожалению, эта важная статья готовилась наскоро и содержит много опечаток. Прошитые списки Перлиса и Торнтона в нашей терминологии представляют собой правопрошитые деревья. Бинарные деревья, прошитые в обоих направлениях, были независимо открыты А. В. Хольтом (А. W. Holt), А Mathematical and Applied Investigation of Tree Structures (Thesis, U. of Pennsylvania, 1963). Прямой и непрямой порядки узлов деревьев в работе Z. Pawlak, Colloquium on the Foundation of Mathematics, Tihany, 1962 (Budapest: Akademiai Kiado, 1965), 227-238, назывались "нормальный прямой порядок" и "дуальный прямой порядок". В приведенной выше работе Айверсон и Джонсон назвали прямой порядок порядком поддеревьев. Графические способы представления связей между древовидными структурами и соответствующими линейными обозначениями были описаны в А. G. Oettinger, Proc. Harvard Symp. on Digital Computers and their Applications (April, 1961), 203-224. Представление деревьев в прямом порядке степенями с алгоритмами, связывающими это представление с десятичной записью Дьюи и другими свойствами деревьев, были представлены в работе S. Gorn, Proc. Symp. Math. Theory of Automata (Brooklyn: Poly. Inst., 1962), 223-240.

История древовидных структур как математических объектов вместе с библиографией по этой теме приведена в разделе 2.3.4.6.

В то время, когда в 1966 году создавался этот раздел, большинство сведений об информационных структурах было получено благодаря изучению систем обработки списков, игравших очень важную роль в истории. Первой широко использземой системой был язык IPL-V (наследник IPL-III, разработанный в 1959 году). Он представлял собой интерпретирующую систему, в которой программист изучал машино-подобный язык для работы со списками. Примерно в то же время Г. Гелернтером (Н. Gelernter) и его сотрудниками был разработан FLPL (набор подпрограмм на языке FORTRAN для работы со списками, который также обязан своему появлению на свет IPL, но в отличие от него вместо интерпретируемого языка использовал вызовы

подпрограмм). Третья система, LISP, была также создана в 1959 году Дж. Мак-Карти (J. McCarthy)". LISP существенно отличался от своих предшественников: его программы были (и .остаются) математическими функциональными выражениями, скомбинированными с "условными выражениями" (conditional expressions) и конвертированными затем в представление списков. В 60-е годы возникло много систем обработки списков; с исторической точки зрения среди них наиболее известен набор подпрограмм SLIP для реализации списков с двойными связями на языке FORTRAN, созданный Й. Вейзенбаумом (J. Weizenbaum).

В статье Боброу (Bobrow) и Рафаэля (Raphael), САСМ 7 (1964), 231-240, можно прочесть краткое введение в IPL-V, LISP и SLIP.. В ней же дается сравнение этих систем. Превосходное введение в LISP было опубликовано Ф. М. Вудвордом (Р. М. Woodward) и Д. П. Дженкинсом (D. Р. Jenkins), Сотр. 3. 4 (1961), 47-53. Кроме того, можно ознакомиться с авторским описанием их собственных систем (эти статьи представляют значительную историческую ценность): "An introduction to IPL-V" A. Ньювелла (A. Newell) и Ф. M. Тонге (F. M. Tonge), CACM 3 (1960), 205-211; "A FORTRAN-compiled List Processing Language" Г. Гелернтера (H. Gelern-ter), Д. P. Хансена (J. R. Hansen) и К. Л. Гербериха (С. L. Gerberich), ЗАСМ 7 (1960), 87-101; "Recursive functions of symbolic expressions and their computation by machine, I" Джона Мак-Карти (John McCarthy), CACM 3 (1960), 184-195; "Symmetric List Processor" Й. Вейзенбаума (J. Weizenbaum), CACM 6 (1963), 524-544. Статья Вейзенбаума включает полное описание всех использованных в SLIP алгоритмов. Из всех перечисленных ранних систем только LISP имел все необходимые составляющие для того, чтобы пережить десятилетия дальнейшего прогресса. Мак-Карти описал раннюю историю LISP в History of Programming Languages (Academic Press, 1981), 173-197.

В 60-e годы появился ряд систем для работы со строками, в которых первостепенное значение приобрели операции со строками переменной длины, содержащими алфавитную информацию - поиск вхождения в строку определенной подстроки, ее замещение другой и т. п. Наиболее важными из них с исторической точки зрения были COMIT [V. Н. Yngve, САСМ 6 (1963), 83-84] и SNOBOL [D. J. Farber, R. Е. Griswold, and I. P. Polonsky, ЗАСМ 11 (1964), 21-30]. Хотя системы работы со строками широко использовались и состоят, в первую очередь, из алгоритмов, подобных рассмотренным в этой главе, они сыграли сравнительно малую роль в истории развития технологий представления информационных структур. Детали внутренней реализации были скрыты от пользователей этих систем. Обзор ранних систем работы со строками можно найти в S. Е. Madnick, САСМ 10 (1967), 420-424.

В системах обработки списков IPL-V и FLPL не использовались ни сборка мусора, ни технология счетчиков ссылок при работе с разделяемыми списками. Вместо этого каждый список "принадлежал" одному списку и "заимствовался" всеми другими списками, которые на него ссылались. Список удалялся, когда его владелец позволял это. Следовательно, программист должен был сам гарантировать, что при удалении список никому не был одолжен. Технология счетчика ссылок для списков введена Д. Э. Коллинзом (G. Е. Collins), САСМ 3 (1960), 655-657, и позже проанализирована в САСМ 9 (1966), 578-588. Сборка мусора впервые была описана в статье Мак-Карти в 1960 году [см. также примечания Вейзенбаума в САСМ 7 (1964), 38, и статью Коэна (Cohen) и Триллинга (Trilling), BIT 7 (1967), 22-30].

Рост понимания важности работы со связями естественным образом привел к их включению в алгебраические языки программирования, созданные после 1965 года. Новые языки позволяли программистам выбрать подходящую форму представления данных, не прибегая к ассемблеру и избегая накладных расходов универсальных структур списков. Некоторыми из фундаментальных шагов на этом пути были работы N. Wirth and Н. Weber, САСМ 9 (1966), 13-23, 25, 89-99; Н. W. Lawson, САСМ 10 (1967), 358-367; С. А. R. Ноаге, Symbol Manipulation Languages and Techniques, ed. by D. G. Bobrow (Amsterdam: North-Holland, 1968), 262-284; O.-J. Dahl and K. Nygaard, CACM 9 (1966), 671-678; A. van Wijngaarden, B. J. Mailloux, J. E. L. Peck, and C. H. A. Koster, Numerische Math. 14 (1969), 79-218; Dennis JVI. Ritchie, History of Programming Languages -и (ACM Press, 1996), 671-698.

Алгоритмы динамического выделения памяти появились за несколько лет до их описания в печати. Очень интересное обсуждение было подготовлено В. Т. Комфортом (W. Т. Comfort) в 1961 году и опубликовано в САСМ 7 (1964), 357-362. Метод граничного дескриптора, описанный в разделе 2.5, был разработан автором книги в 1962 году для использования в операционной системе компьютера Burroughs В5000. Система двойников впервые использовалась Г. Марковицем (Н. Markowitz) в системе программирования SIMSCRIPT в 1963 году, а также была независимо разработана и опубликована К. Ноултоном (К. Knowlton), САСМ 8 (1965), 623-625 [см. также САСМ 9 (1966), 616-625]. Дополнительную информацию о динамическом выделении памяти можно найти в статьях Iliffe and Jodeit, Сотр. J. 5 (1962), 200-209; Bailey, Barnett, and Burleson, CACM 7 (1964), 339-346; A. T. Berztiss, CACM 8 (1965), 512-513; D. T. Ross, CACM 10 (1967), 481-492.

Общее обсуждение информационных структур и их связи с программированием было подготовлено Мэри дИмперио (Магу dImperio) - "Data Structures and their Representation in Storage", Annual Review in Automatic Programming 5 (Oxford: Pergamon Press, 1969). Ее статья служит серьезным путеводителем по истории предмета, поскольку включает детальный анализ структур, использованных в двенадцати системах обработки списков и работы со строками. Дополнительные исторические детали можно найти в трудах двух симпозиумов, САСМ 3 (1960), 183-234, и САСМ 9 (1966), 567-643 (отдельные статьи из этих трудов упоминались ранее).

Великолепно аннотированная библиография ранних работ по манипуляции символами и математическими формулами, имеющая множество связей с материалом этой главы, была составлена Д. Э. Саммет (J. Е. Sammet); см. Computing Reviews 7 (July-August, 1966), В1-В31.

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