Delimited continuations в языке, где их изначально нет

[arseniiv]

Можно ли в условно императивном языке с исключениями их реализовать? (Если нет, можно будет расширять постановку.)

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

UPD. Исправил название, следующие два сообщения были написаны при старом.

[rockclimber]

А можно в двух словах, что это? Я начал гуглить, нашел статью на хабре, где было описано, как реализовать континуации в java, но без объяснения толком, что это. Ну и соответственно, ответ на ваш вопрос там был - в виде списка готовых фреймворков для этого дела.
(Ничего полезного по теме я скорее всего не скажу, но хотя бы понимать буду, о чем речь.)

-- 03.05.2018, 01:16 --

Это оно?

[arseniiv]

Кажется, я неправильно их назвал. Вот тут они: https://en.wikipedia.org/wiki/Delimited_continuation. Насколько в курсе, сопрограммы можно реализовать через них (генераторы — точно, там yield прямо в статье).

[EtCetera]

Если я правильно понял суть, то нечто подобное можно реализовать с помощью обычных лямбд (используется синтаксис C++17, но этот код можно переписать и на C++14, и на C++11):

Используется синтаксис C++

#include <iostream>
#include <tuple>
#include <vector>


template <typename Functor, template <typename...> class Container, typename Element>
auto fmap(Functor&& functor, const Container<Element>& container)
{
    Container<decltype(functor(std::declval<Element>()))> transformed_container;

    for (const auto& element : container)
    {
        transformed_container.emplace_back(functor(element));
    }

    return transformed_container;
}

template <typename Container>
auto flat(const Container& container)
{
    return container;
}

template <template <typename...> class Container, typename Element>
Container<typename Element::value_type> flat(const Container<Element>& container)
{
    Container<typename Element::value_type> transformed_container;

    for (const auto& element : container)
    {
        transformed_container.insert(transformed_container.end(), element.cbegin(), element.cend());
    };

    return flat(transformed_container);
}

template <typename Functor, typename Container>
auto flat_map(Functor&& functor, const Container& container)
{
    return flat(fmap(std::forward<Functor>(functor), container));
}


template <typename Functor, typename Shift, typename... OtherShifts>
auto reset(Functor&& functor, Shift&& shift, OtherShifts&&... other_shifts)
{
    return shift([&functor, &other_shifts...](auto&&... arguments) {
        if constexpr (sizeof...(other_shifts) > 0)
        {
            return reset(
                [&functor, &arguments...](auto&&... other_arguments) {
                    return functor(
                        std::forward<decltype(arguments)>(arguments)...,
                        std::forward<decltype(other_arguments)>(other_arguments)...);
                },
                other_shifts...);
        }
        else
        {
            return functor(std::forward<decltype(arguments)>(arguments)...);
        }
    });
}


int main()
{
    const auto left = std::vector{1, 2, 3, 4};
    const auto right = std::vector{'x', 'y', 'z'};

    const auto cartesian_product = reset(
        [](auto&& shift1, auto&& shift2) {
            return std::tuple{shift1 + 10, shift2};
        },
        [&left](auto&& functor) { return flat_map(functor, left); },
        [&right](auto&& functor) { return flat_map(functor, right); });

    for (const auto& [l, r] : cartesian_product)
    {
        std::cout << '(' << l << ", " << r << ')' << std::endl;
    }
}

fmap, flat и flat_map реализованы здесь только для примера, самым простым и неэффективным способом. В реализации reset они не используются.

Если все же хочется, чтобы выражения для shifts записывались внутри общего выражения для reset и (возможно) захватывали бы некоторые переменные из него, то это тоже можно сделать, как мне кажется. Только это будет некрасивый и медленный код.

[rockclimber]

EtCetera
А можно чуть подробнее прокомментировать код? Я не знаю С++, для меня он выглядит почти как китайская грамота.

[worm2]

Вообще-то, код выглядит как китайская грамота даже для многих из тех, кто думает, что знает C++

[arseniiv]

rockclimber в сообщении #1309834 писал(а):

Я не знаю С++, для меня он выглядит почти как китайская грамота.

Я тоже немного всмотрелся, но не особо понял.

EtCetera
В предположении, что это то, как перевести выражение

reset (2 * shift (\continue -> 17 + continue 4))

(должно давать 25)? (Пример отсюда, только слова там другие и внизу поясняется соответствие привычным; для тех, кто не знаком с синтаксисом, \x -> e — это $\lambda x.e$.)

[EtCetera]

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

В самом простом случае, когда в reset передан некий functor и только один shift, код аналогичен простому вызову shift(functor) (ветка else в if constexpr). Точнее, functor перед передачей завертывается в лямбду, но это не имеет значения. Когда число переданных shiftов более одного, из остальных shiftов (other_shifts) и самого reset конструируется функтор, который передается в первый shift. При этом передаваемый во внутренний reset функтор получается из исходного functor фиксацией нескольких первых аргументов, используемых первым shiftом (скорее всего, для нужд первого shiftа надо было оставить только один аргумент).
Кажется, объяснение получилось еще непонятнее, чем сам код.

arseniiv

arseniiv в сообщении #1309889 писал(а):

В предположении, что это то, как перевести выражение

reset (2 * shift (\continue -> 17 + continue 4))

(должно давать 25)?

Используется синтаксис C++

const auto result =
    reset([](auto&& shift) { return 2 * shift; }, [](auto&& functor) { return 17 + functor(4); });

std::cout << result << std::endl;

Вы это хотели увидеть? Или что-то другое имели в виду?

-- Пт май 04, 2018 10:36:56 --

arseniiv

arseniiv в сообщении #1309889 писал(а):

Пример отсюда

Можно реализовать и пример с try ... catch ... оттуда же:

try (17 + throw 4) catch (\e -> 42 + e),

где try ... catch ... и throw определяются так:

throw e = escape (\_ -> (\h -> h e))
try a catch h = (capture (let x = a in \_ -> x)) h

Реализация на C++17 с использованием ранее написанного reset:

Используется синтаксис C++

const auto make_throw = [](auto exception) {
    return [exception = std::move(exception)](auto&&) {
        return [exception = std::move(exception)](auto&& handler) { return handler(exception); };
    };
};

auto try_catch = [](auto&& try_, auto&& catch_, auto&&... exceptions) {
    if constexpr (sizeof...(exceptions) > 0)
    {
        return reset(try_, make_throw(std::forward<decltype(exceptions)>(exceptions))...)(catch_);
    }
    else
    {
        return try_();
    }
};

// ...

const auto result_exception_thrown = try_catch(
    [](auto&& throw_) { return 17 + throw_; }, [](auto&& exception) { return 42 + exception; }, 4);
const auto result_no_throw =
    try_catch([] { return 17; }, [](auto&& exception) { return 42 + exception; });

std::cout << "An exception is thrown: " << result_exception_thrown << std::endl;
std::cout << "No throw: " << result_no_throw << std::endl;

Собственно, тут хорошо видны ограничения моего подхода.

[arseniiv]

EtCetera
Ага, спасибо. Теперь я сопоставил перевод и оригинал.

Сейчас посмотрел, на хаскеле этот пример записывается тоже не очень коротко, и клей (в данном случае то, что оперируем монадическими значениями) тоже виден:

reset $ liftM2 (*) (return 2) (shift $ \c -> return $ 17 + c 4)

и запускается это всё с помощью evalCont.

(Альтернативная запись)

Или можно записать поднятое умножение инфиксно (заодно и лишние скобки уйдут), но стандартный хаскель не позволяет использовать ` для выражения, не являющегося одним именем. В таком случае можно вручную определить «инфиксаторы» -* и *-, которые будут работать во всех или почти во всех случаях как `...`.

reset $ return 2 -* liftM2 (*) *- shift $ \c -> return $ 17 + c 4

Ещё можно записать по-рабоче-крестьянски:

Используется синтаксис Haskell

reset $ (shift $ \c -> return $ 17 + c 4) >>= \s -> return $ 2 * s

reset $ do
        s <- shift $ \c -> return $ 17 + c 4
        return $ 2 * s

но это как-то уж совсем далеко от того, как выглядит пример.