Монады

Эта глава не является обязательной (кроме раздела про обещания), но внимательное её изучение может расставить точки над i и помочь в написании более простого кода.

Стиль передачи продолжений

В современном программировании всё чаще и чаще встречаются ситуации, в которых классический механизм возврата значения из функции недостаточно гибок (обработка возможных ошибок в процессе исполнения) или же вообще недоступен (асинхронные вычисления).

Стандартный выход в такой ситуации – стиль передачи продолжений (Continuation Passing Style): вместо возвращения результата работы «наверх» при помощи return, этот результат явно передаётся некоторой другой функции – продолжению. Например, вот так можно представить стандартную процедуру вычисления числа Фибоначчи:

function fib(n, cont) {
    if (n < 2) { return cont(n) }  
    // return здесть _только_ для того, чтобы else не писать;
    // возвращаемое fib значение -- undefined

    fib(n-1, function (f_nm1){
        fib(n-2, function (f_nm2) {
            cont(f_nm1+f_nm2)
        })
    })
}

Как нетрудно заметить, такой стиль несколько отличается от «классического»

function fib(n) {
    if (n < 2) { return n }
    
    let a = fib(n-1)
    let b = fib(n-2)
    return a + b
}

Если кажется, что отличие состоит лишь в дополнительном аргументе, приведём пример асинхронного «параллельного» вычисления чисел Фибоначчи:

function Async(action) {
    let computation = {
        finished: false,
        result: null,
        subscriptions: []
    }

    setTimeout(function() { 
        action(function(result) {
            computation.result   = result
            computation.finished = true
            let subs = computation.subscriptions
            computation.subscriptions = undefined
            for (s of subs) { s(result) }
        })
    })

    return computation
}

function subscribe(async, cont) {
    if (async.finished) { return cont(async.result) }

    async.subscriptions.push(cont)
}

function fib(n, cont) {
    if (n < 2) { return cont(n) }

    let af_nm1 = Async(function(c) {fib(n-1,c)})
    let af_nm2 = Async(function(c) {fib(n-2,c)})

    subscribe(af_nm1, function(f_nm1) {
        subscribe(af_nm2, function(f_nm2) {
            cont(f_nm1+f_nm2)
        })
    })
}

Это тоже разновидность стиля передачи продолжений, правда, существенно более хитрая.

Монады приходят на помощь

В начале 90-х годов прошлого века Eugenio Moggi опубликовал статью, в которой большое количество различных (и на первый взгляд не слишком связанных между собой) моделей вычислений были представлены как частный случай понятия монады – одной из алгебраических структур, рассматриваемых теорией категорий.

Мы не будем сейчас углубляться в математическую сторону вопроса (она не слишком сильно связана с практической). Вместо этого сразу перейдём к практической стороне.

Монадой называется тип данных Foo с унарным конструктором (назовём его тоже Foo) и унарным методом .then, принимающим на вход генератор объектов типа Foo (функцию, возвращающую объект типа Foo). Метод .then должен обладать следующей тройкой свойств:

x.then( Foo )     /*эквивалентно*/ x
Foo(x).then( g )  /*эквивалентно*/ g(x)
x.then(y).then(z) /*эквивалентно*/ x.then( (r) => y(r).then(z) )

Монады являются альтернативой и обобщением стиля передачи продолжений. Если в стиле передачи продолжений f(cont) – актуальное вычисление (уже запущенное), то для монад f.then(cont) – потенциальное вычисление (которое можно запустить по требованию). Если использовать (не очень удачную) метафору, то между монадами и стилем передачи продолжений примерно та же разница, что между ленивым и энергичным порядками вычисления.

Ещё одна метафора (чуть более удачная): между монадами и стилем передачи продолжений примерно та же разница, что между структурами данных и соответствующими им катаморфизмами. Достоинство потенциального вычисления – наличие внутренней структуры, которой можно явно манипулировать.

В программировании встречаются очень много примеров монад. Мы сейчас приведём пять примеров.

Пример первый: вычисления с возможной ошибкой (иногда называются Maybe-монадой).

function Success(x) {
    return {
        success: true,
        value: x,
        then(g) { return g(x) }
    }
}

function Error() {
    let me = {
        success: false,
        then(g) { return me }
    }

    return me
}

function maybe(m,onerror,onsuccess) {
    if (m.success) { return onsuccess(m.value) }
    return onerror()
}

Пример второй: вычисления с несколькими возможными ошибками (иногда называются Either-монадой).

function Success(x) {
    return {
        success: true,
        value: x,
        then(g) { return g(x) }
    }
}

function Error(x) {
    let me = {
        success: false,
        value: x,
        then(g) { return me }
    }

    return me
}

function maybe(m,onerror,onsuccess) {
    if (m.success) { return onsuccess(m.value) }
    return onerror(m.value)
}

Пример третий: недетерминированные вычисления (с любым количеством возможных исходов; иногда называются List-монадой).

function Trivial(collection)   { 
    let values = []
    for (x of collection) { values.push(x) }
    
    let me = {
        values: values,
        then(g) {
            results = []
            
            for (v of me.values) {
                for (r of g(v).values) {
                    results.push(r)
                }
            }

            return Trivial(results)
        }
    }

    return me
}

function Single(x) { return Trivial([x]) }
function None()    { return Trivial([]) }

function results(comp) {
    return comp.values.slice()
}

Пример четвёртый: классический синхронный CPS (иногда называется Cont-монадой).

function WrapCPS(f) {
    let me = {
        fun: f,
        then(g) {
            return WrapCPS(function (cont) {
                me.fun(function (result) {
                    g(result).fun(cont)
                })
            })
        }
    }

    return me
}

function Give(x) {  // унарный конструктор
    return WrapCPS(function (cont) { cont(x) })
}

function call(f_cps, cont) { f_cps.fun(cont) }


// Полезные функции

function run(f_cps) {
    let result = undefined
    
    call(f_cps, function(r) { result = r })
    
    return result
}


function when(p, f) {
    if (p) {return f}
    
    return Give(undefined)
}

// Вишенка на торте: механизм, передающий в генератор CPS-функции 
// "текущее продолжение" -- способ _преждевременного_ выхода "наверх".
function withCC(gen_cps) {
    function goto(next) {
        return function (x) {
            return WrapCPS(function(cont) {
                next(x)
            })
        }
    }

    return WrapCPS(function (cont) {
        return call(gen_cps(goto(cont)),(cont))
    })
}


// пример использования: числа Фибоначчи
function fib(n) { return run(fibCPS(n)) }
function fibCPS(n) { 
    return withCC( (ret) =>  
        when(n < 2, ret(n)).then( (_) =>
        fibCPS(n-1).then( (f_nm1) =>
        fibCPS(n-2).then( (f_nm2) =>
        Give(f_nm1+f_nm2)
        )))
    )
}
// Здесь ret -- вполне полноценное значение.
// Его, в отличие от return, можно при желании передать другой функции...

Пример пятый: асинхронные вычисления.

function Async(action) {
    let computation = {
        finished: false,
        result: null,
        subscriptions: [],
        subscribe(cont) {
            if (computation.finished) { cont(computation.result) }
            else { computation.subscriptions.push(cont) }
        },
        then(g) {
            return Async(function (finish) {
                computation.subscribe(function (result) {
                    g(result).subscribe(finish)
                })
            })
        }
    }

    setTimeout(function() { 
        action(function(result) {
            computation.result   = result
            computation.finished = true
            let subs = computation.subscriptions
            computation.subscriptions = undefined
            for (s of subs) { s(result) }
        })
    })

    return computation
}


// опять пример с числами Фибоначчи
function fibAsync(n) {
    if (n < 2) { return Async( (cont) => cont(n) ) }

    let a1 = fibAsync(n-1)
    let a2 = fibAsync(n-2)

    return a1.then( (f_nm1) =>
           a2.then( (f_nm2) => 
           Async( (cont) => cont(f_nm1+f_nm2) )))
}

Обещания

Несколько лет назад в Javascript появись обещания (Promise) – асинхронный вариант вышеописанной Either-монады. Они, наконец, позволили превратить огромные CPS-пирамиды, называемые Callback Hell, во что-то более приличное и человекочитаемое.

Обещание символизирует собой асинхронное вычисление, которое потенциально может завершиться ошибкой. Обычно обещания не создаются программистом в явном виде, а являются результатом вызова какой-то функции какой-нибудь библиотеки. Тем не менее, для понимания их работы полезно уметь пользоваться механизмом их создания.

Создаётся обещание конструкцией

new Promise( function(success, error) { ... } )

Поданная конструктору на вход функция должна последним действием применить success к результату вычисления или применить error к «сообщению об ошибке» (вообще говоря, на вход error допускается совершенно любое значение).

Вообще говоря, с точки зрения математики, тип Promise является относительной монадой бифунктора суммы (удивительно, что понятие относительной монады окончательно сформировалось только в 2016 году и пришло в математику из информатики, а не наоборот). Эти слова означают, в частности, что комбинатор then является бинарным. Его работа (по модулю асинхронности) иллюстрируется следующим кодом (на Haskell):

then :: Promise a b -> (a -> Promise x y) -> (b -> Promise x y) -> Promise x y
then (Success x) f g = f x
then (Error   x) f g = g x

Проще говоря, первый аргумент определяет, что делать с результатом успешного вычисления, а второй – что делать с результатом неуспешного.

Полезно помнить несколько сокращений:

Promise.resolve = (x) => new Promise( (s,e) => s(x) )
Promise.reject  = (x) => new Promise( (s,e) => e(x) )

foo.then(f)  /* эквивалентно */ foo.then(f, (x) => x)
foo.catch(f) /* эквивалентно */ foo.then((x) => x, f)

Также полезно помнить, что если результат любого из аргументов then не является обещанием, то он автоматически оборачивается в Promise.resolve.

Также по какой-то странной причине актуальные реализации Promise.resolve и Promise.reject (что в Firefox, что в Chrome) обязательно требуется вызывать как методы объекта Promise. Поэтому Promise.reject не эквивалентен (x) => Promise.reject(x). То есть в тех случаях, когда хочется написать

foo.then(Promise.reject)

нужно писать

foo.then((x) => Promise.reject(x))