Наибольший кайф античных книг в их выдержке, актуальности. Книги точно проверены временем, актуальны (правда если знаешь в чем) и как ни странно, честны (книги хотели бы, чтобы их читали через сотню или тысячу лет). В программировании античные скрипты, наверно, написал Деннис Ритчи, сегодня же почитаем современников - 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)


  1. Dhwtj
    08.07.2025 16:18

    Эмуляция Higher-Kinded Types

    Жесть из мира scala

    Это способ написать функцию, которая работает с разными "контейнерами" (vec, option,...) одинаково. Можно реализовать свой вариант map, например...


  1. 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