Хювенен - Мир лиспа. Том 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

УКАЗАТЕЛЬ ИМЕН И СОКРАЩЕНИЙ

...


Архивариус Бизнес-планы Типовые серии Норм. документы Литература Технол. карты Программы Серии в DWG, XLS