Функциональное программирование в учебных заведениях обычно начинают изучать уже после того, как изучено структурное программирование, а во многих случаях уже и объектно-ориентированное программирование.
Вначале изучения курса у студентов складывается мнение, что функциональный стиль программирования намного скуднее привычного структурного. Поэтому, для понимания того, что любую структурированную программу можно перевести в программу, основанную на функциях, то есть записать в функциональном стиле, и была написана эта программа.
Кроме того, смысл перевода программ написанных на императивном языке в функциональный стиль состоит в том, что функциональные программы можно проверять на правильность, а следовательно, если императивную программу преобразовать в функциональную, то и ее можно проверить на правильность.
Также преобразование императивной программы в функциональный стиль разбивает ее на маленькие элементарные функции, а следовательно разбив программу, можно провести ее тестирование пошаговым методом снизу-вверх (тестирование элементарных функций не вызывает никакого труда). Пошаговый метод тестирования снизу вверх заключается в том, что вначале тестируются функции, находящиеся на самом нижем уровне, которые не используют других функций полученной функциональной программы, а затем функции, которые используют уже ранее протестированные функции.
Программа написана на языке PHP. Это интерпретируемый С-подобный язык, который используется на серверах в Интернете и предназначен для динамического формирования Web-страниц. При использовании этого языка программу, написанную на нем, можно разместить на Web-сервере. Все желающие могут использовать ее, имея только доступ в Интернет, совершенно независимо от того, какое у них аппаратное обеспечение, какую операционную систему они используют.
Для большей читабельности программных текстов и для возможности проверки полученных результатов выполнения этой программы были использованы не какие-либо псевдоязыки, а языки, для которых существуют компиляторы и интерпретаторы, синтаксис которых известен большому кругу программистов.
В качестве императивного языка используется часть языка Pascal (его конструкции: присваивание (:=), условный оператор (if), циклы (while, repeat, for)), а в качестве функционального языка используется язык Lisp.
Выполнение программы происходит по блокам, то есть программа ищет элементы, которые непосредственно преобразуются в функцию, и заменяет их. Такими элементами являются: цепочка присваиваний, условный оператор, циклы.
В условных операторах и циклах перед тем, как преобразовать их в функцию, нужно преобразовать вначале их тело, при этом тело функции рассматривается как отдельная подпрограмма.
Пример:
if (a > b) then begin a:=c;b:=a; end
В этом случае вначале преобразовывается цепочка присваиваний: f(a,b,c)={a := c;b := a}, а затем и сам условный оператор g(a,b,c)={if (a > b) then f(a,b,c)};.
После преобразования всех элементов императивной программы в их функциональные эквиваленты нужно создать функцию, которая свяжет все полученные ранее функции. Очевидно, что во второй полученной функции (преобразование происходит сверху-вниз), необходимо учитывать результат выполнения первой, а в третьей – второй и т.д. Следовательно, видим, что получается цепочка, где каждая следующая функция применяет предыдущую. На языке Lisp это выглядит так:
(APPLY FUNC_N (APPLY FUNC_N1 … (APPLY FUNC_2 (FUNC_1 x))…)), где х – начальные значения переменных императивной программы.
Далее приведем представление основных конструкций императивного языка в функциональном стиле. Пусть в программе используются 3 переменных a, b, c. В таблице представлено преобразование самых популярных конструкций императивного языка, это присваивание, условный оператор и цикл пока (цикл for всегда можно свести к циклу while).
| Императивный язык (Pascal) | Функциональный язык (Lisp) |
|---|---|
|
a := b; b := c + 2; |
(defun FUNC (a b c) (list b (+ c 2) c) ) |
|
if (a > b) then f(a, b, c) else g(a, b, c); |
(defun FUNC (a b c) (if (> a b) (f a b c) (g a b c)) ) |
| if (a > b) then f(a, b, c); |
(defun FUNC (a b c) (if (> a b) (f a b c) (list a b c)) ) |
| while (c = b + a) do f(a, b, c); |
(defun FUNC(a b c) (if (= c (+ b a)) (APPLY FUNC (f a b c)) (list a b c) ) ) |
Для преобразования выше указанных конструкций требовалась для представления лишь одна функция, однако (например, в цикле repeat-until), возникает необходимость использовать более чем одну функции. В этом случае удобно воспользоваться λ-определением функций.
| Императивный язык (Pascal) | Функциональный язык (Lisp) |
|---|---|
|
repeat f(a, b, c) until (b < c) |
(defun FUNC (a b c) (APPLY (LAMBDA (a b c) (if (b < c) (list a b c) (FUNC a b c))) (f a b c) ) ) |