Языки программирования - концепции и принципы

Предисловие

Значение языков программирования

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

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

это тот «материал», из которого создается программное обеспечение, то, что мы видим на наших экранах большую часть дня. Я верю, что язык программирования — один из наиболее, а не наименее важных факторов, которые влияют на окончательное качество программной системы. К сожалению, слишком у многих программистов нет достаточных языковых навыков. Они страстно любят свой «родной» язык программирования и не способны ни проанализировать и сравнить конструкции языка, ни оценить преимущества и недостатки современных языков и языковых понятий. Слишком часто можно услышать утверждения, демонстрирующие концептуальную путаницу: «Язык L1мощнее (или эффективнее) языка L2».

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

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

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

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

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

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

 

 

Цель книги

Цель этой книги — научить читателя разбираться в языках программирова­ния, анализируя и сопоставляя языковые конструкции, и помочь ему уяснить:

• Какие альтернативы доступны разработчику языка?

• Как реализуются языковые конструкции?

• Как их следует использовать?



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

Конечно, эту книгу не следует рассматривать как справочник по какому-либо конкретному языку программирования. Задача автора заключается в том, чтобы научить анализировать языки, не погружаясь в мелкие языковые частности.

Книга также не является руководством

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

Выбор материала

   Автору книги по языкам программирования неизбежно приходится обижать, по крайней мере 3975 из 4000, если не больше, изобретателей различных язы­ков! Я сознательно решил (даже если это обидит 3994 человека) сосредоточить внимание на очень небольшом наборе языков, поскольку уверен, что на их примере смогу объяснить большинство языковых понятий. Другие языки об­суждаются только при демонстрации таких понятий, которые отсутствуют в языках, выбранных для основного рассмотрения.

   Значительная часть книги посвящена «заурядным» процедурным (импе­ративным, imperative) языкам; из этого класса выбраны два. Языки с низким уровнем абстракции представляет С, который обошел Fortran, прежде доми­нирующий в этой категории. Для представления более высокого уровня аб­стракции мы выбрали язык Ada с гораздо более четкими определениями, чем в широко известном языке Pascal.

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

    К сожалению, (как я полагаю) большинство программ сегодня все еще пишутся на процедурных языках, но за последние годы качество реализаций непроцедурных (неимперативных) языков улучшилось настолько, что они могут использоваться для разработки «реального» программного обеспече­ния. В последних главах представлены функциональные (ML) и логические (Prolog) языки программирования с целью убедить учащихся, что процедур­ные языки не являются концептуальной необходимостью для программиро­вания.

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

Чтобы избежать путаницы при сравнении

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

 

О чем эта книга

Часть 1 является описательной. Она содержит определения и обзор языков и сред программирования. Во второй части подробно объясняются основные конструкции языков программирования: типы, операторы и подпрограммы. В части 3 рассматриваются более сложные понятия программирования, та­кие, как действительные числа, статический полиморфизм, обработка оши­бок и параллелизм. В части 4 обсуждается программирование больших систем с акцентом на языковой поддержке объектно-ориентированного программи­рования. Заключительная часть 5 посвящена основным концепциям функци­онального и логического программирования.

Рекомендации по обучению

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

   На основе изложенного материала можно составить несколько курсов лек­ций. Части 1 и 2 вместе с разделами части 4 по модулям и объектно-ориенти­рованному программированию могут послужить основой односеместрового курса лекций для второкурсников. Для продвинутых студентов можно уско­рить изложение первой половины, с тем чтобы сосредоточиться на более трудном материале в частях 3 и 4. Углубленный курс, несомненно, должен включить часть 5, дополненную в большом объеме материалом по некоторо­му непроцедурному языку, выбранному преподавателем. Разделы, отмечен­ные звездочкой, ориентированы на продвинутых студентов.

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

а не по программированию, то

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

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

Примечание автора

 

    Лично я предпочитаю более высокие уровни абстракции низким. Это — убеждение, а не предубеждение. Нам — разработчикам программного обес­печения — принадлежат печальные рекорды в вопросах разработки надеж­ных программных систем, и я полагаю, что решение отчасти лежит в пере­ходе к языкам программирования более высоких уровней абстракции. Обоб­щая высказывание Дейкстры, можно утверждать: если у вас есть программа в 100 000 строк, в которой вы запутались, то следует переписать ее в виде про­граммы в 10 000 строк на языке программирования более высокого уровня.

   Первый опыт я получил в начале 1970-х годов как член большой группы программистов, работающих над системой финансовых транзакций. Мы ус­тановили новую интерактивную систему, хотя знали, что она содержала ошибку, которую мы не могли найти. Спустя несколько недель ошибка была, наконец, обнаружена: оказалось, что изъяны в используемом языке програм­мирования привели к тому, что тривиальная опечатка превратилась в несоот­ветствие типов. Пару лет спустя, когда я впервые увидел Pascal, меня «зацепи­ло». Мое убеждение в важности проблемы усиливалось всякий раз, когда я по­могал ученому, потратившему впустую недели на отыскание ошибки в про­грамме, причем в такой, которую, будь она на языке Pascal, нельзя было бы даже успешно скомпилировать. Конечно, несоответствие типов — не единст­венный источник ошибок программирования, но оно настолько часто встре­чается и так опасно, хотя и легко обнаруживается, что я считаю жесткий кон­троль соответствия типов столь же необходимым, как и ремень безопасности в автомобиле: использование его причиняет неудобство, но оно весьма незна­чительно по сравнению с возможным ущербом, а ведь даже самые лучшие во­дители могут попасть в аварию.

Я не хочу быть вовлеченным

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

 

Благодарности

   Я хотел бы поблагодарить Кевлина А.П. Хеннея (Kevlin A.P Неппеу) и Дэ­вида В. Баррона (David W. Barron) за ценные замечания по всей рукописи, так же как Гарри Майрсона (Harry Mairson), Тамара Бенея (Tamar Benaya) и Бруриа Хабермена (Bruria Haberman), которые прочитали отдельные ча­сти. Я обязан Амирему Ехудаи (Amiram Yehudai), моему гуру в объектно-ориентированном программировании: он руководил мной во время много­численных обсуждений и тщательно проверял соответствующие главы. Эдмон Шенберг (Edmond Schonberg), Роберт Девар (Robert Dewar) вместе со своей группой в NYU быстро отвечали на мои вопросы по GNAT, позволив мне обучиться и написать о языке Ada 95 еще до того, как стал доступен полный компилятор. Ян Джойнер (lan Joyner) любезно предоставил свой неопубликованный анализ языка C++, который был чрезвычайно полезен. Подобно моим предыдущим книгам, эта, вероятно, не была бы написана без LATEX Лесли Лампорта (Leslie Lamport)!

     Мне посчастливилось работать с высоко профессиональной, квалифици­рованной издательской группой Джона Уайли (John Wiley), и я хотел бы по­благодарить всех ее членов и особенно моего редактора Гейнора Редвеса-Мат-тона (Gaynor Redvers-Mutton).

                                                                                                                               М. Бен-Ари

 Реховот, Израиль

1 Введение

        в языки

        программирования

    Глава 1

   Что такое

   языки программирования

1.1. Некорректный вопрос

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

Неявно мы сравниваем новый язык

   Что этот язык может «делать»?

   Неявно мы сравниваем новый язык с другими. Ответ очень прост: все язы­ки могут «делать» одно и то же — производить вычисления! В разделе 1.8 объ­яснена правомерность такого ответа. Однако, если все они могут выполнять одно и то же — вычисления — то, несомненно, причины существования сотен языков программирования должны быть в чем-то другом.

   Позвольте начать с нескольких определений:

  Программа — это последовательность символов, определяющая вычисление.

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

  Вас может удивить, что в определении не упоминается слово «компьютер»! Программы и языки могут быть определены как сугубо формальные матема­тические объекты. Однако люди больше интересуются программами, чем другими математическими объектами типа групп, именно потому, что про­грамму — последовательность символов — можно использовать для управле­ния работой компьютера. Хотя мы настоятельно рекомендуем изучение тео­рии программирования, здесь ограничимся, в основном, изучением того, как программы выполняются на компьютере.

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

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

Наиболее значительным из первых шагов

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

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

load     R3,54

означающую «загрузить в регистр 3 данные из ячейки памяти 54», намного легче прочитать, чем эквивалентную последовательность битов. Трудно пове­рить, но термин «автоматическое программирование» первоначально отно­сился к ассемблерам, так как они автоматически выбирали правильную по­следовательность битов для каждого символа. Известные языки программи­рования, такие как С и Pascal, сложнее ассемблерных языков, потому что они «автоматически» выбирают адреса и регистры и даже «автоматически» выби­рают последовательности команд для организации циклов и вычисления арифметических выражений.

  Теперь мы готовы ответить на вопрос из названия этой главы.

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

Теперь понятно, почему существуют сотни

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

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

   Из концепции абстракции вытекает общее правило:

   Чем выше уровень абстракции, тем больше деталей исчезает.

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

    В этом учебнике вы изучите языки трех уровней абстракции. Опуская ас­семблер, мы начнем с «обычных» языков программирования, таких как Fortran, С, Pascal и Pascal-подобные конструкции языка Ada.

мы обсудим языки типа

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

1.2. Процедурные языки

 

Fortran 

   Первым языком программирования, который значительно превзошел уро­вень языка ассемблера, стал Fortran. Он был разработан в 1950-х годах груп­пой специалистов фирмы IBM во главе с Джоном Бекусом и предназначался для абстрактного описания научных вычислений. Fortran встретил сильное противодействие по тем же причинам, что и все последующие предложения абстракций более высокого уровня, а именно из-за того, что большинство программистов полагало, что сгенерированный компилятором программный код не может быть лучше написанного вручную на языке ассемблера.

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

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

   Однако преимущества абстракции быстро покорили большинство про­граммистов: разработка программ стала более быстрой и надежной, а их машинная зависимость уменьшилась из-за абстрагирования от регистров и машинных команд. Поскольку самыми первыми на компьютерах рассчитыва­лись научные задачи, Fortran стал стандартным языком в науке и технике, и только теперь на смену ему приходят другие языки. Fortran был неоднократно модернизирован (1966,1977,1990) с тем, чтобы адаптировать его к требовани­ям современных программных разработок.

 

 

х для обработки коммерческих данных.

Cobol и PL/1

   Язык Cobol был разработан в 1950- х для обработки коммерческих данных. Он создавался комитетом, состоящим из представителей Министерства Обороны США, производителей компьютеров и коммерческих организаций типа стра­ховых компаний. Предполагалось, что Cobol — это только временное решение, необходимое, пока не создан лучший проект; однако язык быстро стал самым распространенным в своей области (как Fortran в науке), причем по той же самой причине: он обеспечивал естественные средства выражения вычисле­ний, типичных для своей области. При обработке коммерческих данных не­обходимо делать относительно простые вычисления для большого числа сложных записей данных, а по возможностям структурирования данных Cobol намного превосходит алгоритмические языки типа Fortran или С.

    IBM позже создала язык PL/1, универсальный, обладающий всеми свой­ствами языков Fortran, Cobol и Algol. PL/1 заменил Fortran и Cobol на мно­гих компьютерах IBM, но этот язык очень широкого диапазона никогда не поддерживался вне IBM, особенно на мини- и микроЭВМ, которые все больше и больше используются в организациях, занимающихся обработкой данных.

 

 

Algol и его потомки

   Из ранних языков программирования Algol больше других повлиял на созда­ние языков. Разработанный международной группой первоначально для об­щих и научных приложений, он никогда не достигал такой популярности, как Fortran, поскольку не имел той поддержки, которую Fortran получил от боль­шинства производителей компьютеров. Описание первой версии языка Algol было опубликовано в 1958 г.; пересмотренная версия, Algol 60, широко ис­пользовалась в компьютерных научных исследованиях и была реализована на многих машинах, особенно в Европе. Третья версия языка, Algol 68, пользова­лась влиянием среди теоретиков по языкам, хотя никогда широко не приме­нялась.

    От языка Algol произошли два важных языка: Jovial, который использовался Военно-воздушными силами США для систем реального времени, и Simula, один из первых языков моделирования.

наиболее известным его потомком является

Но, возможно, наиболее известным его потомком является Pascal, разработанный в конце 1960-х Никлаусом Виртом. Целью разработки было создание языка, который можно было бы использовать для демонстрации идей объявления типов и контроля их соответствия. В после­дующих главах мы докажем, что эти концепции относятся к наиболее важным, когда-либо предлагавшимся в проектировании языков.

   Как язык практического программирования Pascal имеет одно большое преимущество и один большой недостаток. Первоначальный компилятор языка Pascal был написан на самом языке Pascal и, таким образом, мог быть легко перенесен на любой компьютер. Язык распространялся быстро, особен­но на создаваемых в то время мини- и микроЭВМ. К сожалению, как язык, Pascal слишком мал. Стандартный Pascal вообще не имеет никаких средств для деления программы на модули, хранящиеся в отдельных файлах, и поэто­му не может использоваться для программ объемом больше нескольких тысяч строк. Компиляторы Pascal, используемые на практике, поддерживают деком­позицию на модули, но никаких стандартных методов для этого не существу­ет, так что большие программы непереносимы. Вирт сразу понял, что модули являются необходимой частью любого практического языка, и разработал язык Modula. Modula (теперь в версии 3, поддерживающей объектно-ориенти­рованное программирование) — популярная альтернатива нестандартным «диалектам» языка Pascal.

 

С

   Язык С был разработан в начале 1970-х Деннисом Ричи, сотрудником Bell Laboratories, как язык реализации операционной системы UNIX. Операцион­ные системы традиционно писали на ассемблере, поскольку языки высокого уровня считались неэффективными. Язык С абстрагируется от деталей программирования, присущих ассемблерам, предлагая структурированные управ­ляющие операторы и структуры данных (массивы и записи) и сохраняя при этом всю гибкость ассемблерного низкоуровневого программирования (указа­тели и операции на уровне битов).

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

и прикладные программы выходили из

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

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

  

   Язык С был стандартизирован в 1989 г. Американским Национальным Ин­ститутом Стандартов (ANSI); практически тот же самый стандарт был принят Международной Организацией по Стандартизации (ISO) годом позже. В этой книге делаются ссылки на ANSI С, а не на более ранние версии языка.

 

C++

   В 1980-х годах Бьярн Строуструп, также из Bell Laboratories, использовал С как базис языка C++, добавив поддержку объектно-ориентированного програм­мирования, аналогичную той, которую предоставлял язык Simula. Кроме то­го, в C++ исправлены многие ошибки языка С, и ему следует отдавать пред­почтение даже в небольших программах, где объектно-ориентированные свойства, возможно, и не нужны. C++ — наиболее подходящий язык для об­новления систем, написанных на С.

   Обратите внимание, что C++ — развивающийся язык, и в вашем справоч­ном руководстве или компиляторе, возможно, отсутствуют последние изме­нения. Обсуждаемый в этой книге язык соответствует книге Annotated C++ Reference Мanual Эллиса и Строуструпа (издание 1994 г.), которая является ос­новой рассматриваемого в настоящее время стандарта.

Ada

   В 1977 г. Министерство Обороны Соединенных Штатов решило провести унификацию языка программирования, в основном, чтобы сэкономить на обучении и стоимости поддержки операционных сред разработки программ для различных военных систем.

После оценки существующих языков было

После оценки существующих языков было принято решение провести конкурс на разработку нового языка, положив в основу хороший существующий язык, такой как Pascal. В конце концов был выбран язык, который назвали Ada, и стандарт был принят в 1983 г. Язык Ada уникален в ряде аспектов:

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

• Многие языки первоначально были реализованы на единственном ком­пьютере, и на них сильно повлияли особенности этого компьютера. Язык Ada был разработан для написания переносимых программ.

• Ada расширяет область применения языков программирования, обеспечи­вая обработку ошибок и параллельное программирование, что традицион­но считалось (нестандартными) функциями операционных систем.

   Несмотря на техническое совершенство и преимущества ранней стандар­тизации, язык Ada не достиг большой популярности вне военных и других крупномасштабных проектов (типа коммерческой авиации и железнодорож­ных перевозок). Язык Ada получил репутацию трудного. Это связано с тем, что он поддерживает многие аспекты программирования (параллелизм, обра­ботку исключительных ситуаций, переносимые числовые данные), которые другие языки (подобные С и Pascal) оставляют операционной системе. На са­мом деле его нужно просто больше изучать. К тому же первоначально были недоступны хорошие и недорогие среды разработки для сферы образования. Теперь, когда есть бесплатные компиляторы (см. приложение А) и хорошие учебники, Ada все чаще и чаще встречается в учебных курсах даже как «пер­вый» язык.

 

 

 

Ada 95

   Ровно через двенадцать лет после принятия в 1983 г. первого стандарта языка Ada был издан новый стандарт.

В новой версии, названной Ada

В новой версии, названной Ada 95, исправле­ны некоторые ошибки первоначальной версии, но главное — это добавление поддержки настоящего объектно-ориентированного программирования, включая наследование, которого не было в Ada 83, так как его считали неэф­фективным. Кроме того, Ada 95 содержит приложения, в которых описываются стандартные (но необязательные) расширения для систем реального вре­мени, распределенных систем, информационных систем, защищенных сис­тем, а также «числовое» (numerics) приложение.

   В этой книге название «Ada» будет использоваться в тех случаях, когда об­суждение не касается особенностей одной из версий: Ada 83 или Ada 95. Заме­тим, что в литературе Ada 95 упоминалась как Ada 9X, так как во время разра­ботки точная дата стандартизации не была известна

.

1.3. Языки, ориентированные на данные

 

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

 

Lisp

  Основная структура данных в языке Lisp — связанный список. Первоначаль-но Lisp был разработан для исследований в теории вычислений, и многие ра­боты по искусственному интеллекту были выполнены на языке Lisp. Язык был настолько важен, что компьютеры разрабатывались и создавались так, чтобы оптимизировать выполнение Lisp-программ. Одна из проблем языка состояла в обилии различных «диалектов», возникавших по мере того, как язык реализовывался на различных машинах. Позже был разработан стандар­тный язык Lisp, чтобы программы можно было переносить с одного компью­тера на другой. В настоящее время популярен «диалект» языка Lisp — CLOS, поддерживающий объектно-ориентированное программирование.

Три основные команды языка Lisp

   Три основные команды языка Lisp — это car(L) и cdr(L), которые извлека­ют, соответственно, начало и конец списка L, и cons(E, L), которая создает но­вый список из элемента Е и существующего списка L. Используя эти коман­ды, можно определить функции обработки списков, содержащих нечисловые данные; такие функции было бы довольно трудно запрограммировать на языке Fortran.

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

 

 

 

 

 

APL

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

   Предположим, что задана векторная переменная:

V= 1 5 10 15 20 25

   Операторы языка APL могут работать непосредственно с V без записи цик­лов с индексами:

+ /V      =76 Свертка сложением(суммирует элементы)

 фV        =   25 20 15 10 5 1          Обращает вектор

2 3 pV  =        1        5    10 Переопределяет размерность

                 V 15      20    25            как матрицу 2x3

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

Snobol, Icon

    Первые языки имели дело практически только с числами.

в таких областях, как обработка

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

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

line := 0                                                                   # Инициализировать счетчик строк               while s := read() {                                                    # Читать до конца файла

             every col := find("the", s) do                      # Генерировать позиции столбца                                               write (line, " ",col)                                                   # Write(line,col) для "the"

line := line+ 1

}

     Эта программа записывает номера строк и столбцов всех вхождений стро­ки "the" в файл. Если команда find не находит ни одного вхождения, то она «терпит неудачу» (fail), и вычисление выражения завершается. Ключевое сло­во every вызывает повторение вычисления функции до тех пор, пока оно за­вершается успешно.

     Выражения Icon содержат не только строки, которые представляют собой последовательности символов; они также определены над наборами символов csets. Таким образом

vowels := 'aeiou'

 

присваивает переменной vowel (гласные) значение, представляющее собой набор указанных символов. Это можно использовать в функциях типа upto(vowels,s), генерирующих последовательность позиций гласных в s, и many(vowels,s), возвращающих самую длинную начальную последователь­ность гласных в s.

Более сложная функция bal подобна

     Более сложная функция bal подобна upto за исключением того, что она ге­нерирует последовательности позиций, которые сбалансированы по «ско­бочным» символам:

bal(' +-*/','([', ')]',*)

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

"х + (у [u/v] - 1 )*z", вышеупомянутое выражение сгенерирует индек­сы, соответствующие подстрокам:

x

x+(y[u/v]-1

   Первая подстрока сбалансирована, так как она заканчивается «+» и не содержит никаких скобок; вторая подстрока сбалансирована, поскольку она завершается символом «*» и имеет квадратные скобки, правильно вложенные внутри круглых скобок.

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

line := 0                                                                    # Инициализировать счетчик строк            while s := read() {                                                    # Читать до конца файла                                                                    every col := (upto (vowels, line) > 1 ) do

                                                                                 # Генерировать позиции столбца                                 write (line, " ",col)                                                   # write(line,col) для гласных

 line := line + 1

}

 

     Функция поиска генерирует индекс, который затем проверяется на «>». Если проверка неуспешна (не говорите: «если результат ложный»), программа возвращает управление генерирующей функции upto, чтобы получить новый индекс.

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

в Icon очень интересен встроенный

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

 

 

 

 

 

 

 

SETL

Основная структура данных в SETL — множество. Так как множество — наи­более общая математическая структура, с помощью которой определяются все другие математические структуры, то SETL может использоваться для со­здания программ высокой степени общности и абстрактности и поэтому очень коротких. Такие программы имеют сходство с логическими программа­ми (гл. 17), в которых математические описания могут быть непосредственно исполняемыми. В теории множеств используется нотация: {х \р(х)}, обозна­чающая множество всех х таких, что логическое выражение р(х) является ис­тиной. Например, множество простых чисел в этой нотации может быть запи­сано как

{ п \ -,3 т [(2<т<п— 1) л (nmodm = 0)]}

Эта формула читается так: множество натуральных чисел п таких, что не cуществует натурального т от 2 до п — 1 , на которое п делится без остатка.

     Чтобы напечатать все простые числа в диапазоне от 2 до 100, достаточно «протранслировать» это определение в однострочную программу на языке SETL:

print ({n in {2.. 100} | not exists m in {2.. n — 1} | (n mod m) = 0});

 

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

   Языки, ориентированные на данные, сейчас несколько менее популярны, чем раньше, отчасти потому, что объектно-ориентированные методы позво­ляют внедрить операции, ориентированные на данные, в обычные языки ти­па C++ и Ada, а также из-за конкуренции более новых языковых концепций, таких как функциональное и логическое программирование.

Тем не менее эти языки

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

 

1.4. Объектно-ориентированные языки

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

    Первый объектно-ориентированный язык программирования Simula был создан в 1960-х годах К. Нигаардом и О.-Дж. Далом для моделирования сис­тем: каждая подсистема, принимающая участие в моделировании, програм­мировалась как объект. Так как возможно существование нескольких экзем­пляров одной подсистемы, то можно запрограммировать класс для описания каждой подсистемы и выделить память для объектов этого класса.

    Исследовательский центр Xerox Palo Alto Research Center популяризировал ООП с помощью языка Smalltalk. Такие же исследования вели к системам окон, так популярным сегодня, но важное преимущество Smalltalk заключает­ся в том, что это не только язык, но и полная среда программирования. В тех­ническом плане Smalltalk был достижением как язык, в котором классы и объ­екты являются единственными конструкциями структурирования, так что нет необходимости встраивать эти понятия в «обычный» язык.

    Технический аспект этих первых объектно-ориентированных языков по­мешал более широкому распространению ООП: отведение памяти, диспетче­ризация операций и контроль соответствия типов осуществлялись динамиче­ски (во время выполнения), а не статически (во время компиляции).

ге программы на этих языках

Не вда­ваясь в детали (см. соответствующий материал в гл. 8 и 14), отметим, что в ито­ ге программы на этих языках связаны с неприемлемыми для многих систем накладными расходами по времени и памяти. Кроме того, статический кон­троль соответствия типов (см. гл. 4) теперь считается необходимым для раз­работки надежного программного обеспечения. По этим причинам в языке Ada 83 реализована только частичная поддержка ООП.

    Язык C++ показал, что можно реализовать полный механизм ООП спосо­бом, который совместим со статическим распределением памяти и контро­лем соответствия типов и с фиксированными затратами на диспетчеризацию: динамические механизмы ООП используются только, если они необходимы до существу. Поддержка ООП в Ada 95 основана на тех же идеях, что и в C++.

 

    Однако нет необходимости «прививать» поддержку ООП в существующие языки, чтобы получить эти преимущества. Язык Eiffel подобен Smalltalk в том, что единственным методом структурирования является метод классов и объ­ектов, а также подобен C++ и Ada 95 в том, что проверка типов статическая, а реализация объектов может быть как статической, так и динамической, если нужно. Простота языка Eiffel по сравнению с гибридами, которым «привита» полная поддержка ООП, делает его превосходным выбором в качестве первого  языка программирования.

   Мы обсудим языковую поддержку ООП более подробно, сначала в C++, а затем в Ada 95. Кроме того, краткое описание Eiffel покажет, как выглядит «чистый» язык ООП.

 

1.5. Непроцедурные языки

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

как правило, представляют собой языки

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

    Другой подход к абстрактному программированию состоит в том, чтобы описывать вычисление, используя уравнения, функции, логические импликации или другие формализмы подобного рода. Благодаря математическим формализмам определенные таким образом языки оказываются действи­тельно универсальными, выходящими за рамки конкретных прикладных областей. Компилятор реально не преобразует программу в машинные коды; скорее, он пытается решать математическую проблему и ее решение выдает в качестве результата. Так как абстракция оставляет индексы, указатели, циклы и т. п. вне языка, эти программы могут быть на порядок короче обычных про­грамм. Основная проблема описательного программирования состоит в том, что «процедурные» задачи, например ввод-вывод на экран или диск, плохо «укладываются» в эту концепцию, и для этих целей языки должны быть до­полнены обычными конструкциями программирования.

    Мы обсудим два формализма непроцедурных языков: 1) функциональное программирование (гл. 16), которое основано на математическом понятии чистой функции, такой как sin и log, которые не изменяют своего окружения в отличие от так называемых функций обычного языка типа С, которые могут иметь побочные эффекты; 2) логическое программирование (гл. 17), в кото­ром программы выражены как формулы математической логики и «компиля­тор», чтобы решить задачу, пытается вывести логические следствия из этих формул.

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

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

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

 

1.6. Стандартизация

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

    Стандарты существуют (или находятся в стадии подготовки) для большин­ства языков, обсуждаемых в этой книге. К сожалению, обычно стандарт пред­лагается спустя годы после широкого распространения языка и должен сохра­нять машинно-зависимые странности ранних реализаций. Язык Ada — иск­лючение в том смысле, что стандарты (1983 и 1995) создавались и оценивались одновременно с проектом языка и первоначальной реализацией. Более того, стандарт ориентирован на то, чтобы компиляторы можно было сравнивать по производительности и стоимости, а не только на соответствие стандарту.

Компиляторы зачастую могут предупреждать вас,

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

 

 

 

 

 

 

 

 

 

 

 

1.7. Архитектура компьютера

   Поскольку мы рассматриваем языки программирования с точки зрения их практического использования, мы включаем короткий раздел по архитектуре компьютеров, чтобы согласовать минимальный набор терминов. Компьютер состоит из центрального процессора (ЦП) и памяти (рис. 1.1). Устройства вво­да-вывода могут рассматриваться как частный случай памяти.

          

рис. 1 . 1 . Архитектура компьютера.

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

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

• Доступ к памяти. Загрузить (load) содержимое слова памяти в регистр и сохранить (store) содержимое регистра в слове памяти.

• Арифметические команды типа сложить (add) и вычесть (sub). Эти дей­ствия выполняются над содержимым двух регистров (или иногда над со­держимым регистра и содержимым слова памяти).

и перейти. ЦП может сравнивать

Результат остается в регистре. Например, команда

add m,N   R1,N

складывает содержимое слова памяти N с содержимым регистра R1 и ос­тавляет результат в регистре.

• Сравнить и перейти. ЦП может сравнивать два значения, такие как со­держимое двух регистров; в зависимости от результата (равно, больше, и т.д.) указатель команды изменяется, переходя к другой команде. На­пример:

jump_eq        R1.L1

                                                                    …

                                                            L1:   ...

заставляет ЦП продолжать вычисление с команды с меткой L1, если со-держимое  R1 — ноль; в противном случае вычисление продолжается со следующей команды.

    Во многих компьютерах, называемых Компьютерами с Сокращенной Системой команд команд (RISC— Reduced Instruction Set Computers), имеются только такие элементарные команды.Обосновывается это  тем, что ЦП, который должен выполнять всего несколько простых команд, может быть очень быст­рым. В других компьютерах, известных как CISC (Complex Instruction Set Computers), определен Сложный Набор команд, позволяющий упростить как программирование на языке ассемблера, так и конструкцию компилятора. Обсуждение этих двух подходов выходит за рамки этой книги; у них достаточ­но много общего, так что выбор не будет иметь для нас существенного значе­ния.

     Память — это набор ячеек, в которых можно хранить данные. Каждая ячейка памяти, называемая словом памяти, имеет адрес, а каждое слово состо­ит из фиксированного числа битов, обычно из 16, 32 или 64 битов. Возможно, что Компьютер умеет загружать и сохранять 8-битовые байты или двойные слова из 64 битов.

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

нотацию С:

Современные компьютеры широко используют индексные

load R3, # 54                                                         Загрузить значение 54 в R3 load           

 R2, &N                                                                 Загрузить адрес N в R2

    Следующий способ — это абсолютная адресация, в которой обычно ис­пользуется символический адрес переменной:

              load       R3,54               Загрузить содержимое адреса 54     

              load       R4, N               Загрузить содержимое переменной N

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

           

             load       R3,54(R2)           Загрузить содержимое addr(R2) + 54

             load       R4, (R1)              Загрузить содержимое addr(R1) + О

где первая команда означает «загрузить в регистр R3 содержимое слова памя­ти, чей адрес получен, добавлением 54 к содержимому (индексного) регистра R2»; вторая команда — это частный случай, когда содержимое регистра R1 ис­пользуется просто как адрес слова памяти, содержимое которого загружается в R4. Индексные регистры необходимы для эффективной реализации циклов и массивов.

 

Кэш и виртуальная память

     Одна из самых трудных проблем, стоящих перед архитекторами компьюте­ров, — это приведение в соответствие производительности ЦП и пропускной способности памяти. Быстродействие ЦП настолько велико по сравнению со временем доступа к памяти, что память не успевает поставлять данные, что­бы обеспечить непрерывную работу процессора. Для этого есть две причины: 1) в компьютере всего несколько процессоров (обычно один), и в них можно использовать самую быструю, наиболее дорогую технологию, но объем памя­ти постоянно наращивается и технология должна быть менее дорогая; 2) ско­рости настолько высоки, что ограничивающим фактором является быстрота, с которой электрический сигнал распространяется по проводам между ЦП и памятью.

Решением проблемы является использование иерархии

    Решением проблемы является использование иерархии блоков памяти, как показано на рис. 1.2. Идея состоит в том, чтобы хранить неограниченное количество команд программы и данных в относительно медленной (и недо­рогой) памяти и загружать порции необходимых команд и данных в меньший объем быстрой (и дорогой) памяти. Если в качестве медленной памяти ис пользуется диск, а в качестве быстрой памяти — обычная оперативная память с произвольным



доступом (RAM — Random Access Memory), то концепция называется виртуальной памятью или страничной памятью. Если медленной памятью является RAM, а быстрой — RAM, реализованная по более быстрой технологии, то концепция называется кэш-памятью.

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

х годах, еще до того,

1.8.  Вычислимость

 

В 1930- х годах, еще до того, как были изобретены компьютеры, логики иссле­довали абстрактные концепции вычисления. Алан Тьюринг и .Алонзо Черч независимо предложили чрезвычайно простые модели вычисления (назван­ные соответственно машинами Тьюринга и Лямбда-исчислением) и затем вы­двинули следующее утверждение (известное как Тезис Черча —Тьюринга):

    Любое исполнимое вычисление может быть выполнено на любой из этих моделей.

  

    Машины Тьюринга чрезвычайно просты; если воспользоваться синтак­сисом языка С, то объявления данных будут выглядеть так:

    char tape[...];

    int current = 0;

где лента (tape) предполагается бесконечной. Программа состоит из любого числа операторов вида:

             L17:        if (tape[currentj == 'g') {

                                         tape[current++] = 'j'i

                                         goto L43;

                                      }

Оператор машины Тьюринга выполняется за четыре следующих шага.

• Считать и проверить символ в текущей ячейке ленты.

• Заменить символ на другой символ (необязательно).

• Увеличить или уменьшить указатель текущей ячейки.

• Перейти к другому оператору.

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

• Исследователи предложили множество моделей вычислений, и было до­казано, что все они эквивалентны машинам Тьюринга.

• Никому пока не удалось описать вычисление, которое не может быть ре­ализовано машиной Тьюринга.

    Так как машину Тьюринга можно легко смоделировать на любом языке программирования, можно сказать, что все языки программирования «дела­ют» одно и то же, т. е. в некотором смысле эквивалентны.

 

1.9. Упражнения

1. Опишите, как реализовать компилятор для языка на том же самом язы­ке («самораскрутка»).

Составьте список полезных команд над

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

3. Составьте список полезных команд над строками и сравните ваш список со встроенными командами языков Snobol и Icon.

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

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

Глава 2

Элементы

языков программирования

2.1. Синтаксис

  Как и у обычных языков, у языков программирования есть синтаксис:

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

     Синтаксис задается с помощью формальной нотации.

    Самая распространенная формальная нотация синтаксиса — это расширен­ная форма Бекуса — Наура (РБНФ). В РБНФ мы начинаем с объекта самого верхнего уровня, с программы, и применяем правила декомпозиции объектов, пока не достигнем уровня отдельного символа. Например, в языке С синтак­сис условного оператора (if-оператора) задается правилом:

      

                  if-onepamop  :: = if (выражение) оператор [else оператор]

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

[ ]      Не обязательный        {}    Ноль или более повторений          | Или

Таким образом, else-оператор в if-операторе не является обязательным. Использование фигурных скобок можно продемонстрировать на (упрощен­ном) правиле для объявления списка переменных:

Объявление-переменной ::= спецификатор-типа идентификатор {, идентификатор};

Это читается так: объявление переменной

     Это читается так: объявление переменной представляет собой специфика­тор типа, за которым следует идентификатор (имя переменной) и необяза­тельная последовательность идентификаторов, предваряемых запятыми, в конце ставится точка с запятой.

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



.  

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

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

Будьте внимательны с ограничениями на длину идентификаторов. Ес­ли значимы только первые 10 символов, то current_winner и current _width будут представлять один и тот же идентификатор.

Многие языки не чувствительны к регистру, то есть СЧЕТ и счет пред-ставляют одно и то же имя. Язык С чувствителен к регистру, поэтому эти имена представляют два разных идентификатора. При разработке чувст­вительных к регистру языков полезно задать четкие соглашения по ис­пользованию каждого регистра, чтобы случайные опечатки не приводи­ли к ошибкам. Например, по одному из соглашений языка С в програм­ме все записывается на нижнем регистре за исключением определенных имен констант, которые задаются на верхнем регистре.

Существуют две формы комментариев: комментарии в языках Fortran, Ada и C++ начинаются с символа (С, - -, и //, соответственно) и распро­страняются до конца строки, в то время как а языках С и Pascal коммента­рии имеют как начальный, так и конечный символы: /* ... */ в.С и (* ... *) иди {...} в Pascal.

но при этом существует опасность

Вторая форма удобна для «закомментаривания» неис-пользуемого кода  (который, взможнo, был вставлен для тестированя), но при этом существует опасность пропустить конечный символ, в результате чего будет пропущена последовательность операторов:

с

 /*                         Комментарий следовало бы закончить здесь        

а = b + с;             Оператор будет пропущен

/*...*/                   Здесь конец комментария

 Остерегайтесь похожих, но разных символов. Если вы когда-либо изуча­ли математику, то вас должно удивить, что знакомый символ «=» ис­пользуется в языках С и Fortran как оператор присваивания, в то время как новые символы «==» в С и «.eq.» в Fortran используются в качестве операции сравнения на равенство. Стремление написать:

с

          if(a=b)...                     

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

 В качестве исторического прецедента напомним известную проблему с синтаксисом языка Fortran. Большинство языков требует, чтобы слова в программе отделялись одним или несколькими пробелами (или другими пробельными символами типа табуляции), однако в языке Fortran пробель­ные символы игнорируются. Рассмотрим следующий оператор, который определяет «цикл до метки 10 при изменении индекса i от 1 до 100»:

Fortan

do 10 i = 1,100

Если запятая случайно заменена точкой, то этот оператор становится на самом деле.оператором присваивания, присваивая 1.100 переменной, имя которой образуется соединением всех символов перед знаком «=»:

Fortan

do10i = l.TOO

Говорят, эта ошибка заставила ракету взорваться до запуска в космос!

2.2.  Семантика

Семантика — это смысл высказывания (программы) в языке (программи­рования).

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

The pig is in the

The pig is in the pen. (Свинья в загоне.)

The ink is in the pen. (Чернила в ручке.)

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

   Формализованная нотация семантики языков программирования выходит за рамки этой книги. Мы только кратко изложим основную идею. В любой точ­ке выполнения программы мы можем описать ее состояние, определяемое: (1) указателем на следующую команду, которая будет выполнена, и (2) содержимым памяти программы. Семантика команды задается описанием изменения состо­яния, вызванного выполнением команды. Например, выполнение:

а:=25

заменит состояние s на новое состояние s', которое отличается от s только тем, что ячейка памяти а теперь содержит 25.

    Что касается управляющих операторов, то для описания вычисления используется математическая логика. Предположим, что мы уже знаем смыслы двух операторов S1 и S2 в произвольном состоянии s. Обозначим это с по­мощью формул р (S1, s) и р (S2, s) соответственно. Тогда смысл if-оператора:

if С then S1 elseS2

задается формулой:

(C(s)=>p(S1,s))&((-C(s)=>p(S2,s))

     Если вычисление С в состоянии s дает результат истина, то смысл if-опера­тора такой же, как смысл S1; в противном случае вычисление С дает результат не истина и смысл if-оператора такой же, как у S2.

     Как вы можете себе представить, определение семантики операторов цик­ла и вызовов процедур с параметрами может быть очень сложным. Здесь мы удовлетворимся неформальными объяснениями семантики этих конструк­ций языка, как их обычно описывают в справочных руководствах:

     Проверяется условие после if; если результат — истина, выполняется сле­дующий после then оператор, иначе выполняется оператор, следующий за else.

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

По сути, выполнение программы можно

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

      Конечно, «доказанную» правильность программы следует понимать лишь относительно утверждений на входе и выходе, поэтому не имеет смысла доказывать, что программа вычисляет квадратный корень, если вам нужна программа для вычисления кубического корня! Тем не менее верификация про­граммы применялась как мощный метод проверки для систем, от которых требуется высокая надежность. Важнее то, что изучение верификации поможeт вам писать правильные программы, потому что вы научитесь мыслить,  исходя из требований правильности программы. Мы также рекомендуем изучить и использовать язык программирования Eiffel, в который включена под­держка утверждений (см. раздел 11.5).

 

2.3. Данные

   При первом знакомстве & языками программирования появляется тенденция сосредоточивать внимание на действиях: операторах или командах. Только изучив и опробовав операторы языка, мы обращаемся к изучению поддержки, которую обеспечивает язык для структурирования данных. В современных взглядах на программирование, особенно на объектно-ориентированное, опе­раторы считаются средствами манипулирования данными, использующимися для представления некоторого объекта. Таким образом, следует изучить аспек­ты структурирования данных до изучения действий.

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

Ранние языки программирования продолжили эту

Ранние языки программирования продолжили эту традицию идентифицировать сущности языка, подобные переменным, как слова памяти, несмотря на то, что этим переменным припи­сывались математические атрибуты типа целое. В главах 4 и 9 мы объясним, почему int и float — это не математияеское, а скорее, физическое представле-

ние памяти.       

   Теперь мы определим центральную концепцию программирования:

  

Тип — это множество значений и множество операций над этими значениями.

     Правильный смысл int в языке С таков: int — это тип, состоящий из конеч­ного множества значений (количестве примерно 65QOQ или 4 миллиардов, в зависимости от компьютера) и набора операций (обозначенньгх, +, < =, и т.д.) над этими значениями. В таких современных языках программирования, как Ada и C++, есть возможность создавать новые типы. Таким образом, мы боль­ше не ограничены горсткой типов, предопределенных разработчиком языка; вместо этого мы можем создавать собственньхе типы, которые более точно.со-ответствуют решаемой задаче.

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

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

 

Значение. Простейшее неопределяемое понятие.

Литерал. Конкретное значение, заданное в программе «буквально», в виде последовательности символов, например 154, 45.6, FALSE, 'x', "Hello world".

Представление. Значение, представленное внутри компьютера конкретной строкой битов.

жет представляться строкой из восьми

Например, символьное значение, обозначенное 'х', мо­ жет представляться строкой из восьми битов 01111000.

 

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

 

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

 

Объект. Объект — это переменная или константа.

   Обратите внимание, что для переменной должен быть определен конкрет­ный тип по той простой причине, что компилятор должен знать, сколько па­мяти для нее нужно выделить! Константа — это просто переменная, которая не может изменяться. Пока мы не дошли до обсуждения объектно-ориенти­рованного программирования, мы будем использовать знакомый термин «пе­ременная» в более общем смысле, для обозначения и константы, и перемен­ной вместо точного термина «объект».

 

2.4. Оператор присваивания

 

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

ах2 + bх + с = О

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

Скромный оператор присваивания на самом

   Скромный оператор присваивания на самом деле является очень сложным и решает три разные задачи:

1. Вычисление значения выражения в правой части оператора.

2. Вычисление выражения в левой части оператора; выражение должно определять адрес ячейки памяти.

3. Копирование значения, вычисленного на шаге 1, в ячейки памяти, начи­ная с адреса, полученного на шаге 2.

Таким образом, оператор присваивания

a(i + 1) = b + c;

несмотря на внешнее сходство с уравнением, определяет сложное вычисление.

 

 

2.5. Контроль соответствия типов

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

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

   Возможны следующие подходы к контролю соответствия типов:

• Не делать ничего; именно программист отвечает за то, чтобы присваива­ние имело смысл.

• Неявно преобразовать значение выражения к типу, который требуется в левой части.

• Строгий контроль соответствия типов: отказ от выполнения присваива­ния, если типы различаются.

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

в том, что его реализация

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

     Строгий контроль соответствия типов может исключить скрытые ошибки, которые обычно вызываются опечатками или недоразумениями. Это особенно важно в больших программных проектах, разрабатываемых группами програм­мистов; из-за трудностей общения, смены персонала, и т.п. очень сложно объ­единять такое программное обеспечение без постоянной проверки, которой является строгий контроль соответствия типов. Фактически, строгий конт­роль соответствия типов пытается превратить ошибки, возникающие во вре­мя выполнения программы, в ошибки, выявляемые при компиляции. Ошиб­ки, проявляющиеся только во время выполнения, часто чрезвычайно трудно найти, они опасны для пользователей и дорого обходятся разработчику про­граммного обеспечения в смысле отсрочки сдачи программы и испорченной репутации. Цена ошибки компиляции незначительна: вам, вероятно, даже не требуется сообщать своему начальнику, что во время компиляции произошла ошибка.

2.6. Управляющие операторы

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

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

Есть два класса хорошо структурированных

Есть два класса хорошо структурированных управ­ляющих операторов.

  

   • Операторы выбора, которые выбирают одну из двух или нескольких альтернативных последовательностей выполнения: условные операто­ры (if) и переключатели (case или switch).

 

 • Операторы цикла, в которых повторяется выполнение последовательно­сти операторов: операторы for и while.

   Хорошее понимание циклов особенно важно по двум причинам: 1) боль­шая часть времени при выполнении будет (очевидно) потрачена на циклы, и 2) многие ошибки связаны с неправильным кодированием начала или конца цикла.

 

 

2.7. Подпрограммы

Подпрограмма — это программный сегмент, состоящий из объявлений дан­ных и исполняемых операторов, которые можно неоднократно вызывать (call) из различных частей программы. Подпрограммы называются процедура­ми (procedure), функциями (function), подпрограммами (subroutine) или метода­ми (method). Первоначально они использовались только для того, чтобы раз­решить многократное использование сегмента программы. Современная точ­ка зрения состоит в том, что подпрограммы являются важным элементомструктуры программы и что каждый сегмент программы, который реализует не­которую конкретную задачу, следует оформить как отдельную подпрограмму.

   

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

2.8. Модули

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

software engineering) используется для обозначения

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

    Возможно, вам говорили, что отдельная подпрограмма не должна превы­шать 40 или 50 строк, потому что программисту трудно читать и понимать большие сегменты кода. Согласно тому же критерию, должно быть понятно взаимодействие 40 или 50 подпрограмм. Отсюда следует очевидный вывод: любую программу, в которой больше 1600 — 2500 строк, трудно понять! Так как в полезных программах могут быть десятки тысяч строк и нередки систе­мы из сотен тысяч строк, то очевидно, что необходимы дополнительные структуры для создания больших систем.

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

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

• Необходима мощная среда, разработки программ, чтобы отслеживать «истории», модулей и проверять интерфейсы. ;

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

Однако это больше не является

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

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

   Несмотря на тот факт, что невозможно научить здравому смыслу в проек­тировании программ, есть некоторые принципы, которые можно изучить. Одним из основных методов декомпозиции программы является объектно-ориентированное программирование (ООП), опирающееся на концепцию типа, рассмотренную выше. Согласно ООП, модуль следует создавать для любого реального или абстрактного «объекта», который может представляться набо­ром данных и операций над этими данными. В главах 14 и 15 детально обсуж­дается языковая поддержка ООП.

 

2.9. Упражнения

1. Переведите синтаксис (отдельные фрагменты) языков С или Ada из нор­мальной формы Бекуса — Наура в синтаксические диаграммы.

2. Напишите программу на языке Pascal или С, которая компилируется и выполняется, но вычисляет неправильный результат из-за незакрытого комментария.

3. Даже если бы язык Ada использовал стиль комментариев, как в языках С и Pascal, то ошибки, вызванные незакрытыми комментариями, были бы менее частыми, Почему?

4. В большинстве языков ключевые слова, подобные begin и while, зарезер­вированы и не могут использоваться как идентификаторы.

В других языках типа Fortran

В других языках типа Fortran и PL/1 нет зарезервированных ключевых слов. Ка­ковы преимущества и недостатки зарезервированных слов?

Глава 3

Среды программирования

 

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

 

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

 

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

 

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

 

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

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

 

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

 

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

 

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

 

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

 

Средства конфигурирования автоматизируют создание программ и просле­живают изменения до уровня исходных файлов.

Интерпретатор непосредственно выполняет исходный код программы в от­личие от компилятора, переводящего исходный файл в объектный.

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

в чрезвычайной простоте интерфейса пользователя:

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

3.1. Редактор

 

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

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

3.2. Компилятор

 

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

Язык L1 эффективнее языка L2.

Правильно же то, что компилятор С1 может сгенерировать более эффек­тивный код, чем компилятор С2, или что легче эффективно откомпилировать конструкции L1, чем соответствующие конструкции L2.

Одна из целей этой книги

Одна из целей этой книги — показать соотношение между конструкциями языка и получающим­ся после компиляции машинным кодом.

    Структура компилятора показана на рис. 3.1. Входная часть компилятора



«понимает» программу, анализируя синтаксис и семантику согласно прави­лам языка. Синтаксический анализатор отвечает за преобразование последова­тельности символов в абстрактные синтаксические объекты, называемые лек­семами. Например, символ «=» в языке С преобразуется в оператор присваива­ния, если за ним не следует другой «=»; в противном случае оба соседних сим­вола «=» (т.е. «==») преобразуются в операцию проверки равенства. Анализа­тор семантики отвечает за придание смысла этим абстрактным объектам. На­пример, в следующей программе семантический анализатор выделит глобаль­ный адрес для первого i и вычислит смещение параметра — для второго i:

с

static int i;

void proc(inti) {... }

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

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

   Выходная часть компилятора берет промежуточное представление про­граммы и генерирует машинный код для конкретного компьютера. Таким об­разом, входная часть является языковозависимой, в то время как выходная — машиннозависимой. Поставщик компиляторов может получить семейство ком­пиляторов некоторого языка L для ряда самых разных компьютеров Cl, C2,..., написав несколько выходных частей, использующих промежуточное представление общей входной части.

Точно так же поставщик компьютеров

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

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

• Оптимизация промежуточного представления, например нахождение общего подвыражения:

a = f1 (x + y) + f2(x + y);

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

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

• Локальная оптимизация обычно выполняется для сгенерированных ко­манд, хотя иногда ее можно проводить для промежуточного представле­ния. В этой методике делается попытка заменять короткие последователь­ности команд одной, более эффективной командой. Например, в языке С выражение n++ может быть скомпилировано в следующую последователь­ность:

load R1,n

add R1,#1

store R1,n

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

incr n

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

тор при отладке лучше отключать.

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

с

 

transmit_register = 0x70; /* Ждать 1 секунду */ transmit_register = 0x70;

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

3.3. Библиотекарь

 

   Можно хранить объектные модули либо в отдельных файлах, либо в одном файле, называемом библиотекой. Библиотеки могут поставляться с компи­лятором, либо приобретаться отдельно, либо составляться программис­том.

   Многие конструкции языка программирования реализуются не с по­мощью откомпилированного кода, выполняемого внутри программы, а через обращения к процедурам, которые хранятся в библиотеке, предусмотренной поставщиком компилятора. Из-за увеличения объема языков программиро­вания наблюдается тенденция к размещению большего числа функциональ­ных возможностей в «стандартных» библиотеках, которые являются неотъем­лемой частью языка. Так как библиотека — это всего лишь структурированная совокупность типов и подпрограмм, не содержащая новых языковых конст­рукций, то она упрощает задачи как для студента, который должен изучить язык, так и для разработчика компилятора.

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

если высокоточная арифметика реализована библиотечными

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

 

 

 

 

 

 

 

 

 

 

3.4. Компоновщик

 

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

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

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

с динамической загрузкой, при этом

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

 

3.5. Загрузчик

Как подразумевает название, загрузчик загружает программу в память и инициализирует ее выполнение. На старых компьютерах загрузчик был не-тривиален, так как должен был решать проблему перемещаемости программ. Такая команда, как load 140, содержала абсолютный адрес памяти, и его приходилось настраивать в зависимости от конкретных адресов, в которые загружалась программа. В современных компьютерах адреса команд и данных задаются относительно значений в регистрах. Для каждой области памяти с программой или данными выделяется регистр, указывающий на начало этой области, поэтому все, что должен сделать загрузчик теперь, — это скопировать программу в память и инициализировать несколько регистров. Команда load 140 теперь означает «загрузить значение, находя­щееся по адресу, полученному прибавлением 140 к содержимому регистра, который указывает на область данных».

 

 

 

 

 

 

 

 

 

 

3.6. Отладчик

Отладчики поддерживают три функции.

 

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

 

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

 

Проверка/изменение данных. Возможность посмотреть и изменить значе­ние любой переменной в любой точке вычисления.

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

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

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

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

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

 

 

3.7. Профилировщик

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

В этой книге мы обсудим

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

• Текущая эффективность программы неприемлема.

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

• Можно выявить причину неэффективности.

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

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

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

3.8. Средства тестирования

    Тестирование большой системы может занять столько же времени, сколько и программирование вместе с отладкой. Для автоматизации отдельных аспек­тов тестирования были разработаны программные инструментальные средст­ва. Одно из них — анализатор покрытия (coverage analyzer), который отслежи­вает, какие команды были протестированы.

Более сложные инструментальные средства выполняют

Однако такой инструмент не по­могает создавать и выполнять тесты.

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

3.9. Средства конфигурирования

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

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

Инструментальные средства управления изменениями упрощают

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

3.10. Интерпретаторы

 

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

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



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

    Первоначально Pascal-компилятор был написан для получения ма­шинного кода конкретной машины (CDC 6400). Немного позже Никлаус Вирт создал компилятор, который вырабатывал код, названный Р-кодом, для абстрактной стековой машины. Написав интерпретатор для Р-кода или компилируя Р-код в машинный код конкретной машины, можно создать интерпретатор или компилятор для языка Pascal, затратив относительно небольшие усилия.

---

---