Предыдущая серия:
У парадигм программирования имеются две важнейшие характеристики: характерен ли для них явный недетерминизм, и насколько "сильно" они поддерживают работу с состояниями.
Явный недетерминизм
Под недетерминизмом понимается ситуация, когда программа не полностью определена своей спецификацией (исходным кодом, условно говоря), т. е. в некоторой точке в процессе выполнения спецификация позволяет самой "физической" программе выбирать, что ей делать дальше (исходный текст программы не позволяет однозначно определить схему её работы). Такой выбор осуществляется как правило планировщиком, входящим в среду времени выполнения (runtime).
Недетерминизм будет явным (наблюдаемым), если пользователь будет видеть разные результаты работы программы, запускаемой с одними и теми же внутренними настройками. В большинстве случаев это крайне нежелательно. Речь идёт, конечно, прежде всего о параллельных программах, когда несколько частей кода могут выполняться одновременно, и нельзя по исходному тексту однозначно сказать, каким будет итог их работы. Это типичная ошибочная ситуация конкуренции (race condition) -- когда работа программы зависит от того, в каком порядке выполняются её части кода. Как правило, race condition проявляется в параллельных системах, когда например несколько процессов пытаются одновременно изменить состояние некоторого общего объекта, и результат зависит от промежутков времени между работой разных частей кода (race). Какой тред отработает последним, тот и зафиксирует итоговое состояние общего объекта, однако по исходному тексту это установить невозможно.
Но в ряде задач (например, моделирование ситуаций реального мира) требуется как раз парадигма с поддержкой явного недетерминизма, потому что именно он предоставляет нужный уровень выразительности для такого моделирования. Например, в Java, когда к именованным состояниям добавилась concurrency, проявился и явный недетерминизм, поэтому продуктивное параллельное программирование в ней затруднено.
Гораздо продуктивнее создавать параллельные программы в декларативной параллельной парадигме, когда все программы детерминистические (детерминированные).
Именованное состояние
Это вторая ключевая характеристика любой парадигмы. Состояние -- это способность запоминать информацию, или, более точно, способность хранить последовательность значений, растянутую во времени.
Выразительная сила этой характеристики находится под сильным влиянием содержащей её парадигмы. Например, в императивном программировании состояния -- это переменные, "именующие" значения.
Различаются три измерения выразительности:
-- является ли состояние безымянным (к нему нету доступа в коде по явному имени, идентификатору) или именованным;
-- детерминистическим или недетерминистическим;
-- последовательным или параллельным.
Всего получается восемь комбинаций, но опять-таки, не все они полезны. Подходящие варианты приведены на диаграмме. Все элементы по стрелкам отличаются ровно одной концепцией. Наличие параллелизма в парадигме показано толстой стрелкой.
Наименее выразительная комбинация концепций расположена на самом верху диаграммы (вертикальное измерение) -- это функциональное программирование. В нём применяется по сути состояние потока вычислений -- неименованное, детерминистическое и последовательное. Мы последовательно вызываем (комбинируем) чистые детерминированные функции, подавая им на вход неизменяемые значения.
Добавление именованного состояния даёт классическое императивное программирование: функции и переменные.
Добавление недетерминированности приводит к оригинальному случаю: так называемому программированию с охраняемыми командами. Это например язык Guarded Command Language Дейкстры. В нём классические императивные подходы (именованное состояние и последовательное выполнение) были дополнены охраняемыми командами -- недетерминированным циклом, чтобы избежать излишне подробной спецификации процесса работы алгоритма, что ослабило требования к вычислительной модели.
По правой ветке, начиная с корня (функциональное программирование), добавление параллельности приводит к парадигме декларативного параллельного программирования: несмотря на возможность одновременного выполнения частей программы, вычисления по-прежнему остаются детерминированными (например за счёт использования автоматически синхронизируемых неименованных ячеек с промежуточными значениями). Гарантированно независимые потоки вычислений с помощью чистых функций, хоть и подразумевающие последовательное исполнение, вполне можно автоматически распараллелить.
Добавление недетерминированности приводит к параллельному логическому программированию, когда используются "объединители" потоков вычислений: неименованные, недетерминированные и параллельные.
Добавление именованных портов (или ячеек), соответственно, даёт возможность обмена сообщениями и разделяемые состояния (именованные, недетерминированные и параллельные).
Баланс в вашем проекте
Недетерминизм важен во всех классических системах, где взаимодействие происходит в реальном времени (например, клиент-серверные системы). Именованные состояния важны для обеспечения модульности проекта.
Явный недетерминизм и именованные состояния -- две крайние ситуации, между которыми важно найти баланс. С одной стороны, надо выбрать достаточно выразительную парадигму; с другой стороны, излишняя выразительность тут может и навредить, оказаться чрезмерной. Каждая из этих двух концепций сама по себе иногда реально необходима, однако её следует оставить в покое, если в этом нет явной необходимости.
Главный смысл в том, чтобы научиться выбирать парадигму с оптимальным множеством концепций, точнее всего подходящим вашему конкретному проекту. Если концепций, которые попадут в цель вашего проекта, будет слишком мало, усложнится реализация системы (programming in small). Если таких концепций будет слишком много, то сложным станет её проектирование (programming in large).
Данный цикл статей посвящён знакомству с именно таким подходом к программированию, на основе разбираемых тут концепций и парадигм, пониманию фундаментальных вещей в этой теме. На конкретных прикладных курсах по парадигмам мы будем, во-первых, изучать, как подбирать такое оптимальное множество концепций и структурирующих их парадигм под ваши прикладные задачи, и во-вторых, изучать конкретные программистские техники programming in small и programming in large, порождённые данным научным подходом.
В следующей заметке разберём, как учёные computer science открывают новые концепции программирования.
продолжение следует
Высшая школа программирования Сергея Бобровского
