Числовые классы типов в Rust

в 7:34, , рубрики: Rust, дуальные числа, математика

Абстракции Rust отличаются от привычных в ООП. В частности вместо классов (классов объектов) используются классы типов, которые называются «trait» (не следует путать с trait из Scala, где под этим термином прячутся примеси — mixin).
Классы типов не уникальны для Rust, они поддержаны в Haskell, Mercury, Go, из можно реализовать слегка извращенным способом на Scala и C++.

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

Интерфейсы числовых типов довольно громоздки, и я буду вставлять здесь только фрагменты кода. Весь код доступен на github.
Большинство реализованных здесь интерфейсов имеют статус experemental или unstable и скорее всего будут меняться. Я постараюсь поддерживать код и текст актуальными.

Rust поддерживает перегрузку операций, но, в отличие от C++, у операций есть метод-синоним с обычным буквенным именем. Так a+b может быть записано a.add(b), а для переопределения операции '+' надо просто реализовать метод add.

Что же такое — класс типов?

Класс типов часто сравнивают с интерфейсом. Действительно, он определяет что можно делать с некоторыми типами данных, но реализовать эти операции надо отдельно. В отличие от интерфейса, реализация класса типов для некоторого типа не создает нового типа, а живет со старым, хотя старый тип про реализуемый интерфейс может ни чего не знать. Что бы код, использующий данный интерфейс, стал работать с данным типом данных, не требуется править ни тип данных, ни интерфейс, ни код — достаточно реализовать интерфейс для типа.

В отличие от интерфейса в стиле ООП, класс типов может ссылаться на тип несколько раз. Например в Haskell метод '+' требует что бы оба аргумента имели строго один тип и ожидался возврат объекта строго этого же типа (в Rust, в классе типов Add эти типы могут быть разными — в частности, можно складывать Duration и Timespec). Тип возвращаемого значения тоже важен — в аргументах может вообще не используется тип из класса, а какую реализацию метода использовать компилятор решает на основе того, какой тип надо получить. Например в Rust есть класс типов Zero и код

let float_zero:f32 = Zero::zero();
let int_zero:i32 = Zero::zero();

присвоит переменным разных типов разные нули.

Как это сделано в Rust

Описание

Класс типов создается ключевым словом trait, за которым следует имя (возможно с параметрами, примерно как в C++) и список методов. Метод может иметь реализацию по умолчанию, но такая реализация не имеет доступа к внутренностям типа и должна пользоваться другими методами (например выражать неравенство (!=,ne) через отрицание равенства).

pub trait PartialEq {
    /// This method tests for `self` and `other` values to be equal, and is used by `==`.
    fn eq(&self, other: &Self) -> bool;

    /// This method tests for `!=`.
    #[inline]
    fn ne(&self, other: &Self) -> bool { !self.eq(other) }
}

Здесь описание класса типов из стандартной библиотеки, который включает типы, допускающие сравнение на равенство.
Первый аргумент, названный self или &self каждого метода — аналог this из классического ООП. Наличие амперсенда указывает на способ передачи владения объектом и, в отличие от C++, на возможность его изменять не влияет (передача по ссылке или по значению). Право на модификации объекта дает явное указание mut.
Позже мы столкнемся с тем, что этот аргумент не обязателен — получается что-то типа статических методов, хотя на самом деле они все-таки остаются «динамическими» — диспечеризация осуществляется по другим параметрам или по типу ожидаемого результата.

pub trait Add<RHS,Result> {
    /// The method for the `+` operator
    fn add(&self, rhs: &RHS) -> Result;
}

Операция '+' в Rust не обязана требовать одинаковости типов аргументов и результатов. Для этого класс типов сделан шаблонным: аргументы шаблона — типы второго аргумента и результата.
Для сравнения, в Haskell классы типов не параметризованы (кроме как самим типом), но могут содержать не отдельные типы, а пары, тройки и прочие наборы типов (расширение MultiParamTypeClasses), что позволяет делать аналогичные вещи. К релизу в Rust обещают добавить поддержку этой возможности.
Стоит обратить внимание на синтаксическое отличие от C++ — описание сущности в Rust (в данном случае класса типов) само по себе является шаблоном, а в C++ шаблон объявляется отдельно с помощью ключевого слова. Подход C++, в чем-то, более логичен, но сложнее в восприятии.
Рассмотрим еще пример Zero:

pub trait Zero: Add<Self, Self> {
    /// Returns the additive identity element of `Self`, `0`.
    ///
    /// # Laws
    ///
    /// ```{.text}
    /// a + 0 = a       ∀ a ∈ Self
    /// 0 + a = a       ∀ a ∈ Self
    /// ```
    ///
    /// # Purity
    ///
    /// This function should return the same result at all times regardless of
    /// external mutable state, for example values stored in TLS or in
    /// `static mut`s.
    // FIXME (#5527): This should be an associated constant
    fn zero() -> Self;

    /// Returns `true` if `self` is equal to the additive identity.
    #[inline]
    fn is_zero(&self) -> bool;
}

В описании этого класса типов можно усмотреть наследование — для реализации Zero требуется реализовать сначала Add (параметризованный тем же типом). Это привычное наследование интерфейсов без реализации. Допускается и множественное наследование, для этого предки перечисляются через '+'.
Обратите внимание на метод fn zero() -> Self;. Это можно рассматривать как статический метод, хотя далее мы увидим, что он несколько динамичнее, чем статические методы в ООП (в частности, они могут быть использованы для реализации «фабрик»).

Реализация

Рассмотрим реализацию Add для комплексных чисел:

impl<T: Clone + Num> Add<Complex<T>, Complex<T>> for Complex<T> {
    #[inline]
    fn add(&self, other: &Complex<T>) -> Complex<T> {
        Complex::new(self.re + other.re, self.im + other.im)
    }
}

Комплексные числа — обобщенный тип, параметризуемый представлением действительного числа. Реализация сложения тоже параметризована — она применима к комплексным числам над различными вариантами действительных, если для этих действительных реализован некий интерфейс. В данном случае требуемый интерфейс излишне богатый — он предполагает наличие реализаций Clone (позволяющего создавать копию) и Num (содержащий базовые операции над числами, в частности наследующий Add).

Deriving

Если лень самому писать реализации простых стандартных интерфейсов, эту рутинную работу можно передать компилятору с помощью директивы deriving.

#[deriving(PartialEq, Clone, Hash)]
pub struct Complex<T> {
    /// Real portion of the complex number
    pub re: T,
    /// Imaginary portion of the complex number
    pub im: T
}

Здесь разработчики библиотеки просят создать реализацию интерфейсов PartialEq, Clone и Hash, если тип T поддерживает все необходимое.
На данный момент автогенерация реализаций поддерживается для классов типов Clone, Hash, Encodable, Decodable, PartialEq, Eq, PartialOrd, Ord, Rand, Show, Zero, Default, FromPrimitive, Send, Sync и Copy.

Числовые классы типов

В модуле std::num описано большое количество классов типов, связанных с разными свойствами чисел.
Они могут ссылаться на некоторые другие трейты — для операций сравнения и размещения в памяти (например Copy подсказывает компилятору, что этот тип можно копировать побайтно).
Я выделил интерфейсы, которые реализовал для дуальных чисел в диаграмму.Числовые классы типов в Rust

Реализация дуальных чисел

Тип данных устроен тривиально:

pub struct Dual<T> {
  pub val:T,
  pub der:T
}

В отличие от комплексных чисел из стандартной библиотеки, я старался реализовывать интерфейс исходя из минимальных предположений. Так реализация Add у меня требует только интерфейса Add у исходного типа, а Mul — только Mul+Add.
Иногда это приводило к странному коду. Например, Signed не обязан поддерживать Clone, и, что бы для положительного дуального числа в методе abs вернуть его копию, пришлось сложить его с нулем

impl<T:Signed> Signed for Dual<T> {
 fn abs(&self) -> Dual<T> {
   if self.is_positive() || self.is_zero() {
    self+Zero::zero() // XXX: bad implementation for clone
   } else if self.is_negative() {
    -self
   } else {
     fail!("Near to zero")
   }
 }
}

Иначе компилятор не может проследить владение этим объектом.
Обратите внимание, что тип Zero::zero() явно не задан. Компилятор догадывается, какой он должен быть, по попытке сложения с self, который реализует Num, а, следовательно, и Add<Self,Self>. Но тип Self на момент компиляции еще не известен — он задается параметром шаблона. А значит метод zero динамически находится в таблице методов реализации Num для Dual<T>!

Еще отмечу интересный прием, как в Float реализованы целочисленные константы, характеризующие весь тип. То есть они не могут на вход получать экземпляр (его в нужном контексте может и не быть), а должны быть аналогом статических методов. Та же проблема часто возникает в Haskell, и для ее решения таким методам добавляется фейковый параметр с нужным типом. Haskell язык ленивый и в качестве неиспользуемого аргумента всегда можно передать error «Not used». В строгом языке Rust такой прием не проходит, а создавать объект для этого может быть слишком дорого. По этому используется обходной трюк — передается None типа Option<Self>

#[allow(unused_variable)]
impl<T:Float> Float for Dual<T> {
 fn mantissa_digits(_unused_self: Option<Dual<T>>) -> uint {
  let n: Option<T> = None;
  Float::mantissa_digits(n)
 }
}

Так как параметр не используется, по умолчанию компилятор выдает предупреждение. Подавить его можно двумя способами — начав название параметр с символа '_' или с помощью директивы #[allow(unused_variable)].

Автор: potan

Источник

Поделиться

* - обязательные к заполнению поля