Хювенен - Мир лиспа. Том 1
Э.Хювёнен, И.Сеппянен
МИР ЛИСПА, Т.1: ВВЕДЕНИЕ В ЯЗЫК ЛИСП И ФУПКЦИОПАЛЬНОЕ ПРОГРАММИРОВАНИЕ
Двухтомник финских специалистов, содержащий введение в язык Лисп, методы и системы программирования. Этот язык широко известен и применяется в задачах символьной обработки информации, обработки естественных языков, искусственного интеллекта, экспертных систем, систем логического программирования. Изложение языка и примеры основаны на последней версии, которая станет стандартом языка. В книге приведены конкретные задачи с ответами и решениями. В 1-м томе даны основные понятия языка Лисп и введение в функциональное программирование.
Для программистов разной квалификации, для всех, использующих язык Лисп.
Содержание
Предисловие редактора перевода 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 БАЗОВЫЕ ФУНКЦИИ 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 ОПРЕДЕЛЕНИЕ ФУНКЦИЙ 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
Последовательные вычисления: PR0G1, PR0G2 и PROGN 131
Разветвление вычислений: условное предложение COND 132
Другие условные предложения: IF, WHEN, UNLESS и CASE 136
Циклические вычисления: предложение DO 137
Предложения PROG, GO и RETURN 13 9
Другие циклические структуры 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
У свойств есть имя и значение 169
Системные и определяемые свойства 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 изменяет а-список 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
УКАЗАТЕЛЬ ИМЕН И СОКРАЩЕНИЙ