Абстракции без накладных расходов: типажи в Rust

В предыдущем посте (англ.) мы затронули два столпа дизайна Rust (поскольку во внутренней речи я постоянно склоняю название языка, дальше я буду использовать русскоязычное название «раст», что мне кажется более органичным — прим. перев.):

• безопасное использование памяти без сборщика мусора,
• многопоточность без гонок данных.

Этот пост начинает рассказ о третьем столпе:

• абстракции без накладных расходов.

Одна из мантр C++, которая делает его таким подходящим для системного программирования — принцип абстракции с нулевой стоимостью:

Реализации C++ подчиняются принципу нулевой стоимости: ты не платишь за то, что не используешь [Страуструп, 1994]. Более того: то, что ты используешь, кодируется наилучшим образом.

– Бьёрн Страуструп

Эта мантра не всегда подходила расту, который когда-то имел обязательный сборщик мусора. Но через какое-то время амбиции раста стали более низкоуровневыми, так что сейчас абстракции с нулевой стоимостью — основной принцип языка.

Центральное понятие абстракции в расте — типажи (traits).

• Типажи в расте играют роль интерфейса. Типаж могут реализовывать несколько типов, а новые типажи могут предоставлять реализации для существующих типов. С другой стороны, если вы хотите абстрагироваться от неизвестного типа, типажи дают возможность указать конкретные требования к этому типу, определяющие ожидаемое от него поведение.
• К типажам может применяться статическая диспетчеризация. Как и с шаблонами в C++, компилятор может сгенерировать реализацию абстракции для каждого случая её использования. Возвращаясь к мантре C++ — «то, что ты используешь, кодируется наилучшим образом» — абстракция полностью удаляется из скомпилированного кода.
• К типажам может применяться и динамическая диспетчеризация. Иногда вам действительно нужна косвенная адресация, так что нет смысла «удалять» абстракцию из скомпилированного кода. То же самое представление интерфейса — типаж — может быть использовано для диспетчеризации во время выполнения программы.
• Типажи решают множество разнообразных проблем помимо простого абстрагирования. Они используются как «маркеры» для типов, например маркер Send, описанный в предыдущем посте. Они же используются для объявления «дополнительных методов», то есть, чтобы добавить новые методы к уже определённому где-то типу. Они заменяют собой традиционную перегрузку методов. А ещё они предоставляют простой способ перегрузки операторов.

Учитывая всё выше сказанное, система типажей — секретное оружие, которое даёт расту эргономику и выразительность высокоуровневых языков, сохраняя низкоуровневый контроль над выполнением кода и представлением данных.

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

Основа: методы в расте

Перед погружением в типажи, мы рассмотрим маленькую, но очень важную деталь языка: разницу между методом и функцией.

В расте есть как методы, так и самостоятельные функции, и они тесно связаны друг с другом:

struct Point {
    x: f64,
    y: f64,
}

// a free-standing function that converts a (borrowed) point to a string
fn point_to_string(point: &Point) -> String { ... }

// an "inherent impl" block defines the methods available directly on a type
impl Point {
    // this method is available on any Point, and automatically borrows the
    // Point value
    fn to_string(&self) -> String { ... }
}

Методы, наподобие to_string, называются «собственными» потому, что они:

• привязаны к конкретному типу «self» (указанному в заголовке блока impl),
• автоматически доступны для всех значений этого типа, то есть, в отличие от функций, собственные методы всегда «в области видимости».

Первый параметр метода всегда явно указан в виде «self», и может быть self, &mut self, либо &self — в зависимости от требуемого уровня владения (может ещё быть mut self, но по отношению к владению это то же самое, что и self — прим. перев.). Методы вызываются с использованием точки (.), как в обычном ООП, а параметр self неявно заимствуется, если того требует сигнатура метода:

let p = Point { x: 1.2, y: -3.7 };
let s1 = point_to_string(&p);  // calling a free function, explicit borrow
let s2 = p.to_string();        // calling a method, implicit borrow as &p

Методы и авто-заимствование — важные аспекты эргономичности раста, поддерживающие простоту API, например интерфейса создания процесса:

let child = Command::new("/bin/cat")
    .arg("rusty-ideas.txt")
    .current_dir("/Users/aturon")
    .stdout(Stdio::piped())
    .spawn();

Типажи как интерфейс

Интерфейсы описывают ожидания одного кода по отношению к другому, позволяя каждой из частей изменяться независимо друг от друга. В случае типажей это описание вертится вокруг методов.

Возьмём, например, следующий простой типаж, описывающий хеширование:

trait Hash {
    fn hash(&self) -> u64;
}

Чтобы реализовать этот типаж для какого-либо типа, мы должны написать метод hash с соответствующей сигнатурой:

impl Hash for bool {
    fn hash(&self) -> u64 {
        if *self { 0 } else { 1 }
    }
}

impl Hash for i64 {
    fn hash(&self) -> u64 {
        *self as u64
    }
}

В отличие от интерфейсов в таких языках, как Java, C# или Scala, новые типажи могут быть реализованы для уже существующих типов (как в случае с Hash в последнем примере). То есть абстракции могут быть созданы по необходимости, а затем применены к уже существующим библиотекам.

В отличие от собственных методов, методы типажей находятся в области видимости только тогда, когда их типаж в области видимости. Но если предположить, что типаж Hash уже находится в нашей области видимости, вы можете написать true.hash(). Таким образом, реализация типажа расширяет набор методов, доступный для данного типа.

Ну и… это всё! Определение и реализация типажа — не более чем абстрагирование общего интерфейса, которому удовлетворяют несколько типов.

Статическая диспетчеризация

Всё становится интереснее с другой стороны — для пользователей типажей. Самый частый способ использования типажей ­— через использование типового параметризма:

fn print_hash<T: Hash>(t: &T) {
    println!("The hash is {}", t.hash())
}

Функция print_hash параметризована неизвестным типом T, но требует, чтобы этот тип реализовал типаж Hash. Что означает, что мы можем использовать её для значений типов bool и i64:

print_hash(&true);      // instantiates T = bool
print_hash(&12_i64);    // instantiates T = i64

Параметризованные типами функции после компиляции разворачиваются в конкретные реализации, в результате получаем статическую диспетчеризацию. Здесь, как и с шаблонами C++, компилятор сгенерирует две копии функции print_hash: по версии для каждого используемого вместо типового аргумента типа. В свою очередь, это означает, что внутренний вызов к t.hash() — то место, где используется абстракция — имеет нулевую стоимость, так как он будет скомпилирован в прямой статический вызов к соответствующей реализации метода hash:

// The compiled code:
__print_hash_bool(&true);  // invoke specialized bool version directly
__print_hash_i64(&12_i64);   // invoke specialized i64 version directly

Такая модель компиляции не очень полезна для функции вроде print_hash, но весьма удобна для более реалистического использования хеширования. Предположим, что у нас так же есть типаж для сравнение на равенство:

trait Eq {
    fn eq(&self, other: &Self) -> bool;
}

(Тип Self здесь будет заменён на тип, для которого реализован данный типаж; в случае impl Eq for bool он будет соответствовать типу bool.)

Мы можем определить тип-словарь, параметризованный типом T, для которого должны быть реализованы типажи Eq и Hash:

struct HashMap<Key: Hash + Eq, Value> { ... }

Тогда модель статической компиляции для параметрических типов даст несколько преимуществ:

Каждое использование HashMap с конкретными типами Key и Value приведёт к созданию отдельного конкретного типа HashMap, что означает, что HashMap может содержать ключи и значения непосредственно в своих бакетах, без использования косвенной адресации. А это экономит место, уменьшает количество разименований указателей и позволяет более полно использовать память кеша.

Каждый метод HashMap также скомпилируется в специализированный для заданных типов код. Так что нет дополнительных расходов на диспетчеризацию при вызовах методов hash и eq. Это так же означает, что оптимизатор сможет работать с полностью конкретным кодом — то есть с точки зрения оптимизатора абстракций нет. В частности статическая диспетчеризация позволяет инлайнить параметризованные типами методы.

Вместе с тем, как и в случае шаблонов C++, эти свойства параметрических типов означают, что вы можете писать достаточно высокоуровневые абстракции, которые компилируются в полностью конкретный машинный код, «закодированный наилучшим образом».

Однако, в отличие от шаблонов C++, использование типажей полностью проверяется на корректность типов. То есть когда вы компилируете HashMap сам по себе, его код проверяется на типы только один раз, на корректное использование абстрактных типажей Hash и Eq, а не каждый раз при применении конкретных типов. Что означает как более ясные и ранние ошибки компиляции для авторов библиотек, так и меньшие затраты на проверку типов для пользователей языка (читать «более быстрая компиляция»).

Динамическая диспетчеризация

Мы увидели одну модель компиляции типажей, когда все абстракции разрешаются статически при компиляции. Но иногда абстракции не только нужны для повторного использования кода или модульности, иногда абстракции играют важную роль во время выполнения программы и не могут быть убраны при компиляции.

Например, GUI фреймворки часто используют колбеки для реакции на события, вроде клика мышкой:

trait ClickCallback {
    fn on_click(&self, x: i64, y: i64);
}

Для элементов GUI часто характерна поддержка регистрации нескольких колбеков для одного события. С помощью параметрических типов вы могли бы написать что-то такое:

struct Button<T: ClickCallback> {
    listeners: Vec<T>,
    ...
}

Но тут возникает очевидная проблема: каждая кнопка будет специализирована только для одного типа, реализующего ClickCallback, и это отражается на конкретном типе кнопки. Это совсем не то, что нам нужно! Мы хотим один конкретный тип кнопки Button с набором разнородных получателей события, каждый из которых может быть произвольного конкретного типа, который реализует типаж ClickCallback.

Одна из сложностей при этом состоит в том, что мы имеем дело с группой разнородных типов, каждый из которых может иметь разный размер. Так как же нам их расположить в векторе? Решение стандартно: с помощью косвенной адресации. Мы сохраним в векторе указатели на колбеки.

struct Button {
    listeners: Vec<Box<ClickCallback>>,
    ...
}

Здесь мы используем типаж так, как будто это тип. Вообще-то в расте типажи — это «безразмерные» типы, что примерно означает, что их можно использовать только через указатели, например с помощью Box (указатель на кучу) или & (любой указатель куда угодно).

В расте тип &ClickCallback или Box называется «объект-типаж» и включает в себя указатель на экземпляр типа T, который реализует заданный типаж (ClickCallback), и указатель на таблицу виртуальных методов с указателями на все методы типажа, реализованные для типа T (в нашем случае только метод on_click). Этой информации достаточно, чтобы корректно определить вызываемый метод во время выполнения программы, при этом сохранить единое представление для всех возможных T. Так что тип Button будет скомпилирован только один раз, а абстракции будут существовать и во время выполнения.

Статическая и динамическая диспетчеризация — дополняющие друг друга инструменты, каждый из которых подходит для своих случаев. Типажи в расте дают единую простую систему интерфейсов, которая может быть использована в обоих случаях с минимальной предсказуемой ценой. Объекты-типажи удовлетворяют принципу Страуструпа «плати по необходимости»: у вас есть таблицы виртуальных методов тогда, когда они нужны, но тот же самый типаж может быть статически развёрнут и убран во время компиляции, когда эта сложность не нужна.

Множество способов использовать типажи

Мы увидели то, как могут работать типажи, и их основные способы применения, но они играют и другие важные роли в расте. Несколько примеров:

• Замыкания. Как и типаж ClickCallback, замыкания в расте просто отдельные типажи. Подробнее о том, как они устроены, можно почитать в блоге Хуона Вилсона (Huon Wilson) в этом подробном посте.
• Условные API. Параметрические типы дают возможность реализовать типажи по условию:
  
  

    struct Pair<A, B> { first: A, second: B }
    impl<A: Hash, B: Hash> Hash for Pair<A, B> {
        fn hash(&self) -> u64 {
            self.first.hash() ^ self.second.hash()
        }
    }
  

  
  Здесь тип Pair реализует типаж Hash тогда, и только тогда, когда его компоненты тоже реализуют этот типаж. Это позволяет использовать один и тот же тип в разных контекстах, при этом поддерживая наиболее широкое API, возможное в каждом контексте. Это настолько обычный для раста подход, что есть даже поддержка для автоматического создания некоторых типажей:
  
  

    #[derive(Hash)]
    struct Pair<A, B> { .. }
  

  
  
• Дополнительные методы. Можно использовать типажи для добавления новых методов к существующим типам (которые определены в других местах), подобно расширенным методам (extension methods) в C#. Это свойство происходит напрямую из правил видимости методов типажа: просто добавляете новые методы в типаж, реализуете этот типаж для нужного типа, и всё, методы готовы к использованию!
• Маркеры. В расте есть несколько «маркеров», которые классифицируют типы: Send, Sync, Copy, Sized. Эти маркеры — просто типажи с пустыми телами, которые затем могут быть использованы как в параметрических типах, так и в типажах-объектах. Маркеры могут быть определены в библиотеках, и для них автоматически доступны реализации с помощью #[derive]. Например, если все компоненты типа реализуют Send, то и сам тип может автоматически реализовать Send. Как мы видели раньше, маркеры могут быть очень полезными — с помощью того же маркера Send раст гарантирует потокобезопасность.
• Перегрузка методов. Раст не поддерживает традиционную перегрузку методов, когда один и тот же метод может быть объявлен с разными сигнатурами. Но типажи дают те же преимущества, что и перегрузка: если метод объявлен с типовым параметром, реализующим какой-либо типаж, его можно вызвать с аргументом любого типа, который реализует этот типаж. По сравнению с традиционной перегрузкой методов, у этого подхода есть два преимущества. Во-первых, перегрузка менее ad hoc: как только вы поймёте требуемые типажи, вы сразу же поймёте и способ перегрузки любого API, который их использует. Во-вторых, этот подход очень гибкий: вы можете добавить новые варианты перегрузки методов, просто реализовав нужные типажи для своих типов.
• Перегрузка операторов. Раст позволяет перегружать операторы вроде + для ваших собственных типов. Каждый оператор определяется соответствующим типажом из стандартной библиотеки, и любой тип, реализующий такой типаж, автоматически будет поддерживать и заданные операторы.

Основная мысль: не смотря на кажущуюся простоту, типажи объединяют в себе множество шаблонов проектирования и способов использования, при этом не добавляя в язык никаких дополнительных фич.

Будущее

Один из основных путей эволюции языка — через существующие в нём абстракции, и раст — не исключение: многие из наших приоритетов после версии 1.0 включают расширение системы типажей тем или иным способом. Вот некоторые примеры:

• Статическая диспетчеризация по выходным типам. Сейчас можно использовать типовые параметры для входных аргументов методов, но не для выходного типа: нельзя сказать «эта функция возвращает значение какого-то типа, реализующего типаж Iterator», и при этом получить развёртывание абстракции во время компиляции. Это особенно становится проблемой, когда вы хотите вернуть замыкание, и получить для него статическую диспетчеризацию. Это невозможно в современном расте. Мы хотим сделать это возможным, и у нас уже есть некоторые идеи по этому поводу.
• Специализация. Раст не позволяет перекрываться реализациям типажей, так что двусмысленности по поводу вызываемого метода не возникает. С другой стороны, есть некоторые случаи, когда вы можете написать более общую реализацию, покрывающую множество типов, но потом захотеть сделать более конкретную реализацию для некоторых случаев (что часто требуется, например, при оптимизациях). Мы надеемся, что сможем предложить способы реализовать такое поведение в ближайшем будущем.
• Типы высшего порядка (ТВП, Higher-kinded types, HKT). Типажи сейчас могут быть применены только к типам, а не конструкторам типов (то есть для Vec реализовать типаж можно, а просто для Vec — нет). Это ограничение делает очень сложным предоставить хороший набор типажей для контейнеров, которые поэтому и отсутствуют в стандартной библиотеке. ТВП — очень большая и важная фича, которая даст огромный толчок к развитию абстракций в расте.
  
  Эффективное повторное использование кода. Наконец, хотя типажи предоставляют механизмы для переиспользования кода (что не было упомянуто с этом посте), всё ещё есть подходы к повторному использованию, для которых не вполне подходят средства нынешнего раста, в частности объектно-ориентированные структуры (типа DOM), GUI-фреймворки, многие игры. Поиск подходов к этим проблемам без лишнего дублирования средств и увеличения сложности — довольно интересная проблема проектирования, про которую Нико Матсакис (Niko Matsakis) начал писать отдельную серию постов в своём блоге. Всё ещё не до конца ясно, можно ли сделать всё это с помощью типажей, или требуются какие-то новые ингредиенты.
  

Конечно, мы ещё только подходим к релизу 1.0, и потребуется какое-те время, пока не осядет пыль, а сообщество накопит достаточно опыта, чтобы начать добавлять все эти расширения в язык. Но именно поэтому сейчас замечательное время присоединиться к разработке — начиная с участия в проектировании языка на этом раннем этапе, работе по реализации всех этих фич, и вплоть до испытания различных подходов в своём собственном коде. Мы будем рады вашей помощи!