Парадигмы Томаса Куна

В восьмидесятых  Пер Мартин-лоф создал теорию интуиционного  типа(также называемую конструктивной). В ней функциональное программирование получило конструктивное доказательство того, что ранее было известно как зависимый тип. Это дало мощный толчок к развитию диалогового доказательства теорем и к последующему созданию множества функциональных языков. Haskell был создан в конце восьмидесятых в попытке соединить множество идей, полученных в ходе исследования функционального программирования.

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

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

Функции высших порядков позволяют использовать карринг  — преобразование функции от пары аргументов в функцию, берущую свои аргументы по одному. Это преобразование получило свое название в честь Х. Карри. 

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

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

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

Если нет  никакой зависимости по данным между двумя чистыми функциями, то порядок их вычисления можно поменять или распараллелить (говоря иначе вычисление чистых функций удовлетворяет принципам thread-safe)

Если весь язык не допускает побочных эффектов, то можно использовать любую политику вычисления. Это предоставляет свободу компилятору комбинировать и реорганизовывать вычисление выражений в программе (например, исключить древовидные структуры).

До тех  пор пока большинство компиляторов императивных языков программирования распознают чистые функции и удаляют общие подвыражения для вызовов чистых функций, они не смогут делать это всегда для предварительно скомпилированных библиотек, которые, как правило, не предоставляют эту информацию. Некоторые компиляторы, такие как gcc, в целях оптимизации предоставляют программисту ключевые слова для обозначения чистых функций. Fortran 95 позволяет обозначать функции как «pure» (чистые).

В функциональных языках цикл обычно реализуется в  виде рекурсии. Строго говоря, в функциональной парадигме программирования нет такого понятия как цикл. Рекурсивные функции вызывают сами себя, позволяя операции выполняться снова и снова. Для использования рекурсии может потребоваться большой стек, но этого можно избежать в случае хвостовой рекурсии. Хвостовая рекурсия может быть распознана и оптимизирована компилятором в код, получаемый после компиляции аналогичной итерации в императивном языке программирования. Стандарты языка Scheme требуют распознавать и оптимизировать хвостовую рекурсию. Оптимизировать хвостовую рекурсию можно путём преобразования программы в стиле использования продолжений при её компиляции, как один из способов.

Рекурсивные функции можно обобщить с помощью  функций высших порядков, используя, например, катаморфизм и анаморфизм (или «свертка» и «развертка»). Функции такого рода играют роль такого понятия как цикл в императивных языках программирования. 

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

print length([2+1, 3*2, 1/0, 5-4])

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

Как правило  нестрогий подход реализуется в виде редукции графа. Нестрогое вычисление используется по умолчанию в нескольких чисто функциональных языках, в том числе Miranda, Clean и Haskell.

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

В языке C указатели  на функцию могут быть использованы для получения эффекта функций  высшего порядка. Функции высшего  порядка и отложенная списковая структура реализованы в библиотеках С++. В языке C# версии 3.0 и выше можно использовать λ-функции для написания программы в функциональном стиле. В сложных языках, типа Алгол-68, имеющиеся средства метапрограммирования (фактически — дополнения языка новыми конструкциями) позволяют создать специфичные для функционального стиля объекты данных и программные конструкции, после чего можно писать функциональные программы с их использованием.

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

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

Логическое  программирование

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

Самым известным  языком логического программирования является Prolog.

Первым языкомлогического  программирования был язык Planner, в котором была заложена возможность автоматического вывода результата из данных и заданных правил перебора вариантов (совокупность которых называлась планом). Planner использовался для того, чтобы понизить требования к вычислительным ресурсам (с помощью метода backtracking) и обеспечить возможность вывода фактов, без активного использования стека. Затем был разработан язык Prolog, который не требовал плана перебора вариантов и был, в этом смысле, упрощением языка Planner.

От языка Planner также произошли логические языки программирования QA-4, Popler, Conniver и QLISP. Языки программирования Mercury, Visual Prolog, Oz и Fril произошли уже от языка Prolog. На базе языка Planner было разработано также несколько альтернативных языков логического программирования, не основанных на методе backtracking, например, Ether.

Объектно-ориентированное  программирование

Объе́ктно-ориенти́рованное программи́рование (ООП) — парадигма  программирования, в которой основными  концепциями являются понятия объектов и классов (либо, в менее известном варианте языков с прототипированием, — прототипов).

Класс —  это тип, описывающий устройство объектов. Понятие «класс» подразумевает  некоторое поведение и способ представления. Понятие «объект» подразумевает  нечто, что обладает определённым поведением и способом представления. Говорят, что объект — это экземпляр класса. Класс можно сравнить с чертежом, согласно которому создаются объекты. Обычно классы разрабатывают таким образом, чтобы их объекты соответствовали объектам предметной области.

Класс является описываемой на языке терминологии (пространства имён) исходного кода моделью ещё не существующей сущности, т.н. объекта.

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

Прототип  — это объект-образец, по образу и подобию которого создаются  другие объекты.

Объектное и объектно-ориентированное программирование (ООП) возникло в результате развития идеологии процедурного программирования, где данные и подпрограммы (процедуры, функции) их обработки формально не связаны. Кроме того, в современном объектно-ориентированном программировании часто большое значение имеют понятия события (так называемое событийно-ориентированное программирование) и компонента (компонентное программирование).

Первым языком программирования, в котором были предложены принципы объектной ориентированности, была Симула. В момент своего появления (в 1967 году), этот язык программирования предложил поистине революционные идеи: объекты, классы, виртуальные методы и др., однако это всё не было воспринято современниками как нечто грандиозное. Тем не менее, большинство концепций были развиты Аланом Кэйем и Дэном Ингаллсом в языке Smalltalk. Именно он стал первым широко распространённым объектно-ориентированным языком программирования.

В настоящее  время количество прикладных языков программирования (список языков), реализующих  объектно-ориентированную парадигму, является наибольшим по отношению к другим парадигмам. В области системного программирования до сих пор применяется парадигма процедурного программирования, и общепринятым языком программирования является язык C. Хотя при взаимодействии системного и прикладного уровней операционных систем заметное влияние стали оказывать языки объектно-ориентированного программирования. Например, одной из наиболее распространенных библиотек мультиплатформенного программирования является объектно-ориентированная библиотека Qt, написанная на языке C++.

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

Наличие инкапсуляции достаточно для объектности языка  программирования, но ещё не означает его объектной ориентированности — для этого требуется наличие наследования.

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

Язык Self, соблюдая многие исходные положения объектно-ориентированного программирования, ввёл альтернативное классам понятие прототипа, положив  начало прототипному программированию, считающемуся подвидом объектного.

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