В статье про Python пользователь Xronos попросил рассказать о функциональном программировании (ФП). Поскольку я одно время довольно плотно занимался с Lisp, я хотел бы немножко рассказать об этом. Сразу хочу сказать, что о чистом ФП речь не идет. Я расскажу о более простых и более применимых приемах на примере языка Python.
Сразу скажу, почему я не буду рассказывать о чистом ФП. Чистое ФП подразумевает отсутствие состояния вычисления и немодифицируемость памяти (отсутствие побочных эффектов выполнения подпрограмм). Грубо говоря, вся программа в чистом ФП представляет собой одну большую формулу. Чисто императивные концепции, вроде последовательности вычислений, ввода-вывода и изменяемого состояния, в них реализуются различными красивыми способами вроде монад в Haskell. Кроме того, в ФП включают различные концепции более высокого порядка:
- совпадение по шаблону (pattern matching) — наподобие перегрузки функций, только более продуманно и более гибко
- продолжения (continuation) — возможность останавливать вычисление и продолжать его в другое время (т.е. «консервировать» состояние вычисления и потом возобновлять его). Вид продолжения мы видим в работе оператора
yield - ленивые вычисления — При такой модели, грубо говоря, аргументы функций вычисляются только тогда, когда они реально необходимы, а не при входе в функцию
- алгебраические типы данных, рекурсивные типы данных, автоматический вывод типов — и т.д. и т.п.
На этом я концентрироваться не буду, поскольку а) сам не применял этих концепций на практике (или применял, но ограниченно), б) их применимость для «обычного» программиста на «обычных» языках пока недоступна. Поэтому мы начнем с более простых понятий.
Функции
В ФП все завязано вокруг функций, поэтому функция должна быть объектом первого рода (first-class object). Это значит, что функцию можно создать (анонимная функция), можно присвоить переменной, можно передать в функцию, можно вернуть из функции. Вновь созданные функции должны обладать свойством замыкания (closure) — т.е. новая функция должна захватывать окружающий контекст (объявленные переменные как локальной, так и глобальной области видимости). Простой пример (полный код к данному посту вы можете найти по ссылкам внизу поста):
# encoding: utf-8
def get_writer(type, params):
# вывод данных в HTML
def html_writer(filename):
f = open(filename + '.' + type, 'w');
f.write("""
<html>
<head>
<title>%s</title>
</head>
<body>
<h1>Hello</h1>
</body>
""" % params['title'])
f.close()
# вывод данных в PLAIN TEXT
def text_writer(filename):
f = open(filename + '.' + type, 'w');
f.write("""
%s
=================================
Hello
""")
f.close()
# определим, какой тип данных запросили, и вернем соответсвующую функцию
if type == 'html':
return html_writer
elif type == 'txt':
return text_writer
params = { 'title': 'Header' }
# выведем в HTML
f = get_writer('html', params)
f('file1')
# выведем в PLAIN TEXT
f = get_writer('txt', params)
f('file2')
Обратите внимание на то, что внутри
html_writer и text_writer используются аргументы get_writer (type и params). Как такое может быть? Ведь после возврата из get_writer ее аргументы, по идее, перестают существовать? В этом и заключается суть замыкания: если одна функция возвращает другую, то к последней добавляется еще и так называемый контекст — совокупность всех доступных переменных (локальных, глобальных, аргументов) с их значениями на момент вызова. Таким образом, при возврате функции из функции вы возвращаете не просто функцию (простите за тавталогию), а замыкание — функцию + контекст.Функции высшего порядка
Теперь представьте такой пример. Мы пишем программу построения графиков определенных функций. Определим пару таких функций:
# encoding: utf-8 import math # y = k * x + b def get_linear(k, b): return lambda x: k * x + b # y = k * x^2 + b def get_sqr(k, b): return lambda x: k * x ** 2 + b # y = A * sin(k * x + phi) def get_sin(amplitude, phi, k): return lambda x: amplitude * math.sin(math.radians(k * x + phi)) # y = A * e^(k*x) def get_exp(amplitude, k, b): return lambda x: amplitude * math.exp(k * x + b)
Это простые функции. Как мы можем их использовать:
# y = 5 * sin(0.3 * x + 30) y = get_sin(5, 30, 0.3) # y(90) = 4.19 print y(90) print # результат применения y к интервалу от 0 до 180 print [ y(x) for x in range(0, 180) ]
Но, вы видите, каждая из этих функций поддерживает операцию сдвига функции по оси X. А ведь это отдельная функция и мы можем ее выделить! И точно так же мы можем выделить функции масштабирования по X и по Y:
def shifter(func, b): return lambda x: func(x + b) def x_scaler(func, k): return lambda x: func(k*x) def y_scaler(func, A): return lambda x: A * func(x) def combine(func1, func2): return lambda x: func2(func1(x))
shifter, x_scaler, y_scaler, combine — это функции высшего порядка (high-order functions), т.к. они принимают не только скалярные аргументы, но и другие функции, модифицируя их поведение. Combine — крайне полезная общая функция, позволяющая применить одну функцию к другой. Теперь мы можем переписать наши предыдущие функции следующим образом:def identity(x): return x def sqr(x): return x ** 2
Уже интересней. Мы переименовали две функции, а две вообще убрали. Зачем переименовали? Дело в том, что избавившись от «шелухи» вроде масштабирования и переноса, мы получили еще более общие функции. Первая из них называется
identity — функция идентичности — очень важное понятие в ФП. Очень важное, но очень простое — возвращает свой аргумент и все. Вторая функция просто возводит аргумент в квадрат. Теперь любую конфигурацию, которую мы могли описать нашими функциями из первого примера, мы можем получить путем комбинирования простых функций и функций высшего порядка — главное комбинировать их в корректной последовательности. Для демонстрации того, что значит в корректной последовательности, приведу такое выражение:y = x_scaler(shifter(x_scaler(sqr, 5), 6), 7)
Какую результирующую функцию мы получим? Сначала к аргументу применяется… нет, не
x_scaler(5) и не sqr, а самый внешний x_scaler. Затем shifter. затем внутренний x_scaler. Затем sqr. Покрутите это немного у себя в голове, к этому нужно немного «привыкнуть». Порядок такой: первым применяется самый внешний модификатор. Результат будет полностью аналогичен следующей функции: def y(x): return sqr(((x * 7) + 6) * 5)
С тем различием лишь, что мы фактически создали эту функцию вручную по кусочкам. Теперь давайте для закрепления попробуем написать y = 5 * sin(0.3 * x + 30):
# самым последним должен применяться y_scaler(5) y = y_scaler(math.sin, 5) # предпоследним -- превращение угла в радианы y = combine(math.radians, y) # далее -- shifter(30) y = shifter(y, 30) # наконец -- x_scaler(0.3) y = x_scaler(y, 0.3)
Очевидно, результат будет полностью аналогичен примеру без комбинаторов.
И последний финт функциями
Поднаторев в комбинировании, мы довольно просто напишем, например, модулятор одной функции при помощи другой:
def modulate(mod, src): return lambda x: mod(x) * src(x)
Теперь мы можем описать затухающие гармонические колебания:
# y1 = 5 * sin(15 * x + 30) -- исходная функция
y1 = \
x_scaler(
shifter(
combine(
math.radians,
y_scaler(
math.sin,
5)),
30),
15)
# y2 = exp(-0.01 * x) -- модулирующая функция
y2 = x_scaler(math.exp, -0.01)
y = modulate(y2, y1)
print [ y(x) for x in range(0, 180) ]
По-моему, неплохо:
На этом, пожалуй, пост закончу. В следующий раз будут списки, техника map-reduce и list comprehensions как синтаксический сахар для данной техники и как это все помогает нам более ясно выражать свои мысли в коде.
Код к этому посту: 1 2 3 4
UPDATE: т.к. кармы теперь достаточно, решил перенести этот топик в блог Python