#prog #rust #article
Я считаю, что в дизайне современных языков программирования упущена весьма важная тема: перекрывающийся доступ к значениям (aliasing). В статье Niko Matsakis (старой, написанной ещё в те времена, когда в Rust ещё был сборщик мусора) раскрывается связь между управлением памятью и отсутствием гонок данных. В статье Manish Goregaokar эта тема раскрыто несколько более глубоко, а в статье Matt Brubeck рассказывается, в частности, о том, как связаны мутабельность и уникальность доступа и как можно построить безопасные API поверх небезопасного, предоставляющего безусловное перекрытие доступа.
И да, если вы считаете, что это исключительно бзик Rust, то вот вам статьи о аналогичных механизмах в Swift и D.
Я считаю, что в дизайне современных языков программирования упущена весьма важная тема: перекрывающийся доступ к значениям (aliasing). В статье Niko Matsakis (старой, написанной ещё в те времена, когда в Rust ещё был сборщик мусора) раскрывается связь между управлением памятью и отсутствием гонок данных. В статье Manish Goregaokar эта тема раскрыто несколько более глубоко, а в статье Matt Brubeck рассказывается, в частности, о том, как связаны мутабельность и уникальность доступа и как можно построить безопасные API поверх небезопасного, предоставляющего безусловное перекрытие доступа.
И да, если вы считаете, что это исключительно бзик Rust, то вот вам статьи о аналогичных механизмах в Swift и D.
#prog #rust #моё
Исторически решение задач с бектрекингом является более простым в функциональных ЯП с персистентными структурами данных. Взял состояние, немного поменял его и получил новую версию, делаешь на ней рекурсивный вызов, если решение зашло в тупик — возвращаешься обратно и работаешь со старой версией состояния. Благодаря должной реализации и заточенным под работу с иммутабельными данными компилятору это даже может достаточно эффективно работать. Императивные ЯП обычно обделены подобной роскошью. Даже если есть реализация подобной структуры данных, работает она зачастую менее эффективно полноценно изменяемой структуры данных. Из-за этого в решении задач с бектрекингом появляется некоторая структура данных, которая умеет отменять изменения. Это несколько неудобно и чревато ошибками.
Я задумался над тем, как можно упростить подобное решение, не потеряв эффективности мутабельных изменений, и, кажется, нашёл тот краеугольный камень, с помощью которого можно выстроить такую инфраструктуру, подобно тому, как все методы Iterator определены через Iterator::next. Это трейт
Дополнительное требование к реализации, которое, увы, невыразимо в коде на Rust (но было бы выразимо на, скажем, Agda или Idris), состоит в том, что изменение, возвращённое apply, будучи применённым обратно к self, переводит его в первоначальное состояние (до степени, требуемой задачей: это изменение может поменять, скажем, ёмкость хэшмапы, но навряд ли для вас это существенно). Иными словами,
Данное определение вкупе с приведённым выше требованием обеспечивает композируемость и, как следствие, линейную историю. Скажем,
Если несколько изменить способ хранений изменений и не отбрасывать их, то можно также реализовать redo.
Вот несколько более изощрённый пример, который применяет отменяющие патчи автоматически, когда изменённая версия становится не нужна:
Этот метод уже по эргономике приближается к варианту с персистентными структурами данных: если мы в каждый момент времени работаем только с одной версией структуры, то этого достаточно, при этом нам не требуется применять отмену руками, всё происходит автоматически.
Исторически решение задач с бектрекингом является более простым в функциональных ЯП с персистентными структурами данных. Взял состояние, немного поменял его и получил новую версию, делаешь на ней рекурсивный вызов, если решение зашло в тупик — возвращаешься обратно и работаешь со старой версией состояния. Благодаря должной реализации и заточенным под работу с иммутабельными данными компилятору это даже может достаточно эффективно работать. Императивные ЯП обычно обделены подобной роскошью. Даже если есть реализация подобной структуры данных, работает она зачастую менее эффективно полноценно изменяемой структуры данных. Из-за этого в решении задач с бектрекингом появляется некоторая структура данных, которая умеет отменять изменения. Это несколько неудобно и чревато ошибками.
Я задумался над тем, как можно упростить подобное решение, не потеряв эффективности мутабельных изменений, и, кажется, нашёл тот краеугольный камень, с помощью которого можно выстроить такую инфраструктуру, подобно тому, как все методы Iterator определены через Iterator::next. Это трейт
Apply:trait Apply {
type Patch;
fn apply(&mut self, patch: Self::Patch) -> Self::Patch;
}Дополнительное требование к реализации, которое, увы, невыразимо в коде на Rust (но было бы выразимо на, скажем, Agda или Idris), состоит в том, что изменение, возвращённое apply, будучи применённым обратно к self, переводит его в первоначальное состояние (до степени, требуемой задачей: это изменение может поменять, скажем, ёмкость хэшмапы, но навряд ли для вас это существенно). Иными словами,
let changed = {
let mut changed = original.clone();
let undo = changed.apply(change);
changed.apply(undo);
changed
};
assert_eq!(original, changed);Данное определение вкупе с приведённым выше требованием обеспечивает композируемость и, как следствие, линейную историю. Скажем,
let undo1 = state.apply(change1);
let undo2 = state.apply(change2);
let undo3 = state.apply(change3);
state.apply(undo3);
state.apply(undo2);
state.apply(undo1); // сейчас state находится в том же
// состоянии, что и до начала преобразований
Разумеется, хранить историю можно и в более организованном виде. Скажем, вот как организовывается обобщённая структура для поддержки отмены изменений:struct Undo<Data: Apply> {
data: Data,
changes: Vec<Data::Patch>,
}
impl<Data: Apply> Undo {
fn get(&self) -> &Data {
&self.data
}
fn apply(&mut self, patch: Data::Patch) {
self.changes.push(self.data.apply(patch));
}
fn undo(&mut self) {
if let Some(undo) = self.changes.pop() {
self.data.apply(undo);
}
}
}Если несколько изменить способ хранений изменений и не отбрасывать их, то можно также реализовать redo.
Вот несколько более изощрённый пример, который применяет отменяющие патчи автоматически, когда изменённая версия становится не нужна:
struct Patching<Data>(Data);
struct Unapply<'a, Data: Apply> {
data: &'a mut Data,
undo: Option<Data::Patch>,
}
impl<Data: Apply> Patching<Data> {
fn applying(&mut self, patch: Data::Patch) -> Unapply<Data> {
let undo = self.0.apply(patch);
Unapply {
data: &mut self.0,
undo: Some(undo),
}
}
}
impl<Data: Apply> Unapply<'_, Data> {
fn applying<'a>(&'a mut self, patch: Data::Patch) -> Unapply<'a, Data> {
let undo = self.data.apply(patch);
Unapply {
data: &mut self.data,
undo: Some(undo),
}
}
}
impl<Data: Apply> Drop for Unapply<'_, Data> {
fn drop(&mut self) {
let undo = self.undo.take().unwrap();
self.data.apply(undo);
}
}Этот метод уже по эргономике приближается к варианту с персистентными структурами данных: если мы в каждый момент времени работаем только с одной версией структуры, то этого достаточно, при этом нам не требуется применять отмену руками, всё происходит автоматически.
Wikipedia
Persistent data structure
data structure that always preserves the previous version of itself when it is modified
👍2
По идее, здесь должен был быть мотивирующий пример, показывающий, как вся эта машинерия упрощает код, и я думал о том, чтобы сделать решатель судоку... А потом понял, что набор всех возможных значений для всех 9 ⨯ 9 = 81 клеток поля занимает настолько мало места, что его проще копировать целиком, чем содержать целый список изменений (либо в куче, либо неявно на стеке, как в случае с Unapply), так что у меня пропала мотивация делать этот относительно сложный пример. Может, вы сможете что-то подсказать?
#prog #rust #parsing #article
Традиционные парсеры формальных языков обычно прекращают работа сразу после того, как встретят первую ошибку. Для использования в IDE такие парсеры не подходят: пользователь ожидает, что различные фичи IDE (подсветка синтаксиса, автодополнение, переименование) будут работать и в том случае, когда код ещё не дописан до той степени, что он проходит синтаксическую проверку. Для таких целей нужны парсеры, которые в состоянии восстанавливаться после ошибок и продолжать разбор текста.
В этой статье рассказывается о консервативном расширении PEG, добавляющем семантику восстановления после ошибки разбора. Чуда не случилось в том смысле, что много чего надо писать руками, но авторам удалось побить ANTLR — как по качеству сообщений об ошибках, так и по быстроте работы.
А вот также статья, адаптирующая этот подход к парсер-комбинаторам (конкретно к nom)
Традиционные парсеры формальных языков обычно прекращают работа сразу после того, как встретят первую ошибку. Для использования в IDE такие парсеры не подходят: пользователь ожидает, что различные фичи IDE (подсветка синтаксиса, автодополнение, переименование) будут работать и в том случае, когда код ещё не дописан до той степени, что он проходит синтаксическую проверку. Для таких целей нужны парсеры, которые в состоянии восстанавливаться после ошибок и продолжать разбор текста.
В этой статье рассказывается о консервативном расширении PEG, добавляющем семантику восстановления после ошибки разбора. Чуда не случилось в том смысле, что много чего надо писать руками, но авторам удалось побить ANTLR — как по качеству сообщений об ошибках, так и по быстроте работы.
А вот также статья, адаптирующая этот подход к парсер-комбинаторам (конкретно к nom)
#prog #rust #article
Как заставить программы на Rust работать с длинными путями на Windows.
gal.hagever.com/posts/windows-long-paths-in-rust/
Как заставить программы на Rust работать с длинными путями на Windows.
gal.hagever.com/posts/windows-long-paths-in-rust/
Hagever
Using Long Paths in Windows and Rust
There's a simple solution for using long paths in Windows binaries
#prog #rust #successstory
"What would our ideal language look like for rewriting our LIQUID platform? Since a key feature of LIQUID is its speed and low latency, performance and the lack of a garbage collector were an absolute must. We also needed broad cross-platform support, as we want to run LIQUID everywhere, from iOS, Android, Mac, Windows, Linux, and even embedded devices. This hypothetical language would need C interoperability with no performance overhead so that we could integrate with existing components and dip into raw memory access when performance demanded it. Ideally, this language would also be safer than C/C++, helping us to prevent common programming errors at compile time. It turns out there is a language that does all that and more…"
astropad.com/why-rust/
"What would our ideal language look like for rewriting our LIQUID platform? Since a key feature of LIQUID is its speed and low latency, performance and the lack of a garbage collector were an absolute must. We also needed broad cross-platform support, as we want to run LIQUID everywhere, from iOS, Android, Mac, Windows, Linux, and even embedded devices. This hypothetical language would need C interoperability with no performance overhead so that we could integrate with existing components and dip into raw memory access when performance demanded it. Ideally, this language would also be safer than C/C++, helping us to prevent common programming errors at compile time. It turns out there is a language that does all that and more…"
astropad.com/why-rust/
Astropad
Why We're Bringing Astropad Cross-Platform with Rust
Here at Astropad, we’ve kept a close eye on the shift away from Apple, knowing that Windows would be a big part of our company’s future.
#prog #rust #successstory
"With all of the optimizations, you’d expect Condure to run pretty well. Early observations confirm this to be true! We’ll publish more detailed benchmarks in the future, but here are some standout points:
* We were able to establish 1 million client connections to a single instance.
* We load tested ~16k HTTP requests/second using a single ZeroMQ handler.
* We are seeing a 90% reduction in CPU usage compared to Mongrel2 on our production systems."
blog.fanout.io/2020/08/11/rewriting-pushpins-connection-manager-in-rust/
"With all of the optimizations, you’d expect Condure to run pretty well. Early observations confirm this to be true! We’ll publish more detailed benchmarks in the future, but here are some standout points:
* We were able to establish 1 million client connections to a single instance.
* We load tested ~16k HTTP requests/second using a single ZeroMQ handler.
* We are seeing a 90% reduction in CPU usage compared to Mongrel2 on our production systems."
blog.fanout.io/2020/08/11/rewriting-pushpins-connection-manager-in-rust/
#prog #article
Разбор довольно старой статьи с описанием различных схем реализации структур данных, хранящих большое количество таймеров. Спойлер: иерархичность рулит! Причём не только с таймерами, но и с аллокациями и битовыми множествами.
Разбор довольно старой статьи с описанием различных схем реализации структур данных, хранящих большое количество таймеров. Спойлер: иерархичность рулит! Причём не только с таймерами, но и с аллокациями и битовыми множествами.