Хювёнен Э., Сеппянен И. - Мир Лиспа (в 2-х томах) [1990, DjVu, RUS]

Предисловие редактора перевода 5
ВВЕДЕНИЕ 11
Скачок в развитии вычислительной техники 11
Исследовательские программы искусственного интеллекта 12
Национальные программы по исследованию языков 13
Появление Лиспа в Финляндии 13
Лисп - основа искусственного интеллекта 14
Учебник Лиспа на финском языке 14
Язык Лисп и функциональное программирование 15
Методы и системы программирования 16
На кого рассчитана книга 17
Терминология 17
Иконология 18
От дерева к мысли и от мысли к дереву 19
Благодарности 20
1 ВВЕДЕНИЕ В МИР ЛИСПА 21
1.1 СИМВОЛЬНАЯ ОБРАБОТКА И ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ 22
Искусственный интеллект и технология знаний 23
Исторические предубеждения 23
Символьное или численное вычисление 24
Эвристическое или алгоритмическое решение задачи 25
Искусственный интеллект - сфера исследования многих наук 27
Знание дела и умение как товар 27
Учебники по искусственному интеллекту 28
Упражнения 29
1.2 ПРИМЕНЕНИЯ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА 30
Многообразие форм искусственного интеллекта 30
Обработка естественного языка 31
Экспертные системы 33
Символьные и алгебраические вычисления 35
Доказательства и логическое программирование 36
Программирование игр 37
Моделирование 37
Обработка сигналов и распознавание образов 38
Машинное зрение и обработка изображений 39
Робототехника и автоматизация производства 39
Машинное проектирование 40
Языки и средства программирования искусственного интеллекта ч. 40
Повышение производительности программирования 41
Автоматическое программирование и обучение 41
Литература 42
Упражнения 45
1.3 ЛИСП - ЯЗЫК ПРОГРАММИРОВАНИЯ ИСКУССТВЕННОГО 46 ИНТЕЛЛЕКТА
Символьная обработка 47
Лисп опередил свое время 48
Одинаковая форма данных и программы 49
Хранение данных, не зависящее от места 50
Автоматическое и динамическое управление памятью 51
Функциональный образ мышления 51
Возможность различных методов программирования 52
Пошаговое программирование 52
Интерпретирующий или компилирующий режимы выполнения 53
Лисп - бестиповый язык программирования 53
Единый системный и прикладной язык программирования 54
Интегрированная среда программирования 55
Широко распространенные заблуждения и предрассудки 56
Простой и эффективный язык 57
Учебная литература по Лиспу 58
Упражнения 59
2 ОСНОВЫ ЯЗЫКА ЛИСП 60
2.1 СИМВОЛЫ И СПИСКИ 61
Символы используются для представления других объектов 61
Символы в языке Коммон Лисп 62
Числа являются константами 63
Логические значения Т и NIL 64
Константы и переменные 64
Атомы - Символы + Числа 64
Построение списков из атомов и подсписков 65
Пустой список = NIL 65
Список как средство представления знаний 66
Значение способа записи 67
Различная интерпретация списков 67
Упражнения 68
2.2 ПОНЯТИЕ ФУНКЦИИ 69
Функция - отображение между множествами 69
Тип аргументов и функций 70
Определение и вызов функции 71
Единообразная префиксная нотация 71
Аналогия между Лиспом и естественным языком 73
Диалог с интерпретатором Лиспа 73
Иерархия вызовов 74
QUOTE блокирует вычисление выражения 75
Упражнения 77
2.3 БАЗОВЫЕ ФУ1IKI ЩИ 78
Основные функции обработки списков 79 Функция CAR возвращает в качестве значения головную часть списка 80
Функция CDR возвращает в качестве значения хвостовую часть 81 списка
Функция CONS включает новый элемент в начало списка 83
Связь между функциями CAR, CDR и CONS 84
Предикат проверяет наличие некоторого свойства 85
Предикат АТОМ проверяет, является ли аргумент атомом 85
EQ проверяет тождественность двух символов 86
EQL сравнивает числа одинаковых типов 88
Предикат * сравнивает числа различных типов 88
EQUAL проверяет идентичность записей 89
EQUALP проверяет наиболее общее логическое равенство 90
Другие примитивы 90
NULL проверяет на пустой список 91
Вложенные вызовы CAR и CDR можно записывать в сокращенном 91 виде
LIST создаст список из элементов 93
Упражнения 94
2.4 ИМЯ И ЗНАЧЕНИЕ СИМВОЛА 95
Значением константы является сама константа 95
Символ может обозначать произвольное выражение 96
SET вычисляет имя и связывает его 96
SETQ связывает имя, не вычисляя его 97
SETF - обобщенная функция присваивания 98
Побочный эффект псевдофункции 99
Вызов интерпретатора EVAL вычисляет значение значения 100
Основной цикл: READ-EVAL-PRINT 102
Упражнения 103
2.5 ОПРЕДЕЛЕНИЕ ФУHKI *ИЙ 104
Лямбда-выражение изображает параметризованные вычисления 104
Лямбда-вызов соответствует вызову функции 106
Вычисление лямбда-вызова, или лямбда-преобразование 106
Объединение лямбда-вызовов 107
Лямбда-выражение - функция без имени 108
DEFUN даст имя описанию функции 108
SYMBOL-FUNCTION выдаст определение функции 110
Задание параметров в лямбда-списке 111
Изображение функций в справочных руководствах 114
Функции вычисляют все аргументы 115
Многозначные функции 115
Определение функции в различных диалектах Лиспа 115
При вычислении NLAMBDA аргументы не вычисляются 117
Упражнения 117
2.6 ПЕРЕДАЧА ПАРАМЕТРОВ И ОБЛАСТЬ ИХ ДЕЙСТВИЯ 119
В Лиспе используется передача параметров по значению 119
Статические переменные локальны 120
Свободные переменные меняют свое значение 121
Динамическая и статическая область действия 121
Одно имя может обозначать разные переменные 123
Упражнения 125
2.7 ВЫЧИСЛЕНИЕ В ЛИСПЕ 127
Программа состоит из форм и функций 127
Управляющие структуры Лиспа являются формами 128
LET создает локальную связь 129
Последовательные вычисления: PROG 1, PROG2 и PROGN 131
Разветвление вычислений: условное предложение COND 132
Другие условные предложения: IF, WHEN, UNLESS и CASE 136
Циклические вычисления: предложение DO 137
Предложения PROG, GO и RETURN 139
Другие циклические структуры 142
Повторение через итерацию или рекурсию 142 Формы динамического прекращения вычислений: CATCH и THROW 145
Упражнения 146
2.8 ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ 148
Лисповская память состоит из списочных ячеек 149
Значение представляется указателем 149
CAR и CDR выбирают поле указателя 151
CONS создаст ячейку и возвращает на нес указатель 151
У списков могут быть общие части 152
Логическое и физическое равенство не одно и то же 154
Точечная пара соответствует списочной ячейке 155
Варианты точечной и списочной записей 157
Управление памятью и сборка мусора 159
Вычисления, изменяющие и не изменяющие структуру 160
RPLACA и RPLACD изменяют содержимое полей 161
Изменение структуры может ускорить вычисления 163
Упражнения 166
2.9 СВОЙСТВА СИМВОЛА 168
У символа могут быть свойства 168
У свойств есть имя и значение 16Я
Системные и определяемые свойства 169
Чтение свойства 169
Присваивание свойства 170
Удаление свойства 171
Свойства глобальны 171
Упражнения 172
2.10 ВВОД И ВЫВОД 174 Ввод и вывод входят в диалог 174 READ читает и возвращает выражение 175 Программа ввода выделяет формы 176 Макросы чтения изменяют синтаксис Лиспа 177 Символы хранятся в списке объектов 179 Пакеты или пространства имен 180 PRINT переводит строку, выводит значение и пробел 180 PRIN1 и PRINC выводят без перевода строки 182 TERPRI переводит строку 183 FORMAT выводит в соответствии с образцом 184 Использование файлов 187 LOAD загружает определения 190 Упражнения 191
3 ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ 193
3.1 ОСНОВЫ РЕКУРСИИ 194
Лисп - это язык функционального программирования 194
Процедурное и функциональное программирование 195
Рекурсивный - значит использующий самого себя 196
Рекурсия всегда содержит терминальную ветвь 197
Рекурсия может проявляться во многих формах 198
Списки строятся рекурсивно 200
Лисп основан на рекурсивном подходе 201
Теория рекурсивных функций 201
Литература 204
3.2 ПРОСТАЯ РЕКУРСИЯ 205
Простая рекурсия соответствует циклу 205
MEMBER проверяет, принадлежит ли элемент списку 208
Каждый шаг рекурсии упрощает задачу 209 Порядок следования ветвей в условном предложении существенней 211
Ошибка в условиях может привести к бесконечным вычислениям 213
APPEND объединяет два списка 214
REMOVE удаляет элемент из списка 216
SUBSTITUTE заменяет все вхождения элемента 217
REVERSE обращает список 218
Использование вспомогательных параметров 220
Упражнения 221
3.3 ДРУГИЕ ФОРМЫ РЕКУРСИИ 224
Параллельное ветвление рекурсии 225
Взаимная рекурсия 228
Программирование вложенных циклов 229
Рекурсия более высокого порядка 232
Литература 235
Упражнения 235
3.4 ФУНКЦИИ БОЛЕЕ ВЫСОКОГО ПОРЯДКА 239
Функционал имеет функциональный аргумент 239
Функциональное значение функции 241
Способы композиции функций 242
Функции более высокого порядка 243
Литература 244
3.5 ПРИМЕНЯЮЩИЕ ФУНКЦИОНАЛЫ 245
APPLY применяет функцию к списку аргументов 246
FUNCALL вызывает функцию с аргументами 246
Упражнения 248
3.6 ОТОБРАЖАЮЩИЕ ФУНКЦИОНАЛЫ 249
Отображающие функции повторяют применение функции 249
MAPCAR повторяет вычисление функции на элементах списка 250
MAPLIST повторяет вычисление на хвостовых частях списка 252
MAPCAN и MAPCON объединяют результаты 252
МАРС и MAPL теряют результаты 254
Композиция функционалов 255
Итоговая таблица отображающих функций 256
Упражнения 257
3.7 ЗАМЫКАНИЯ 259
FUNCTION блокирует вычисление функции 259
Замыкание - это функция и контекст ее определения 260
Связи свободных переменных замыкаются. 261
Замыкания позволяют осуществлять частичное вычисление Г 263
Генератор порождает последовательные значения 264
Контекст вычисления функционального аргумента 265
Литература 269
Упражнения 269
3.8 АБСТРАКТНЫЙ ПОДХОД 270
Обобщение функций, имеющих одинаковый вид 271
Параметризованное определение функций 275
Рекурсивные функции с функциональным значением 279
Автоаппликация и авторепликация 280
Порядок и тип функций 283
Проблемы абстрактного подхода 285
Литература 286
Упражнения 287
3.9 МАКРОСЫ 288
Макрос строит выражение и вычисляет его значение 288
Макрос не вычисляет аргументы 290
Макрос вычисляется дважды 290
Контекст вычисления макроса 291
Пример отличия макроса от функции 292
Рекурсивные макросы и продолжающиеся вычисления 294
Тестирование макросов 295
Лямбда-список и ключевые слова макроса 296
Обратная блокировка разрешает промежуточные вычисления 298
Образец удобно использовать для определения макросов 300
Макросы с побочным эффектом 301
Определение новых синтаксических форм 304
Определение типов данных с помощью макросов 305
Литература 306
Упражнения 307
4 ТИПЫ ДАННЫХ 308
4.1 ПОНЯТИЯ 309
Явное и неявное определение 309
Абстракция данных 310
Составные типы и процедуры доступа 312
В Лиспе тип связан со значением, а не с именем 312
Проверка и преобразование типов 314
Иерархия типов 316
Определение новых типов 316
4.2 ЧИСЛА 319
Лисп умеет работать с числами 319
Целые числа 323
Дробные числа 323
Числа с плавающей запятой 324
Комплексные числа 325
4.3 СИМВОЛЫ 326
Системные свойства символа 326
Специальные знаки в символах 327
Обращение с внешним видом символа 328
GENTEMP создает новый символ 330
4.4 СПИСКИ 331
Ассоциативный список связывает данные с ключами 332
PAFRLIS строит список пар 332
ASSOC ищет пару, соответствующую ключу 333
ACONS добавляет новую пару в начало списка 334
PUTASSOC изменяет a-список 335
4.5 СТРОКИ 337
Знаки и строки 337
Преобразования строк 338
Работа со строками 339
Наследуемые функции 340
4.6 ПОСЛЕДОВАТЕЛЬНОСТИ 341
Последовательности являются списками или векторами 341
Основные действия с последовательностями 342
Мощные функционалы 344
Упорядочивание последовательности 347
4.7 МАССИВЫ 349
Типы массивов 350
Работа с массивами 350
Хэш-массив ассоциирует данные 351
Хэш-массивы обеспечивают быстродействие 351
4.8 СТРУКТУРЫ 353
Структуры представляют собой логическое целое 353
Определение структурного типа и создание структуры 354
Функции создания, доступа и присваивания 354
Действия не зависят от способа реализации 356
5 РЕШЕНИЯ 358
ПРИЛОЖЕНИЕ 1. СВОДКА КОММОН ЛИСПА 384
ПРИЛОЖЕНИЕ 2. УКАЗАТЕЛЬ СИМВОЛОВ КОММОН ЛИСПА 417
ПРИЛОЖЕНИЕ 3. УКАЗАТЕЛЬ ИМЕН И СОКРАЩЕНИЙ 431
ПРИЛОЖЕНИЕ 4. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 434

ВВЕДЕНИЕ 5
Скачок в развитии вычислительной техники 5
Лисп - основа искусственного интеллекта 6
Учебник Лиспа на финском языке 6
Язык Лисп и функциональное программирование 6
Методы программирования 7
Среда программирования 9
Примеры программ 9
Развитие Лисп-культуры и Лисп-систем 10
На кого расчитана книга 10
Терминология 10
Иконология 11
Благодарности 13
1 ВВЕДЕНИЕ В МЕТОДЫ И СИСТЕМЫ ПРОГРАММИРОВАНИЯ 14 Основные типы знаний 15 Методы представления знаний 16 Процедурные и декларативные знания 18 Способы решения проблем 20 Лисп предлагает различные модели 21 Методы и стиль программирования 21 Парадигмы программирования 22 Литература 24
2 МЕТОДЫ ПРОГРАММИРОВАНИЯ 25
2.1 ОПЕРАТОРНОЕ ПРОГРАММИРОВАНИЕ 26
Функциональное программирование 26
Операторное и процедурное программирование 27
Рекурсия или итерация 28
Рекурсивное операторное программирование 31
Фразовое программирование 35
Макропрограммирование 37
Литература 38
2.2 ПРОГРАММИРОВАНИЕ, УПРАВЛЯЕМОЕ ДАННЫМИ 40
Принцип программирования, управляемого данными 40
Универсальное программирование 41
Дифференцирование выражений 42
Язык представления электрических схем 47
Другие методы программирования, управляемого данными 51
Программирование, управляемое событиями 52
Литература 53
2.3 СОПОСТАВЛЕНИЕ С ОБРАЗЦОМ 54
Сопоставление с образцом и распознавание образов 54
распознавание списочных образов 55
Условия сопоставимости 55
Использование переменных в образце 58
Сопоставление с переменной образца 61
Предикатный образец ограничивает сопоставимость 62
Компьютерный психиатр ELIZA 63
Распознавание структур 66
Литература 67
2.4 ПРОДУКЦИОННОЕ ПРОГРАММИРОВАНИЕ 69
Продукция = условие + следствие 69
Интерпретатор продукций применяет продукции 70
Полный перебор 71
Аннулирование выбора 72
Направление поиска 72
Порядок перебора альтернатив 73
Программирование методов поиска 74
Поиск в глубину, в ширину и по наилучшему варианту 77
Применения продукционного программирования 79
Литература 80
2.5 ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 82
Декларативная программа не содержит алгоритма 83
Процедурная семантика 83
Отношение является обобщением функции 84
Унификация структур 85
Алгоритм унификации 87
Логика хорновских предложений 89
Логическая интерпретация хорновских предложений 90
Логическое определение отношений 91
Множество предложений трактуется как программа 93
Метод резолюций 94
Алгоритм доказательства 96
Реализация интерпретатора 97
Пролог использует поиск в глубину 100
Развитие логического программирования 101
Литература 103
2.6 ОБЪЕКТНОЕ ПРОГРАММИРОВАНИЕ 105
Объектное мышление и объектное программирование 106
Объект, класс объектов и метакласс 107
Объект содержит данные и действия 107
Свойства и состояние объекта 108
Действия или методы объекта 108
Сообщения управляют вычислением 109
Подкласс и надкласс 111
Естественный класс и качественный класс 111
Иерархия классов и механизм наследования 112
Порядок наследования в иерархии классов 113
Композиция методов в вычислениях 115
Базовые классы и метаклассы системы 117
Пример системы - Flavors 117
DEFFLAVOR определяет класс 117
MAKE-INSTANCE создает новый объект 118
DEFMETHOD определяет метод 119
SEND посылает сообщение 120
Объекты моделируют мир проблемы 122
Применимость объектного программирования 122
Развитие объектного мышления и программирования 123
Литература 126
2.7 ДОСТОИНСТВА И КАЧЕСТВО ПРОГРАММИРОВАНИЯ 128
Факторы качества и подходы к программированию 129
Разделяй и именуй объекты естественным образом 132
Используй хорошо определенные соединения 133
Переносимость и стандартизация 134
Другие советы 134
Литература 136
3. СРЕДСТВА И СРЕДА ПРОГРАММИРОВАНИЯ 137
3.1 ПЕРВИЧНАЯ СРЕДА КОММОН ЛИСПА 138
Аппаратная среда реализаций языка 138
Составные части среды программирования на Лиспе 139
Интегрированность и прозрачность 141
Редактирование программ: ED 142
Тестирование программ: TRACE и STEP 143
Прерывание вычислений: BREAK и ERROR 145
Трансляция программ: COMPILE 147
Система документирования и справочная система 147
Комментарии 150
Средства определения количественных характеристик вычислений 151
3.2 СРЕДА ИНТЕРЛИСПА 151
Списочный редактор - List Editor 152
Ассистент программиста - Programmer’s Assistant 154
Структурная печать - Prettyprint 155
Прерывания - Break Package 156
Прерывание вычислений и трассировка 157
Работа с файлами - File Package 157
Транслятор - Compiler 158
Анализатор программы - Masterscope 158
Справочная система - Help System 159
Исправление ошибок - Do What I Mean 159
Лисп с фразовой структурой - Conversational Lisp 161
Оконная система - Window System 161
Целостность системы - System Integration 162
Библиотека программ - Lispusers Package 162
Литература 163
3.3 СРЕДА ЗЕТАЛИСПА 164
Объектная система Flavor 165
Макрос итерации Loop 165
Интерфейс пользователя 166
Оконная система 166
Интегрированные средства разработки 167
Экранный редактор Zmacs 168
Инспектор структур Inspector 169
Отладчик программ Debugger 169
У правление файлами 170
Инспектор состояния Реек 170
Zmail и работа в сети 170
Языки и инструменты 170
Литература 171
4 ПРИМЕРЫ ПРОГРАММ 172
4.1 ЛИСП НА ЛИСПЕ 174
Интерпретатор Лиспа на Лиспе 174
Примитивы интерпретатора 175
Универсальная функция EVAL1 176
Основная часть интерпретатора: APPLY1 178
Примеры вычислений 181
Печать результатов - структурная печать 183
Программирование диалога 184
Программирование ввода и вывода 185
Литература 188
4.2 МИКСИМА 189
Миксима - символьный вычислитель 189
Действия и их порядок 190
Чтение выражения с преобразованием в списочную форму 191
Преобразование выражения в форму дерева 192
Представление выражения в форме дерева 194
Порядок обхода дерева 196
Интерпретация и вычисление выражений 197
Упрощение выражений 199
Снятие скобок и вывод 200
Диалог с Миксимой 201
Литература 202
4.3 ЯЗЫК СПЛЕТНИКА 203
Исчезающие народные традиции 204
Язык сплетника и цыганский жаргон 204
Анализ правил и их программирование 205
Выбор места разбиения слова на части 206
Перевод слова и ключа 209
Долгота и созвучие гласных 209
Перевод слов и предложений 212
Расширение до цыганского жаргона 214
Литература 215
4.4 ДАРВИН 217
Структура экспертной системы 218
Представление знаний 218
Машина вывода 219
Факты и правила 219
Правила вывода базы знаний 221
Стратегия обратного вывода 225
Работа системы Дарвин 226
Примеры запросов 230
Расширение системы Дарвин 231
Литература 232
4.5 СОЛНЕЧНАЯ СИСТЕМА 233
Сначала были созданы небо и Земля 234
Окно в космос 234
Солнце, планеты и спутники 235
И все-таки она вертится 236
Вращением спутника управляет демон 237
Создание небесных тел 238
Запуск Солнечной системы 240
Литература 240
5 РАЗВИТИЕ ЯЗЫКА ЛИСП И ЛИСП- СИСТЕМ 242
5.1 ИСТОРИЯ ЛИСПА 243
Отец Лиспа - Джон Маккарти 243
Обработка списков и искусственный интеллект 244
Значение Лиспа 245
Ранние реализации Лиспа 247
Литература 248
5.2 ЛИСП РАСПРОСТРАНЯЕТСЯ ПО СВЕТУ 250
Развитие Лиспа в других странах 250
Лисп в Западной Европе 250
Лисп в Восточной Европе 254
Лисп в далеких странах 256
Лисп в Скандинавии 258
Лисп в Финляндии 260
Литература 265
5.3 ЛИСП-СИСТЕМЫ 272
Маклисп - основной диалект восточного побережья 272
BBN-Lisp, Xerox и Интерлисп 274
Standard Lisp и PSL 277
Franz Lisp 279
NIL - New Implementation of Lisp (новая реализация языка) 280
Диалект Т Йельского университета 280
Зеталисп Лисп-машин 282
Вавилонская башня мира Лиспа 282
Стандарт Коммон Лиспа 284
Производители Лисп-машин приходят к договоренности 287
Литература 288
5.4 ЛИСП-МАШИНЫ 291 Бегство из систем разделения времени 291 Первые изготовители 292 Успехи Лисп-машин 293 Лисп или Пролог? 294 Литература 295 ПРИЛОЖЕНИЕ 1 Указатель функций и символов 297 ПРИЛОЖЕНИЕ 2 Указатель имен и сокращений 301 ПРИЛОЖЕНИЕ 3 Предметный указатель 309