Программы как математические объекты

Фундаментальный подход в компьютерных науках предполагает понимание программ как математических объектов, о которых можно рассуждать с математической строгостью. Математически программа больше, чем ее представление на языке программирования, например таком как CFPascal. Аналогичная ситуация с числами. Число тринадцать – математический объект, который имеет свойство быть тринадцатью вне зависимости от того, как это число будет представлено в письменной или устной форме: словом «двенадцать», набором цифр «12», или в римском варианте «XII» или «дюжина». Все эти представления являются строками символов. Разница между числом и его устным или письменным обозначением в том, что число имеет определенные математические свойства, не зависимые от того, как мы называем или обозначаем это число. Двенадцать – это на два больше, чем десять, четное, кратное трем, четырем, шести и т.д.

Выделение концепции натуральных чисел в виде набора аксиом было большим достижением в математике, сделанным итальянским математиком Джузеппе Пеано, который жил на рубеже XIX и XX веков.

Пеано ввел два понятие целого (натурального) числа, понятие следования одного числа непосредственно за другим в натуральном ряде и понятие начального члена натурального ряда (за который можно принять 0 или 1). Эти понятия связаны между собой пятью аксиомами, которые можно рассматривать как аксиоматическое определение указанных основных понятий.

1. 0 есть натуральное число;

2. следующее за натуральным числом есть натуральное число;

3. 0 не следует ни за каким натуральным числом;

4. если натуральное число а следует за натуральным числом b и за натуральным числом с, то b и с тождественны;

5. если какое-либо предложение доказано для 0 и если из допущения, что оно верно для натурального числа n, вытекает, что оно верно для следующего за п натурального числа, то это предложение верно для всех натуральных чисел.

Последняя аксиома - аксиома полной индукции - даёт возможность доказывать общие свойства натуральных чисел.

Обычные названия чисел могут быть интерпретированы как сокращения для неуклюжих названий, которые встречаются в работе Пеано. Пусть следующий для целого числа n будет обозначаться s(n). Тогда сокращения будут такими:

1 для s(0)

2 для s(1) = s(s(0))

…

10 для s(9) = s(s(8)) = …

…

100 для s(99) = s(s(98)) = …

Математические свойства чисел 0, 1, 2 , …, 10, …, 100,… зависят только от 0 и s, а не от представления их с помощью цифр. Например, 10 > 8, потому что существует выражение

10 = s(s(8)), 5 = 3 + 2, потому что 5 = s(s(3)) (s использовано дважды). Нужно заметить, что представления чисел ни разу не использованы в работе Пеано, за исключением символа 0, который достаточно условно взят как символ начала последовательности.

Большинство людей имеют дело с обычными представлениями чисел, например при сложении, делении и т.д. Понимание чисел как математических объектов, например, через аксиомы Пеано, обычно является областью деятельности тех, кто изучает математику в соответствующих вузах. Но операции, которые мы выполняем над числами, используя их некоторые представления, основаны именно на свойствах чисел. Например, при нахождении квадратного корня из 100 мы используем свойства десятичного представления числа и легко получаем 10, та же самая процедура будет сложнее, если мы будем пользоваться римским представлением чисел, но даст тот же результат, потому что вычисление квадратного корня базируется на свойстве числа, а не на его представлении.

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

[будущие инженеры должны это знать, уже сейчас некоторые теряют интеллектуальный контроль на простых программах, пример с IFSort3б или впадают в ступор неверно поставив точку с запятой]

Свойство программ, которое не зависит от их представления, синтаксиса – управление поведением компьютером. Программа, которая сортирует строку, конечно имеет представление, выраженное в соответствии с синтаксическими правилами, но суть того, что она делает – сортировка. Может существовать множество программ на CF Pascal, которые сортируют строку, подобно тому как число 12 может быть получено из 11+1, 10+2, 7+5 и т.д. Аналогичные программ могут быть написаны на других языках программирования, таких как BASIC или С. Каждый язык программирования – всего лишь средство выражения способа решения задачи аналогично тому, как арабские или римские цифры представляют натуральные числа. Функциональное поведение программы независимо от ее представления на том или ином языке программирования и конкретной формы для выбранного языка.

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

Синтаксис и семантика CF Pascal

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

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

Нотация Бекуса-Наура (BNF) предоставляет нам точный способ описания синтаксиса CF Pascal. Вместе с контекстными правилами, синтаксические правила BNF описывают все возможности для разработки программ на CF Pascal.

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

оно должно показывать нам, что происходит с переменными и файлами, и какими выражениями программы вызваны те или иные изменения. Тут мы сталкиваемся с проблемой тестовых данных: на каких входных данных должно быть описано поведение программы. Идеальный ответ: «на любых», или «на всех». Полное семантическое описание программы должно включать все варианты. Это означает, что с помощью таблицы выполнения такое описание получить невозможно.

Семантическое значение для данной CF Pascal программы будет математическое отношение или функция, упорядоченный набор пар, который определяет соответствие между одним набором данных (INPUT) и другим набором данных (OUTPUT). Значением программы будет трансформация данных, описанная следующим соответствием: данным значениям в INPUT соответствуют значения в OUTPUT полученные при выполнении этой программы на Паскаль-машине.