Предисловие.................¦......... '
Введение............................. °
Глава 1. Основные понятия и обозначения.............. 10
1.1. Введение........................ 10
, \.'г. Выражения [типа оператор/операнд............ И
1.3. Переменные и лямбда-выражения.............. 16
1.4. Структуры данных................... 18
1.5. Дополнительные формы выражений............ 21
1.6. Примеры....................... 28
1.7. Упрощение выражений................. 32
1.8. Лямбда-преобразование................. 36
1.9. Комбинаторы ..................... 40
1.10. Рекурсивные функции................. 42
1.11. Преобразование к комбинаторам............. 45
Ссылки и библиография................. 47
Глава 2. Структуры программ.................... 48
2.1. Введение........................ 48
2.2. Программы обратной польской записи........... 49
2.3. Значения идентификаторов................ 52
2.4. Вычисление комбинаций................. 54
2.5. Компилятор комбинаций,............... 57
2.6. Блоки и процедуры................... 59
2.7. Вычисление выражений................. 62
2.8. Компиляция выражений................. 66
2.9. Методы повышения эффективности программ........ 72
2.10. Метки и операторы перехода............... 81
2.11. Совмещение, присваивание и копирование......... 86
2.12. Другие методы вычисления выражений.......... 94
Ссылки и библиография................. 97
Глава 3. Структуры данных.................... 98
3.1. Введение ....................... 98
3.2. Основные понятия................... 100
3.3. Некоторые простые структуры.............. 105
3.4. Списки ........................ 107
3.5. Списковые структуры.................. 115
3.6. Деревья и леса. ."..'.'...'............. 117
3.7. Бинарные деревья. '.............. 122
3.8. Комбинации .,.,.,,.,.........., 125
5
. 3.9. Веса деревьев...................... 127
3.10. Последовательности, сопрограммы и потоки........ 128
3.11. Комбинаторные конфигурации.............. 140
Ссылки и библиография................. 147
Глава 4. Грамматический разбор................... 148
4.1. Введение ........................ 148
4.2. Конечные автоматы и регулярные выражения........ 149
4.3. Контекстно-свободные языки............... 155
4.4. Выражения, описывающие языки............. 158
4.5. Нисходящий грамматический разбор............ 161
4.6. Левоугольный восходящий грамматический разбор..... 175
4.7. Правоугольный восходящий грамматический разбор..... 182
Библиография...................... 191
Глава 5. Сортировка ........................ 193
5.1. Введение........................ 193
5.2. Векторы упорядочения................., 195
г 5.3. Деревья двоичного поиска................. 204
5.4. Двоичная вставка.................... 208
:, 5.5. Быстрая сортировка................... 210
5.6. Обмен по основанию системы счисления и память типа drie», 212
;'; 5.7. Вставка дерева и его перестройка.............. 214
5.8. Упорядочение с помощью дерева сортировки......... 221
5.9. Сортировка на лентах................... 225
Ссылки и библиография................. 242
Указатель программ........................ 244
Предметный указатель....................... 247
ПРЕДИСЛОВИЕ
Область системного программирования возникла главным образом как результат труда многих программистов и исследователей, чья творческая энергия привела к созданию практических обслуживающих системных программ. Это было обусловлено бурным развитием вычислительной техники. На ранних стадиях программирование развивалось как вид искусства, где каждый программист создавал собственные программы решения задач с кратким описанием, которыми кроме него самого могли пользоваться лишь его непосредственные коллеги. В 1968 году Ашер Оплер, работая в то время в фирме ИБМ, пришел к выводу, что знания в области программирования следует привести к форме, доступной для всех системных программистов. Исследуя состояние данного вопроса, он убедился, что имеется достаточно оснований для систематизации рассматриваемого материала. По его рекомендации фирма ИБМ решила субсидировать Серию Системного Программирования,1 что дало возможность собирать, систематизировать и освещать в печати принципы и методы, имеющие важное значение для всех пользователей ЭВМ.
Серия задумана как постоянно продолжающийся ряд моно-. графий, отражающих личные взгляды авторов на предмет изложения, которые не всегда совпадают с мнением фирмы ИБМ. Каждая из книг задумана как изложение отдельного курса, но может служить и справочным пособием. Серия состоит из трех уровней: обширный вводный материал в книгах, посвященных основам программирования; более сложный материал в книгах по программному обеспечению; наконец, специальные вопросы в книгах, посвященных науке программирования. Как правило, книги Серии удовлетворяют и начинающих и опытных программистов, а также специалистов по математическому обеспечению вычислительных машин.
Таким образом, книги Серии отражают современное состояние в этой области и могут стать основой для изучения системного программирования.
ВВЕДЕНИЕ
Книга посвящена особому методу программирования, который использует систему обозначений лямбда-исчисления. Применения этого метода иллюстрируются многочисленными примерами. При изложении материала книги основное внимание уделяется тем выражениям — частям языка, которые описывают получаемые с помощью машин конечные результаты, а не программам, обеспечивающим их достижение. Во многих случаях подобный акцент на выражения, а не на технику программирования позволяет упрощать и совершенствовать задачи.
В первой главе вводится используемый в книге язык программирования, представляющий собой такую версию обозначений лямбда-исчисления, которая облегчает практическое программирование. В ней содержится также краткое описание известных подходов к вычислениям с использованием лямбда-функций. Излагаемые подходы к формированию функций представляют интерес для исследования математических и вычислительных проблем, а также целесообразны с точки зрения простоты и удобства написания программ.
Во второй главе излагается несколько способов создания систем программирования, переводящих выражения в программы. При обсуждении механизма вычислений и стыковки программ с блочной структурой в качестве машинной модели используется машина типа SECD. Используемый язык программирования может применяться как модель для точного описания других языков. Для получения наиболее полного соответствия с другими языками в модель вводятся дополнительные свойства и операторы перехода. В результате машинная модель содержит в обобщенной форме также и свойства языков рассматриваемых программ, которые могут быть с успехом использованы при решении практических задач программирования.
Третья глава содержит систематический способ составления программ для создания и анализа древовидных структур из наборов деревьев. Результирующие программы соответствуют структурам данных. В этой главе также описан способ представления 8
структур данных с помощью функций поточной обработки, которые материализуют составляющие части структур лишь при их необходимости. Список древовидных функций может быть преобразован в функции поточной обработки. Этот метод затем применяется для создания программ, образующих потоки комбинаторной конфигурации.
Четвертая глава связана с методами распознавания и грамматического разбора цепочек символов. Контекстно-свободный язык создан в виде блочного описания программы его грамматического разбора. Программы анализа формируются переопределением операций на символьных цепочках, при этом структура программы грамматического анализа соответствует структуре языка.
В пятой главе приведен ряд примеров программ сортировки, . выраженных с помощью рекурсивных функций. Они позволяют простейшим способом составлять программы сортировки, поскольку сортировку всякого массива часто можно выразить через такие же программы для его подмассива.
Книга предназначена для специалистов, работающих в области применения вычислительной техники, и в качестве дополнительного пособия для студентов старших курсов. Она содержит значительную часть материала, соответствующего учебным планам комиссии в области вычислительной техники при Ассоциации вычислительных машин (АСМ) и необходимого при изучении структур данных, языков программирования и конструирования компиляторов. Книгу можно также рассматривать как введение в методы программирования, которое особенно необходимо на начальных этапах создания программ. Большинство программ приведено в виде доступных для понимания примеров, они могут служить исходным рубежом для специалистов, приступающих к сложным задачам программирования по всем изложенным в книге направлениям.
В. Бердж
