Очисти код вільними монадами

Від перекладача:
Це вільний переклад статті «Purify code using free monads» Габріеля Гонзалеса, присвячений використанню вільних монад для представлення коду як синтаксичного дерева з подальшою керованої інтерпретацією.
На хабре є інші статті Габріеля — «Кооперативні потоки з нуля в 33 рядках на Хаскеле» і «Чим хороші вільні монади».
Всі зауваження перекладача виділені курсивом.
По всіх зауважень, пов'язаних з перекладом, звертайтесь в лічку.


Досвідчені програмісти на Хаскеле часто радять новачкам робити програми настільки чистими, наскільки це можливо. Функція називається чистою, якщо вона детермінована (обчислене значення однозначно визначається значеннями всіх формальних аргументів) і не має побічних ефектів (тобто не змінює стан середовища виконання). У класичній математиці, λ-числення і комбінаторної логіки всі функції чисті. Чистота надає безліч практичних переваг:
  • можна формально довести якісь властивості написаного коду,
  • крім того, можна легко оглядати код і сказати, що він робить,
  • нарешті, можна прогнати через QuickCheck.
Для демонстрації я буду використовувати таку простеньку програму
echo
:
import System.Exit

main = do x <- getLine
putStrLn x
exitSuccess
putStrLn"Finished"

У наведеній програмі, проте, є один недолік: в ній змішані бізнес-логіка і побічні ефекти. У конкретному випадку в цьому немає нічого поганого, я завжди так пишу простенькі програми, які можу цілком тримати в голові. Втім, я сподіваюся вас зацікавити прикольними штуками, які виходять, коли побічні ефекти відокремлені від бізнес-логіки.


Вільні монади
Для початку, ми повинні очистити нашу програму. Відокремити нечисті ділянки від будь-якого коду ми можемо завжди за допомогою вільних монад. Вільні монади дозволяють розділити будь-яку нечисту програму на чисте подання її поведінки і мінімальний нечистий інтерпретатор:
import Control.Монада.Free
import System.Exit hiding (ExitSuccess)

data TeletypeF x
= PutStrLn String x
| GetLine (String -> x)
| ExitSuccess

instance Functor TeletypeF where
fmap f (PutStrLn str x) = PutStrLn str (f x)
fmap f (GetLine k) = GetLine (f . k)
fmap f ExitSuccess = ExitSuccess

type Teletype = Free TeletypeF

putStrLn' :: String -> Teletype ()
putStrLn' str = liftF $ PutStrLn str ()

getLine' :: Teletype String
getLine' = liftF $ GetLine id

exitSuccess' :: Teletype r
exitSuccess' = liftF ExitSuccess

run :: Teletype r -> IO r
run (Pure r) = return r
run Free (PutStrLn str t)) = putStrLn str >> run t
run Free (GetLine f )) = getLine >>= run . f
run Free ExitSuccess ) = exitSuccess

echo :: Teletype ()
echo = do str <- getLine'
putStrLn' str
exitSuccess'
putStrLn' "Finished"

main = run echo

Переписаний таким чином код збирає нечисті дії функції
run
. Я волію називати цей процес «очищенням коду», тому що ми очищаємо всю логіку програми до чистого коду, залишаючи осторонь мінімальний нечистий залишок тільки в нашому інтерпретаторі
run
.

Докази
Здається, ми не боляче-то багато виграли від такого очищення коду, а заплатили за це задоволення безліччю рядків коду (а ще накладними витратами пам'яті та часу). Тим не менше, тепер ми можемо довести деякі властивості нашого коду використовуючи эквациональный висновок (екваціональной reasoning — висновок через еквівалентні перетворення).

Наприклад, кожен, хто читає це, напевно помітив очевидний баг у вихідній програмі
echo
:
import System.Exit

main = do x <- getLine
putStrLn x
exitSuccess
putStrLn "Finished" -- ой-ой!

Остання команда ніколи не буде виконана… чи все ж буде? Як би це довести?

Взагалі-то ми не можемо довести, що остання команда ніколи не буде виконана, тому що це не так. Автор модуля
System.Exit
міг би запросто змінити визначення
exitSuccess
на
exitSuccess :: IO ()
exitSuccess = return ()

Ця програма, як і раніше, проходить перевірку типів, але тепер вона також успішно друкує
Finished
в консоль.

А ось для нашої очищеної версії ми можемо довести, що будь-яка команда після
exitSuccess'
ніколи не буде виконана:
exitSuccess' >> m = exitSuccess'

Доведемо эквациональным висновком, цим найбільш значущим профітом очищення. Эквациональный висновок передбачає, що ми можемо взяти будь-який вираз і просто підставити у визначення функцій компонент. Кожен крок нижченаведеного докази супроводжується коментарем, який вказує на конкретне функціональне визначення, використане для переходу до наступного кроку…
exitSuccess' >> m

-- exitSuccess' = liftF ExitSuccess
= liftF ExitSuccess >> m

-- m >> m' = m >>= \_ -> m'
= liftF ExitSuccess >>= \_ -> m

-- liftF f = Free (fmap Pure f)
= Free (fmap Pure ExitSuccess) >>= \_ -> m

-- fmap f ExitSuccess = ExitSuccess
= Free ExitSuccess >>= \_ -> m

-- Free m >>= f = Free (fmap (>>= f) m)
= Free (fmap (>>= \_ -> m) ExitSuccess)

-- fmap f ExitSuccess = ExitSuccess
= Free ExitSuccess

-- fmap f ExitSuccess = ExitSuccess
= Free (fmap Pure ExitSuccess)

-- liftF f = Free (fmap Pure f)
= liftF ExitSuccess

-- exitSuccess' = liftF ExitSuccess
= exitSuccess'

Зверніть увагу, як на останніх кроках ми перевернули рівності і перейшли назад від функціонального визначення (праворуч) к визначається виразом (ліворуч). Такий прийом цілком припустимо, оскільки, завдяки чистоті, знак рівності в Хаскелле не означає присвоювання, а означає дійсно рівність! Це означає, що, розмірковуючи про коді в термінах рівності, ми можемо перекладати вираження в обидві сторони щодо знака рівності. Вражає!
Для тих, хто чув про λ-числення (від перекладача)насправді рівність у Хаскеле значить не зовсім рівність у традиційному розумінні. В λ-числення є поняття редукції — перетворення терма за певним правилом. Формально кажучи, це просто бінарне відношення на множині термів. Терм може редукуватися до декількох різних термів, і ця неоднозначність обумовлює множинність стратегій редукций (енергійна — спочатку редукується аргумент, потім вираз; лінива — спочатку все вираз, потім аргумент щодо необхідності; і тому подібні). При фіксованій стратегії редукції терм або редукується певним чином до іншого терма, або не редукується взагалі ніяк. Останній випадок називається нормальною формою терма, нами мислиться як повністю завершене обчислення. Самі редукції породжуються якимись правилами. Найбільш відомі β — і η-редукції. У певному сенсі кожне функціональне рівність (визначення функцій) виражають такі ж правила. Коли відбувається обчислення, ці правила працюють в одну сторону. Якщо правило замикається на себе, відбувається нескінченна рекурсія, на зразок
inf = inf :: a
. Тим не менш, в метатеорії ми можемо взяти це бінарне відношення і замкнути за транзитивности і симетричності, отримавши бінарне відношення редукційного рівності. По теоремі Черча—Россера редукційний рівність M=N справедливо тоді і тільки тоді, коли знайдеться терм (не обов'язково в нормальній формі) P такою, що обидва терма M і N через якесь кінцеве кількість кроків редукуються до загального значення P. От якраз про таких рівностях йде мова в цій статті.

В рівній мірі важливо і те, що вищенаведене доказ справедливо, як би ця вільна монада не інтерпретувалася. Ми можемо поміняти функцію
run
на будь-який інший інтерпретатор, в т. ч. чистий, а рівність як і раніше виконується
exitSuccess' >> m = exitSuccess'

Це означає, що ми можемо безпечно використовувати його як правило перевизначення GHC (GHC rewrite rule) для оптимізації проходу по нашій програмі:
{-# RULES
"exit" forall m. exitSuccess' >> m = exitSuccess'
#-}

...і ми можемо гарантувати, що правило буде завжди безпечно застосовано і ніколи не буде порушено.

Міркування про коді
Хотілося б довести, що наша програма завжди виводить рядок, яку вона отримує на вході. На жаль, це ми також не можемо довести, тому що це не так. Автор (the maintainer)
putStrLn
міг би в будь-який момент передумати і перевизначити
putStrLn str = return () -- найгірший автор у світі!

Насправді, ми не можемо навіть довести, що для очищеної вільної монадою версії це виконується. Функція
run
використовує той же
putStrLn
, тому програма в будь-якому випадку піддається тій же загрозі бага. Тим не менш, ми все ж можемо довести дещо про саму вільний монаде, розглядаючи її через чистий інтерпретатор:
runPure :: Teletype r -> [String] -> [String]
runPure (Pure r) xs = []
runPure (Free (PutStrLn y t)) xs = y:runPure t xs
runPure (Free (GetLine k)) [] = []
runPure (Free (GetLine k)) (x:xs) = runPure (k x) xs
runPure (Free ExitSuccess ) xs = []

Тепер ми можемо довести
runPure echo = take 1

використовуючи функцію
take
з пакету
Prelude
стандарту Haskell98. Залишаю це в якості вправи для читача, оскільки цей пост вже досить довгий.

Звернемо увагу на ще один важливий момент. Досліджуючи
echo
крізь призму чистого коду, ми виявляємо маленьку деталь, яку початково не бачили: користувач може нічого не ввести! У цьому випадку наш (останній) інтерпретатор повинен повернути порожній список, як і функція
take _ [] = []
. Эквациональный висновок примушує нас до строгості тоді, коли простого висловлювання «наша програма завжди видає ту ж рядок, яку вона отримує» не достатньо. Чим більше ви працюєте з такими рівностями, тим більше удосконалюєте навик міркування про властивості вашого коду і виявляєте помилки у ваших вихідних припущеннях.

В рівній мірі важливо і те, що еквівалентні перетворення дозволяють бачити вашу програму в абсолютно новому світлі. Ми побачили, що наша програма стала горезвісним
take 1
після пропускання через
runPure
, що означає те, що ми можемо запозичити нашу інтуїцію про функції
take
для розуміння нашої програми і виявлення таких підступних дрібних багів.

Після того, як ми виділили чисту частина коду монадою
Free
і довели його спроможність, він стає надійним ядром і нам залишилося лише скласти інтерпретатор з цього моменту. Так, поки ми не можемо повністю довести корретность всієї програми, ми могли б довести коректність все, за винятком інтерпретатора. У тій же мірі важливо і те обставина, що ми звели інтерпретатор до абсолютно мінімально піддана для атак увазі, що возволяет нам тримати його в голові і підтримувати вручну.

Тестування
Ми не можемо нічого довести про код, зануреному в монаду
IO
. А як би це можна було зробити? Можна було б сказати як-то: «якщо скомпілювати код, запустити програму і ввести якусь одну рядок, ця ж рядок буде повернута назад», але це насправді не рівняння, тому нічого суворого в такій фразі немає. Однак, ми можемо записати її як тест до нашої програми.

На жаль, тести нечистого коду не масштабуються на великі і складні програми і в тестово-залежних МП написання таких тестів займає значну частку часу всього циклу програмування.

На щастя, ми все ж можемо легко відчувати чистий код за допомогою бібліотеки QuickCheck, яка перебирає чисті затвердження та перевіряє їх на некоректність в повністю автоматичному режимі.

Наприклад, припустимо, що ви занадто ліниві, щоб доводити
runPure echo = take 1
. Ми можемо замість цього попросити QuickCheck протестувати це судження за нас:
>>> import Test.QuickCheck
>>> quickCheck (\xs -> runPure echo xs == take 1 xs)
+++ OK, passed 100 tests.

Круто! Ви можете тестувати ваш код набагато активніше, якщо він настільки чистий, наскільки можливо.

висновок
Эквациональный висновок працює тільки для чистого коду, так що чисті ділянки коду служать достовірним ядром, який ви можете:
  • перевірити на правильність, цілісність і коректність (prove soundness),
  • вивести властивості його поведінки (reason about behavior),
  • активно тестувати (aggressively test).
Ось чому ми завжди боремося за частку чистого коду в нашому коді і зводимо до мінімуму нечисті частини.
На щастя, вільна монада
Free
гарантує нам легке досягнення високого рівня чистоти, наскільки це можливо, і наимешнего кількості нечистого коду. Ось чому всі досвідчені програмісти-хаскеллисты повинні вільно володіти вільними монадами.

Подяки
Спасибі KolodeznyDiver за допомогу в перекладі.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.