Функциональное программирование (LISP). Логическое программирование (Prolog)

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

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

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

 

Сформулированная Джоном Мак-Карти (1958) концепция символьной обработки информации компьютером восходит к идеям Черча и других математиков, известным как лямбда-исчисление с конца 20-х годов XX века.

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

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

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

Дополнительное отличие от императивных языков программирования заключается в декларативности описаний функций. Тексты программ на функциональных языках программирования описывают «как решить задачу», но не предписывают последовательность действий для решения.

Первым функциональным языком стал Лисп. Он был предложен Джоном Мак-Карти в качестве средства исследования границ применимости компьютеров, в частности, методом решения задач искусственного интеллекта.

Вариант данного языка широко используется в системе автоматизированного проектирования AutoCAD и называется AutoLISP

Основные преимущества функциональных языков:

Краткость и простота

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

quickSort ([]) = []
quickSort ([h : t]) = quickSort (n | n   t, n <= h) + [h] + quickSort (n | n   t, n > h)

Строгая типизация

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

Модульность

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

Функции - объекты вычисления

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

Чистота (нет побочных эффектов)

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

Отложенные (ленивые) вычисления

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

LISP

Тексты программ на функциональных языках программирования описывают «как решить задачу», но не предписывают последовательность действий для решения. 

Первым спроектированным функциональным языком стал Лисп. 

Лисп / LISP (LISt Processing language - «язык обработки списков») -  семейство ЯП, программы и данные в которых представляются системой вложенных списков.

Лисп является вторым в истории (после Фортрана) используемым по сей день высокоуровневым языком программирования. 

http://ru.wikipedia.org/wiki/Лисп

Haskell

Haskell (Хаскель, Хаскелл) - стандартизованный чистый функциональный ЯП общего назначения (один из самых распространённых с поддержкой отложенных/ленивых вычислений). Типизация строгая, статическая, с автоматическим выводом типов.

Концепция языка отражает идею математика Хаскелла Карри, писавшего, что «доказательство — это программа, а доказываемая формула — это тип программы». Именно в честь Х. Карри язык и получил своё название.

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

Пролог (фр. Programmation en Logique) - язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.

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

Факты в языке Пролог описываются логическими предикатами с конкретными значениями.

Правила в Прологе записываются в форме правил логического вывода с логическими заключениями и списком логических условий.

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

Факты в базах знаний на языке Пролог представляют конкретные сведения (знания).

Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщёнными сведениями.

Начало истории языка относится к 1970-м годам.

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

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

Другим часто подвергаемым критике свойством языка является отсутствие типизации. В языке предопределён порядок обхода дерева решений в глубину и стандартизированы операторы, позволяющие вмешиваться в этот процесс (такие как оператор отсечения ! или ветвления ->) и не позволяющие распараллелить программу, задействовав в поиске решения несколько процессоров или узлов сети.