WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

Pages:   || 2 |

«Пышкин Е.В. СТРУКТУРНОЕ ПРОЕКТИРОВАНИЕ: ОСНОВАНИЕ И РАЗВИТИЕ МЕТОДОВ С примерами на языке C++ Учебное пособие Санкт-Петербург Издательство Политехнического университета УДК ...»

-- [ Страница 1 ] --

Пышкин Е.В.

СТРУКТУРНОЕ ПРОЕКТИРОВАНИЕ:

ОСНОВАНИЕ И РАЗВИТИЕ МЕТОДОВ

С примерами на языке C++

Учебное пособие

Санкт-Петербург

Издательство Политехнического университета

УДК 004.415.2:004.43 (075.8)

ББК 32.973-018я73

Пышкин Е.В. Структурное проектирование: основание и развитие

методов. С примерами на языке C++: Учеб. пособие. – СПб.: Изд-во

Политехнического ун-та, 2005. – 324 с., ил.

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

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

Учебное пособие может быть использовано при проведении занятий по курсам «Алгоритмизация и теория программирования», «Программирование на языке высокого уровня», «Теория и технология программирования» и при изучении смежных дисциплин студентами, обучающимися по специальностям 210100 «Информатика и управление в технических системах», 230100 «Вычислительные машины, комплексы, системы и сети», 230105 «Программное обеспечение вычислительной техники и автоматизированных систем». Материалы учебного пособия могут использоваться студентами, обучающимися по программе второго высшего образования, а также для самообразования.



Рекомендовано к изданию кафедрой автоматики и вычислительной техники факультета технической кибернетики.

Табл. 9. Ил. 150. Библиогр.: 79 назв.

© Пышкин Евгений Валерьевич, 2005 © Санкт-Петербургский государственный политехнический университет, 2005 ISBN 5-7422-1000-0 Мы структурируем программы, чтобы облегчить их модификацию; в конце концов, программы тем и отличаются от «железа», что их можно менять Мартин Фаулер Глаз следует путями, проложенными для него в произведении Пауль Клее... элемент не предшествует в своем существовании целому, он не опережает целое и не одновременен с ним, не отдельные элементы определяют целое, но целое определяет свой элементный состав: знание о законах целого и о его структуре невозможно было бы вывести из информации о его отдельных частях Жорж Перек Одного формализма недостаточно, поскольку он ведет к малопонятным деталям; точно так же недостаточно одного здравого смысла и интуиции (...), поскольку им сопутствует много ошибок и плохих решений. Что необходимо - это тонкое равновесие между ними Дэвид Грис... профессиональное использование иерархической декомпозиции в сочетании с пошаговым уточнением структур данных – более важные инструменты разработки программного обеспечения, поскольку они не зависят от выбранной формы реализации (функциональноориентированной или объектноориентированной) Михаил Федорович Лекарев Об авторе этой книги Пышкин Евгений Валерьевич – кандидат технических наук, доцент кафедры автоматики и вычислительной техники Санкт-Петербургского государственного политехнического университета.

Области интересов автора в научной и преподавательской деятельности связаны с изучением современных моделей и технологий программирования. Опубликовал ряд книг и статей по различным аспектам программирования, в том числе в 2005 году: монографию «Основные концепции и механизмы объектно-ориентированного программирования», статью «Уровни абстрагирования при управлении сложными типами в структурном программировании», статью «Синтаксический анализ выражений в скобочной форме на основе визуального формализма L-сети»

(в соавторстве с М.Ф. Лекаревым).

В ходе работы на кафедре Пышкин Е.В. участвовал в ряде международных проектов. В рамках сотрудничества в области образовательных технологий приглашался в Финляндию (Central Ostrobothnia Polytechnic) для проведения краткосрочных курсов: «Основы языка программирования Java», «Введение в программирование на платформе Microsoft.NET Framework». Для организации соответствующих лекционных курсов и практикума были подготовлены и опубликованы учебные пособия на английском языке: «Understanding the Object Model»

(2003), «An Introduction to the Microsoft.NET Framework Architecture and Tools» (2004).

В СПбГПУ читает следующие курсы:

Основы алгоритмизации и программирования. Технология программирования. Программирование на языке высокого уровня Объектно-ориентированное программирование Информационные технологии в проектировании программного обеспечения Играет на фортепиано. В 2004 году в концертном зале Ylivieskatalo Akustiikka (Финляндия) записал программу “Night in Ylivieska”, составленную из произведений Моцарта, Дебюсси, Скрябина и нескольких собственных сочинений.

Содержание

Предисловие

Введение

Изучение структурного программирования: проблемы и современное состояние

Организация книги

Исходные тексты программ

Использование книги в учебном процессе

Глава 1. Основание программирования

1.1. Необходимые предпосылки

Кодирование и содержание

Системы счисления

Понятие сложности кода

Цифровые вычислительные машины

Операции над двоичными числами

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

Языки программирования C и C++: цели разработки и назначение.......... 40 1.2. «Алгоритмы + структуры данных = программы»

Описания программных объектов

Определение действий над программными объектами

Понятие об определении и объявлении

1.3. Понятие о структурно-императивном программировании..... 48 Определение императивного программирования

Целевая архитектура

Процедурная парадигма

Глава 2. Понятие типа данных

2.1. Стандартные типы данных

Целые типы

Символьные типы

Плавающие типы

Логический (булевский) тип

Указатели

Ссылки

2.2. Массивы

2.3. Перечисления

2.4. Множества

2.5. Структуры и классы

2.6. Объединения

2.7. Система типов C++

Глава 3. Организация процедурного кода

3.1. Алгоритмы: определения и способы записи

Текстуальная форма записи

Схема алгоритма

Диаграммы Нэсси-Шнейдермана

Диаграммы Дейкстры

Псевдокод

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

ДРАКОН-схемы

Р-схемы

Запись алгоритмов функционирования реактивных систем

От схем алгоритмов и конечных автоматов к визуализации проектирования

3.2. Основные управляющие конструкции структурноимперативного программирования

Условная инструкция

Повторяющиеся вычисления (циклы)

Безусловная передача управления

Мультиветвление

3.3. Функционально-иерархическая декомпозиция

Основные стратегии проектирования: первоначальные сведения.......... 137 Процедуры и функции

Вызов функционального блока и возврат управления

3.4. Области видимости и классы памяти

Область видимости программных объектов

Классы памяти и время жизни программных объектов

3.5. Механизмы связывания функциональных модулей............. 153 Связывание по значению

Связывание с косвенной адресацией

Связывание по ссылке

Связывание через общий интерфейс

3.6. Функции и управление исполнением программы.................. 165 Механизм обратного вызова

Рекурсия

Глава 4. Управление данными в процедурной программе.

......181

4.1. Построение модели предметной области

Постановка демонстрационной задачи

Анализ предметной области

Построение модели обрабатываемых данных

Построение модели фрагмента грамматики русского языка

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

4.3. Модульность в связи с управлением данными





4.4. Полиморфизм в процедурном программировании............... 194 Перегруженные функции

Шаблоны функций

Функции как параметры функций

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

Глава 5. Управление связанными структурами данных.

....... 208

5.1. Матричный контейнер

Постановка задачи

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

Уровни абстрагирования и обобщенная модель

Интеграция сегментов: «Вычисления = операции + управление»........... 215

5.2. Списочные структуры (на примере односвязного списка).. 216 Постановка задачи

Реализация абстракции списка и базового комплекта операций............ 217 Определение других операций над списком. Первоначальное представление о рефакторинге кода

Реализация операций вставки элемента в обобщенной форме.............. 228 Проблемы реализации

Построение гибридного кода

5.3. Древовидные структуры

Бинарное дерево как вариант организации данных в одномерном массиве

Алгоритм поиска с использованием бинарного дерева

Алгоритм сортировки с использованием бинарного дерева

5.4. Hash-таблицы и ассоциативные массивы

Hash-поиск. Идея алгоритма

Распознавание служебных слов из фиксированного набора

Ассоциативные массивы

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

6.1. Императивная модель

Задача о возведении в степень. Постановка

«Наивное» решение и его проблемы

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

Проблемы чисто императивного решения

6.2. Функционально-иерархическая декомпозиция

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

Ограничения, присущие процедурной модели

6.3. Построение гибридного кода. Введение в мультипарадигменное программирование

Разработка и использование типа SafeLong

Понятие об общности и изменчивости кода

Глава 7. Визуализация проектирования в примерах и иллюстрациях

7.1. Визуальный формализм на базе L-сети

Среда последовательного управления

Среда разветвленного управления

Управление данными

7.2. Визуальный язык ДРАКОН

7.3. Визуализация проектирования систем, основанных на событиях

Диаграммы состояний Д. Харела

SWITCH-технология

Глава 8. Задачи лексического и синтаксического анализа.

....291

8.1. Постановка задачи

8.2. Лексический анализ

Понятие синтерма: непересекающиеся и пересекающиеся синтермы

Формирование и распознавание синтерма

8.3. Решение задачи синтаксического анализа логических выражений в форме L-сети

Лексический анализатор в форме L-сети

Синтаксический анализатор в форме L-сети

Экспресс-анализ средств проектирования

Заключение

Компьютерные программы для людей

Несколько слов о форме и содержании

От сложного к простому, или принципы Дэвида Стрэйкера........ 306 Приложение 1. Задачи для самостоятельного практикума

П1.1. Вычислительные процедуры

П1.2. Управление сложными и связанными типами

П1.3. Лексический и синтаксический анализ

Приложение 2. Описание компакт-диска

Список источников

–  –  –

В настоящее время многие специалисты отмечают, что методы разработки, ориентированные на функционально-ориентированное (процедурное) программирование, не исчерпали себя, более того – во многих областях применения информационных технологий остаются главенствующими [Brooks, 1995], [Паронджанов, 1999], [Лекарев, 1997], [Легалов, 2000].

Понятие «структура программы» в последнее время претерпело существенные изменения. Эти изменения отчасти обусловлены успехами развития технологий программирования, основывающихся на объектноориентированной парадигме. Использование объектно-ориентированных технологий само по себе не влечет автоматического улучшения качества программного обеспечения и преодоления присущей программному обеспечению (ПО) сложности. М.Ф. Лекарев отмечает, что, хотя объектноориентированные методы представляют собой существенный прогресс в развитии систем проектирования ПО и позволяют преодолеть многие виды дополнительной сложности, этот прогресс не затрагивает существенную сложность, поскольку относятся в большей части к форме представления решения [Лекарев, 2000-1].

Ошибочно противопоставление структурных методов, основывающихся на иерархической декомпозиции и пошаговом уточнении структур данных, объектно-ориентированным технологиям. В конечном счете, наилучшие результаты дает совместное применение систематических методов проектирования, хорошо зарекомендовавших себя в проектной практике, и различных парадигм программирования [Coplien, 1999], [Stroustrup, 2001].

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

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

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

Введение Данное учебное пособие обеспечивает курсы, читаемые студентам в начале обучения и обобщаемые наименованием «Теория и технология программирования». Основная задача этих курсов – дать студентам начальные сведения о представлении информации и обработке программ в ЭВМ, о построении алгоритмов и структуры программного кода и основных направлениях развития информационных технологий в области разработки ПО.

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

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

Если анализировать обобщающее наименование системы курсов по программированию – «Теория и технология программирования», то первая составляющая подразумевает, прежде всего, изучение моделей и методов проектирования ПО, концепций проектирования, реализуемых этими методами, изобразительных средств, синтаксиса и семантики конструкций языков программирования, которые выражают эти концепции. Каждый язык программирования выражает, по существу, определенную модель вычислительного процесса. В связи с этим студенты должны иметь представление об организации вычислительного процесса для выполнения компьютерной программы, о способах представления данных в ЭВМ и манипулирования этими данными. В качестве основного инструмента проектирования принципиально может выбираться любой язык, поддерживающий процедурную модель. В данной книге в качестве основного средства иллюстрации изучаемых концепций используется язык программирования C++.

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

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

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

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

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

В главе 2 дается определение и анализ понятия типа данных.

Представлена система типов, поддерживаемая языком C++. Рассмотрены стандартные скалярные типы данных и составные типы, конструируемые пользователем.

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

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

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

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

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

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

визуальный формализм на базе L-сети [Лекарев, 1997], визуальный язык ДРАКОН [Паронджанов, 1999], SWITCH-технология [Шалыто, 1998].

В главе 8 рассматриваются проектные проблемы, возникающие при решении задач обработки текстов. Студенты получают представление о задачах лексического и синтаксического анализа и варианта решения этих задач на основе совместного использования структурного программирования на языке C++ и визуального формализма для разработки ПО на базе L-сети [Лекарев, 1997].

Исходные тексты программ Исходные тексты примеров программ предоставляются читателю на прилагаемом к книге компакт-диске. Описание содержимого компакт диска см. в приложении 2.

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

Однако, по справедливому замечанию М.Ф. Лекарева, «термин черновые записи не означает неаккуратные записи!» [Лекарев, 2000-3].

Использование книги в учебном процессе Данная книга совместно с книгами [Лекарев, Давыдов, 2002], [Давыдов, 2003], [Pychkine, 2003], [Pychkine, 2004], [Давыдов, 2005], [Пышкин, 2005], написанных преподавателями кафедры автоматики и вычислительной техники (АиВТ) факультета технической кибернетики Санкт-Петербургского государственного политехнического университета, является частью литературного обеспечения курсов «Программирование на языке высокого уровня», «Основы программирования и алгоритмизации», «Технология программирования» и ряда смежных курсов, читаемых студентам кафедры АиВТ.

Книга не является учебником по программированию на языке C++, хотя и содержит некоторый учебный материал в связи с языком C++. Задачи обучения языку C++ в достаточной степени решаются во многих современных учебниках, активно используемых в учебном процессе (например, [Eckel, 2000], [Stroustrup, 2000], [Павловская, 2001], [Давыдов, 2003] и др.).

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

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

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

Кодирование и содержание Термин «информация» является сильно нагруженным, достаточно заглянуть в любой толковый словарь. Даже применительно к задачам технической науки можно констатировать разнообразие уровней абстрагирования при определении термина «информация». Н. Винер, рассматривая подобие процессов управления и связи в машинах, живых организмах и обществах, определял эти процессы как передачу, хранение и переработку информации, т.е. различных сигналов, сообщений, сведений [Wiener, 1961]. Любой сигнал рассматривается как некоторый выбор между двумя и более значениями, наделенными известными вероятностями. Винер заложил основы селективной концепции информации, на которой базируется статистическая теория информации.

А.Н. Колгоморов сформулировал и развил разделы теории информации, связанные с оценкой сложности информации, предложив механизмы оценки количества информации и способы измерения количества информации при помощи сравнения любой информации с информацией в виде некоторого числа двоичных знаков. А.Н. Колмогоров ввел определение сложности объекта как минимальной длины описания объекта в некотором коде, заложил основы математической теории алгоритмов [Колмогоров, 1987], [Ming, Vitanyi, 1993].

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

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

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

Алфавит – базовая характеристика любого кода. Без знания алфавита невозможно расшифровать код и «вычислить» его содержание. Однако знания алфавита недостаточно, поскольку код сам по себе не имеет смысла (пример: древние языки, нерасшифрованные нотации, например, знаменная нотация церковного пения до 15 века). Причина заключатся в отсутствии правила расшифровки (правила декодирования). Ошибка в декодировании приводит к искажению смысла (рис. 1.1).

–  –  –

Информация, с которой имеют дело вычислительные машины, обычно обобщенно называется термином «данные».

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

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

–  –  –

Непозиционной является и используемая до сих пор римская система счисления, в которой для записи чисел используется 7 латинских букв: I, V, X, L, C, D, M (соответственно для обозначения привычных для нас чисел 1, 5, 10, 50, 100, 500, 1000). Ниже приведены некоторые числа, записанные в римской нотации.

3 III 4 IV 8 VIII 19 XIX 256 CCLVI 2005 MMV Ч. Петцольд замечает, что, долгое время римские числа считались весьма удобными для выполнения операций сложения и вычитания, однако умножение и деление римских чисел является весьма нетривиальной задачей [Petzold, 1999].

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

–  –  –

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

Проще всего перевести в десятичную систему счисления, например, для двоичного числа 1101 получим:

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

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

Например:

31, остаток: 9 (разряд единиц) 3, остаток: 1 (разряд десятков) 0, остаток: 3 (разряд сотен) Аналогично, чтобы перевести десятичное число в другую систему счисления, нужно делить его на основание другой системы, например, для числа 13, переводимого в двоичную систему счисления, получим:

6, остаток: 1 (самый младший разряд) 3, остаток: 0 1, остаток: 1 0, остаток: 1 (самый старший разряд) Последовательность остатков от деления и определяет искомый результат.

–  –  –

где n – число разрядов в целой части, а m – число разрядов в дробной части. В сокращенной форме записи это эквивалентно:

Aq an 1an 2...a2 a1a0.a 1a 2...a m Поскольку вес разрядов дробной части соответствует долям единицы, то для преобразования дробной части из одной системы счисления в другую необходимо умножать дробную часть на основание целевой системы счисления, выделяя целые части произведений (это и будут цифры представления дробной части). Для получающихся при умножении дробных частей процесс умножения повторяется до тех пор, пока не получится нулевая дробная часть (это означает, что нам удалось найти точное представление числа в заданной системе счисления) или пока не будут исчерпаны ячейки памяти для хранения результата (в этом случае говорят о приближенном результате преобразования).

Рассмотрим пример. Пусть необходимо перевести в двоичную систему счисления десятичное число 13.4375. Перевод целой части мы рассмотрели выше. Теперь займемся переводом дробной части.

Сначала умножаем дробную часть на 2:

0.4375 2 0.875 Целая часть произведения равна нулю, следовательно, разряд двоичного числа с весом 2 1 0.5 равен нулю. Дробную часть снова умножаем на 2:

0.875 2 1 0.75 Целая часть произведения (единица) – это разряд двоичного числа с весом 2 2 0.25. Дробную часть снова умножаем на 2:

0.75 2 1 0.5 Целая часть произведения (единица) – это разряд двоичного числа с весом 2 3 0.125. Дробную часть снова умножаем на 2:

0.5 2 1 Целая часть произведения (единица) – это разряд двоичного числа с весом 2 4 0.0625. Дробной части нет, следовательно, преобразование закончено, окончательное представление десятичного числа 13.6875 в двоичной системе счисления имеет вид:

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

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

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

Системы счисления, используемые в информатике и вычислительной технике Помимо двоичной системы счисления, наибольшее распространение в различных областях вычислительной техники получили системы счисления с основаниями 8 (восьмеричная), 16 (шестнадцатеричная) и нередко используемая в схемотехнике двоично-десятичная система счисления (в двоичном коде раздельно представляется каждая десятичная цифра). Для представления цифр в системах счисления с основанием больше десяти обычно используют строчные или прописные латинские буквы в порядке их следования в латинском алфавите. Шестнадцатеричные цифры, соответствующие десятичным значениям от 10 до 15, приведены в табл. 1.1.

Таблица 1.1.

Шестнадцатеричные цифры Двоичный код Десятичный код Шестнадцатеричная цифра 1010 10 A 1011 11 B 1100 12 C 1101 13 D 1110 14 E 1111 15 F Преобразование из двоичной системы счисления в системы счисления с основанием, кратным степеням двойки (в частности, восьмеричную и шестнадцатеричную системы), и обратно, осуществляется очень просто.

Каждая цифра системы счисления с основанием 2 r представляется точно r разрядами соответствующего двоичного представления. Так, каждая восьмеричная цифра соответствует двоичной триаде (трем разрядам), а каждая шестнадцатеричная цифра – двоичной тетраде (четырем разрядам).

Если число разрядов двоичного представления не кратно числу разрядов восьмеричного (шестнадцатеричного и т.д.) представления, то двоичное число дополняется необходимым числом старших разрядов в целой части и младших разрядов в дробной части. Рассмотрим пример преобразования двоичного числа 1101.0111 в восьмеричную систему счисления. Двигаясь от десятичной точки влево, составляем две триады, дополняя двумя нулевыми старшими разрядами. Двигаясь от десятичной точки вправо, также выделяем две триады, на этот раз дополняя нулями разряды справа. Условно выделяя триады запятыми, получим 001,101.011,100, что соответствует восьмеричной записи 15.34.

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

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

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

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

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

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

kq, где Ldigit

–  –  –

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

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

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

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

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

При напряжении питания 5 В это:

диапазон (0..0,4) В, соответствующий логическому значению сигнала «0»;

диапазон (2,4..5) В, соответствующий значению сигнала «1».

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

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

Биты, байты, слова, слова, слова… Вообще говоря, при обработке двоичных данных манипулируют не отдельными битами, а последовательностями битов. Стандартная длина такой последовательности битов – 8. В вычислительной технике восьмерка двоичных разрядов называется байтом (этот термин используется примерно с середины 50-х годов XX века). При записи байта принято изображать все восемь битов, даже если старшие биты нулевые, например, 00010011, а не 10011.

Почему байт содержит именно 8 битов? Несмотря на то, что ряд причин принятия такого решения имеет скорее исторический характер, Ч. Петцольд приводит и некоторые разумные технические объяснения.

Поскольку байт позволяет представить 256 различных комбинаций, то его удобно использовать для представления большинства символов, используемых в разных языках (за исключением китайских, японских и корейских иероглифов), что и было реализовано в 1967 году в виде стандарта ASCII. Байт также вполне подходит для представления оттенков серого цвета на черно-белых фотографиях, поскольку человеческий глаз способен различать в среднем около 256 оттенков [Petzold, 1999].

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

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

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

–  –  –

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

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

..

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

–  –  –

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

Положительные и отрицательные числа. Понятие о дополнительном коде Изложенный подход хорошо работает, но что, если нам нужно вычесть 123 из 67? Как обеспечить адекватную схему вычислений, позволяющую оперировать с отрицательными числами?

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

8 разрядов позволяет представить 256 комбинаций. Половина комбинаций (от 0000 0000 до 0111 1111) соответствуют десятичным числам от 0 до 127. Остальная половина (от 1000 0000 до 1111 1111) соответствует отрицательным кодам. В табл. 1.5 приведены двоичные коды и соответствующие им десятичные числа.

Таблица 1.5.

Дополнительный код Двоичный код (1 байт) Десятичное число 1000 0000 -128 1000 0001 -127 1000 0010 -126 1000 0011 -125 … … 1111 1101 -3 1111 1110 -2 1111 1111 -1 … … Нетрудно заметить, что отрицательное число получается вычитанием положительного числа с тем же абсолютным значением из максимального кода 1111 1111 (то есть инверсией) с последующим добавлением единицы (рис. 1.6). Код, представленный в таблице, называется дополнительным, или комплементарным кодом (two’s complement code).

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

При выполнении вычислений в рамках ограничений, накладываемых разрядностью кода, возможно возникновение ситуаций переполнения сверху (overflow), когда результат превышает максимальный положительный код (в нашем примере это код числа 127), и переполнения снизу (underflow), когда

–  –  –

_ + _ Рис. 1.7. Вычитание в комплементарном коде Основные элементы языка программирования В данном разделе мы рассмотрим элементы, позволяющие формально определить любой язык, при этом для иллюстрации используемых понятий мы будем использовать определение языка C++.

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

Наиболее распространены пять основных категорий лексем:

идентификаторы – для записи символических имен программных объектов;

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

литералы: целочисленные, с плавающей точкой, символьные, строковые – для записи констант;

знаки операций (арифметических, логических, операций отношения и др.) – для записи элементарных действий над данными;

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

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

abcdefghijklmnopqrstuvwxyz

ABCDEFGHIJKLMNOPQRSTUVWXYZ

+-*/= () {} [] '"!#~%^&_;:,.?\| Символы пробелов и табуляции При генерации лексем компилятор выбирает наиболее длинную строчку, которая составляет лексему. Подробнее задача лексического анализа рассматривается в гл. 8.

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

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

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

В естественных языках синтаксически корректное предложение в некоторых случаях может трактоваться по-разному (иметь различную семантику) в зависимости от контекста (если речь идет об идиомах) или порядка применения правил языка. М.Ф. Лекарев приводит следующий выразительный пример из русского языка. В предложении «он встретил ее на лугу с цветами», на первый взгляд, речь может идти о галантном кавалере, не забывшем принести букет цветов на встречу с любимой. «Однако правила русского языка допускают и иное толкование», - замечает автор – «с цветами в руках могла быть она. Наконец, цветами мог быть усеян цветущий луг»

[Лекарев, 2000-1]. Несмотря на то, что правила языка обычно содержат рекомендации для подобных неоднозначностей (в данном случае, руководствуясь принципом применения правил к ближайшему определяемому слову, следует, вероятно, считать, что все-таки романтика ситуации ограничивалась цветением луга! – Е.П.), полностью проблема не снимается. Синтаксис формальных языков специально разрабатывается таким образом, чтобы исключить возможность неоднозначного толкования предложений языка.

–  –  –

Для описания синтаксиса используют различные способы. Наиболее распространенными из них являются два способа: металингвистические формулы Бэкуса-Наура (текстовая форма описания синтаксиса) и синтаксические диаграммы, впервые предложенные Н. Виртом (текстографическая форма описания синтаксиса, см. рис. 1.10).

Аналогичные правила в форме Бэкуса-Наура будут выглядеть следующим образом:

десятичная-цифра ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 идентификатор ::= { латинская-буква} | _ } [ латинская-буква | десятичная-цифра | _ ]...

Описание семантики является более сложной проблемой, чем описание синтаксиса. Читатель, интересующийся методами описания семантики, может обратиться, например, к [Sebesta, 2002].

–  –  –

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

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

Например, стандарт ANSI C позволяет различать идентификаторы по первым 6 символам (для глобальных имен) и 31 символу (для локальных имен). Компилятор Microsoft С, интегрированный в платформу Microsoft.NET 2003, допускает различение идентификаторов C по первым 247 символам (при этом не делается различия между локальными и глобальными именами). Компилятор Microsoft Visual C++ различает идентификаторы до 2048 символов.

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

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

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

Служебные слова в языках C/C++ набираются в нижнем регистре, таким образом, идентификаторы IF, FOR, WHILE являются корректными незарезервированными идентификаторами. Однако из этого н е с л е д у е т, что их нужно использовать для именования пользовательских объектов.

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

Часть ключевых слов унаследована от языка C:

asm Вставка ассемблерного кода в код на C auto Спецификатор класса памяти «автоматическая переменная»

break Прекращение итераций цикла, выход из мультиветвления case Ветвь мультиветвления char Спецификатор типа «символьный»

continue Переход к очередной итерации цикла default Ветвь мультиветвления «по умолчанию»

do Заголовок цикла с постусловием do...while double Спецификатор типа «с плавающей точкой двойной точности»

else Ветвь «иначе» в инструкции if enum Спецификатор перечисляемого типа extern Спецификатор доступа к внешним объектам float Спецификатор типа «с плавающей точкой»

for Заголовок цикла с предусловием for goto Безусловный переход на метку if Условная инструкция int Спецификатор типа «стандартное целое» (2 или 4 байта) long Спецификатор типа «длинное целое» (4 байта) main Зарезервированное имя функции-точки входа register Спецификатор класса памяти «регистровая переменная»

return Возврат управления из функции short Описатель типа «короткое целое» (2 байта) signed Спецификатор типа «целое со знаком»

sizeof Операция определения размера программного объекта static Спецификатор класса памяти «статический»

struct Спецификатор структурного типа switch Инструкция «мульиветвление»

typedef Спецификатор пользовательского типа union Спецификатор типа-объединения unsigned Описатель «целое без знака»

while Заголовок цикла с предусловием while void Спецификатор типа void

Остальные слова являются специфичными для C++:

bool Спецификатор типа «булевский»

catch Заголовок обработчика исключения class Спецификатор типа «класс»

const_cast Преобразование типа для избавления от константности delete Операция удаления объекта из динамической памяти dynamic_cast Преобразование типа времени выполнения explicit Спецификатор конструктора «без неявного преобразования»

false Зарезервированная константа булевского типа «ложь»

friend Спецификатор дружественного доступа inline Спецификатор подставляемой (встроенной) функции mutable Спецификатор «никогда не является константой»

namespace Спецификатор простраства имен new Операция размещения объекта в динамической памяти operator Спецификатор перегружаемой операции private Спецификатор «закрытый доступ к членам класса»

protected Спецификатор «защищенный доступ к членам класса»

public Спецификатор «открытый доступ к членам класса»

reinterpret_cast Спецификатор «произвольное преобразование типа»

static_cast Спецификатор «преобразование времени компиляции»

template Спецификатор «шаблонное объявление»

this Зарезервированный константный указатель на объект throw Инструкция генерации исключения true Зарезервированная константа булевского типа «истина»

try Спецификатор блока «возможно возникновение исключения»

typeid Определение информации о типе во время выполнения typename Спецификатор для разрешения неоднозначностей в шаблонах using Спецификатор для использования пространств имен virtual Спецификатор «виртуальная функция»

volatile Спецификатор «изменяемый извне (фоновым процессом)»

wchar_t Спецификатор типа «символьный в формате Unicode»

Ряд служебных слов (auto, goto, register, signed) по разным причинам довольно редко встречаются в современной практике программирования на C++, область употребления некоторых служебных слов крайне ограничена (continue, mutable, volatile, явные приведения типов).

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

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

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

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

Несмотря на то, что самим языком правила форматирования исходного текста программы не обязательно жестко зафиксированы, форматирование исходного текста в соответствии с его логической структурой существенно облегчает разработку и восприятие текстов программ. По сути дела, форматирование исходного текста в соответствии с его логической структурой – не что иное, как один из визуальных формализмов, используемых уже в течение десятилетий [Straker, 1992]. При этом, хотя полезность форматирования «настолько очевидна, что не оспаривается никем [...], конкретные правила форматирования были и остаются предметом дискуссии» [Лекарев, 1997].

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

Вертикальное форматирование: действия, составляющие один логический блок, комментарии, сопровождающие текст, символы, ограничивающие обособленные блоки (например, фигурные скобки в языке C++, пары ключевых слов begin, end в языке Pascal) записываются друг под другом с выравниванием по левому краю.

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

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

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

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

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

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

В языке C++ используются комментарии двух видов:

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

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

Это иногда удобно при отладке */ С точки зрения назначения в тексте программы комментарии можно классифицировать следующим образом:

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

Выделяющие, или предваряющие, комментарии (Д. Стрэйкер использует термин блочные комментарии [Straker, 1992]) размещаются перед относительно обособленными фрагментами текста, служат промежуточными заголовками к группам данных или действий или объясняют назначение отдельных подпрограмм.

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

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

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

Листинг 1.1.

Комментарии к функциям обработки параметров командной строки /* * Файл: PARMOS.CPP * PARaMeters from Operating System CPP module * * Проект: описание проекта * * Назначение: обработка параметров командной строки * * Дата создания : 13.06.2005 * Дата корректировки : 21.07.2005 * * Copyright (C) Пышкин Евгений Валерьевич, 2005 */ #include string.h #include "parmos.h" /* * Внешние интерфейсы данных */ PARMOS ParmOS; // Сведения о параметрах командной строки /* * Конфигурируемые внутренние параметры модуля */

–  –  –

/* * Функции, входящие в состав модуля */ // SEND PARAMETERS from main program // Параметры, пересылаемые основной программой.

// Функция возвращает значения кода ошибки при работе // с командной строкой int SendParameters( int argc_copy, char *argv_copy[] ) { ParmOS.ErrorCode = 0;

// Проверка корректности количества параметров if( argc_copy PMLIM ) return ParmOS.ErrorCode = 1;

ParmOS.IxLast = argc_copy-1;

–  –  –

//...

// INPUT FILE NAME IS CORRECT?

// Проверка: имя исходного файла корректно?

bool InputFileNameIsCorrect() { char *observed; // Указатель на обозреваемый символ char *preobserved; // Прежнее значение "observed"

–  –  –

//...

/* * Конец файла PARMOS.CPP */ Стоит заметить, что затруднение, возникающее при попытке пояснить программный текст, часто связано с плохим качеством самого текста, так что комментирование программы служит и дополнительным средством контроля качества собственной разработки. Б. Керниган предлагал руководствоваться следующими правилами: «не комментируйте плохой код – перепишите его», стремитесь к ясности самого кода, «не умничайте»

[Kernighan, Plauger, 1978]. Продуманный, легко читаемый, грамотный комментарий, как правило, является свидетельством качественной разработки, ибо если проектировщик не может ясно рассказать о своих проектных решениях на естественном языке, то разве можно ожидать от него элегантных, красивых и надежных решений на языке искусственном?

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

Обычно таким комментариям предшествует текст подобного содержания:

// DO NOT EDIT THIS TEXT!

// IT IS MACHINE GENERATED!

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

Например, в C# для этой цели используется язык XML (eXtensible Markup

Language), при этом документирование кода выглядит примерно так:

/// summary /// Plain triangle construction and processing class /// /summary /// remarks /// see cref="Point"Point/see /// /remarks

–  –  –

Рис. 1.11. Документирующие комментарии Унификация форматов документирующих комментариев позволяет обеспечить их машинную обработку и автоматизировать генерацию документации к разрабатываемому ПО, например, в форме связанных HTML-страниц с единым пользовательским интерфейсом. Некоторые подробности интеграции кода и документации обсуждаются также в учебном пособии [Пышкин, 2005].

Языки программирования C и C++: цели разработки и назначение История возникновения языка C++ не может рассматриваться в отрыве от его прямого предшественника – языка C. Появление же языка C во многом было связано с актуальными задачами системного программирования, стоявшими перед разработчиками в 60-70-е года двадцатого века.

Историческим прототипом языка C является язык BCPL (Basic Combined Programming Language), разработанным в 60-е годы Мартином Ричардсом из Кембриджского университета. В 1970 году сотрудники Bell Laboratories создали вариант языка BCPL, названный B, который был использован при разработке операционной системы Unix для компьютера PDP-11 фирмы DEC. В этом диалекте BCPL не было типов данных, его единственным объектом было машинное слово, не различались целые значения и значения с плавающей точкой, не обеспечивались удобные способы выполнения операций над этими данными.

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

Язык C++ был спроектирован для того, чтобы предоставить разработчикам мощный и гибкий инструмент, обеспечивающий модель памяти и вычислительного процесса, которая была бы пригодна для использования на большинстве современных платформ [Stroustrup, 2000].

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

Язык C++ в существенной степени ориентирован на мультипарадигменное программирование, позволяя объединить гибкость и эффективность языка C для системного программирования с объектноориентированными возможностями организации программ. C++ не вынуждает программиста следовать какой-то определенной модели программирования (в отличие, например, от языка Java), и это является одной из его конструктивных особенностей. Б. Страуструп отмечал, что он не хотел, чтобы пользователи языка были вынуждены делать что-то жестко определенное: «Из истории мы знавали множество идеалистов, пытавшихся заставить людей делать что-либо во имя их же блага и оказывавшихся виновными в самых страшных трагедиях».

Описывая язык C++, Б.

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

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

поддерживает абстракцию данных;

поддерживает ООП;

поддерживает обобщенное программирование.

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

1.2. «Алгоритмы + структуры данных = программы»

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

–  –  –

В соответствии с концепцией типа в определении Хоара, тип определяет класс значений, которые могут принимать переменная или выражение. При работе с языком программирования знание типа позволяет обнаруживать бессмысленные конструкции и решать вопрос о методе представления данных и преобразования их в ЭВМ [Dahl, Dijkstra, Hoare, 1972].

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

Таким образом, описание данных необходимо для решения трех основных задач:

1. Определить необходимое количество памяти для хранения этих данных.

2. Определить способ представления значения в памяти компьютера (код и правило декодирования цепочки битов, хранящихся в этой памяти).

3. Задать символическое имя, соответствующее адресу в памяти.

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

Для представленного примера расшифровка следующая: a является переменной, которая может принимать целые значения, представляемые дополнительным двоичным кодом, длина которого зависит от архитектуры компьютера (например, 16 разрядов, или 2 байта,– для 16-разрядных процессоров, 32 разряда, или 4 байта,– для 32-разрядных процессоров).

Определение действий над программными объектами Действия над программными объектами определяются посредством элементарных операций над данными и высокоуровневых инструкций языка.

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

В этом случае говорят, что выражение имеет побочные эффекты:

int a, b;

printf( "%d", a+b ); // Выражение a+b не имеет побочных эффектов

–  –  –

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

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

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

1.13):

int a = 10; // Переменная a инициализирована значением 10 int b = 25; // Переменная b инициализирована значением 25 // NB! Инициализация НЕ является присваиванием

–  –  –

// Здесь: a=10, // b=10 Особенность присваивания заключается в том, что в различных языках программирования присваивание может быть инструкцией языка (statement) или операцией (operator). Например, в языке Pascal присваивание – это инструкция языка, обеспечивающая занесение в одну ячейку памяти копии значения, хранящегося в другой ячейке памяти.

–  –  –

В языках C/C++ присваивание – это операция языка. В результате вычисления операции получается значение (совпадающее с присваиваемым значением). Это значение не обязательно совпадает со значением переменной, расположенной справа от операции присваивания, после вычисления выражения.

Рассмотрите примеры двух выражений:

int a = 10;

int b = 25;

b = a; // Значение операции присваивания (10) совпадает // со значением переменной a (10) b = a++; // Значение операции присваивания (10) НЕ совпадает // со значением переменной a (11) Подробнее операции языка обсуждаются в следующих разделах.

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

По числу операндов операции можно классифицировать следующим образом:

одноместные операции (например, операция взятии с обратным знаком, операция обращения по адресу, операции увеличения и уменьшения на единицу, операция sizeof, операция «запятая»);

двуместные операции (например, операции сложения и вычитания, логические операции И и ИЛИ, операция сравнения, операция присваивания);

трехместная (тернарная) операция (такая в языке C++ одна – условная операция).

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

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

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

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

К операциям с побочным эффектом относятся следующие операции:

операции увеличения и уменьшения на единицу;

операции присваивания и составного присваивания.

В связи с организацией вычисления выражений вводятся понятия приоритета операций и правил группирования операций (ассоциативность). Приоритет определяет очередность выполнения операций в выражении. Из арифметических операций самый высокий приоритет имеют одноместные операции, самый низкий – операция присваивания. Приоритет операций, поддерживаемых языком, определяется правилами языка. Наиболее полное описание операций, поддерживаемых C++, см. в [Stroustrup, 2000].

Группирование операций определяет порядок выполнения операций равного приоритета. Операции называются правоассоциативными, если они выполняются справа налево, например, все одноместные операции и операции присваивания – правоассоциативны.

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

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

ЧТЕНИЕ b a = a + b * 25 * 25

–  –  –

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

–  –  –

В [Sebesta, 2002] указывается, что языки, допускающие использование скобок при записи выражений, могут вообще обходится без правил приоритета, предоставляя программисту самому определить требуемый порядок вычислений. При этом программистам не приходилось бы запоминать правила приоритета и группирования, однако написание выражений стало бы более утомительным, а сами выражения – более громоздкими. Язык, использующий такой подход, все же существует – это язык APL.

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

Понятие об определении и объявлении Описание может являться определением (и одновременно объявлением), а может быть только объявлением. Между понятиями «определение программного объекта» (definition) и «объявление программного объекта» (declaration) существует принципиальная разница, которую нужно понимать.

–  –  –

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

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

Очевидно, что любое определение автоматически является объявлением.

Требование объявления объекта является более мягким, чем требование определения (объект должен быть известен в некотором модуле, но не обязательно именно в этом модуле определен). Понятие объявления тесно связано с понятием «область видимости». Объявление объекта делает его доступным в пределах области видимости этого объекта (рис. 1.16).

Информацию об областях видимости и классах памяти программных объектов см. в разд. 3.4.

1.3. Понятие о структурно-императивном программировании Важнейшими факторами, влияющими на разработку языков программирования, являются архитектура компьютера и методологии программирования [Sebesta, 2002]. В конечном счете, большинство языков программирования являются выразителями концепций программирования и одновременно с этим своего рода моделями вычислительной системы [Пышкин, 2005]. Поэтому, определяя модель программирования, наряду с такими ключевыми факторами как организация управляющих конструкций языка, система типов данных, семантика основных конструкций, необходимо учитывать архитектуру вычислителя, на которую ориентирована эта модель.

Определение императивного программирования Методология императивного программирования основана на принципе конструирования программ как описаний последовательного изменения состояния вычислителя пошаговым образом. Для императивного программирования характерна полная определенность и контролируемость переходов из одного состояния в другое [Одинцов, 2002].

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

Императивная методология лежит в основе таких языков как FORTRAN, Pascal, Algol, C.

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

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

Вычислительная машина является устройством для обработки информации. Обработка информации предполагает представление информации и управление информацией.

Отсюда вытекает наличие двух важнейших конструктивных элемента любой компьютерной программы:

данные и операции над данными.

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

–  –  –

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

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

Оперативная память состоит из большого числа регистров (см. рис. 1.18).

Каждый регистр имеет уникальный числовой адрес. Использование специального регистра адреса позволяет обратиться к любому регистру памяти. Память с такой организацией управления называется памятью с произвольным доступом (Random Access Memory – RAM). Размер регистра адреса определяет, сколько ячеек памяти может адресовать этот регистр.

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

Основные два режима управления оперативной памятью – это управление в режиме чтения и в режиме записи.

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

1. В регистр адреса записывается адрес считываемого регистра.

2. На блок управления подается управляющий сигнал READ.

3. Информация перемещается из адресуемого регистра в регистр данного.

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

–  –  –

Рис. 1.18. Принципы организации оперативной памяти

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

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

2. В регистр данных загружается исходная цепочка битов.

3. На блок управления подается управляющий сигнал WRITE.

4. Информация перемещается из регистра данных в адресуемый регистр памяти.

5. Блок управления выставляет сигнал готовности.

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

–  –  –

Рис. 1.19. Арифметико-логическое устройство Основное назначение арифметико-логического устройства (АЛУ) состоит в преобразовании информации посредством выполнения простейших арифметических и логических операций (сложения, вычитания, умножения, деления, сравнений). Классическая структура АЛУ предполагает наличие трех компонентов: операционный блок и двух регистров. Исходные данные операции (см. рис. 1.19) помещаются в регистры RA и RB. Результат операции помещается в регистр RA, поэтому АЛУ такой структуры называют АЛУ накапливающего типа.

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

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

Код операции Адрес операнда

–  –  –

Рис. 1.20.

Одноадресные и двухадресные команды Любая двухадресная команда может быть представлена в виде последовательности одноадресных команд, например для сложения содержимого двух ячеек оперативной памяти VAR1 и VAR2 и помещения результата в ячейку RES, требуется реализовать следующую последовательность действий:

ЧТЕНИЕ VAR1 ‘ИЗ РЕГИСТРА RAM VAR1 В РЕГИСТР АЛУ RA

+ VAR2 ‘ИЗ РЕГИСТРА RAM VAR2 В РЕГИСТР АЛУ RB

К ‘РЕЗУЛЬТАТ СЛОЖЕНИЯ ПОМЕЩАЕТСЯ В RA

ЗАПИСЬ RES ‘ИЗ RA В РЕГИСТР RAM RES

Для организации правильного порядка выполнения команд структура устройства управления (control unit) предполагает использование двух специальных регистров: регистра текущей команды (РТК) и регистра адреса следующей команды (РАСК). Алгоритм работы устройства управления состоит в следующем:

1. Очередная команда (адрес которой находится в РАСК) передается из оперативной памяти в РТК устройства управления (задействован цикл чтения данных из оперативной памяти), см. рис. 1.21.

2. Содержимое РАСК увеличивается на 1. То есть теперь в РАСК действительно хранится адрес следующей команды.

3. Выполняется команда из РТК. Возможен побочный эффект – модификация содержимого РАСК (это происходит в том случае, если выполняемая команда является командой условной или безусловной передачи управления).

4. Если выполненная в п.3 команда не является командой останова, перейти к п.1, иначе – прекратить вычисления.

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

3. Выполнение команды из РТК с возможной модификацией РАСК

–  –  –

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

переменные, моделирующие ячейки оперативной памяти;

операции над переменными, включая важнейшую операцию присваивания, основанную на пересылке данных из одной ячейки в другую;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Процедурное программирование иерархично по своей природе.

Решение задачи средствами процедурного программирования всегда связано с построением иерархии процедур и функций (рис. 1.23).

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

–  –  –

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

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

Main

–  –  –

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

Main

–  –  –

Рис. 1.25. Логический уровень модульности Для выражения понятия модульности на уровне, учитывающем логические связи между функциями и обрабатываемыми им данными, во многих языках программирования реализованы механизмы пространств имен. Пространство имен (namespace) является абстракцией более высокого уровня, поскольку, в общем случае, одно пространство имен может объединять объекты, определенные в разных файлах, с другой стороны, в одном файле могут быть определены объекты из нескольких пространств имен. Таким образом, концепции физической и логической модульности являются ортогональными (рис. 1.26).

Module1 Module2 Module3

–  –  –

Подробно реализация пространств имен в ряде современных языков программирования (в том числе, в C++), рассматривается в учебном пособии [Пышкин, 2005].

Глава 3. Организация процедурного кода Важнейшим развитием императивной методологии является методология структурно-императивного программирования, или просто – структурное программирование.

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

[Одинцов, 2002]), что подразумевает следование ряду проектных принципов:

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

Функционально-иерархическая декомпозиция.

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

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

Независимая компиляция модулей.

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

Иерархическое проектирование по принципу «сверху – вниз».

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

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

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

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

Систематизируя это описание, В.Ф.

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

1. Совокупность возможных исходных данных.

2. Совокупность возможных результатов.

3. Совокупность возможных промежуточных результатов.

4. Правило начала процесса обработки данных.

5. Правило непосредственной обработки.

6. Правило окончания обработки.

7. Правило извлечения результата.

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

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

Текстуальная форма записи

1. Скопировать значение X во вспомогательную переменную x.

2. Скопировать значение Y во вспомогательную переменную y.

3. Если xy, перейти к п. 4, иначе – к п. 7.

4. Если xy, перейти к п. 5, иначе – к п. 6.

5. Записать в x результат вычисления выражения x-y и перейти к п. 3.

6. Записать в y результат вычисления выражения y-x и перейти к п. 3.

7. Конец. x – результат работы.

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

–  –  –

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

Еще в первом издании книги [Brooks, 1995], вышедшей в свет в 1975 году, Ф. Брукс замечает, что «пошаговая блок-схема является досадным анахронизмом, пригодным только для новичков в алгоритмическом мышлении», и большинство программистов, если это необходимо, рисуют схему алгоритма на основе уже законченной программы.

В статье [Шалыто, Туккель, 2001] авторы утверждают о плохой наглядности и графической избыточности схем алгоритмов даже для простых итерационных алгоритмов. Для полноты картины следует заметить, что ряд специалистов полагает, что плохи не схемы алгоритмов как таковые, а стандарты, в которых, в действительности, не учтены принципы структуризации программ, сформулированные Э. Дейкстрой [Паронджанов, 1999].

Диаграммы Нэсси-Шнейдермана Ряд ученых предлагали различные способы борьбы с логической запутанностью, свойственной схемам алгоритмов и текстуальным описаниям. Один из методов был предложен И. Нэсси и Б. Шнейдерманом в 1973 году [Nassi, Shneiderman, 1973].

Запись алгоритма вычисления наибольшего общего делителя двух положительных чисел представлена на рис. 3.2.

–  –  –

Рис. 3.2. Диаграммы Нэсси-Шнейдермана Основной недостаток диаграмм Нэсси-Шнейдермана определяется их геометрией: для сложных программ либо внешний прямоугольник будет очень большим, либо внутренние элементы – слишком маленькими.

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

Диаграммы Дейкстры В работе по структурному программированию, являющейся частью книги [Dahl, Dijkstra, Hoare, 1972], Э. Дейкстра, по существу, определил альтернативный схемам программ визуальный формализм, который, по не вполне понятным причинам, не был востребован разработчиками стандартов на схемы алгоритмов и программ. Пример записи алгоритма с использованием диаграмм Дейкстры представлен на рис. 3.3.

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

Исходя из того, что соответствующие диаграммы и сами принципы структурного программирования обнаруживаются в одной и той же книге, В.Д. Паронджанов делает вывод об одновременности появления текстовой и визуальной моделей структурного программирования, хотя самого «визуального программирования» как понятия и концепции на тот момент не существовало. Может быть, именно поэтому и «сам отец-основатель, обычно весьма настойчивый в продвижении и популяризации своих идей, отнесся к своему видеоструктурному детищу с удивительным безразличием и ни разу не выступил с предложением о закреплении структурной идеи в стандартах на блок-схемы» [Паронджанов, 1999].

НОД( X, Y )

–  –  –

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

НОД( X, Y ) x:=X;

y:=Y;

пока( x y ) повторять если( x y ) то x:=x-y;

иначе y:=y-x;

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

–  –  –

ДРАКОН-схемы Идея ограничения топологии схем программ с целью их лучшей структуризации и формализации лежит в основе визуального языка программирования ДРАКОН и построенного на его основе шампур-метода как абстрактной визуальной модели программы [Паронджанов, 1999].

Пример простой ДРАКОН-схемы представлен на рис. 3.4.

–  –  –

Визуальная модель программирования на базе шампур-метода и языка ДРАКОН вкратце рассматривается в гл. 7.

Р-схемы Р-схемы являются центральным элементом визуального ядра Р-технологии, разработанной в институте кибернетики Академии наук Украины [Вельбицкий, 1984, 1985]. Р-схема программы нахождения наибольшего общего делителя показана на рис. 3.5.

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

Визуальная часть Р-схемы, по существу, эквивалентна расширенной сети переходов (Augmented Transition Network – ATN) с тем отличием, что в основе ATN лежит формализм автомата Мура, в то время как Р-схема основывается на модели автомата Мили.

Структуры Р-схем Основные элементы

–  –  –

Несомненным успехом разработчиков Р-технологии является факт принятия стандарта на Р-схемы [ГОСТ 19.005-85], и использование этой технологии в многочисленных проектах под руководством В.М. Глушкова.

Определенным недостатком Р-схем является тот факт, что все внимание концентрируется на представлении потока управления, потоки данных никак явно не отображаются.

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

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

Конечный автомат и способы его задания В разд. 1.1 было введено понятие преобразователя информации. Пусть преобразователь информации имеет n входов и p выходов, то есть определены вектор входных сигналов X ( x1, x2,..., xn ) и вектор выходных сигналов Y ( y1, y 2,..., y p ). Зависимость, реализуемая преобразователем информации, может быть функциональной или алгоритмической.

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

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

Абстрактный конечный автомат с выделенным начальным состоянием определяют как шестерка объектов In, Out, State, S0, FTrans, FOut, где:

In = { Ini }, i=1..n – входной алфавит;

Out = { Outj }, j=1..p – выходной алфавит;

State = { Statek }, k=1..s – множество состояний;

S0 – начальное состояние (элемент множества State);

FTrans : StateInState – функции перехода, устанавливающие зависимость перехода автомата из одного состояния в другое от входного сигнала, например Statek+1=FTrans( Statek, Ini ) – функция перехода из состояния Statek в состояние Statek+1 при входном сигнале Ini;

FOut : StateInOut – функции выхода, устанавливающие зависимость выходного сигнала от текущего состояния и сигнала на входе, например, Outj=FOut( Statek, Ini ) – функция выхода Outj,.формируемого при активации перехода из Statek при входном сигнале Ini.

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

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

Автомат имеет два конечных состояния: «успех», соответствующее символу «конец файла» во входном потоке, и «ошибка», соответствующее ситуации, если во входном потоке обнаружен некорректный символ (не цифра, не буква, не пробел и не «конец файла»).

–  –  –

Автомат, определяемый таким образом, называют автоматом Мили.

Существует также модель автомата, называемая автоматом Мура, отличающаяся от автомата Мили тем, что выходная функция зависит только от множества состояний, то есть FOut : StateOut. По вычислительной мощности автомат Мура полностью эквивалентен автомату Мили.

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

Указанных недостатков лишены диаграммы состояний, предложенные Д. Харелом [Harel, 1988], а также SWITCH-технология – подход, основывающийся на программировании реактивных систем в форме сети взаимодействующих автоматов [Шалыто, 1998] (см. гл.7).

Определение конечного автомата, дополненное условием необязательного продвижения по входной цепочке, положено в основу среды разветвленного управления визуального формализма проектирования ПО на базе L-сети, предложенного, теоретически обоснованного и реализованного М.Ф. Лекаревым [Lekarev, 1993], [Лекарев, 1997].

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

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

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

Для реализации разветвлений большинство структурноориентированных языков поддерживают два типа инструкций: условная инструкция (if statement) и мультиветвление (switch statement).

Условная инструкция Условная инструкция (рис. 3.7) позволяет реализовать варианты продолжения исполнения программы в зависимости от истинности или ложности некоторого условия.

Порядок выполнения условной инструкции состоит в следующем:

вычисляется значение условного выражения;

если в двоичном представлении результата есть хотя бы один ненулевой разряд, выполняется ветвь «ДА», иначе (в двоичном представлении все биты – нулевые) – исполняется ветвь «НЕТ».

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

пример сокращенной формы использования условной инструкции на рис. 3.7).

–  –  –

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

if( x ) { // Действия, выполняемые в том случае, когда x!=0 //...

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

int NameIsFound; // Признак обнаружения имени в таблице имен:

// 1 – ДА, имя найдено // 0 – НЕТ, имя не найдено //...

if( NameIsFound ) { // Обработка случая, когда имя найдено //...

} Для проверки «отрицательного» условия естественной выглядит следующая форма записи:

if( !NameIsFound )

–  –  –

if( false == NameIsFound ) { // Обработка случая, когда имя не найдено //...

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

int NumName; // Номер имени в таблице:

// 0 – ИМЯ отсутствует в таблице имен // положительное число – уникальный номер //...

if( NumName != 0 ) // Следует предпочесть записи if( NumName ) { // Обработка случая, когда имя есть в таблице //...

} Для программных объектов со сложной внутренней структурой смысл операции ! может быть определен явно. Обычно в этом случае речь идет об определении корректности или некорректности функционирования объекта в некотором специфичном для этого объекта смысле, например:

#include iostream using namespace std

–  –  –

Как явствует из рисунка, попытка записать сложное условие по правилам математики ведет к семантической ошибке (то есть такой ошибке, которая не может быть установлена транслятором). В действительности, требуется несколько иное, а именно: одновременное выполнение двух простых условий: 3 x и x 2. Таким образом, сложное условие является логической комбинацией простых условий. Логическая связка, используемая в данном случае (одновременное выполнение двух условий) называется логическим «И», или конъюнкцией.

В языках C/С++ предусмотрена специальная операция:

if( -3=x && x2 ) { // x находится в требуемом интервале //...

}

–  –  –

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

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

Максимум из трёх чисел

–  –  –

Конструкция if…else if Во многих практических случаях явное вложение условных инструкций можно заменить особой организацией последовательности выполнения условных инструкций (см. рис. 3.10).

–  –  –

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

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

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

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

Инструкция-while ::=

–  –  –

Решение задачи поиска наибольшего общего делителя с использованием цикла while, было приведено в подразделе «Запись алгоритма в форме текста программы» разд. 3.1.

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

–  –  –

Классическим примером использования цикла с постусловием является реализация опроса внешнего устройства или простого пользовательского ввода (листинг 3.3).

Листинг 3.3.

Цикл с постусловием int inputValue;

bool entered;

do { printf( "Enter integer value:" );

int ret = scanf( "%d”, &inputValue );

if( ret == 1 ) { entered = true;

} else { printf( "Error. This is not integer value!\n” );

entered = false;

} } while( !entered );

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

Преобразование одной формы записи в другую обычно не составляет труда (см. листинг 3.4).

Листинг 3.4.

Преобразование цикла do..while к циклу while int inputValue;

bool entered = false;

–  –  –

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

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

3.13):

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

2. Условие продолжения: проверяется каждый раз перед выполнением очередной итерации (обычно связано с проверкой значения управляющей переменной).

3. Модификация состояния управления циклом (обычно соответствует изменению значения управляющей переменной).

–  –  –

Рис. 3.13. Цикл с фиксированным числом повторений В языке C++ семантику цикла с фиксированным числом повторений реализует инструкция for (см. рис. 3.14).

Инструкция-for ::=

–  –  –

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

Цикл с нестандартной структурой В ряде случаев условие, определяющее необходимость прекращения цикла, удобно проверять не в начале или конце итерации, а где-то посередине (см. рис. 3.16 и листинг 3.6).

–  –  –

ProcessResponse();

} Для выхода из цикла в этом случае удобно использовать специальную инструкцию языка – инструкцию break.

Наряду с инструкцией break, C++ содержит также инструкцию continue, позволяющую обойти ряд инструкций в теле цикла (рис. 3.17).

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

Листинг 3.7.

Преобразование цикла с нестандартной структурой bool InProgress = true;

–  –  –

Рекомендации по использованию break и continue Инструкцию break следует использовать для организации циклов с нестандартной структурой, в том числе и таких циклов, в которых проверяется последовательно сразу несколько условий.

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

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

Листинг 3.8.

Функция пропуска комментария в сканируемом тексте на языке C static FILE * fin; // Файл, содержащий текст для анализа static char litera; // Очередная читаемая литера /*

–  –  –

Циклы, основанные на структурах данных Некоторые языки поддерживают дополнительный вид циклических структур, основанный на структурах данных и используемый для просмотра содержимого наборов объектов (коллекций, списков, множеств и т. п.). В языках Visual Basic, Perl, C# подобный цикл называется цикл foreach (по наименованию соответствующей инструкции языка).

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

Пример использования цикла foreach на языке C# иллюстрирует листинг 3.9.

Листинг 3.9.

Цикл для обработки ассоциативного массива в языке C# using System;

using System.Collections;

–  –  –

persons.Add("Мелехин","Архитектура вычислительных систем");

persons.Add("Бабко","Теория автоматичиского управления");

persons.Add("Давыдов","Теория и технология программирования");

persons.Add("Павловский","Микропроцессорные системы");

persons.Add("Ицыксон","Технологии компьютерных сетей");

foreach( string teacher in courses ) { Console.Writeline( teacher + " читает " + courses[teacher] );

} } } Подробнее о реализации hash-таблиц и ассоциативных массивов см. в разд. 5.4.

Использование определяемых пользователем итераций играет важную роль в ООП. В С++ итераторы для типов, определенных пользователем, реализуются в виде дружественных функций, вложенных классов или в виде отдельных классов, а соответствующие циклы конструируются на базе стандартных циклов for и while (см. [Пышкин, 2005]).

–  –  –

В знаменитой статье 1968 года Э. Дейкстра определил так называемую ортодоксальную модель управления вычислениями в структурном программировании. В соответствии с ней, использование безусловной передачи управления (goto) является вредным и влечет гибельные последствия, поэтому инструкция goto должна быть исключена из структурных языков программирования [Dijkstra, 1968]. Э. Дейкстра полагал, что качество кода обратно пропорционально числу goto, используемых в программе, а корректность программы, не содержащей goto, обычно проще доказать (если вообще ее можно доказать).

Так, программа, соответствующая алгоритму цикла с нестандартным условием (см. рис.

3.16 и листинг 3.6) в соответствии со строгими требованиями структурного программирования должна быть переписана в следующей форме:

bool InProgress = true;

–  –  –

if( ResponseIsBad() ) InProgress = false else { ProcessResponse();

} } Нетрудно убедиться, что в большинстве универсальных алгоритмических языков инструкция goto все-таки присутствует. Замечая, что код, содержащий goto, редко является самым быстрым и самым компактным из возможных реализаций, Д. Кнут, тем не менее, утверждал, что формальное устранение goto может в ряде случаев приводить к громоздкому коду [Knuth, 1974]. По мнению Д. Кнута, использование goto может оказаться оправданным и в хорошо структурированных программах, например, при выходе из нескольких вложенных циклов или при написании процедур, которые распределяют ресурсы, выполняют некоторые операции (с возможными разветвлениями), а затем – освобождают занятые ресурсы.

При этом освобождение ресурсов целесообразно осуществлять в одном месте (рис. 3.18). Безусловно, немотивированного использования goto следует избегать, но не ценой ясности программы.

В ряде языков существуют заменители goto типа рассмотренных выше инструкций break и continue в C/C++ (например, инструкция exit в языках Ada и Modula-2). Б. Керниган указывал на следующие преимущества заместителей по отношению к goto: во-первых, они, как правило, не требуют метки, во-вторых, передают управление в конкретную точку, исключая некорректное или нежелательное использование.

–  –  –

Вообще, следует иметь в виду, что в соответствии с теоремой о структурировании, любая программа может быть преобразована к структурированной программе, составленной из элементов базисного множества {последовательность, ветвление, цикл} (строгую формулировку и доказательство см. в. [Linger, Mills, Witt, 1979, §4.4.3]).

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

В [McConnell S., 1993] приводится пример вполне разумного участка кода, где написать ясный корректный эквивалент, не использующий goto, не так уж просто (листинг 3.10):

Листинг 3.10.

Задача на устранение goto if( StatusOK ) { if( DataIsAvailable ) { ImportantVar = x;

goto EXTRA_WORK;

} } else { ImportantVar = GetValue();

–  –  –

В связи с этим С. МакКоннелл предлагает помнить о том, что в 90 случаях из 100 преобразование текста, содержащего goto к тексту без оного, может быть осуществлено без особых усилий. В 9 случаях из 100 преобразование, возможно, потребует некоторых усилий или консультаций с более квалифицированным программистом, но оно, безусловно, должно быть осуществлено. Оставшийся 1%, вероятно, соответствует случаям, когда использование goto уместно, и в целом не нарушает связность программного текста и ясность его восприятия: «если вы в сапогах, вероятно, не стоит обходить к а ж д у ю лужицу».

В целом, можно руководствоваться следующими основными правилами:

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

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

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

Если вы – руководитель проекта (или преподаватель), исходите из того, что баталия из-за единственного goto, возможно, не стоит поражения во всей войне: если программист д е й с т в и т е л ь н о о с в е д о м л е н о возможных вариантах решения проблемы (это преподавателю стоит проверить!) и может аргументировать свою позицию, возможно, перед нами как раз один из 1% случаев.

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

–  –  –

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

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

Например, в языке Pascal мультиветвление (обычно называемое оператором выбора) реализовано так, как показано на рис. 3.20.

В языке C++ продолжение исполнения программы после перехода осуществляется в строгом соответствии с фон Неймановским принципом последовательных вычислений. Для выхода за пределы мультиветвления следует дополнительно использовать специальную инструкцию break (рис. 3.21).

–  –  –

Рис. 3.21. Реализация мультиветвления (язык C) Два простых примера, представленных ниже, иллюстрирует особенности обработки мультиветвления в языках C/C++.

#include stdio.h

–  –  –

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

Реализация программной модели конечного автомата Мультиветвления позволят достаточно наглядно и просто реализовать программную модель конечного автомата. Для конечного автомата, распознающего идентификаторы (см. разд.

3.1.), построение соответствующей программной модели иллюстрирует листинг 3.11:

Листинг 3.11.

Конечный автомат, распознающий идентификаторы #include stdio.h #include stdlib.h #include ctype.h

–  –  –

return lit.synterm = NOALP;

} /* * LEXema: register FIRST litera * Функция регистрации первой литеры в составе лексемы */ void LexFirst( Lexema& lex, const Litera& lit ) { lex.ix = 0;

lex.ixLast = 30;

lex.value[ 0 ] = lit.value;

} /* * LEXema: register NEXT litera * Функция регистрации очередной литеры в составе лексемы */ void LexNext( Lexema& lex, const Litera& lit ) { if( lex.ix != lex.ixLast ) { lex.value[ ++lex.ix ] = lit.value;

} } /* * LEXema: STOP register literas * Функция завершения регистрации литер в составе лексемы

–  –  –

case ERROR : fprintf( output, "Stopped in error state\n" );

return;

} } } Отметим, что, как показано в [Лекарев, 2000-4], продвижение по входной цепочке не является в общем случае обязательным при каждом переходе конечного автомата. Если конечный автомат не осуществляет автоматического чтения при каждом переходе, то такая модель автомата может распознавать язык, не распознаваемый обычным конечным автоматом. Поэтому программная модель позволит обеспечить бльшую общность решения, если операцию GetLit перенести внутрь обработчиков состояний, подчеркивая тем удобство во многих практических случаях реализации считывания из входного потока явным образом.

Соответствующую модификацию кода оставляем для самостоятельного упражнения.

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

if( StatusOK ) { if( DataIsAvailable ) { ImportantVar = x;

ExtraWork( ImporatantVar );

} } else { ImportantVar = GetValue();

ExtraWork( ImporatantVar );

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

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

Стоит привести замечательное эссе на эту тему из уникального в своем роде романа-головоломки французского писателя Жоржа Перека [Perec, 1978]:

“l’objet vis – qu’il s’agisse d’un acte perceptif, d’un apprentissage, d’un systme physiologique ou, dans le cas qui nous occupe, d’un puzzle de bois – n’est pas une somme d’lments qu’il faudrait d’abord isoler et analyser, mais un ensemble, c’est--dire une forme, une structure: l’lment ne prexiste pas l’ensemble, il n’est ni plus immdiat, ni plus ancien, ce ne sont pas les lments qui dterminent l’ensemble, mais l’ensemble qui dtermine les lments: la connaissance du tout et de ses lois, de l’ensemble et de sa structure, ne saurait tre dduite de la connaissance spare des parties qui le composent: cela veut dire qu’on peut regarder une pice d’un puzzle pendant trois jours et croire tout savoir de sa

configuration et de sa couleur sans avoir le moins du monde avanc:

seule compte la possibilit de relier cette pice d’autres pices, et en ce sens il y a quelque chose de commun entre l’art du puzzle et l’art du go; seules les pices rassembles prendront un caractre lisible, prendront un sens: considre isolment une pice d’un puzzle ne veut rien dire; elle est seulement question impossible, dfi opaque;

mais peine a-t-on russi, au terme de plusieurs minutes d’essais et d’erreurs, ou en une demi-seconde prodigieusement inspire, la connecter l’une de ses voisines, que la pice disparat, cesse d’exister en tant que pice...” Georges Perec. “La Vie, mode d’emploi”, prambule Итак, задачи построения иерархии проекта, проблемы определения его файлового и функционального состава образуют неотъемлемые составляющие процесса проектирования. Без грамотно принятых решений "...объект, представленный нашему вниманию, будь то акт восприятия, узнавания, функциональная система [sic! - курсив мой - Е.П.] или в том случае, который нас занимает – картонная мозаика – не образуется суммой элементов, которые требовалось бы сначала изолировать друг от друга, и затем анализировать, но единое целое, то есть некая структура, форма: элемент не предшествует в своем существовании целому, он не опережает целое и не одновременен с ним, не отдельные элементы определяют целое, но целое определяет свой элементный состав: знание о законах целого и о его структуре невозможно было бы вывести из информации о его отдельных частях. Иными словами, можно разглядывать кусочек мозаики в течение трех дней и изучить столь досконально его конфигурацию и его цвета, что добавить что-нибудь к этому знанию будет невозможно до тех пор, пока мы не примем в расчет возможность соединения этого элемента с другими, и в этом смысле есть нечто общее между искусством составления мозаики и искусством го: только вместе собранные части обретут видимый, распознаваемый [досл. lisible – читаемый] смысл, – взятая изолированно частичка не означает ничего, лишь повисший вопрос, смутный намек, но стоит только найти одну из соседних с ней, может быть через долгие минуты проб и ошибок, может быть в долю мгновенья чудесным озарением, как частичка вдруг исчезает, перестает существовать..." – Жорж Перек. Жизнь, способ употребления. Из авторского предисловия (перевод с франц.: Е.П.) уже на стадии формулирования технического задания хороший проект невозможен.

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

Листинг 3.12.

Функциональная декомпозиция программной модели конечного автомата #include stdio.h #include stdlib.h #include ctype.h

–  –  –

// Прототипы функций обработки состояний конечного автомата StateType Process_S0( const Litera&, Lexema& ident );

StateType Process_NXTLIT( const Litera&, Lexema&, FILE* output );

void Process_STOP( FILE* output );

void Process_ERROR( FILE* output );

–  –  –

void Process_ERROR( FILE* output ) { fprintf( output, "Stopped in error state\n" );

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

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

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

«сверху вниз», «снизу вверх», «изнутри к границам», «от границ внутрь».

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

Рис. 3.23. Нисходящая функциональная декомпозиция

Проектирование «сверху вниз» позволяет проектировать высокоуровневые абстракции, основываясь на анализе предметной области, однако повторное использование спроектированных компонентов, как правило, затруднено. Кроме того, в сложном проекте, когда за отдельные части отвечают разные разработчики может возникать дублирование компонентов. При использовании стратегии «снизу вверх» проще создавать базовые обобщенные алгоритмы с их последующим многократным использованием, однако труднее прогнозировать вписываемость этих компонентов в высокоуровневую архитектуру [Coplien, 1999].

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

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

–  –  –

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

[Gries, 1971].

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

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

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

Большинство языков программирования предоставляют самостоятельные синтаксические средства для определения как процедур, так и функций (Pascal, PL/1, FORTRAN, Ada и др.).

–  –  –

if correct then writeln( 'Date is correct' ) else writeln( 'Date is incorrect' ) end;

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

В некоторых языках семантика процедур и функций соединена в одной синтаксической конструкции, обычно называемой функцией (C, C++, Java, C#).

Эквивалентные функциональные блоки, написанные на языке C, представлены в листинге 3.14.

Листинг 3.14.

Функции C/C++ #include stdio.h

–  –  –

if( correct ) printf( "Date is correct\n" );

else printf( "Date is incorrect\n" );

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

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

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



Pages:   || 2 |


Похожие работы:

«УСТРОЙСТВО КОНТРОЛЯ ПАРАМЕТРОВ ДВУХТАКТНОГО ДВИГАТЕЛЯ Руководство по эксплуатации. Паспорт АБВГ.466369.001 РЭ Москва СОДЕРЖАНИЕ ВВЕДЕНИЕ 1. НАЗНАЧЕНИЕ 2. ТЕХНИЧЕСКИЕ ХАРАКТЕРИСТИКИ 3. КОМПЛЕКТНОСТЬ 4. ПРИНЦИП РАБОТЫ 5. УКАЗАНИЕ М...»

«Філософія УДК 37.01.37(09) ЯН ЗУБЕЛЕВИЧ доктор философских наук, профессор кафедры философии факультета Администрации и социальных наук Варшавского политехнического института (Варшава, Польша) j.zubelewicz@ans.pw.edu.pl _ ОБЩАЯ ПЕДАГОГИКА БОГУСЛАВА ВОЛ...»

«Устройства сбора данных L-761, L-780 и L-783 Платы АЦП/ЦАП/ТТЛ на шину PCI 2.1 Руководство пользователя Москва. Май 2009 г. Ревизия документа C1 ЗАО "Л-КАРД", 117105, г. Москва, Варшавское шоссе, д. 5, корп. 4, стр. 2...»

«ПРОДОВОЛЬСТВЕННАЯ БЕЗОПАСНОСТЬ Дмитрий Леонидович Азин Кандидат технических наук, доцент, заведующий кафедрой товароведения продовольственных продуктов Уральского государственного экономического университет...»

«Теория и история архитектуры, реставрация Известия КГАСУ, 2016, № 4 (38) и реконструкция историко-архитектурного наследия УДК 72.01 Денисенко Е.В. – кандидат архитектуры, старший преподаватель E-mail: e.v.denisenko@bk.ru Казанский государственный архитектурно-строительный университет Адрес организации: 420043,...»

«СПОРТ УДК 796.83:796.012.2 СТАНОВЛЕНИЕ ТЕХНИЧЕСКОГО МАСТЕРСТВА ДЕВУШЕК-БОКСЕРОВ ПОСРЕДСТВОМ РАЗВИТИЯ СЕНСОМОТОРНОЙ КООРДИНАЦИИ Т.С. Аслаев, Н.Ю. Токмакова Представлена методика совершенствования технического мастер...»

«Техническое задание Сайт муниципального образования Типовая структура сайта крупного муниципального образования 1. Главная страница 1.1. О сайте 2. Муниципальное образование 2.1. Карта муниципального образования (интерактивная...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Механико-математический факультет Кафедра теоретической кибернетики Н. Н. Токарева Симметричная криптография. Краткий курс Учебное пособие Новосибирск УДК 519.7 ББК 22.1 Т 510 ISB...»

«Сибирское отделение РАН Государственная публичная научно-техническая библиотека Сибирский региональный библиотечный центр непрерывного образования Л.А. Кожевникова ЭКОНОМИКА БИБЛИОТЕКИ В ВОПРОСАХ И ОТВЕТАХ Учебно-методическое пособие Новосибирск УДК 02:338.4(075.8...»

«Технологии и технические средства механизированного производства кормов и продукции животноводства. Региональная целевая комплексная программа интенсификации кормопроизводства "Корма" Ленинградской области на 2000-2005 гг. – СПб.: СЗНИИМЭСХ, 2000. – 133 с. Получено 12.05.2003. УДК 631.354:519 А. Н. ПЕРЕКОПСКИЙ, канд....»

«Галиев Ильгиз Гакифович ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ЭКСПЛУАТАЦИИ ТРАКТОРОВ ПУТЕМ ОБЕСПЕЧЕНИЯ ИХ РАБОТОСПОСОБНОСТИ ДЛЯ РАЗЛИЧНЫХ УСЛОВИЙ АГРАРНОГО ПРОИЗВОДСТВА (на примере хозяйств республики Татарстан) Специальности: 05.20.01технологии и средства механизации сельского хозяйства 05.20.03технологии и средства технического обслуживания в...»

«Юрасов Алексей Владимирович Адаптация логистических систем управления товародвижением к конъюнктуре потребительского рынка.1. Теоретические основы функционирования логистических систем товарного рынка...»

«ОАО ЮТЭК Баланс (Форма №1) 2009 г. Статья баланса Код строки Начало года Конец года АКТИВ I. ВНЕОБОРОТНЫЕ АКТИВЫ Нематериальные активы 110 0 0 Основные средства 120 466 709 469 002 Незавершенное строительство 130 2 183 869 2 115 446...»

«Федеральное агентство по образованию Архангельский государственный технический университет Институт экономики, финансов и бизнеса ТРУД И ЗАРАБОТНАЯ ПЛАТА В ЛЕСНОМ ХОЗЯЙСТВЕ Методические указания к практическим занятиям АгТу Архангельск 2007 Р...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ" И.Г. ВИДЯЕВ, Г.Н. СЕРИКОВА, Н.А. ГАВРИКОВА ФИНАНСОВЫЙ МЕНЕДЖМЕНТ, РЕСУРСОЭФ...»

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

«Запрос ценовых предложений Объект закупки: замена лифта больничного в корпусе № 15 ГБУЗ МО МОНИКИ им. М.Ф. Владимирского г. Москва "31" марта 2016г. Государственное бюджетное учреждение здравоохранения Московской области "Московский областной нау...»

«ПЛАНИРОВАНИЕ НА ПРЕДПРИЯТИИ ИЗДАТЕЛЬСТВО ТГТУ инистерство образования и науки Российской Федерации ГОУ ВПО "Тамбовский государственный технический университет" ПЛАНИРОВАНИЕ НА ПРЕДПРИЯТИИ Методические указан...»

«212 МАШИНОСТРОЕНИЕ Xсуп Y суп Z суп B`=360*1 Xw B` Xi X сал Zсал Y сал Yw X с X ст Yi Zст Yст Zw Yc Zi +Z c 0 Zwp Ywp -Z д 0 wp +Y д +X д X b Xн Yн 9 92 ( 16 09 00 ) 60 Z -4 a 50 0 Zн 0 Y Zп Рис.2. Системы координат ГМП FC440К Yп (общий вид...»

«199004, Санкт-Петербург Тел.: +7 (812) 327-7979 В.О., Малый пр., 22, лит. А Факс +7 (812) 327-7979 Бизнес-центр "Соверен" www.sevgorod.ru ДОГОВОР № участия в долевом строительстве жилого дома по адресу: г.Санкт-Петербург, Петровский просп...»

«Заключая ЛИЦЕНЗИОННЫЙ ДОГОВОР с нашей компанией, Вы действуйте в рамках Российского законодательства. Мы являемся обладателем исключительного права на предлагаемый Вам музыкальный материал. Наши права возникли в соответствии со ст. 1288 ГК РФ по договорам авторского заказа. Публичное исполнение произведений — это представление произв...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.