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

В настоящее время наиболее распространены следующие языки функционального программирования: Haskell; ML; Ocaml; Erlang; LISP.

Будем рассматривать функциональную парадигму на примере языка программирования LISP.

Лисп (LISP, от англ. LIST Processing — «обработка списков») — семейство языков программирования, основанных на представлении программы системой линейных списков символов, которые являются основной структурой данных языка. Лисп был создан Дж. Маккарти в 1958 году как результат исследований в области искусственного интеллекта, а также продемонстрирован на решении задач символьного дифференцирования и интегрирования алгебраических выражений. Лисп считается вторым после Фортрана старейшим высокоуровневым языком программирования. Несмотря на это, он продолжает развиваться.

Традиционный Лисп имеет строгую динамическую систему типов, содержит императивные свойства, но в основном поощряет функциональную парадигму программирования. Современный Лисп поддерживает также объектно-ориентированное программирование (реализовано на платформе CLOS). Язык Лисп прошёл процесс фундаментальной стандартизации, в результате чего появился стандарт ANSI Common Lisp. Его реализации существуют для большинства платформ. Вот несколько реализаций Lisp:

свободного распространения:

CLISP – под лицензией GNU GPL, доступен для Windows, Macintosh и Linux / Unix; OpenMCL – под лицензией GNU LGPL, доступен для Mac, Linux, FreeBSD, Solaris, Windows (in alpha); CMU Common Lisp – Public License, доступен для Unix и Linux; Steel Bank Common Lisp – производное от CMU Common Lisp (включает компилятор);

коммерческие продукты:

LispWorks – система высокого качества и по разумным ценам для Windows и Linux; Franz Allegro Lisp – высокое качество и высокая стоимость.

В Лиспе также существует ряд диалектов: Scheme, Common Lisp, Emacs Lisp, AutoLisp. Важнейшие примеры программных продуктов, построенных на основе Лисп, – это AutoCAD, текстовый редактор Emacs. Особую роль Лисп также играет в системах компьютерной алгебры (Maxima, Axiom, Mathematica, Reduce). Можно заметить, что практически все перечисленные программные продукты имеют очень большой жизненный цикл – они созданы очень давно и продолжают развиваться в настоящее время.

Основные структуры данных и базовые функции по работе с ними в среде Лисп

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

Символы T, Nil имеют в Лисп специальные названия: T – истина (true), Nil – ложь (false). Эти символы нельзя использовать в качестве имён других объектов. Числа и логические значения T, Nil являются константами, которые вычисляются сами в себя, остальные символы являются переменными, которые используются для обозначения других объектов. Числа и символы представляют собой простейшие объекты – атомы, из которых строятся остальные структуры. Основной тип данных и структура, с которой приходится иметь дело в Лисп – списки. Список – упорядоченная последовательность элементов, ограниченная круглыми скобками, сами элементы отделяются друг от друга пробелами; в качестве элементов могут использоваться атомы или списки. Вот ряд примеров списков: (a s d f); (a b (c d) e); (); nil. Последние два примера представляют список, который не содержит элементов, такой список называется пустым. Атомы и списки называются символьными выражениями или s-выражениями Лиспа. В языке Лисп, с точки зрения синтаксиса, программы и данные не различаются, поэтому любое s-выражение можно интерпретировать как программу.

Важная особенность Лисп – использование префиксной формы записи: сначала записывается операция, затем операнды. Например, обычное выражение 7+9 в Лиспе записывается так (+ 7 9). Это имеет свои преимущества – в выражении 1+2+3+4+5 можно сэкономить на символах «+»: (+ 1 2 3 4 5). Рассмотрим еще ряд примеров вычислений в среде Лисп:

; точка с запятой используются как комментарии в Лисп

;пример 1

;пусть необходимо вычислить 5*3+7

;в Лиспе это запишется так:

(+ (* 5 3) 7) ;после Enter получим ответ:

• 22

;пример 2

;пусть необходимо вычислить (1+2+3+4)/20

;в Лиспе это запишется так:

(/ (+ 1 2 3 4) 20)

;ответ будет не совсем ожидаемым:

> 1/2

;т. е., Лисп сам динамически получает тип данных – рациональное число,

;как наиболее точное представление результата операции

;при желании всегда можно перейти к вещественным числам:

(float (/ (+ 1 2 3 4) 20))

> 0.5

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

;попробуем вычислить

(1 2 3)

>Error

;Ошибка возникает потому, что Лисп пытается вычислить это выражение,

;используя символ «1» в качестве имени функции, «2», «3» – в качестве её ;аргументов.

;если блокировать вычисление,

'(1 2 3)

;то ошибку уже не получим

> (1 2 3)

Для работы с какой-либо структурой данных в языке программирования Лисп должны быть предусмотрены три механизма: 1) позволяющие разбирать структуру данных на части – селекторы; 2) позволяющие собирать структуру данных из частей – конструкторы; 3) позволяющие проверять различные условия на структуре данных и возвращать T или Nil–предикаты.

В качестве базовых селекторов в языке Лисп используются всего две функции:

1. Функция CAR (читается «кар») – возвращает в качестве значения первый (головной) элемент списка – аргумента. Тип результата – s-выражение.

2. Функция CDR (читается «кудр») – возвращает в качестве значения хвостовую часть списка – аргумента. Тип результата – список.

Рассмотрим ряд примеров:

(car '(1 2 3))

;обращаем внимание на блокировку в начале списка (1 2 3), иначе будет ;ошибка

> 1

(car '((1 2) 3))

>(1 2)

(cdr '(1 2 3))

>(2 3)

(cdr '((1 2) 3))

>(3)

(cdr '(3))

>nil

;с помощью этих функций можно добраться до любого элемента в списке

(car (cdr '(1 2 3 4)))

;так получаем второй элемент списка

>2

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

(cons 'a '(b c))

>(a b c)

(cons '(+ 1 2) '(c d))

>((+ 1 2) c d)

(cons (+ 1 2) '(4 5))

;первый аргумент не заблокирован, поэтому перед подстановкой

;вычисляется

>(3 4 5)

В качестве предикатов в Лиспе используется множество различных функций. Рассмотрим некоторые из них.

Функция ATOM – проверяет, является ли аргумент атомом. Аргументом может быть любое s-выражение. Значение предиката равно T, если аргумент является атомом, в противном случае Nil. Примеры:

(atom 'x)

> T

(atom '())

>T

;дело в том, что пустой список является одновременно и атомом и списком

(atom '(a b c))

>Nil

Функция EQL – сравнивает числа одинаковых типов. Предикат нельзя использовать для сравнения списков (для чисел можно также использовать обычный символ «=»). Примеры:

(eql 3 3)

>T

(eql 3 3.0) ;Хотя числа равные, но разных типов

> Nil

(= 5 5)

>T

(eql '(1 2 3) '(1 2 3))

>Nil

Функция EQUAL – работает так же, как EQL, но позволяет сравнивать и списки. Примеры:

(equal 'x 'x)

>T

(equal '(1 2 3) '(1 2 3))

>T

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

Ветвление реализуется в Лисп с помощью следующей специальной формы:

(IF (condition) (expression-true) (expression-false))

Здесь condition – условие, которое проверяется;

expression-true – выражение, которое вычисляется и значение которого возвращается в качестве ответа всей формы IF, если условие condition верно;

expression-false – выражение, которое вычисляется и значение которого возвращается в качестве ответа всей формы IF, если условие condition неверно.

Иногда требуется рассмотреть более одного условия (осуществить разбор случаев), тогда может быть полезна следующая форма:

(COND

((condition1) (expression1))

((condition2) (expression2))

…

((condition_n) (expression_n))

(T (expression-else)))

Здесь проверяется условие condition1. Если оно выполняется, то результатом формы COND будет значение выражения expression1 (условия, расположенные ниже, уже не рассматриваются); если condition1 неверно, то проверяется condition2, и если оно верно, то результатом формы COND будет значение выражения expression2 и т. д. Если неверно ни одно из условий condition1, condition2, …, condition_n, то вычисляется выражение expression-else, и его значение возвращается в качестве результата формы COND.

Для задания функции используется специальное служебное слово DEFUN. При этом функция задаётся в следующем виде:

(DEFUN Function-name (list-arg) (body-function))

Здесь Function-name – имя функции;

list-arg – список аргументов функции;

body-function – тело функции.

Рассмотрим ряд примеров:

(if (equal (cdr '(1)) nil) 1 2)

>1

(if (atom '(1 2)) 1 2)

>2

(defun f (x) (+ x 1)) ; определили функцию

>(f 1) ;вычисляем её значение от x=1

>2

(defun g (x y) (if (> x y) (- x y) (* x y)))

>(g 1 2)

>2

>(g 3 2)

>1

(defun h (x)

(cond

((= x 0) 1)

((> x 0) (+ x 1))

(t x)))

>(h 0)

>1

>(h 1)

>2

>(h -1)

>-1

Техники функционального программирования – рекурсия

Рекурсия является одной из важнейших техник функционального программирования.

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

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

Пусть необходимо построить функцию вычисления факториала:

(defun factorial (n)

(if (= n 1)

1

(* n (factorial (- n 1)))))

При вычислении используется так называемая подстановочная модель:

(factorial 6)

(* 6 (factorial 5))

(* 6 (* 5 (factorial 4)))

(* 6 (* 5 (* 4 (factorial 3))))

(* 6 (* 5 (* 4 (* 3 (factorial 2)))))

(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))

(* 6 (* 5 (* 4 (* 3 (* 2 1)))))

(* 6 (* 5 (* 4 (* 3 2))))

(* 6 (* 5 (* 4 6)))

(* 6 (* 5 24))

(* 6 120)

720

Выделяют следующие способы организации рекурсии:

• Простая рекурсия.

• Параллельная рекурсия.

• Взаимная рекурсия.

• Рекурсия высоких порядков.

Общий вид простой рекурсии:

(defun f (...)

(cond ((...) (...)) ((...)( ...(f ...) ...)) ((...)(...))) )

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

Определение функции factorial является простой рекурсией. Вот еще пример простой рекурсии – функция append, объединяющая два списка в один:

(defun append (X Y)

(if (Null X) Y (cons (car X) (append (cdr X) Y))))

;здесь предикат Null принимает значение T, если список X пуст,

;Nil — в противном случае.

Общий вид параллельной рекурсии:

(defun f ... (g ... (f ...) ... (f ...) ...) ...)

Таким образом, при параллельной рекурсии тело определения функции f содержит вызов некоторой функции g, несколько аргументов которой являются рекурсивными вызовами функции f. Пример такой функции – вычисление чисел Фибоначчи.

Общее правило для чисел Фибоначчи можно сформулировать так:

если n = 0 , то Fib(n) = 0

если n = 1 , то Fib(n) = 1

в остальных случаях Fib(n)=Fib(n − 1) + Fib(n − 2)

Можно немедленно преобразовать это определение в процедуру Лисп:

(defun fib (n)

(cond ((= n 0) 0)

((= n 1) 1)

(t (+ (fib (- n 1))

(fib (- n 2))))))

Общий вид взаимной рекурсии:

(defun f ... (g ...)...)

(defun g ... (f ...)...)

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

(defun turn (L)

(cond ((Atom L) L)

(t (permulate L nil))))

(defun permulate (L Result)

(cond ((Null L) result)

(t (permulate (cdr L)

(cons (turn (car L))

result)))))

Общий вид рекурсии высших порядков:

(defun f ... (f ...(f ...)...) ...)

В качестве классического примера рекурсии более высокого порядка часто приводится известная из теории рекурсивных функций функция Аккермана,пользующаяся славой «плохой» функции:

(defun akkerman (m n)

(cond ((= m 0) (+ n 1))

((= n 0) ( akkerman (- m 1) 1))

(t ( akkerman (- m 1)

(akkerman m (- n 1))))))

>(аккерман 2 2)

>7

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