Начала программирования

Начала программирования
Автор: Александр Степанов, Пол Мак-Джоунс
Год: 2011
ISBN: 978–5–8459–1708–9
Страниц: 272
Язык: 0
Формат: PDF
Размер: 10 Мб

Download

В настоящей книге применяется дедуктивный подход к программированию, основанный на объединении программ с абстрактными математическими теориями, которые обеспечивают их работу.
Представлены вместе описания этих теорий, алгоритмы, записанные с точки зрения этих теорий, а также теоремы и леммы, описывающие их свойства. Реализация алгоритмов на реальном языке программирования является центральной темой книги.
Эта книга предназначена для тех, кто стремится глубже понять суть программирования, будь то профессиональные программисты или ученые и инженеры, для которых программирование составляет важную часть их профессиональной деятельности. Книга предназначена для чтения от начала и до конца. Читатели смогут достичь понимания материала, только изучая код, доказывая леммы и выполняя упражнения.
“В книге содержатся одни из наиболее замечательных образцов кода, с которыми я когда-либо сталкивался.” – Бьярне Страуструп, разработчик языка C++

+

Вводные определения

Начиная с краткой таксономии идей, мы введем понятия значения, объекта, типа, процедуры и концепции, которые представляют различные категории идей в компьютере. Затем определим центральное понятие книги — регулярность. Для процедур регулярность означает, что процедуры возвращают равные результаты для равных аргументов. Для типов регулярность означает, что типы позволяют воспользоваться оператором проверки на равенство, а также сохраняющим равенство конструированием копии и присваиванием. Регулярность дает нам возможность заменять значения на другие, но равные им значения, для преобразования и оптимизации программ.

1.1. Категории идей: сущность, вид, род

Чтобы объяснить, в чем состоят объекты, типы и другие фундаментальные понятия программирования, полезно дать краткий обзор некоторых категорий идей, которые соответствуют этим понятиям.

Абстрактная сущность — это предмет, который является вечным и неизменным, тогда как конкретная сущность — это предмет, который может обрести свое существование в пространстве и времени или перестать существовать. Атрибут определяет соответствие между конкретной сущностью и абстрактной сущностью — он описывает некоторое свойство, измерение или качество конкретной сущности. Идентичность, одно из примитивных понятий нашего восприятия действительности, определяет одинаковость предмета, изменяющегося в течение времени. Атрибуты конкретной сущности могут изменяться, не затрагивая его идентичность. Моментальный снимок конкретной сущности — это полная коллекция его атрибутов в определенный момент времени. Конкретными сущностями являются не только физические объекты, но также и правовые, финансовые или политические сущности. Синий цвет и число 13 — это примеры абстрактных сущностей. Сократ и Соединенные Штаты Америки — примеры конкретных сущностей. Цвет глаз Сократа и число американских штатов — это примеры атрибутов.

Абстрактный вид описывает общие свойства эквивалентных абстрактных сущностей. Примеры абстрактных видов — натуральное число и цвет. Конкретные виды описывают множество атрибутов почти полностью эквивалентных конкретных сущностей. Примеры конкретных видов — человек и штат США.

Функция — это правило, которое связывает одну или несколько абстрактных сущностей, называемых аргументами, из соответствующего вида с абстрактной сущностью, называемой результатом, из другого вида. Примерами функций являются функция определения преемника, которая связывает каждое натуральное число с непосредственно следующим за ним, и функция,
которая связывает с двумя цветами результат их смешивания.

Абстрактный род описывает различные абстрактные виды, которые являются подобными в некотором отношении. Примеры абстрактных родов — число и бинарный оператор. Конкретный род описывает различные конкретные виды, подобные в некотором отношении. Примеры конкретных родов — млекопитающее и двуногое.

Сущность принадлежит к одному и только одному виду, который регламентирует правила для ее построения или существования. Сущность может принадлежать к нескольким родам, каждый из которых описывает определенные свойства.

Ниже мы покажем, что объекты и значения представляют сущности, типы представляют виды, а концепции представляют роды.

1.2. Значения

Если мы не знаем интерпретацию, то единственными предметами, которые мы видим в компьютере, являются нули и единицы. Элемент данных представляет собой конечную последовательность нулей и единиц.

Тип значения определяет соответствие между видом (абстрактным или конкретным) и множеством элементов данных. Элемент данных, соответствующий определенной сущности, называется представлением сущности; сущность называется интерпретацией элемента данных. Мы называем элемент данных вместе с его интерпретацией значением. Примерами значений являются целые числа, представленные в формате 32-битовых двоичных чисел в дополнительном коде с обратным порядком байтов, и рациональные числа, представленные как конкатенация двух 32-битовых последовательностей, интерпретируемых как целочисленный числитель и знаменатель, которые представлены как значения двоичных чисел в дополнительном коде с обратным
порядком байтов.