Структурные языки программирования

Структурное программирование

— Учитель,- проговорил Сунь У-кун.- Я человек простой и вашего городского языка не понимаю. Что значат подпорки к стене?

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

У Чэн-энь. «Путешествие на Запад», глава 2

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

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

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

Начнем с того, что обратимся к истории.

В теории схем программ было замечено, что некоторые случаи блок-схем легче поддаются анализу [ 16 ] . Поэтому естественно было выделить такой класс блок-схем, что и сделали итальянские ученые С. Бем и К. Джакопини в 1966 г. Они доказали, что любую блок-схему можно привести к структурированному виду, использовав несколько дополнительных булевых переменных. Э. Дейкстра подчеркнул, что программы в таком виде, как правило, являются легче понимаемыми и модифицируемыми, так как каждый блок имеет один вход и один выход .

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

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

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

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

Средства структурного программирования в первую очередь включаются во все языки программирования традиционного типа и во многие нетрадиционные языки. Они занимают основное место в учебных курсах программирования и в теоретических работах (например, [ 1 ] , [ 4 ] , [ 9 ] ).

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

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

действия и условия локальны.

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

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

Для структурного стиля программирования требуется следующее. Задача разбивается на подзадачи, и таким образом выстраивается дерево вложенности подзадач. Информационное пространство структурируется в точном соответствии с деревом вложенности: для каждой подзадачи оно состоит из ее локальных объектов, определяемых вместе с подзадачей и для нее, и так называемых глобальных объектов, определяемых как информационное пространство непосредственно объемлющей подзадачи. Таким образом, информационное пространство всей задачи (подзадачи самого верхнего уровня) расширяется по мере перехода к подзадачам за счет их локальных объектов. Для различных дочерних подзадач одной подзадачи оно имеет общую часть — информационное пространство родительской подзадачи 3 В этой системе требований без труда распознается так называемая блочная структура языков программирования, появившаяся еще в Algol 60 и ставшая в настоящее время фактическим стандартом. .

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

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

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

Первым обратил внимание на необходимость введения призраков для логического и концептуального анализа программ Г. С. Цейтин в 1971 г. В Америке это «независимо» открыли заново в 1979 г., хотя упомянутая статья Цейтина была опубликована на английском языке в общедоступном издании. Даже название сущностям было дано то же самое. Этому важнейшему и традиционно игнорируемому понятию посвящена отдельная лекция в курсе «Основания программирования» [ 21 ] .

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

Для структурного программирования весьма важно требование:

Все структуры подчиняются структуре информационного пространства.

Это общее требование конкретизируется в следующие.

1. Необходимо, чтобы структура управления программы была согласована со структурой ее информационного пространства. Каждой структуре управления соответствуют согласующиеся с ней структуры данных и часть информационного пространства. Это условие позволяет человеку легко отслеживать порядок выполнения конструкций в программе.
2. Подзадачи могут обмениваться данными только посредством обращения к объектам из общей части их информационных пространств (в современных языках чаще всего к глобальным).
3. Информационные потоки должны протекать согласно иерархии структур управления; мы должны четко видеть для каждого блока программы, что он имеет на входе и что дает на выходе. Таким образом, свойства каждого логически завершенного фрагмента программы должны ясно осознаваться и в идеале четко описываться в самом тексте программы и в сопровождающей ее документации 5 Как видим, программа должна составляться после того, как программист хорошенько подумал, а не до того. .
4. Описание переменных, представляющих перерабатываемые объекты, а также других, вспомогательных переменных при структурном программировании строго подчиняется разбиению задачи на подзадачи.
5. Все призраки действуют на своем структурном месте и соответствуют идеальным сущностям, которые, согласно парадоксу изобретателя, должны вводиться для эффективного решения задачи.
6. Все подпорки строго локализованы в том месте, где их вынуждены ввести. Желательно даже обозначать их по-другому, чем идеальные сущности, например, оставляя мнемонические имена лишь для идеальных сущностей, а подпорки именовать джокерами типа x или i . Необходимо строго следить за тем, чтобы подпорки не искажали идеальную структуру программы.

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

Структурное программирование

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

Используя язык высокого уровня (такой как Фортран) программисты могли писать программы до несколько тысяч строк длиной. Однако язык программирования, легко понимаемый в коротких программах, когда дело касается больших программ, становится нечитабельным (и неуправляемым). Избавление от таких неструктурированных программ пришло после создания в 1960 году языков структурного программирования. К ним относятся языки Алгол, Паскаль и С.

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

Структурное программирование тесно связано такими понятиями как «нисходящее проектирование» и «модульное программирование».

Метод нисходящего проектирования предполагает последовательное разложение функции обработки данных на простые функциональные элементы («сверху-вниз»).

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

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

1) определяются цели автоматизации предметной области и их иерархия;

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

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

4) определяются необходимые для решения задач функции обработки данных;

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

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

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

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

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

· циклической (цикл, или повторение).

Эта теорема была сформулирована в 1966 г. Боймом и Якопини (Corrado Bohm, Guiseppe Jacopini). Главная идея теоремы – преобразовать каждую часть программы в одну из трех основных структур или их комбинацию так, чтобы неструктурированная часть программы уменьшилась. После достаточного числа таких преобразований оставшаяся неструктурированной часть либо исчезнет, либо становится ненужной. В теореме доказывается, что в результате получится программа, эквивалентная исходной и использующая лишь упоминавшиеся основные структуры.

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

В алгоритмическом языке С (С++) для реализации структурного кодирования используются следующие операторы:

· объявление (только в С++).

Структура «следование»(рис. 5.1, а) реализуется составным оператором, оператором-выражение, asm-оператором и др.

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

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

Компилятор языка C++ выполняет операторы-выражения, вычисляя выражения. Все побочные эффекты от этого вычисления завершаются до начала выполнения следующего оператора. Большинство операторов-выражений представляют собой операторы присваивания или вызовы функций (например, printf(), scanf() ). Особым случаем является пустой оператор, состоящий из одной точки с запятой (;). Пустой оператор не выполняет никаких действий. Однако он полезен в тех случаях, когда синтаксис C++ ожидает наличия некоторого оператора, но по программе он не требуется (например, бесконечный цикл for ).

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

Структура «развилка» (рис. 5.1, б, в) реализуется операторами выбора. Операторы выбора, или операторы управления потоком, выполняют выбор одной из альтернативных ветвей программы, проверяя для этого определенные значения. Существует два типа операторов выбора: if. else и switch.

Базовый оператор if(рис. 5.1, б) имеет следующий формат:

Язык C++ в отличие от, например, языка Паскаль не имеет специального булевого типа данных. В условных проверках роль такого типа может играть целочисленная переменная или указатель на тип. Условное_выражение должно быть записано в круглых скобках. Это выражение вычисляется. Если оно является нулевым (или пустым в случае типа указателя), мы говорим, что условное_выражение ложно(false); в противном случае оно истинно(true).

Если предложение else отсутствует, а условное_выражение дает значение «истина», то выполняется оператор_если_»истина»; в противном случае он игнорируется.

Если задано предложение оператор_если_»ложь», а условное_выражение дает значение «истина», то выполняется оператор_если_»истина»; в противном случае выполняется оператор_если»ложь».

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

if (!ptr). или if (ptr = = 0).

Оператор_если_»ложь» и оператор_если_»истина» сами могут являться операторами if, что позволяет организовывать любую глубину вложенности условных проверок. При использовании вложенных конструкций if. else следует быть внимательным и обеспечивать правильный выбор выполняемых операторов. Любая неоднозначность конструкции «else» разрешается сопоставлением else с последним найденным на уровне данного блока if без else.

if (x == 1)

if (y == 1) puts(«x=1 и y=1»);

else puts(«x != 1»);

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

else puts(«x=1 и y!=1»);

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

if (x = = 1)

if (y = = 1) puts(«x = и y=1»);

else puts(«x != 1»); // правильное решение

Оператор switch (см. рис. 5.1, в) использует следующий базовый формат:

switch (переключающее_выражение) case_оператор;

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

caseконстантное_выражение_i : case_оператор_i;

где каждое константное_выражение_i должно иметь уникальное целочисленное значение (преобразуемое к типу переключающего_выражения) в пределах объемлющего оператора switch.

Допускается иметь в одном операторе switch повторяющиеся константы case.

Оператор может иметь также не более одной метки default:

После вычисления переключающего_выражения выполняется сопоставление результата с одним из константных_выражений_i. Если найдено соответствие, то управление передается case_оператору_i с меткой, для которой найдено соответствие. Если соответствия не найдено и имеется метка default, то управление передается оператору_умолчания. Если соответствие не найдено, а метка default отсутствует, то никакие операторы не выполняются. Для того чтобы остановить выполнение группы операторов для конкретного варианта, следует использовать оператор break.

Структурное программирование

— Учитель,- проговорил Сунь У-кун.- Я человек простой и вашего городского языка не понимаю. Что значат подпорки к стене?

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

У Чэн-энь. «Путешествие на Запад», глава 2

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

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

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

Начнем с того, что обратимся к истории.

В теории схем программ было замечено, что некоторые случаи блок-схем легче поддаются анализу [ 16 ] . Поэтому естественно было выделить такой класс блок-схем, что и сделали итальянские ученые С. Бем и К. Джакопини в 1966 г. Они доказали, что любую блок-схему можно привести к структурированному виду, использовав несколько дополнительных булевых переменных. Э. Дейкстра подчеркнул, что программы в таком виде, как правило, являются легче понимаемыми и модифицируемыми, так как каждый блок имеет один вход и один выход .

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

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

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

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

Средства структурного программирования в первую очередь включаются во все языки программирования традиционного типа и во многие нетрадиционные языки. Они занимают основное место в учебных курсах программирования и в теоретических работах (например, [ 1 ] , [ 4 ] , [ 9 ] ).

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

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

действия и условия локальны.

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

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

Для структурного стиля программирования требуется следующее. Задача разбивается на подзадачи, и таким образом выстраивается дерево вложенности подзадач. Информационное пространство структурируется в точном соответствии с деревом вложенности: для каждой подзадачи оно состоит из ее локальных объектов, определяемых вместе с подзадачей и для нее, и так называемых глобальных объектов, определяемых как информационное пространство непосредственно объемлющей подзадачи. Таким образом, информационное пространство всей задачи (подзадачи самого верхнего уровня) расширяется по мере перехода к подзадачам за счет их локальных объектов. Для различных дочерних подзадач одной подзадачи оно имеет общую часть — информационное пространство родительской подзадачи 3 В этой системе требований без труда распознается так называемая блочная структура языков программирования, появившаяся еще в Algol 60 и ставшая в настоящее время фактическим стандартом. .

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

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

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

Первым обратил внимание на необходимость введения призраков для логического и концептуального анализа программ Г. С. Цейтин в 1971 г. В Америке это «независимо» открыли заново в 1979 г., хотя упомянутая статья Цейтина была опубликована на английском языке в общедоступном издании. Даже название сущностям было дано то же самое. Этому важнейшему и традиционно игнорируемому понятию посвящена отдельная лекция в курсе «Основания программирования» [ 21 ] .

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

Для структурного программирования весьма важно требование:

Все структуры подчиняются структуре информационного пространства.

Это общее требование конкретизируется в следующие.

1. Необходимо, чтобы структура управления программы была согласована со структурой ее информационного пространства. Каждой структуре управления соответствуют согласующиеся с ней структуры данных и часть информационного пространства. Это условие позволяет человеку легко отслеживать порядок выполнения конструкций в программе.
2. Подзадачи могут обмениваться данными только посредством обращения к объектам из общей части их информационных пространств (в современных языках чаще всего к глобальным).
3. Информационные потоки должны протекать согласно иерархии структур управления; мы должны четко видеть для каждого блока программы, что он имеет на входе и что дает на выходе. Таким образом, свойства каждого логически завершенного фрагмента программы должны ясно осознаваться и в идеале четко описываться в самом тексте программы и в сопровождающей ее документации 5 Как видим, программа должна составляться после того, как программист хорошенько подумал, а не до того. .
4. Описание переменных, представляющих перерабатываемые объекты, а также других, вспомогательных переменных при структурном программировании строго подчиняется разбиению задачи на подзадачи.
5. Все призраки действуют на своем структурном месте и соответствуют идеальным сущностям, которые, согласно парадоксу изобретателя, должны вводиться для эффективного решения задачи.
6. Все подпорки строго локализованы в том месте, где их вынуждены ввести. Желательно даже обозначать их по-другому, чем идеальные сущности, например, оставляя мнемонические имена лишь для идеальных сущностей, а подпорки именовать джокерами типа x или i . Необходимо строго следить за тем, чтобы подпорки не искажали идеальную структуру программы.

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

Try Objective-с

сайта «Try Objective-c — программирование для начинающих»!

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

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

Сам процесс обучения программированию довольно трудоемок, но если у вас есть цель — то у вас все получится!

Заучивать весь представленный материал нет необходимости. Главное — чтобы вы понимали саму суть здесь изложенного.

• Просмотров: 21792
• Автор: Midav
• Дата: 5-10-2012, 00:57

1.17 Типы программирования. Часть 1. Структурное программирование. Циклы

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

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

Формальные языки характерны тем, что имеют четкие синтаксические правила.
Например запись 2×2=4 является синтаксически правильной математической записью, а 2=+4 – нет.

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

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

Парадигма программирования — это некий набор правил, который определяет стиль написания программ.

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

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

Перевод осуществлён Kovalev Filipp

Это обзорная лекция профессора Джери Кейн с факультета Computer Sciense университета Стэнфорд.
Парадигмы программирования представляют несколько языков, включая C, Ассемблер, C++, Параллельное программирование, Sheme и Python.
Цели данного курса — научить слушателей как писать код на каждом из этих языков и понимать парадигмы программирования, представляемые этими языками.

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

Рассмотрим основные моменты касающиеся структурного программирования.

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

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

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

2
Ветвление (if) — это однократное выполнение одной из двух или более операций, в зависимости от выполнения некоторого заданного условия;
Операторы выполняющие функции ветвления имеют название — условные операторы.

Условие — любое выражение
Оператор — любой допустимый оператор или блок операторов
Если условие истинно — оператор будет выполнен.
Если условие ложно — оператор будет пропущен

Условный оператор if может быть усложнен служебным словом else — иначе
Это слово позволяет получить законченность условного оператора if, которое будет выражаться так:

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

— Цикл for
Для организации цикла for необходимо выполнить три обязательных действия:
— установить начальные значения переменных
— проверять истинность условия цикла
— на каждом шаге изменять значение счетчика чикла

— Выражение 1 — инициализация (выполняется только один раз в самом начале цикла)
— Выражение 2 — условие цикла (выполняется на каждом последующем витке цикла)
— Выражение 3 — приращение счетчика (выполняется на каждом последующем витке цикла после выполнения оператора)

циклы с предусловием (while)
— сперва выполняется условие (проверяется его истинность или ложность) и только после этого выполняется сам цикл. Данный цикл может не выполниться ни разу если результатом проверки окажется «ложь».

Условие — любое выражение
Оператор — любой допустимый оператор или блок операторов

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

В программе циклы могут быть ВЛОЖЕННЫЕ друг в друга произвольным образом.

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

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

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

Например в программе мы можем какой либо переменной присвоить значение (результат) какой то функции:
x = function(y)
Здесь мы переменной Х присваиваем значение Y, которое вернула функция function
(синтаксис мы будем рассматривать позднее)
В языке СИ например, что процедура, что функция называются одинаково — функция. Независимо от того какую работу они выполняют.

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

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

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

Структурное программирование

Применение структурного программирования позволяет увеличить скорость написания программ и облегчить отладку написанной программы. Структурное программирование возможно и на языках программирования assembler, где не предусмотрено структурных операторов, подобных структурным операторам языков программирования C, PASCAL, PL/M.

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

Программирование для микроконтроллеров во многом повторяет тот же путь. Переход от этапа к этапу зависит от доступных внутренних ресурсов микроконтроллеров. Ещё несколько лет назад использование языков высокого уровня было невозможно из-за малого объёма внутренней памяти программ. (В дешёвых моделях микроконтроллеров эта ситуация сохраняется до сих пор.) В настоящее время с появлением микроконтроллеров и сигнальных процессоров с объёмом внутренней памяти в несколько десятков килобайт появляется возможность объектного проектирования.

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

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

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

Алгоритмическое изображение оператора

Структурно-логическая цепочка «линейная цепочка операторов» легко реализуется на всех языках программирования. На языке программирования СИ она выглядит следующим образом:

Не вызывает затруднений и ее реализация на языке программирования asm-51:

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

Алгоритмическое изображение оператора

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

На языке программирования ассемблер, реализация условного оператора встречает определенные трудности. Для того, чтобы организовать два параллельных плеча потребуется применение команд безусловного перехода. Собственно проверка условия выполняется командой условного перехода. Пример шаблона условного оператора на языке программирования asm-51:

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

Алгоритмическое изображение оператора

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

Язык программирования asm-51

Третий структурный оператор — это оператор цикла с проверкой условия после тела цикла. Такой оператор легко реализуется на языке программирования ассемблер при помощи команды условного или безусловного перехода. Отличие от условного оператора заключается в том, что передача управления осуществляется не вперёд, а назад. На языках программирования высокого уровня такой оператор входит в состав языка (оператор do..while в языке программирования C или оператор repeat..until в языке программирования PASCAL).

Алгоритмическое изображение оператора

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

Язык программирования asm-51

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

Алгоритмическое изображение оператора

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

Язык программирования asm-51

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

1. М. Рафикумазан Микропроцессоры и машинное проектирование микропроцессорных систем, пер. с англ. — М.: Мир, 1988
2. Н. Вирт Систематическое программирование. Введение. М.: Мир, 1977
3. Н. Вирт Алгоритмы и структуры данных. Новая версия для Оберона + CD. М.: ДМК Пресс, 2010
4. М. Бен-Ари Языки программирования. Практический сравнительный анализ: М.: Мир, 2000
5. Уоллес Вонг Основы программирования для «чайников» М.: Диалектика, 2007
6. Микушин А.В. Занимательно о микроконтроллерах. СПб, БХВ-Петербург, 2006.
7. Микушин А.В., Сажнев А.М., Сединин В.И. Цифровые устройства и микропроцессоры. СПб, БХВ-Петербург, 2010.

Вместе со статьей «Структурное программирование» читают: