Мне всегда хотелось написать серию статей по функциональному программированию для этого журнала, и я очень рад, что у меня наконец-то появилась такая возможность. Даже несмотря на то, что моя серия про анализ данных еще далека от завершения :). Не буду анонсировать содержание всей серии, скажу лишь, что сегодня мы поговорим о разных языках программирования, поддерживающих функциональный стиль и соответствующих приемах программирования.
Языки программирования, о которых не каждый знает
Я начал программировать еще в детстве, и годам к двадцати пяти мне казалось, что я все знаю и понимаю. Объектно ориентированное программирование стало частью моего мозга, все мыслимые книги о промышленном программировании были прочитаны. Но у меня оставалось такое ощущение, будто я что-то упустил, что-то очень тонкое и необыкновенно важное. Дело в том, что, как и многих в девяностые годы, в школе меня учили программировать на Pascal (о да, слава Turbo Pascal 5.5! — Прим. ред.), потом был C и C++. В университете Fortran и потом Java, как основной инструмент на работе. Я знал Python и еще несколько языков, но все это было не то. А серьезного образования в области Computer Science у меня не было. Однажды во время перелета через Атлантику я не мог заснуть, и мне захотелось что-то почитать. Каким-то волшебным образом у меня под рукой оказалась книга про язык программирования Haskell. Мне кажется, именно тогда я понял истинный смысл выражения «красота требует жертв».
Теперь, когда меня спрашивают, как я выучил Haskell, я так и говорю: в самолете. Этот эпизод изменил мое отношение к программированию вообще. Конечно, после первого знакомства многие вещи казались мне не вполне понятными. Пришлось напрячься и изучить вопрос более тщательно. И знаешь, прошло десять лет, многие функциональные элементы стали частью промышленных языков, лямбда-функции уже есть даже в Java, вывод типов — в С++, сопоставление с образцом — в Scala. Многие думают, что это какой-то прорыв. И в этой серии статей я расскажу тебе про приемы функционального программирования, используя разные языки и их особенности.
Интернетчики часто на потеху публике составляют всякие списки и топы. Например, «список книг, которые ты должен прочесть до тех пор, пока тебе не исполнилось тридцать». Если бы передо мной стояла задача сделать список книг по программированию, которые ты должен прочесть до тех пор, пока тебе сколько-то там не исполнилось, то первое место, безусловно, досталось бы книге Абельсона и Сассмана «Структура и интерпретация компьютерных программ». Мне даже иногда кажется, что компилятор или интерпретатор любого языка должен останавливать каждого, кто не читал эту книгу.
Поэтому если и есть язык, с которого нужно начинать изучение функционального программирования, так это Lisp. Вообще, это целое семейство языков, куда входит довольно популярный сейчас язык для JVM под названием Clojure. Но в качестве первого функционального языка он не особо подходит. Для этого лучше использовать язык Scheme, который был разработан в MIT и до середины двухтысячных годов служил основным языком для обучения программированию. Хотя сейчас вводный курс с тем же названием, что упомянутая книга, был заменен на курс по Python, она все еще не потеряла своей актуальности.
Постараюсь кратко рассказать о языке Scheme и вообще об идее, стоящей за языками данной группы. Несмотря на то что Lisp очень старый (из всех языков высокого уровня старше только Fortran), именно в нем впервые стали доступны многие методы программирования, применяемые сейчас. Далее я буду использовать название Lisp, имея в виду конкретную реализацию — Scheme.
Синтаксис за две минуты
Синтаксис в языке Lisp, хм, слегка спорный. Дело в том, что идея, лежащая в основе синтаксиса, крайне проста и построена на основе так называемых S-выражений. Это префиксная запись, в которой привычное тебе выражение 2 + 3 записывается как (+ 2 3). Это может показаться странным, но на практике дает некоторые дополнительные возможности. Кстати, (+ 2 10 (* 3.14 2)) тоже работает :). Таким образом, вся программа — это набор списков, в которых используется префиксная нотация. В случае языка Lisp сама программа и абстрактное синтаксическое дерево — «если вы понимаете, о чем я» 😉 — по сути, ничем не отличаются. Такая запись делает синтаксический анализ программ на Lisp очень простым.
Раз уж мы говорим о языке программирования, то следует сказать о том, как определять функции в этом языке.
Тут нужно сделать небольшое отступление. Существует одна тонкость, значимость которой в современной литературе недооценена. Нужно все-таки разделять функцию в математическом смысле и функцию, как мы ее понимаем в функциональном программировании. Дело в том, что в математике функции являются декларативными объектами, а в программировании они используются для организации процесса вычислений, то есть в каком-то смысле, скорее, представляют собой императивное знание, знание, отвечающее на вопрос «как?». Именно поэтому Абельсон и Сассман в своей книге это очень тщательно разделяют и называют функции в программировании процедурами. В современной литературе по функциональному программированию это не принято. Но я все же настоятельно рекомендую разделять эти два смысла слова «функция» хотя бы у себя в голове.
Самый простой способ определить функцию — это написать следующий код. Начнем с неприлично простого:
(define (sq-roots a b c)
(let ((D (- (* b b) (* 4 a c))))
(if (< D 0)
(list)
(let ((sqrtD (sqrt D)))
(let ((x1 (/ (- (- b) sqrtD) (* 2.0 a)))
(x2 (/ (+ (- b) sqrtD) (* 2.0 a))))
(list x1 x2))))))Да, это именно то, что ты подумал, — решение квадратного уравнения на Scheme. Но этого более чем достаточно, чтобы разглядеть все особенности синтаксиса. Здесь sq-roots — это название функции от трех формальных параметров.
На первый взгляд в конструкции let, которая используется для определения локальных переменных, слишком много скобок. Но это не так, просто сначала мы определяем список переменных, а затем выражение, в котором эти переменные используются. Здесь (list) — это пустой список, который мы возвращаем, когда корней нет, а (list x1 x2) — это список из двух значений.
Теперь о выражениях. В нашей функции sq-roots мы использовали конструкцию if. Вот здесь-то и начинается функциональное программирование.
Дело в том, что в отличие от императивных языков, таких как C, в функциональных языках if — это выражение, а не оператор. На практике это означает, что у него не может отсутствовать ветка else. Потому что выражение всегда должно иметь значение.
Нельзя рассказать про синтаксис, не поговорив о синтаксическом сахаре. В языках программирования синтаксическим сахаром называют конструкции, которые не являются необходимыми, а лишь облегчают чтение и переиспользование кода. Для начала приведем классический пример из языка C. Многие знают, что массивы не обязательное средство выражения, так как есть указатели. Да, действительно, массивы реализованы через указатели, и a[i] для языка C — это то же самое, что и *(a + i). Данный пример вообще довольно необычный, с ним связан забавный эффект: так как операция сложения остается коммутативной в случае указателей, то последнее выражение — это то же самое, что и *(i + a), а это может быть получено при удалении синтаксического сахара из выражения i[a]! Операция удаления синтаксического сахара в английском языке называется специальным словом desugaring.
Возвращаясь к языку Scheme, следует привести важный пример синтаксического сахара. Для определения переменных, как и в случае функций, используется ключевое слово (в Lisp и Scheme это называется специальной формой) define. К примеру, (define pi 3.14159) определяет переменную pi. Вообще говоря, точно так же можно и определять функции:
(define square (lambda (x) (* x x)))это то же самое, что и
(define (square x) (* x x))Последняя строчка выглядит чуть более легко читаемой по сравнению с вариантом, в котором используется лямбда-выражение. Однако понятно, что достаточно иметь первый вариант, а второй необязателен. Почему именно первый важнее? Потому что одно из самых базовых свойств функциональных языков — что функции в них являются объектами первого класса. Последнее означает, что функции можно передавать в качестве аргумента и возвращать в качестве значения.
Если посмотреть на let с точки зрения лямбда-выражения, то легко заметить следующее соответствие:
(let ((x 5) (y 2)) (* x y))
(apply (lambda (x y) (* x y)) (list 5 2))Здесь оба выражения можно считать эквивалентными, а apply просто применяет функцию к списку аргументов.
Функциональное программирование
Функциональные языки бывают чистыми и нечистыми. Чистые функциональные языки сравнительно редки, к ним относятся в первую очередь Haskell и Clean. В чистых языках нет побочных эффектов. На практике это означает отсутствие присваивания и ввода-вывода в том виде, к которому мы привыкли. Это создает ряд трудностей, хотя в уже упомянутых языках это решено довольно хитроумно, и на этих языках пишут код с большим количеством ввода-вывода. Языки типа Lisp, OCaml или Scala допускают функции с побочными эффектами, и в этом смысле данные языки зачастую более практичны.
Наша задача — изучить основные приемы функционального программирования на Scheme. Поэтому мы будем писать чисто функциональный код, без использования генератора случайных чисел, ввода-вывода и функции set!, которая позволят менять значения переменных. Обо всем этом можно прочитать в книге SICP. Сейчас остановимся на самом существенном для нас.
Первое, что смущает начинающего в функциональном программировании, — это отсутствие циклов. А как же быть? Многих из нас учат, что рекурсия — это плохо. Аргументируется это тем, что рекурсия в обычных языках программирования обычно реализована неэффективно. Дело в том, что в общем случае следует различать рекурсию как технический прием, то есть вызов функции из самой себя, и рекурсию как процесс. В функциональных языках поддерживается оптимизация хвостовой рекурсии или, как иногда говорят, рекурсии с аккумулятором. Это можно проиллюстрировать на простом примере.
Пускай у нас есть две функции — succ и prev. Первая возвращает число, на 1 большее, чем аргумент, а вторая — на 1 меньшее. Теперь попробуем определить операцию сложения, причем двумя способами:
(define (add x y)
(if (eq? y 0) x (add (succ x) (prev y))))
(define (add-1 x y)
(if (eq? y 0) x (succ (add-1 x (prev y)))))В чем разница между первым и вторым случаем? Дело в том, что если рассмотреть способ вычисления для первого случая по шагам, то можно увидеть следующее:
(add 3 4) =>
(add 4 3) =>
(add 5 2) =>
(add 6 1) =>
(add 7 0) =>
7Во втором случае мы будем иметь примерно следующее:
(add-1 3 4) =>
(succ (add-1 3 3)) =>
(succ (succ (add-1 3 2))) =>
(succ (succ (succ (add-1 3 1)))) =>
(succ (succ (succ (succ (add-1 3 0))))) =>
(succ (succ (succ (succ 3)))) =>
(succ (succ (succ 4))) =>
(succ (succ 5)) =>
(succ 6) =>
7Несмотря на то что и в том и другом случае результат одинаков, процесс вычисления кардинально отличается. В первом случае количество используемой памяти не меняется, а во втором растет линейным образом. Первый процесс является итеративным, а второй — рекурсивым. Так, для написания эффективных программ на функциональных языках нужно использовать хвостовую рекурсию для того, чтобы избежать переполнения стека.
Списки
Один из важнейших элементов функционального программирования, наряду с рекурсией, — списки. Они обеспечивают основу для сложных структур данных. Как и в других функциональных языках, списки являются односвязными по принципу голова — хвост. Для создания списка используется функция cons, а для доступа к голове и хвосту списка — функции car и cdr соответственно. Так, список (list 1 2 3) — это не что иное, как (cons 1 (cons 2 (cons 3 '()))). Здесь '() — пустой список. Таким образом, типичная функция обработки списка выглядит так:
(define (sum lst)
(if (null? lst)
0
(+ (car lst) (sum (cdr lst)))))Эта функция просто суммирует элементы списка. Так выглядят многие функции обработки списков, в одной из следующих статей я расскажу почему. А сейчас лишь замечу, что если заменить первый аргумент в сложении на 1, то получим функцию, которая вычисляет длину списка.
Функции высших порядков
Раз уж функции можно передавать как аргументы и возвращать в качестве значения, то неплохо бы найти этому применение. Рассмотрим следующий классический пример:
(define (map f lst)
(if (null? lst)
lst
(cons (f (car lst)) (map f (cdr lst)))))Функция map применяет функцию f к каждому элементу списка. Как бы это странно ни выглядело, но теперь мы можем выразить функцию вычисления длины списка length через sum и map:
(define (length lst)
(sum (map (lambda (x) 1) lst)))Если ты вдруг сейчас решил, что все это как-то слишком просто, то давай подумаем вот над чем: как сделать реализацию списков, используя функции высших порядков?
То есть нужно реализовать функции cons, car и cdr так, чтобы они удовлетворяли следующему соотношению: для любого списка lst верно, что значение (cons (car lst) (cdr lst)) совпадает с lst. Это можно сделать следующим образом:
(define (cons x xs)
(lambda (pick)
(if (eq? pick 1) x xs)))
(define (car f) (f 1))
(define (cdr f) (f 2))Как это работает? Здесь функция cons возвращает другую функцию, которая имеет один параметр и в зависимости от этого возвращает либо первый, либо второй аргументы. Легко проверить, что необходимое соотношение выполняется для этих функций.
Использование quote и метапрограммирование
Одна приятная особенность языка Lisp делает его необыкновенно удобным для написания программ, которые занимаются преобразованием других программ. Дело в том, что программа состоит из списков, а список — это основная структура данных в языке. Существует способ просто «закавычить» текст программы, чтобы она воспринималась как список атомов.
Атомы — это просто символьные выражения, к примеру ('hello 'world), что то же самое, что и '(hello world), или в полной форме (quote (hello world)). Несмотря на то что в большинстве диалектов Lisp есть строки, иногда можно обходиться quote. Что более важно, с помощью такого подхода можно упростить кодогенерацию и обработку программ.
Для начала попробуем разобраться с символьными вычислениями. Обычно под этим понимают системы компьютерной алгебры, которые способны обращаться с символьными объектами, с формулами, уравнениями и прочими сложными математическими объектами (таких систем много, основными примерами служат системы Maple и Mathematica).
Можно попробовать реализовать символьное дифференцирование. Я думаю, правила дифференцирования представляет себе каждый, кто близок к окончанию школы (хотя на самом деле все чуть сложнее — здесь мы будем вычислять частную производную, просто считая другие переменные константами, но это нисколько не усложняет суть дела).
Так что я лишь приведу пример кода, который бы показывал суть дела, детали оставлю читателю (который, как я надеюсь, тщательно изучит книгу «Структура и интерпретация компьютерных программ»).
(define (deriv exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
((product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))
(else
(error "unknown expression type - DERIV" exp))))Здесь функция deriv представляет собой реализацию алгоритма дифференцирования так, как его проходят в школе. Данная функция требует реализации функций number?, variable? и так далее, которые позволяют понять, какую природу имеет тот или иной элемент выражения. Также нужно реализовать дополнительные функции make-product и make-sum. Здесь используется пока неизвестная нам конструкция cond — это аналог оператора switch в таких языках программирования, как C и Java.
Перед тем как мы перейдем к реализации недостающих функций, стоит отметить, что в функциональном программировании довольно часто используется top-down подход к разработке. Это когда сначала пишутся самые общие функции, а затем небольшие функции, отвечающие за детали реализации.
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (make-sum a1 a2) (list '+ a1 a2))
(define (make-product m1 m2) (list '* m1 m2))
(define (sum? x)
(and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))
(define (product? x)
(and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))Реализация данных функций не требует специальных комментариев, за исключением, может быть, функций cadr и caddr. Это не что иное, как функции, которые возвращают второй и третий элементы списка соответственно.
Если воспользоваться интерактивным интерпретатором Scheme, то легко убедиться, что полученный код работает правильно, но без упрощения выражений:
(deriv '(+ x 3) 'x) =>
(+ 1 0)
(deriv '(* (* x y) (+ x 3)) 'x) =>
(+ (* (* x y) (+ 1 0))
(* (+ (* x 0) (* 1 y)) (+ x 3)))Для тривиальных случаев (например, умножение на 0) задача упрощения решается довольно легко. Этот вопрос остается читателю. Большинство примеров в этой статье взяты из книги SICP, поэтому в случае возникновения трудностей можно просто обратиться к источнику (книга находится в открытом доступе).
Как и любой диалект, Lisp имеет большие возможности в метапрограммировании, по большей части связанные с использованием макросов. К сожалению, этот вопрос требует разбора в отдельной статье.
Давай напишем функцию, которая будет удалять синтаксический сахар из определения функции так, как это обсуждалось ранее:
(define (desugar-define def)
(let ((fn-args (cadr def))
(body (caddr def)))
(let ((name (car fn-args))
(args (cdr fn-args)))
(list 'define name (list 'lambda args body)))))Эта функция прекрасно работает с правильно сформированными определениями функций:
(desugar-define '(define (succ x) (+ x 1))) =>
(define succ (lambda (x) (+ x 1)))Однако это не работает для обычных определений, таких как (define x 5).
Если мы хотим удалить синтаксический сахар в большой программе, содержащей множество различных определений, то мы должны реализовать дополнительную проверку:
(define (sugared? def)
(and (eq? (car def) 'define)
(list? (cadr def))))Такую проверку можно встроить прямо в функцию desugar-define, сделав так, чтобы в случае, если определение не нуждается в удалении синтаксического сахара, оно просто бы не менялось (данное тривиальное упражнение остается читателю). После чего можно обернуть всю программу в список и использовать map:
(map desugar-define prog)Заключение
В данной статье я не ставил себе задачу рассказать про Scheme сколь-нибудь подробно. Мне прежде всего хотелось показать несколько интересных особенностей языка и привлечь читателя к изучению функционального программирования. Этот чудесный язык при всей его простоте имеет свое очарование и особенности, которые делают программирование на нем очень увлекательным. Что касается инструмента для работы со Scheme, то сильные духом могут замахнуться на MIT-Scheme, а остальные — пользуйтесь прекрасной учебной средой Dr. Racket. В одной из следующих статей я обязательно расскажу, как написать собственный интерпретатор Scheme.
