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

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

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

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

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

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

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

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

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

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

В Википедии:

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

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

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

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

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

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

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

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

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

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

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

  • уже не связывание ли это из функциональной парадигмы?

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

• Фортран и Алгол: шашечки или ехать?

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

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

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

• Тысячи их!

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

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

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

  • ⇒ кросс-платформенность на уровне семантики ЯП

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

Си и Паскаль

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

Общее

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

Различия

• P: Перечеслимые типы, диапазоны и множества
• P: Указатели
• P: Разделение процедур и функций, передача параметров по ссылке
• P: Файл как тип данных
• P: …
• C: Присваивание и запятая как операции
• C: Приведение типов (особенно ссылочных)
• C: Адресная арифметика как реализация понятия «массив»
• C: Аппаратно-ориентированные возможности (+ packed array в Паскале)

• C: … (например, Duff device)

Общий вывод: сильное отличие в уровне абстракции

• Недостаточная высокоуровневость стандартного Pascal
  • Модель памяти и указатели
  • Отказ от «синтаксического сахара»
• Проблемы читаемости Си
  • Побочные эффекты

  • International_Obfuscated_C_Code_Contest

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

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

• Более безопасная модель памяти
• Включение удобных инструментов из других парадигм
• Инкапсуляция как базовый инструмент

Бонус

• NIM как новый Паскаль

• ZIG как новый Си

Д/З

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

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

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

  • Ввод и вывод можно делать в основной программе или в отдельных подпрограммах, но нельзя — в самой функции или процедуре, реализующей решение

  • Конкретная реализация алгоритма — на ваше усмотрение. Условие: глобальными переменными внутри функций и процедур пользоваться запрещено.

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

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

• Задачи:

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

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

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

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

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

  6. Написать процедуру, которая принимает (необязательно единственный) параметр — натуральное число N, а затем создаёт и заполняет числами от 1 до N целочисленный массив размера N. (В стандарт Pascal не входят динамические массивы, можно воспользоваться расширением).

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

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

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

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

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