Обзор и сравнительный анализ языков программирования [Антон Евгеньевич Москаль kouzdra] (pdf) читать онлайн

Антон Е.Москаль,
Олег А.Плисс,
Андрей А.Терехов,
Андрей Н.Терехов,
Владимир В.Уфнаровский

Конспект лекций
"Обзор и сравнительный анализ
языков программирования"

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

Оглавление
ВВЕДЕНИЕ ......................................................................................................................................................................3
ТРАНСЛЯЦИЯ ПРОГРАММ ....................................................................................................................................10
ИСТОРИЧЕСКИЙ ОБЗОР .........................................................................................................................................20
АССЕМБЛЕР.................................................................................................................................................................23
BASIC ..............................................................................................................................................................................27
PASCAL/MODULA 2 ....................................................................................................................................................29
C/C++...............................................................................................................................................................................34
PROLOG .........................................................................................................................................................................37
OCCAM...........................................................................................................................................................................40
ФУНКЦИОНАЛЬНЫЕ ЯЗЫКИ ПРОГРАММИРОВАНИЯ................................................................................47
SMALLTALK.................................................................................................................................................................54
ЗАКЛЮЧИТЕЛЬНАЯ ЛЕКЦИЯ...............................................................................................................................58
УКАЗАТЕЛЬ ЛИТЕРАТУРЫ ....................................................................................................................................60

Введение
Общая задача курса – дать понятие о современных языках программирования,
научить выбирать правильный язык программирования, обучить созданию ЯП и т.п.
Общая схема рассмотрения языка:
1. Название, кем, когда и зачем был создан
2. Общая характеристика:
– декларативный или императивный;
– язык-оболочка или язык-ядро;
– хороший или плохой (красивый? схожесть операторов, т.е. если что-то
изменить, то насколько велика вероятность неявной ошибки? Эффективность
– по скорости исполнения; по скорости компиляция; по времени отладки, т.е.
перекомпиляции; отзывчивость (responsiveness), например, можно даже
продолжать исполнение программы).
3. Синтаксис
4. Данные (типы, представление)
5. Управление последовательностью действий
6. Управление данными (передача параметров, подготовка к исполнению операций)
7. Управление памятью
8. Модульность (по-хорошему надо бы записать после 3)
9. Среда ЯП, работа с файлами, устройствами
Как описывается синтаксис ЯП?
–
–

неформально
в форме Бэкуса-Неймана (БНФ):
метасимволы в угловых скобочках
::= есть «обозначает»
| есть «один из вариантов»

Пример БНФ:
::=
::= | –
::=
::= 0|1|2|3|4|5|6|7|8|9
Расширенная БНФ (для записи регулярных выражений)
вводятся дополнительные символы *, +, { }, [ ]
Пример РБНФ:
::= { пробел | –}{0|1|2|3|4|5|6|7|8|9}+
или [–] {0|1|2|3|4|5|6|7|8|9}+

Как описывается семантика ЯП?
В терминах абстрактного вычислителя; считается, что программа транслируется в
терминах вычислителя (виртуальной машины). Кроме того, бывает последовательность
виртуальных машин.
Интерпретация
Программно-аппаратная реализация – в микропрограммах. Что
такое
микропрограмма? Современные процедуры сделаны либо совсем аппаратно, либо с
помощью микропрограмм, с помощью которых можно добраться до процессора напрямую.
Архитектура ЭВМ
Раньше делались процессоры, ориентированные на язык (ФОРТРАН-машины). Дело в
том, что выгоднее потратить транзисторы на очень простые операции, но сделать их очень
быстрыми.

Память состоит из бестиповых ячеек, у которых есть только целый адрес, туда можно
записать что угодно.
У процессора есть instruction pointer (он же program counter). Есть декодер и АЛУ.
Работает все это так: декодер вынимает следующую команду, управление данными
вынимает операнды, АЛУ все это исполняет, IP инкрементируется.
В современных ЭВМ все это сопровождается наворотами (несколько параллельно
исполняемых команд, выборка вперед и т.п.). Бывает иерархия памяти (например, кэш –
промежуточный уровень между быстрой и медленной памятью).
Когда пишешь что-то в порты I/O сразу записывается что-то на внешнее устройство.
Интересно, что input и output регистры не совпадают.
Это не очень удобно. Прерывания – различные уровни (256 уровней). Прервал
программу – передай управление на обработчик.
Память – данные по 8, 16, 32 бита (выравнивание). Бывают binary/decimal,
packed/unpacked, floating.
Операции над данными – арифметические, сравнения (результат – в регистре
состояния), проверка битов состояния (⇒ ветвление), переходы бывают безусловными и
условными, ввод/вывод в порты прерывания; иногда управление иерархией памяти; бывают
аппаратно поддерживаемые стеки. В таких случаях можно поддерживать подпрограммы
(адрес кладется на стек, по окончании снимается). Это поддержка не везде и если не
поддержано, то надо делать руками.

Многопроцессорные системы – несколько декодеров + память общая. Основания
проблема – управление памятью, особенно кэшем.
Данные в ЯП:
– встроенные типы данных (есть такие-то и других не может быть)
– конструируемые типы (т.е. существует конечный набор элементарных типов, есть
набор конструкторов типов), например:
элементарные (первичные) = (целые, плавающие, вещественные, литеры)
конструкторы = (записи, массивы, объединения)
– абстрактные типы данных (тип можно не только сконструировать, но и сделать
неотличимым от первичного)
Теперь подробнее о типах.
Элементарные типы:
целые числа (двоичные и десятичные представления)
числа с плавающей точкой (знак, мантисса, порядок)
логические значения (true/false либо логические шкалы)
литеры (литеры внешнего вида, т.е. 7 или 8 бит)
Целые числа отличаются от реальных тем, что они обрезаны слева и справа.
Вещественные числа отличаются ограниченным диапазоном и ограниченной точностью, т.е.
a+b–b может быть ≠ a (например, из-за переполнения).
Операции: +, –, *, /, mod, abs, , ==, !=, преобразование целых к
вещественным; у вещественных – log, sin/cos, возведение в степень.
Логические: &(and), | (or), !(not), ^(xor)
Если логические значения представлены шкалами, то над каждым битом операции
проводятся побитно. Кроме того, бывают сдвиги влево/вправо (простые/циклические).
В большинстве современных ЯП нет прямой адресации битов (⇒ нет типа bit).
Иногда бывают комплексные числа (пара плавающих чисел).
Набор элементарных типов в разных языках ЯП отличаются: могут быть быть строки
фиксированной или переменной длины, ограниченной длины.
Строки обычно представляются просто как последовательность байт. У строк
фиксированной длины должен быть еще счетчик, либо конец строки должен явно
обозначаться. Счетчик может быть в самой строке, либо хранится в дескрипторе.
Выборка литеры из строки, конкатенация строк, выборка подстроки и т.п. операции
над строками реализуются по-разному (например, копирование куска в фикс. или заведение
другого дескриптора при выборке строки).
Обычно все это транслируется программными средствами (то есть обычно нет
аппаратной поддержки для выборки подстроки).

Конструкторы типов данных:
Массивы:
– одномерные и многомерные
– однородные и неоднородные
– фиксированной и изменяемой длины (обычно целым числом, иначе это
называется коллекциями)
– плотные и неплотные
1. Одномерные массивы (однородные плотные фиксированного размера):
– нижняя граница
– верхняя границы
Конструктор: тип элемента массива
В памяти все это представляется просто:
Операции: создать, узнать upb/lwb, вырезка и запись по номеру в массив.
2. Многомерные массивы
Можно смоделировать с помощью одномерного массива:

n = 1 : base, itemsize, low, i ⇒ addr (i ) = base + itemsize ∗ (i − low)
n > 1 : addr (i1 , i 2 ) = base + size ∗ (i1 − low1 ) + size ∗ (i 2 − low2 ) = c + size1 ∗ i1 + size2 ∗ i2
Формальная корректность – гарантия того, сто программа написанная человеком
может быть понята машиной.
Отсутствие разночтений – не должно быть возможности истолковать программу поразному.
Пример 1 (Pascal):
if
then
if
then …
else

else на самом деле принадлежит второму
условному предложению. Если бы в Паскале
существовал endif, то этой проблемы не было бы.

Пример 2 (Fortran, PL/I):

A(i) – может быть вырезкой из массива или вызовом функции. Если массив забыли
описать, то ошибка обнаружиться только при сборке.
Если вырезка обозначается A[i], то проблема не возникает.
Удобство чтения и удобство записи – противоречащие требования.

Простота трансляции – зависит от регулярности языка (хороший язык – Pascal).
Синтаксис
Синтаксические элементы:

1. входной алфавит
2. формат исходного текста
3. идентификаторы
4. пробелы
5. знаки операций
6. ключевые слова (зарезервированные)
7. комментарии и шумовые слова
8. ограничительные скобки
9. выражения
10. операторы
11. программные единицы
12. литералы
Входной алфавит – набор литер, с помощью которых можно писать программы
(например, ASCII – тогда возникают проблемы с национальными символами).
Формат исходного текста:
– свободный – корректный не зависящий от позиции слов программы
– фиксированный (точнее с фиксированными полями) – в разных полях можно писать
разные элементы программы
– с частично зафиксированными полями (часть строки зарезервирована – в Фортране
первые 5 символов для метки)
– с выделенными позициями ('*' в седьмой колонке в Коболе, '\' в С/С++ в последней
колонке - перфокарты)

VLIW-ассемблер – разным полям соответствуют разные устройства, поэтому
программа может выглядеть так:
Метка

OR x1, x2

SHL …

Метка перехода

Комментарий

Идентификаторы – обычно последовательности вида:

::= {|}*
Иногда у множеству букв или символов добавляют специальные символы, например
'_'. Из множества возможных идентификаторов исключаются ключевые слова. Длина
идентификаторов иногда ограничивается (⇒ 2 реакции на слишком длинный
идентификатор: ошибка либо отсечение хвоста). Возможно различение больших и маленьких
букв (abc≠ABC в C, но = в Pascal-e).

Пробелы (под этим подразумевается white space, т.е. еще табуляции, переводы строк
и т.п.) Иногда пробелы игнорируются (например, в Фортране или в Алголе 68: MyVar≡My
Var, 123≡1 2 3).
Знаки операций – обычно специальные символы. Иногда их объединяют в более
длинные операции (+=). В некоторых языках – специальные слова (Plus), в Фортране –
сравнение записывается как .EQ.
::= * {h|H} – в
начале цифра, иначе идентификатор!
Литералы – изображения числе, строк и т.п.
Например ::= {* | 0 }
::=[-|+]
0 выделен, так как во многих языках с 0 начинаются восьмеричные числа: 0123≠123!
Ключевые слова – имеют особый смысл для образования конструкций, могут быть
зарезервированными (т.е. их нельзя использовать как идентификаторы), это сильно
облегчает трансляцию.
Комментарии и шумовые слова – комментарии бывают от скобки до скобки и до
конца строки. Шумовые слова – для повышения читабельности ( GO [TO] )
Ограничители и скобки – " есть ограничитель, (–), begin-end – это скобки.
Литералы (константы):

[.] [{e|E}]
Литеры: могут быть в апострофах 'abc', либо в кавычках. Если нужен апостроф, то
либо дублируют "", либо вводят специальный символ '\''; иногда бывает специальный символ
спереди: $a.
Строки: как литеры, только символов может быть несколько.
Булевские значения: могут быть идентификаторы true/false (зарезервированные/не
зарезервированные), могут быть специальные символы (.T. или .R.)
Выражения – составные конструкции языка. Состоят из литералов,
идентификаторов, знаков операций и разделителей (скобок).
Выражения могут быть в следующих формах:
1. Префиксная (польская запись) – знак операции, затем операнд.
2. Постфиксная (обратная польская) – в начале операнды, затем знак операции.
3. Инфиксная – знак между операндами.
4. Смешанная.
Пример 1. (PLUS (MINUS A B) C) ~ (A–B)+C
либо PLUS (MINUS A B) C – то же самое
Скобки можно вообще убрать, если задана арность операции:
PLUS MINUS A B C
Пример 2. То же самое, но наоборот
(( A B MINUS) C PLUS)
A B MINUS C PLUS
Пример 3. Для бинарных операций:
A+B.
1) Приоритет – разным операциям приписывается приоритет ∈ [0, MAX_PRIO].
Если нет приоритетов, то A+B*C=(A+B)*C
Если они есть, то первым выполняется более приоритетный оператор.
2) Присоединение.

Если присоединение слева направо, то A+B+C=(A+B)+C, если присоединение
справа налево, то A+B+C=A+(B+C)
Ясно, что приоритеты и присоединения нужны для уменьшения числа скобок в
выражениях.
Пример 4. Используется практически во всех языках программирования (для разных
операций – разная форма записи)
f(x) – префиксная
a+-sin(x)

Операторы – основные конструкции языка, из которых состоят программные
единицы
Программные единицы:
– функции
– процедуры
– подпрограммы
– модули
– файлы

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

int main(void) {
printf( %d”,1);
return 0;
}


< ( – разделитель>


лексическая свертка программ
…

синтаксический анализатор (парсер)
дерево разбора + может быть таблицы

ф-ция(“main”,0,(void), int)
вызов ф-ции (printf …)
оператор(“return”,0)

семантический анализ
трансформир.??? преобразования
кодогенерация
Объектный код можно линковать, загружать и исполнять при исполнении
относительные адреса заменяются на абсолютные.
Программы про трансляции:
– препроцессор; ⇒ время препроцессора
– транслятор; ⇒ время трансляции
– линковщик; ⇒ время загрузки
– загрузчик.
⇒ время исполнения
(Массив фиксированный ⇒ фиксированный в какое-то время из этих четырех)
Компилятор – берет исходный текст, производит объектный модуль.
Интерпретатор – берет исходный текст и сразу его исполняет.
Есть промежуточный вариант – остановиться на некотором Промежуточном Языке
(ПЯ) (виртуальная машина) и интерпретировать ее.

Пример
# include
int a [MAX_SIZE];
int b [sizeof(a)];
int c [b[0]];

//a – фиксированный массив времени препроцессора
//b – фиксированный массив времени трансляции
//c – фиксированный массив времени исполнения

Система типов – та информация в рамках языка, которая относится к значениям
переменных во время исполнения.
Языки:
– бестиповые (Smalltalk, Forth, Basic)
– со статической типизацией
– с динамической типизацией
– со смешанным типовым контролем (часть во время компиляции, часть во время
исполнения)
n

addr (i0 ,K , i n ) = base + ∑ c k i k
k =0

Полный дескриптор массива:
type – тип элемента массива
dim – количество индексов
base – базовый указатель массива
lwbound
upbound dim штук граничных индексов
width
– для удобства, ширина массива
Что известно во время трансляции?
Обычно тип и количество индексов можно убить, т.к. известно во время трансляции
Про неплотные массивы рассказано не будет, так как они почти нигде не встречаются
в виде базовой конструкции
Неоднородные одномерные массивы (структуры/записи)
struct S {
int a;
float b;
char c;
};

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

Неоднородные многомерные массивы

Структуры с вложенными структурами. Дальше – все точно так же.
Объединения размеченные
union S {
int a;
float b;
char c;
}

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

Исполняемые единицы (процедуры/программы)

В простейшем случае – процедура есть кусок кода, а представляется она адресом ее
кода (Фортран, C).
Если есть блочные среды ⇒ представляется парой (адрес процедуры, адрес блочной
среды)

Управление последовательностью действий

I. Неявное управление последовательностью действий.
1) последовательное выполнение (в порядке записи)
2) совместное исполнение ( компилятор может определить удобный ему порядок
исполнения, например:
x= 5;
y= x*x++;

может получится либо 25, либо 30, в зависимости от компилятора)
3) параллельное исполнение (по возможности исполняется параллельно)
II. Явное управление последовательностью действий
1) условное выражение:
if условие then ... [else ...] fi

2) циклические предложения
a) forever
тело цикла
repeat

Выйти, конечно, можно – возвратом
процедуры программы, break-ом, переходом
на метку.

б) цикл с предусловием:
while (условие)
тело цикла

end
в) цикл с постусловием:
begin
тело цикла
repeat until (условие)

г) цикл со счетчиком:
for int i from … to … [by …]

д) цикл со списком:
for i in (1,2,5,10)

Был язык в котором все эти циклы присутствовали одновременно в одной
универсальной циклической конструкции (Алгол 60):
3) выбор по метке:
case (
Вычисляется выражение, которое
of …;
затем сравнивается с константными
default
выражениями.
end-case

Есть вариации в которых на месте константного выражения могло
стоять любое булевское выражение
4) оператор безусловного перехода на метку:
goto … ;

«Трудно выйти в C из нескольких вложенных циклов». Не оператор
плохой, а плохи люди, которые не умеют его использовать.
a) goto
…
:
б) goto выражение (A,B,L,M)
…
A:
B:
…
M:

в) goto x; // где x – некоторое выражение
Например,
read (x);
goto x

Если строки занумерованы. Трудно сделать что-нибудь приличное, так
как любой строке потенциально соответствует метка.
5) вызов процедуры:
call (параметр 1, … ,параметр n)

Такая запись называется позиционным следованием: где-то есть
описание процедуры:
proc f (int a, float b=1, char c) // формальные параметры
f(1,2,’?’)
// фактические параметры
f(1,,'?')
// один из параметров по умолчанию

Если параметры по умолчанию допускаются только в конце, то от таких
странных запятых можно избавиться.
Передача параметров с ключевыми словами
f(a=1, b=2, c='?');

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

f: ZxRxChar
Но процедуры определены лишь частично на своих областях определения (нет
деления на 0)
3. Процедуры могут использовать неявные параметры (глобальные переменные).
4. Неявные результаты
5. Процедура может не возвращаться в точку вызова (исключительные ситуации,
переходы)
6. Значение процедуры может быть недетерминированным.
Замечание Терехова про время в процедурализме и логицизме.
Какие бывают процедуры?

1. Простые: a→b→c→b→a
2. Рекурсивные: a→a
[ прямая и косвенная – в том числе может быть через параметры: f (proc g) ]
Вернулись к простым:
в Фортране только это и есть: никакого стека не нужно. Однако при таком
подходе никакой рекурсии не получится.
Если есть рекурсивные вызовы, то нужен стек, так как надо уметь
идентифицировать различные экземпляры процедур.
3. Сопрограммы
сall переходит без возврата, но с
запоминанием адреса.

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

В C это можно сделать
с помощью longjmp.

4. Процесс – после вызова может выполняться в прикрепленном состоянии или
отсоединиться.
fork A (…)
detach

5. Исключения или прерывания

Можно сделать процедуру, которая будет выполняться после выполнения
какого-либо условия (заранее заданного или собственного):
ON OVERFLOW f

Если самостоятельно определено условие, то его надо и самостоятельно
анализировать:
on g
…
signal

6. Планируемые процедуры – вместо какого-то события (как в прерываниях)
ставится просто булевское условие. Это может быть связано со временем между
запусками и т.п. (Симула 67)
Управление данными (управление средами)

Связывание (binding); обычно идентификаторы связывают со значениями:
– времени препроцессирования #define A 10
– времени компиляции const int b=2;
– времени линковки
–

const int a=b+10;
extern int b=2; // надо разрешить все внешние ссылки
// во время линковки

времени исполнения
а) время вызова процедуры (формальные/фактические параметры) A(1,2)
б) время входа в блок {
int a=1;
}

в) время исполнения данного оператора
p→f();

Если f – виртуальная функция, то до самого последнего момента
неясно, что мы вызовем.
Ассоциация идентификатора со значением:
1. Создать
2. Уничтожить
3. Временно деактивировать
4. Активировать заново
5. Поменять

Промежуток между созданием и уничтожением – время жизни. Области, где
идентификатор активирован – области видимости.
void f (void) {
static int a=0;
}

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

Отличаются ли статические вложенные среды от динамически вложенных? Да. В
статических видимость определяется последовательностью описаний в тексте, а в
динамической – последовательностью вызова.
proc f
int a;
proc g;
int b;
proc h;
int a;

f
f

g

f h g
a a b

–

–
– –

– если статическая вложенность (посл-ть описаний)
– если динамическая вложенность (посл-ть вызовов)

Три процедуры A,B,C:

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

Модульные среды – нелокальные статические.

Локальные динамические среды.

Процедура: адрес возврата
секция активации
Устройство секции активации:
Существует два способа записи стековой рамки: один или два указателя
а) если один указатель ⇒ не можем динамически выделять
память во время исполнения процедур.
FP – рамка стека
Необходимо разместить локальные данные в стек, который у
подпрограммы уже есть.

б) два указателя: на рамку активной процедуры и на
вершину стека.
push FP
// Адресуем локальные данные относительно FP
mov FP,SP // c отрицательным смещением
sub SP,NB // (не относительно рамки стека).

Обратно аналогично:

mov SP,FP
pop FP

Нелокальные среды статической вложенности:
Proc A {
int x;
proc B {
real y;
x++; // x из A
}
proc C {
char x;
B();
} B(); C();

};

при статической
вложенности

при динамической
вложенности (по
динамической цепочке)

Реализация:
1) Статическая цепочка: указатель на секцию активации, статическая объемлющая
процедура. Знаем уровень вложения статически.
Для
адресации:
количество
шагов
по
статической
цепочке
(уровень)+смещение в секции активации

Проблема в том, что необходимо все время ходить по статической цепочке.
Можно звенья записывать и вместо хождения по цепочке смотрим в регистры.
2) Динамические вложенные среды: адресация переменной:
а) самое простое – просмотр динамической цепочки
б) hash-таблица
Передача параметров

1) по значению – при входе копируем в локальную переменную (теряем при выходе)
2) по результату – при выходе из процедуры копируем локальную переменную (на
входе – ничего)
3) по значению-результату – при входе копируем в локальную переменную, при
выходе – обратно
4) по ссылке
5) по имени – если в качестве параметра передаем выражение
Пример
int y,x;
proc f(int x) {
x+=1; y+=1;
print(x,y);
x–=1; y–=1;
}
y=0; x=1;
f(y);
print(y);

1) по значению

x
1

2) по результату

x
2???

3) по значению-результату

x
1

4) по ссылке

x
2

5) по имени – то же самое

y
1
0
y

0
y
1
0
y
2
0

1

Параметры могут передаваться на стеке или на регистрах.
a) на стеке

–
–
–
–

б) на регистрах:
Группы регистров:
для архивации вызова и передачи параметров
регистры, которые хранят процедуры (сохраняют вызывающую процедуру)
сохраняются вызванной процедурой
рабочие (ни те, ни другие не хранятся)
Управление памятью
1. Статическое (работа только во время компиляции и линковки)
2. Стек (статический или динамический)
3. Куча (управление ручное или автоматическое)
Зависит от запросов (бывают фиксированного и нефиксированного размера)
Фрагментация
Самолокаторы

Исторический обзор
ФОРТРАН был самым первым языком высокого уровня (1956 г.) и породил целый
класс интуитивно неясных ошибок:
x = 1/3 // выдает 0, а не 0.3333

Другая ошибка:

x = 9.3 // x – число двойной точности

Порождение было такое:

LE 0, = E “9.3” // младшие 32-бита не зачищались
STD 0, x

Как это можно было обойти? Либо написать 9.3000000 (⇒ длинное), либо 9.3D
(double).
Наконец, классическая ошибка (самая дорогая ошибка программирования).
DO 3 I=1.4 // (надо было не “.”, а “,”) Получилось присваивание.

Пример:
F(1)
I=1
WRITE ()I // печатается 0
SUBR F(a)
A=0

Кроме того, ФОРТРАН не переносим, так как у него не было формального описания.
Спорное утверждение про то, что ЯП лучше создавать группами. Рассказывает про
IFIP.
Working group 2.1 по языкам программирования
Working group 2.3 по методологии программирования
1958, 1960 гг. Алгол 60

а) формальная грамматика. БНФ;
Пример программы на Алголе 60:
begin
integer i,j;
real b,c
b:=c+1; #обругал С++ с его “==”
if then else # (fi – еще не было)
for i:=A step B until C do #обругал предвычисление В и C; двойное вычисление В
# из-за знака
procedure p(a,b);
value a; real a,b
begin
…
end

Подстановка по значению p(3+0.5, x) или
подстановка по наименованию (с изменением значения и
перевычислением). Например, p(3+0.5, x[i]) – круто, да?

б) переносимость программ;
в) динамические массивы;
г) рекурсивные процедуры
Про оптимизацию заведомо плохих алгоритмов – спорный момент.
Разделение на PL/I и Алгол 68.
Язык-оболочка; громоздкий
Пересмотренное сообщение Алгол60 – 1964 (от начала до содержательного языка
прошло 6 лет)
«Белая книга Алгола 60» – целая пачка статей, определивших развитие
программирования.
Обсудили регулярные выражения и их эквивалентность БНФ. Далее про конечные
автоматы (и они тоже эквивалентны).
Бесконтекстные и контекстные грамматики.
ret MODE assignment:
ret MODE variable, ‘:=‘,
MODE expression

То, что написано большими буквами – определяется в другой грамматике, более
высокого уровня. Единственное ограничение – что всюду надо подставлять одно и тоже (⇒
все виды в присваивании одинаковые).
Приведений в Алголе 68 всего 6 (ср. с PL/I, где их более 200)
1964 г. придумано структурное представление данных (Xoap, struct).
Декабрь 1968 г. Алгол 68

Реализовать A68 оказалось кошмарно сложным занятием, ибо язык был существенно
сложным.
mode цепь = struct (int зв, ret цепь след.)
mode цепь = struct (int зв, ret цепь след)

Эти два вида эквивалентны? В структурной эквивалентности – да, а в именной
эквивалентности – нет. (В Алголе 68 структурная эквивалентность).
union (m1, m2, m3)

Ограничения вводили сразу же – нельзя использовать int и ref int
case и in (m1): A1, (m2): A2, …

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

Вместо модели видов использовали конечный автомат и оказалось возможным
доказать эквивалентность видов за nlogn шагов. Кроме того, придумали еще и канонический
порядок ( в том числе и трансляции модулей).
Тем не менее, у этого алгоритма была очень большая константная составляющая и на
СМ1420 стандартное вступление транслировалось 1.5 минуты. В результате вернули старый
экспоненциальный алгоритм.
Короче, много тем для диссертаций дал A68 (А. Рухлин защитил диссертацию с тем
же названием, что и П. Сёки в 1976 г.).
Что же такое A68?
int, real, bool, char;
можно сказать ref m;
s struct (m1 a1, m2 a2) ⇒ a of s
(flex)? [l:u] m M;
(‘l:’ можно опускать, тогда от 1)

Триммерные вырезки (на примере умножения матриц)
for k to N do
s+:=a[i,k]*b[k,j]
od

Цикл выполняется n³ раз, при этом i,j не меняются. Поэтому можно написать так:
ref [] real ai = a[i,];
ref [] real bj = b[,j];
for k to N do
s+:=ai[k]*bj[k]
od

При этом копирования не происходит (заводится лишний паспорт).
proc (m) n ;
flex [3] int a;
a:=(); a:=(10,20,30,40);

… – меняются границы

a; b; c – последнее исполнение
(a; b; c) – совместное исполнение (порядок не определен)
par (a; b; c) – параллельное исполнение (с семафорами)

A68 оказался слишком тяжелым в реализации (с A68 тоже ушло 6 лет на доделку –
пересмотренное сообщение в 1974).
Мнение меньшинства (Minority Report).
Через несколько лет Вирт опубликовал Паскаль, но в нем было слишком много дырок
и неточностей. «Двухкопеечный язык».
Похожесть
языков
программирования:
«Золотой
фонд
системного
программирования». Эта часть системного программирования устоялась.

Ассемблер
Зачем нужен ассемблер?
1. Исторически – чтобы не считать смещения и адреса в машинном коде, что для
своего времени было большим продвижением.
2. Чтобы оптимизировать узкие места и использовать расширения команд, которые
транслятор напрямую сгенерировать не может (например, Pentium MMX и выше)

Развитие ассемблера продолжается, в направлениях NGWS (Next Generation Windows
System) и Typed Assembler (ассемблер с гарантированной надежностью типов).
Ассемблер имеет смысл рассказывать для конкретной архитектуры (в данной
лекции – для PDP-11).
Команды бывают с двумя операторами: mov src, dst или с одним (инвертирование
знака).
В ASM принципиально нет выражений ⇒ a:=b-c-1 расписывается как
mov b,a
sub c,a
dec a

; a:=b
; a-:=c
; a-:=1

В PDP-11 было 6 регистров общего назначения. R0-R5, кроме того SP, PC.
Работа с адресами:
0 Rx
1 (Rx)+
2 –(Rx)
3 x(Rx)
4 @Rx – содержимое регистра используется как адрес
5 @(Rx)+
6 @–(Rx) используются реже
7 @x(Rx)
Команды push нет, вместо этого пишут mov r0, –(sp), вместо pop пишут
mov (sp)+, r0

Программа копирования строчки, заканчивающейся нулем:
; r0 – src
; r1 – dst
L: mov b (r0)+, (r1)+
Bne L

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

i:=1;
repeat
a[i]:=b[i];
i:=i+1;
until a[i-1]=chr(0)

В частности, одной из причин популярности C может быть то, что в нем эти
конструкции схожи с ASM’ом: while (*a++=*b++);
Команды с двумя операндами:
mov
movb
add
sub
cmp
cmpb

По первому биту можно
определить, 4 бита используется
для кода операции или 10(а то и
16 – безоперандовые команды)

Коды условий – хранят результат последнего сравнения 0, >0, PC указывает сюда

Одна из проблем PDP-11 – в невозможности конвейеризации команд. Если же хочется
достучаться до элемента по адресу 10, то надо писать
mov @#10, r0

Были команды .byte n, .word n, .ascii “abc”(+’0’) и .asciz – автоматически
заполнит конечным нулем (все команды заносят операнд в память); например i: .word [1]
– можно сразу проинициализировать (все метки, используемые как операнды, означают
адрес в памяти : inc@#i)
Структуры управления – практически сводятся к goto.
position-independent code (PIC) – можно переместить в другое место без заморочек.
inc @#i – не перемещаемый код (позиционно-зависимый, если только не от PC, у
которого адрес абсолютен)
inc i – не реентерабельный, но позиционно-независимый

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

Зачем ASM? Например, для переписывания узких мест.
Макропроцессор в ASM тоже есть (а кроме него, есть только в PL/I и в C).
.macro name args
…
.endmacro (.endm)

; определяется псевдокоманда с именем name
; текстуальная замена

Пример:
.macro push arg
mov arg, –(sp)
.endm

⇒

~ mov r1, -(sp)

push r1

Пример: (сохранение регистров)
Push

.macro push args
.irp arg args
mov arg, -(sp)
.endr
.endm

(угловые скобки делают из набора
элементов один аргумент). Сами скобки
никуда не передаются

Есть значения по умолчанию (,sptr=sp).
В ASM есть раздельная трансляция (модульности, конечно, нет). Те переменные,
которые должны быть видны из других модулей, должны быть помечены как .globl f
(аналог extern).
...
f:

(аналог static, если нет globl)

Чему соответствует подпрограмма?
jsr rx, addr

;

-(sp) ← rx
rx ← pc
pc ← addr

jump to subroutive

Есть парная команда rts (return):
rts rx
pc ← rx
rx ← (sp)+

Вопрос: Что будет, если написать jsr pc, x ? В таких случаях, не заводятся
промежуточные регистры; все кладется на стек ( ~ call x)

Пример: strcpy(s1,s2). Параметры запихиваются на стек справа налево, запускается
функция, а затем вызывавшая процедура чистит стек:
mov #a, -(sp)
mov #b, -(sp)
call strcpy
add #4,sp

~ strcpy(b,a)
- можно было написать сmp (sp)+, (sp)+ (более компактный код)

strcpy:
mov 2(sp), r0; s1
mov 4(sp), r1; s2
L:
movb (r1)+,(r0)+
bne L
ret

Зачем нужны промежуточные регистры при вызове?
Пример: На Фортране была функция strcat(b,s1, …)
jsr r5, strcat
bne L
.word

При входе в strcat:
⇒

; r5 → число параметров
movb r5 , … ; сохранили куда-то

: s1
: s2
:
L:

Пример: memmov (число копируемых байт – константно)
mov #a, -(sp)
mov #b, -(sp)
jsr r5, cpy
(r5) → .word n
(r5)+→ …
cpy:
mov (r5)+, r0
…
rts r5

Т.о. за счет соглашения о связях
можно вот так сэкономить

Была условная компиляция: ife, ifne, ifeven
.if …
; .iff ≡ else (условие ложно)
; .ift – если выполнено условие
; .iftr – выполнялось безусловно
.endc

Это может быть удобно, если что-то надо делать в начале и в конце предложения

BASIC
BASIC – Beginners All-purpose Symbolic Instruction Code

Создан в 1961 г. для студентов гуманитарных вузов.
Что в нем есть?

часть.

Переменные: A … Z, A1… (после буквы можно поставить цифру).
Массивы: A(5), B(5,10)
A(α), где α-выражение – это вырезка. Если α∉Z, то отбрасывается дробная
BASIC – интерпретирующий язык ⇒ очень медленный

«Удобная среда для создания и редактирования программ». Заключалось в том, что
каждой строчке присваивается номер:
5 DIM A(10)
10 FOR I=1 TO 10
15 PRINT A(I)
20 NEXT I

Рекомендовали писать в каждой строчке несколько операторов, разделяя их
специальными символами : или \
На самом деле, это очень неудобно – никогда не знаешь, какой длины программа изза возможности различной нумерации.
Позже появилось: RENUM, RESEQ, которые перенумеровывают строки
(соответственно изменяя адреса переходов в операторах GOTO).
Команды BASIC:

1) PRINT – печать, возможно использование нескольких параметров
Если через ‘,’ то вывод через табуляцию
Если через ‘;’, то через пробел
Если просто так несколько параметров, то просто так и печаталось
Можно было написать PRINT USING
Можно было указать устройство вывода
2) INPUT – ввод с клавиатуры
INPUT “Введите числа” A, B, C

3) IF B THEN n ~ IF B GOTO n
IF B THEN

4) Приоритет операций
0) скобки, функции
1) ^,¬ (возведение в степень)
2) – (унарный минус)
3) *, /
4) +, –
5) , =

Потом появились OR, AND, NOT, XOR, IMPимпликация, EQU ~ ⇔. У этих операторов
приоритета либо нет, либо OR, AND, NOT, а
затем все остальные.

5) Описание переменных
COM – одномерный массив
DIM – многомерный массив (для массивов описание обязательно!)
Были и такие версии Basic’a в которых описание массива также было
необязательно. Такие массивы могут быть произвольной длины и реализовывались
как «пачка переменных»
6) LET – необязательное слово. A=5 ~ LET A=5
7) GOTO n – безусловный переход; почти все программы на Basic имели оператор
GOTO.
GOSUB n – переход с возвратом (вызов подпрограммы).
При это важно то, что у Basic’a все данные глобальны (⇒ нет процедур или
функций).
Можно GOTO/GOSUB – переход по значению переменной.
8) Циклы: FOR = TO [STEP ]
Если STEP неуказан, то шаг=1
9) REM (от слова REMARK) – комментарии, печатались на листинге
Модификации Basic’a:
CALL addr
rts, ref
DEF FN y=sinx/x
FN y(1)

Обозначения типов (с помощью добавления суффиксов):
! – целое
A1 $NAME
% – плавающая точка
A$(10,10,25) – двумерный массив строк меньших
# – двойная точность
25 символов.
$ – строка
Есть функции преобразования типов.
Основной язык для игровых приставок – графика, звук и т.д. Пишут интерфейс на
Basic’e и вставки на ASM’е.
SCREEN – магическая функция, в зависимости от параметров меняет цвет экрана,
звук и т.д.
10) DATA 5,10,8,7 …
…
READ A,B,C,D
RESTORE
– перевернуть стек
11) ON ERROR GOTO – обработка ошибок
GOSUB
ON α GOTO 5,10,135 – в зависимости от целой части α
если 0 ⇒ на 5
GOSUB

если 1 ⇒ на 10 и т.д.
Есть Quick Basic, Turbo Basic – более продвинутые.
Visual Basic – совсем другой язык, на нем писать удобно.

Pascal/Modula 2
Pascal (Н. Вирт, около 1972 г.), был придуман как язык для обучения, но со временем
перерос изначальный замысел и даже собственные возможности.
В первоначальном виде язык был очень простым и минимизировал ошибки с типами
(в отличие от C).
Система типов данных (достаточно удачная и позже растиражированная во многих
ЯП).
Скалярные типы (представлены одним значением):
Встроенные типы: integer, char, boolean, real
Перечислимые типы: type color = (red, green, blue), причем этот тип не совпадает
напрямую с integer.
Диапазон значений: type natural = 1 … maxint; эти типы совместимы с integer, но
во время работы производится проверка на нахождение в диапозоне.
Отметим, что тип boolean может быть определен как type boolean = (false, true)
Составные типы:
1) Массив:
type vec10 = array [1..10] of char;

здесь может быть диапазон или любой другой
тип: chartab = array [char] of char и это юудет
нормальный массив с индексами типа char.
Многомерные массивы – как массив массивов.
type mat = array [1..10] of
array[0..20] of integer;

~
полная
эквивалентность

array [1..10,0..20] of
integer;

2) Запись
type complex = record
re, im: real;
end

Есть еще указатели: type ptrint =↑integer; (ныне записывается как ^integer).
Записи с вариантами:
ptree = ↑tree;
tag = (node, leaf);
tree = record
tag: tag of
leaf : (info : integer)
node : (l,r : ptree)
end;

type
type
type
case

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

необходимо все типы описать явно (то есть нельзя описать переменную a: ↑tree, хотя
большинство компиляторов это не учитывает).
Типы считаются одинаковыми, если их имена совпадают, либо если они описаны как
тождественные некоторому третьему. То есть,
var a = array [char] of char;
var b = array [char] of char;

Неэквивалентные типы, т.е. нельзя a:=b. Для этого необходимо описать общий тип
type t = array [char] of char;

Структура программы на Pascal’e:
[program имя;]
[label … ]
[const … ]
[type … ]
[var … ]
[proc & func ]
begin
end

Все блоки должны следовать именно в таком порядке. Любой блок может быть
опущен. Современные трансляторы понимают программы, в которых эти блоки встречаются
несколько раз, но в каноническом Pascal’e этого нет (равно как и константных выражений).
Операторы
1) a:=expr;
+, –, *, /, div, mod
m[i,j] ~ m[i][j]. Можно присвоить строку m[i]:=m[j], но нельзя вырезать строку или
столбец как Алголе 68.
Разыменование указателей: a↑ (это лучше, чем в С++, так как a↑. выглядит
нормально, но (*a).b выглядит так плохо, что даже ввели специальный опертаор a→b).
2) if
then
[else ]

Причем должно быть именно одним оператором, иначе необходимо окружить
операторными скобками begin … end
3) Циклы трех видов:
while do
repeat until – выполняется пока условие ложно
for i:= to/downto do

Начальное и конечное выражения вычисляются только при входе в цикл ⇒
присваивание переменной цикла приводит к непредсказуемым последствиям. Выражение
переменной цикла может быть любого перечислимого типа.
4) with do
Здесь выражение должно выдавать переменную типа запись и тогда его внутренние
поля доступны как простые переменные
5) Выделение памяти:
new (p[,tag, …])

В классическом Pascal’e это единственный способ доступиться к памяти (адрес
переменной получить вообще-то нельзя).
Пример
var one,two,t: ptree;
begin
new(one,leaf);
one↑.tag:=leaf;
one↑.info:=1;
new(t,node);
with t↑ do
tag:=node; l:=one; r:=two;
end;
end.

Процедуры в Pascal’e
procedure p (…);
function f (…): integer; – возвращаемое значение может быть только скалярного
типа (⇒ не запись)

Параметры могут быть:
а) a: t – по значению
б) var a:t – по ссылке (причем переменная должна быть точно совпадающей по типу)
в) параметры процедурного типа

Процедуры без параметров пишутся без скобок, что порою приводит к
двусмысленности прочтения.
Процедуры могут быть вложенные, что в более поздних языках не используется. По
утверждению Москаля, это не так просто как кажется…
procedure foreach (t: ptree; procedure action (var t: integer));
begin
with t↑ do
case tag of
Наблюдаются существенные различия
leaf: action(info);
между Turbo Pascal’ем и прочими реализациями
node: begin
(в Turbo Pascal’e необходимо было, чтобы
foreach(l, action);
передаваемая параметром процедура была
foreach(r, action);
глобальной).
end
end
Кроме того, в TP запрещен выход из
end;
процедуры по метке.
function sum (t: ptree): integer;
var s: integer;

procedure action (var i: integer);
begin s:=s+i end;
begin
s:=0;
foreach (t,action);
sum:=s;
end;

–
так
ничего
работать не будет,
ибо достучаться
до переменных не
удается (поэтому
в TP передаваемая
процедура должна
быть глобальной)

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

процедура, передаваемая параметром

push bp
mov bp,sp
sub sp,2
push 4[bp]
push action
push bp
call foreach

Как в нем вызывается action(i)?
push
mov si,bp(action)
mov di,action
xchg bp,si
call [di]
xchg bp,si

Модула 2 – улучшенный вариант Pascal’я.
1) Запретили передавать вложенные процедуры параметром.

push bp
mov bp,sp
mov bx, [bp]
mov ax, 4[bp]
add –2[bx],ax
mov sp,bp
pop bp
ret 2

2) Поддержка раздельной трансляции (напоминает Pascal’евские unit)
DEFINITION MODULE M;
…
END
IMPLEMENTATION MODULE M
…
END

В Модуле 2 различаются большие и маленькие буквы.
Все что описано в definition module, должно быть реализовано в implementation
module. После этого можно писать
IMPORT M;
M.P;
END

– вызов P из модуля M

Чем это лучше С-шной системы с include? При трансляции definition module создается
табличка, которая может быть подкачана при встрече оператора import (⇒ уменьшаем время
трансляции). Кроме того, модули не могут мешать друг другу (в отличие от include’ов,
которые могут описывать одно и то же, вызывая ошибку).
В C++ системные заголовки – порядка 10 Мб и при трансляции каждого файла все это
заново транслируется.

C/C++
Как возник язык С? Все началось с языка CPL (середина 60-х гг., Кристофер
Стрейч). Этот язык так и не был доведен даже до формального описания, но была придумана
масса полезных идей.
Упрощенная версия CPL – Basic CPL или BCPL. Был реализован методом раскрутки
(bootstrapping), для этого выкинули из языка всю динамику и т.д.
MULTICS – первая попытка написать ОС на языке высокого уровня. Провалилась изза чрезмерной раздутости и монстрячности. Затем попытались сделать что-то попроще,
сделали язык B и OC UNIX.
Специфика языка была связана со спецификой машины PDP7, для которой он
создавался. Адресация на PDP7 была условная, объем доступной памяти – 16 килослов
(никакихбайтов!) ⇒ сделали автокод бестиповым (все данные – целые).
*(a+i) – это адрес i-го элемента массива. Массив – это указатель на начало, так как
ничего другого нет (структур нет).
f(a,b,c) { … } – никаких типов для параметров было не нужно.
Все имена всех полей структур должны были быть различными (эта особенность
дожила даже до стандарта Кернигана и Ричи).
Язык С (Керниган, Ричи, 1978 г.) – язык-ядро, компилирующий язык. Основные
задачи:
– эффективность;
– низкоуровневость;
– вставки на ASM.

Что появилось нового?
1) union S {
int a;
float b;
}

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

2) Макропроцессор (до того был в PL/I и частично в ASM)
Пример:
file1.c
file2.c
Вынесем
в
один
заголовочный
файл:
struct S {int a; char b}
struct S {int a; chat b} structdef.h struct s {…}
S* T1;
S* T1;
И заменим на #include.
Существует проблема избыточных описаний – не всегда получается все иерархически
организовать и одни и те же определения могут быть включены несколько раз. Против этого
применяется следующий трюк:
#ifndef STRUCT_DEFS_H
#define STRUCT_DEFS_H
struct S …
#endif

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

С помощью макросов из C++ можно сделать «почти Алгол 68»!
Можно #define int16 int и при переносе не иметь проблем с заменой типов (по делу,
конечно, надо использовать typedef).
typedef – синоним типа (⇒ типы int16 и int были бы приводимы).
struct – всегда создает новый тип. Например S1 и S2 – разных типов:
struсt S1 { int a;}
struсt S2 { int b;}

Итак, что хорошо в С?
– можно писать эффективно, практически без контроля;
– мощная поддержка и переносимость (хотя размер типов данных отличается,
стандартные библиотеки разные и т.д.)
– работа с памятью
Что плохо в C?
– можно описать функцию без параметра, а вызвать с параметром:
void f ();
int main ()
{
f(2);
}

И это не будет отловлено

– функции с неопределенным числом параметров (printf – определяет по формату: если
формат и переменные не совпадают ⇒ облом);
printf("My name is %s%s\n",2);

– значения по умолчанию;
– индексация всегда с нуля ⇒ int a[15]; a[15]:= …; – это ошибка, но отловлено
опять-таки не будет
– интуитивно неясные операторы: if (a=b) // надо “==”
– отсутствие break в case
Язык С++ (Страуструп, 80-е)

Что в С++ существенного нового?
–
–
–
–
–
–

классы (classes);
шаблоны(templates);
пространства имен (namespaces);
перегрузка (overload);
потоки (streams);
исключения (exception)

Замечание. Практически нигде С++ в полном объеме не используется, что бы там ни
писал Страуструп. Обычно выдергивают какие-то части, а остальное берут из чистого С.

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

средства макропроцессора. Перегрузка используется достаточно часто (ибо действительно
удобно), но иногда ведет к трудно находимым ошибкам или ошибкам времени компиляции:
void f1(char);
void f2(char*);

void f1(long);
void f2(int*);

void foo (int i)
{
f1(i); // неоднозначность
f2(0); // также неоднозначность: char* или int
}

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

Впервые появились в COBOL и PL/I (но там пользователь не мог определить новых
исключений). Замечателен оптимизм названия – «исключительные» ситуации возникают
сплошь и рядом.
Без исключений приходится делать безусловный переход наружу и там обрабатывать
ситуацию. Еще вариант – setjmp/longjmp (глобальный переход). Проблема в том, что не
вызываются деструкторы для созданных объектов (подразумеваются в конце блока). Иначе
надо проверять коды возврата для каждой функции, проверять успешность каждой операции
и т.д. (defensive programming).
Как же выглядит обработка исключений в C++?
{
try {
… foo(); …
} catch( … ) {
// обработка исключений, возникших в блоке try
}
}
void foo (void)
{
… if (!something_ready)
throw 0; …
}

Есть проблемы, прежде всего с освобождением памяти. Теперь свертка стека
произойдет, НО не будет производиться освобождение памяти для всех ресурсов,
управляемых программистом (new/delete).
Для решения этой проблемы предлагается создавать «классы-обвязки» (wrapper
classes) с освобождением всех ресурсов в деструкторе класса – довольно неуклюже выглядит
на практике.
В C++ исключения могут создаваться пользователем; используется механизм
наследования try {throw 1;} catch (long) {} не работает (нельзя приводить базовые типы), но
try {throw B();} catch(A) {} будет работать, если B – производный от A/
В C++ НЕТ finally (считается повышающим вероятность ошибок в коде). Если
хочется, можно написать опять-таки класс и поместить эти действия в его деструктор.

PROLOG
Язык Prolog (PROgramming in LOGic), около 1970 г. Является языком логического
программирования.
Логическое программирование (язык описаний) являются противоположностью к
подходу процедурного программирования (языка предписаний).
Описывается модель мира, затем формулируются вопросы, т.е. не говорится «как
делать», а спрашивается «верно/неверно»?
Формулируются:
1. Факты
2. Правила
3. Вопросы
1) Факты
нравится(джон, деньги)
нравится (мэри, рыба)
король(иван, франция)
нравится(джон, мэри)
женщина(мэри)
женщина(лиза)
красивый(лиза)

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

Согласуется ли данный факт с базой данных? СМотрим сверху вниз, ищем
совпадающий предикат, затем – совпадающие параметры.
Переменные:
? – нравится(джон, X)

X=деньги ???
Х=мэри;
???

Переменные – с большой буквы. Могут принимать любые значения. Переменные
бывают анонимными:
? – отец(_,джон)
конкретизируется самостоятельно
3) Правила, конъюнкции, дизъюнкции
женщ_нравится(джон,Х) :– женщина(Х), красивый(X).

С помощью таких правил можно порождать новые факты. Как это работает? Вначале
Х не кокретизирован, при конкретизации X подставляется во всём правиле.
Цели согласуются по порядку: вначале находим женщину, затем пытаемся узнать,
является ли она красивой. Если вторая цель не согласовывается, то производится возврат
(backtracking) к первой цели и т.д.
Backtracking ужасно неэффективен.
Для записи дизъюнкции правило записывается второй раз с другой правой частью:
женщ_нравится(джон,X) :– женщина(X), нравится(джон,X).

В этом случае Мэри тоже подойдет.

Упражнение. Пусть есть предикаты родитель(X,Y), ребенок(X,Y), женщина(X),
мужчина(X). Написать предикаты для брата, сестры, дочери, тети и т.п.

4) Рекурсия

человек(адам).
человек(X) :– человек(Y), отец(Y,X).

Таким образом – это либо адам, либо тот, чьим прапра…прадедом был адам.
Очень важен порядок – если поменять факт и правило местами, то программа
зациклится на правиле (никогда не завершится).
PROLOG допускает только правосторонню рекурсию. Надо также избегать кольцевой
рекурсии:
ребенок(X,Y):–родитель(Y,X).
родитель(Y,X):– ребенок(X,Y).

Какие еще бывают неприятности с рекурсией?
Рассмотрим списки: структуры с головой и хвостом, ‘|’ – объединение двух списков.
[a,b,c, [a,b]] – список, где [a] – голова, [b,c,[a,b]] – хвост и т.д.
Теперь:
список([A|B]) :– список(B).
список([]).

В эти правила замечательно укладывается список, приведенный выше, а также другие
конкретные списки. Но если задать вопрос:
? – список(X)
произойдет зацикливание. Надо поменять местами факт и правило, а также заменить
работу с хвостом на работу с головой списка.
Наконец, рекурсия может быть использована для порождения бесконечного числа
элементов, как в следующем примере:
целое(0).
целое(X) :– целое(Y), X is Y+1.

Этот пример породит 0,1,2,3…
5) Отсечения
Предназначены для повышения эффективности программ путем уменьшения числа
возвратов. Используются в тех случаях, когда программист знает, что встретив данное
решение, дальше искать не надо.
Пример: Библиотечная система, в которой обычным читателям доступны все услуги,
а читателям не возвратившим в срок книги (хотя бы одну), доступны только основные
услуги:
услуги(Читатель, Вид_услуг) :– книга_не_возвр(Читатель,Книга),
!,
основные_услуги(Вид_услуг).
услуги(Читатель,Вид_Услуг) :- все_услуги(Вид_услуг).
осн_услуги(польз_книгами).
осн_услуги(сдача_книг).
доп_услуги(бан).
доп_услуги(межбибл_абонемент).
все_услуги(X) :– осн_услуги(X).
все_услуги(X) :– осн_услуги(X).
…
книга_не_возвр(‘А.Терехов’,’Феденко’).
книга_не_возвр(‘А.Терехов’,’Брукс’).
читатель(‘А.Терехов’).
читатель(‘В.Уфнаровский’).

? – читатель(X), услуги(X,Y).

Данный вопрос выводит список всех читателей и доступных им услуг. При этом если
хотя бы одна книга не возвращена, то происходит отсечение и все сделанные до этого
выборы (в том числе, конкретизация переменных) фиксируются, т.е. влево от ‘!’ мы уже не
пойдем.
Пример: foo(X) :– a,b,c,!,d,e,f.
Здесь после того, как согласованы a,b и с, они больше уже никогда не изменятся, и
если мы не согласуем d,e и f при данных условиях, то все правило выдает нет. Т.о. ‘!’ –
заборчик, через который можно перепрыгнуть только в одну сторону.
С точки зрения нахождения решения отсечение эквивалентно отрицанию.
A:- B,!,C.
A:-D.

A:-B,C.

~

A:-not(B),D.

Но во втором случае перебор существенно больше.
В некоторых реализациях Пролога not выражается через отсечение в явном виде.
not(P) :– call(P),!, fail.
not(P).

Когда бывают отсечения?
1) нашли условие, из которого ясно, что других согласований не нужно
2) если что-то не так, то сразу закончить перебор обломом (см. определение not через
отсечение)
3) в качестве успешного останова (например, в качестве граничного условия, как в
следующем примере).
Пример: считаем сумму чисел от 1 до N:
сумма(1,1) :– !.
сумма(N,результат):- N1 is N-1, сумма(N1, Результат), Результат is Результат+N.

Пример(заключительный):
Ханойские башни
1) перемещать можно только верхнее
кольцо.
2) класть можно только на кольцо
большего диаметра.
ханой(N) :– переместить(N,лев,средн,прав).
переместить(0,_,_,_) :- !.
переместить(N,A,B,C) :–
M is N-1,
переместить (M,A,B,C),
сообщить(A,B),
переместить (M,C,B,A).
сообщить(X,Y) :write([переместили, диск, со, штыря, X, на, Y]), nl.

Occam
Язык Оккам – зык параллельного программирования. Давно было известно, что
увеличение числа процессоров от 1 до n не означает ускорения вычислений в n раз. Однако
постоянно ведутся работы над созданием эффективной модели для параллельных
вычислений. Одной из первых таких моделей стала CSP, предложенная Тони Хоаром (C.A.R.
Hoare). Основная идея – применение относительно независимо выполняющихся процессов,
обменивающихся информацией с помощью посылки и приема сообщений по каналам (CSP =
Communication Sequential Processes, взаимодействующие последовательные процессы).
Недавно возникла еще одна популярная модель параллелизма – BSP (BulkSynchronous Parallelism) – 1990 г., Оксфорд, McColl.
Программа на Оккаме – это процесс, описывающий некоторые действия, подлежащие
выполнению (т.е. алгоритм).
Какие бывают процессы?

1) Примитивные процессы
а) SKIP – не выполняет никаких действий и завершается (так же полезен в Оккаме,
как 0 в десятичной системе);
б) STOP – тоже не выполняет никаких действий, но не завершается (аварийная
ситуация, например, тупик, запрещенная команда и т.п.)
2) Последовательные процессы
Последовательное выполнение заключается
в присваивании переменным
определенных значений, на основании которых в дальнейшем принимаются некоторые
решения. Присваивание выглядит так:
переменная := выражение
И выражение и переменные не имеют типов и представляют собой просто
комбинации битов размером в слово данного компьютера. В некоторых операциях эти
последовательности битов используются как числа, логические значения или символы, но ни
язык, ни компиляторы Оккама не поддерживают распознование типов (до 2-й версии языка –
в ней были введены различные типы данных, что «позволяет отнести эти версии языка к
АЯВУ»).
Последовательный процесс (SEQ-процесс) конструируется посредством записи
последовательности его компонент, располагаемых одна под другой с небольшим отступом
вправо от ключевого слова SEQ.
Пример:
SEQ
x:=3
y:=x=7
x:=x+6
x:=(y+z)/2

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

IF
n0
sign:=1

Просмотр производится сверху вниз, пока не встретим истинное условие – тогда
начинает выполняться соответствующий процесс (причем выполняется только один
процесс). Если истинное условие не встретилось, то возникает ошибочная ситуация и IFпроцесс останавливается (т.е. ведет себя как STOP).
Интересно, что в качестве условий можно было бы перечислить n=0, n>) x f = f x
(сокращение от let (>>) = fun x → fun f → f x)
Теперь можно писать x >> sin >> cos вместо cos(sinx)

Заметим, что в функциональных языках аргумент функции пишется сразу после
функции без скобок (⇒ в примере cos sin x скобки ставятся как (cos sin) x ).

Из описания >> видно, что f имеет вид ’a → ’b, выдаваемый результат равен
выдаваемому значению f=’b; итого имеем для >> (что уже неплохая информация о типах):
’a → (’a → ’b) → ’b что уже неплохая информация о типах
В C++ для записи такой функции пришлось бы использовать конкретный тип, либо
template (хотя работает плохо на приведенном примере – ни х, ни sin классами не являются).
Пример (классический, композиция функций):
let compose f g =
fun x → f (g x)
(’a → ’b ) → (’c → ’a) → (’c → ’b)

тип f

тип g

тип compose

Как реализуется полиморфизм? Любой тип укладывается в слово, либо ставится
указатель на адрес со значением (плохо для плавающих чисел). Полиморфные функции.
В ML существуют переменные и присваивания. Существуют конструкторы с
параметром (параметр записывается перед конструктором). Пространство имен и
пространство типов не пересекаются. Имена конструкторов – с большой буквы, имена
переменных – с маленькой. Case sensitive.
ref: ’a → ’a ref
(аналог new, по значению создает переменную)
(!): ’a ref → ’a
(аналог ‘*’, выдает значение переменной)
(:=): ’a ref → ’a → unit (“:=” выдает пустое значение)

Пример.
(( let n = ref 0 in
(( for i=1 to 10 do
n:=(!n)+i
done);
!n))

; – бинарная операция; считает первое значение, его затем убивает и выводит второе
значение.
Вместо ‘(‘,’)’ можно писать begin , end в качестве структурных скобок.
В этом примере все переменные целые, т.к. используется ref 0, т.е. целые.
Алгебраические типы данных (на самом деле, скорее тэгированные объединения),
обычно это рекурсивные типы – либо пустые, либо набор (голова, хвост), возможно с
рекурсией.
type ’a list =
Nil
| Cons of ’a*’a list

‘*’ образовывает упорядоченную пару из двух элементов. Используется рекурсия.
Когда в такой список запихают переменную какого-либо конкретного типа, список будет
принимать переменные только такого типа (встроенные списки реализуются именно так).

Пример использования списка: cons (1, cons(2, Nil)). Т.к. списки встроены, то
это можно записать как [1;2]
let rec map f l =
match l with
Nil → Nil
| Cons (hd, tl) →
Cons (f hd, map f tl)
let div a b =
(a/b, a mod b)
int → int → int*int
let (q,r) = div n 10 in …

Сравнение с образцом после левой части
образца можно также вставить when
Словечко rec ставится для того, чтобы
можно было использовать в правой части
переменную из левой части let.
Здесь тоже упорядоченная пара, ‘*’
используется только в типах (см. типы
функций). И дальше используется пара q,r…

Пример (символические вычисления. Будем упрощать выражения):
type expr
Con of int
| Var of string
| Bin of (expr*string*expr)
let rec simplify e =
match e with
Bin (a,op,b) →
let rec s’ e = match e with
(con a, "+", con b) → con(a+b)
|(con a, "*", con b) → con(a*b)
|(con n, ("+"|"*") as op,b) → s’ (b,op con n) ???
|(a, "+", con 0) → a
|(a, "*", con 0) → con 0
|(a, "*", con 1) → a
| _ → Bin e
т.е. не упростилось
in
s’ (simplify a,op, simplify b)
| _ → e

Замечание Апостроф не в первой позиции – обычная буква

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

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

Пример (бесконечный список):
from n = n: from (n+1)

‘:’ – аналог cons ⇒ бесконечный список. Однако, напечатать такой список нельзя.
Можно воспользоваться функцией take, печатающей первые k чисел списка: take 10 from 0
Пример (бесконечный список простых чисел. «Ленивое решето Эратосфена»):
primes = from [2..] where
from (n: tail) = n:
from [m|m ← tail, m ‘mod‘n /=0]
main = putStr (show(
take 20 primes ))

Smalltalk
Smalltalk - разработка фирмы Xerox, около 1970 г., сугубо ОО-язык.
Smalltalk – первый чистый ОО-язык; Smalltalk представляет из себя систему,
которая абстрагирует пользователя от реального мира с помощью виртуальной
машины (но даже ее пользователь может переписать). Объекты обладают
модульностью (⇒ раздельная трансляция). ST позволяет управлять сложностью
системы.
Из чего состоит система Smalltalk?
1. Объекты – простейший компонент системы. Содержат в себе данные и методы
(операции над данными). Наружу из объекта торчат интерфейсы.
2. Сообщения – все управление программой производится с помощью сообщений.
Сообщение состоит из:
– объекта-получателя;
– имени сообщения;
– [аргументы].
Интерфейс – это множество всех сообщений, на которое объект может ответить.
3. Класс – описывает тип объекта и его структуру. Бывают данные класса и методы
класса (которые разделяются между всеми экземплярами класса).
4. Переменные – это объект, принадлежащий памяти какого-то объекта и
ссылающаяся на какой-то другой объект (может ссылаться на специальный объект
Nil). Существуют правила видимости, контексты.
Имена классов, данных классов должны начинаться с большой буквы.
Переменные бывают разные:
а) доступные только одному объекту
– переменные экземпляра;
– временные переменные (например, переменная, объявленная в блоке);
б) общие переменные, доступные либо экземплярам данного класса, либо всем
объектам, либо выборочно:
– переменные класса;
– глобальные переменные;
– переменные пула.
Программирование на ST состоит из создания иерархии классов, описания
внутренности этих классов и правил взаимодействия между ними. Существует достаточно
много предопределенных классов, что сильно облегчает программирование.
Иерархия классов

Создается с помощью наследования. Наследующий класс называется подклассом, от
которого наследуется – называется суперклассом. Все, классы от кого-то наследуются
(наиболее часто от Object’a – некоторого класса, у которого нет суперкласса).
Множественного наследования как такового нет.

Отрывок из иерархии классов
Object
Magnitude
Character
Date
Time
Number
Float
Fraction
Integer
LargeNegativeInteger
LargePositiveInteger
SmallInteger
Collection
SequenceableCollection
LinkedList
Semaphore
ArrayedCollection
Array
Word Array
Display Bitmap
Run Array
String …

Почему надо знать иерархию объектов? Потому, что сообщение, которое не может
быть обработано, передается на обработку его суперклассу, затем его суперклассу и т.д. Если
дошли до Object’a и не смогли обработать, то высылается ответное сообщение
doesNotUnderstand: (‘:’ – т.к. системное сообщение).
О гармонии мироздания:
Объекты – являются экземплярами класса.
Классы – если все является объектами ⇒ у них тоже должны быть свои прототипы ⇒
Метаклассы – невидимы для пользователя; классы являются экземплярами
метакласса. Все метаклассы являются экземплярами MetaClass.

Синтаксис языка:

Выражения:
1. Литералы
2. Имена переменных (только эти выражения зависят от контекста)
3. Выражения посылки сообщений (значение определяется классом-получателем)
4. Выражения-блоки

Массив:
# ('1' '2' '3')
# ((1 2) 3)

Внутри массива могут быть другие массивы ( но они решеткой не обозначаются).
Массивы могут быть неоднородными.
Присваивания:
Обозначаются “←” (в более поздних версиях “:=” тоже разрешено)
Сообщения:
Имя получателя
Имя сообщения
Сообщения могут быть:
– унарные alpha sin (могут выдать результат или ошибку)
– бинарные Number+1 (результат будет выдан наружу)
– ключевые ages at: 'Вася' put 3 (эквивалентно at: put: 'Вася' 3, т.е. сообщение с 2
переменными)
Правила разбора сообщений:
1. Унарные и бинарные – слева направо
2. Бинарные выше по приоритету, чем ключевые
3. Унарные выше бинарных
4. Выражения в скобках выше унарных
Каскадирование сообщений:
Collection new add:1; add:2; add:3

что эквивалентно
|temp|
temp ←
temp ←
temp ←
temp ←

Описание переменных заключается в |…|.
Операторы разделяются “.”

Collection new.
add:1.
add:2.
add:3.

Выражения-блоки:
[index ← index+1]

– вычисляется только по получении сообщения value

Т.о. записывается, например, цикл for:
4 Times Repeat: [index ← index+1]

Если послать value блоку [], то получим Nil

Условные выражения:
(number \\ 2) = 0
if True: [parity ← 0]
if False: [parity ← 1]
[: array | total ← total+array size]

– параметром будет передан массив и
добавится его размер

Пример:
Class name
History
superclass
Object
instance variable names allIncomes incomes
class variable names RateTax
class methods
initialize
initialize
RateTax ← 0.12
instance creation
initial Balance : amount
^ super new setInitialBalance : amount
new
^ super new setInitialBalance : 0
instance methods
transaction recording
recieve: amount from: source
incomes at: source
put: (self totalRecievedFrom : source)+amount
inquires
totalRecievedFrom: source
(incomes includekey: source)
if True: [^incomes at: source]
if False: [^0]...

Заключительная лекция
Subtyping – подтипы (строятся наследованием, но не только им).

Определение. Тип A является подтипом B, если в любом контексте, где можно
использовать B, допустимо использование A. Обозначается A