Что такое программное исчисление.

Часть II. Программное исчисление.

 

Следующий шаг.

 

Часть I была посвящена тому, как писать программы, решая простые задачи с использованием простого языка программирования, CF Pascal. Часть II выводит нас на следующий уровень, предлагая нам осознать обобщенные математические концепции программирования, которым подчиняются все программы. При этом наша цель остается неизменной – изучение программирования методом проб и ошибок, используя подход сходный с обучением слепой печати на клавиатуре. В части I мы рассматривали средства языка, часть II будет знакомить нас с технологиями систематического программирования.

Компактный CFPascal был подходящим выбором для части I, поскольку он позволял нам концентрироваться на программировании, а не на изучении языка программирования. Для части II он также хорошо подходит, потому что он позволит нам решить следующую задачу: рассматривать программы как математические объекты, более сложные, чем просто строки символов. Рассмотренные идеи будут масштабироваться вне зависимости от роста размеров программ, подобно тому, как, обучившись делению трехзначных чисел, мы сможем в дальнейшем делить тридцатизначные.

Понимание программ как математических объектов организовано как программное исчисление, которое ориентировано в основном на семантику программ, а не на синтаксис.

 

Что такое программное исчисление.

Вводный курс в дифференциальное исчисление в математике основывается на концепции гладкой функции, принимающие вещественные (real) значения. Исчисление связано с понятием вычисления двух связанных функций: производной и первообразной (интеграла) для данной функции. Такие вычисления очень значимы в физике и технических дисциплинах, собственно современная физика и производные науки без этих вычислений невозможны. Функции дифференциального исчисления имеют физический смысл, производная – это интенсивность изменения величины, например скорости движения (ускорение), интеграл – площадь подкривой.

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

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

 

В программном исчислении существуют две основные задачи. Первая, для данной программы как синтаксического объекта найти функцию, описывающую ее значения. Вторая, имея функцию, описывающую значение программы, найти программу с таким значением. Вторая задача ведет нас к систематическим методам проектирования и разработки программ, а первая – к систематическим методам верификации правильности программ.

 

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

Математическими основами программного исчисления являются пять дискретных математических структур символьных данных, а именно:

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

 

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

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