Различия между версиями 21 и 22
⇤ ← Версия 21 от 2021-09-27 10:31:39 →
Размер: 19174
Редактор: FrBrGeorge
Комментарий:
← Версия 22 от 2022-09-04 16:37:21 → ⇥
Размер: 19181
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 1: Строка 1:
= Императивное программирование = = Императивное программирование (2021) =

Императивное программирование (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
  • Проблемы читаемости в Си

Общий вывод

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

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

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

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

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

Бонус

Д/З

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

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

  • Требования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    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» должно присутствовать словосочетание «Курс ПП»

LecturesCMC/AL/2021_09_13 (последним исправлял пользователь FrBrGeorge 2022-09-04 16:37:21)