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

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

ISBN 978-5-91329-013-7
2008. 384 c.
ББК 22.176я73
УДК 519.711.4(076.2)
Мягкий переплет.
Цена 1
440
Цена 2
810
Цены действительны до
30.12.2024
Цена 1 с учетом НДС
Цена 2 с учетом почтовых расходов по РФ и НДС.
ПОЛОЖИТЬ В КОРЗИНУ
ПОЛОЖИТЬ В КОРЗИНУ
Вольфенгаген В.Э.
3-е изд., перераб. и дополн.
Изложен основной круг задач, сводимых к исчислению объектов - "от простого к сложному". Конкретный вариант исчисления выбирается в зависимости от решаемых задач. В ходе последовательного решения задач читатель овладевает основными методами и средствами комбинаторной логики и ламбда-исчисления. Все задачи снабжены подробными и элементарными решениями. Для студентов старших курсов и аспирантов, изучающих математические основы объектно-ориентированных вычислений, начинающих и профессионально работающих над продвинутыми проектами программистов. Может быть использована в курсах дискретной математики, информатики, теории программирования. Предварительной математической подготовки не требуется. Материал частично или полностью может быть использован для самостоятельного изучения как книга "для первого чтения".

См. также

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

Содержание

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

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