Языки программирования, 12 лекция (от 12 октября)

Материал из eSyr's wiki.

Версия от 12:02, 14 января 2013; 79.165.47.85 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Содержание

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

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

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

Операторный базис ЯП — то, какие операторы есть в ЯП.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Самый главный оператор — оператор присваивания. Самое интересное с операторе присваивания — согласование типов, а это уже ТД.

Основные операторы классифицируются на несколько видов:

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

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

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

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

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

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

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

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

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

[править] Пункт 2. Ветвление

[править] Двухвариантное ветвление

(Algol)
(Pascal)
if B then 
  S1 
else 
  S2

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

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

if B1 then if B2 then S1 else S2

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

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

В языках с явными терминаторами явно обозначается конец. Примеры — Ada, Modula-2, Oberon. В этих языках отсутствует понятие составного языка как такового.

if B then S1 else S2 end if;


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

[править] Многовариантное ветвление

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

(Ada)
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. Простое синтаксическое решение ведёт к появлению специального оператора.

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

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

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

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

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

(Pascal)
case E of
  0: seg1; { в Modula-2 и Oberon вместо «;» d этом случае используется «|» }
  1..3: seg2;
  4, 6..9 : seg3;
else
  segN;
end;
(Ada)
сase E of
  when V1 => seg1 — знаков-терминаторов не нужно, ибо им будет либо следующий when, либо end
  when V2 => seg2 
...
  when others => segN
end case

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

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

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

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

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


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

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

Синтаксис:

(C)
switch (e) S

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

Switch(e)
{
  case val: 
    ...
  default:
    ...
}
if e = val then goto val;

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

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

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

Языки, которые основаны на C: В Java goto нет, но идиотизм с break остался. В C# брейк писать надо, но не писать его нельзя, дабы обеспечить мобильность навыков, знаний. В Java break может содержать метку, а метка может помечать начало цикла, и это позволяет делать break более чем на один уровень.

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

[править] Циклы

(Pascal)
while B do 
  S;

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

do 
  S 
while (B)

Мэтры согласислись, что этого достаточно, но не тут-то было. Кнут в статье «структрное программирование с goto» отметил, что структура программы должна отвечать структуре алгоритма, а он структурен, но алгоритм не всегда укладывается в while и do while.

Алгоритм:

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

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

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

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

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

Есть

WHILE B DO
  S1
END

А есть

LOOP
  S1 ... SN
END

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

Наиболее универсальная концепция цикла в языке Ада:

(Ada)
loop
  S1 ... Sn
end loop;

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

(Ada)
[when B => ] EXIT;

аналог

(Ada)
if B then
  exit;
end if;

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

Ещё BASIC.

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

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

  1. C-подобные языки
  2. Остальные — те языки, которые представлены в курсе, основаны или близки к Pascal

BASIC:

(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;

Oberon-2:

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

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

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

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

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

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

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

foreach (T x in C) S

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

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


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


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28


Календарь

чт вт чт вт чт вт чт вт чт вт
Сентябрь
  05 07 12 14 19 21 26 28
Октябрь
  03 05 10 12 17 19 24 26 31
Ноябрь
02 14 16 21 23 28 30
Декабрь
05 07 12 14

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


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы