ФП: lazy evaluation — это завтрашние результаты вычисления функций уже сегодня.
После вводной статьи о ФП впору переходить к демонстрации конкретных примеров, приемов и трюков.
Сегодняшняя статья будет посвящена ленивым вычислениям (lazy evaluation). Оставайтесь с нами, и вы увидите, как функция может использовать в качестве аргумента результаты своей работы.
В качестве языка для иллюстрирования взят Haskell. От читателя не требуется знания Haskell или его синтаксиса.
Рассмотрим такую задачу: дан текст, в котором используются специальные слова @label и @ref. С помощью @label определяются метки, а с помощью @ref делаются ссылки на них. Например, так:
Введение@label{intro}. Как известно, чушь бывает разная: зеленая (@ref{green}) и красная (@ref{red}).
...
Как мы уже отмечали (@ref{intro}), чушь бывает разная, и именно поэтому жизненно важно ...
...
Чушь красная@label{red}.
Не следует путать с чушью зеленой (@ref{green}).
...
Чушь зеленая@label{green}.
Радикально отличается от чуши красной (@ref{red}).
...
Нам необходимо написать программу, которая заменит метки их номером (в виде «[1]», «[2]», ...), а ссылки — текстом «см. [1]». Из нашего образца должно получиться:
Введение[1]. Как известно, чушь бывает разная: зеленая (см. [2]) и красная (см. [3]). ... Как мы уже отмечали (см. [1]), чушь бывает разная, и именно поэтому жизненно важно ... ... Чушь красная[2]. Не следует путать с чушью зеленой (см. [3]). ... Чушь зеленая[3]. Радикально отличается от чуши красной (см. [2]). ...
Классический алгоритм таков: проходим по тексту, собирая метки в порядке следования и назначая им номера. Проходим второй раз, заменяя метки и ссылки на вычисленые номера. Второй проход необходим, т.к. нам могут встретиться ссылки на метки, определенные дальше по тексту. Будем програмировать «сверху вниз»:
> module Main where > import Data.List > import Text.Regex.Posix > import Control.Arrow > > main = do > txt <- readFile "sample.txt" > let numbering = collectLabels txt > let result = replaceLabels numbering txt > writeFile "sample.out" result
Тут txt, numbering и result — это не имена переменных, а имена, связанные (bound) с выражениями. Другими словами мы можем использовать numbering для того, чтобы быстро сослаться на результат применения функции collectLabels к выражению, связанному с именем txt. Можно связывать имена со значениями несколько раз, при этом более «вложенное» связывание перекрывает внешнее (как и в случае с именами локальных переменных в императивных языках программирования).
Поскольку мы идем «сверху вниз» и реализации collectLabels и replaceLabels у нас еще нет, так и напишем:
> collectLabels = undefined > replaceLabels = undefined
Сохраняем наше творчество в файл «labeling.hs». Запускаем ghci (интерактивную среду, прилагающуюся к компилятору GHC), в появившемся промпте вбиваем «:load labeling.hs».
Ура, наша программа компилируется, хотя ничего разумного пока еще не делает. Мы еще не знаем, как именно будут реализованы функции collectLabels и replaceLabels, поэтому их тело состоит из одного примитива undefined. Использование undefined позволяет нам по ходу написания проверять правильность того, что мы пишем, начиная с самых первых строк. Как минимум, мы можем проверять, что компилятору удается выполнить вывод типов (type inference), т.е. определить, какой тип у всех выражений и функций, использованых в нашей программе, и проверить эти типы на соответствие друг другу (type checking).
Компиляторы C++/Java всегда выполняют проверку типов, но возможности вывода типов у них сильно ограничены. Упражнение номер один для пытливого читателя — написать минимальный компилирующийся «скелет», аналогичный приведеному, на C++/Java.
Начнем со сбора меток. Нам нужно найти в тексте все вхождения @label{xxx} в порядке упоминания и сложить их в какую-то структуру данных. Например, в список. Для извлечения текста используем сравнение с регулярным выражением:
> collectLabels txt =
> let matches = ( txt =~ "@label\\\\{([^}]*)\\\\}" :: [[String]] )
> in map (!!1) matches
Явно указывая тип возвращаемого значения для ф-ии (=~), мы заставляем библиотеку Text.Regex.Posix выбирать один из многих вариантов представления результата сравнения с регулярным выражением (всего их более [весь_текст_совпадения, текст_группы_1, текст_группы_2, ...] для каждого совпадения с образцом. Пример ожидаемого результата: [["@label{ccc}","ccc"],["@label{bbb}","bbb"]].
В каждом списке-результате нас интересует второй элемент — имя метки. Ф-ия извлечения элемента списка по номеру имеет имя (!!) — например, второй элемент списка lst можно получить выражением lst!!1. Поскольку нам надо применить операцию ко всем результатам, воспользуемся ф-ией map и приемом, называемым «частичное применение» (partial application или currying).
Чтобы этот кусок кода было проще понять, обратимся к ghci. Используем его для того, чтобы поиграться с кусками кода и лучше понять, что именно они делают:
<u>Можно просто проверить, совпала строка с регулярным выражением или нет</u>
<b>*Main> "@label{aaa} some text @label{bbb} some more text" =~ "@label\\{([^}]*)\\}" :: Bool</b>
True
<u>... или получить полный текст всех совпадений</u>
<b>*Main> "@label{aaa} some text @label{bbb} some more text" =~ "@label\\{([^}]*)\\}" :: [String]</b>
["@label{aaa}","@label{bbb}"]
<u> ... или полный текст всех совпадений, плюс - текст всех подгрупп</u>
<b>*Main> let matches = "@label{aaa} some text @label{bbb} some more text" =~ "@label\\{([^}]*)\\}" :: [[String]]</b>
[["@label{aaa}","aaa"],["@label{bbb}","bbb"]]
<u>... из которого потом можно извлечь либо текст совпадения</u>
<b>*Main> map (!!0) matches</b>
["@label{aaa}","@label{bbb}"]
<u> ... либо содержимое первой подгруппы.</u>
<b>*Main> map (!!1) matches</b>
["aaa","bbb"]
<u>Кроме того, мы можем посмотреть, что компилятор думает о типе определенного выражения:</u>
<b>*Main> :type map (!!1)</b>
map (!!1) :: [[a]] -> [a]
Если вы использовали функцию map в Perl, Python или Ruby, то знаете, что ей нужно давать функцию от одного аргумента. В то же время (!!) — это функция от двух аргументов (список и позиция_в_списке). Однако, если функции (!!) дать всего один аргумент, то в результате получится новая функция от одного аргумента. Это и есть частичное применение.
Особо обратите внимание на последний пример: используя информацию о том, что (!!) возвращает элемент списка, компилятор самостоятельно вычислил, что выражение-функция map (!!1) будет преобразовывать список списков в список просто значений. Самостоятельно посмотрите на тип функций map, (!!) и (!!1), чтобы понять, как именно компилятор произвел вывод. Подобный алгоритм выведения типов используется также в языках Clean, ML, OCaml, Scala, Nemerle, D. Ожидается, что вывод типов появится в C# 3.0 и Perl 6 (помните, что я говорил о влиянии ФП на mainstream языки?).
Как мы видим, функции не только могут быть использованы в качестве аргументов в вызовах функций, но и могут быть результатами вычисления выражений. В этом смысле функции ничем не отличаются от прочих базовых типов языка — чисел, символов, списков. Говорят, что функции являются полноправными сущностями (first-class citizens). В качестве упражнения номер два можете попробовать определить на C++/Java аналоги функций map и !! так, чтобы их можно было комбинировать в стиле map (!!1) и самостоятельно сделать вывод о том, являются ли функции полноправными сущностями в этих языках.
Проверим наш код:
<b>*Main> collectLabels "some text@label{one} with labels@label{two}\nand several lines@label{three}"</b>
["one","two","three"]
Быстро закрепим пройденый материал: мы увидели кусок программы на функциональном языке Haskell. Язык — со строгой типизацией (как в C++/Java), что не мешает существованию интерактивной среды исполнения (interactive top-level), как в Python. Для создания программы используется создание новых функций путем комбинирования библиотечных функций, и функций, определенных пользователем. Отсуствие изменяемых переменных (mutable variables) пока что сильно не мешает.
Теперь напишем замену меток и ссылок номерами. Имена меток у нас уже собраны в список. Номер, на который надо заменять метку — это ее позиция в этом списке. Нам надо пройтись по всему тексту, находя специальные слова и заменяя их номерами.
Нам нужно разделить исходный текст на строки, которые в свою очередь разбить на слова. Среди слов нам надо найти «специальные» и заменить их на номера, после чего собрать слова в строки, а строки — в текст. Так и запишем:
> replaceLabelsUgly labelList txt = unlines ( map unwords ( map (map process) ( map words ( lines txt )))) > where process = undefined
Люди, страдающие лиспофобией, уже бьются в припадке и хрипят «Скобки! Уберите скобки! Опять эти чертовы скобки! ». Пожалуй, они в чем-то правы. Перепишем эту функцию так:
> replaceLabelsBetter labelList txt = unlines $ map unwords $ map (map process) $ map words $ lines txt > where process = undefined
Уже лучше. «Прикольный синтаксический наворот» — скажут многие. Однако, это не выверт в синтаксисе языка. Тут использована функция ($), которая объявлена как инфиксный оператор и определена так:
f $ x = f x
Получается, что $ — это такой способ композиции функций, только и всего. И в самом деле, легко убедиться, что f (g x) = f $ g x. Можно даже взять и переписать функцию replaceLabels с использованием композиции функций в чистом виде:
> replaceLabelsPointfree labelList = unlines . map unwords . map (map process) . map words . lines > where process = undefined
Обратите внимание, что в этой форме записи у replaceLabelsPointfree стало на один аргумент меньше, как это и происходит в математической нотации. Мы пишем f(x) = ... и g(x) = ..., но t = f . g.
Впрочем, тут могут объявится любители Ruby и сказать «все равно эта функция записана криво и непонятно. Что за дела? Чтобы ее понять, надо читать ее с конца. То ли дело запись вида txt.to_lines().map({|l| l.words()}).map ..., которую можно нормально прочесть слева направо».
Что ж перепишем так, чтобы нормально читалось слева направо:
-> replaceLabels labelList = lines >>> map words >>> map (map process) >>> map unwords >>> unlines -> where process = undefined
Как можно догадаться, (>>>) — это еще одна функция, позволяющая записать композицию ф-ий вот так, «шиворот навыворот», в виде, напоминающем shell pipes из Unix-а.
Ну, тут уже явно возмутятся даже те, кто честно пытался вникнуть в написанное без перенесения на Haskell опыта работы со своим любимым языком программирования. «И это называется нормально?» — скажут они. «Тут же нифига не понятно!».
Ну, раз непонятно, надо «мерять хвост частями» с помощью ghci:
<b>*Main> lines "this is a\nsample\nmultiline text"</b>
["this is a","sample","multiline text"]
<b>*Main> lines >>> map words $ "this is a\nsample\nmultiline text"</b>
[["this","is","a"],["sample"],["multiline","text"]]
<b>*Main> lines >>> map words >>> map unwords $ "this is a\nsample\nmultiline text"</b>
["this is a","sample","multiline text"]
<b>*Main> lines >>> map words >>> map unwords >>> unlines $ "this is a\nsample\nmultiline text"</b>
"this is a\nsample\nmultiline text\n"
Теперь осталось разобраться с тем, что стоит между map words и map unwords. Если process w проверяет, не является ли слово w специальным, и заменяет его на номер, то map process ws выполнит эту операцию для всех слов в ws. Если ws — это список слов, стоявших в одной строке, то нам осталось применить эту операцию ко всем строкам текста, чтобы обработать его полностью. Для этого и нужен второй, внешний map. Получаем, что обработка все слов текста — это и есть map (map process).
Быстро закрепим пройденый материал: мы увидели, как возможность объявлять функции инфиксными операторами с нужным приоритетом позволяет гибко создавать новые управляющие конструкции языка и, фактически, создавать удобный нам синтаксис. Прослеживается типичный шаблон (pattern) програмирования на функциональных языках — создание «конвейера» из функций, последовательно применяющих к исходным данным ряд преобразований для получения конечного результата.
Нам осталось определить функцию process. Она должна работать следующим образом: все слова вида @label{xxx} заменять на «[номер метки xxx]», все слова @ref{xxx} заменять на «см. [номер метки xxx]», а все прочие слова — не трогать. С вашего позволения, я сразу приведу соответствующих код, без подробных объяснений.
> replaceLabels labelList = lines >>> map words >>> map (map process) >>> map unwords >>> unlines
> where process w | isInfixOf "@label{" w = replace "" w
> | isInfixOf "@ref{" w = replace "see " w
> | otherwise = w
>
> -- Эта функция заменяет ссылку/метку в слове `w' на ее [номер], предваряя [номер] строкой `prepend'
> replace prepend w =
> -- Слово "Введение@label{aaaa}." будет разбито на части "Введение", "aaa" и ".",
> -- из которых мы потом соберем результат.
> let [[_,prefix,label,suffix]] = ( w =~ "(.*)@.*\\\\{([^}]*)\\\\}(.*)" :: [[String]] )
> in prefix ++ prepend ++ "[" ++ idx label ++ "]" ++ suffix
>
> -- Возвращает позицию `l' в списке `labelList' (нумерация начинается с 1).
> idx l = case elemIndex l labelList of
> Just x -> show (x+1)
> Nothing -> error $ "Label "++l++" is not defined"
Я надеюсь, что даже минимальный опыт работы с python и ruby позволит без особого напряжения прочесть и понять этот код. Возможно, вам также поможет пример функции, которая для четных аргументов возвращает «fuzz», а для нечетных — «buzz»:
fuzzbuzz x | even x = "fuzz" | odd x = "buzz" | otherwise = "something is odd ..."
Проверим наш код:
<b>*Main> main</b>
В файле «sample.out» должен оказаться текст с замененными ссылками.
Тут самое время спросить: «НУ И ЧТО?». Казалось бы, до сих пор мы не сделали ничего необычного и отличающегося от того, что мы делали бы при программировании на любом другом императивном языке. Ну, разве что, обошлись без переменных :)
Наберитесь еще немного терпения, мы уже подобрались «гвоздю программы». Попробуем соединить сбор меток и замену ссылок в одну функцию. Предположим, что у нас уже есть полученый каким-то волшебным образом список всех меток в документе, назовем его allLabels. Откуда он взялся? А черт его знает. Допустим, мы сами прислали его себе из будущего, из того момента, когда мы уже обработали весь файл и знаем полный список меток :)
По-прежнему будем обрабатывать текст по словам, но чуть-чуть изменим алгоритм: если в слове есть ссылка, то использует allLabels для вычисления ее номера. Если же в слове есть метка, то используем allLabels для вычисления ее номера и добавим метку в список labelList. Зачем нам нужен labelList? Ну, должен же откуда-то взяться в будущем список меток, который мы пошлем себе в прошлое :)
Вашему вниманию предлагается функция process' (апостроф — это допустимый символ в имени функции), которая обрабатывает слово w, используя словарь меток allLabels и аккумулятор labelList, куда мы добавляем все найденые метки.
> process' (_,labelList,allLabels) w
> | isInfixOf "@label{" w = replace "" True
> | isInfixOf "@ref{" w = replace "see " False
> | otherwise = (w, labelList, allLabels)
>
> -- Заменяем ссылку/метку в слове `w' на ее номер, предваряя его строкой `prepend'. Если `add' == True,
> -- добавляем метку в список labelList
> where replace prepend add =
> let [[_,prefix,label,suffix]] = ( w =~ "(.*)@.*\\\\{([^}]*)\\\\}(.*)" :: [[String]] )
> labelList' = if add then (label:labelList) else labelList
> in (concat [prefix, prepend, "[", idx label,"]", suffix], labelList', allLabels)
>
> idx l = case elemIndex l allLabels of
> Just x -> show (x+1)
> Nothing -> "Label "++l++" is not defined"
Кроме того, несколько изменим процесс обработки всего текста: вместо того, чтобы превращать его в список списков слов, превратим его в «плоский» список слов, который будет удобно обработать функций process'. Чтобы можно было собрать текст обратно, сохранив разбиение на слова, свяжем в с каждым словом номер строки, в которой оно (слово) стояло. После замены ссылоку/меток собирем слова в цельный текст, используя сохраненную информацию о том, какие слова были в какой строке.
> process = combineFromWords . replaceLabels . splitToWords > where > splitToWords txt = unzip $ concat $ zipWith tagWords [1..] $ lines txt > replaceLabels (tags, ws) = zip tags (processWords ws) > combineFromWords ws = unlines $ map (unwords . map snd) $ groupBy (comparing fst) ws > tagWords lineNo line = zip (repeat lineNo) (words line) > comparing f a b = (f a) == (f b)
Пару примеров для облегчения понимания этого куска (используйте ghci, чтобы увидеть типы и «попробовать на зуб» все функции, которые я не упомянул в этих примерах):
<b>*Main> zip [1..] $ lines "aaa bbb ccc\nddd eee fff"</b>
[(1,"aaa bbb ccc"),(2,"ddd eee fff")]
<b>*Main> let l = zipWith (\lineNo line -> zip (repeat lineNo) (words line)) [1..] $ lines "aaa bbb ccc\nddd eee fff"</b>
[[(1,"aaa"),(1,"bbb"),(1,"ccc")],[(2,"ddd"),(2,"eee"),(2,"fff")]]
<b>*Main> unzip $ concat l</b>
([1,1,1,2,2,2],["aaa","bbb","ccc","ddd","eee","fff"])
А теперь, собственно, создадим нашу «машину времени» — функцию, которая получит результаты работы функции process' (собраный списко меток) и «отправит его в прошлое» — передаст в качестве аргумента ... самой функции process'.
> processWords ws =
> -- Из списка слов ["@label{aaa}","@ref{aaa}","ccc"] получаем список
> -- [ ("[0]",["aaa"],все_метки_из_будущего)
> -- , ("см [0]", ["aaa"], все_метки_из_будущего)
> -- , ("ccc", ["aaa"], все_метки_из_будущего)
> -- ]
> -- Нас интересует последий элемент этого списка, который содержит список всех найденых меток
> let result = drop 1 $ scanl process' ([],[],reverse collectedLabels) ws
> -- Извлекаем список найденых меток, чтобы использовать его ...
> -- ... в предыдущей строке в качестве аргумента для process' !
> (_,collectedLabels,_) = last result
> -- Конечным результатом является список обработаных слов, без информации о найденых метках.
> in map discardLabelLists result
> where discardLabelLists (w,_,_) = w
Чтобы проверить, что этот код действительно работает, изменим функцию main:
> main' = do > txt <- readFile "sample.txt" > writeFile "sample.out" $ process txt
Выполнив main', вы можете убедиться, что все метки и ссылки в действительности были заменены номерами. Черная магия? Отнюдь. Но как ...?
Использование в вычислениях еще не посчитаных значений становится возможным благодаря так называемой «ленивой» схеме вычислений (lazy evaluation) выражений в языках функционального программирования. При использовании этой схемы результатом выражения let y = ((f x) + (g x)) является не фактическая сумма, а что-то вроде ссылки на код, который эту сумму посчитает, когда нам понадобится значение y (я намерено опускаю технические детали). Если значение нам не понадобится — то и вычисление фактически не произойдет.
Таким образом, даже если вставить в произвольное место программы выражение let foobar = sum ( map (^2) [1..1000000000] ), можно не боятся, что программа будет тратить время на подсчет суммы квадратов всех чисел от одного до ста миллионов. Если мы нигде явно или косвенно не используем символ foobar, то это вычисление просто не произойдет.
Возвращаясь к нашему коду, становится понятно, что использование функции idx l не приводит к фактическому немедленному поиску метки l в списке allLabels. Вместо него создается «замороженный код» (thunk), который произведет этот поиск тогда, когда в нем будет необходимость. А необходимость эта появляется аж в самом конце программы, когда мы выводим результат обработки в выходной файл. Естественно, в этот момент времени у нас уже есть полный список меток, использованых в обрабатываемом тексте.
Получается, что я всех обманул — мы не отправляем «в прошлое» результаты вычислений, мы как бы «отправляем в будущее» сами вычисления с пометкой «до востребования».
Прошу не считать эту статью поводом для очередной священной войны — она не писалась в рассчете на это. Я просто надеюсь, что этот текст послужил для вас хорошей пищей для размышлений и поводом присмотреться поближе к функциональному програмированию.
Да, а чтобы вы не думали, что использованый мной прием — искуственный и редковстречающийся, вот вам еще практических примеров из этой же категории:
-- Функция `fib' возвращает список чисел Фибоначчи fib = 1:1:(zipWith (+) fib (tail fib)) -- Функция `primes' возвращает список простых чисел primes = primes' [2..] where primes' (n:ns) = n : primes' [ y | y <- ns, y `mod` n /= 0] -- Функция ralign выравнивает список строк вправо: ralign xs = [ rjustify m x | x <- xs ] where m = maximum [ length x | x <- xs ] rjustify m x = replicate (m - length x) ' ' ++ x
Если эта статья вызовет интерес, то в следующих выпусках нашей программы ожидайте: работа с бесконечными списками и бесконечными структурами данных, зачем нужны в реальной жизни катаморфизмы (foldr) и анаморфизмы (unfoldr) списков и многое другое :)
PS
Текст этой статьи можно сохранить в файл с суффиксом «.lhs» (literate Haskell), и его можно будет без изменений загружать и исполнять в ghci как программу.
PPS
Ссылки для самостоятельного чтения:
- Перечень учебных текстов по Haskell на Haskell Wiki. Беззастенчивая реклама: «Hitchhickers guide to Haskell» написан вашим покорным слугой.
- Wikibook по Haskell
- OCaml Tutorial
anonymous
Ruslan Shevchenko
Sergiy Matusevych
Kostiantyn Sokolinskyi
Artur Rakytskyi
Dmitry Astapov
Sergii Voloshyn
61 коментар
Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.