В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 48

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 48)

Однако рамки одного стиля становятся тесными, если нас интересуют

тенденции и перспективы развития ЯП. Мало вероятно, что в ближайшей

перспективе какой-либо иной стиль программирования вытеснит операционный.

Отсутствует и какой-либо пример современного ЯП, который вобрал бы в себя

практически все накопленное богатство в этой области. Однако в ЯП

практического программирования попадает лишь то, что предварительно

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

полезно каждому, кто желает понимать, чего можно ждать от будущих ЯП.

Наконец, знакомство с нетрадиционным подходом и оригинальным взглядом на,

казалось бы, хорошо знакомые сущности доставляет ни с чем не сравнимое

удовольствие.

За некоторыми стилями программирования закрепились вполне определенные

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

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

отражают суть рассматриваемого подхода. Вместо слов, например,

"операционный стиль программирования" иногда говорят короче "операционное

программирование". Будем поступать аналогично по отношению ко всем

рассматриваемым стилям.

Рассмотрим несколько моделей ЯП, представляющих операционное,

ситуационное, функциональное, доказательное, реляционное, параллельное и

объектно-ориентированное программирование.

Первая из них играет роль чисто историческую, роль "начала координат".

Вместе с тем она предоставляет возможность на содержательно хорошо знакомом

материале познакомить с весьма общими понятиями, характерными для

математической позиции. В дальнейшем эти понятия применяются к менее

знакомому материалу при рассмотрении других моделей.

Остальные модели непосредственно предназначены для представления

определенных перспективных тенденций в области ЯП и программировании в

целом.

13.2. Операционное программирование - модель фон-Неймана (модель Н)

Рассмотрим модель, отражающую свойства первых ЭВМ - модель весьма

примитивную, но способную послужить для нас точкой отсчета. Опишем ее в

соответствии с концептуальной схемой из раздела 1.21.

Базис. Два скалярных типа данных: адреса и значения. Конечный набор

базисных скалярных операций (система команд): присваивание, условные

операции, останов и другие. Единственная структура данных - кортеж ячеек

(т.е. пар адрес -> значение) с линейно упорядоченными адресами (память).

Есть выделенная ячейка C (регистр команд), в которой хранится адрес

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

операция сама определяет своего преемника (в том смысле, что модифицирует

содержимое регистра команд).

Развитие. Никаких выделенных явно средств развития - все они скрыты в

универсальности набора операций, среди которых ключевую роль играет оператор

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

состояния памяти. Любое развитие возможно только путем явного моделирования

новых операций за счет универсальности системы команд. Что такое значение -

не уточняем. Достаточно считать, что это целые и строки литер (для

выделенных ячеек ввода-вывода).

Защита. Полностью отсутствует.

Исполнитель. Память - базисная структура данных (кортеж ячеек),

процессор - устройство, последовательно выполняющее указанные в С операции,

поведение - последовательность состояний памяти, план (программа) - исходное

состояние (или его выделенная часть), результат - заключительное состояние

(если оно есть; при этом содержательно результатом обычно служит лишь

выделенная часть заключительного состояния).

Указанные "части" для каждой программы свои. Так что в общем случае

программа формально не отличается от исходных данных и результатов - одни и

те же ячейки исполнитель может интерпретировать либо как содержащие команды,

либо как содержащие данные. Все дело в том, в какой роли адреса ячеек

используются в исполняемых командах.

Знаки и денотаты в модели Н. Сведения о базисе можно выразить с помощью

следующих обозначений.

Пусть А - тип данных "адрес" (т.е. множество адресов в модели Н), V -

тип данных "значение" (т.е. множество содержимых ячеек с адресами из А).

Тогда конкретное состояние памяти можно представить функцией s типа

S:A->V

т.е. конкретным отображением адресов в значения. Обратите внимание, мы

применяем метаязык (т.е. язык для описания языков), в котором допустимы

функциональные типы, причем структура функционального типа S описана парой

A->V

где A - область определения (область отправления) функций этого типа, а V -

область значений (область прибытия) функций этого типа.

Итак, состояние памяти (содержательно это кортеж содержимых ячеек)

представлено формально функцией из адресов в значения (хранящиеся по этим

адресам).

Тип функции "состояние" выражает первый принцип фон-Неймана - принцип

произвольного доступа к памяти (в конкретном состоянии s из S равнодоступны

все ячейки; задай адрес - получишь значение).

Операции (операторы) в модели Н - это объекты типа

St:S->S.

Кроме того, модель фон-Неймана характеризуется функцией декодирования

операций (частично определенной)

d:V->Com,

где Com - команды, т.е. операции, встроенные (элементарные,

предопределенные) в Н.

В этих обозначениях второй принцип фон-Неймана - принцип хранимой

программы отражается формулой

(А с из Com)(E v из V):d(v) = с ,

где A обозначает "для всех", а E - "существует". Т.е. всякую команду можно

записать в память (найдется способ ее закодировать).

[Фактически здесь использованы элементы некоторого языка для описания

семантики ЯП - семантического метаязыка. Язык для описания синтаксиса ЯП

знаком из курса программирования. Таким синтаксическим метаязыком служит,

например, БНФ (форма Бэкуса-Наура).]

Основное семантическое соотношение в модели Н (денотационная

семантика). Каков денотат программы s в модели Н? Другими словами, какова та

функция, которую реализует программа s?

Рассмотрим функцию r типа St

r:S->S

которая обозначает результат выполнения программы s, т.е. r(s) - это

состояние s1, в котором выполняется операция остановки (stop). Оно не всегда

достигается, т.е. функция r - частично определенная - ведь, не всякое

состояние может служить программой и не всякая программа завершает работу.

Так что, если C - регистр команды, то

d(s1(s1(C))) = stop.

(такому семантическому соотношению удовлетворяет заключительное состояние

s1).

Обозначим через k=d*s*s композицию функций d,s,s. Тогда основное

семантическое соотношение, определяющее денотат r(s) программы s в модели Н,

записывается так:

r(s)=если k(С)=stop, то s, иначе r(k(C)(s)).

Другими словами, нужно выполнить над состоянием s операцию,

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

вычислить функцию r от полученного нового состояния, пока не окажется, что

нужно выполнить операцию stop.

Что можно извлечь из формулы для r?

Во-первых, то, что один шаг выполнения программы требует, в общем

случае, трех обращений к памяти (в нашей модели регистр команд - в основной

памяти), ведь переход к новому состоянию описывается как d(s(s(С)))(s).

Во-вторых, становится еще очевиднее, что средства развития в модели Н

не выделены - денотат программы разлагается лишь на очень мелкие части -

денотаты отдельных команд (выраженные, кстати, функцией k). Отсутствуют

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

укрупнения денотатов.

Функциональная (денотационная) семантика. Пусть P = {p} - множество

программ, R = {r} - множество функций типа S->S. Функциональной или

денотационной семантикой программ называют функцию типа P->R, отображающую

программу (т.е. исходное состояние p) в соответствующую ей функцию r,

удовлетворящую основному семантическому соотношению.

Название "денотационная" возникло исторически. Всякая семантика

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

денотат (смысл).

Обратите внимание, насколько сложной концептуально оказалась знаковая

система Н. Во всяком случае, нам потребовались функции высших порядков (т.е.

функции, среди аргументов и (или) результатов которых встречаются снова

функции). Функции такого рода математики часто называют "операторами".

Действительно, посмотрите на перечень примененных функций:

s: A --> V

St: S --> S

d: V --> Com

r: S --> S

sem: P --> R

очевидно, что и операция, отображающая состояния (функции из адресов в

значения), и декодирующая функция - функции высшего порядка, как и

семантическая функция - по отношению к функциям p и r (первая из них

отображает адреса в значения, вторая - исходное состояние в заключительное).

Примеры программ в модели Н можно найти в любом учебнике по

программированию.

13.3. Ситуационное программирование - модель Маркова-Турчина (модель

МТ)

Модель Н возникла как обобщение такого поведения, когда после

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

устанавливает следующую команду). Такое поведение типично для рутинных

вычислений, на автоматизацию которых ориентировались первые компьютеры (они

были предназначены для расчетов, связанных с созданием атомной бомбы).

Расчеты такого рода характеризуются данными относительно простой

структуры - программы имеют дело с числами. Вся сложность поведения

исполнителя определяется сложностью плана (т.е. числом и связями указанных в

нем действий). Управление последовательностью действий зависит от сравнения

простых данных. Еще Джон фон-Нейман хорошо понимал, что для других классов

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

поведения.

13.3.1. Перевод в польскую инверсную запись (ПОЛИЗ)

Рассмотрим, например, задачу перевода арифметической формулы в

постфиксную форму. Другими словами, исходными данными для нашей программы

должны быть обычные арифметические формулы, а в результате нужно получить их

запись в ПОЛИЗе. Например,

(a+b)*(c+d) --> ab + cd + *.

Данные ко всякой программе записываются на некотором языке (являются

знаками в некоторой знаковой системе). Чтобы их обработать, нужно

воспользоваться правилами построения знаков в этой системе (синтаксисом

языка) для распознавания структуры знака, затем семантикой знаковой системы,

чтобы связать со структурой знака его смысл (денотат) и обработать данное в

соответствии с его смыслом.

Пусть синтаксис языка формул, которые мы хотим обрабатывать, задают

следующие правила БНФ:

<формула>::=<сумма>I<произведение>I<первичная>.

<сумма>::=<сумма>+<произведение>I<первичная>.

<произведение>::=<произведение>*<первичная>I<первичная>.

<первичная>::=<число>I<переменная>I(<формула>).

Числа и переменные точно определять не будем, оставляя представление о

них на интуитивном уровне (23 и 305 - числа, x, y, a, b, АЛЬФА -

переменные).

Тогда 23 - формула (первичная, произведение, сумма), a+b*23 - также

формула (сумма), (a+b)*23 - также формула (произведение); (a+*b) - не

формула.

Семантика формул - общепринятая. Смыслом (денотатом) формулы будем

считать число, получающееся из чисел, входящих в формулу, применением

указанных операций в общепринятом порядке. Задача состоит в том, чтобы

получить перевод в ПОЛИЗ, сохраняющий денотат (т.е. в данном случае - над

теми же числами нужно выполнить те же операции и в том же порядке).

Другими словами, было бы идеально, если бы вся программа записывалась

фразой примерно такого вида:

перевод(<формула1><операция><формула2>) =

перевод(<формула1>)

перевод(<формула2>)

<операция>

Две ключевые абстракции - анализ и синтез. Можно заметить, что перевод

текста с языка формул четко распадается на действия двух сортов - на

распознавание компонент структуры исходной формулы и на компоновку ее образа

Характеристики

Список файлов книги