Материал из ESyr's Wiki pages.

Предыдущая лекция | Следующая лекция

Содержание 1 Часть 1. Основные понятия традиционных процедурных ЯП 1.1 Глава 3. Операторный базис ЯП 1.1.1 Пункт 1. Структурное программирование 1.1.2 Пункт 2. Ветвление

Часть 1. Основные понятия традиционных процедурных ЯП

Глава 3. Операторный базис ЯП

В терминологии полный бардак. Нет согласия, как переводить computer science. Начиная с 60х годов, то, что слово statement, в описании языка А60, стало эталоном языкового описания. Assignment statement – оператор присваивания. В русском языке появилась традиция переводить слово "statement" как "оператор". Иногда ещё употребляется темин инструкция. Мы будем употреблять термин "оператор". Проблема в чём: проблем нет: есть оператор, есть операция (сложение, вычитание). Проблема была порождена Си++, где под оператором понимали то, что мы понимаем под словом операция. Есть переопределение операций.

В терминологии главное договориться. Мы будем следовать традициям А60 и под оператором будем понимать statement, операция – это операция.

Поэтому, операторный базис ЯП – то, какие операторы есть в ЯП.

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

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

Кто-то отмечал, что strcutured programming переводится как структурированное программирование.

История начинатся в 61 году, когда ныне покойный Дейкстра опубликовал статью о вреде языка goto. Идея (бредовая0: необходимо ограничитиь программиста в управлении, то есть, ограничеть возможности по управлению выполннием программы. Бредовость: до этого цель разработчика ЯП дать как можно больше возможностей программисту.

Ограничение возможностей программиста влияет благотворно.

В Java, Си шарп, нет goto. Но в Java он зарезервировано, чтобы изгнать это слово из четырёх букв.

Разбиение операций на приватные и публичние тоже ограничение возможностей программиста.

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

Структурное программирование вредно представлять как программирование без goto. Это программирование в терминах уровней абстракций.

Есть три блока:

1. Подготовить
2. Выполнить
3. Завершить

Потом понижаем уровень абстракции до конкретных языках ЯП, и операторы – чёрные ящики.

Идея оказалась благотворной.

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

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

Любимый пример лектора из опыта военной подготовки: Читали там на А60. Была программа, которую написал майор. Программа генерации перестановок. Сама по себе задача выеденного яйца не стоит. Проблема в том, что рекурсия не употреблялась, но там где-то на 9 строчек было 7 операций goto. Ив течении половинылекции пытался \объяснить, как она работает, и в итоге сказал «даю вам слово, это программа работает. Я её полночи проверял».

Программы с интенсивным использованием goto стали называтьм ​DS-программы (d... spagetti).

Самый главный оператор – оператор присваивания. Самое интересное с операторе присваивания – согласование типов, а это уже ТД. Основные операторы классифицируются на несколько видов:

1. Оператор присваивания
2. Управляющий оператором
3. Специальные операторы

В современных языках оитсустствуют такие вещт, как операторы ввода-вывода.

Существенно оказало влияние то, какие операторы управления.

1. Операторы ветвления. Делятся на
   1. Ветвления
   2. Дичкретные
   3. Многовариантные
2. Циклы
   1. С предусловием
   2. С постусловием
   3. С фиксированны числом повторений
   4. С управлением пользователем
3. Переходы
4. Блок

Переходов очень много вариантов.

А можно обойтись без гото?

Была опудликована статья: любую управляющую структуру можно свести к трём структурам – цикл и последовательность (условие – цикл с не более одной операцией0

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

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

Пункт 2. Ветвление

Самое простое: на две стороны

if B then S1 else S2

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

Проблема, которую заметил Донаьлд Кнут:

if B1 then if B2 then S1 else S2

Вопрос, когда выполняется S2, к какому if прижимается else. Более того, в первой реализации А60 эту проблему просмотрели, а Кнут её первый заметил.

В языках без терминаторов нужно использовать составные операторы (begin...end, {...})

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

If B then S1 else S2 end if;

Бейсик тоже удовлетворяет.

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

В ЯП с явным терм синт анализ проводить проще, и ошибки искать проще

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

Многовариантное ветвление:

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

select
when B1 => S1
when B2=> S2
...
when Bn => Sn
else Sn+1;
end select;

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

if (B1) 
	S1
else if (B2)
	S2
else if (B3)
	S3
else Sn+1

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

В М-2: ELSIF, чтобы подчеркнуть, что это не ELSE IF:

(Ada)
if B then
seg1
elseif (b2)
seg2
...
else
segn
end if;

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

Дискретный оператор ветвления:

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

Case E of
0: seg1; в М-2 и Обероне используется |
1..3: seg2|
4, 6..9 : seg3|
else
segN
end

(Ada)
Case E of
when V1 => seg1 знаков-терминаторов не нужно, ибо им будет либо следующий вен, либо енд
when V2 => seg2 
...
when others => segN
end case

Этот синтаксис похож на синтакси записей с вариантами.

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

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

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

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

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

На экзамене за синтаксические ошибки лектор ругать не будет

(C)
switch (e) S

Обычно S – составной оператор. В котором есть метки специального вида?

Switch(e)
{
	case val: 
...
	default:
...
}

if e=val then goto val;

В этом уродство. Если не нашли и есть дефолт, то гото дефолт.

Проблема в том, что только один гото.

Основная ошибка, которую делает даже лектор, и не потому что он крутой, а потому что он 15 лет программирует на Си с перерывами на Дельфи и другие языки: забывание break. В некоторых случаях отсутствие break бывает необходимо, но лектор использовал её всего несколько раз, и то неправильно.

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

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

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

Циклы

while B do S
repeat S1; ... Sn; until B;
C:
while (B) S
do S while (B)

Мэтры согласислись, что этого достаточно, но не тут-то было.

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

Алгоритм: Подготовить ввод Если конец файла, то выйти иначе обработать и в начало.

Тут выход из середины цикла. Это можно смоделировать циклами до, но это корёжит структуру. Тут лучше использовать goto.

Лектор будучи студентом писал метакомпилятор на Ф66 (там отсутствовал логический оператор, отсутствовали циклы, но было 4 оператора перехода), который отвечсал структурному программированию, но был на гото.

Циклы, управляемые пользователем.

Рассмотрим на примере языков Вирта, как минимальных

Есть

WHILE B DO
S1
END

А есть

LOOP
S1 ... SN
END

В Модуле-2 квазипараллельное программирование: бесконечные циклы не ошибка, они иногда необходимы, например, для фоновых процессов. только в LOOP может использоваться EXIT. EXIT то же самое, что и бряк в Си, только у него более широкое поле деятельности. Наиболее универсальная концепция цикла в языке Ада:

loop
S1 ... Sn
end loop;

есть специальная конструкция:

[when B => ] EXIT;

аналог

if B then
	exit;
end if;

На этот луп модет навёртывается while B do который или перед loop, или end loop

Ещё Бейсик.

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

Языки делятся на два класса:

1. Си-подобные языки
2. Остальные – в курсе основаны или близки на Паскале

Бейсик:

(C)
for(e1; e2; e3) S

(Pascal)
for i:=e1 to e2 do S;

(Modula-2)
FOR I:=E1 TO E2 STEP E3 do ... END;

Оберон-2:

Вирт с пафосом в design notes: Так же сочтён излишним оператор for.

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

(Ada)
for i in range do
loop
end loop;

Переменная i локализуется внутри цикла.

(C++)
for(int i=0; )

Страуструп сказал, что некоторые вещи он сделал бы по-другому.

Дальше всех пошли создатели VB и C#:

foreach (T x in C) S

Для массивов не особо нужен, но тем не менее, лучше ибо for(int i=0; i<a.length; i++) {... a[i] ...} там индексация медленнее, ибо проверки, а для foreach проверки не нужны. На самом деле, в современных ЯП появляются понятия рефлексии – в проргамме могут использоваться свойства программы. В Си шарп – коллекция – то, что поддерживает интефейсом Enumerable, и если написать свой класс, то он тоже будет коллекцией и поддерживаться foreach.Этого в Си++ и более старых языках не было. Другой пример рефлексии – атрибуты в Си шарп.

Осталось поговорить про переходы: есть операторы, которые являются частными случаями переходов, бряк и континью, ретёрн. Это не противоречит основным концепциям структруного программирования.