Функциональное программирование на языке LISP — это использование программной парадигмы, в которой вычислительный процесс понимается в виде вычисления значений функций в математической трактовке, в отличие от функций, являющихся подпрограммами в процедурном программировании.
Общие сведения о функциональном программировании
Функциональным программированием является подраздел дискретной математики и программная парадигма, в которой процесс вычислений понимается как вычисление значений функций в математическом понимании, в отличие от функций, являющихся подпрограммами в процедурном программировании. Функция в математике обладает аргументом и результатом, она не изменяет состояние остальной программы, то есть, у нее нет побочных эффектов.
Функциональное программирование можно противопоставить парадигме императивного программирования, в которой описывается процесс вычислений как поочередное изменение состояний подобно принятому пониманию в теории автоматов.
Функциональное программирование предполагает обходиться вычислением результатов функций от исходных данных и результатов других функций, и не предусматривает явного хранения состояния программы. Соответственно, не предполагается и изменяемость данного состояния в отличие от императивного программирования, в котором одной из основных концепций выступает переменная, сохраняющая свое значение и позволяющая изменять его в процессе исполнения алгоритма.
Слабой типизацией являются операции приведения типов, а строгой типизацией является обязательное задание типа. Статической типизацией является вариант, когда все типы являются известными на этапе компиляции. Динамической типизацией является случай, когда у переменной может изменяться тип в процессе исполнения программы, а на этапе компиляции типы являются неизвестными.
Функциональное программирование на языке LISP
Есть отличия в восприятии функции в математике и функции в программировании, поэтому нельзя относить языки, подобные языку программирования Си, к функциональным языкам, которые используют менее строгое понятие. Функция в математике не способна поменять вызывающее ее окружение и запомнить результаты своей работы, а способна лишь предоставить итог вычисления функции.
Программирование с применением математических понятий функции может вызвать определенные трудности, по этой причине функциональные языки, в разной степени способны предоставить и императивные возможности, что может ухудшить дизайн программы (к примеру, возможность безболезненного дальнейшего ее корректирования).
Дополнительным отличием от императивных языков программирования является декларативность описаний функций. Текст программы на функциональном языке программирования предоставляет описание «как решить задачу», но не предопределяет очередность действий для решения этой задачи.
Одним из первых функциональных языков был язык LISP, который предложил Джон Мак-Карти как средство изучения границ применимости компьютеров, в частности, методом решения задач искусственного интеллекта. Одним из вариантов этого языка является широко используемый в системе автоматизированного проектирования AutoCAD язык программирования AutoLISP.
Основными преимуществами функциональных языков могут считаться следующие аспекты:
- краткость и простота,
- строгая типизация,
- модульность,
- использование функций в качестве объектов вычисления,
- отсутствие побочных эффектов,
- наличие отложенных (ленивых) вычислений.
Программы на функциональных языках, таких как LISP, как правило, получаются существенно более короткими и простыми, чем такие же программы на императивных языках.
Приведем пример реализации алгоритма быстрой сортировки Хоара на функциональном языке программирования LISP:
quickSort ($[]$) = $[]$
quickSort ($[$h : t$]$) = quickSort ($[$n | n ∈ t, n ∠= h$]$) + $[$h$]$ + quickSort ($[$n | n ∈ t, n > h$]$)
Строгая типизация предполагает, что в функциональном языке практически все ошибки могут быть исправлены на стадии компиляции, что может сократить стадию отладки и общее время создания программы. Помимо этого, строгая типизация может позволить компилятору осуществить генерацию более эффективного кода и тем самым ускорять исполнение программы.
Механизм модульности предоставляет возможность разделения программы на совокупность нескольких относительно независимых фрагментов (модулей) с однозначно определенными связями между ними. Это помогает облегчить процесс проектирования и последующей поддержки больших программных систем. Поддержка модульности не может считаться свойством именно функциональных языков программирования, там не менее, она поддерживается практически всеми такими языками.
В функциональных языках, как, впрочем, и вообще в языках программирования и математике, функции могут передаваться другим функциям как аргумент или возвращаться как итоговый результат. Функции, которые принимают функциональные аргументы, именуются функциями высших порядков или функционалами.
В чистом функциональном программировании нет операторов присваивания, объекты нельзя изменить и уничтожить, можно лишь выполнять создание новых путем декомпозиции и синтеза уже существующих. О ненужных объектах должен позаботиться встроенный в язык сборщик мусора. Благодаря этому в чистых функциональных языках все функции являются свободными от побочных эффектов.
В императивных языках программирования, таких как, к примеру, C++, вызов функции может привести к вычислению всех аргументов. Данный метод вызова функции именуется вызовом по значению. Если какой-нибудь аргумент не применялся в функции, то итог вычислений может пропасть, то есть, вычисления были выполнены впустую. Противоположностью вызова по значению может считаться вызов по необходимости, то есть, ленивые вычисления. В этом варианте вычисление аргумента выполняется только тогда, когда он необходим для вычисления результата.
