2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Delimited continuations в языке, где их изначально нет
Сообщение02.05.2018, 23:45 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Bounded continuations в языке, где их изначально нет
Сообщение03.05.2018, 00:13 
Заслуженный участник


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

-- 03.05.2018, 01:16 --

Это оно?

 Профиль  
                  
 
 Re: Bounded continuations в языке, где их изначально нет
Сообщение03.05.2018, 00:39 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Delimited continuations в языке, где их изначально нет
Сообщение03.05.2018, 19:39 
Заслуженный участник


28/04/09
1933
Если я правильно понял суть, то нечто подобное можно реализовать с помощью обычных лямбд (используется синтаксис 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 и (возможно) захватывали бы некоторые переменные из него, то это тоже можно сделать, как мне кажется. Только это будет некрасивый и медленный код.

 Профиль  
                  
 
 Re: Delimited continuations в языке, где их изначально нет
Сообщение03.05.2018, 20:04 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Delimited continuations в языке, где их изначально нет
Сообщение03.05.2018, 20:25 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Вообще-то, код выглядит как китайская грамота даже для многих из тех, кто думает, что знает C++ :D

 Профиль  
                  
 
 Re: Delimited continuations в языке, где их изначально нет
Сообщение04.05.2018, 03:39 
Заслуженный участник


27/04/09
28128
rockclimber в сообщении #1309834 писал(а):
Я не знаю С++, для меня он выглядит почти как китайская грамота.
Я тоже немного всмотрелся, но не особо понял.

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

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

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

 Профиль  
                  
 
 Re: Delimited continuations в языке, где их изначально нет
Сообщение04.05.2018, 09:45 
Заслуженный участник


28/04/09
1933
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;

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

 Профиль  
                  
 
 Re: Delimited continuations в языке, где их изначально нет
Сообщение04.05.2018, 17:00 
Заслуженный участник


27/04/09
28128
EtCetera
Ага, спасибо. Теперь я сопоставил перевод и оригинал. :-)

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

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

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

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

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

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

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

Используется синтаксис Haskell
reset $ &#40;shift $ \c -> return $ 17 + c 4&#41; >>= \s -> return $ 2 * s

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group