Кратко — ключевые идеи и как они влияют на две задачи: обработка списков и конкурентное программирование.
Общие принципы
- Императивная парадигма: программирование через изменение состояния (переменные, массивы), последовательные команды. Типичные языки: C, Java, Python.
- Функциональная: вычисления как применение функций, предпочтение неизменяемости и чистым функциям, сильная роль рекурсии и высших функций. Типичные: Haskell, OCaml, (частично) Erlang.
- Логическая: программа — набор логических отношений/предикатов; исполнение через поиск/унификацию и вывод. Типичные: Prolog, CLP языки.
1) Обработка списков — что и как меняется
Императивно
- Подход: мутируемые структуры и циклы. Часто реализуют in-place алгоритмы (меньше аллокаций).
- Пример: инвертирование массива — цикл со свапами двух концов (временная сложность \((\)время\() = O(n)\), память $O(1)$).
- map/filter: пишем явный цикл, обновляем результирующий массив или список по месту.
Функционально
- Подход: списки неизменяемы; используют рекурсию, хвостовую рекурсию, высшие функции (map, fold, filter).
- Пример: сумма списка через fold: $\text{foldl}(\lambda accx.acc+x)0xs$. Параллелизация: чистые функции позволяют легко распараллеливать map/fold (разбить на подпоследовательности).
- Алгоритмы часто более декларативны; некоторые in-place оптимизации невозможны без специальных механизмов (STM, уникальность).
Логически
- Подход: описывают отношения над списками (append, member, reverse) и получают ответы через поиск/унификацию. Можно как проверять свойства, так и генерировать варианты.
- Пример (Prolog-стиль):
append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).
reverse([], []).
reverse([X|Xs], R) :- reverse(Xs, Rx), append(Rx, [X], R).
- Особенность: алгоритм выражается в виде правил; поиск может давать все возможные решения; сложность зависит от порядка правил и стратегии поиска (обычно backtracking).
Сравнение по метрикам
- Память: императив — минимальная при in-place; функциональный — часто больше (создаёт новые списки) но подлежит оптимизациям (sharing, lazy evaluation); логический — может требовать стека для поиска и хранения частичных решений.
- Параллелизация: функциональный — самая простая модель для автоматической параллелизации; императивный — возможна, но требует синхронизации; логический — параллелизм возможен через независимый поиск или конкурентные логические языки, но сложнее контролировать.
2) Конкурентное программирование — подходы и последствия
Императивно
- Модель: потоки/процессы, общая память, синхронизаторы (мьютексы, семафоры, условные переменные). Код явно управляет состоянием и синхронизацией.
- Проблемы: гонки, дедлоки, сложности в валидации корректности.
- Пример: несколько потоков обновляют общий массив; требуется блокировка для атомарности операций.
Функционально
- Модель: предпочитают обмен сообщениями и иммутабельность (actors, message-passing — Erlang), или STM (software transactional memory) для управляемых изменяемых структур.
- Преимущества: отсутствие общих изменяемых данных снижает число гонок; чистые функции безопасны для параллельного выполнения.
- Пример: параллельный map — для списка длины $n$ разбить на части, запустить задачи-фьючерсы и собрать результаты; отсутствие блокировок при чистых функциях.
- Минусы: при необходимости общей изменяемой структуры приходится вводить транзакции или специализированные примитивы.
Логически
- Модель: в чистом Prolog конкуренция отсутствует; в конкурентных логических языках (Concurrent Prolog, Parlog, Oz/Mozart) используются параллельный поиск, dataflow-переменные, или конкурентные ограничения. Часто применяются правила с «committed choice» (гардированные правила).
- Преимущества: естественная модель выражения синхронизации через логические переменные (ожидание привязки — implicit synchronization), декларативное управление зависимостями.
- Пример: несколько процессов работают с общими dataflow-переменными: процесс блокируется пока переменная не получит значение — синхронизация без явных блокировок.
- Минусы: сложнее предсказать порядок выполнения и влияние на производительность; не все логические языки имеют зрелые средства для масштабируемой конкуренции.
Короткое сведение (практическая рекомендация)
- Если нужен контроль над памятью и простая производительность — императивный подход с явной синхронизацией.
- Если важна параллельная обработка данных и простота рассуждений о корректности — функциональный (чистые функции, actors, STM).
- Если задача описывается как набор логических ограничений или генераций решений — логическая парадигма даёт выразительные декларативные средства; для конкурентности выбирают специализированные конкурентные логические/constraint языки.
Если нужно — могу привести минимальные код‑фрагменты (императивный, функциональный, Prolog) для конкретной операции (map/reverse/sum) и для параллельного map.