«ОСНОВАНИЯ ПРОГРАММИРОВАНИЯ УДК 519.682 Непейвода Н. Н., Скопин И. Н. Основания программирования Книга представляет собой первое издание в серии, предназначенной для студентов, готовящихся к работе по современным ...»

Он указывает на особый способ использования переменной: в алгоритме scanf используется не значение X, а его адрес, чтобы указать, куда должно помещаться читаемое значение.

4. Тело функции. Следующие строки описывают алгоритм. Это подряд идущие операторы присваивания знаY = Y * Y * X;

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

5. Вызов функции вывода. Строка определяет формат вывода \n7 power of %d is %d\n и переменные X и Y, отформатированные значения которых вставляются вместо двух вхождений %d. "\n" — это символ завершения текущей печатаемой строки.

6. Завершение. Наконец, строка представляет завершающий вычисления оператор. В результате его выreturn 0;

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

Чем определяется последовательность действий линейной программы? Что может делать транслятор? И как это зависит от языка программирования?

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

СТРУКТУРА ВЫЧИСЛЕНИЙ И СТРУКТУРА ТЕКСТА ПРОГРАММЫ

§ 1.4.

Текст программы носит двойственную природу: это операционная структура, ориентированная на человека, но в то же время допускающая интерпретацию абстрактным автоматом. Например, структура вычислений программы 1.3.3 представлена на рис. 1.5, а структура ее текста — на рис. 1.6. Из этих рисунков видно, что понятия, использованные при задании текстовой структуры, во многом обусловлены тем, как вычисления представлены в виде текста, т. е. последовательности символов. Структура вычислений более свободна в этом отношении.

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

1.4.1. Последовательное, параллельное и совместное исполнение Для того, чтобы разобраться с тем, как порядок конструкций в тексте программы соотносится с порядком их исполнения абстрактным вычислителем и с представлением абстрактного вычислителя в конкретном, целесообразно Выделение памяти для X Выделение памяти для Y Рис. 1.5. Структура вычислений программы #include int main (void) scanf( “%d”, &X );

полнения.

При последовательном вычислении последовательность языковых конструкций переходит в команды абстрактного вычислителя, исполняемые строго в том порядке, который явно задан в тексте программы (именно так, в первом приближении, интерпретируется последовательность операторов, разделенных ";", в языках С и Pascal).

Параллельное вычисление означает, что для выполнения двух и более команд абстрактного вычислителя выделяется соответствующее число процессоров, каждый из которых выполняет свою команду (в стандартном С понятие параллельности отсутствует, в Алголе-68, Concurrent Pascal и других языках параллельные участки часто выделяются отдельными программными скобками, например, parbegin и parend; обрамляемые ими операторы могут быть выполнены параллельно).

Даже если на машине всего один процессор, указание на параллельность процессов часто полезно, поскольку оно позволяет организовать квазипараллельное исполнение, при котором команды каждого из процессов исполняются в строгом порядке, но они могут перемежаться в абстрактном вычислителе командами другого, квазипараллельно исполняемого, процесса. В частности, это позволяет более производительно использовать время, которое процесс тратит на ожидание завершения операции ввода-вывода. Например, при таком исполнении отрезок программы printf("Первый результат: %d, %d\n", X, Y);

Оператор 1;

printf("Второй результат: %d, %d\n", Z, V);

Oператор n;

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

Если они не успеют выполниться, пока печатается первая строка, то все в порядке, если успеют, то перед печатью второй строки придется подождать, пока допечатается первая.

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

В частности, C++, Java и Object Pascal Delphi имеют операторы порождения процессов, подобные которые все программисты воспринимают как исполняемые квазипараллельно с основным текстом программы (и правильно делают!). Но на самом деле еще более важна для обычных вычислений концепция совместного вычисления, когда порядок последовательного вычисления или параллельность выполнения двух и более команд абстрактного вычислителя не зависят от того, в каком порядке они заданы в тексте программы.

';

Следы совместности встречаются почти во всех языках программирования. Таково, например, совместное вычисление операндов операций. В операторе a, b, c, d могут вычисляться в любом порядке, перемежаясь с вычислениями того из подвыражений a*b, c*d, для которого уже готовы исходные данные.

Если a, b, c, d являются простыми переменными, то действительно безразлично с точки зрения результата, в каком порядке их вычислять. Но вычисление операнда может иметь побочный эффект, то есть вызывать не относящиеся к использующему оператору и не обозначенные явно действия. Например, побочный эффект появляется при вызове функции, в теле которой меняются значения глобальных переменных. Распознавать такие ситуации в общем случае невозможно. И поэтому в руководствах по языкам можно часто увидеть загадочную фразу «побочный эффект игнорируется», смысл которой соответствует тому, что в данном месте могут быть элементы совместного вычисления.

Явно и достаточно четко концепция совместного исполнения была проведена лишь в Алголе 68, в котором был введен другой разделитель операторов:

“,” вместе с оставшимся как признак строго последовательного исполнения “;”.

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

бы находить автоматизированно, но задача определения независимости операторов в программе алгоритмически неразрешима. Хотя ее можно решать в частных случаях, но гораздо лучше было бы сразу при составлении программы помечать, какие действия независимы. Слабое совместное вычисление возникает, если результаты зависят от способа исполнения группы операторов. Как говорят, в данном случае исполнение не детерминировано. Например, слабое совместное вычисление возникает в той форме условного оператора, которую предложил Э. Дейкстра [30] и интенсивно использовал Д. Грис20 [27]:

Этот оператор исполняется следующим образом. Совместно вычисляются все условия Ai, пока одно из них, например, Aj, не окажется истинным. Далее берется и исполняется соответствующий выполнившемуся условию оператор Sj. Если истинных условий не оказалось вообще, оператор (1.2) выдает ошибку.21 Например, вычисление минимума двух чисел в форме Дейкстры выглядит, как показано ниже:

Если наши данные не являются числами и лишь предупорядочены (см., напр. [34]), то не определено, какое значение получит z в итоге, но это нам и безразлично.

К сожалению, в общераспространенных системах таких средств не предусмотрено.

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

Даже если мы рассматриваем обычные числа, то в случае x = y мы можем получить результат путем двух различных действий.

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

Исполнение следующего фрагмента программы иллюстрирует, что использовать параллелизм и совместность нужно весьма осторожно.

X := 1;

parbegin parend;

Это некорректное по смыслу вычисление, поскольку невозможно сказать, какое значение получит переменная в результате счета. Если выполнение первого из указанных операторов завершится ранее, чем начнется чтение X во втором операторе, то Y получит значение 7, а в противном случае — 6.

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

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

Прямое решение на языке С — программа 1.4.1.

Программа 1.4. Корни квадратного уравнения /* Прямолинейная попытка */ #include /* это указание препроцессору о том, #include что нужно получить доступ к функции sqrt(), которая, как и средства ввода/вывода, имеется в стандартной int main (void) oat X1, X2; /* ВСЕ вычисления проводятся oat P, q;

oat D;

scanf ( "%f %f", &p, &q ); /* Ввод p, q. Обратите внимание на oat r;

плавающей точкой. Не забываем о взятии адреса: & */ printf ("\nX1 = %d; X2 = %d\n", X1, X2);

return 0;

Что будет, если r r q < 0? Ошибка счета!

Ответ на этот вопрос доказывает, что программу требуется доработать.

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

1. if ( условие ) действие T — если условие истинно, то выполняется действие T, в противном случае действие T пропускается;

2. if ( условие ) действие T else действие F — если условие истинно, то выполняется действие T, в противном случае выполняется действие F.

Действие T и действие F — это операторы языка. За счет блоков (последовательностей операторов, заключенных в фигурные скобки) можно в качестве действий использовать несколько операторов.

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

1. if условие then действие T 2. if условие then действие T else действие F Обе формы условного оператора восходят к устоявшимся стереотипам управления фон Неймановских машин. Так, для формы 2 годится схема, изображенная на таблице 1.1. Здесь выделены жирным шрифтом машинные коАдреса Команды манды, записанные в некотором произвольном формате:

(аргумент-регистр = false)? ПЕРЕЙТИ К аргумент-адрес перехода — условная передача управления по адресу перехода — безусловная передача управления по адресу перехода.

m+k+i и m+k+i+j изображают адреса, участвующие в командах перехода в качестве операндов.

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

Программа 1.4. /* Корни квадратного уравнения Попытка решения с разветвлениями */ #include #include int main (void) oat X1, X2;

oat p, q;

oat D;

oat r;

scanf ( "%f %f", &p, &q );

printf ("\nX1 = %f, X2 = %f\n", X1, X2);

else printf ("\nДействительные корни не существуют\n");

Оба приведенных выше представления условного оператора по сути изоморфны, и при каждом из них возникает одна и та же проблема. Рассмотрим запись К какому из if... then относится else? Есть два, с внешней содержательной точки зрения совершенно равноправных ответа:

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

1. Запретить использование условного оператор в качестве действия T.

Такое решение, принятое в Алголе 60, приводит тому, что при необходимости нужно превращать условный оператор в безусловный, обрамляя его блочными скобками:

2. Видоизменить синтаксис условного оператора, рассматривая само if как открывающую скобку и ввести парную к ней закрывающую, как сделано в языках Алгол 68, Modula-2 и Ada, соответственно:

Пожалуй, это решение — самое лучшее.

3. Принять соглашение: считать верным один из указанных перед началом данного перечисления вариантов (чаще второй). Именно такое решение предлагается для С, С++, Pascal. Даже если такое соглашение имеется, лучше им не пользоваться, а применять одно из тех представлений, в которых структура вычислений указывается явно!

РАБОТА СО ЗНАЧЕНИЯМИ

§ 1.5.

В наиболее часто используемых профессионалами языках программирования предполагается устройство вычислителя, близкое к реальной аппаратуре компьютеров. Известно, что компьютер выполняет действия в процессоре, а хранит данные и программы в памяти (см. § 1.2). Память может быть представлена на самом абстрактном уровне как некоторая совокупность контейнеров, в которых размещаются значения. Реально такие контейнеры чаще всего соответствуют ячейкам памяти, и именно на такое специальное (хотя и практически общепринятое сейчас) устройство логической структуры памяти ориентированы, в частности, традиционные языки. Из упомянутых нами примеров к такой структуре не привязаны Lisp, Рефал и Prolog. Дальнейшее рассмотрение в данном параграфе относится только к традиционным языкам.

В традиционных языках основными способами представлять значения и оперировать ими является использование переменных и констант. Рассмотрим некоторые базовые понятия, связанные с этим.

Значения всегда принадлежат некоторому типу.

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

Конец определения 1.5.1.

Например, число 1 — литерал со значением единица. "Что за чушь!" — литерал, обозначающий соответствующую строку символов.

Типом константы является тип ее значения. Если есть некоторый тип, то его множество значений чаще всего может рассматриваться как состоящее из константных значений данного типа.22 Например, bool — тип данных, множеством значений которого является {false, true}, а операциями — конъюнкция, дизъюнкция, исключающее или и отрицание.

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

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

Например, в языке Pascal "L" — изображение как литерного, так и строкового значений.

Значения обозначаются не только своими изображениями, т. е. литералами, но часто и именами, которые должны быть описаны как имеющие определенные значения (например в конструкции описания константы — см. ниже). Определение 1.5.2. Имя как конструкция (см. стр. 7) языка программирования — это последовательность символов, обычно букв, цифр и некоторых дополнительных символов (например, "_"), построенная в соответствии с определенными правилами (например, в С первый символ — буква или "_"), которая является лексемой.

Конец определения 1.5.2.

Например, в языке Pascal имя константы вводится описанием, подобным следующему:

Изображения констант разных типов, вообще говоря, могут совпадать, но всегда должны существовать соглашения, позволяющие, в частности, при определении имени константы, однозначно определить еще и ее тип. Например, в Алголе 68 константа описывается в виде Рассмотрим в языке C++ два частных случая:

В первом из них shortlength будет интерпретировано как обычное действительное число, имеющее значение, изображаемое 2.2888. Во втором то же изображение действительного числа понимается как константа, представляющая длинное действительное число, имеющее повышенную точность и расОбычно встречающимися исключениями из данного правила являются промежуточные значения, возникающие в ходе вычисления выражений, например, значение x + y в выражении (x + y) z, и литералы.

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

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

Пример 1.5.3. Рассмотрим оператор Этот оператор обозначает в языке C следующую последовательность действий:

Взять значение из ячейки, обозначенной как Y;

Сложить его со значением из ячейки, обозначенной как Z;

Поместить результат в ячейку, обозначенную как X.

Конец примера 1.5.3.

Пример 1.5.4. Рассмотрим оператор языка Pascal:

Этот оператор дает следующую последовательность действий:

Взять значение из ячейки, обозначенной как y;

Сложить его с целым числом, имеющим значение единица;

Поместить результат в ячейку, обозначенную как x.

Конец примера 1.5.4.

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

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

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

Чаще всего типовая информация вычисляется до выполнения программы, т. е. статически, и принципиальной новацией объектно-ориентированного подхода явилось, в частности, широкое использование динамического определения типа объекта и, более того, динамического его переопределения в некоторых пределах.26 В дальнейшем это было перенесено и на типы данных, используемые в работе с распределенными системами. В частности, в системах COM и CORBA, предназначенных для построения программ, работающих по схеме клиент-сервер (программ, которые могут работать в качестве объектов внутри других, заранее неизвестных программ (клиент) или же, наоборот, использовать такие объекты, которые динамически подставляются в момент исполнения (сервер)) широко применяется тип данных variant, значение которого несет информацию о своем типе внутри себя.

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

Достоинствами тегирования, реализованного аппаратно, являются:

• семантически емкие операции (в частности, поэтому время выполнения программ сокращается);

• дополнительный контроль корректности вычислений.

В языковых терминах это выражается как динамическая (определяемая при выполнении программы) типизация данных.

На практике впервые такие средства получили распространение в языке SMALLTALK.

определяет тип того, что хранится в основной части ячейки (тип значения) Рис. 1.7. Структура ячейки при тегировании В языке C тегированное данное соответствует описанию структуры, подобному Здесь второе поле структуры tagged является значением, тип которого может быть либо целым, либо действительным. Первое поле должно (по смыслу идентификатора) быть значением, которое однозначно идентифицирует, согласно некоторой системе договоренностей, тип второго поля. При этом приходится внешним образом (например, в фирменных либо технологических стандартах) определять множество соглашений, являющихся по сути затыканием очевидных недоделок языка. В данном случае (как и во многих других) в языках Pascal и Ada приняты более логичные решения. Например, в языке Pascal говорится о вариантной части структуры, причем должен явно определяться соответствующий тег и значения этого тега, приписанные каждому варианту:

Соотношение между понятиями имя, значение, тип, константа и переменная наиболее точно и строго определено в языке Алгол 68. Эта точность отражена и в языковых конструкциях описания имен. Так, описание type Имя = выражение_вырабатывающее_значение_типа_тип;

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

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

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

рассматривается как сокращение для где loc type — это выражение, вырабатывающее новое значение типа ref type (локальный генератор адреса для размещения значений типа type в качестве содержимого по указанному адресу; это — один из исключительно редко встречающихся случаев, когда переменная задается не именем, а значением некоторого выражения). Таким образом, по-прежнему определяется константа, значением которой обладает имя Имя1.

Но это значение есть адрес (о чем говорит служебное слово ref), и появляется возможность использовать Имя1 как переменную: можно присваивать ей значение типа type.

Аналогично сокращение для Таким образом, есть возможность присваивать Имя2 значение типа ref type.

Иными словами, Имя2 — это переменная, предназначенная для размещения в ней адресов, или, что то же самое, имен других переменных.

Таким образом, последовательность предложений описывает константу A со значением, равным результату деления числа 53 на 5, и переменную B вещественного типа. Можно записать и выполнить присваивание B:=A, но не наоборот. Если же записать то A оказывается переменной и присваивание A:=B становится законным.

В языке С все, казалось бы, проще. Понятие констант и переменных определяется на уровне соглашений об их отношении к памяти вычислителя. Описание определяет имена X и Y как переменные, способные принимать целочисленные значения, а как вещественные переменные. Но, как и обычно, иная простота хуже воровства. За недоработку в базовых понятиях приходится многократно платить целой серией соглашений, которые сейчас будут описаны для простейшего случая, и которые отдельно и достаточно сложно вводятся для более сложных случаев, возникающих, в частности, в объектно-ориентированном программировании.

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

• auto — автоматические переменные (слово auto можно не указывать).

Они имеют локальную область действия: только внутри текста той программной единицы, в которой автоматическая переменная определена, ее можно использовать, т. е. употреблять ее имя как ее наименование. Это позволяет, сгруппировав некоторый текст с помощью {}, вводить в данном тексте свои имена, не заботясь о том, что происходит снаружи. Если снаружи была определена переменная с таким же именем, то работает внутреннее описание. Эта блочная структура областей действия имен является общепринятой для большинства современных языков программирования и для логических языков.

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

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

• static — статические переменные. Этим термином определяются переменные, которым приписано фиксированное место в памяти. Они создаются при входе в программу и никогда не уничтожаются. В частности, статические переменные функций сохраняют свои значения от вызова до вызова функции.

• register — регистровые переменные. Это те переменные, которые для оптимизации вычислений размещаются в специальных (быстрых) регистрах процессора (если это возможно). Во всем остальном они полностью аналогичны автоматическим переменным.

Понятие класса памяти подтверждает тот факт, что С создавался как язык программирования для вычислителя вполне определенной архитектуры. Сейчас язык C++ реализован практически для всех архитектур. Но для них, с одной стороны, некоторые из конкретных средств С оказались избыточными (например, регистровые переменные на архитектуре Intel), с другой стороны, для некоторых из ценных качеств, предоставляемых архитектурно, в С++ нет средств для их эффективного использования (примером является тегирование). В целом в языке C и его наследниках догматизируется принцип однородности памяти.

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

Программа 1.5. /* Вычисление среднего арифметического значения #include #dene two int X, Y;

int main (void) scanf ( "%d, %d ", &X, &Y );

printf ("\n average of %d and %d is %d\n", X, Y, (X + Y) / two );

return 0;

Поскольку логически понятие константы весьма полезно и ничему не противоречит, в С++ оператор описания константы введен и имеет обычную форму (показанную в фрагменте (1.4)).

Тому, чему в Алголе 68 соответствовали значения типа ref ref type и так далее, в С соответствуют указатели, например:

и ссылки:

int **a;

int &r;

1. Возьмите книгу по программированию на неизвестном вам языке (желательно выбрать первый доступный из списка Ada, Perl, Modula, Java, FORTRAN) и, не читая текста, поймите некоторые из приведенных в ней программ. Повторяйте это упражнение раз в несколько месяцев по мере овладения новыми понятиями программирования.

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

3. Приведите пример программы, в которой выражения вида дают различные результаты.

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

5. Постройте трансляцию формы условного оператора из п. 1 на стр. 56 в команды фон Неймановского вычислителя.

6. Постройте программу вычисления значения ex при целых значениях x в диапазоне от 1 000 000 000 до 1 000 000 000, выдающую порядок числа и 10 точных значащих цифр. Проверьте свою программу, воспользовавшись какой-либо математической системой высокого уровня (например, Maple).

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

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

b) Нужно понимать, как представлены средствами языка сущности, закодированные в программе. Это включает в себя ясное понимание того, как будут исполняться предусмотренные нами действия над данными сущностями.

c) Знание конкретных команд вычислителя необязательно, но требуется понимание того, какие ограничения вносит конкретное представление с тем, чтобы не оказаться в ситуации, когда, казалось бы, технические детали существенно влияют на решение и полностью сбивают нас с толку. В качестве примера здесь можно упомянуть непредсказуемость результатов действий над целыми числами при превышении их диапазона. Со следствиями обычно явно не диагностируемого переполнения диапазона целых чисел сталкиваются не только программисты.

Например, во многих играх это — одна из самых коварных ошибок.

d) Все вышеизложенные аспекты соединяются воедино в проблеме переносимости программ, возникающей перед каждым профессиональным программистом. Например, Вы написали программу для Windows, а использовать ее оказалось необходимо для машин с операционной системой Unix, и так далее. Эта задача является очень сложной и в практически важных случаях почти всегда теоретически неразрешимой.2 Некоторое время мировое программистское сообщество интенсивно занималось проблемой переносимости, но затем, так и не добившись серьезных результатов, перешло на «более интересные» темы освоения новых архитектур машин и новых операционных систем, тем более, что фирма Sun объявила проблему решенной, представив язык Java. Тем не менее, проблема стоит, и новое поколение программистов столкнется с ней уже в гораздо более запущенном состоянии. Связь данной проблемы со всеми сторонами строгого и точного определения языка очевидна. Для ее успешного решения, в частности, необходимо выработать четкое понимание абстрактных и конкретных аспектов системы программирования. На нынешний момент единственно практичное решение проблемы переносимости — с самого начала писать программу так, чтобы она была переносимой. Дополнительные затраты труда при этом обычно в пределах 5–10%, а перенос непереносимой программы часто требует ее полного переписывания с самого начала, что означает не менее чем 100% дополнительных затрат.

СИНТАКСИС, СЕМАНТИКА

§ 2.1.

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

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

программы — то, как исполняется ее текст после перевода транслятором).

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

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

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

• Считать определением языка формальную лингвистическую систему (грамматику).

Это соответствует взгляду на язык как на множество правильных последовательностей символов, изложенному на стр. 6. Мы выделяем некоторое множество правильных (синтаксически) программ L и описываем его формально. Если это описание явное, оно может быть понято человеком и использовано для построения либо для контроля правильности работы транслятора. Но синтаксическая правильность не гарантирует даже осмысленности программы. Таким образом, здесь определяется лишь одна сторона языка — синтаксис.

• Считать определением языка соответствие между структурными единицами текста и правилами интерпретации. Это также односторонний взгляд, поскольку структурные единицы должны соединиться в синтаксически правильную систему, но он раскрывает вторую сторону языка — семантику.

Определение 2.1.1.

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

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

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

Конец определения 2.1.1.

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

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

• К понятности для программиста и умеренной сложности описания.

• К точности и полной определенности для построения транслятора или интерпретатора.

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

Если какая-то задача не решается целиком, надо пытаться выделить те ее части, которые легче поддаются решению и позволяют хотя бы приблизиться к поставленным общим целям. В данном случае оказывается, что синтаксис описывается во всех разумных случаях намного легче семантики. А синтаксис можно разделить на две части: контекстно-свободную грамматику3 (КСграмматика) языка, которая представляется достаточно обозримым образом даже для таких монстров, как C++ или Ada; и правила задания контекстных зависимостей, дополняющие контекстно-свободное описание.

Содержательно можно охарактеризовать КС-грамматику языка как ту часть его синтаксиса, которая игнорирует вопросы, связанные с зависимостью интерпретации лексем от описаний имен в программе. На уровне КС-грамматики можно также достаточно точно описать некоторые семантические аспекты языка.

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

Неоднократные попытки формально описывать контекстные зависимости при определении языков показали, что эта задача гораздо более сложная, чем задание контекстно-свободного синтаксиса. Вдобавок ко всему, даже такие естественные правила, как только что представленное, при формальном описании становятся громоздкими и весьма трудно понимаемыми человеком. По этой причине в руководствах редко прибегают к формализации описаний контекстных зависимостей (одним из немногих исключений такого рода является Алгол 68, за что разработчики языка были подвергнуты весьма серьезной критике; позитивным результатом этой критики явилось создание языка Pascal; см. стр. 28).

В практических описаниях языков и в курсах программирования обычно довольствуются неформальным, но достаточно точным описанием контекстПонятие контекстно-свободной грамматики стало первым строгим понятием в описаниях практических алгоритмических языков. Что это такое, в базовом курсе программирования определять нет смысла, поскольку за понятием КС-грамматики, при внешней его простоте, стоит достаточно серьезная теория. Эта грамматика представляется во многих формах (синтаксические диаграммы, металингвистические формулы Бэкуса-Наура либо расширенные металингвистические формулы), и, как правило, сопровождает любое систематизированное изложение конкретного языка. Любое такое конкретное представление КС-грамматики достаточно понимаемо.

ных зависимостей. Приведем пример такого описания.

Пример 2.1.2. Дадим следующую характеризацию налагаемого (в частности языком С) требования, что каждое имя должно быть описано.

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

Это описание должно стоять либо в данном блоке, либо в охватывающем его, и предшествовать в тексте программы использованию данного имени.

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

Такая совокупность требований достаточна для того, чтобы человек мог проверить по тексту программы, как в данном месте понимается данное имя.

Конец примера 2.1.2.

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

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

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

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

a) Понятия языка (языковые конструкции — определяемые и входящие как ского языка, обрамляемые угловыми скобками < и >. Эти слова и сочетания слов называются наименованиями понятий.

b) Символы и (непрерывные) последовательности символов, из которых строятся языковые конструкции, изображают сами себя и обрамляются кавычками “ и ”. Такие последовательности, в частности, представляют изображения некоторых лексем.

c) Каждое правило в определении грамматики размещается с нового абзаца.

d) Определяемое понятие отделяется в синтаксическом правиле от своего определения знаком ::= (читается: «определяется как»).

e) Вариантные фрагменты правила, т. е. те части определяемой конструкции, которые в тексте программы могут иметь различное представление, обрамляются скобками [ и ]; между собой варианты разделяются знаком f) Если за фрагментом, заключенным в скобки [ и ], следует знак +, то в текстовом представлении определяемого понятия фрагмент повторяется произвольное число раз.

g) Если за фрагментом, заключенным в скобки [ и ], следует знак *, то фрагмент повторяется (произвольное число раз) либо отсутствует.

h) Если за фрагментом, заключенным в скобки [ и ], следует знак ?, то фрагмент может либо присутствовать, либо отсутствовать.

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

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

2. Следующие фрагменты текстов считаются комментирующими:

(a) пробелы, знаки табуляции и перехода к следующей строке текста;

(b) последовательности символов, заключенные в /* и */, и не содержащие в себе эти пары символов;

(c) последовательности символов, начинающиеся с "//"и заканчивающиеся концом строки текста.

Комментирующие фрагменты нужны только для пояснений.

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

4. При описании языка используются понятия вида, где многоточием обозначена последовательность символов, не содержащая >.

Каждое из них является лексическим и синтаксически определяется как (см., напр., определение ниже):

“G” | “g” | “H” | “h” | “I” | “i” | “J” | “j ” | “K ” | “k ” | “L ” | “l” | “M” | “m” | “N” | “n” | “O” | “o” | “P” | “p” | “Q” | “q” | “R” | “r” | “S” | “s” | “T” | “t” | “U” | “u” | “V” | “v” | “W” | “w” | “X” | “x” | “Y” | “y” | “Z” | “z” | “_” В дальнейшем правила порождения имен понимаются в указанном только что смысле.

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

::= “#include” Комментарий /*это определение упрощено*/ здесь и далее означает, что в стандарте языка данное понятие определено более полно. Некоторые из таких понятий в дальнейшем будут дополняться.

“(” [ [“,” ]* ]? “)” “{” ::= |“void” ::= < имя параметра > [ “,” ::= “=” /* определяется позже */“;” ::= /* пустая последовательность лексем */ Вывод понятия в КС-грамматике можно представить как дерево, в вершинах которого стоят терминальные символы, а в корне — выводимое понятие.

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

Пример 2.1.3. Вывод описания функции main смотри на рис. 2.1. С помощью данного вывода получается простейшая программа Конец примера 2.1.3.

void main(void){} Для усвоения материала настоятельно рекомендуется построить вывод какой-либо из предъявленных выше программ на основе приведенных правил.

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

Если семантическое соответствие определено, то задача трансляции языка —это построение двух программ:

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

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

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

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

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

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

• образ мышления программиста при составлении программы характеризуется как абстрагирование;

• трансляция может осуществляться на разных конкретных вычислителях;

• исследование общих свойств программ математическими методами возможно только при отвлечении от особенностей конкретных вычислителей.

Следуя этой точке зрения, мы, говоря о модели программы, всегда имеем в виду ее образ в виде команд абстрактного, а не конкретного вычислителя.

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

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

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

программа окажется неприемлемой, если ее вычисление с реальными данными выходит за определенные временные границы (для каждой программы свои!). Об этом вынуждены заботиться и трансляторы, а потому они никогда не следуют модели вычислений языка точно. Другая возможная причина расхождений абстрактной и конкретной моделей вычислений — неоправданная сложность алгоритмов трансляции, из-за которой приходится идти на те или иные ограничения, делать (может быть) разумные предположения о том, какими будут реальные программы и т. д. Иными словами, реализованный язык всегда демонстрирует прагматический компромисс между абстрактной моделью вычислений и возможностями ее воплощения. Как влияет такой компромисс на языки программироваНа самом деле даже в принципе ни один вычислитель не может точно работать с такими идеальными и актуально бесконечными объектами, как действительные числа.

Показательный пример такого рода дает язык FORTRAN. В этом языке разрешается использование идентификаторов с пробелами (причем пробелы внутри идентификаторов просто игнорируются), в том чисел и таких:

Транслятор должен отличить присваивания таким переменным от соответствующих начал условного и циклического оператора, например Как он это ухитряется делать, рассматривать нет смысла, но гораздо практичнее и безопасDO I=1,...

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

ния — предмет обсуждения следующего параграфа.

ПРАГМАТИКА

§ 2.2.

До сих пор речь шла об определении языка его абстрактным вычислителем. Конкретные условия реализации дополняют такое определение в следующих направлениях:

• Все определения становятся явными (изгоняются такие понятия, как «не определено», «определяется реализацией» и т. п.)7.

• Появляются дополнительные конструкции, описатели и др., обусловленные реализацией. Они обязательно учитывают:

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

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

Пример 2.2.1. В языке Pascal есть так называемые прагматические комментарии, например, {$I+}, {$I-} (включение/выключение контроля ввода-вывода). Многие из таких комментариев практически во всех версиях одни и те же. В самом стандарте языка явно предписана лишь их внешняя форма: {$... }.

Конец примера 2.2.1.

Рассмотрим крайний случай. Пусть данный язык ориентирован на реализацию лишь в единственной операционной обстановке (например, это какойнибудь язык скриптов для микропроцессора, встроенного в собачий ошейник). Есть ли надобность в этом случае выделять прагматику специально?

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

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

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

Пример такого рода — скоропись для определения переменных и констант в Алголе-68 (см. стр. 64).

Другой пример более интересен. Это команды увеличения и уменьшения на единицу. В С/С++ они представлены операторами ++; или ++;

- -; или --;

В Turbo-Pascal:

Inc () соответственно. В С/С++ команды такого рода следует относить к модели выDec () числений языка, так как для нее постулируется, что язык является машинноориентированным и отражает в себе особенности архитектуры вычислительного оборудования, а команды увеличения и уменьшения на единицу предоставляются программисту на уровне оборудования достаточно часто.

Если же рассматривать Turbo Pascal как правильное расширение стандартного языка Pascal, не содержащего обсуждаемые команды из-за стремления к минимизации средств, то эти команды есть не что иное, как подсказка транслятору, как надо программировать данное вычисление. Следовательно, указанные операторы для данного языка нужно относить к прагматике. Семантическая прагматика — это уже упомянутые определения того, что в описании языка оставлено на усмотрение реализации или предписывается в качестве вариантов задания вычислений.

Пример 2.2.2. Стандарт языка Pascal утверждает, что при использовании переменной с индексом на уровне вычислений контролируется выход индекса за диапазон допустимых значений. Однако в объектом коде постоянные проверки этого свойства могут оказаться накладными и избыточными (например, когда можно гарантировать соответствующие значения индексов).

Стандарт языка для таких случаев предусматривает сокращенный, т. е. без Вообще говоря, данная подсказка избыточна для современных трансляторов, поскольку распознать шаблон вида “:=” “+” и им подобные не представляет труда не только в тех случаях, когда указана явно, но и тогда, когда она вычисляется (индексирование, косвенная адресация и т. д.). Таким образом, обсуждаемые операторы можно рассматривать и как прагматику-скоропись.

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

Конец примера 2.2.2.

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

Определение модели вычислений языка дает рецепт, как отделять прагматику от семантики: прагматика — это то, что органично не вписывается в абстрактные вычисления программы. Но это весьма неконструктивный рецепт, и разработчики языка должны прилагать специальные усилия, чтобы обеспечить явное выделение прагматического уровня. Зачем это нужно? Ответ прост: без этого может сложиться превратное представление как о предлагаемой модели вычислений, так и о ее реализации. Вдобавок к тому, резко ограничиваются возможности программиста применять в своей практике методы абстрагирования. Следующие иллюстрации обосновывают данное утверждение.

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

Постулируется, что программа на языке С есть то, что получается после работы препроцессора с текстом (разумеется, если результат такой работы окажется корректным). Следовательно, использование препроцессора — синтаксическая прагматика языка. Но это противоречит практике работы программиста: он просто не в состоянии написать содержательную программу, которая могла бы выполняться без использования при своей трансляции препроцессора. Если при программировании на С ограничиваются употреблеГЛАВА 2. ССП нием препроцессорных команд подключения файлов определений и определения констант, то работа препроцессора не очень затрудняет понимание получившейся программы. Но когда применяются, к примеру, условные препроцессорные конструкции, возможно появление программ-химер, зрительно воспринимаемый текст которых дезинформирует относительно их реальной структуры.

Пусть написано Внешне это выглядит как то, что действие выполняется, если x 0, но первый макрос раскрывается как...

и возможности использования представленных выше схем.

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

ПРИНЦИПИАЛЬНЫЕ ТРУДНОСТИ, СВЯЗАННЫЕ С СЕМАНТИКОЙ

§ 2.4.

Любой алгоритмический язык является формальным языком10. Поэтому Точнее, должен являться в теории и во всякой своей конкретной реализации является.

Переменная Константа Имя = sqrt Операнд Переменная Рис. 2.11. Представление фрагмента текста программы для его точного определения нужно задать его синтаксис и семантику. Методы определения синтаксиса рассматриваются во вводных курсах программирования для будущих профессионалов. Хотя полноты определения синтаксиса обычно не достигают, но изложение этих методов достаточно последовательное и строгое (как Вы могли увидеть в предыдущих главах данной книги). Даже если нечто объясняется на пальцах вместо кропотливого точного определения (как, например, соглашения о том, какое описание соответствует какому вхождению идентификатора), об этом говорится прямо.

Семантику же обычно рассказывают на поверхностном уровне, без тени точных определений, в выражениях типа «При исполнении присваивания x:=S старое значение, содержавшееся в памяти, обозначенной именем x, используется для вычисления S, после чего заменяется на полученное значение.» Это скорее беда, чем вина начальных (да и профессиональных) курсов программирования. Ведь смысл — многоаспектное, крайне сложное и неформализуемое понятие. Это означает, что любое его уточнение приемлемо лишь для некоторых целей и отказывает в других случаях. Но это не означает, что формализовывать семантику не нужно. Ведь если мы откажемся от ее формализации, мы тем самым сползем на позицию первых языков типа FORTRAN: смысл выражений языка определяется тем, как они переводятся транслятором и исполняются компьютером. Далее, поскольку алгоритмические языки делались прежде всего не для удобства определения их свойств, а для удобства их использования, работает концептуальное противоречие, которое вы могли бы уже заметить в курсе, например, логики: чем удобнее представление формального понятия для применения, тем тяжелее его строгое формальное определение. Определение семантики реальных алгоритмических языков намного сложнее семантик математических языков (хотя и намного проще семантик естественных языков). Оно находится как раз на той грани, когда считанные по пальцам профессионалы еще могут создать точное и полное определение и воспользоваться им, но при этом практически все их интеллектуальные ресурсы уходят на выработку и освоение данного понятия. Соответственно, данное точное определение задает лишь значение либо действие конструкций языка, Конечно, такое определение семантики алгоритмического языка в принципе является непогрешимым для каждой конкретной его реализации, применяемой в конкретной среде программирования. Но оно, мало того, что ничего не дает для осмысленного применения человеку, еще и меняется непредсказуемо при изменениях версии или настроек транслятора и всей вычислительной системы.

2.4. ПРИНЦИПИАЛЬНЫЕ ТРУДНОСТИ, СВЯЗАННЫЕ С СЕМАНТИКОЙ совершенно игнорируя их содержательный смысл. Так что тот, кто пользуется алгоритмическим языком на практике, прибегает к точному определению (если оно имеется; в частности, у языка Pascal его нет, есть лишь стандарты, которые практически не применяются) лишь в самом крайнем случае, и обычно при помощи посредника-трансляторщика. И даже те, кто реализуют язык программирования, обычно вовсю нарушают формальное определение, если только они не будут проходить официальную аттестацию на строгое соответствие принятому стандарту (как, например, разработчики трансляторов для языка Ada, сертифицируемых Министерством обороны США).

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

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

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

III) Логическая семантика. Далее, программа решает некоторую задачу.

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

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

IV) Трансляционная семантика. Далее, программа должна быть обработана нашей вычислительной системой и переведена в исполняемый код.

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

V) Алгебраическая семантика. И, наконец, нам часто нужно преобразовывать программы, и тогда на совокупность программ естественно смотреть как на некоторую обобщенную алгебраическую систему. Соответственно, те внутренние понятия программ, для которых критично наличие внутренне непротиворечивой и богатой системы преобразований, тоже описываются на алгебраическом языке.

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

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

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

1. Вернитесь на стр. 70. Подумайте, в каких случаях и почему затраты на переписывание программы могут превысить 100% ее исходной стоимости?

2.4. ПРИНЦИПИАЛЬНЫЕ ТРУДНОСТИ, СВЯЗАННЫЕ С СЕМАНТИКОЙ Интерпретационная Теория алгоритмов Функциональная Топология Логическая Теория моделей Трансляционная Теория графов Алгебраическая Теория категорий Таблица 2.1. Семантики и требуемые знания 2. Приведите пример на используемом Вами языке программирования, когда программа корректна при одних значениях прагматических параметров (прагматических комментариев, параметров трансляции или чего-то другого, что используется в Вашей стандартной системе программирования), а при других — успешно транслируется, но дает неверный результат.

3. Семантика каких понятий языка задается без ссылок на семантику других понятий языка?

4. Возьмите какой-нибудь официальный стандарт описания языка (желательно Алгола 68 [65] или Ada) и попытайтесь прочесть хотя бы три страницы определений.

5. Приведите пример графически разных операторов с одинаковым абстрактным синтаксисом.

6. Реализуйте приведенные на рис. 2.11 схемы вызова процедуры при помощи действий с указателями.

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

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

Рассмотрению различных стилей программирования мешала иллюзия безусловной пользы от универсальности, пронизывающая современную теорию и практику. До сих пор слово ‘универсальный’ используется в качестве хвалебного эпитета. Но универсальная система не всегда является удобным инструментом в конкретных обстоятельствах. Воспользоваться такой системой целесообразно, в частности, если задача достаточно простая и освоение инструмента для ее решения потребует больше сил, чем само решение. Если бор подходящего инструмента многократно окупится.

Беда в том, что порой в качестве универсальной рекламируется большая специализированная система, плохо спроектированная, плохо проанализированная или переросшая в результате «добавления новых возможностей»

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

А для решения нашей задачи необходимо сначала разобраться в самом понятии стиля программирования.

СТИЛИ ПРОГРАММИРОВАНИЯ

§ 3.1.

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

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

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

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

• Поощрение (или прямое предписание) использования некоторых базовых концепций программирования.

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

• Требования и рекомендации по оформлению и документированию программ.

• Совокупность инструментальных и организационных средств, поддерГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА живающих все вышеперечисленные требования и рекомендации.

То, что в данном тексте называется “методикой программирования”, в литературе традиционно называется “методологией”, а то, что у нас обозначается этим словом, называется “парадигмой программирования”.

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

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

Важнейший аспект стиля и соответствующей ему методологии: запрещения и самоограничения. Необходимо твердо усвоить, что многие базовые концепции плохо согласуются друг с другом. В результате, будучи соединенными вместе, они утрачивают свои лучшие стороны, зато многократно усиливают худшие (как говорят, они концептуально противоречат друг другу). Поэтому каждый стиль отгораживается от тех конструкций, которые концептуально противоречат ему (если уж вам такая конструкция необходима, выносите ее в под-, над- или сопрограмму)2. Большой бедой является то, что, запрещая не согласующиеся со стилем конструкции, практически всегда представляют их как абсолютно плохие, хотя на своем месте они часто Заметим, что в программировании происходит систематическая ‘возгонка’ понятий. То, что в других местах называется орудием, здесь называется методом; то, что называется методом или методикой, называется методологией; то, что называется методологией, возводится в ранг парадигмы, и т. д. В данном пособии мы придерживаемся выражений, более адекватно передающих смысл используемых понятий и согласующихся с общечеловеческой практикой.

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

великолепно работают.

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

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

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

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

Поэтому рассмотрим читателей программы.

Самый очевидный читатель программы — это вычислитель, для которого А непонимание и неучет читателя, соответственно, один из распространеннейших недостатков.

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

она составляется. С узко программистской точки зрения, ориентированной в основном на производителя, можно, более того, говорить лишь о конкретном вычислителе. Тогда критерии качества программного текста укладываются в задачу повышения эффективности результирующей программы. Но такой путь немедленно ведет в тупик. Так, ошибки при программировании (а это правило; программист чувствует на себе, что атрибут человека — ошибка), делают необходимым рассмотрение, по крайней мере, еще одного читателя: автора программы, который вынужден исправлять составленный им же текст. Далее, в реальной ситуации часто появляется и несчастный, который вынужден исправлять текст другого программиста. Следовательно, появляется ряд критериев качества программы: ее понятность, приспособленность для модификаций представленного программой алгоритма и его модернизаций. Заметим, что обеспечить выполнение значительной части этих критериев (но далеко не всех) можно, рассмотрев в качестве читателя абстрактного, а не конкретного вычислителя, поскольку именно абстрактные вычисления являются предметом деятельности программиста. Более того, чем глубже мы погружаемся в предмет программирования, тем больше становится ясно, что задача эффективного исполнения программы конкретным вычислителем на самом деле одна из наиболее низкоприоритетных при составлении программного текста4.

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

Уже само по себе наличие комментариев говорит о том, что программа предназначена для чтения человеком, (путь даже единственным человеком — ее автором). На практике же всегда приходится иметь дело и с другими читателями программы, которые в силу разных причин вынуждены разбираться в том, как она работает. Для поддержки этого процесса необходимы соглашения между разработчиком и читателем, способствующие пониманию. Здесь Низкий приоритет задачи не влечет, что ей всегда можно пренебречь, но практически всегда означает, что ею можно заняться в последнюю очередь. “Практически всегда”, в свою очередь, понимается как: ‘всегда, если задача не заставляет нас явно заняться этим вопросом’. А задача определяется как цель в заданных ограничениях, и тот компонент задачи, который чаще всего заставляет заняться вопросами эффективности — это ограничения.

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

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

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

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

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

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

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

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

• Как структурировать априори однородную память?

• На какие логические и физические части должна разбиваться программа?

• Как преодолевать сложность процесса разработки программного обеспечения?

• За счет чего можно достичь повторного использования накопленных программных решений и облегчать модификации программ?

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

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

Более того, привязанность стиля к базису часто переоценивается. Например, в книгах [37, 77] приведены методики, как структурно программировать для столь неструктурных языков, как старые ассемблеры, FORTRAN и Но некоторые из характеристик стилей, связанные с традиционной модеCOBOL.

лью, являются специфичными для нее и не поддаются интерпретации вне ее рамок. В первую очередь это касается операторов присваивания, в частности, присваивания глобальным или локальным объектам. Другая специфичная характеристика фон Неймановской модели — централизованное формирование последовательности приказов для задания вычислений и тесная взаимосвязь этого порядка с порядком записи операторов в программе. Эта модель принципиально императивна, т. е. все действия, которые возможны при выполнении программы, задаются в повелительной форме. А можно ли строить программы, используя изъявительное наклонение? Как показывает опыт нетрадиционных языков, ответ на этот вопрос утвердительный: да, причем достаточно красиво и эффективно!

Вместо приказа выполнить то или иное действие в неимперативном языке должны быть записаны условия, ограничения и предпочтения, которые выявляют подходящие для исполнения действия. Следовательно, нет нужды в разбиении цели на приказы, последовательность которых приводит к реализации цели, — система сама выстроит действия, нужные для достижения цели и сама гибко перестроит их в зависимости от имеющихся и появляющихся соотношений между данными. В одной из первых монографий по языку Рефал [72] В. Ф. Турчин выдвигает любопытное положение: мерой развитости естественного языка служит доля в нем изъявительного наклонения (чем меньше приказов, тем язык богаче). Это утверждение выглядит еще более правдоподобным, если применять его не к языку народа, а к языку индивидуума. Турчин пытается перенести его в сферу искусственных языков и, в частности, языков программирования. И хотя в те годы (начало 70-х) опыт языков программирования, построенных на идее использовать соотношения вместо приказов, т. е. изъявительность вместо повелительности, был очень мал, продуктивность их использования, разумеется, в своих сферах приложения, уже тогда стала очевидной.

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

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

Реализация идеи внедрения изъявительного наклонения в языки программирования возможна по следующим направлениям:

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

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

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

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

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

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

Если граф коммутационной системы содержит циклы, то он может быть проинтерпретирован как рекурсивная система фукнций. Такая система может быть теоретически развернута в бесконечный ациклический граф, но не каждый бесконечный ациклический граф задает рекурсивную систему функций. Но функции, связанные (возможно, косвенной и взаимной) рекурсией — не единственная вычислительная модель коммутационной системы. Имеются и другие модели, которые совмещают параллелизм и системы состояний и переходов. Наиболее популярны из таких моделей сейчас сети Петри.

• Ассоциативные системы. Элементы системы — активные данные, представляющие собой пары: значение, ключ. Пары, имеющие одинаковые ключи, соединяются и используются в качестве аргументов действия, закодированного ключом. Алгоритм действия может быть задан в любом стиле (например, в рамках стилей фон Неймановских вычислений), его результатом для системы является набор пар, порождаемых в ходе локального действия, а исходные аргументы при этом уничтожаются. Легко заметить, что ассоциативная система может рассматриваться как иная форма коммутационной системы, и с точки зрения возможностей, предоставляемых для программирования, они теоретически эквивалентны. Однако эта форма соответствует иному взгляду на описываемые вычисления, который лучше подходит, в частности, для работы с базами знаний6.

• Аксиоматические системы. Если система отождествлений и замен фиксирована для целых классов задач и предметных областей, то мы работаем в фиксированном классе исчислений, и на первый план выходят задача описания знаний и предпочтений на фиксированном языке.

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

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

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

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

поскольку он не является элементарной операцией). Программиста в такой системе обычно интересует не способ вывода, а лишь его осуществимость.

Не все из этих направлений представлены одинаково в экспериментальных разработках языков, экспертных систем и, тем более, оборудования. Например, в полном сооветствии с теоретическими результатами об окольных путях в доказательствах и парадоксом изобретателя (см. [63] или краткий очерк в Приложении А), прямая реализация аксиоматических систем, несмотря на их явную привлекательность, заведомо неалгоритмична, а потому в чистом виде они могут быть основой лишь для весьма узких классов описаний прикладных областей.