Структуризация алгоритмических моделей

Лекция № 6

Структуризация моделей программ (продолжение)

- это структурное программирование в узком смысле, как оно зародилось в конце 60-х, иначе называемое программированием без go to (начало - статья Дейкстры 1965 г. "GO TO considered to be harmful": частые ошибки кодирования - неправильная передача управления - вызваны скачками по тексту). Разрешены только три вида элементарных управляющих структур над функциональными блоками SN:

· Последовательность (составной оператор): S1; S2;

· Выбор (разветвление): if P then S1 else S2;

· Повторение (цикл): while P do S1;

Каждая из этих стандартных структур имеет, как и ФБ, один вход - один выход (два входа потребовали бы go to!), следовательно возможны эквивалентные преобразования для иерархической структуризации:

- ФБ à станд. структура (детализация)

- станд. структура à ФБ (обобщение)

Теоретическое обоснование возможности записи любого алгоритма с помощью только указанных трех ЭС - теорема Бома-Якопини (1966).

Запрет на go to часто приводит к потере эффективности. Например, следующее пре-образование неструктурной блок-схемы в структурную путем дублирования блока В:

Рис. 6-1

Дублирование кода В неэффективно по памяти, оформление В какподпрограммы - неэффективно по времени. Лишние проверки условий - в следующем примере преобразования рис.6-2.

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

Вопрос 1.

Языки программирования делятся на структурные – содержащие конструкции трех стандартных структур управления, и неструктурные. К первым относятся все современные языки (в них список стандартных структур расширен добавлением операторов case, for и repeat); некоторые из них вообще не содержат go to (Modula-2, BLISS, CLU). Ко вторым ассемблеры и первоначальный Фортран, Бейсик. Вопрос 2.

Рис. 6-2

Чтобы избежать неэффективности, современные языки содержат “структурные” операторы перехода: не на метку, а в точку входа в объемлющий блок (break) или точку вызова подпрограммы (return), позволяя описывать преждевременный выход из цикла или подпрограммы. Подобным же образом оператор возбуждения исключения (механизм exception в Аде, CLU или С++) описывает переход не на метку, а по имени исключительной ситуации – на код ее обработки. В целом современный подход не рекомендует, но и не запрещает go to.