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

Монтаж лекции / прямой эфир

Напоминание: требования к алгортимически полной системе (предположительно обязательные)

1. Соответствие операциональному определению алгоритма

2. Аллегируемые объекты

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

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

• Дисциплина аллегирования (как различать объекты)

  • имена, номера, связывание (например, операндом функции), …?

• Порядок составных действий (как гарантировать однозначность хода выполнения программы)

  • граф зависимости (⇒ последовательность, зависимость по данным/управлению и т. п.)
• Итерация
  • циклы, рекурсия, актуально конечные повторения, …

В Википедии:

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

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

• Хранение объектов как основной способ аллегирования, ссылки на них (имена, адреса, указатели и т. п.)

• Действие — это модификация (+создание/удаление) хранимого объекта (инструкция)

• Программа — это последовательность инструкций

• В зависимости от свойств объектов, последовательные части программы не выполняются или выполняются повторно.

NB: неизвестно, являются ли необходимыми даже такие нестрогие требования

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

«Машинный код»:

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

NB: всё остальное — регистры, типы адресации и стек, сопроцессоры, управление В/В и т. п. — «удобства»

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

• + Человеко-ориентированное представление данных и инструкций
• + Метки вместо адресов

NB: всё остальное — псевдоинструкции, макросы, директивы и т. п. — «удобства»

Пример текста на языке ассемблера 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
    

    • В чём подвох? (нажмите «Комментарии» в шапке страницы, чтобы прочитать спойлер): при передаче по именованию b актуально соответствует s[i] для разных i, так что массив s[] заполнится нулями

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

    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-х
• Очень простой синтаксис
• Глобальные и локальные переменные
• Типы данных:
  • Простые
  • Составные
  • Указатели
  • Отсутствие алгоритмически непрозрачных абстрактных типов данных
• …

Различия

Оба языка когда-то были равно популярны, так что доразвили в себе почти все недостающие инструменты. Однако зачастую в одном языке некоторое свойство является определяющим, а в другом — ощущается как побочное, а то и явно ненужное. В частности, многие абстракции есть в Паскале, но их нет в Си; в то же время абстракции паскаля как-то уж чересчур привязаны к 16-разрядности.

• Перечислимые типы:
  • Pascal: Перечеслимые типы, диапазоны и множества — максимально возможный уровень абстракции

  • C: Enum-ы, для поддержки дисциплины разработки

• Типизация:
  • Pascal: строгая
  • C: Приведение типов (в том числе ссылочных), привязка к размеру машинного слова
• Работа с памятью
  • C: Работа с адресами; адресная арифметика; непосредственное обращение к ОС для динамического выделения блоков памяти

  • Pascal: Абстрактный тип данных — указатель и New() / Dispose() в качестве интерфейса.

• Память как хранилище произвольных данных

  • C: Указатель = адрес (⇒ кастинг из void *); активное использование union для хранения разнотипных значений

  • Pascal: Почти нет, «записи с вариантами» не используются, кажется, никем
• Подпрограммы:
  • C: Функция = подпрограмма, передача параметров — это передача значений через стек или память
  • Pascal: Разделение процедур и функций, передача параметров по значению или по ссылке (абстракция)
• Файл
  • C: Библиотечный объект, предоставляемый ОС
  • Pascal: Встроенный тип данных (практически не используется ИРЛ)
• Арифметические операции
  • Pascal: Выражение = типизированная формула

  • C: Выражение = порядок вычисления атомарных инструкций; операция присваивания

• Синтаксис:
  • Pascal: Предельно ясный, читаемая БНФ

  • C: Контекстно-зависимая грамматика, кунштюки наподобие Duff device

• Генезис:

  • Pascal: Разнообразие диалектов, их несоответствие стандарту (в т. ч. не реализованный до конца Extended Pascal); считается устаревшим

  • C: Практически не теряет популярности, активно поддерживается GCC/Clang и развивается

    • Несколько блогов на тему: https://thephd.dev , https://people.kernel.org/kees/ , https://gustedt.wordpress.com

    • Стандарты

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

• Недостаточная высокоуровневость стандартного Pascal

  • Модель динамической памяти с указателями имеет более низкий уровень абстракции, чем модель статических данных ⇒ большую часть структур данных необходимо моделировать с их помощью (или вводить в расширение, как динамические массивы)

  • Отказ от «синтаксического сахара»
  • Разнобой и зависимость «расширений» от legacy
  • В частности, взлёт и падение Object Pascal (aka Delphy)
• Проблемы читаемости и надёжности в Си
  • Разрешительная модель доступа к памяти и все 33 удовольствия (stack smash, memory corruption, garbage dereference, …)

    • Pаscal формально не лучше!

  • Побочные эффекты (см., например, у А. В. Столярова тут и тут)

  • International_Obfuscated_C_Code_Contest

Общий вывод

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

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

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

• Насыщение синтаксиса ЯП актуальными приёмами программирования и актуальными встроенными типами данных (словари, итераторы, декораторы, асинхронность, исключения, неопределённые значения, статус ошибки и т. п.)

• Более безопасная модель памяти (в качестве единственной или в качестве альтернативы)

  • Memory safe VS Memory unsafe

• Включение удобных инструментов из других парадигм
• Частичная алгоритмизация периода компиляции в синтаксисе (а не внешним препроцессором, как в Си)

• Интроспекция / рефлексия

• Инкапсуляция (иерархия пространств имён) как базовый синтаксический инструмент (даже в отсутствие поддержки ООП)

Бонус

• NIM как «новый Паскаль» (пример на Learn X in Y minutes)

• ZIG как «новый Си»…примеры в документации

• …или Rust?

• …

Д/З

• Восстановить в памяти синтаксис Си и Паскаля.

• Выбрать один пример из перечисленных ниже, написать решение на двух языках — Си и Паскале

• Требования

  0. По возможности не писать «на Си как на Паскале» и наоборот, а пользоваться особенностями языка (это один из критериев оценки!)
     • Например, при работе со строками предпочтительно пользоваться строковыми функциями, а не реализовывать их вручную поэлементно

  1. Во всех задачах требуется написать программу, которая (1) введёт данные, (2) вызовет функцию или процедуру (если в задании их несколько, то все), (3) получит результат от функции или дождётся завершения процедуры, (4) выведет результат.

     • Можно вводить дополнительные процедуры и функции.

     • Обратите внимание на требования языка Pascal относительно отсутствия побочных эффектов в функциях.

     • В данном задании оно распространяется и на Си; в Си «процедурой» (в которой разрешены побочные эффекты) будем называть или void-функцию, или функцию, которая возвращает только код ошибки, а «функцией» — функцию без побочных эффектов, возвращающую значение заданного типа.

  2. Вводом и выводом занимается только основная программа (в случае Си — main(), в случае Паскаля — program). Если ввод/вывод сложный и/или структурированный — отдельные функции, вызываемые из основной программы.

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

  3. Глобальными переменными внутри функций и процедур пользоваться запрещено (передавайте модифицируемые параметры по ссылке или в виде указателя). Константами — можно.

  4. Решения должны быть достаточно эффективными (например, избегать неоправданного копирования массивов)

  5. Везде, где не указан фиксированный размер массива, ограничиться 100 элементами.

  6. Данные вводятся со стандартного ввода и выводятся на стандартный вывод. Ввод и вывод для обеих программ должен быть идентичен.

• Если соответствующего компилятора нет, можно воспользоваться многочисленными online-компиляторами, (например https://www.onlinegdb.com , их десятки)

Задачи

1. Написать процедуру, которая сортирует передаваемый ей массив строк (за $$~n log n$$ действий) по возрастанию количества английских гласных в них

2. Написать процедуру, которая преобразует время в строковом формате «чч:мм:сс» в три натуральных числа; предусмотреть возможность уведомить вызывающую программу о том, что такое преобразование невозможно

3. Написать функцию, которая преобразует строку, содержащую натуральное число в восемнадцатеричном представлении, в число; предусмотреть возможность уведомить вызывающую программу о том, что такое преобразование невозможно

   • Восемнацатеричные цифры: 0123456789ABCDEFGH

4. Написать процедуру, которая преобразует строку вида «Имя Отчество Фамилия» в «Фамилия, Имя Отчество.» (обратите внимание на то, что длина преобразованной строки больше длины исходной); предусмотреть возможность уведомить вызывающую программу о том, что такое преобразование невозможно

5. Написать функцию, которая подсчитывает количество вхождений каждой из десятичных цифр в передаваемом ей тексте. Функция должна возвращать соответствующую структуру данных.

6. Написать функцию, которая возвращает название товара, на который в сумме затрачено больше всего денег, обрабатывая массив карточек вида «название / цена за килограмм / вес». Количество названий фиксировано. Карточки реализованы в виде структур / записей.

7. Написать функцию, которой на вход подаются два целых числа: размер массива N и начальное значение M. Функция создаёт целочисленный массив, заполняет его по порядку числами от M до M+N, и возвращает его. Основная программа должна ввести N, M1 и M2, завести помощью функции два таких массива и вывести их поэлементную сумму — последовательность длины N.

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

8. Написать функцию, которая получает три параметра a, b, и c (любой коэффициент может быть нулевым) и решает квадратное уравнение $$ax^2+bx=c$$ . Возвращаемое значение функции должно содержать как сами корни, так и информацию об их количестве.

   • Программа должна обрабатывать все возможные варианты ответов (в частности, любые из коэффициентов могут быть нулевыми)

9. Реализовать тип данных «таблица» — массив указателей на строки. Написать процедуру, которая меняет местами строки с номерами i и k в таблице T.

10. Для типа данных «упорядоченный связный список натуральных чисел» (последовательность данных вида «значение / указатель на следующий элемент») реализовать ввод (конец ввода — 0) и вывод списка, а также процедуру добавления одного элемента в список, соблюдающую условие упорядоченности значений.

    • Динамические/открытые массивы Pascal использовать нельзя.

11. Реализовать динамически расширяемый тип данных TStack, хранящий целые числа. Написать процедуру push(стек, число), которая заносит число на вершину стека, и функцию pop(стек), которая снимает одно число с вершины стека. Опустошение стека можно не проверять. Переполнение стека и сокращение количества элементов в нём ниже 1/4 общего объёма должно обрабатываться геометрическим масштабированием. Основная программа и ввод должны вызывать push() и pop() в таком количестве, чтобы масштабирование сработало более одного раза (например, положить а затем сняь 2*max элементов). Подсказка: в Си с задачей масштабирования справляется функция realloc(), а в Паскале разрешается использовать динамические массивы и setLength().

12. Написать функцию, которая определяет наличие подстроки в строке в соответствии с алгоритмом Кнута-Морриса-Пратта.

(для сдающих курс ПП на кафедре) переслать свои решения в виде приложенных файлов по электронной почте uneexlecturescs.msu.ru):

• NB! в поле «Subject» должно присутствовать ключевое слово «ПП2024» — в противном случае робот письмо не примет!

• решение — это четыре приложенных файла:

  1. prog.pas — программа на Паскале

  2. prog.c — программа на Си

  3. input.txt — пример ввода

  4. output.txt — пример вывода

• Обе программы должны работать одинаково: при вводе данных из input.txt выводить результат, совпадающий с output.txt