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

Категориальная абстрактная машина. Конспект лекций: введение в вычисления

ISBN 5-89158-102-7
2002. 96 c. В721
ББК 32.97
УДК 004
Мягкий переплет.
Цена 1
100
Цена 2
290
Цены действительны до
28.03.2024
Цена 1 с учетом НДС
Цена 2 с учетом почтовых расходов по РФ и НДС.
ПОЛОЖИТЬ В КОРЗИНУ
ПОЛОЖИТЬ В КОРЗИНУ
Вольфенгаген В.Э.
Изд. 2-е.

Работа содержит изложение базовых моделей вычислений, применяемых в компьютерных науках. Изложены основы лямбда-исчисления и комбинаторные исчисления. Основное внимание уделено подробному рассмотрению техники вычисления значения конструкций языков программирования, включая компилирование кода, его оптимизацию и исполнение на примере категориальной абстрактной машины. Изложение построено на примерах возрастающей сложности. Книга может быть рекомендована студентам и аспирантам, изучающим основы компьютерных наук, теорию и языки программирования, информационные технологии, информатику и дискретную математику.


This book contains the basics for computation models in Computer Science. The core topics both of lambda-calculus and combinatory calculi are covered.

The main goals are to provide formal tools to assess meaning of programming constructs in both a language-independent and a machine independent way including the code compiling and generation, its optimization and runtime considerations. This is done using the categorical abstract machine - relatively new direction in studying and understanding the programs and computations. The material is equipped with serial examples of growing up complexity.

This book is recommended to the undergraduate and postgraduate students in Computer Science, Programming Languages, Information Technologies, and Discrete Mathematics.


См. также

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


Оглавление

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

Предисловие

Введение

1. Категориальная теория вычислений 11

  • 1.1 Передача параметров 11
  • 1.2 Формальное описание семантики выражений 13
    Упражнения
  • 1.3 Формализм Дебрейна 20
    Упражнения
  • 1.4 Вычисления с помощью категориальных комбинаторов 23
    • Вычисления по Дебрейну 24
    • Вычисления с помощью семантических неравенств 25
    • Вычисления с категориальными комбинаторами 27
    • Большой пример 29
Упражнения 31
  • 1.5 Бета-редукция и категориальные комбинаторы 32
    Упражнения 36
  • 1.6 Категориальная комбинаторная логика 37
    Упражнения 38

    2 Абстрактная машина 39

    • 2.1 Значение выражений 39
    • 2.2 Сравнение различных способов вычисления 47
    • 2.3 Построение абстрактной машины 48
    • 2.4 Вычисления в категориальной абстрактной машине 48
    • 2.5 Статические комбинаторы 49
    • 2.6 Работа КАМ 50
    • 2.7 Замена символов д.з.к. инструкциями КАМ 54
    • 2.8 Цикл работы КАМ 54
    Примеры и упражнения 56

    3 Оптимизация вычислений 65

    • 3.1 Вычисление на КАМ бета-свертывания 65
    • 3.2 Обоснование вычисления бета-свертывания 66
    • 3.3 Экономия в кодировании двухместных операторов 67

    Расширение и реализация КАМ 69

    • 4.1 Неподвижная точка и конструкция ветвления 69
    • 4.2 Вычисления с рекурсивной модификацией среды 73
    • 4.3 Организация цикла mkloop 80
    • 4.4 Рекурсия и ленивые вычисления 83

    5 Категория как чистая теория объектов 89

    Литература 93

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