#prog #rust #моё

Меня тут один Олег™ попросил коротко рассказать о афинных типах в Rust. Что ж, рассказываю.

Аффинные системы типов — это системы типов, в которых объявленные значения можно использовать не более одного раза. Как и прочие ти́повые навороты, это позволяет писать более корректные программы путём перекладывания бо́льшего числа проверок на компилятор.

Для демонстрации практической пользы приведу пару примеров из стандартной библиотеки Rust:

1. std::sync::Mutex. Для корректной работы многопоточной программы требуется, чтобы доступ к совместно разделяемым изменяемым данным был должным образом синхронизирован. Один из способов достичь его — это защитить изменяемое значение мьютексом. Простой способ, обладающий, однако, существенным недостатком: очень просто забыть захватить блокировку перед тем, как получить доступ к значению (особенно если мьютекс защищает несколько переменных). Какое решение предлагает Rust?

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

Другая возможная проблема с мьютексом связана с тем, что в большинстве языков программирования значения неявно копируются: нужно прилагать специальные усилия для того, чтобы удостовериться, что каждый из thread-ов получает один и тот же мьютекс, а не свою собственную копию (тут была шутка про Go, но она была настолько толстой, что Telegram не давал загрузить пост). В Rust это получается автоматически: нет методов, позволяющих получить копию мьютекса, поэтому расшарить можно только тот или иной вид указателя на мьютекс.

2. std::fs::File. Сборщик мусора помогает освобождать занятую память, но он не очень помогает с внешними ресурсами, в частности, файлами: закрыть файл обычно нужно сразу после того, как работа с ним окончена, а сборщик мусора никаких гарантий по времени закрытий файла не даёт. В стандартной библиотеке большинства языков программирования (даже с GC) есть отдельная функция, которая закрывает файл. Тем не менее, присутствие этой функции обнажает серьёзный изъян в системе типов: файл невозможно использовать после закрытия (также, как и до открытия, но обычно это не является большой проблемой), но это состояние никак не отслеживается в системе типов. Более того, дважды закрывать файл может быть попросту опасно: например, на Linux файл описывается файловым дескриптором — фактически, просто числом. После закрытия файла это же числовое значение может быть переиспользованно для другого файла, поэтому второе закрытия того же файлового дескриптора может привести к закрытию файла в другой программе!

Как эти проблемы обходятся в Rust? Если вы проверите API File, то... Вы не найдёте там метода close! Когда File выходит из области видимости, для него вызывается деструктор, который и закрывает файл. Т. к. явного метода закрытия файла в публичном API нет, единственный способ форсировать закрытие файла — это дропнуть файл (например, вызовом std::mem::drop). В силу того, что после этого получить доступ к файлу нельзя, возможность двойного закрытия статически запрещается.

Очевидно, аффинные типы не являются серебряной пулей. Каковы же недостатки? Конкретно в случае с File недостаток очевиден: закрытие файла может завершиться ошибкой, но закрытие посредством вызова деструктора не позволяет об этом узнать. Более сильные линейные типы (в которых каждое значение используется ровно один раз) позволили бы решить эту проблему, требуя явно вызывать close и таким образом давать доступ к возможным ошибкам, но это уже тема для другого поста.

Другие статьи, раскрывающие эту тему:

habr.com/ru/post/324382
habr.com/ru/post/350372/

О, число подписчиков перевалило за сотню! Спасибо

Что-то кушать захотелось

#prog #article

Отвечая на закономерный вопрос "откуда": это из статьи про исследовательский язык программирования Mezzo. Статья рассказывает о том, как в языке достигается отсутствие гонок данных, с соответствующими доказательствами.

#tips

Ну почему, почему в телеграме столько клёвых и при этом недокументированных фич?!

Ладно, похоже, об этом всё ещё мало кто знает, хотя функция старая. Мой долг рассказать вам, а ваш рассказать друзьям.

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

Удобнее, чем кнопочка непрочитанных упоминаний, которую можно случайно сбросить, а иногда и сама ломается.

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

Казалось бы, бесполезно, но нет. По количеству найденных результатов можно узнать, сколько вы уже наговорили со своим другом, возлюбленным, или соседом по общаге.

Эту фичу сама только узнала от подписчика.

#prog #go #моё

"Разбудите меня через сто лет, спросите, что делают гоферы, и я отвечу: копируют и вставляют." © Почти Салтыков-Щедрин

#prog #quotes #meme

Коротко о ненужных резалтах

#video

Годный лайфхак.

https://www.youtube.com/watch?v=XxmBBFJ57fY

#prog #article

Статья про специализированный язык программирования для манипуляций с массивами. Интересен тот факт, что язык фактически является подмножеством F#, а реальная компиляция проводится с трансляцией в C.

We show how to compile high-level functional array-processing programs, drawn from image processing and machine learning, into C code that runs as fast as hand-written C. The key idea is to transform the program to destination-passing style, which in turn enables a highly-efficient stack-like memory allocation discipline.

Спойлер: производительность на уровне Eigen. Да, настолько круто.

https://www.microsoft.com/en-us/research/publication/using-destination-passing-style-compile-functional-language-efficient-low-level-code/

#prog #science

Залипательная симуляция гравитации с открытым исходным кодом (к сожалению, на JS — идеальный кандидат на переписывание на Wasm!).

https://hermann.is/gravity/

#prog #haskell #meme

И ведь не поспоришь

#prog #rust #моё

В стандартной библиотеке Rust есть замечательное определение итератора. Оно выглядит следующим образом:

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    // и ещё уйма методов, все из которых имеют реализацию по умолчанию
}

Это определение замечательно тем, что, в отличие от канонического определения из GoF здесь нет места вопросу "что возвращает next, если hasNext вернул false": при использовании итератора элементы достаются, пока .next() возвращает Some(_). Тем не менее, поведение итератора после того, как он вернул None, не является частью контракта итератора: разные конкретные реализации могут возвращать, а могут и не возвращать новые элементы. Конечно, большинство итераторов возвращают None после того, как в них закончились элементы, но в общем случае это не так. В частности, std::iter::from_fn создаёт итератор, который для получения следующего f просто вызывает замыкание, переданное в функцию аргументом. Не зная ничего об этом замыкании, нельзя сделать никаких выводов по поведению итератора.

В некоторых случаях, когда итератор используется более интересным образом, чем просто из цикла for, для корректности кода нужно, чтобы вызовы next после возврата None продолжали возвращать None. Такие итераторы называют плавлеными слитыми обезвреженными fused iterators. Для того, чтобы отделять агнцев от козлищ, стандартная библиотека предоставляет два инструмента:
1. Трейт FusedIterator, который, по идее, должен быть реализован всеми итераторами, которые ведут себя желаемым образом (к сожалению, корректность подобной реализации находится целиком и полностью на совести программиста (где, чёрт возьми, мой прувер для раста?!));
2. Метод Iterator::fuse, который оборачивает итератор в адаптер Fuse, гарантирующий fused поведение.

Второй метод связан со вторым: благодаря специализации, если Fuse оборачивает итератор, реализующий FusedIterator, то вызов next у Fuse просто вызывает метод next у нижележащего оператора. Как написано в документации к FusedIterator:

"Note: In general, you should not use FusedIterator in generic bounds if you need a fused iterator. Instead, you should just call Iterator::fuse on the iterator. If the iterator is already fused, the additional Fuse wrapper will be a no-op with no performance penalty."

Часть про no-op верна, а вот часть про "with no performance penalty" несколько сомнительна: Fuse хранит булев флаг, говорящий, вернул ли нижележащий итератор None или нет, даже несмотря на то, что для fused итераторов он не используется. Можно представить себе ситуацию, когда дополнительный флаг может привести к тому, что итератор перестаёт влезать в кэш процессора, что несколько ударяет по производительности. Это не zero-cost abstraction! Сегодня я займусь тем, что буду это исправлять.

Посмотрим, как реализован Iterator::next для Fuse:

    default fn next(&mut self) -> Option<<I as Iterator>::Item> {
        if self.done {
            None
        } else {
            let next = self.iter.next();
            self.done = next.is_none();
            next
        }
    }

Здесь нагло эксплуатируется тот факт, что поле done имеет булев тип. Если мы хотим, чтобы адаптер не содержал флаг для fused итератора, нам нужно сделать тип флага зависящим от типа итератора. Т. к. теперь мы не можем считать флаг булевым, нам нужно абстрагироваться от конкретного типа. Немного перепишем реализацию метода:

    default fn next(&mut self) -> Option<<I as Iterator>::Item> {
        if self.done {
            None
        } else {
            let next = self.iter.next();
            if next.is_none() {
                self.done = true;
            }
            next
        }
    }

Как видно, от флага требуется две операции: проверка на то, выставлен ли он, и его установка в положение "да, сэр, к сожалению, этот джентельмен вернул None". Также нам нужно каким-то образом получить начальное значение флага, когда мы создаём адаптер. Выразим это в трейте:

trait Flag: Default {
    fn is_set(&self) -> bool;
    fn set(&mut self);
}

Этот трейт тривиально реализуется для bool:

impl Flag for bool {
    fn is_set(&self) -> bool {
        *self
    }

    fn set(&mut self) {
        *self = true
    }
}

Теперь подумаем, что нам требуется для fused итератора. Наш метод next будет эквивалентен вызову next у нижележащего итератора, если флаг всё время ведёт себя так, как будто он не выставлен (рекомендую ещё раз посмотреть на код выше, чтобы убедиться в этом). Создадим соответствующий тип и реализуем для него Flag:

#[derive(Default)]
struct False;

impl Flag for False {
    fn is_set(&self) -> bool {
        false
    }

    fn set(&mut self) {}
}

Теперь нам нужно сопоставить каждому итератору соответствующий тип флага. Именно здесь нам понадобится специализация: по умолчанию для итератора флагом является булев тип, но для fused итераторов (т. е. реализующих FusedIterator) это будет False. Непосредственно функций на уровне типов в Rust нет, но их роль играют трейты с ассоциированными типами.

trait FlagType: Iterator {
    type Flag: Flag + Default;
}

impl<I: Iterator> FlagType for I {
    // ключевое слово default позволяет нам переопределять элементы трейтов
    // в более специфичных impl-ах...
    default type Flag = bool;
}

impl<I: FusedIterator> FlagType for I {
    // ...что мы и делаем
    type Flag = False;
}

Теперь напишем сам адаптер. Ничего сложного в нём нет, нужно только иметь в виду, что нам требуется тип, для которого определён флаг:

struct SlimFuse<I: FlagType> {
    iter: I,
    finished: I::Flag,
}

После всего описанного выше нетрудно написать реализацию Iterator:

impl<I: FlagType> Iterator for SlimFuse<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        if self.finished.is_set() {
            return None;
        }

        let ret = self.iter.next();
        if ret.is_none() {
            self.finished.set();
        }
        ret
    }
}

Осталось только приправить extension trait для того, чтобы адаптер было удобно создавать:

trait IteratorExt: Sized + FlagType {
    fn fuse_slim(self) -> SlimFuse<Self>;
}

impl<I: Sized + FlagType> IteratorExt for I {
    fn fuse_slim(self) -> SlimFuse<Self> {
        SlimFuse {
            iter: self,
            finished: <_>::default(),
        }
    }
}

Теперь проверим, как это всё работает:
use std::mem::size_of_val;
use std::iter;

// FromFn не реализует FusedIterator по понятным причинам
let it1 = iter::from_fn(|| None::<i32>).fuse();
let it2 = iter::from_fn(|| None::<i32>).fuse_slim();

// В этом случае SlimFuse не лучше (но и не хуже!), чем Fuse
assert_eq!(size_of_val(&it1), size_of_val(&it2));

// Итераторы возвращают одно и то же
assert!(it1.eq(it2));

// Теперь возьмём fused итератор. Все итераторы коллекций являются fused —
// в частности, std::slice::Iter.
let it1 = [1, 2, 3].iter().fuse();
let mut it2 = [1, 2, 3].iter().fuse_slim();

// Наш адаптер эксплуатирует свойства итератора и оказывается менее жирным!
assert!(size_of_val(&it1) > size_of_val(&it2));

// Проверим, что наш итератор выдаёт то же самое, что и стандартный
assert!(it1.eq(it2.by_ref()));

// Проверим, что с наш адаптер действительно fused
assert!(it2.by_ref().eq(iter::empty::<&i32>()));
assert!(it2.by_ref().eq(iter::empty::<&i32>()));

Замечательно. Торжество zero-cost абстракций!

Весь код в этих постах я выложил гистом на GitHub