Императивное программирование (2022)

Монтаж лекции / Запись прямого эфира

Напоминание:

Аллегируемые объекты
Выполнение действий, обусловленное свойствами объекта

Проблемы реализации:

Дисциплина аллегирования (как различать объекты)
- имена, номера, связывание (например, операндом функции), …?
Порядок составных действий (как гарантировать однозначность хода выполнения программы)
- граф зависимости (⇒ последовательность, зависимость по данным/управлению и т. п.)
Итерация
- циклы, рекурсия, актуально конечные повторения, …

В Википедии:

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

С нашей кочки зрения:

Хранение объектов как основной способ аллегирования, ссылки на них (имена, адреса, указатели и т. п.)
Действие — это модификация (+создание/удаление) хранимого объекта (инструкция)
Программа — это последовательность инструкций
В зависимости от свойств объектов, последовательные части программы не выполняются или выполняются повторно

Архитектура фон Неймана

Адресуемая память
Объекты — ячейки памяти с данными
Программа — последовательность ячеек памяти с инструкциями
Условные переходы вперёд и назад по адресам

Язык ассемблера:

Человеко-ориентированное представление данных и инструкций
Метки вместо адресов
(всё остальное — «удобства»)
Пример текста на языке ассемблера RISC-V
```
   1 # Посчитать сумму цифр числа (в т. ч. отрицательного)
   2 .data
   3 number: .word   -12345
   4 digsum: .word   0
   5 
   6 .text
   7         lw      t1 number
   8         bgez    t1 pos
   9         sub     t1 zero t1
  10 pos:    mv      t2 zero
  11         li      t3 10
  12 next:   remu    t4 t1 t3
  13         add     t2 t2 t4
  14         divu    t1 t1 t3
  15         bgtz    t1 next
  16         sw      t2 digsum t4
```

Получаемые машинные коды

Address     Code        Basic                        Line Source
0x00400000  0x0fc10317  auipc x6,0x0000fc10          7          lw      t1 number
0x00400004  0x00032303  lw x6,0(x6)
0x00400008  0x00035463  bge x6,x0,0x00000008         8          bgez    t1 pos
0x0040000c  0x40600333  sub x6,x0,x6                 9          sub     t1 zero t1
0x00400010  0x000003b3  add x7,x0,x0                 10   pos:  mv      t2 zero
0x00400014  0x00a00e13  addi x28,x0,10               11         li      t3 10
0x00400018  0x03c37eb3  remu x29,x6,x28              12   next: remu    t4 t1 t3
0x0040001c  0x01d383b3  add x7,x7,x29                13         add     t2 t2 t4
0x00400020  0x03c35333  divu x6,x6,x28               14         divu    t1 t1 t3
0x00400024  0xfe604ae3  blt x0,x6,0xfffffff4         15         bgtz    t1 next
0x00400028  0x0fc10e97  auipc x29,0x0000fc10         16         sw      t2 digsum t4
0x0040002c  0xfc7eae23  sw x7,0xffffffdc(x29)

Процедурные языки

Процедурный язык как результат борьбы с неудобствами языка Ассемблера:

Формулы (⇒ Фортран)
Архитектурно-зависимое ABI (⇒ Си)
Абстрактные и актуальные (но ∄ на данной архитектуре) типы данных и их моделирование

Типичные черты (не обязательно для всех):

Типизированные «переменные» вместо меток (метафора «ящика с дыркой»)
Отдельные типы данных для аллегирования («указатели») вместо адресов
Составные типы данных («структуры», «записи» и т. п.)
Функции/процедуры, содержащие «локальные переменные»

Дисциплины аллегирования не влияют на парадигму:

Передача параметров по значению (как в Си)
Передача параметров по имени (как в Алголе)
Передача параметров по соиспользованию (как в Python, Java, …)
Несколько способов (Паскаль, C++, …)

Исключение указателей из синтаксиса также не выводит из парадигмы, при этом:

требует автоматическое управление памятью (например, с помощью refcount)
почти всегда означает передачу параметров по соиспользованию

Исторические представители:

Фортран и Алгол:

Алгол: шашечки или ехать:
```
   1 begin
   2   procedure p (a, b);
   3     name a, b; integer a, b;
   4   begin
   5     for a:=1 step 1 until 10 do
   6       b := 0
   7   end p;
   8   integer i; integer array s [1:10];
   9   p (i, s[i])
  10 end
```
- В чём подвох? Спойлер (нажмите «комментарии» в шапе страницы):

Фортран: динамические массивы под ковром…

1 do k=1,10 2 do j=1,20 3 do i=1,100 4 arr(i,j,k)=25 5 end do; end do; end do	Правильно
1 do k=1,10 2 do j=1,20 3 do i=1,100 4 arr(k,j,i)=25 5 end do; end do; end do	В несколько раз медленнее

Фортран живее всех живых!
Работающий Алгол ∃ скорее в виде экспоната

Бейсик и Кобол
Си_(язык_программирования) и Паскаль

Современные:

Тысячи их!

Высокоуровневые ЯП

( На Википедии понятие описано несколько невразумительно)

Объективный признак: несовпадение модели вычислений абстрактного (заданного ЯП) и фактического исполнителя
- ⇒ фиксация модели вычислений на уровне семантики ЯП
- (скорее всего) введение в синтаксис сложных структур данных и операций над ними
⇒ Признаки низкоуровневого ЯП:
- введение вычислительной модели фактического исполнителя в прагматику ЯП
- наличие явных областей неопределённого поведения в синтаксисе (это «не бага, а фича», означающая, что на различных архитектурах работа этих областей имеет право различаться)
Субъективные признаки: сокращение объёма и увеличение читаемости программы, ориентация на решение определённого класса прикладных задач

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

ООП (частый спутник ЯПВУ) — парадигма или нет?
Мультипарадигмальность

Си и Паскаль

Онтологическое отличие: цель создания

Общее

Процедурный ЯП начала 70-х
Очень простой синтаксис
Глобальные и локальные переменные
Типы данных:
- Простые
- Составные
- Указатели
- Отсутствие алгоритмически непрозрачных абстрактных типов данных
…

Различия

Pascal:

P: Перечеслимые типы, диапазоны и множества
P: Указатели
P: Разделение процедур и функций, передача параметров по ссылке
P: Файл как тип данных (устаревшее?)
…
P: Разнообразие диалектов, их несоответствие стандарту (в т. ч. не реализованный до конца Extended Pascal)

C:

C: Присваивание и запятая как операции
C: Приведение типов (в том числе ссылочных)
C: Адресная арифметика как реализация понятия «массив»
C: Аппаратно-ориентированные возможности (+ packed array в Паскале)
C: … (например, Duff device)
…
Практически не теряет популярности, активно поддерживается GCC/Clang и развивается

Характерные недостатки

Недостаточная высокоуровневость стандартного Pascal
- Модель памяти и указатели
- Отказ от «синтаксического сахара»
- Разнобой и зависимость «продолжений» от legacy
Проблемы читаемости в Си
- Побочные эффекты (см., например, у А. В. Столярова тут и тут)
- International_Obfuscated_C_Code_Contest

Общий вывод

Сильное отличие в уровне абстракции

Pascal: высокоуровневый язык вокруг низкоуровневой вычислительной модели
C: лучший в мире макроассемблер

Современные тенденции

Насыщение синтаксиса ЯП актуальными приёмами программирования и актуальными встроенными типами данных (словари, итераторы, декораторы, асинхронность, исключения, неопределённые значения, статус ошибки и т. п.)
Более безопасная модель памяти (в качестве единственной или в качестве альтернативы)
Включение удобных инструментов из других парадигм
Частичная алгоритмизация периода компиляции в синтаксисе (а не внешним препроцессором, как в Си)
Интроспекция / рефлексия
Инкапсуляция как базовый синтаксический инструмент (даже в отсутствие поддержки ООП)

Бонус

NIM как «новый Паскаль» (пример на Learn X in Y minutes)
- …
ZIG как «новый Си»…примеры в документации
- или Rust?
- …

Д/З

Восстановить в памяти синтаксис Си и Паскаля.
Выбрать один пример из перечисленных ниже, написать решение на двух языках — Си и Паскале
Требования
1. По возможности не писать «на Си как на Паскале» и наоборот, а пользоваться особенностями языка
2. В задачах требуется (1) написать функцию или процедуру, (2) ввести данные, (3) вызвать написанную подпрограмму, (4) вывести результат.
  - Можно вводить дополнительные процедуры и функции.
  - Обратите внимание на требования языка Pascal относительно отсутствия побочных эффектов в функциях.
  - В данном задании оно распространяется и на Си; в Си «процедурой» (в которой разрешены побочные эффекты) будем называть void-функцию
3. Вводом и выводом занимается только основная программа (в случае Си — main(), в случае Паскаля — program)
  - Если это требуется условием задачи, вызов процедуры либо преобразует данные, либо сообщает вызывающей программе о том, что данные были некорректны, и вызывающая программа обрабатывает обе эти ситуации, выводя либо результат, либо сообщение о некорректности
4. Глобальными переменными внутри функций и процедур пользоваться запрещено. Константами — можно.
5. Решения должны быть достаточно эффективными (например, избегать неоправданного копирования массивов)
6. Везде, где не указан фиксированный размер массива, ограничиться 20 элементами.
7. Данные вводятся со стандартного ввода и выводятся на стандартный вывод. Ввод и вывод для обеих программ должен быть идентичен.
Если соответствующего компилятора нет, можно воспользоваться многочисленными online-компиляторами, (например https://www.onlinegdb.com , их десятки)
Задачи
1. Написать процедуру, которая сортирует передаваемый ей массив строк (за $$~n log n$$ действий) по возрастанию количества английских гласных в них
2. Написать процедуру, которая преобразует время в строковом формате «чч:мм:сс» в три натуральных числа, также по результатам работы процедуры вызывающая её программа должна распознавать неправильный ввод.
3. Написать функцию, которая преобразует строку, содержащую натуральное число в восемнадцатеричном представлении, в число; также по результатам работы функции вызывающая её программа должна распознавать неправильный ввод.
  - Восемнацатеричные цифры: 0123456789ABCDEFGH
4. Написать функцию, которая подсчитывает количество вхождений каждой из десятичных цифр в передаваемом ей тексте. Функция должна возвращать соответствующую структуру данных.
5. Написать функцию, которая возвращает название товара, на который в сумме затрачено больше всего денег, обрабатывая массив карточек вида «название / цена за килограмм / вес». Количество названий фиксировано. Карточки реализованы в виде структур / записей.
6. Написать функцию, которой на вход подаются два целых числа: размер массива N и начальное значение M. Функция создаёт целочисленный массив, заполняет его по порядку числами от M до M+N, и возвращает его. Основная программа должна ввести N, M1 и M2, завести помощью функции два таких массива и вывести их поэлементную сумму — последовательность длины N.
  - В стандарт Pascal не входят динамические массивы. Вместо этого ужаса можно воспользоваться расширением языка.
7. Написать функцию, которая получает три параметра a, b, и c (любой коэффициент может быть нулевым) и решает квадратное уравнение $$ax^2+bx=c$$ . Возвращаемое значение функции должно содержать как сами корни, так и информацию об их количестве.
  - Программа должна обрабатывать все возможные ответы.
8. Реализовать тип данных «таблица» — массив указателей на строки. Написать процедуру, которая меняет местами строки с номерами i и k в таблице T.
9. Для типа данных «упорядоченный связный список натуральных чисел» (последовательность данных вида «значение / указатель на следующий элемент») реализовать ввод (конец ввода — 0) и вывод списка, а также процедуру добавления одного элемента в список, соблюдающую условие упорядоченности значений. Динамические/открытые массивы использовать нельзя.
10. Написать функцию, которая определяет наличие подстроки в строке в соответствии с алгоритмом Кнута-Морриса-Пратта.
(для сдающих курс ПП на кафедре) переслать свои решения в виде приложенных файлов по электронной почте <uneexlectures AT cs DOT msu DOT ru>:
- в поле «Subject» должно присутствовать словосочетание «Курс ПП»
- решение — это четыре приложенных файла:
  1. prog.pas — программа на Паскале
  2. prog.c — программа на Си
  3. input.txt — пример ввода
  4. output.txt — пример вывода

LecturesCMC/AL/2022_09_12 (последним исправлял пользователь FrBrGeorge 2022-09-12 14:35:47)