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

Запись прямого эфира

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

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

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

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

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

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

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

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

В Википедии:

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

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

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

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

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

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

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

• Человеко-ориентированное представление данных и инструкций
• Метки вместо адресов
• (всё остальное — «удобства»)
• Пример текста на языке ассемблера MIPS

  .data 0x10020000
          .word 1                         # Количество
  a:      .word -12345                    # Входные данные
  
  .data 0x10030000
          .word 1                         # количество
  res:    .word 0
  
  # Пример: Посчитать сумму цифр числа (в т. ч. отрицательного)
  .text
          lw      $t1, a
          bgez    $t1, ok
          sub     $t1, $zero, $t1
  ok:     move    $t2, $zero
          li      $t3, 10
  next:   blez    $t1, done
          divu    $t1, $t3
          mfhi    $t1
          addu    $t2, $t2, $t1
          mflo    $t1
          b       next
  done:   sw      $t2, res

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

  0x00400000  0x3c011002  lui $1,0x00001002     11        lw      $t1, a
  0x00400004  0x8c290004  lw $9,0x00000004($1)
  0x00400008  0x05210001  bgez $9,0x00000001    12        bgez    $t1, ok
  0x0040000c  0x00094822  sub $9,$0,$9          13        sub     $t1, $zero, $t1
  0x00400010  0x00005021  addu $10,$0,$0        14   ok:  move    $t2, $zero
  0x00400014  0x240b000a  addiu $11,$0,0x000000015        li      $t3, 10
  0x00400018  0x19200005  blez $9,0x00000005    16   next:        blez    $t1, done
  0x0040001c  0x012b001b  divu $9,$11           17        divu    $t1, $t3
  0x00400020  0x00004810  mfhi $9               18        mfhi    $t1
  0x00400024  0x01495021  addu $10,$10,$9       19        addu    $t2, $t2, $t1
  0x00400028  0x00004812  mflo $9               20        mflo    $t1
  0x0040002c  0x0401fffa  bgez $0,0xfffffffa    21        b       next
  0x00400030  0x3c011003  lui $1,0x00001003     22   done:        sw      $t2, res
  0x00400034  0xac2a0004  sw $10,0x00000004($1)

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

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

• Составные типы данных
• «Переменные» вместо меток (метафора «ящика с дыркой»)
• Функции/процедуры, содержащие «локальные переменные»
  • Передача параметра по имени / по соиспользованию — другой способ аллегирования

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

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

  • шашечки или ехать?

  • чудеса Фортрана

  • Фортран живее всех живых!

  • Работающий Алгол ∃ скорее в виде экспоната

• Бейсик и Кобол

• Си_(язык_программирования) и Паскаль

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

• Тысячи их!

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

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

• Объективный признак: несовпадение модели вычислений абстрактного (заданного ЯП) и фактического исполнителя

  • ⇒ фиксация модели вычислений на уровне семантики ЯП

  • (скорее всего) введение в синтаксис сложных структур данных и операций над ними

• Субъективные признаки: сокращение объёма и увеличение читаемости программы, ориентация на решение определённого класса прикладных задач

Си и Паскаль

• Си_(язык_программирования)

• Паскаль

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

Общее

• Процедурный ЯП начала 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. В задачах требуется написать функцию или процедуру, ввести данные, вызвать написанную подпрограмму и вывести результат. Можно вводить дополнительные процедуры и функции.

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

     • В Си «процедурой» будем называть void-функцию

  2. Вводом и выводом занимается только основная программа (в случае Си — main()

     • Условие «по результатам работы процедуры вызывающая её программа должна распознавать неправильный ввод» и ему подобные означают, что после вызова процедуры основная программа должна иметь возможность проверить, был ли ввод правильный или нет (и должна проверить, разумеется!)

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

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

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

  6. Данные вводятся со стандартного ввода, в комментариях внутри самой программы должен присутствовать как минимум один пример такого ввода в формате, пригодном для копипасты на вход запущенной программе. Формат ввода, если это не указано, произвольный.

     • Везде, где предполагается различное поведение программы, предоставить все возможные варианты ввода

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

• Задачи ( — простые):

  1. Написать процедуру, которая сортирует передаваемый ей массив строк за $$~n log n$$ действий

     • TODO массивы и контроль ввода?

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

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

     • TODO переделать в 18-ричную

  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. Написать функцию, которая определяет наличие подстроки в строке в соответствии с алгоритмом Кнута-Морриса-Пратта.

• (для сдающих курс ПП на кафедре) переслать свои решения в виде приложенных файлов по электронной почте мне, в поле «Subject» должно присутствовать словосочетание «Курс ПП»