2008-12-15

Парадигмы программирования

Со всем спектром придуманных на сегодня парадигм программирования можно ознакомиться в Википедии. В этой статье я хотел остановиться на тех из них, которые имеют значительное влияние на современные языки и программные среды, и о которых, соответственно, обязательно иметь представление любому разработчику. Обязательно потому, что за каждой из парадигм стоит огромная работа по поиску путей решения типичных проблем, возникающих при программировании "интуитивным"[1] путем, и не учитывать этот опыт — значит наступать на те же грабли в который раз и заново придумывать велосипед. Разумеется, многое из написанного в статье общеизвестно, но несмотря на это дискуссии на эти (базовые) темы возникают вновь и вновь. Эта статья — попытка упорядочить для себя общую картину, а также установить точку отсчета, к которой можно было бы привязываться впоследствии.

Основные парадигмы


  • Структурное программирование
    Эта парадигма представляет в основном теоретическое значение (хотя и является неотъемлемой частью практически всех современных языков). По сути, это был первый сдвиг парадигмы в программировании, когда после появления первых абстрактных и высокоуровневых по сравнению с ассемблером языков, пришло осознание, что разрабатывать на них также нужно на более высоком уровне абстракции, чем на ассемблере: в терминах условных выражений и циклов, а не передачи управления между метками. И, что не удивительно, был достигнут консенсус, неоднократно с тех пор подтвержденный практикой, что при использовании более абстрактных конструкций программирование становится более доступным, а программы — расширяемыми, поддерживаемыми,— и, в целом, можно решать намного более сложные задачи.
    Эта парадигма основывается на работах Дейкстры, Хоара, Вирта и других, которые доказали, что любое вычисление можно выразить через 3 базовые операции:

    • последовательное выполнение;
    • условный переход;
    • цикл с условием.

    Девиз структурного программирования — "GOTO является вредным".


  • Объектно-ориентированное программирование
    Это самая распространенная на сегодняшний день парадигма, которая является развитием идей структурного программирования. Она подается как реализация "естественного" взгляда на окружающий мир, в котором всё является объектом. Она, как известно, покоится на 3-х китах:

    • инкапсуляция;
    • наследование;
    • полиморфизм.

    Однако, учитывая распространение, которое она приобрела, а также, наверное, тот факт, что понятие "естественного" и строго математического определения немного отличаются, каждый ОО-язык понимает эти 3 концепции по-своему (во всяком случае, последние две), и каждое такое понимание имеет право на жизнь и применение.
    Наследование включает, условно говоря, наследование "свойств" и "функциональности".
    Для свойств оно может быть основано на классе (от абстрактного к конкретному) — см. C++, Java,— или же на прототипе (от конкретного к абстрактному) — JavaScript.
    Наследование же функциональности и полиморфизм — это 2 стороны одной медали. В Lisp подходе, основанном на родовых функциях эти 2 концепции унифицируются в рамках одной абстракции. Наследование функциональности может пониматься по-разному: как наследование реализации или как наследование интерфейса (см. http://weblog.raganwald.com/2008/04/is-strictly-equivalent-to.html). С другой стороны спектра находится обобщение подхода родовых функций — мультиметоды Clojure — диспетчиризация не только по типу аргументов, а и по любому предикату от аргументов.

    Самой распространненой, однако не единственной рализацией ОО-модели является придуманная в SmallTalk и перенятая в той или иной степени C++, Java, Python и другими основными современнымя языками модель передачи сообщений (диспетчиризация метода по типу первого аргумента, который является объектом, принимающим сообщение). Этот подход я бы еще назвал субъектно-ориентированным программированием, потому что в нем неявно считается, что каждый объект совершает действия, т.е. становится субъектом. В зависимости от динамичности языка в нем может поддерживаться утиная типизация (Duck typing), согласно которой для вызова метода для объекта этот объект должен иметь метод с такой сигнатурой, при этом его тип может не проверяться (динамическая передача сообщений).


  • Функциональное программирование
    Эта парадигма имеет свои корни в Лямбда-исчислении Черча и ее первой реализации — оригинальному Lisp'у — больше лет, чем первому структурному языку Algol-60.
    Сейчас функциональная парадигма (в форме декларативного программирования) противопоставляется императивному подходу. Ее основа — это функция в математическом понимании (преобразование входных данных), а не функция как процедура, меняющая состяние мира.
    Концепциями функциональной парадигмы являются:

    • программирование без побочных эффектов (ссылочная прозрачность)
    • применение функций высших порядков (итерации с помощью map и рекурсии, карринг, композиция...)

    Основным направлением в ФП сейчас направлением являются т.н. "чисто" функциональные языки, которые реализуют такие концепции, как:

    • ленивые вычисления
    • строгая типизация и вывод типов
    • сопоставление с образцом (pattern matching)

    Это Haskell, ML (Ocaml, SML), Scala и Qi.
    Однако, и динамические (не поддерживающие строгую типизацию) функциональные языки (как правило, имеющие Lisp-основу) также существуют и активно развиваются: Scheme, Erlang, Clojure.


  • Мета-программирование
    Основными идеями этой парадигмы являются возможности расширения базового языка превоклассными (такими, которые смогут использоваться наравне со встроенными) конструкциями, а также всегда программирование на уровне адекватном логике решаемой задачи и прдеметной области. Мета-программирование поддерживается методологией проектирования и разработки снизу-вверх, при которой сложная система разбивается на уровни, каждый из которых соответствует определенным независимым горизонтельным задачам: от уровня утилит-расширений языка вплоть до уровня доменно-специфического языка для моделирования той или иной прикладной области,— и реализуется постепенно уровень за уровнем. При этом на каждом уровне сложность задачи не увеличивается, поскольку примитивами на нем являются абстракции, выработанные на более низких уровнях.
    Таким образом мета-рограммирование порождает концепцию DSL — доменно специфических языков, создаваемых для той или иной предметной области (языко-ориентированное программирование), одновременно и использующими возможности хост-языка (все его базовые подсистемы, такие как: сбор мусора, математические библиотеки и т.д.), и являющимися адаптированными в синтаксисе и семантике к той сфере, для которой они реализованы.
    К мета-программным возможностям можно отнести те или иные особенности многих языков. Например, в C это перпроцессор, в C++ — в каком-то смысле, перегрузка операторов, а также применение шаблонов для абстракции на уровне системы типов. В Python — это механизм декораторов, позволяющий динамически дополнять реализацию методов. Попытки добавить определенные макросистемы делаются во многих языках. Это, например, MetaLua, а также модули andand, rewrite, rubymacros и др. в Ruby и т.д. Безусловно, базовым языком для парадигмы мета-программирования является Lisp, в котором и зародились (и продолжают зарождатся) ее концепции.


  • Скриптинговые языки
    Можно сказать, что это недопарадигма, поскольку она не основывается на какие-то фундаментальные исследования или принципы. Основная идея тут — максимальное удобство и простота ad-hoc реализации опеределенного класса решений на определенной архитектуре (иными словами, практичность). Это обуславливает такие характеристики языка, как:

    • динамичность
    • интерпретируемость
    • привязка к хост-системе

    В рамках этой парадигмы получили свое рождение такие языки, как: Perl (и PHP), Python, Ruby, Tcl, Lua, Basic, JavaScipt, Shell-языки (Bash, PowerShell, ActionScript, AppleScript, ...), некоторые из которых впоследствии переросли ее и перешли, как правило, в категорию объектно-ориентированных языков.


  • Программирование, ориентированное на параллелизм
    Это самая новая парадигма и, пожалуй, еще не до конца сформировавшаяся, поскольку пока что нет косенсуса на счет того, какая из предложенных концепций станет общепризнанной (если это вообще произойдет). А это и развитие архитектуры, подобной MapReduce Google, и асинхронная передача сообщений между процессами (полностью без общего состояния) Erlang'а, и использование программной транзакционной памяти — обобщения концепции транзакции в базах данных на любое вычисление (Haskell, Clojure). Основой для выделение этого подхода в отдельную парадигму стало понимание того, что использование блоков для синхронизации параллельных вычислений не является масштабируемым и поддерживаемым решением при реализации многопоточности (в том числе см. http://jcp.org/en/jsr/detail?id=166). Можно провести параллели между этой парадигмой и процедурной: проблема с использованием блоков аналогична проблеме goto. Пока что ясно одно: эта парадигма станет развитием функционального подхода с его краеугольными камнями немутируемых структур данных и ссылочной целостности.


Дуализм типизации


Несмотря на распространенное мнение поддержка языком программирования того или иного вида типизации является ортогональным к парадигме, которую этот язык реализует. Более того, вопрос типизации можно рассматривать в 2-х аспектах:

  1. Слабая vs сильная. Это различие скорее количественное, чем качественное. "Абсолютно" сильная типизация (как это реализовано в Haskell'е) не позволяет никакого приведения типов (во время исполнения). Более слабые системы типизации дают такую возможность до определенной степени. Например, многие источники называют С слабо-типизированным языком, поскольку он позволяет выполнять неявное приведение типов, а также явное приведение указателей (что не дает возможность проверить тип на этапе компиляции).
  2. Статическая (проверка типов во время компиляции) vs динамическая (проверка на этапе исполнения). Суть динамической типизации можно изложить во фразе из Common Lisp: "у переменных нет типов, типы есть только у значений". Это не значит, что типы не проверяются (как это происходит в нетипизированных языках, тких как Assembler и Forth, но они проверяются при выполнении операций над конкретными значениями во время исполнения программы. Поэтому в динамическом с сильной типизацией Lisp'е не может возникнуть ошибки сегментации памяти при попытке использовать значение не того типа, которая часто встречается в статическом со слабой типизацией С. По мнению идеологов статической типизации, благодаря ее использованию можно исправить большой класс ошибок в программе, связанных с использованием несоответствующих типов, с помощью явного указания типов и их проверки компилятором. А также увеличить быстродействие программы благодаря отсутствию необходимости проверки типов во время исполнения. В то же время написание таких программ является более длительным и сложным процессом (языки со строгой статической типизацией еще называют bondage & discipline languages), и что самое неприятное, их становится очень трудно менять впоследствии. Поэтому, наверное, ни тот ни другой подход не являются предпочтительными в общем случае и могут быть оба использованы в зависимости от конкретной задачи и преференций разработчиков. В идеале, должны появиться языки, которые будут позволять задействовать обе системы параллельно или на выбор. Например, в Common Lisp есть возможность объявлять типы для выражений и переменных для того, чтобы отключить их проверку во время исполнения — это решает проблему скорости для динамического языка, однако не адресует вопрос статической проверки типов при компиляции.

Ссылки на другие интересные парадигмы


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

  • Программирование на основе стека
    Языки на основе стека — это очень простые языки, примитивные операции которых построенны вокруг манипуляции этой структурой данных. Такой подход, в основном, избавляет от необходимости использования переменных для ссылок на значения (point-free programming). Кроме того, синтаксис таких языков становится весьма унифицированным (как правило, используется постфиксная нотация), что дает возможность задействовать мета-программирование.
    Языками на основе стека являются PostScript и Forth. Кроме того, большинство виртуальных машин современных языков, такие как JVM, .Net CLR, Perl Parrot и т.д. также являются языками основанными на стеке.

  • Логическое программирование
    Это реализация в языке модели формальной логики. При этом результаты работы программы часто являются побочными эффектами логического вывода. Интерес таких языков в том, что они предлагают совершенно иную модель вычислений, чем фон Неймановская архитектура или Лямбда-исчесление Черча, соответственно некоторые задачи, например, связанные с праллельными вычислениями или имеющие четкую математическую модель, можно решать с применением совсем других подходов. В рамках этой парадигмы получили развитие такие концепции, как бэктрекинг и сравнение с образцом (pattern matching).

  • Программирование в массивах
    Это направление было введено в APL и продолжает развиваться в его последователях J/K/Q, также его реализации присутствуют в MatLab'е и Mathematica. Базовая идея заключается в том, чтобы обобщить скалярные операции на векторные типы данных. Кроме того в этих языках, как правило поддерживается point-free programming. Их удобно использовать для выполнения сложных математических вычислений и они представляют скорее исследовательский интерес. Интересным примером промышленной системы с использованием таких языков является БД kdb+.


P.S



В заключение хотелось бы упомянуть еще одну парадигму или, скорее, анти-парадигму: эзотерические языки (эзоязыки). Эту концепцию также называют Turing tarpit (бочка дегтя Тюринга), потому что эзоязыки показывают, что можно легко создать Тюринг-полный язык, на котором будет совершенно невозможно программировать. По-моему, это хороший урок для тех, кто утверждает, что язык программирования не имеет значения. Да, на любом Тюринг-полном языке можно реализовать любой алгоритм и любую программу, но поробуйте сделать это на brainfuck'е, использующем только 8 допустимых символов и 8 операций, на котором "Hello world" выглядит так:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
, или на Whitespace, для которого весь набор значащих символов составляют пробел, табуляция и новая строка.


[1] Как верно замечено в книге "Основы практики на пианино" в сложных областях деятельности существует настолько много методов решения задач, что даже не смотря на неплохие способности человеческого мозга навскидку выделять более эффектиные из них (которые мы называем "интуитивными"), даже среди этого подмножества есть группа методов, которые являются на порядки эффективнее других, но для того, чтобы их найти, простой интуиции не достаточно.

11 comments:

Native-born citizen said...

Тема чрезвычайно интересная, но, мне кажется, есть несколько концептуальных неточностей. В частности в разделе «Основные парадигмы» имеется логическая ошибка, называемая подменой основания деления: делить языки имеет смысл, например, на функциональные и императивные, а не на функциональные и объектно-ориентированные. Также несправедливо, на мой взгляд, на одном уровне поставлены мета-программирование и структурное программирование. Кроме того, достойны упоминания процедурный и модульный подход, аспектно-ориентированное программирование, было бы неплохо как-то вспомнить рефлексию. Шаблонную декомпозицию или абстракцию алгоритмов можно выделить в самостоятельную парадигму, а не ограничиваться упоминанием в мета-программировании. И, опять же, параллелизм и скриптовые языки – это скорее особенности предметной области чем парадигма. Почему-то совершенно забыты языки с динамической типизацией (имеется в виду определение типа во время выполнения, а не динамический контроль типов).

Vsevolod Dyomkin said...

Re: Native-born citizen
На счет процедурного и модульного подхода, мне кажется, что они укладываются в структурное программирование (во всяком случае, так нам его объясняли в вузе :)

Могу сказать, что при составлении перечня я руководствовался прежде всего собственным опытом и собственной оценкой значимости того или иного течения (поэтому, разумеется, он получился субъективным). Все же считаю, что каждая из "основных" парадигм имеет право называться таковой в данных условиях, поскольку есть достаточно значимые и самобытные языки, которые начинают свою концепцию (официальную или не официальную :) с фразы "<name> — это <парадигма>-ориентированный язык ..."
Java — это объектно-ориентированный язык, Perl — это скриптинговый язык, Common Lisp — это язык для мета-программирования, а Erlang — язык для параллельно-ориентированного программирования.

Но, в целом, конечно, согласен, что перечисленные парадигмы не являются взаимоисключающими и не составляют полного множества. По каким-то аспектам они могут пересекаться, а по каким-то вообще лежать в ортогональных плоскостях. Существуют мультипарадигменные языки. Поэтому, конечно, нельзя говорить, что такая классификация является точной...

Anonymous said...

замечательный пост! лучшее что я прочёл за последние месяцы

Vsevolod Dyomkin said...

2 katkov: спасибо :)

Anton S. Kraievoy said...

или на Whitespace, для которого весь набор значащих символов составляют пробел, табуляция и новая строка.

Я уже полез под этот параграф читать исходник хелловорлда на Whitespace...
Спасибо, интересная подборочка.

Unknown said...

tarpit - это не бочка с дегтем, а смоляное болото, в котором утопали динозавры. Метафора придумана Бруксом в книге "Мифический человеко-месяц".

Vsevolod Dyomkin said...

Юрий, я, в общем-то, не пытался дать дословный перевод. По моему мнению, выражение бочка дегтя несет большую смысловую нагрузку, чем смоляное болото, поскольку с одной стороны, в ней точно также можно увязнуть и утонуть (деготь = смола), а с другой -- это ассоциация с ложкой дегтя, которая портит бочку меда.
Да и не трудно понять, что это была шутка :)

Unknown said...

В оригинале смысл такой, что в экзотических языках можно увязнуть. Значения грязи или испорченности там нет. Поэтому ваш перевод не точен.

Vsevolod Dyomkin said...

В данном случае имеет место не только мой перевод, но и мое понимание. Для меня -- сторонника динамических языков -- это ложка дегтя. И я не единственный, кто придерживается такой трактовки. Связанное с этим "bondage & discipline" тоже в данном случае несет негативный подтекст.
Но, как вы, наверное, знаете, в этом споре статического и динамического подходов нет правых, каждый остается при своем мнении (потому что потребности разные)

Unknown said...

bondage & discipline - вообще из лексикона садомазо :-) Даже не знаю, как точно перевести.

Но точно передает ощущения любителя динамических языков, который вынужден писать на каком-нибудь C++.

Vsevolod Dyomkin said...

У меня, кстати, все смешалось, когда я вам отвечал: эзоязыки с функциональными. В данном случае, не так важно болото или бочка, все равно это особого значения не имеет.
А вот на счет bondage&discipline -- да, в одно время ничего меня так не доставало, как С++-сное приведение типов (cast).