Способы обозначения и определения процедур

ПРОГРАММИРОВАНИЕ И

АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ

 

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

 

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

 

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

 

 

Моделирование – задача любой науки. Судьба программиста - создание моделей на предельно точном, формальном, но очень бедном на обозначения языке.

 

Математический язык, используемый для описания реальной области – язык моделирования или язык спецификации.

 

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

 

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

 

Как правильно понимать? – семантика

Для понимания конструкций одного языка мы описываем их смысл в терминах другого языка (языка описания или метаязыка).

 

Для программиста особенно важен случай, когда метаязык существенно беднее описываемого языка (как в случае толкования слов в «толковом словаре»). В этих случаях говорят о трансляции или редукции выражений одного языка на выражения другого языка. Такой перевод с очень богатого языка на очень бедный возможен лишь, как постепенный, последовательный процесс.

 

 

 

Основные понятия процедурного программирования.

Области и процедуры

 

При описании объектов и процессов мы обычно выделяем статику и динамику.

 

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

 

Каждое состояние подразумевает некоторое соответствие между совокупностью имен (характеристик) и множеством их возможных значений. С точки зрения математики состояние – это функция, областью определения которой служит множество имен атрибутов, а множеством значений – множество возможных значений. Что может служить множеством имен, а что множеством значений? – все, что угодно.

 

Динамика (изменение вещей) описывается преобразованиями состояний. С точки зрения математики описание динамики – это снова определение функции. Множеством значений и определений этой функции является множество всевозможных состояний объекта. Функции «высших порядков», аргументами и/или значениями которых служат функции, в математике принято называть операторами.

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

 

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

 

В математических терминах любой объект можно описать множеством допустимых состояний и классом допустимых преобразований состояний (операторов). Такое математическое описание объектов называют областью или доменом, пространством, типом данных или классом.

 

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

 

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

 

Пример моделирования

СВЕТОФОР

Состояния:

Наиболее очевидным кажется выделить единственный атрибут – цвет.

«Текущий цвет»

«Предыдущий цвет»

Область значений: {КРАСНЫЙ, ЖЕЛТЫЙ,     ЗЕЛЕНЫЙ }

Значения будем выделять заглавными буквами, чтобы не путать их с именами.

Множество всех состояний светофора:

S₁< ЖЕЛТЫЙ, КРАСНЫЙ >

S₂< ЖЕЛТЫЙ, ЗЕЛЕНЫЙ >

S₃< КРАСНЫЙ, ЖЕЛТЫЙ >

S₄< ЗЕЛЕНЫЙ, ЖЕЛТЫЙ >

 

Класс процедур преобразований состояний светофора состоит из 4-х функций:

<ГОТОВЬСЯ>

<ОСТАНОВИСЬ>

<ЕЗЖАЙ>

<СТОЙ>

 

Готовься = {< ЖЕЛТЫЙ, КРАСНЫЙ > → < КРАСНЫЙ, ЖЕЛТЫЙ >}.

 

Иной вариант – определить единственную функцию, задающую следующее состояние светофора

 

 

Наша модель абстрактна как с содержательной точки зрения («с точки зрения программиста»), так и с формальной («с точки зрения компьютера»). С точки зрения программиста она описывает абстрактный объект, т.е. все возможные в мире светофоры. С формальной точки зрения компьютера важно лишь то, что в модели 4 разных состояния и 4 функции, а не то, как они называются. Формальный смысл не изменится, если переименовать атрибуты.

 

Способы обозначения и определения процедур

 

Мы определили операторы как изменения значений некоторых переменных, имена которых принадлежат состоянию, в зависимости от значений тех же переменных

Оператор

<N₁→V₁                 <N₁→V₁’

…                     …

N_m→V_m>              N_m→V_m’>

 

где N – имена, V – значения.

 

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

для некоторых функций f₁ и f_m.

 

В программировании подобное преобразование записывается в виде:

N₁,…,N_m:=f₁(N₁,…,N_m),…,f_m(N₁,…N_m)

 

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

N_i:=f_i(N₁,…,N_m)

 

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

 

Каждый язык процедурного программирования – язык определения операторов. Сами процедуры можно трактовать как определение оператора заданием способа его вычисления.

 

Традиционно такой язык определяется:

1. классом базовых операторов (в частности допустимых присваиваний);

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

 

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

 

Языки блок-схем

 

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

В реальной жизни для того, чтобы отделить собственно имя от значения обычно используют кавычки:

‘Маша’ состоит из 4-х букв.

В языке блок-схем для этого используют рамку, например:

 y:=succ(x)  

здесь через succ обозначена одноместная функция – следующий за x в естественном порядке натуральных чисел.

 

Способы определения функций

 

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

φ(x)=f(g(x))

Функция φ – результат композиции функций f и g.

Обозначение суперпозиции процедур в терминах блок-схем.

 P₁ → P₂

 

Содержательный смысл композиции – последовательное выполнение фиксированного, явно заданного числа действий.

 

Предикат – условие, определяемое как функция.

 

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

 

ение 1 неявно, до начала работы операторов программы.

 

 

Для выходных потоков определен оператор записи write(f,e), где e – некоторое выражение.

{f→<a₁, a₂, …, a_n>, e→X}

write(f,e)

{f→<a₂, …, a_n, X>}

 

Выходные потоки изменяют количество компонентов, в ходе выполнения программы. Такие типы данных называются динамическими.

 

 

Трассировка программы

 

Очевидно, в ходе выполнения вычислений согласно некоторой блок-схеме для каждого входного состояния S выбирается некоторая ветка блок-схемы, т.е. последовательность операторных блоков S₁, …, S_n. Последовательность значений S₁(S), S₂S₁(S), …, S_nS_n-1…S₁(S) называется трассой выполнения.

 

Понятие трассы используется для трассировки - проверки работы алгоритмов путем выписывания трассы для данного входного состояния.

x,y:=y,x

x:=X y:=Y

x:=x•y y:=x/y x:=x/y

z:=x x:=y y:=z

x:=x+y y:=x-y x:=x-y

 

Не обязательно выписывать трассу после каждого выполняемого оператора, а лишь в некоторых особых контрольных точках. Определение таких точек тесно связано со структурированием алгоритмов.