ЮрИнфоР >>> Библиотека ЮрИнфоР >>> Компьютерные науки и информационные технологии >>>

Комбинаторная логика в программировании: Вычисления с объектами в примерах и задачах

ISBN 978-5-91329-013-7 2008. 384 c. ББК 22.176я73 УДК 519.711.4(076.2) Мягкий переплет. Цена 1 198 Цена 2 447 Цены действительны до 31.03.2023 Цена 1 с учетом НДС Цена 2 с учетом почтовых расходов по РФ и НДС. ПОЛОЖИТЬ В КОРЗИНУ × Выберите способ доставки: самовывоз по почте Адрес самовывоза: г. Москва, ул. Малая Пироговская, дом 5, офис 33. При оформлении заказа необходимо будет указать почтовый адрес для отправки посылки с заказом. Отмена Положить в корзину

Аннотация Как приобрести См. также Содержание ПОЛОЖИТЬ В КОРЗИНУ × Выберите способ доставки: самовывоз по почте Адрес самовывоза: г. Москва, ул. Малая Пироговская, дом 5, офис 33. При оформлении заказа необходимо будет указать почтовый адрес для отправки посылки с заказом. Отмена Положить в корзину

.

Изложен основной круг задач, сводимых к исчислению объектов - "от простого к сложному". Конкретный вариант исчисления выбирается в зависимости от решаемых задач. В ходе последовательного решения задач читатель овладевает основными методами и средствами комбинаторной логики и ламбда-исчисления. Все задачи снабжены подробными и элементарными решениями. Для студентов старших курсов и аспирантов, изучающих математические основы объектно-ориентированных вычислений, начинающих и профессионально работающих над продвинутыми проектами программистов. Может быть использована в курсах дискретной математики, информатики, теории программирования. Предварительной математической подготовки не требуется. Материал частично или полностью может быть использован для самостоятельного изучения как книга "для первого чтения".

---

См. также

Дополнительные учебно-методические материалы и компьютерные обучающие средства (практикумы, активные книги)

---

Содержание

Предисловие редактора серии

Special Preface

Круг вопросов

Предисловие к третьему изданию

Предисловие ко второму изданию

Предисловие к первому изданию

Введение

Комбинаторы: объекты, помогающие понять строение компьютинга 39

• Компьютинг и его проблематика 40
• Аппликативная среда: взаимодействие объектов 42
• Внутренняя структура операций: элементарна ли операция композиции? 53
• Условные конструкции 60
• Бесконечные конструкции 63
• "Разрешающая способность" вычислительной системы? 66

Предварительные сведения 67

• Круг основных идей 69
• Структура раздела 70
• Состояние исследований 71
• Типовая задача 76
• Варианты задания 78
• Рекомендуемый порядок выполнения задания 84

Синтез нового объекта 85

• Принцип комбинаторной полноты 86
  • Комбинаторная характеристика 86
  • Системы концептов 87
  • Комбинаторная полнота 87
  • Элементарная комбинаторная логика 89
• Синтез основных комбинаторов: задачи 91
• Исторические замечания 102
• На переднем крае исследований 103
  • Редукция и экспансия объектов 104
  • Синтез объекта с заданной характеристикой 106
  • Бесконечные конструкции 106

Неподвижная точка 109

• Теоретические сведения 109
  • Абстракция 110
  • Мультиабстракция 111
  • Локальная рекурсия 111
• Основные задачи 112
• Упражнения 117

Экстенсиональность 119

• Теоретические сведения 119
• Задачи 121
• Упражнения 123

Нумералы 125

• Числа и нумералы 125
• Комбинаторная арифметика 126
• Задачи 132
• Упражнения 135

Комбинаторы с типами 137

• Представление о типе 137
  • Комбинаторные термы 140
  • Ламбда-термы 141
• Задачи 141

Базис I, К, S 159

• Теоретические сведения 160
• Задачи 160
• Упражнения 161

Базис I, В, С, S 163

• Теоретические сведения 163
• Свойство базисности 164
• Элементарные примеры 166
• Упражнения 167

Применения неподвижной точки Y 169

• Теорема о неподвижной точке 169
• Элементы рекурсивных вычислений 170
• Использование комбинатора Y 171
• Вычисление функций 173
• Упражнения 177

Функция list1 179

• Теоретические сведения 179
• Задачи 180
• Функтор-как-объект 183
• Упражнения 184

Изоморфизм д.з.к. и ABC 185

• Теоретические сведения 185
• Задачи 187

Каррирование 189

• Теоретические сведения 189
  • Операторы и функции 189
  • Свертывание 190
  • Соответствие операторов и функций 190
• Задачи 191
• Упражнения 193

Оболочка Каруби 195

• Теоретические сведения 195
• Задачи 196
• Упражнения 200

Произведение и проекции 203

• Теоретические сведения 203
• Задача 204
• Произведение и декартово замкнутая категория 208

Погружение Lisp в ABC 209

• Теоретические сведения 209
• Основная задача 210
• Заключительные замечания 216

Суперкомбинаторы 217

• Теоретические сведения 217
  • Понятие о суперкомбинаторе 218
  • Процесс компиляции 220
  • Приведение к суперкомбинаторам 221
  • Устранение избыточных параметров 223
  • Упорядочивание параметров 224
  • Ламбда-подъем при рекурсии 228
  • Работа алгоритма ламбда-подъема 230
  • Другие способы ламбда-подъема 234
  • Полная ленивость 236
  • Максимально свободные выражения 238
  • Ламбда-подъем с использованием МСВ 240
  • Полностью ленивый ламбда-подъем с letrec 241
  • Комплексный пример 243
• Задача 246
• Ответы к упражнениям 248

Ленивая реализация 257

• Задачи 257
• Упражнения 260

Перестановка параметров 261

• Задача 261
• Упражнения 265
• Вопросы для самопроверки 266

Непосредственные вычисления 267

• Задача 267
• Упражнения 269
• Вопросы для самопроверки 270

Код де Брейна 271

• Задачи 271
• Упражнения 276

Абстрактная машина: КАМ 277

• Теоретические сведения 277
  • Структура КАМ 278
  • Инструкции 280
• Задачи 284
• Упражнения 284

Оптимизация КАМ-вычислений 287

• Задача 287
• Упражнения 296
• Вопросы для самопроверки 297

Переменные объекты 299

• Модели 299
  • Аппликативная структура 300
  • Модели с типами 304
  • Частичные элементы 311
  • Модели объектов данных 315
• Основная задача 319
  • Элементарные типы 320
  • Типизация переменных объектов 321
  • Вычислительные модели 323
  • Индексированные объекты 325
• Интерпретация среды вычислений 333
• "Плохая" задача передачи знаний: теории концепцтов для ее решения 333

Библиография 337

Предметный указатель 356

Глоссарий 361

Практикум 377

Диссертации 381