Функциональное программирование на Python
Рассмотрена поддержка функционального программирования в языке Python. Даны примеры использования лямбда-выражений и функций высших порядков
Парадигма функционального программирования
Математические функции выражают связь между исходными данными и итоговым продуктом некоторого процесса. Процесс вычисления также имеет вход и выход, поэтому функция - вполне подходящее и адекватное средство описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно через самих себя. При выполнении программы функции получают параметры, вычисляют и возвращают результат, при необходимости вычисляя значения других функций. На функциональном языке программист не должен описывать порядок вычислений. Нужно просто описать желаемый результат как систему функций.
Функциональное программирование - это стиль программирования, который опирается на вычисление выражений, а не на выполнение команд. Выражения формируются с помощью комбинирования функций.
В отличие от императивного, которое работает со строго определёнными состояниями и инструкциями, функциональное программирование основывается на взаимодействии с функциями, то есть процессами, описывающими связь между входными и выходными параметрами. Таким образом, в то время, как императивный язык описывает конкретное действие с известными входными параметрами, функциональный описывает некое тело взаимодействий, не опускаясь до конкретных случаев.
Функциональное программирование, несмотря на кажущуюся сложность, несёт в себе ряд преимуществ:
- Код становится короче;
- Проще в понимании;
- Включает в себя признаки императивных языков: модульность, типизация, чистота кода.
Примерами функциональных языков являются LISP (Clojure), Haskell, Scala, R.
Функциональное программирование, как и логическое программирование, нашло большое применение в теории искусственного интеллекта и её приложениях.
В основном, языки программирования представляют собой гибрид нескольких парадигм программирования, в частности, одни из таких языков является Python. Однако можно выделить основные концепции функционального программирования:
Чистые функции
Это концепция является основной в функциональном программировании. Чистые функции удовлетворяют двум условиям:
1. Функция, вызываемая от одних и тех же аргументов, всегда возвращает одинаковое значение. Например, если происходит вызов функции sum(2, 3), то ожидается, что результат всегда будет равен 5. При вызове же функции rand(), или при обращении к переменной, не определённой в функции, чистота функции нарушается, а это в функциональном программировании недопустимо.
2. Во время выполнения функции не возникают побочные эффекты. Побочный эффект - это изменение чего-то отличного от функции, которая исполняется в текущий момент. Изменение переменной вне функции, вывод в консоль, вызов исключения, чтение данных из файла - всё это примеры побочных эффектов, которые лишают функцию чистоты.
Функции высших порядков.
Это такие функции, которые могут принимать в качестве аргументов и возвращать другие функции. Функции высших порядков позволяют использовать карринг - преобразование функции от пары аргументов в функцию, берущую свои аргументы по одному.
Рекурсия.
В функциональных языках цикл обычно реализуется в виде рекурсии, так как в функциональной парадигме программирования отсутствует такое понятия, как цикл. Рекурсивные функции вызывают сами себя, позволяя операции выполняться снова и снова. Для использования рекурсии может потребоваться большой стек, но этого можно избежать в случае хвостовой рекурсии. Хвостовая рекурсия может быть распознана и оптимизирована компилятором в код, получаемый после компиляции аналогичной итерации в императивном языке программирования. Оптимизировать хвостовую рекурсию можно путём преобразования программы в стиле использования продолжений при её компиляции, как один из способов.
Переменные неизменяемы.
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путём разбора и сбора существующих. О ненужных объектах позаботится встроенный в язык сборщик мусора. Благодаря этому в чистых функциональных языках все функции свободны от побочных эффектов.
Лямбда-исчислении
Функциональное программирование по большей части берет своё начало из математического направления, называемого
1. В лямбда-исчислении все функции могут быть анонимными, поскольку единственная значимая часть заголовка функции - это список аргументов.
2. При вызове все функции проходят процесс каррирования. Он заключается в следующем: если вызывается функция с несколькими аргументами, то сперва она будет выполнена лишь с первым аргументом и вернёт новую функцию, содержащую на 1 аргумент меньше, которая будет немедленно вызвана. Этот процесс рекурсивен и продолжается до тех пор, пока не будут применены все аргументы, возвращая финальный результат. Поскольку функции являются чистыми, это работает.
Краткая история функционального программирования
Теория, положенная в основу функционального подхода, родилась в 20-х - 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать Моисея Шейнфинкеля и Хаскелла Карри, разработавших комбинаторную логику, и Алонзо Чёрча, создателя лямбда-исчисления.
Теория так и оставалась теорией, пока в конце 1950-х годов Джон Маккарти не разработал язык Лисп, который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется (также как и Фортран), после многих лет эволюции он удовлетворяет современным запросам, которые заставляют разработчиков программ взваливать как можно большую ношу на компилятор, облегчив так свой труд. Нужда в этом возникла из-за всё более возрастающей сложности программного обеспечения.
В связи с этим обстоятельством всё большую роль начинает играть типизация. В конце 70-х — начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм. Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число диалектов.
В семидесятых в университете Эдинбурга Робин Милнер создал язык ML, а Дэвид Тернер начинал разработку языка SASL в университете Сент-Эндрюса и, впоследствии, язык Miranda в университете города Кент. В конечном итоге на основе ML были созданы несколько языков, среди которых наиболее известные Objective Caml и Standard ML. Также в семидесятых осуществлялась разработка языка программирования, построенного по принципу Scheme (реализация не только функциональной парадигмы), получившего описание в известной работе «Lambda Papers», а также в книге восемьдесят пятого года «Structure and Interpretation of Computer Programs».
В результате вышло так, что практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов.
Большинство функциональных языков программирования реализуются как интерпретируемые, следуя традициям Лиспа (примечание: большая часть современных реализаций Лиспа содержат компиляторы в машинный код). Таковые удобны для быстрой отладки программ, исключая длительную фазу компиляции, укорачивая обычный цикл разработки. С другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие машинный код (например, Objective Caml) или код на С/С++ (например, Glasgow Haskell Compiler). Практически каждый компилятор с функционального языка реализован на этом же самом языке. Это же характерно и для современных реализаций Лиспа, кроме того среда разработки Лиспа позволяет выполнять компиляцию отдельных частей программы без остановки программы (вплоть до добавления методов и изменения определений классов).
Особенности функционального программирования
Основной особенностью функционального программирования, определяющей как преимущества, так и недостатки данной концепции, является то, что в ней реализуется модель вычислений без состояний. Если императивная программа на любом этапе исполнения имеет состояние, то есть совокупность значений всех переменных, и производит побочные эффекты, то чисто функциональная программа ни целиком, ни частями состояния не имеет и побочных эффектов не производит. То, что в императивных языках делается путём присваивания значений переменным, в функциональных достигается путём передачи выражений в параметры функций. Непосредственным следствием становится то, что чисто функциональная программа не может изменять уже имеющиеся у неё данные, а может лишь создавать новые путём копирования или расширения старых. Следствием этого является отказ от циклов в пользу рекурсии.
Достоинства функционального программирования:
Недостатки функционального программирования::
Недостатки функционального программирования следуют из его плюсов. Отсутствие присваиваний и замена их на создание новых данных приводят к необходимости постоянного выделения и автоматического освобождения памяти, поэтому в системе исполнения функциональной программы обязательным компонентом становится высокоэффективный сборщик мусора. Нестрогая модель вычислений приводит к непредсказуемому порядку вызова функций, что создает проблемы при вводе-выводе, где порядок выполнения операций важен. Кроме того, функции ввода в своем естественном виде (например, getchar из стандартной библиотеки языка C) не являются чистыми, поскольку способны возвращать различные значения для одних и тех же аргументов, и для устранения этого требуются определенные ухищрения.
Для преодоления недостатков функциональных программ уже первые языки функционального программирования включали не только чисто функциональные средства, но и механизмы императивного программирования. Использование таких средств позволяет решить некоторые практические проблемы, но означает отход от идей функционального программирования и написание императивных программ на функциональных языках.
Поддержка функционального программирования в Python
Python поддерживает большую часть характеристик функционального программирования, начиная с версии Python 1.0. Но, как и большинство возможностей Python, они присутствуют в очень смешанном языке.
Базовые элементы функционального программирования в Python - функции map(), reduce(), filter() и оператор lambda. Этих функций и всего нескольких базовых операторов почти достаточно для написания любой программы на Python; в частности, все управляющие утверждения (if, elif, else, assert, try, except, finally, for, break, continue, while, def) можно представить в функциональном стиле, используя исключительно функции и операторы.
Функции в Python
Функции в Python определяются 2-мя способами: через определение def или через анонимное описание lambda. Оба этих способа определения доступны, в той или иной степени, и в некоторых других языках программирования. Особенностью Python является то, что функция является таким же именованным объектом, как и любой другой объект некоторого типа данных, например, как целочисленная переменная. В листинге представлен пример объявления одной и той же функции разными способами:
def show(fun, arg):
print(type(fun), ':', fun)
print('arg =',arg,'=> fun(arg) =', fun(arg))
n = float(input('Введите число: '))
def pow3(n): # 1-е определение функции
return n**3
show(pow3, n)
pow3 = lambda n: n**3 # 2-е определение функции с тем же именем
show(pow3, n)
show((lambda n: n**3),n) # 3-е, анонимное описание функции
При вызове всех трёх объектов-функций мы получим один и тот же результат:
Введите число: 13
< class 'function' > : < function pow3 at 0x03425270 >
arg = 13.0 => fun(arg) = 2197.0
< class 'function' > : < function pow3 at 0x03425270 >
arg = 13.0 => fun(arg) = 2197.0
< class 'function' > : < function pow3 at 0x03425270 >
arg = 13.0 => fun(arg) = 2197.0
В Python версии 3, в которой всё является классами (в том числе, и целочисленная переменная), функции являются объектами программы, принадлежащими к классу function.
Существуют ещё 2 типа объектов, допускающих функциональный вызов - функциональный метод класса и функтор.
Если функциональные объекты Python являются такими же объектами, как и другие объекты данных, значит, с ними можно и делать всё то, что можно делать с любыми данными:
- динамически изменять в ходе выполнения;
- встраивать в более сложные структуры данных (коллекции);
- передавать в качестве параметров и возвращаемых значений и т.д.
На этом (манипуляции с функциональными объектами как с объектами данных) и базируется функциональное программирование. Python, конечно, не является настоящим языком функционального программирования, так, для полностью функционального программирования существуют специальные языки: Lisp, Planner, а из более свежих: Scala, Haskell. Ocaml. Но в Python можно "встраивать" приёмы функционального программирования в общий поток императивного (командного) кода, например, использовать методы, заимствованные из полноценных функциональных языков. Т.е. "сворачивать" отдельные фрагменты императивного кода (иногда достаточно большого объёма) в функциональные выражения.
Основным преимуществом функционального программирования является то, что после однократной отладки такого фрагмента в нём при последующем многократном использовании не возникнут ошибки за счёт побочных эффектов, связанных с присвоениями и конфликтом имён.
Достаточно часто при программировании на Python используют типичные конструкции из области функционального программирования, например:
print([(x, y) for x in (1, 2, 3, 4, 5) \
for y in (20, 15, 10) \
if x * y > 25 and x + y < 25])
В результате запуска получаем:
[(2,20), (2,15), (3,20), (3,15), (3,10), (4,20), (4,15), (4,10), (5,15), (5,10)]
Элементы функционального программировании в Python
Основными элементами функционального программирования в Python являются следующие функции: lambda, map, filter, reduce, zip.
lambda выражение
lambda оператор или lambda функция в Python это способ создать анонимную функцию, то есть функцию без имени. Такие функции можно назвать одноразовыми, они используются только при создании. Как правило, lambda функции используются в комбинации с функциями filter, map, reduce.
Синтаксис lambda выражения в Python:
lambda arguments: expression
В качестве arguments передается список аргументов, разделенных запятой, после чего над переданными аргументами выполняется expression. Если присвоить lambda-функцию переменной, то получим поведение как в обычной функции:
>>> multiply = lambda x, y: x * y
>>> multiply(21, 2)
42
Но все преимущества lambda-выражений состоят в использовании lambda в связке с другими функциями.
Ниже приведен пример использования lambda-выражения который позволяет напечатать словарь в порядке убывания суммы каждого значения:
dict = {"AB": [10, 11, 12], "BC": [5, -5, 8], "CD": [105, 1, 0],
"DE": [6, 6], "EF": [15, 20, 15], "FG": [22, 11, 32],
"GH": [20, 20, 20]}
sorter = sorted(dict.items(), key=lambda key: sum(key[1]), reverse=True)
print(sorter)
На выводе получим отсортированный словарь в виде списка:
[('CD', [105, 1, 0]), ('FG', [22, 11, 32]), ('GH', [20, 20, 20]), ('EF', [15, 20, 15]), ('AB', [10, 11, 12]), ('DE', [6, 6]), ('BC', [5, -5, 8])]
Кроме того, можно создавать списки lambda-выражений, которые позволяют получить список действий, выполняемых по требованию:
a3 = [(lambda x,y: x+y),(lambda x,y: x-y),(lambda x,y: x*y),(lambda x,y: x/y)]
b = a3[0](5,12)
print(b)
for i in a3:
print(i(4,1))
Результат:
17
5
3
4
4.0
Также можно создавать таблицы действий с помощью словарей, значениями которых являются lambda-выражения:
a4 = {'pos':lambda x: x-1, 'neg':lambda x: abs(x)-1, 'zero':lambda x: x}
b = [-3, 10, 0, 1]
for i in b:
if i < 0:
print(a4['neg'](i))
elif i > 0:
print(a4['pos'](i))
else:
print(a4['zero'](i))
Результат:
2
9
0
0
Функция map()
В Python функция map принимает два аргумента: функцию и аргумент составного типа данных, например, список. map применяет к каждому элементу списка переданную функцию. Например, вы прочитали из файла список чисел, изначально все эти числа имеют строковый тип данных, чтобы работать с ними - нужно превратить их в целое число:
old_list = ['1', '2', '3', '4', '5', '6', '7']
new_list = []
for item in old_list:
new_list.append(int(item))
print (new_list)
Вывод:
[1, 2, 3, 4, 5, 6, 7]
Тот же эффект мы можем получить, применив функцию map:
old_list = ['1', '2', '3', '4', '5', '6', '7']
new_list = list(map(int, old_list))
print(new_list)
В результате запуска получим тоже самое:
[1, 2, 3, 4, 5, 6, 7]
Такой способ занимает меньше строк, более читабелен и выполняется быстрее. map также работает и с функциями, созданными пользователем:
def miles_to_kilometers(num_miles):
return num_miles*1.6
mile_distances = [1.0, 6.5, 17.4, 2.4, 9]
kilometer_distances = list(map(miles_to_kilometers, mile_distances))
print (kilometer_distances)
[1.6, 10.4, 27.84, 3.84, 14.4]
А теперь то же самое, только используя lambda выражение:
mile_distances = [1.0, 6.5, 17.4, 2.4, 9]
kilometer_distances = list(map(lambda x: x * 1.6, mile_distances))
print(kilometer_distances)
[1.6, 10.4, 27.84, 3.84, 14.4]
Функция map может быть так же применена для нескольких списков, в таком случае функция-аргумент должна принимать количество аргументов, соответствующее количеству списков:
l1 = [1,2,3]
l2 = [4,5,6]
new_list = list(map(lambda x,y: x+y, l1, l2))
print (new_list)
[5, 7, 9]
Если же количество элементов в списках совпадать не будет, то выполнение закончится на минимальном списке:
l1 = [1,2,3]
l2 = [4,5]
new_list = list(map(lambda x,y: x+y, l1, l2))
print (new_list)
[5, 7]
Функция filter()
Функция filter предлагает элегантный вариант фильтрации элементов последовательности. Принимает в качестве аргументов функцию и последовательность, которую необходимо отфильтровать:
mixed = ['мак', 'просо', 'мак', 'мак', 'просо', 'мак', 'просо', 'просо', 'просо', 'мак']
zolushka = list(filter(lambda x: x == 'мак', mixed))
print (zolushka)
['мак', 'мак', 'мак', 'мак', 'мак']
Функция, передаваемая в filter должна возвращать значение True или False, чтобы элементы корректно отфильтровались.
Функция reduce()
Функция reduce принимает 2 аргумента: функцию и последовательность. reduce() последовательно применяет функцию-аргумент к элементам списка, возвращает единичное значение.
Вычисление суммы всех элементов списка при помощи reduce:
from functools import reduce
items = [1,2,3,4,5]
sum_all = reduce(lambda x,y: x + y, items)
print (sum_all)
15
Вычисление наибольшего элемента в списке при помощи reduce:
from functolls import reduce
items = [1, 24, 17, 14, 9, 32, 2]
all_max = reduce(lambda a,b: a if (a > b) else b, items)
print (all_max)
32
Функция zip()
Функция zip объединяет в кортежи элементы из последовательностей переданных в качестве аргументов.
a = [1,2,3]
b = "xyz"
c = (None, True)
res = list(zip(a, b, c))
print (res)
[(1, 'x', None), (2, 'y', True)]
Функция zip прекращает выполнение, как только достигнут конец самого короткого списка.
Замыкание в Python
Одно из интересных понятий функционального программирования - это замыкания. Эта идея оказалась настолько заманчивой для многих разработчиков, что была реализована даже в некоторых нефункциональных языках программирования (Perl). Девид Мертц приводит следующее определение замыкания: "Замыкание - это процедура вместе с привязанной к ней совокупностью данных" (в противовес объектам в объектном программировании, как: "данные вместе с привязанным к ним совокупностью процедур").
Смысл замыкания состоит в том, что определение функции "замораживает" окружающий её контекст на момент определения. Это может делаться различными способами, например, за счёт параметризации создания функции, как показано:
def multiplier(n): # multiplier возвращает функцию умножения на n
def mul(k):
return n * k
return mul
mul3 = multiplier(3) # mul3 - функция, умножающая на 3
print(mul3(3), mul3(5))
Вот как срабатывает такая динамически определённая функция:
9 15
Другой способ создания замыкания - это использование значения параметра по умолчанию в точке определения функции:
n = 3
def mult(k, mul = n):
return mul * k
n = 7
print(mult(3)) #Получим 9
n = 10
mult = lambda k, mul=n: mul * k
print(mult(3)) #Получим 30
Никакие последующие присвоения значений параметру по умолчанию не приведут к изменению ранее определённой функции, но сама функция может быть переопределена.
Частичное применение функции
Частичное применение функции предполагает на основе функции N переменных определение новой функции с меньшим числом переменных M < N, при этом остальные N - M переменных получают фиксированные "замороженные" значения (используется модуль functools). Подобный пример будет рассмотрен ниже.
Функторы в Python
Сравнение замыкания, частичного определения и функтора:
def multiplier(n): # замыкания
def mul(k):
return n * k
return mul
mul3 = multiplier(3)
from functools import partial
def mulPart(a, b): # частичное применение функции
return a * b
par3 = partial(mulPart,3)
class mulFunctor: # эквивалентный функтор
def __init__(self, val1):
self.val1 = val1
def __call__(self, val2):
return self.val1 * val2
fun3 = mulFunctor(3)
print(mul3(5), par3(5), fun3(5))
Вызов всех трёх конструкций для аргумента, равного 5, приведёт к получению одинакового результата, хотя при этом и будут использоваться абсолютно разные механизмы:
15 15 15
Карринг
Карринг (или каррирование, curring) - преобразование функции от многих переменных в функцию, берущую свои аргументы по одному.
Это преобразование было введено М. Шейнфинкелем и Г. Фреге и получило своё название в честь математика Хаскелла Карри, в честь которого также назван и язык программирования Haskell.
Карринг не относится к уникальным особенностям функционального программирования, так карринговое преобразование может быть записано, например, и на языках Perl или C++. Оператор каррирования даже встроен в некоторые языки программирования (ML, Haskell), что позволяет многоместные функции приводить к каррированному представлению. Но все языки, поддерживающие замыкания, позволяют записывать каррированные функции, и Python не является исключением в этом плане.
В листинге 8 представлен пример с использованием карринга:
def spam(x, y):
print( 'arg1 =', x, ' arg2 =', y)
spam1 = lambda x: lambda y: spam(x, y)
def spam2(x):
def new_spam(y):
return spam(x, y)
return new_spam
spam1(2)(3) # карринг
spam2(2)(3)
Вот как выглядит результат этих вызовов:
arg1 = 2 arg2 = 3
arg1 = 2 arg2 = 3
Таким образом, поддержка функционального программирования в Python реализована достаточно полно, хотя и понятно, что Python не является чистым функциональным языком.
Литература
1. Филд А., Харрисон П. Функциональное программирование / А. Филд, П. Харрисон. - М.: Мир, 1993.
2. Хендерсон П. Функциональное программирование. Применение и реализация / П. Хендерсон. - М.: Мир, 1983.
3. Джонс С., Лестер Д. Реализация функциональных языков / С. Джон, Д. Лестер. - М.: Мир, 1991.
4. Ездаков А. Функциональное и логическое программирование / А. Ездаков. - М.: Бином. Лаборатория знаний, 2016.
5. Лутц М. Изучаем Python, 4-е издание / М. Лутц. - М. Символ-Плюс, 2011. - 1280 с.
6. Харрисон Д. Введение в функциональное программирование
Приложения
Функции map и zip и lambda. Python
http://ninjaside.info/blog/ru/funkcii-map-i-zip-i-lambda-python/
https://www.ibm.com/developerworks/ru/library/l-python_details_03/index.html
