Наибольший кайф античных книг в их выдержке, актуальности. Книги точно проверены временем, актуальны (правда если знаешь в чем) и как ни странно, честны (книги хотели бы, чтобы их читали через сотню или тысячу лет). В программировании античные скрипты, наверно, написал Деннис Ритчи, сегодня же почитаем современников - Sean Parent (довольно известный чел в c++ тусовке) начал писать на расте (возможно, как начал так и закончил, но мы живем в моменте - поэтому предлагаю насладиться). Читать на расте сложнее, чем писать (это прям факт) - пишут его двое (автор и компилятор), а читают, ну читают на гитхабе. Далее в прозаическом сочинении свободной композиции, подразумевающем впечатления и соображения автора по конкретному поводу или предмету, рассмотрим компоненты новой библиотеки и попробуем насладиться примерами кода.
Начнем, пожалуй, с простого алгоритма (так сказать, алгоритмы тоже бывают в одну строчку, а не то, что обычно пишут на модных майках):
const fn align_index(align: usize, index: usize) -> usize {
debug_assert!(align.is_power_of_two());
(index + align - 1) & !(align - 1)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_align_index() {
assert_eq!(align_index(16, 0), 0);
assert_eq!(align_index(16, 1), 16);
assert_eq!(align_index(16, 15), 16);
assert_eq!(align_index(16, 16), 16);
assert_eq!(align_index(16, 17), 32);
}
}
Как можно заметить, тесты прекрасно дополняют читаемость функции и, как ни странно, располагаются всего двумя строчками ниже.
Могут возникнуть вопросы о выравнивании индекса, собственно, зачем оно? Вопросы и гугление может привести к интересной связи между "alignment" и "memory paging" (спасибо Алисе за перевод - "страничное запоминание"). Тут настолько гуглить, на сколько хватит терпения и врожденного интереса.
Собственно, алгоритм выше мы увидим в следующих структурах данных:
/// A sequence that stores heterogeneous values with proper alignment.
///
/// The `RawSequence` provides a memory-efficient way to store heterogeneous values
/// while maintaining proper alignment requirements for each type...
pub struct RawSequence {
buffer: RawVec,
}
...
#[test]
fn sequence_operations() {
let mut seq = RawSequence::new();
seq.push(100u32);
seq.push(200u32);
seq.push(42.0f64);
seq.push("Hello, world!");
...
}
RawVec это почти равно Vec<MaybeUninit<u8>>
, то есть тупо храним байтики, что позволяет нам хранить в векторе гетерогенные (вот это слово) составляющие. Для статических языков программирования эт прям очень круто. Далее пару методов структурки:
/// ...
/// Returns a tuple containing:
/// - A reference to the value
/// - The position immediately after the value
#[must_use]
pub unsafe fn next<T>(&self, p: usize) -> (&T, usize) {
let aligned: usize = align_index(mem::align_of::<T>(), p);
let ptr = unsafe { self.buffer.as_ptr().add(aligned).cast::<T>() };
unsafe { (&*ptr, aligned + mem::size_of::<T>()) }
}
pub fn push<T>(&mut self, value: T) {
let len = self.buffer.len();
let aligned: usize = align_index(mem::align_of::<T>(), len);
let new_len = aligned + mem::size_of::<T>();
self.buffer.reserve(new_len - len);
unsafe {
self.buffer.set_len(new_len);
std::ptr::write(self.buffer.as_mut_ptr().add(aligned).cast::<T>(), value);
}
}
Второй метод, который "пуш" - немного длиннее, как мне кажется, чем нужно. Пару моментов, которые не совсем очевидны: 1) buffer.reserve принимает дополнительное кол-во элементов, 2) buffer.set_len прям нужно (не забыть) вызвать.
Перейдем к другой структурке (там их много, и из них как из компонентов собирается конечный механизм, но пожалуй, остальные не очень интересны):
/// A list using a guaranteed memory layout (`repr(C)`), with tail stored first so appending items
/// does not change the memory layout of prior items.
#[repr(C)]
#[derive(Clone)]
pub struct CStackList<H, T>(pub T, pub H);
impl<H: 'static, T: List> List for CStackList<H, T> {
type Push<U: 'static> = CStackList<U, Self>;
fn push<U: 'static>(self, item: U) -> Self::Push<U> {
CStackList(self, item)
}
type Append<U: List> = <T::Append<U> as List>::Push<H>;
fn append<U: List>(self, other: U) -> Self::Append<U> {
self.0.append(other).push(self.1)
}
type ReverseOnto<U: List> = T::ReverseOnto<U::Push<H>>;
fn reverse_onto<U: List>(self, other: U) -> Self::ReverseOnto<U> {
self.0.reverse_onto(other.push(self.1))
}
...
}
Прекрасные рекурсивные алгоритмы - не только код, но и определение типа. Пожалуй, только из-за рекурсии уже можно идти в программирование (на счет указателей, конечно, есть вопросы, но старина Спольски, по-моему, сейчас уже не ведет блоги). С рекурсий на типах еще не все - какие-то ребята сделали библиотеку typenum и теперь вроде индекс можно проверять на этапе компиляции (упоролись они, конечно, знатно, с другой стороны, почему бы и не проверять индекс, полезно вроде):
impl<H: 'static, T: List> ListIndex<RangeFrom<U0>> for CStackList<H, T> {
type Output = CStackList<H, T>;
fn index(&self, _index: RangeFrom<U0>) -> &Self::Output {
self
}
}
impl<H: 'static, T: List, U: Unsigned, B: Bit> ListIndex<RangeFrom<UInt<U, B>>> for CStackList<H, T>
where
T: ListIndex<RangeFrom<Sub1<UInt<U, B>>>>,
UInt<U, B>: Sub<B1>,
{
type Output = <T as ListIndex<RangeFrom<Sub1<UInt<U, B>>>>>::Output;
fn index(&self, index: RangeFrom<UInt<U, B>>) -> &Self::Output {
self.tail().index((index.start - B1)..)
}
}
Там Sean Parent написал еще много интересных компонентов (надеюсь, любознательный читатель нагуглит репозиторий), из которых потом выйдет вот такое описание репозитория (надеюсь, Шон сделает какой-нибудь супер видос про библиотеку, и все с открытыми ртами скажут: "а что, так можно было?", но пока ждем):
// cel-rs provides a stack-based runtime for developing domain specific languages, including
// concative languages to describe concurrent processes. A sequence is a list of operations (the
// machine instructions). Each operation is a closure that takes it's arguments from the stack and
// the result is pushed back onto the stack.
// Create a segment that takes a u32 and &str as arguments
let segment = Segment::<(u32, &str)>::new()
.op1r(|s| {
let r = s.parse::<u32>()?;
Ok(r)
})
.op2(|a, b| a + b)
.op1(|r| r.to_string());
assert_eq!(segment.call((1u32, "2")).unwrap(), "3");
Комментарии (3)
Dhwtj
08.07.2025 16:18Вот нашёл, вроде как аналог
Весь тот «шаманский» кусок Rust – это на самом деле не что иное, как «drop N элементов у H-списка». Н-список это гетерогенный список.
В Scala (с Shapeless) это уже реализовано из коробки тип-классом shapeless.ops.hlist.Drop, поэтому прямой перевод занимает буквально несколько строк
SliceFrom
// build.sbt // libraryDependencies += "com.chuusai" %% "shapeless" % "2.3.10" import shapeless._ import shapeless.ops.hlist.Drop import shapeless.nat._ // готовые Nat-константы _0, _1, _2 … /** --------------------------------------------------------------------------- * Extension-метод, полностью эквивалентный вашему `ListIndex<RangeFrom<N>>`. * Никакой ручной рекурсии – всё делает готовый HKT Drop. * ------------------------------------------------------------------------- */ object syntax { implicit final class SliceFrom[L <: HList](private val l: L) extends AnyVal { /** «Срез от N-го и до конца» (RangeFrom<N>) */ def sliceFrom[N <: Nat](implicit drop: Drop.Aux[L, N, Out], ev: Out <:< HList) : Out = drop(l) type Out <: HList } } import syntax._ // подключаем «сахар» /* ========================= DEMO ========================= */ // Гетерогенный список как у вас (Int, Boolean, String) val hlist = 42 :: true :: "hi" :: HNil // 0.. == целый список val whole = hlist.sliceFrom[_0] // Int :: Boolean :: String :: HNil // 1.. == хвост без первого val tail1 = hlist.sliceFrom[_1] // Boolean :: String :: HNil // 2.. val tail2 = hlist.sliceFrom[_2] // String :: HNil println(whole) // 42 :: true :: hi :: HNil println(tail1) // true :: hi :: HNil println(tail2) // hi :: HNil
Dhwtj
Эмуляция Higher-Kinded Types
Жесть из мира scala
Это способ написать функцию, которая работает с разными "контейнерами" (vec, option,...) одинаково. Можно реализовать свой вариант map, например...