Функциональное программирование для землян — функции



    В статье про 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
    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 26
    • +1
      У вас ошибка в статье:

      # y = k * x + b
      def get_linear(k, b):
      return lambda x: k * x + b

      # y = k * x^2 + b
      def get_linear(k, b):
      return lambda x: k * x ** 2 + b

      Вторая функция видимо должна называться get_poly2 что-ли
      • +1
        да, спасибо, поправил
      • +1
        >> shifter, x_scaler, y_scaler, combine — это функции второго порядка, т.к. они принимают не только скалярные аргументы, но и другие функции

        Вроде как, функции, которые принимают как параметры другие функции, называются функциями высшего порядка. Функции второго порядка это тоже самое что функции высшего порядка?

        • 0
          Разумеется. Функция второго порядка принимает «обычные» функции (первого порядка), хотя можно написать фукнцию например третьего порядка, которая принимает функцию второго (которая, в свою очередь, принимает функцию первого)
          • 0
            Функции первого, второго и т.д. порядков — это терминология из ФП или «самоназвание»? Обычно в документации упоминаются только функции высшего порядка. Может стоит определиться уточнить термины, что бы не было путаницы?

            Кстати, гугл тоже ничего не знает о ваших функциях :)
            • 0
              Не знаю, возможно «самоназвание», я лишь пояснил, что имел в виду автор
              • 0
                Гугл слишком молодой. Недавно попадалась книжка (к сожалению, было совсем неинтересно запоминать её название и автора) по какой-то высокой математике, в которой были даны примерно такие определения:
                Функция, оперирующая скалярами — 1 порядок.
                Функция, среди аргументов которой есть функция n порядка, или она таковую возвращает, — n+1 порядок.
                Высший порядок — n>=2.
                Дальше я ту книжку не читал, но там ещё много страниц про функан было.
            • 0
              Да, вы правы, есть термин «функции высшего порядка» :) Исправил. «Функции первого порядка» — тоже вроде как нет такого понятия, поэтому я их изменил на «простые функции»
            • +2
              Заметок по функцианальному программированию не хватает на хабре.

              А ведь тема очень интересная, и если другие языки/парадигмы способствуют идеям написать свою web-framework, компилятор под .net/java, своё мегакрутое ORM или флейму императивный C# vs. императивная Java, то ФМ способствует тому, что программист начитает интересоваться lambda-исчеслением, мат.логикой/исчеслением секвенций, системой категорий и автоматическими системами доказательств. По мойму это здорово.

              Сам в последние время занимаюсь прикладным программированием на nemerle (гибридный язык) активно используя алгебраические типы данных, pattern matching и стремясь к чистоте методов, функций; а так же читаю статьи про ФП (в основном haskell) и очень хочится во всем этом разобраться и попробывать haskell, так как начинаю видеть, что решения на нем получаются более правильными и простыми. Тем, кто только начинает погружаться в мир ФП рекомендую блоги: thesz, deni-ok, рекулярно читать lambda-the-ultimate, а так же познакомиться с статьей Евгения Кирпечева про монады и статьей про многопоточное программирование здесь.
              • 0
                Хочу попробовать написать серию статей про Хаскель, так как информации практической недостаточно, всё сводится к объяснениям монад и достаточно тривиальным примерам, к которым большинство относится достаточно скептически.
                А вот примера разработки какой-нибудь несложной программы, но с многопоточностью и ГУИ, я не видел.
                • 0
                  Думаю интересно будет проиллюстрировать возможности haskell на примере создания простого языка и реазизации парсера, интерпритатора.
              • +1
                спасибо, статья хорошая, хотя оценки не совсем адекватны.
                очень жду продолжения и надеюсь что вы вскорее сможете ее перенести в блог пайтона.
                  • 0
                    Очень интересная серия, благодарю за ссылку
                  • +2
                    На rsdn'e есть хорошая статья «Функциональное программирование для всех»: rsdn.ru/article/funcprog/fp.xml
                    • 0
                      В последнее время про функционарное программирование упоминается все чаще.
                      Возврат к старым традициям?
                      • 0
                        … и это не может не радовать. Все больше языков перенимают эти возможности, которые доступны программистам на Lisp или Haskell. Наконец-то рекурсия начинает становиться не чем-то непозволительно дорогим, а вполне рядовым инструментом программиста. Некоторые рантайм-окружения уже даже поддерживают оптимизацию хвостовой рекурсии (тот же CLR, например). На мой взгляд, производительность современных компьютеров дошла до той точки, когда можно применять данные методы без сильной оглядки на производительность.

                        Увы, некоторые возможности не будут реализованы еще долго — например, те же макры из Lisp. Если такое встроить в какой-нибудь C#, то по производительности это будет хуже, чем рекурсия во времена четырехкилобайтного стека.
                        • +2
                          С последнем пунктом вы ошибаетесь. Макры идеально встроены в язык nemerle (очень похожий на C#), но в котором бОльшая часть языковых конструкций, таких, как for, if, while,… — макросы. В nemerle можно легко определять свои макросы и тем самым расширять язык. Сами макросы в немерле раскрываются на этапе компиляции и поэтому производительность не падает.
                          • 0
                            Ух ты, вы меня заинтересовали! Обязательно посмотрю, спасибо.
                        • 0
                          Кроме всего прочего, функциональный код лучше подходит для автоматического исполнения многопоточно. А Intel/AMD сейчас пропагандируют многоядерность.
                        • 0
                          Для полноты стоит ещё упомянуть модуль functools.
                          • 0
                            Спасибо за статью, стало более-менее понятно что ФП из себя представляет.

                            Вы не затронули тему применения. Для каких задач используется ФП?
                            • 0
                              Как я и написал, с чистым ФП я дела не имел. Здесь, как я вижу, есть любители Хаскелла, они могут рассказать подробней.

                              Я занимался с Lisp, а Lisp — это мультипарадигменный язык. Самое сложное и красивое, что мне удавалось реализовать при помощи функционального стиля и что я ни за что не стал бы делать в императивной форме (поскольку мне дорог мой мозг как память) — это задача о семи ферзях. Она очень изящно реализуется рекурсией на списках. Кода не просите, т.к. это было очень давно. Могу лишь подсказать, что это была задача из SICP.

                              А так — ну это ж как бы не обязывающий ни к чему стиль программирования. Т.е. это можно использовать наряду с ООП и структурным подходом, если оно к месту.

                              На мой взгляд, ООП больше пригодна для программирования сверху-вниз (top-down design, т.е. когда сначала реализуется общая структура системы, а затем уточняются ее детали, реализуются методы и т.п.), в то время как функциональный стиль больше способствует подходу снизу-вверх (bottom-up design, когда сначала пишутся маленькие кусочки будущей системы, а потом синтезируются все более сложные ее части).

                              Так что, как заключение, я могу сказать что ФП — такой же стиль программирования, доступный каждому продвинутому программисту. Чтобы развеить «мифы» о том, что функциональный стиль и Lisp — чистое теоретизирование, могу посоветовать почитать книгу P. Siebel. Practical Common Lisp, а также M. Pilgrim. Dive Into Python (последняя не конкретно про функциональный стиль, но автор очень умело его использует, на мой взгляд; крайне советую почитать).
                            • –1
                              Поскольку я одно время довольно плотно занимался с Lisp, я хотел бы немножко рассказать об этом.


                              Я занимался с Lisp, а Lisp — это мультипарадигменный язык.


                              Небольшой урок русского языка.
                              Чем вы занимались с Lisp? Заниматься можно с Катей, Светой и т.п. Правильно говорить «занимался Lisp».
                              • 0
                                Очень здорово, сейчас как раз делаю диплом на Python, работаю с алгоритмами, где фп очень хорошо применимо. Материалов по фп в Python немного, так что жду продолжения.
                                • 0
                                  Спасибо за статью. ))

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.