#prog #rust #моё

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

trait Provide<Item> {
fn provide(&mut self) -> Item;
}

И строительные блоки:

struct HNil;
struct HCons<H, T>(H, T);

Первое, что приходит на ум — это реализация в лоб, т. е. реализовать трейт для HCons в том случае, если его реализует либо голова, либо хвост:

impl<Item, H, T> Provide<Item> for HCons<H, T>
where
H: Provide<Item>,
{
fn provide(&mut self) -> Item {
self.0.provide()
}
}

impl<Item, H, T> Provide<Item> for HCons<H, T>
where
T: Provide<Item>,
{
fn provide(&mut self) -> Item {
self.1.provide()
}
}

Даже без запуска понятно, что это не сработает: если и голова, и хвост реализуют Provide<Item>, то у нас выходит две различные реализации для HCons. И действительно, компилятор жалуется:

error[E0119]: conflicting implementations of trait Provide<_> for type HCons<_, _>

Мы можем сделать разные трейты для Provide из головы и Provide из хвоста и потом объединить их при помощи blanket impl, но мы опять упрёмся в перекрывающиеся реализации. Так что же делать?

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

Вводить этот путь при помощи ассоциированных типов — тупиковый вариант, потому что они не являются параметрами трейтов. Нам придётся поменять определение Provide и внести в него ещё один тИповой параметр:

trait Provide<Item, Path> {
fn provide(&mut self) -> Item;
}

И, конечно, добавить типовые маркеры, отвечающие за компоненты пути:

struct Itself;
struct Head<T>(T);
struct Tail<T>(T);

Теперь модифицируем реализации для Hcons:

impl<Item, H, T, HSource> Provide<Item, Head<HSource>> for HCons<H, T>
where
H: Provide<Item, HSource>,
{
fn provide(&mut self) -> Item {
self.0.provide()
}
}

impl<Item, H, T, TSource> Provide<Item, Tail<TSource>> for HCons<H, T>
where
T: Provide<Item, TSource>,
{
fn provide(&mut self) -> Item {
self.1.provide()
}
}

И... Оно компилируется. Что ж, сделаем пример:

struct Cloning<T>(T);

impl<T> Provide<T, Itself> for Cloning<T>
where
T: Clone,
{
fn provide(&mut self) -> T {
self.0.clone()
}
}

fn _test() {
let mut list = HCons(Cloning(0), HCons(Cloning(()), HNil));
let _: u32 = list.provide();
let _: () = list.provide();
}

Как видите, всё прекрасно работает, нужные типы выводятся по возвращаемому результату. Сила вывода типа!

Окей, а что будет, если в списке окажется два типа, которые могут предоставлять требуемый тип, или, наоборот, не будет ни одного? Проверим:

let mut list = HCons(Cloning(()), HCons(Cloning(()), HNil));
let _: u32 = list.provide();

Ответ компилятора:

error[E0277]: the trait bound HCons<Cloning<()>, HCons<Cloning<()>, HNil>>: Provide<u32, _> is not satisfied
--> src/lib.rs:47:23
|
47 | let _: u32 = list.provide();
| ^^^^^^^ the trait Provide<u32, _> is not implemented for HCons<Cloning<()>, HCons<Cloning<()>, HNil>>

Что ж, вполне логичный ответ. А теперь для конфликтующих провайдеров:

let mut list = HCons(Cloning(()), HCons(Cloning(()), HNil));
let _: () = list.provide();

Ответ компилятора:

error[E0282]: type annotations needed
--> src/lib.rs:47:23
|
47 | let _: () = list.provide();
| ^^^^^^^ cannot infer type for type parameter Path declared on the trait Provide

Что ж, ошибка явно могла бы быть более внятной, но, по крайней мере, она есть.

Так что, мы закончили? Не совсем. Есть парочка вещей, которые мне не нравятся.

Во-первых, тем, кто это использует, придётся реализовывать Provide<Item, Itself> для своих типов, ибо навряд ли они такие же обобщённые. Несколько бойлерплейтно. Обходится созданием отдельного трейта, который будет реализовывать Provide<_, Itself> через blanket impl:

trait ProvideBase<Item> {
fn provide_base(&mut self) -> Item;
}

impl<Item, T> Provide<Item, Itself> for T
where
T: ProvideBase<Item>,
{
fn provide(&mut self) -> Item {
self.provide_base()
}
}

Во-вторых, при реализации Provide можно использовать произвольные типы для путей, что позволяет немного сломать код:

impl Provide<u32, Head<Itself>> for HCons<(), HNil> {
fn provide(&mut self) -> u32 {
0
}
}

// где-то в коде
let _: u32 = HCons(Cloning(42u32), HCons((), HNil)).provide();
// ^~~ error: type annotations needed

Это было бы неприятным, если бы мы строили вокруг этого библиотеку, даром, что ломается пользовательский код. Оградиться от этого, теме не менее, достаточно просто: сделаем sealed trait для типов-компонент путей, повесим в качестве ограничения на тип Path в определении Provide, и реализуем для Head, Tale и Itself, но Itself оставим единственным публичным типом.

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

trait ProvideExt<T> {
fn provide_via_path<P>(&mut self) -> T
where
Self: Provide<T, P>;
}

impl<Item, T> ProvideExt<Item> for T {
fn provide_via_path<P>(&mut self) -> Item
where
Self: Provide<Item, P>,
{
self.provide()
}
}

Ну и прежде чем закончить, хочу отметить, что решение с путями на уровне типов я придумал не на пустом месте, а вдохновившись вот этим постом Дэдфуда. Вот и всё, как всегда, весь код в гисте.

#prog #rust #rustlib #menacingopensource

В Rust завезли SFINAE. Ну, почти.

#music #video

Потому что это, чёрт побери, замечательно.

youtube.com/watch?v=Q45yicposyI

В СМЫСЛЕ УЖЕ НОЯБРЬ

#prog #rust #python #successstory

"Just to see what happened, I copied the code over to Rust and made the nessecary syntax changes for it to compile (entirely the same code - just in Rust) - and voilà, reading the model now took 330ms, thats 15x faster, and the rasterization took just 25ms, which is a whopping ~2500x faster. Yes, 25 milliseconds instead of 61 seconds, same code, same algorithm"

old.reddit.com/r/rust/comments/qjxwni/we_just_massively_overdelivered_on_a_project

(thanks @psilon)

#prog #article

Не смотря на то, что property-based часто поразительно эффективно, начать использовать его на практике часто сложно, поскольку инварианты, которые требуют проверки, как правило, не очевидны. В этом случае можно начать с простого: для начала просто проверять, что функция в принципе не падает при всех допустимых значениях аргументов. В какой-то степени это походит на фаззинг, однако такой подход отличается осведомлённостью о типах и имеет преимущество в виде автоматической минификации фейлящих наборов аргументов.

После этого можно продолжить тем, чтобы найти в кодовой базе конвертации "в" и "из" некоторого формата (не обязательно именно (де)сериализация, одни и те же данные часто могут быть представлены по разному в разных частях программы) и удостовериться, что их композиция является функцией идентичности, как и должно быть.

И чтобы окончательно развеять сомнения в практичности данного подхода, советую почитать заметку о том, как два разработчика, которые до этого не имели опыта с PBT, интегрировали Hypothesis в тестирование своей консольной программы. Как показывает эта заметка, даже частичный переход на Hypothesis может весьма сильно повысить эффективность тестирования — в частности, авторам удалось выяснить, что у них де-факто нигде нету чётко прописанный ограничений на содержимое одного из аргументов.

#cpp

https://twitter.com/Morwenn_Ed/status/1454968145203105795

(thanks @vpermilp)

xxx: дык зачем ты делал нехороше?)))) в ТЗ же ясно сказано: делайте хорошо, а плохо -- не делайте

#трудовыебудни

#prog #rust #article

Статья про проблемы с chrono (и про то, как наследие UNIX опять поднасрало).

TL;DR: chrono имеет проблемы с soundness, которые уже приводили к реальным сегфолтам в растовых программах, и не обновляется, а потому, по всей видимости, не получит фиксов никогда. В качестве альтернативы предлагают использовать time, ибо если раньше резон использовать chrono был из-за того, что у chrono более широкий спектр возможностей, то после выхода time v0.3 это уже далеко не столь справедливо.

#prog #python #meme

https://twitter.com/fasterthanlime/status/1248025337235210243

вафелька и амос показали мне что я не делаю ничего достойного внимания спасибо как теперь жить дальше

#prog #article

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

#prog #rust #rustlib

Если вам вдруг потребовалось вынимать байтики из BufRead и на лету декодировать в char, то для этого есть библиотека.

lib.rs/crates/utf8-chars

#prog #article

Ещё немного о metamorphic testing

Идеальная девушка
(утянуто с какого-то чата)

#prog #ocaml #article

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

В статье Effect-Driven QickChecking of Compilers авторы решили эту проблему, спроектировав генератор, который создаёт лишь программы, вывод которых не зависит от порядка вычислений. Сделали они это путём введения рудиментарной системы эффектов (попутно доказав её корректность) и архитектуры генератора, позволяющей на ранних этапах генерации отбрасывать альтернативы, которые бы привели к зависимости от конкретного порядка вычислений. Вместе с генератором они также спроектировали минификатор, позволяющий минифицировать программы с сохранением полезного свойства независимости (впрочем, это получилось скорее автоматически ввиду того, что это свойство было закодировано в эффектах, а элементарные операции минификации сохраняли тип).

Генератор получился достаточно ограниченным. Он генерирует только весьма узкое подмножество всех программ (в частности, никакого полиморфизма, ни по типам, не по эффектам), и, в частности, генерирует только программы, которые гарантированно завершаются. Вдобавок, введённая система эффектов отслеживает исключительно сам факт наличия побочного эффекта, но не его конкретную разновидность. Тем не менее, даже такое ограниченный инструмент оказался полезным на практике. Используя реализацию QuickCheck для OCaml для свойства "для любой программы, сгенерированной генератором, вывод этой программы при использовании двух разных компиляторов одинаков", авторы смогли обнаружить четыре новых бага, а также найти два уже ранее известных.

P. S.: единственное, что меня смущает — это лемма об ослаблении контекста типизации в разделе, в котором доказывается корректность системы типов с эффектами:

If
∆;Γ,(x : τ′),Γ′ ⊢ e : τ & φ and τ′′ ⊑ τ′
then
∆;Γ,(x : τ′′),Γ′ ⊢ e : τ & φ

или, если словами, произвольный тип внутри контекста типизации можно заменить на тип с более слабым эффектом. Лично мне это не кажется очевидным от слова совсем.