[ «ОСНОВАНИЯ ПРОГРАММИРОВАНИЯ УДК 519.682 Непейвода Н. Н., Скопин И. Н. Основания программирования Книга представляет собой первое издание в серии, предназначенной для студентов, готовящихся к работе по современным ...»
Н. Н. Непейвода, И. Н. Скопин
ОСНОВАНИЯ
ПРОГРАММИРОВАНИЯ
УДК 519.682
Непейвода Н. Н., Скопин И. Н.
Основания программирования
Книга представляет собой первое издание в серии, предназначенной для
студентов, готовящихся к работе по современным информационным технологиям, и специалистов в данной области.
Рекомендуется как для первокурсников, уже имеющих начальное знакомство с программированием, так и для специалистов, имеющих лишь практический опыт и желающих получить более основательные теоретические знания.
c Н. H. Непейвода, И. Н. Скопин, 2002 Разработка поддержана Фондом содействия развитию малых форм предприятий в научно-технической сфере (договор № 1296р/3029 от 27 апреля 2001г.).
Предисловие Данное учебное пособие предназначено в первую очередь для тех, кто пришел в вуз, уже имея понятие о программировании (либо изучал его в школе, либо был самоучкой) и намерен стать профессионалом в области информационных технологий. Такой студент часто имеет массу предрассудков, связанных с теми разрозненными и обрывочными сведениями и навыками, которые он успел накопить. Заложить прочную базу основных понятий и выработать умение ориентироваться в системе понятий программирования — основная цель пособия.
Это пособие доступно и для начинающего, если он параллельно изучает какой-то конкретный язык программирования.
В данном пособии мы старались следовать стратегии опережающего обучения, сформулированной В. В. Милашевичем [56]. Суть ее в том, чтобы максимально выявить высокоуровневые структуры, лежащие за изучаемыми конкретными понятиями, и тем самым обеспечить обучающемуся, обладающему достаточным интеллектуальным потенциалом, возможность быстро осваивать новые концепции, и, более того, до некоторой степени предугадывать возможное изменение концептуальной базы и работать с заделом на перспективу.
В данной книге одна из целей изложения состоит в том, чтобы показать читателю понятия программирования в их взаимосвязи и взаимозависимости. Отсюда, в частности, следует, что мы вынуждены многократно обращаться к одним и тем же понятиям, показывая их под разными углами зрения. Этим мы стремимся достичь понимания имеющейся на высшем уровне общности многих, по виду различных, методов и приемов деятельности программиста, а также показать понятия не в плоской картине их уже сложившихся взаимосвязей, а многомерно и многоаспектно, что позволяет осуществить переход на высшие слои сфер знаний и умений. В конечном итоге это, как проверено опытом, дает плоды: высокую квалификацию обучаемоi ii го, умение быстро творчески осваивать новые системы понятий и находить новые эффективные решения.
Эту книгу правильнее всего хоть один раз прочитать с начала и до конца подряд. Тогда Вы сможете наиболее четко выстроить систему понятий. Некоторые фрагменты изложения могут показаться сведущему читателю слишком простыми, другие — сложны для новичка. Тем не менее, мы советуем не пропускать материал, возможно, уделяя меньше времени простым вопросам, а к не до конца понятому — обращаясь повторно, когда накопится необходимый опыт. Конечно же, она приспособлена и к фрагментарному чтению, но в этом случае следует контролировать однозначность понимания тех положений, которые определяются ранее1. Отчасти этому помогут приложения и глоссарий в конце текста. При чтении полезно не только знакомиться с приводимыми программами, но и пытаться выполнять их на своем компьютере.
При этом полезно не буквальное повторение написанного, а вариации на заданную тему. Так, если у вас получится более эффективная программа, постарайтесь понять, почему авторы предпочитают свой вариант; если под рукой нет системы программирования, на языке которой представлен пример, постарайтесь перевести его в привычную для вас обстановку, по возможности сохраняя идеи моделируемой программы.
Пособие не затрагивает тренинга, на котором отрабатываются типовые приемы программирования и методы их применения. Место таким занятиям в разделах курсов, посвященным конкретным языкам программирования и алгоритмике как таковой, менее связанной с программированием на языках.
По конкретным языкам есть множество отличных пособий, по алгоритмике можно рекомендовать книгу [42], соответствующую по уровню изложения данному курсу и отлично сочетающуюся с ним по материалу. Отчасти мы неизбежно затрагиваем и эти две темы. Отличие нашего изложения в следующем.
• Языковые аспекты. Подчеркиваются существенные черты, анализируются с показом достоинств, недостатков и существенных особенностей их различные реализации; порою полностью игнорируются случайные детали конкретных (хотя бы и самых распространенных) реализаций;
если какие-то интересные аспекты были отброшены из-за неудачной реализации либо еще не реализованы как следует, они все равно анализируются.
Не стоит пытаться переносить на эту книгу опыт чтения энциклопедий, поскольку при нынешнем понимании этого слова они представляют из себя базу данных, а не базу знаний.
iii • Алгоритмические аспекты. Мы сосредоточиваемся на том, как потребности алгоритмики влияют на развитие соответствующих стилей программирования, а через них — на языковые средства.
Иными словами, как конкретные языки, так и алгоритмы служат для предлагаемого учебника в первую очередь иллюстративным материалом.
Внимание!
При описании языков мы не всегда следуем традиционно принятой для конкретного языка терминологии, поскольку слишком часто по существу одна и та же вещь называется в разных языках совершенно по-разному. Мы стремимся выбрать наиболее адекватный и выразительный из принятых частных терминов, а если все они подчеркивают несущественные особенности, иногда вынуждены вводить свой.
Еще одна особенность данного изложения. Любое конкретное положение и конкретное решение считается неуниверсальным, и поэтому освещаются его существующие либо потенциальные альтернативы. Таким образом, здесь показываются на практике инструменты многоуровневого критического мышления (не путать с одноуровневым, когда некая позиция идолизируется и все критикуется с точки зрения выбранного «Священного писания»!) В учебнике представлен ряд заданий для контроля усвоения материала.
Эти задания не являются задачами с одним-единственным правильным ответом (засилье таких задач и являющейся дальнейшим логическим шагом за ними системы тестов — один из инструментов блокировки критического мышления). Мы считаем, что гораздо перспективнее разбудить мысль читателя, чем давать готовые рецепты и оценивать следование им. Ход рассуждений при решении задачи представляется более полезным, чем получаемые результаты: умную и интересную ошибку порою стоит в процессе обучения оценивать выше, чем лобовое решение.
Базовые понятия Базовый характер данной части книги вовсе не означает ее элементарности. В частности, в ней вводятся важнейшие для всего дальнейшего изложения и для методологии деятельности в информатике понятия стиля программы и ее жизненного цикла, а также такие технические понятия, которые отнюдь нельзя считать общеизвестными: вычислительная обстановка, абстрактный синтаксис, контекст фрагмента программы и др.
Глава Введение в систему понятий программирования Назначение данной главы — ввести обучающегося в систему понятий программирования. Коллекция понятий превращается в систему тогда, когда она становится знанием. Знание предполагает прежде всего умение преобразовывать и сочетать различные элементы. Поэтому здесь мы сосредоточиваемся на рассмотрении соотношений понятий и различных форм их представления, чтобы увидеть структуру взаимосвязей понятий и тем самым сделать шаг к освоению их системы. Практическая цель обучающегося — научиться даже без предварительного изучения языка видеть в нем общие конструкции и, соответственно, понимать программы, написанные на нем.
ЯЗЫКИ И СИСТЕМЫ ПРОГРАММИРОВАНИЯ
§ 1.1.1.1.1. Сравнение программ на разных языках Начнем с рассмотрения нескольких примеров. Всем данным текстам программ при исполнении соответствует действие, состоящее в распечатке строки «Hello World!».
Программа 1.1. /*Язык C.*/ #include int main(void) {printf("Hello World!");
return 0;} Программа 1.1. //Java public class HelloWorld { public static void main (String[] args) { System.out.println("Hello World!");
Программа 1.1. (*Паскаль*) program First (Output);
begin writeln(’Hello World!’) end.
Программа 1.1. comment Algol 68 comment begin println(‘Hello World!’) end коммент Русский Алгол 68 коммент начало печатать(‘Hello World!’) конец comment Еще два представления comment (println(‘Hello World!’)) (печатать(‘Hello World!’)) Программа 1.1. Лисп:
( PRINT “Hello World!”) Программа 1.1. Рефал $ENTRY GO{=};
Программа 1.1. Prolog :-Print(’Hello World!’);
Сравним все эти программы. Что у них является общим?
1. Все они представлены в виде текстов: последовательностей символов, размещенных на нескольких строчках.
2. В каждом языке имеется понятие строки (последовательности символов нефиксированной длины). Строки оформляются во всех языках примерно одинаково: с использованием кавычек как обрамляющих символов. Правда, вид конкретных кавычек меняется от языка к языку.
3. Каждая из этих программ имеет конструкцию, выполнение которой приводит к распечатыванию строки.
4. Все они при их выполнении делают одно и то же: печатают строку В чем же их отличия? Видны некоторые различия в записи, а также в правилах построения. Таким образом, напрашивается вывод, что, освоив один язык программирования, можно понимать тексты программ на большинстве других языков практически так же легко, как образованный русский человек может читать украинский либо, в крайнем случае, польский (это чуть труднее) текст. Казалось бы, что все эти программы, естественно, после преобразования каждого текста в исполняемый код, приводят к одной и той же машинной программе, исполняемой компьютером. Как мы дальше увидим, это не так.
Конечно же, и здесь могут быть исключения, но это верно практически для всех т. н.
языков высокого уровня 1.1.2. Язык, его реализация и среда программирования Начнем с анализа понятия программы. Существуют различные взгляды на то, что такое программа. Например:
1. Запись алгоритма в виде, однозначно понятном для человека.
2. Последовательность символов из заданного (конечного) множества символов V, построенная в соответствии с определенными правилами (формально это записывается L V, где L — множество правильно построенных выражений, которое в данном контексте называется языком, а V — множество всех возможных последовательностей символов).
3. Последовательность команд некоторого абстрактного вычислителя, который специально определен для данного языка. То есть сам текст программы может рассматриваться как изображение команд этого вычислителя.
4. Текст, который может быть преобразован в исполнимый код на машинном языке.
Мы видим, что программа должна удовлетворять следующим требованиям:
1. Должна быть однозначно понятна для человека.
2. Должна удовлетворять точно определенным правилам построения (называемым формальным синтаксисом языка).
3. Должна быть понятна для исполнителя (абстрактного или конкретного вычислителя), что может достигаться различными средствами.
Понятия исполнитель и вычислитель в данном тексте (точно так же, как и в абсолютном большинстве работ по информатике) понимаются как синонимы.
Минимальная осмысленная для исполнителя последовательность символов называется лексемой. Например, в языке С "Ник — не лексема, поскольку такая последовательность символов не осмыслена, а "Ник" — уже лексема.
Заметим, что понятие лексемы зависит от контекста. В операторе x=x1; символ x лексемой является только в первом своем вхождении, но не во втором, где он всего лишь часть лексемы x1.
Минимальная последовательность лексем, которая способна вызывать действия вычислителя, называется конструкцией языка. Во многих языках программирования среди конструкций языка выделяются так называемые операторы, обозначающие законченные действия. Понятие оператора характерно для т. н. операционных языков, к числу которых относятся языки FORTRAN, ALGOL 60, Алгол 68, C/C++/C#, Pascal, Object Pascal, Ada, Modula-2. Только что перечисленные языки имеют, помимо общей основы, целый ряд общих второстепенных признаков, которые делают их настолько же близкими, насколько близки естественные языки одной и той же группы (например, славянские), и очень многие замечания можно высказать сразу для всех данных языков. Поэтому перечисленные выше языки в данной книге будут называться языками традиционного типа или просто традиционными языками. Пример 1.1.1. В языках традиционного типа переменная x является конструкцией, поскольку она может вызвать действия чтения ее значения либо записи значения в нее. Вызов функции sin(x) означает вычисление соответствующего значения имеющейся в системе программирования реализации математической функции sin. Этот вызов оператором не является, а вот присваивание y=sin(x); или y:=sin(x); или Y=SIN(X) или y:=sin(x) уже оператор.
Конец примера 1.1.1.
Имея в виду операторы, осмысленно говорить и о порядке действий вычислителя, и о его соответствии или несоответствии порядку следования операторов-конструкций в тексте программы; о том, какие команды конкретного вычислителя выполняются при исполнении оператора как команды абстрактного вычислителя.
Определение 1.1.2. Реализация языка — это комплект программ, которым обеспечиваются:
Конечно же, это не формальные определения, а указания на то, что в языке программирования, как и в естественном языке, выделены структурные составляющие, за которыми закрепляется их смысл.
Не все операционные языки мы относим к языкам традиционного типа. В частности, язык Java является операционным, но из-за некоторых принципиальных отличий данного языка и языков, перечисленных выше, мы его к традиционным языкам не относим.
— Поддержка операций с исходной программой: ввод, редактирование и сохранение текста, анализ синтаксических ошибок.
— Подготовка синтаксически правильной программы к исполнению на конкретном вычислителе.
— Поддержка на конкретном вычислителе всех возможных действий абстрактного вычислителя.
Кроме того, в комплект реализации языка могут включаться другие программы, удовлетворяющие требованиям, логически связанным с вышеперечисленными.
Конец определения 1.1.2.
Реализация языка неразрывно связана с окружающей ее операционной средой, т. е. с базовыми средствами, доступными при работе на данном компьютере в данной системе. Вместе они составляют систему программирования для данного языка. Система программирования обязательно включает следующие компоненты:
1. Файловая система для хранения текстов программ — как правило, это общая часть программного обеспечения для различных систем на данном компьютере.
2. Редактор для ввода текста программы как последовательности символов и исправления ее (редактирование). Возможно как использование редактора, специализированного для составления программ на данном языке, так и универсального, предназначенного для набора различных 3. Транслятор для преобразования текста программы к виду, в котором она может исполняться, и указания ошибок, если преобразование не удается. Транслятор — это не обязательно одна программа.
4. Библиотеки периода трансляции, которые используются в процессе преобразования программного текста, например, для включения в него стандартизованных фрагментов (чтобы программисту не нужно было их повторять в своих программных текстах).
5. Библиотеки периода исполнения, которые содержат программы стандартных действий абстрактного вычислителя (стандартная библиотека, иногда называемая библиотекой поддержки языка). Они связывают язык с операционной средой.
6. Отладчик — программа, позволяющая отслеживать ход вычислений программ на данном языке.
Кроме перечисленного, системы программирования обычно включают в себя еще:
7. Пользовательские библиотеки, которые содержат программы на данном языке (в текстовом или преобразованном виде), используемые в составляемых программах для задания специальных вычислений (зависят от среды программирования);
8. Средства поддержки разработки программ — разнообразные инструментальные программы, которые применяются в процессе проектирования, составления и отладки программ.
Из перечисленного выше видно, что конкретная реализация языка обычно привязывается к операционной среде и, соответственно, к конкретному вычислителю. Теперь разберем по очереди, как подготавливается к исполнению и исполняется каждый из текстов программ, рассмотренных в предыдущем параграфе.
Пояснение к программе 1.1.1.
/*Язык C:*/ #include int main(void) {printf("Hello World!");
return 0;} В принципе это не исключает переносимости (т. е. возможности исполнять программу без всяких изменений в разных вычислительных обстановках), и уже были эксперименты по созданию переносимых систем программирования.
отражает то, что написанный текст программы должен быть расширен путем вставки вместо этой строки текста, именуемого stdio.h, и уже такой расширенный текст подается транслятору. одно из правил формирования текстов программ на языке С). Таким образом, stdio.h является библиотекой периода трансляции. Фактически stdio.h содержит все то, что нужно для организации ввода и вывода данных, описывая компоненты библиотеки периода исполнения.
Текст после #include — это описание функции без параметров, вырабатывающей целое (ее заголовок — int main (void)), которая печатает строку:
После обработки этого текста транслятором, в частности, подключается биprintf ("Hello World!");.
блиотечная функция периода исполнения printf, описание которой взято из Пояснение к программе 1.1.2.
stdio.h.
// Java:
public class HelloWorld { public static void main (String[] args) { System.out.println("Hello World!");
Строка в тексте на языке Java указывает на то, что программа является публичным (доступным всем) классом, поименованным как HelloWorld. К этому классу можно будет обращаться для исполнения содержащихся в нем действий.
Внутри класса HelloWorld определяется функция static void main, с которой начинаются вычисления. А внутри нее происходит обращение к системным средствам вывода строк, содержащимся в классе System.out:
Это обращение делается из объявляемой функции main.
Пояснение к программе 1.1.3.
(* Pascal:*) program First (Output);
begin writeln(’Hello World!’) end.
(*PASCAL*) PROGRAM FIRST (OUTPUT);
BEGIN WRITELN(’Hello World!’) END.
Последние два текста на стандартном5 языке Pascal — даже с точки зрения синтаксиса одна и та же программа. Из этого видно, что в языке не различаются заглавные и строчные буквы. Эта особенность восходит к использованию древних печатающих устройств, для которых не было такого различия.
Возможность печатать что-либо для языка Pascal обусловлена указанием Output в заголовке программы, который подключает соответствующую библиотеку периода исполнения и инициализирует ее.
Пояснение к программе 1.1.4.
Алгол 68:
begin println(‘Hello World!’) end comment Русский Алгол 68 comment начало печатать(‘Hello World!’) конец comment Еще два представления comment (println(‘Hello World!’)) Мы специально не воспользовались здесь расширениями, предоставляемыми, например, Delphi, чтобы четко видеть разницу между эталонным, или стандартным языком, и его диалектами. Диалекты существуют лишь в контексте данной машины и транслятора.
(печатать(‘Hello World!’)) Алгол 68 демонстрирует четыре текста одной и той же программы. В языке предусмотрены и варианты нотации для национальных алфавитов (сравните первый и второй тексты), и возможности скорописи (сравните первый и третий тексты).
Для этого языка постулируется существования стандартного вступления и заключения, которые окружают написанный текст. Считается, что исходным текстом для трансляции является то, что получится в результате соединения текстов вступления, текста, написанного программистом, и текста заключения. Здесь прослеживается аналогия с #include языка С, но название файла, который должен расширять написанный текст, явно не задается.
Пояснение к программе 1.1.5.
Программа на языке Lisp представляет собой функцию PRINT с аргументом ( PRINT "Hello World!") "Hello World!". Вычисление этой функции — так называемое S-выражение, представляющее аргумент самой функции. В данном случае это "Hello World!".
При вычислении PRINT происходит побочный эффект, т. е. действие, которое сопровождает получение значения. В данном случае это печать аргумента функции, т. е. требуемое действие. Приведенная программа распечатает строку дважды: в первый раз, когда выполняется указанный побочный эффект, а во второй — из-за следующей причины. Лисп-программа всегда завершает свои вычисления распечаткой значения функции, полученного в качестве результата. S-выражение "Hello World!" и есть тот самый результат.
Пояснение к программе 1.1.6.
Программа на Рефале представляет из себя функцию Go. Эта функция раENTRY GO{=};
ботает с полем зрения, которое уже не может быть прямо представлено как совокупность ячеек вычислителя. Она проверяет, что поле зрения пусто, и подставляет вместо пустого выражения то, что идет справа от знака равенства: вызов стандартной функции, печатающей строку и опять очищающей поле зрения. Поскольку в поле зрения функций больше не осталось, программа заканчивает работу, а поскольку поле зрения пусто, больше ничего не печатается.
Пояснение к программе 1.1.7.
:-Print(’Hello World!’);
Программа на языке Prolog представляет собой цель, которая должна быть достигнута. В типичной ситуации описываются еще и данные, необходимые для достижения цели, в нашем простейшем случае таких данных не нужно. Вызывается стандартная функция, которая печатает строку и исчезает.
Поскольку не недостигнутых целей более не остается, программа завершает работу. Prolog так же, как Рефал, имеет дело сразу со сложными данными и так же не имеет прямой связи с физическим строением машинной памяти.
Теперь мы видим, что действия, предписываемые языком, совершенно по-разному достигают одних и тех же целей. С чем это связано? Ответ в том, что каждый язык определяет свою модель вычислений. Иногда эти модели довольно близки, несмотря на существенные различия в изобразительных средствах языков. Для таких языков программист по существу пишет одно и то же, и функции систем программирования весьма близки. Различия в оформлении связаны, например, с тем, как соотносится программа с ее окружением и как задаются общие для всех программ действия. Именно поэтому мы внесли наиболее распространенные из языков, имеющих близкие модели вычислений, в список традиционных языков.
Существенные различия моделей вычислений возникают в случае разного устройства данных, с которыми работают программы (сравните, например, C и Рефал). Но стоит помнить, что одна и та же модель вычислений на разных вычислительных машинах и в разных операционных средах реализуется по-разному. Могут быть различны разрядные сетки, способы представления чисел, способы вызова процедур. Явно позаботились об учете операционной среды, чтобы обеспечить переносимость программного обеспечения, пожалуй, лишь в языке Ada, являющемся стандартом для Министерства Обороны США.
В свою очередь, операционная среда оказывает обратное влияние на языки, и сформировались следующие понятия, их связывающие.
Определение 1.1.3.
Эталонный (стандартный) язык программирования — язык, задаваемый безотносительно операционной среды и без привлечения знания об устройстве конкретного вычислителя (компьютера). Именно эталонным языком фиксируется абстрактный вычислитель для данного языка.
Стандартные библиотеки, или стандартное библиотечное расширение языка — комплект библиотечных средств, которые стандарт языка предписывает для всех его реализаций.
Прагматические расширения языка — конструкции, предписывающие изменение поведения абстрактного вычислителя с теми или иными целями, например, для ускорения выполнения программы. Различаются эталонные прагматические расширения, задаваемые в его стандартном описании (руководстве), и конкретные прагматические расширения, появляющиеся в связи с реализацией языка на данном вычислительном оборудовании, в данной операционной системе.
Библиотеки конкретной системы программирования — комплект библиотечных средств, которые реализованы в данной среде программирования (при правильной реализации они включают в себя стандартные библиотеки).
Конкретный, или реализованный язык — диалект стандартного языка вместе с его конкретной реализацией на данной вычислительной машине.
Конец определения 1.1.3.
К сожалению, иногда в описаниях языков, а в особенности в руководствах для программиста сведения о разных аспектах языка и системы перемешаны, и в результате трудно оценивать предлагаемые средства, сравнивать возможности различных языков.
Применительно к языку С, необходимыми и достаточными составляющими реализации являются:
1. Препроцессор — программа, подготавливающая текст к обработке. Текст, предъявляемый системе программирования, может, строго говоря, являться лишь заготовкой программы на этом языке. Он может содержать ряд обозначений, которые должны быть раскрыты, прежде чем будут исполнены вычислителем, включать в себя прямые указания на необходимость расширения путем вставки других текстов. Все это ставит задачу подготовки текста перед тем, как программа будет транслироваться, решение которой возлагается на препроцессор. Некоторые фрагменты, расширяющие строгий язык, вводятся в качестве скорописи или для наглядности. В частности, с помощью таких вставок задаются указания стандартных библиотек, используемых программистом. Для языка С правила задания текстовых обозначений стандартизованы, и все препроцессоры этого языка должны оперировать с ними одинаково.
2. Компилятор — программа, переводящая (транслирующая) текст программы в машинный код, который затем по отдельному указанию может быть исполнен. В результате компиляции строится так называемый загрузочный модуль. Альтернативой компилятору является интерпретатор — программа, которая одновременно и анализирует, и исполМОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ няет текст. Для реализации языка С обычен компилятор, транслирующий подготовленный препроцессором текст, и в результате получается загрузочный модуль.
3. Редактор связей — специальная программа, обеспечивающая возможность работы загрузочного модуля совместно с другими программами данной операционной среды. В ряде случаев (например, в ОС UNIX) редактор связей не требуется, поскольку решение соответствующих задач возлагается на операционную систему.
4. Стандартная библиотека, которая объединяет в себе библиотеки периода трансляции (статические библиотеки) и периода исполнения (динамические библиотеки).
5. Отладчик — программа, обеспечивающая отслеживание хода вычислений путем пошагового исполнения исходной программы в режиме диалога. Обычной для С и для большинства других систем программирования является организация отладки, которая связывает шаг исполнения со строкой исходного текста.
МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ
§ 1.2.Из материалов предыдущего раздела видно, что подходы к решению программистских задач при использовании различных языков отличаются друг от друга. Иногда эти различия значительны, иногда сводятся лишь к текстовому представлению программы, а потому их можно считать непринципиальными. Если различия считаются непринципиальными, то мы говорим о том, что языки имеют сходную модель вычислений.
В дальнейшем мы часто будем пользоваться термином “традиционные языки”, понимая под этим языки, модель вычислений которых унаследована от так называемой архитектуры фон Неймановского типа, принятой в подавляющем большинстве существовавших и существующих вычислительных машин. Эта архитектура характеризуется следующими принципами:
1. Наличие трех элементов вычислительной системы:
(a) память, которая предназначена для хранения произвольных значений. Значения на аппаратном уровне представляются как последовательности битов;
(b) процессор, который способен выполнять команды, т. е. интерпретировать последовательности битов как инструкции для активизации предписываемых этими инструкциями действий;
(c) управляющее устройство, способное указывать команды, которые должен выполнять процессор (иногда управляющее устройство рассматривается как составная часть процессора).
2. Однородность памяти и адресация. Память машины рассматривается как вектор, состоящий из одинаковых ячеек, способных принимать (от процессора) любые значения. Значение в ячейке с точки зрения процессора является последовательностью битов фиксированной длины без каких бы то ни было ограничений. Ячейки памяти идентифицируются адресами: числами от нуля до максимально возможной для данной машины величины (обозначающей последнюю ячейку), Адреса служат указателями для процессора, откуда следует извлекать значение или куда помещать значение.
Из однородности памяти следует, что команды и данные (перерабатываемые значения) располагаются в единой общей памяти и одинаково 3. Пассивность памяти и активность процессора. Ячейка памяти всегда содержит какое-то значение. Полученное ячейкой значение не может быть изменено иначе как при выполнении специальной команды процессора, предназначенной для этого действия, — команды засылки, или присваивания значения. Изменяемая ячейка указывается своим Процессор всегда выполняет некоторую команду, закодированную последовательностью битов в ячейке и извлеченную из памяти. Команды могут иметь операнды, т. е. в них, как правило, указываются адреса ячеек, над которыми выполняются предписываемые действия. Именно процессор в соответствии с тем, какую команду он должен выполнить, интерпретирует значение ячейки-операнда как число, символ, адрес в памяти и др. Число операндов команды называется ее адресностью, а адресность большинства команд — адресностью машины. Различаются одно-, двух- (и в настоящее время реже) трехадресные машины и машины с нефиксированной адресностью.
4. Роль устройства управления. Управляющее устройство содержит адрес 1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И
ТРАДИЦИОННЫЕ ЯЗЫКИ
5. Наличие канала связи между памятью и процессором. Для передачи данных или команд между памятью и процессором, предписываемой какой-либо командой, используется специальное оборудование, называемое каналом связи. Работа канала осуществляется в следующих случаях:
(a) когда требуется подать для выполнения процессором очередную команду (активизируется управляющим устройством), (b) когда для выполнения команды процессору требуется получить операнд (активизируется процессором), (c) когда при выполнении команды требуется изменение значения ячейки (активизируется процессором).
Конкретная схема канонической фон Неймановской машины дополняется устройствами ввода и вывода данных, активизация которых осуществляется при выполнении соответствующих команд процессором (возможны различные варианты взаимодействия таких устройств с остальным оборудованием:
связь с памятью автономная, через процессор или через специальную шину данных и др.).
На рис. 1.1 показано взаимодействие частей фон Неймановской вычислительной машины. Сплошными стрелками отмечена передача информации по каналу (двунаправленные стрелки — передача в оба направления). Пунктирные стрелки обозначают действия с управляющим устройством, которые осуществляются в связи с исполнением команды К О1 О2, размещенной в памяти по адресу 3: непосредственно до нее (запрос управляющего устройства кода команды по адресу 3) и после нее (указание на необходимость запроса команды, следующей в памяти за исполняемой).
Рис. 1.1. Схема выполнения двухадресной команды на фон Неймановской машине Классическая схема сформировалась под давлением требования минимизировать части системы, критичные к сбоям оборудования, поскольку существовавшая в середине XX века техническая база не позволяла решать задачу надежности в должной мере. В результате только процессор можно назвать активным устройством машины. По этой же причине выбран довольно примитивный способ управления: переход к следующей команде или к команде
1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ
по принудительно задаваемому адресу. К тому же неразвитость отрасли в целом не позволяла даже ставить задачу повышения эффективности вычислений за счет выбора подходящей модели вычислений.По мере накопления опыта работы с вычислительными машинами появилась потребность увеличения быстродействия процессора и объемов памяти.
И очень скоро выяснилось, что каноническая схема фон-неймановских вычислений препятствует повышению производительности. По этой причине сегодня эта схема всегда модифицируется. Ниже приведены некоторые, но довольно характерные модификации схемы:
a) У процессора появляются собственные ячейки со специальной адресацией, не требующие обращения к памяти. С их помощью можно уменьшать адресность команд машины, передавать промежуточные результаты вычислений от команды к команде, выполнять иные локальные действия.
Они называются быстрыми регистрами процессора.
b) Уменьшается размер команд, в частности, их адресность. Наиболее употребляемые действия кодируются короткими последовательностями битов, отдается предпочтение одноадресным командам (это возможно благодаря регистрам процессора).
c) Команды кодируют довольно сложные действия над операндами, которые объединяют наиболее часто употребляемые последовательности элементарных операций.
d) Процессор снабжается памятью для команд, которые вероятно будут выполняться после текущей команды (эта память, называемая кэшем команд, заполняется в параллель с выполнением команды), а также для данных, в которой дублируются значения основной памяти с целью обеспечить следующие команды операндами (кэш данных).
e) Память разбивается по уровням доступа: регистры процессора, область быстрого доступа с непосредственной адресацией, область, адресация которой требует предварительного указания некоторого сегмента, ячейки которого адресуются непосредственно, и т. д. Другой вариант той же идеи — возможность переключения с сегмента на сегмент с сохранением более медленного доступа к ячейкам вне текущего сегмента.
Полезность подобных модификаций очевидна. Однако есть причина, из-за которой возможности роста эффективности фон Неймановских вычислений, пусть даже трансформированных в указанных отношениях, ограничены. Повышение быстродействия процессора как активного элемента оборудования приводит к росту скорости счета лишь в тех пределах, которые определены скоростью канала связи между процессором и памятью: если она невысока, то процессор будет все равно простаивать, ожидая очередной команды, операндов или окончания выполнения присваивания6. В свою очередь, рост скорости канала связи ограничен из-за постоянно растущей потребности расширения объема памяти. На эти принципиально непреодолимые ограничения классической модели вычислений указал Бэкус еще в середине семидесятых годов, назвав канал связи памяти с процессором узким местом (буквально bottleneck) модели фон Неймана. Уместно заметить, что многопроцессорность, а тем более кэширование и прочие модификации канонической модели являются лишь полумерами, позволяющими расширить, но никак не ликвидировать узкое место (впервые это было отмечено в лекции Бэкуса [82]).
В качестве альтернативы фон Неймановской модели укажем лишь на одну из идей радикально новой модели, реализация которой позволяет значительно обогатить возможности параллельного счета. Для достижения параллельности действий увеличивается активность элементов вычислительной системы и изменяются принципы управления вычислениями.
Идея заключается в том, чтобы разрешить выполнение всех команд, для которых к данному моменту готовы операнды (вычислены их значения). Централизованное управление ликвидируется и появляется возможность глубокого распараллеливания вычислений, если оборудование обеспечит фактически одновременное выполнение готовых команд. Прямое развитие данной идеи наталкивается на массу тонких вопросов синхронизации. Простейший и наиболее очевидный из конфликтов синхронизации — попытка одновременной записи результатов нескольких команд в одну ячейку памяти. Поэтому присваивания становятся тормозом на пути программирования. Более того, можно теоретически предвидеть (хотя точной оценки еще не было сделано; впрочем, даже там, где такие оценки имеются, они игнорируются и замалчиваются), что распараллеливание программ, написанных в традиционном стиле — мартышкин труд7. Стиль программирования можно корректировать Иллюстрацией интенсивности работы канала фон Неймановской машины может служить схема выполнения команды на рис. 1.1, которая показывает, что для выполнения двухадресной команды К О1 О2 требуется шесть обращений к каналу.
И. Н. Скопин. Я считаю этот эпитет слишком сильным, но соавтор не согласился смягМОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ различными способами, например, путем замены хранения результата передачей его в качестве операндов ранее заблокированным командам, которые тем самым активизируются. Какие элементы оборудования будут выполнять такие команды, на уровне идеи не имеет значения — это задача техническая (т. н. задача динамической коммутации).
Здесь стоит обратить внимание на два взаимосвязанных момента. Во-первых, часто нет нужды в хранении промежуточных результатов счета, и, как следствие, потребность в пассивной памяти существенно снижается. Во-вторых, ликвидируется примитивное устройство управления, а его роль принимают на себя элементы оборудования, отвечающие за выяснение готовности команд к выполнению. Это — одна из схем, которая подчиняет управление потокам данных (data ow). Такие схемы противопоставляются управляющим потокам (control ow) фон Неймановских вычислений.
Представленная идея неоднократно воплощалась в оборудовании (т. н.
машины потоков данных). Но каждый раз узким местом для таких машин оказывалось несоответствие стиля программ, требуемых для них, тем стилям, к которым привыкли программисты. Как следствие, в каждом из таких процессоров делались грубые системные ошибки, приводившие к затруднениям в программировании, а также к понижению скорости и гибкости вычислений. Тем не менее, поскольку скорость света очень скоро поставит предел механическому увеличению пропускной способности каналов, к подобным схемам придется вернуться на другом уровне.
Одной из сторон машин потоков данных является повышение активности памяти, в которой размещаются команды и их операнды. По этому пути можно пойти еще дальше, сделав всю память активной. В этом случае, во избежание полной анархии, обычно память имеет общее устройство управления, задающее одну команду (или несколько команд, в зависимости от какого-то очень быстро проверяемого условия), которую выполняют все ячейки (ассоциативная память). История реализации этой идеи аналогична истории машин потоков данных: аппаратные предпосылки есть, но эффективных способов программирования нет.
История с ассоциативной памятью и машинами потоков данных показывает, что, несмотря на очевидные преимущества для отдельных классов задач других моделей вычислений и на очевидную неэффективность классической модели вычислений, не происходит переход к другим более перспективным с точки зрения ускорения счета моделям. Почему? Это очень непростой вочить его.
прос, связанный как со сложившимися традициями, так и с огромным грузом накопленного программного обеспечения. В частности, другие модели вычислений очевидно неуниверсальны, ориентированы на некоторые классы задач, а иллюзия универсальности, основанная на примитивно истолкованной теореме об универсальном алгоритме, сопутствует традиционной модели вычислений. Но, пожалуй, более всего консерватизм обусловлен тем, что сегодняшняя армия программистов воспитана на фон Неймановской модели, и она уже не в состоянии перестроиться. Одна из причин тому — так называемые традиционные языки, ключевые средства которых “выросли” из модели фон Неймана. Эти языки стали основой для выработки наиболее употребляемых стилей программирования8. Ниже перечислены особенности языков, которые унаследованы от фон Неймановской модели вычислений:
a) Присваивание значений. Языковая конструкция, предназначенная для локального запоминания результата вычислений, получившее название оператора присваивания значения переменной, или засылки значения, — прямой потомок передачи значения по каналу связи от процессора к памяти.
В большинстве языков программирования понятие переменной практически всегда рассматривается как аналог ячейки (или группы ячеек) памяти.
b) Операторы. Основной конструкцией действия в языке является оператор. Выполнение одного оператора зависит от выполнения другого только в том смысле, что более ранние вычисления могут менять память (содержимое некоторых ячеек), в контексте которой выполняются последующие операторы. Иными словами, зависимость операторов посредством использования памяти в точности соответствует тому, что имеет место для команд фон Неймановской машины.
c) Структура управления. Последовательное выполнение операторов, текстуально следующих друг за другом, совершенно аналогично последовательному выполнению команд процессором. Оператор перехода, т. е.
принудительное указание того оператора, который должен выполняться следующим, ничем не отличается от машинной команды безусловной передачи управления по адресу. То же можно сказать и о ситуациях, когда В последующих разделах мы уделим особое внимание вопросам, связанным со стилями программирования. Здесь же следует отметь, что универсального стиля программирования не существует, и действительно квалифицированный программист не будет ограничивать себя использованием какого бы то ни было, но одного стиля, он всегда стремится применять средства, которые соответствуют решаемой задаче в максимальной степени.
1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ
вычисления определяют, какой оператор будет выполняться следующим.Способы указания групп операторов, выполнение или невыполнение которых зависит от некоторого условия (выражения, значения которого выделяют соответствующие им группы), всего лишь фиксируют в языке типовые приемы разветвления вычислений. Эти приемы есть образы наиболее часто используемых ситуаций при программировании на языке команд.
d) Приведения. В традиционных языках обычным является употребление значения одного типа, которое присваивается переменной другого типа. Это не только присваивание целого вещественной переменной, когда существует “разумная” интерпретация целого как округленного вещественного, или подобное преобразование в выражениях, но и неоднозначно трактуемые преобразования, смысл которых нельзя понять в отрыве от конкретной программы. Автоматические приведения значений к типам, определяемым контекстом использования, — прямое следствие соглашения об однородности памяти. И хотя в развитых языках программирования можно заметить стремление избегать неконтролируемых приведений, сам факт их осуществимости считается чуть ли не достоинством языка.
e) Подпрограммы. Возможность объявлять некоторые последовательности операторов отдельно от тех мест программы, в которых их требуется выполнять, обозначать такие последовательности именами с тем, чтобы указывать эти имена в местах требуемого выполнения, — обычный прием группировки команд в подпрограммах на машинных языках. Единственная разница здесь в том, что языки программирования более выразительны, что они (до известных пределов) позволяют абстрагироваться от того, какие стандартизованные последовательности команд используются для оформления подпрограммы и ее вызова для исполнения.
Если в архитектурах вычислительных машин отходят от принципов фон Неймана преимущественно для повышения эффективности счета, то побудительных причин для нарушения канона при конструировании языков программирования гораздо больше. Это и стремление к большей выразительности, и уже упомянутая фиксация типовых приемов программирования, и помощь в отыскании ошибок в программах. Наиболее часто нарушается принцип однородности памяти, отход от которого дает возможность содержательной трактовки хранимых данных, что, в свою очередь, способствует и выразительноГЛАВА 1. ПОНЯТИЯ сти, и надежности программ9.
Для большинства существующих языков характерно, что программист может (и должен!) думать о выполнении программы как о работе автомата, имеющего активный процессор и пассивную память (возможно, разнородную), связанные каналом. Появление в языке структуры памяти и так называемых высокоуровневых конструкций, а также возможности использования библиотек — это всего лишь повышение уровня абстрактного вычислителя языка, который, тем не менее, трактуется как автомат фон Неймановского типа, пусть даже с весьма сложными командами. Если язык предусматривает возможность отхода программиста от фон Неймановского образа мышления, то мы называем этот язык нетрадиционным. С этой точки зрения такие современные языки, как С++ или Ada, остаются традиционными, а, к примеру, такой “патриарх языкотворчества”, как LISP — нетрадиционен.
Данное разграничение традиционных и нетрадиционных языков нельзя рассматривать в качестве точного определения. Достаточно развитый язык позволяет выражать алгоритмы в разных стилях, и программист может себе позволить строить тексты программ (фрагментов программ) в соответствии с особенностями решаемой задачи, отходя от тех правил, которые поддерживаются явно языком. Но если в языке не хватает возможностей, адекватных для такого построения, а это, вообще говоря, обычная ситуация, то приходится прибегать к моделированию нужных возможностей подручными средствами.
Когда при этом требуется забота об эффективности, а это опять-таки обычно, необходимо учитывать реалии конкретного компьютера. Как следствие, весьма вероятны нарушение адекватности моделирования и потеря наглядности решения.
В заключение настоящего раздела приведем перечень (далеко не полный!) языков, которые мы относим к классу традиционных, сопровождая его небольшими комментариями.
1. FORTRAN. Самый почтенный долгожитель среди языков программиКак уже отмечалось, отклонение от принципа однородности памяти для повышения эффективности используется и в оборудовании. Сегментация, быстрые регистры, кэширование — далеко не единственные решения этого плана. Нарушение принципа здесь лишь частичное: ячейка любого из видов по-прежнему способна принимать значения разного типа, по-прежнему смысл значения раскрывается только процессором. Заслуживают упоминания и более радикальные архитектуры, предусматривающие тегирование (см. стр. 62), а также полное отделение в памяти областей, в которые можно записывать данные и команды (в обычном режиме выполнения программ процессору не разрешается записывать что-либо в область команд, в результате повышается надежность программ).
1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ
рования, постепенно вбирающий в себя новые веяния из области языкотворчества, но сохраняющий преемственность. FORTRAN сегодня — это эклектическое собрание полезных и архаичных средств. Упоминая FORTRAN в дальнейшем, мы чаще всего говорим о языке, сформировавшемся в середине семидесятых, о так называемом FORTRAN-77. Модель вычислений языка FORTRAN в точности соответствует представлению середины XX века о том, что нужно для реализации вычислительных алгоритмов и что можно реализовать на компьютерах фон Неймановского типа (тогда это был единственный тип компьютеров). Таким образом, это наиболее типичный представитель традиционных языков. Разработчики ранних версий языка FORTRAN не принимали в расчет полезности независимого от системы программирования определения языка. И его формальное определение по существу задавалось транслятором. В результате случайные решения, принятые в ранних трансляторах последующие разработчики вынуждены сохранять на многие годы.Для этого языка такое положение дел объяснимо и простительно. Удивительно, что и сегодня, в XXI веке появляются языки, зависимые от реализации, которые претендуют на универсальное применение.
2. Algol 60. Язык, сформировавшийся под давлением идеи осуществимости одновременно понятного для компьютеров и для человека представления алгоритмов. Очень скоро утопичность идеи выяснилась, и Algol 60 (до него был еще Algol 58 — индексация по году публикации первой официальной версии, но лишь Algol 60 был утвержден в качестве стандарта и получил широкое распространение; Algol 60 часто называют в литературе просто Алгол) стал не просто более строгим, но и более многословным аналогом FORTRAN. В Алголе появились и принципиальные новшества, выгодно отличающие его от предшественника. Это, прежде всего, определение языка, независящее от транслятора, структурность описания языка и определение действий абстрактного вычислителя на базе понятий из такого описания.
В Алголе предложена структурная организация контекстов выполнения конструкций, которая выводит вычислитель языка за рамки канона однородности и прямой произвольной индексной адресации памяти, — так называемая блочная структура программы. Этой структуре отвечает определенная дисциплина распределения памяти в рабочих программах, которые получаются в результате трансляции алголовских текстов. Эта дисциплина, получившая название стековой, с тех пор используется повсеместно при реализации языков программирования. Стековая дисциплина распределения памяти является ограничением доступа к векторно организованной памяти, элементы которой могут указываться в произвольном порядке, но именно это ограничение дает возможность эффективно отображать блочную структуру. Более того, поскольку доступ к памяти регламентирован, можно говорить о внедрении этого регламента в систему команд компьютера, хотя бы для уменьшения адресности команд. И сегодня модернизации фон Неймановской модели вычислений, связанные (в большей или меньшей степени) с таким регламентом, являются неотъемлемыми для современных вычислительных архитектур. Можно сказать, что стековая дисциплина стала частью модернизированной фон Неймановской архитектуры компьютера.
Если FOTRTRAN заслужил право считаться выдающимся достижением программистского языкотворчества из-за огромного прикладного значения, то Algol-60 также следует рассматривать как безусловное достижение в данной области, связанное в первую очередь со строгостью описания, отстраненного от конкретного вычислителя, с новыми хорошо проработанными конструкциями, со структурностью. Не случайно именно Алгол стал отправной точкой развития большинства существовавших и до сих пор существующих языков программирования. Он стал базой для многих теоретических разработок, прояснивших основные языковые и программистские понятия.
Появились и до эры персональных компьютеров были популярными вычислительные архитектуры, явно поддерживающие алголовскую организацию памяти. Наиболее известными из них являются машины фирмы Burroughs (США) и линия многопроцессорных вычислительных комплексов Эльбрус 3. Симула 67 характеризуется разработчиками как универсальный язык (СССР).
моделирования. Это, как и его предшественник Симула-1, — правильное расширение Алгола 60, а потому сохраняет его достоинства и недостатки. Впрочем, именно недостатки этой базы стали главной причиной того, что указанная пара языков не получила заслуживающее их распространение. Разработчики Симулы 67 очень точно подошли к оценке программистского опыта при воплощении его в языковые формы: не конкретные решения, а содержательные сущности, их обобщающие, воплощались в языке. В результате новые для того времени конструкции, отражающие объектный взгляд на обрабатываемые данные, стали в будущем основой для весьма перспективных методологий программирования, в частности, для методологии объектно-ориентированного программирования.
4. PL/1. Этот язык разрабатывался как попытка объединения всего, что может в принципе потребоваться программисту. Неизвестно, так это или нет, но вполне правдоподобно, что число “1” в названии языка есть амбициозное “единственный”, т. е. способный сделать бессмысленными любые другие
1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ
языки программирования. Совсем не заботясь о чистоте объединения всех известных программистских средств, разработчики языка предложили изначально эклектичную коллекцию, которая лишь с натяжкой может быть названа системой. Непознаваемость языка отмечается многими критиками, по выражению Э. Дейкстры, PL/1 — это “рождественская елка”, на которой можно увидеть все, а не инструмент, который можно эффективно использовать. Разрозненность и несводимость к единым концепциям создает большие трудности и для реализации: системы программирования для PL/1 всегда выделяли некоторый диалект, по существу определяя соответствующее подмножество средств, зависящее от транслятора.5. Алгол 68 — язык программирования, который, как и PL/1, претендовал на всеобщность, но уже на базе математического обобщения разрозненных средств программирования в фон Неймановской модели вычислений.
Можно сказать, что это PL/1 с элементами научности (С. Костер). Попытка распространения средств, хорошо себя зарекомендовавших в одной сфере, на уровень максимального обобщения в целом удалась, но разработчики зафиксировали в языковых формах лишь то, что уже было известно на момент появления проекта языка. По этой причине в Алголе 68 нет хороших средств поддержки модульного построения программ, в точном соответствии с фон Неймановскими принципами перерабатываемые данные не являются активными. К недостаткам языка следует отнести весьма тяжеловесное формальное описание, совершенно недоступное для практического применения в качестве руководства для программиста10. Основная заслуга разработчиков Алгола 68 в том, что они сумели реализовать на практике принцип обобщения без потерь, продемонстрировали продуктивность этого принципа. Множество ссылок в данном курсе на фактически не используемый сейчас язык Алгол 68 объясняется тем, что в этом языке, несмотря на явные недоделки и недостатки в форме описания языка, одновременно имелись ряд блестящих концептуально важных находок и система понятий, остающаяся до сего дня наиболее последовательной и строгой. Некоторые из концепций Алгола были восприняты в языках C и Ada, но сама система была при этом утеряна.
До сих пор в журнале «Communications of the ACM» периодически появляются комментарии к опубликованным статьям, озаглавленные приблизительно в следующем стиле: “Algol 68 ignorance considered harmful,” сводящиеся к тому, что очередные «новые» предложения являются лишь ухудшенной версией того, что уже давно было реализовано в Алголе 68.
Такова цена, которую пришлось заплатить за полную формальную точность описания.
6. Pascal — один из самых распространенных языков программирования. По этой причине он представлен множеством диалектов и версий. Первый Pascal был предложен Н. Виртом (N. Wirth) в ответ на принципиальное несогласие с позицией руководства рабочей группы по созданию Алгола 68, в частности, с Ван Вейнгаарденом. Главное в критике Вирта — чрезмерная сложность языка и особенно метода его формального описания.
Одной из побудительных причин создания языка стало осознание стройной концепции системы типов, вычисляемых статически, т. е. во время трансляции программы. Рассуждения о типах языка Pascal можно попытаться реконструировать следующим образом. Если базовая машина допускает произвольную трактовку смысла хранимых значений (принцип однородности памяти), а для человека смысл значений первичен для понимания программы, то в программе нужно фиксировать типы значений, а не только вычисления.
В результате появится возможность смыслового контроля программы, отделенного от обработки данных. Что для этого нужно? Прежде всего определить типы строго и дать точные механизмы построения одних типов через другие. Нужно такое определение, которое позволяет, не зная о конкретных значениях переменных, входящих в выражение, определять тип выражения.
В первом приближении тип отождествляется с множеством его значений, а построение требуемых в программе множеств возлагается на транслятор. В результате целый ряд потенциальных ошибок в программе может быть выявлен при трансляции.
Есть и другие особенности языка Pascal, которые делают этот язык строгим, есть и естественные ограничения универсальных возможностей, которые упрощают понимание языковых средств программистом. Язык создан так, чтобы поддержать написание хороших программ (в том понимании, какое сложилось к концу шестидесятых годов). Все это позволило утверждать Вирту, что он разработал язык для обучения студентов программированию.
Это утверждение не лишено основания, особенно если иметь в виду, что в дополнение к языку существует методика обучения с его помощью, которую разработал сам Вирт. Поэтому в учебных заведениях, где имеются серьезные курсы информатики, Pascal остается самым распространенным языком обучения.
Довольно скоро после своего появления Pascal становится очень популярным языком. Это породило потребность сделать на его базе язык программирования, который был бы более приближен к практическим нуждам. Сам Вирт разрабатывает языки-наследники Pascal’я, которые в большей степени поддерживают составление программ с независимыми модулями: Modula и
1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ
Modula 2. Но это все-таки новые языки. Заслуживают внимания и более близкие родственники стандартного Pascal’я, последовательно версией за версией предлагавшиеся коллективом фирмы Borland: языки и системы программирования линии Turbo Pascal. В них новые, весьма развитые возможности органично укладываются в строй родительского языка, не нарушая концепций. К сожалению, в разработанной этой же фирмой системе Delphi язык Object Pascal выпадает из этого ряда: концептуальной целостности сохранить не удалось. В свое время мы будем иметь повод обсудить эту ситуацию подробнее.7. Язык С и другие машинно-ориентированные языки. Осознание того, что программирование с использованием универсального языка, не отражающего особенности конкретного вычислительного оборудования, не дает возможности достичь предельной эффективности программ, возможной на этом оборудовании, привело к появлению так называемых машинно-ориентированных языков. Популярность таких языков зависит не только от распространенности оборудования, для которого они рассчитаны, но и от успешности выполненных с их помощь проектов.
В этом отношении показателен язык С, успех которого был во многом обеспечен удачным решением операционной системы Unix. Для разработки этой системы на машины серии PDP и был построен язык C, с помощью которого, в частности, предложен технологичный метод переноса программного обеспечения. Справедливости ради следует сказать, что хотя вклад системы Unix в успех С очень велик, но не менее важно и то, что этот язык предоставляет достаточно удобную для составления эффективных программ оболочку, закрывающую невыразительные средства машинного уровня. Растущая популярность этого языка повлияла на то, что компьютеры стали конструировать так, чтобы их архитектура соответствовала модели вычислений языка C.
В результате — рост популярности таких архитектур. В этом процессе наиболее преуспела фирма Intel, процессоры которой становятся стандартом дефакто в сфере разработки персональных компьютеров. Сегодня уже нельзя представить массовый компьютер, который не поддерживал бы программное обеспечение, разработанное под эти процессоры11.
Язык С если не первый, то один из первых языков программирования, в которым с самого начала существования провозглашалась идея рассматривать в качестве вычислителя не уровень команд конкретного компьютера, а уровень операционной системы. Иными словами, в данном языке присутВообще говоря, это тормозит развитие машинных архитектур.
ствуют конструкции, выполнение которых не может осуществляться без соответствующего обращения к средствам операционной системы. Конечно же, это не новшество. Во всех практически используемых языках программирования такие средства есть, и всегда они расширяют программистский взгляд на среду функционирования программы. Но чаще всего они представлены в языке как подчиненные средства, вынесенные на уровень библиотек, и далеко не всегда точно специфицированы. В С ситуация иная. В частности, наряду с автоматическим распределением памяти в языке определены механизмы предоставления участков памяти по запросам и возврата их, когда они перестают быть нужными.
В конце 80-х гг. на базе языка С было создан язык C++, практически являющийся расширением С. С++ отличается прежде всего значительным усилением системы описаний (объектно-ориентированные возможности являются одним из наиболее применяемых расширений). Но по конструкции он еще намного сложнее, а определение его производит впечатление еще большей эклектичности. Но С++, усугубив недостатки С с точки зрения человека, сохранил при колоссальном расширении возможностей языка все достоинства С, касающиеся машинной ориентированности и эффективности. Подхватив эстафету С, С++ в последнее время является наиболее распространенным языком профессионального программирования сложных систем.
Еще более укрепляют позиции языка С++ многие современные инструментальные системы, создававшиеся на нем без учета потребностей других языковых средств. В частности, системы работы с динамически подключаемыми программами (middleware) CORBA и COM практически требуют, чтобы программа, к ним обращающаяся, была написана на С++, поскольку вся система интерфейсов ориентирована на типы данных этого языка и порою даже на их конкретные представления.
Чтобы более эффективно работать прежде всего с системами middleware, корпорация Microsoft предложила новый диалект С, названный C#. При его создании ставилась цель получить язык, так же относящийся к С++, как С++ относится к С. Для наших целей в большинстве случаев различия между С++ и С# несущественны.
На фоне заслуженной популярности С уместно упомянуть неизмеримо менее распространенный язык Bliss. Этот машинно-ориентированный язык программирования мог бы быть концептуально более выверенной альтернативой С, но отсутствие разработанного с его помощью проекта, сравнимого по значимости с Unix, не позволило ему выделиться. И хотя в идейном плане Bliss и повлиял на языкотворчество, интерес к нему не вышел за рамки
1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ
академических исследований.Отечественный опыт разработки машинно-ориентированных языков демонстрирует поддержку архитектуры, отличную от Intel-подобной. Укажем на два проекта этого рода. Первый — язык Ярмо (аббревиатура: язык реализации машинно-ориентированный), построенный для ЭВМ БЭСМ-6 и отражающий все современные веяния в языкотворчестве. О качестве и востребованности этого языка можно судить хотя бы по тому, что было реализовано несколько его версий. Второй пример — Эль-76, разработанный в качестве аналога ассемблерного языка для многопроцессорного вычислительного комплекса Эльбрус. Оставаясь в целом фон Неймановской машиной, архитектура этого комплекса далеко отходит от канонических принципов. В частности, в ней предусмотрена аппаратная поддержка вызова процедур, стековая организация памяти и другие высокоуровневые средства программирования. Особенностью этой архитектуры является тегирование: каждое значение сопровождается тегом, т. е. описателем того, к какому типу относится информационная часть значения. По существу это отказ от строго однородной памяти. Все архитектурные особенности Эльбруса отражены в Эль-76, что позволило рассматривать данный язык в качестве единственного инструмента программирования системных программ. Конечно, нельзя говорить о механическом переносе этого языка в архитектурную среду другого типа, а потому время использования его, как и любого машинно-ориентированного языка, ограничено временем жизни данной архитектуры12.
8. Язык Ada. Он разрабатывался по заказу Министерства обороны США на конкурсной основе с предварительным сбором и анализом требований, с обширной международной экспертизой. По существу в нем воплощена попытка определить язык программирования как экспертно обоснованный комплекс средств программирования. На завершающем этапе конкурса приняли участие около ста коллективов. В результате проверки соответствия представленных разработок сформулированным требованиям, для обсуждения общественности было отобрано четыре языка, зашифрованных как Red, Green, Blue и Yellow. В разной степени критике подверглись все четыре кандидата.
Особенно острым критиком оказался Э. Дейкстра, который камня на камне не оставил от Red, Blue и Yellow, но чуть-чуть ‘пожалел’ Green, доказывая, Это утверждение не противоречит долголетию С. Как уже отмечалось, данный язык сегодня навязывает архитектуру машин, которая бы не противоречила его эффективной реализации. Например, использование С в качестве базового языка для Эльбруса явно ограничивало бы доступ ко многим развитым машинным возможностям.
что все недостатки языка связаны с несвободой в выборе решений, обусловленных жестко фиксированными требованиями: там, где авторы могли бы решать какие-либо проблемы по-своему, они были вынуждены идти на поводу у априорных предписаний. Тем не менее, Green стал приемлемым вариантом и получил одобрение. Как оказалось, это был единственный из финалистов язык, предложенный не американцами. Конкурсная комиссия утвердила его в качестве единого официального языка Министерства обороны США для разработки программ для встроенных систем и дала ему имя Ada — в честь Ады Августы Лавлейс, дочери Байрона и ученицы Бэббиджа — первой в истории программистки. Мы будем иметь возможность познакомиться с рядом интересных особенностей этого языка в свое время. Пока же отметим, что успеха разработчики языка добились благодаря заботе о концептуальной целостности — именно это выделяло Green среди конкурентов. В то же время, весьма примечательно, что в ходе последующего развития Ada в угоду появившимся пользователям в язык стали включать все новые и новые средства. В результате к концу девяностых годов Ada по стилю построения стала подобна PL/1: в ней есть средства поддержки всему, что можно найти в практике работы программистов в конце XX века. Как отмечал известный советский программист В. Ш. Кауфман, язык Ada 9х можно рассматривать в качестве добротной энциклопедии программистского знания и опыта, но никак не в качестве инструмента, ориентированного на пользователя.
9. Объектно-ориентированные языки. Последним достижением в области программистского языкотворчества считается поддержка объектно-ориентированной методологии. Эта сфера интересует многих разработчиков языков начиная с восьмидесятых годов. Первым проектом, провозгласившим принцип перехода от пассивных данных к активным объектам, стал Smalltalk.
В этом языке объектам предоставляется возможность действовать в ответ на получаемые ими сообщения без каких бы то ни было иных способов активизации действий. Эта возможность реализована в рамках идеи динамической типизации (отход от классической статической системы типов, ставшей общепризнанной после Pascal’я). В качестве наглядной демонстрации мощи идеи была предложена система программирования Smalltalk-80 с очень богатой библиотечной поддержкой конструирования графических интерфейсов.
Smalltalk — последний крупный проект, результаты которого были представлены не только в виде предложения программного продукта как данного, но и как материалы для всестороннего обсуждения программистской общественностью. В результате таких обсуждений выработалась идея того, что нужно для поддержки объектной ориентированности в языках для промышМОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ ленного производства программ. Такие языки появились достаточно скоро.
Наибольшее распространение из них получил С++, по-видимому, из-за растущей популярности С. Заметными объектными языками стали также Turbo Pascal версий с 5.5 до 7.0 и Object Pascal системы Delphi. Общим для промышленного развития Smalltalk’а является возврат к статическим типам данных, повышенное внимание к вопросам защиты. В результате удалось построить приемлемые по эффективности объектного кода системы программирования, удовлетворяющие требованиям технологичного программирования. Однако, как это обычно бывает с производственными системами, на смену аналитическим исследованиям роли и границ применимости языка пришли рекламные хвалебные обсуждения достоинств и никогда — недостатков.
Применительно к обсуждению традиционности языков уместно посмотреть на то, как трансформируются фон Неймановские принципы вычислений при использовании объектной модели. Очевидно, что отход от однородности памяти для этой модели более радикален, нежели, к примеру в Pascal’е. Если рассматривать объекты как хранимые в памяти данные, то за счет связанности этих данных с программами (методами объектов) память в объектной модели приобретает активность. На концептуальном уровне рассмотрения можно усмотреть, что модернизируется управление: объект сам знает, какую программу-метод нужно активизировать, чтобы выполнить то или иное действие. Несомненно, все это повышает гибкость программирования, способствует расширению возможности отхода от фон Неймановского взгляда на программу, как на автомат, выполняющий предписания-команды. Однако на уровне реализации программ-методов все остается по-старому: все то же последовательное выполнение операторов, те же подходы к разветвлениям вычислений и к организации циклической обработки. Более того, последовательный характер вычислений остается и при задании взаимодействия объектов. Следовательно, объектный подход, хотя и способствует взгляду на вычислительные процессы, отличающемуся от фон Неймановского стиля, сам по себе не приводит к смене базовой модели вычислений. Этот подход может быть применен и для организации вычислений на основе иных моделей, отличных от фон Неймановских. И весьма успешный опыт такого применения имеется: разработан язык CLOS (Common Lisp Object System), который есть надстройка над нетрадиционным языком Lisp.
Уместно отметить, что многие приемы и механизмы объектного программирования на этом языке оказываются более наглядными и естественными, нежели в рамках традиционных моделей вычислений.
10. Язык Java. Заметным этапом в развитии объектно-ориентированноГЛАВА 1. ПОНЯТИЯ го подхода стало появление языка Java, который был предложен как средство программирования не для отдельного компьютера, а сразу для всех машин, имеющих реализацию так называемой Java-машины — исполнителя программ на промежуточном языке более высокого уровня, нежели командный язык обычных машины. Иными словами, провозглашается система программирования с явно и точно определенным промежуточным языком. Другая особенность Java-проекта — его ориентация на Интернет программирование: поддерживается возможность построения приложений, запускаемых на сервере от клиентской рабочей станции и взаимодействующих с клиентом через произвольный браузер.
Схема трансляции с выделенным промежуточным языком, независящим от исходного языка, очень даже не новая. В шестидесятые годы ее пытались применять для сокращения расходов на разработку трансляторов (например, в качестве промежуточного языка в США был разработан специальный язык Uncol, в Советском Союзе для тех же целей предлагался язык АЛМО). Чисто умозрительно можно представить ситуацию. Требуется реализация m языков на n машинах. В схеме без промежуточного языка в этом случае нужно запрограммировать m n трансляторов, тогда как использование такого языка позволяет сократить это число до m + n: для каждого языка пишется транслятор в промежуточный язык (m) и для каждой машины создается транслятор или интерпретатор промежуточного языка (n). К тому же, опятьтаки умозрительно, можно предположить, что затраты на ‘половинки’ трансляторов сократятся. Все получается, если удается построить промежуточный язык удовлетворяющий следующим условиям:
a) все реализуемые языки можно вложить в промежуточный язык, т. е. их модели вычислений совместимы, не противоречат друг другу;
b) все целевые машины можно непротиворечиво представить в одной модели вычислений промежуточного языка так, чтобы трансляция программ для этой общей модели давала бы эффективный код для конкретных вычислителей.
Выполнить эти условия весьма сложно даже для близких языков и машин.
Точнее сказать, что затраты на решение этих задач неизмеримо и неоправданно превышают стоимость пресловутых m n трансляторов. Поэтому после серии экспериментальных проектов идея промежуточного языка была предана забвению. В проекте Java она возродилась, правда, в урезанном до
1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ
одного языка варианте, причем специально разработанном с учетом осуществимости построения Java-машины. Именно эти дополнительные условия (точнее — квалифицированное сужение исходного языка и довольно высокий уровень команд-конструкций языка Java-машины) в сочетании с практически унифицированной архитектурой массовых компьютеров (см. выше) и с очень существенным ростом чисто технических возможностей машин позволило воплотить старую идею в промышленной разработке13.В контексте обсуждения традиционности языков необходимо рассмотреть вопрос о том, насколько далеко язык Java и Java-машина отходят от фон Неймановской модели вычислений. Совместная разработка этих двух компонентов системы программирования для нового языка позволила прийти к достаточно практичным компромиссам, удовлетворить условиям выбранной схемы реализации, о которых шла речь выше.
Условие (a) выполняется почти автоматически, и, т. к. нет нужды заботиться о других языках, можно сосредоточить внимание на том, чтобы обеспечить наиболее рациональное вложение модели вычислений языка в модель машины. Что касается условия (b), то здесь ставка делалась на фактическое сходство архитектуры конкретных вычислителей, для которой уже накоплен опыт программистских решений во многих типовых ситуациях. В результате отход от фон Неймановской модели вычислений в Java-системе, хотя и заметен, но не распространяется далее того, что уже было при разработке трансляторов и языков. Достаточно сказать, что Java-машина построена на принципах, предложенных еще в 1963 году для организации вычислений в рабочей программе Ветстоунского компилятора для Algol 60 [68]. Схема, представленная в этом проекте, стала классической, и именно она воспроизводится в Java-машине, естественно существенно более развитой по сравнению с первоначальным прототипом14.
Важным новым качеством Java-машины является поддержка работы программиста с потенциально неограниченной памятью. При выполнении конПро новые условия данного проекта говорят обычно с неохотой или же вовсе замалчивают их. К примеру в книге «Java технология» успех старой идеи в новом проекте объясняется тем, что в прежние времена эту идею изучали в университетах, тогда как сегодня за нее взялись промышленники.
В этой связи уместно следующее замечание. Если бы книга [68] не была бы сегодня библиографической редкостью, то ее главу 2 «Рабочая программа» можно было бы рекомендовать в качестве первоначального введения для тех, кто желает изучить устройство Javaмашины. После прочтения этого изложения понимание Java-машины окажется более глубоким.
кретной программы на языке Java можно не заботиться о том, что какая-то часть памяти перестает быть нужной. Система программирования сама сделает так, что та память, которая оказалась недоступной, а значит, ненужной, возвращается для использования в новых запросах. Такие ситуации выявляются в процессе вычислений, когда фактические ресурсы, предоставляемые для размещения данных, требуется пополнить для переиспользования. В угоду этому соглашению принесен в жертву ряд приемов организации ручного переиспользования памяти, необходимых, например, при программировании на С.
Модель вычислений Java в точности соответствует тому, что требуется от объектно-ориентированного программирования: активность памяти на уровне методов объектов, совместное описание данных и программ методов, отделение предоставляемых средств от их реализации. Все это сочетается с традиционной схемой управления вычислениями при описании алгоритмов обработки. Следует отметить, что разработчики языка не стали включать в него средства, с трудом укладывающиеся в концептуальную схему Java-машины и обычно, как, например, в С++, предоставляемые через довольно произвольные реализационные соглашения. Ориентация Java-машины на схему организации вычислений, ставшую классической со времен Algol 60, повлияла на язык в том отношении, что все, что выходит за рамки принятой модели, представлено таким образом, чтобы это можно было вычислить в период трансляции. К примеру, проблемы статической типизации в данном языке решены радикально: в нем просто нет средств конструирования структурных типов, отличных от классов объектов. В результате, язык стал лаконичнее по сравнению, например, с С++.
Благодаря совокупности отмеченных и других нововведений, которые в разрозненном виде появлялись в различных языках, программирование на Java, относящееся в целом к объектно-ориентированному стилю, обретает самостоятельность. Характерным для нового стиля является принципиальный отход от учета особенностей конкретных вычислителей в предположении (далеко не всегда оправданном!) о том, что используемые машины выполняют требуемые действия с приемлемым уровнем эффективности.
В значительной степени для того, чтобы перехватить инициативу у языка Java, и был создан C#, стремящийся сохранить в новой области эффективность С/C++.
БАЗОВЫЕ КОНСТРУКЦИИ ЯЗЫКА
§ 1.3.1.3.1. Линейные программы и их компоненты Рассмотрим несколько простых примеров программ в языке C. Последовательность действий всех рассматриваемых программ линейная: оператор за оператором, так, как это записано в тексте. Такие программы называются линейными программами.
Программа 1.3. /* Печатается N -ая степень (7-ая) вводимого числа для данного N.
Прямолинейный алгоритм*/ #include int X, Y;
int main(void) scanf("%d", &X );
Y = X*X*X*X*X*X*X;
printf("\n7 power of %d is %d\n", X, Y);
return 0;
Программа 1.3. /* Печатается N -ая степень (7-ая) вводимого числа для данного N.
Улучшенный алгоритм #include int X, Y, X23;
int main (void) scanf ( "d", &X );
printf (“\n7 power of %d is %d\n”, X, Y);
return 0;
Программа 1.3. /*Печатается N -ая степень (7-ая) вводимого числа для данного N Улучшенный алгоритм 2/* #include int main (void) /* Такой стиль лучше для комментариев к переменным: */ int X; /* для задания входного значения */ int Y; /* для промежуточного и окончательного результата */ scanf( "%d", &X );
printf ("\n7 power of %d is %d\n", X, Y );
Что мы видим, анализируя эти программы? Программа содержит компоненты, обсуждению которых мы посвятим следующие абзацы (порядок разбора следует порядку, в котором компоненты содержатся в обсуждаемых программах 1.3.1, 1.3.2 и 1.3.3).
1.3.2. Не выполняемые вычислителем фрагменты программы Эти фрагменты с точки зрения вычислителя языка не несут никакой информации, но они очень полезны для человека, читающего программу, изменяющего ее, использующего программу при составлении другой программы.
1. Комментарий. Комментарии служат:
— Для облегчения чтения и восприятия программы путем дополнительного выделения и графического оформления ее структур.
— Для понимания того, зачем нужна программа, какие у нее особенности, а также что делает программа или какой-либо ее фрагмент (документирование);
При чтении программы вычислителем комментарии удаляются препроцессором.
2. Пробельные символы: концы строк, пробелы, табуляции.
В данном случае рассматриваются лишь явно обозначенные комментарии.
В С они начинаются с последовательности “/*” и завершаются “*/”, В С++ используются также комментарии, начинающиеся с последовательности “//” и завершающиеся вместе с текущей строкой.
В некоторых языках могут быть не обозначенные явно комментарии15 :
куски текста, пропускаемые транслятором. Сейчас все большую популярность приобретает идея программ, вложенных в поясняющий их и описывающий общую задачу текст. В таком случае комментарии занимают основную часть текста.
Текст программы на языке С сам по себе не нуждается ни в разбиении на строки, ни в специальном расположении своих составляющих в строках. Но без пробельных символов реальные программы неудобно читать человеку! Существуют и форматные языки, где пробельные символы являются значащими (это обычно происходит при табличном задании программ и привязке смысла выражений к структуре текста).
1.3.3. Подключение внешней информации (библиотек) дает возможность пользоваться операторами scanf и printf (которые позволяinclude ют вводить данные и распечатывать результаты выполнения программы), а также другими средствами стандартной библиотеки stdio. На данном примере можно показать, как препроцессор подключает библиотеки к исходному Практически в каждом языке программирования в качестве такого комментария может использоваться текст, идущий после синтаксического конца программы.
В современных технологиях индустриального программирования значительное место отводится требованиям к комментариям и к оформлению программ. Одна из лучших похвал тексту программы — что он самодокументирован, не требует никакого внешнего описания.
В ряде случаев принимается регламент оформления комментариев, который позволяет выделять их автоматически; существуют программы, позволяющие строить из таких комментариев вполне осмысленную документацию (примером может служить библиотечное для Java средство JavaDoc).
тексту программы (см. рис. 1.2, на котором простые стрелки изображают указатели мест хранения нужных текстовых фрагментов, а жирные стрелки показывают процесс включения файла в текст). Из схемы видно, что в С/С++/C# подключение внешних библиотек — двухступенчатый процесс: в исходном тексте программы указывается только заголовочный файл. Встраивание его в тест позволяет транслятору корректно работать с именами, т. е. считать их описанными и доступными в исходном тексте. Для выполнения транслируемой программы нужно иметь следующую ступень: тексты или отдельно оттранслированные фрагменты программ, представленных внутри заголовочных файлов. В С/С++ задачу обеих ступеней решает препроцессор.
В других языках подключение библиотек организовано по-разному. Так, в Algol 60 понятие внешней библиотеки вообще никак не определялось. Считалось, что достаточно говорить об отдельных процедурах. То же можно сказать и про большинство других ранних языков.
Для внешних библиотек, которые определены языком, нет проблемы, как указать их подключение — система программирования их “знает”, а потому может считать их частью программы, которую программист писать не должен. Эта идея в законченном виде представлена в Алголе 68, в котором любая программа считается блоком, погруженным в стандартный блок, начинающийся библиотечным вступлением и заканчивающийся библиотечным заключением (см. § 1.1.1). Проблема может возникнуть, когда в распоряжении программиста есть несколько библиотек, выполняющих похожие функции и поименованных одинаково. В этом случае нужно явно указывать, какую из библиотек подключать17.
В ряде языков приняты более строгие соглашения: программисту предписывается указывать источник подключения (подобно тому, как в С/С++/C# указывается заголовочный файл) и конкретные подключаемые средства, в дальнейшем используемые в программе. Если это соглашение оформляется в виде языковой конструкции, то появляется возможность на уровне языка конструировать библиотеки. В таком случае можно корректно подключать не только процедуры и функции, но иные программные фрагменты (например, описания переменных). В законченном виде этот подход представлен в языке Modula-2, в котором программа рассматривается как набор модулей, Именно это сделано в С/С++/C#, причем для всех, как стандартизованных языком, так и для других доступных библиотек. С точностью до того, что подключение выполняется в С/С++ с помощью препроцессора, который не может ничего знать о заказываемых файлах, это достаточно хорошее решение.
Библиотека stdc заголовков Рис. 1.2. Схема включения файла в текст программы (работа препроцессора для языков семейства С) явно содержащих разделы описания импорта — то, что используется в модуле из других модулей, в том числе и внешних, подключаемых, и экспорта — то, что данный модуль предоставляет для использования. В результате единообразно описываются все связи между модулями, в том числе и связи составляемой программы с окружением, которые естественно трактовать как подключение библиотек (см. рис. 1.3).
Подключение внешних библиотек возможно в виде текстов на транслируемом языке и/или в виде готовых к сборке модулей. Второй режим, по крайней мере в принципе, позволяет говорить об использовании библиотек, написанных на других языках. Но он не в состоянии обеспечить совместимость форматов данных и программ. Контроль за совместимостью, а при необходимости и преобразование форматов в этом случае возлагается на окружающую систему. Наличие этого режима ставит перед разработчиками системы программирования проблему: необходимость различения текстов и оттранслированных библиотечных программ. Если есть оттранслированная библиотека и ее текст, то возникает двусмысленность: какой из вариантов должен подключаться к программе. Разрешение этой двусмысленности делается поразному. В С/С++/C# указание того, какого вида библиотека требуется дается на синтаксическом уровне, а двухступенчатая схема подключения дает определенную гибкость использования: заголовочные файлы могут (и должны!) объединять тематически связанные средства. В Алголе 68 такое объединение не предусматривается, и это один из недостатков языка для практического применения.
Часто для внешних (библиотечных) средств требуются специальные описания с пометкой external вместо их реализации. Это дает возможность транслятору программировать их использование без обращения к фактическому описанию, а также упрощает организацию составления сведений о том, какие внешние средства надо будет подключить на этапе сборки. Такой метод сегодня стал почти стандартом для языков программирования. Иногда он считается достаточным и дополнительных описаний для использования внешних средств не предлагается, во многих случаях он сочетается с другими методами оперирования с библиотеками (в частности, в языках С/С++/C#, Pascal, Алгол 68).
Следует заметить, что когда стандарт языка не распространяется на используемые библиотеки (так было, например, в Algol 60), возможности использования готовых программ в других операционных обстановках резко сужаются.
import Mi1: a,b; // Из модуля Mi1 импортируются a и b Mi2: x,y,z; // Из модуля Mi2 импортируются x, y и z export U, V; // Модуль M предоставляет U и V другим // На схеме импорт изображается на верхней кромке begin // Тело модуля end.
Модули, поставляемые системой Модули составляемой программы Рис. 1.3. Схема взаимосвязей модулей программ на языке Modula- тек предложено в Turbo Pascal’е версий 5 и выше. Здесь к программе подключается не просто текстовый файл заголовков — как в С/С++/C#, не какойто фрагмент-вступление к составляемой программе, который предлагает для использования библиотеку — как в Алголе 68, а самостоятельная языковая единица, конструкция, содержащая все, что нужно при работе с подключаемыми средствами — как в Modula-2. Эта конструкция, называемая модулем (как в Modula-2), описывает как то, что можно использовать, так и то, что нужно выполнить до и после использования с тем, чтобы применение библиотечных средств было бы корректно. На рис. 1.4 схематически показаны описание модуля Turbo Pascal’я (это программный текст, который начинается со служебного слова unit), программы, использующей модуль (начинается со служебного слова program), и подключение модуля к программе как процесс вставки в нее соответствующих фрагментов из модуля (показан серыми стрелками).
В связи с задачей подключения внешней информации мы затронули очень важный общий вопрос программирования, вопрос модульности разрабатываемой системы. К нему мы еще не раз будем возвращаться в связи с тем, что модульность (в разном понимании этого слова) — основа технологии разбиения решаемой задачи на подзадачи. Такое разбиение, получившее название декомпозиции программ, приходится проводить программисту постоянно, ибо сложность конструирования программ не позволяет охватывать все стороны этого процесса одновременно. Искусство программирования во многом состоит в том, чтобы добиваться такой декомпозиции, которая способствует более быстрому и эффективному пути к получению решения.
Применительно к использованию библиотек метод декомпозиции можно продемонстрировать следующим образом. Для нашей задачи нужно выполнить действие, для которого в системе программирования есть уже готовое типовое решение (в обсуждаемых программах это две задачи: ввод данных и вывод результатов счета). Именно его мы и используем. Иными словами, с точки зрения декомпозиции нашей задачи библиотеки выступают в роли заранее решенных подзадач.
1.3.4. Описания В современных системах программирования, как правило, жестко проводится в жизнь следующий принцип:
Bсе, что используется, должно быть предварительно описано!
Рассмотрим встретившиеся нам варианты описаний.
… // описание того, что // внешнего использования (реализация процедур и begin … // действия, которые // нужно выполнить до … // действия, которые // нужно выполнить после // использования предоставляемых средств end. // конец описания модуля Рис. 1.4. Схема подключения модуля в языках Turbo Pascal и Object Pascal.
1. В программе 1.3.2 описание вводит определение трех переменных, которые используются для храint X, Y, X23;
нения значений целого типа. Описание действует во всем тексте программы.
2. Если поставить описания после строки как сделано в программе 1.3.3, то будет запрещено использование X и Y вне функции main, о которой говорится ниже.
3. Как показано в программе 1.3.3, можно обойтись без описания переменной X23, поскольку транслятор сам создает промежуточную переменную для хранения X * X (см. 4) в § 1.3.5.
В С различают объявление имени (предварительное упоминание) и собственно описание (фиксация смысла и содержания описываемого имени). С предварительными упоминаниями приходится работать особенно часто, когда пишется программа в стиле объектно-ориентированного программирования, состоящая из многих модулей. В простых программах обычно достаточно собственно описаний.
Описание переменных — это пассивная часть программы. Сами по себе такие описания ничего не вычисляют, они задают структуру части фон Неймановской памяти, в которой хранятся данные. В программе представлено еще одно описание, определяющее требуемые вычисления. Это активная часть программы, которая транслируется в команды машины. Обсуждение его структуры приводится в следующем разделе.
1.3.5. Действия 1. Заголовок функции. Выражение определяет функцию main, которая должна вычислить целочисленное значение (описатель int). Заданное в скобках служебное слово void указывает на то, что вычисление определяется как независящее от параметров. Компилятор не позволяет вызывать такую функцию с параметрами. Для языка С принято, что любая программа должна содержать функцию main. Выполнение этой функции начинает выполнение программы.
2. Знаки группировки { и }. Строки с фигурными скобками обрамляют блок операторов. Внутри блока находится описание алгоритма как последовательности операторов. В данном случае это алгоритм функции 3. Вызов функции ввода. Чтение значения переменной осуществляется с помощью оператора которая задает формат ввода %d и переменную X, получающую значеscanf ( "%d", &X );
ние с помощью этого оператора. Здесь заслуживает внимания знак "&".
«