/
Поиск
RU
ENRU

Дженерики

Обобщённая функция (дженерик) — это функция, которая написана один раз, а работает со многими типами. В C того же добиваются макросами или через void* с приведениями типов; в Python обобщена любая функция, потому что до момента выполнения ничего не проверяется. kola, как Rust и C++, проверяет обобщённый код при компиляции, а параметры записывает в квадратных скобках.

Чего в kola нет, так это механизмов, которые другие языки строят вокруг дженериков. В Rust есть трейты (именованные наборы методов, которые тип обязуется предоставить, — аналог интерфейсов в Java или Go), значения dyn, выбирающие нужный метод во время выполнения через таблицу указателей на функции (vtable), и специализация. В kola ничего этого нет. Каждая обобщённая функция и структура мономорфизируется: для каждого конкретного набора аргументов компилятор порождает отдельную обычную функцию, как если бы вы сами написали first_u64 рядом с first_bool. В главе Основы уже встречалась first[T: data]. Здесь речь пойдёт обо всём остальном: как регионы, типы и константы делят один список в скобках, какие бывают ограничения, как хеш-таблица стандартной библиотеки обходится без трейтов и во что обходится мономорфизация.

Шаблоны C++ устроены так же. Альтернатива, которую используют Java и dyn в Rust, — динамическая диспетчеризация: одно общее тело, которое во время выполнения решает, какой конкретный код вызвать. Рецензенту такой подход неудобен тем, что прячет решение: какая реализация выполнится, определяется за косвенным вызовом, которого в месте вызова не видно. В kola, если известно, с какими аргументами инстанцирована функция, код перед глазами — это ровно тот код, который выполнится.

Один список в скобках для регионов, типов и констант

Регион — это арена: область памяти, из которой выделяется всё внутри блока region r { ... } и которая освобождается целиком на закрывающей скобке (см. Память: регионы и ссылки). Функция, принимающая ссылку в регион, называет этот регион своим параметром точно так же, как называет тип. Дженерики и регионы пишутся в одних и тех же квадратных скобках, а <...> в kola не встречается вовсе. Различает их регистр имени. Имя со строчной буквы связывает регион, имя с заглавной — тип, и параметр const тоже пишется с заглавной. fn f[r, T](x: &r T) читается так: «для любого региона r, который есть у вызывающего, и любого типа T, если дана ссылка в r». Вот пример контракта из самой карты, дополненный тестом:

fn split_at[r, T](xs: &r [T], mid: usize) -> (&r [T], &r [T])
    req mid <= xs.len
    ens ret.0.len == mid
{
    (xs[0..mid], xs[mid..xs.len])
}

test split_works {
    region r {
        let xs = alloc in r [10u64, 20u64, 30u64, 40u64];
        let (left, right) = split_at(xs, 2);
        assert left.len == 2 && right.len == 2;
        assert left[0] == 10 && right[0] == 30;
    }
}

Обе половины указывают в тот же регион, что и входной срез. В вызове нет ни r, ни T: оба выводятся из аргумента. Аргументы-типы и аргументы-константы можно написать явно (split_at[u64](xs, 2)), допускается и неполный список — остальное будет выведено. А вот регион в вызове писать нельзя никогда. Компилятор откажет и предложит убрать регион из списка, потому что параметр-регион всегда выводится из вызова. Так задумано: если добавить параметр-регион к существующей обобщённой функции, ни один её вызов не сломается.

С обобщёнными по региону типами иначе. В позиции типа их аргументы-регионы пишутся всегда (Header[r], а не просто Header), потому что это тип, а не вызов.

Ставить регионы первыми, а типы после них — соглашение стандартной библиотеки; чекер порядка не требует.

Ограничения: нет, data и move

Ограничение (bound) — это требование, которое обобщённый параметр предъявляет к принимаемым типам. В Rust ограничение называет трейт, например «T должен поддерживать Clone». Трейтов в kola нет, поэтому ограничение не может потребовать операцию. Оно говорит лишь о том, как можно обращаться со значением параметра: можно ли его копировать и можно ли выбросить. Это важно, потому что значения в kola бывают трёх видов. Обычные данные (числа, структуры из чисел) копируются свободно. Ресурс (открытый файл, сокет) используется ровно один раз: его нельзя ни скопировать, ни молча потерять. Владеющее значение (растущий Vec, которому принадлежит буфер в куче, или Map) переходит от одного владельца к другому и никогда не копируется, так что два имени никогда не делят один буфер. Соответственно, вариантов ограничения три.

Параметр без ограничения принимает любой тип, включая ресурс. Внутри тела T считается линейным: значение типа T используется ровно один раз, его нельзя скопировать и нельзя выбросить. Option[T] и Result[T, E] не ограничены, поэтому Result[File, FsErr] работает так же, как Result[u32, ParseErr], а линейность следит за ресурсом внутри обобщённой обёртки так, будто обёртки нет:

resource struct Ticket { id: u64 }

struct Box[T] { v: T }

fn box_new[T](v: T) -> Box[T] !{} {
    Box { v }
}

fn box_open[T](b: Box[T]) -> T !{} {
    let Box { v } = b;
    v
}

fn close_ticket(t: Ticket) -> u64 !{} {
    let Ticket { id } = t;
    id
}

test unbounded_generic_holds_a_resource {
    let b = box_new(Ticket { id: 7 });
    let t = box_open(b);
    let id = close_ticket(t);
    assert id == 7;
}

Раз тело должно рассчитывать на худшее, значение неограниченного T нельзя продублировать. Функция вроде fn dup[T](x: T) -> (T, T) { (x, x) } будет отвергнута с сообщением «use of consumed resource x», а подсказка предложит ограничение [T: data].

[T: data] обещает, что T — простые копируемые данные: внутри нет ни ресурса, ни чего-либо владеющего (ни собственного Vec, ни Map, ни значения со ссылкой &mut). Тогда тело вправе свободно копировать T, возвращать его по индексу и сравнивать через ==. Передать собственный Vec[u8] в параметр с : data не получится: компилятор откажет в месте вызова и посоветует передать ссылку или убрать ограничение.

[T: move] занимает промежуточное положение. Он принимает данные и владеющие значения, но не ресурсы. Значение T перемещается, его можно выбросить и положить в Vec, но нельзя скопировать. Это ограничение для контейнеров и вспомогательных функций, которые перекладывают собственные буферы:

// Оставить одно из двух значений, а другое выбросить.
fn pick[T: move](old: T, new: T, take_new: bool) -> T !{} {
    if take_new { new } else { old }
}

fn stack_push[T: move](s: &mut Vec[T], x: T) !{alloc(heap)} {
    s.push(x);
}

test move_bound_takes_owned_vecs {
    let a: Vec[u8] = Vec::new();
    let mut b: Vec[u8] = Vec::new();
    b.push(7u8);
    let kept = pick(a, b, true);
    assert kept.len == 1;
    let mut all: Vec[Vec[u8]] = Vec::new();
    stack_push(&mut all, kept);
    assert all.len == 1;
}

Инстанцировать pick типом Ticket нельзя: параметр с : move разрешено выбросить, а ресурс обязан быть израсходован. Любое другое имя ограничения компилятор отвергает, называя его:

fn first[T: copyable](xs: &[T]) -> T !{} {
    xs[0]
}
error[card §2]: unknown bound `copyable` (kola has no traits)
  --> a.kl:1:13
   |
 1 | fn first[T: copyable](xs: &[T]) -> T !{} {
   |             ^^^^^^^^
   = help: the bounds are `data` (copyable, no resources inside) and `move` (moves, may be dropped, never copied; no resources inside)

Обобщённый тип из стандартной библиотеки: Map[a, K, V]

У хеш-таблицы из std::collections::map один параметр-регион и два параметра-типа, и обходится она без всяких трейтов. Map::new(hint, hash, eq) принимает подсказку о ёмкости и две fn-ссылки: одна хеширует ключ, другая сравнивает два ключа. fn-ссылка — это функция, используемая как значение, вроде указателя на функцию в C; из окружения она ничего не захватывает. Таблица хранит обе ссылки и вызывает их напрямую. Для ключей u64 в модуле есть готовые id_u64 и eq_u64, для любого другого типа ключа из data пару функций пишут сами.

Map — владеющее значение: оно перемещается, а не копируется. Функции, которая таблицу читает, передают &m, а той, что её меняет, — &mut m. Методы — get, insert, has, remove, key_at, val_at и cursor, а m.len читается как любое другое .len (вызов m.len() отвергается):

use std::collections::map;
use std::collections::map::Map;

fn total_values[r](m: &Map[r, u64, u64]) -> u64 !{} {
    let mut s: u64 = 0;
    let mut c = m.cursor();
    while c.next() {
        s = s +% c.val();
    }
    s
}

test map_insert_get_replace {
    region r {
        let mut m: Map[r, u64, u64] = Map::new(16, map::id_u64, map::eq_u64);
        let a = m.insert(100, 1);
        let b = m.insert(200, 2);
        assert a && b;
        assert m.get(100) == Some(1u64);
        assert m.get(300) == None;
        let fresh = m.insert(100, 9);
        assert !fresh;
        assert m.get(100) == Some(9u64);
        assert m.has(200) && m.len == 2;
        assert total_values(&m) == 11;
    }
}

insert возвращает true для нового ключа и false, если значение заменено. Результаты вставок связаны с именами до assert, потому что assert не может менять состояние: доказанный assert из сборки удаляется, так что его выражение должно значить одно и то же, выполнится оно или нет.

На практике важны два ограничения. Ёмкость — жёсткий предел, перехеширования нет, поэтому если вставить намного больше различных ключей, чем указано в подсказке (примерно вчетверо), сработает трап, а не постепенная деградация. И курсор — это представление таблицы: пока он используется, вставлять в таблицу и удалять из неё нельзя.

total_values объявляет собственный параметр-регион [r], чтобы назвать Map[r, u64, u64] в своей сигнатуре. Регион, входящий в тип, должен быть где-то связан: объемлющим блоком region r { ... } или списком параметров функции. Типы — элементы модулей, поэтому вне своего модуля таблицу либо импортируют по имени (use std::collections::map::Map;, как здесь), либо пишут с путём: map::Map[r, K, V].

Свой обобщённый тип

Блок impl добавляет методы к обобщённому типу. Его параметры видны во всех методах, а при вызове метода берутся из получателя. Этот небольшой ассоциативный список устроен так же, как Map, и сравнение ключей тоже получает как fn-ссылку:

struct Assoc[a, K, V] {
    eq: fn(K, K) -> bool !{},
    keys: &a mut Vec[K],
    vals: &a mut Vec[V],
}

impl Assoc[a, K: data, V: data] {
    pub fn new(eq: fn(K, K) -> bool !{}) -> Assoc[a, K, V] !{alloc(a)} {
        Assoc { eq, keys: alloc in a mut Vec::new(), vals: alloc in a mut Vec::new() }
    }

    pub fn put(self: &mut Assoc[a, K, V], k: K, v: V) -> bool !{alloc(a)} {
        let eqf = self.eq;
        for i in 0..self.keys.len {
            if eqf(self.keys[i], k) {
                self.vals[i] = v;
                return false;
            }
        }
        self.keys.push(k);
        self.vals.push(v);
        true
    }

    pub fn get(self: &Assoc[a, K, V], k: K) -> Option[V] !{} {
        let eqf = self.eq;
        for i in 0..self.keys.len {
            if eqf(self.keys[i], k) {
                return Some(self.vals[i]);
            }
        }
        None
    }
}

fn same_u64(a: u64, b: u64) -> bool !{} {
    a == b
}

test assoc_put_and_get {
    region r {
        let mut m: Assoc[r, u64, u64] = Assoc::new(same_u64);
        let fresh = m.put(7, 700);
        assert fresh;
        assert m.get(7) == Some(700u64);
        assert m.get(8) == None;
    }
}

Обратите внимание на let eqf = self.eq; перед вызовом. Поле функционального типа вызывают через промежуточное имя или в скобках ((self.eq)(a, b)), потому что self.eq(a, b) было бы вызовом метода.

Одни и те же три функции могут обслуживать два разных типа одновременно. В примере для песочницы ниже ячейка на одно значение живёт в регионе, а преобразование приходит обычной fn-ссылкой. Нажмите «Check», затем «Tests»: cell_new, cell_get и cell_apply инстанцируются один раз для u64 и ещё раз для структуры из двух полей.

use std::log;

struct Cell[a, T] { v: &a mut Vec[T] }

fn cell_new[a, T: data](x: T) -> Cell[a, T] !{alloc(a)} {
    let c = Cell { v: alloc in a mut Vec::new() };
    c.v.push(x);
    c
}

fn cell_get[a, T: data](c: Cell[a, T]) -> T !{} {
    c.v[0]
}

// Преобразование приходит обычной fn-ссылкой.
fn cell_apply[a, T: data](c: Cell[a, T], f: fn(T) -> T !{}) !{} {
    c.v[0] = f(c.v[0]);
}

fn double_u64(x: u64) -> u64 !{} {
    x *% 2
}

struct Point { x: i64, y: i64 }

fn negate(p: Point) -> Point !{} {
    Point { x: -p.x, y: -p.y }
}

fn main(sys: Sys) -> u8 !{io, block, alloc(heap), log} {
    region r {
        let c = cell_new(21u64);
        cell_apply(c, double_u64);
        log::info(f"cell holds {cell_get(c)}");
    }
    0
}

test cell_over_u64 {
    region r {
        let c = cell_new(21u64);
        cell_apply(c, double_u64);
        assert cell_get(c) == 42u64;
    }
}

test cell_over_a_struct {
    region r {
        let c = cell_new(Point { x: 3, y: -5 });
        cell_apply(c, negate);
        let p = cell_get(c);
        assert p.x == -3 && p.y == 5;
    }
}

Обобщение по константам

Иногда функцию нужно обобщить не по типу, а по числу, например по длине массива фиксированного размера. Параметр [const N: usize] связывает такое число типа usize, известное при компиляции. N можно использовать как длину массива ([T; N]), в константной арифметике внутри типа ([T; 2*N], допустимы +, - и *) и как обычное значение usize в теле функции. Каждое отдельное значение N даёт свой тип, поэтому экземпляры одной функции для [u64; 3] и [u64; 8] никогда не совпадают. N выводится из аргумента, если это возможно, или пишется явно: sum[3](&a).

fn sum[const N: usize](a: &[u64; N]) -> u64 !{} {
    let mut s = 0u64;
    for i in 0..N { s = s + a[i]; }
    s
}

fn twice[const N: usize](a: &[u8; N]) -> [u8; 2*N] !{} {
    let mut out = [0u8; 2*N];
    for i in 0..N {
        out[i] = a[i];
        out[N + i] = a[i];
    }
    out
}

test const_generic_fns {
    let a = [1u64, 2u64, 3u64];
    assert sum(&a) == 6;
    assert sum[3](&a) == 6;
    let p = twice(&[7u8, 9u8]);
    assert p.len == 4 && p[3] == 9u8;
}

Параметр-константа может быть и у обобщённого типа. Если в вызове нет ничего, откуда можно вывести N (например, у конструктора без аргументов), его указывают в скобках после имени вызываемой функции:

struct Recent[const N: usize] { slots: [u64; N], next: usize }

impl Recent[const N: usize] {
    pub fn new() -> Recent[N] !{} {
        Recent { slots: [0u64; N], next: 0 }
    }

    pub fn push(self: &mut Recent[N], x: u64) !{} {
        self.slots[self.next % N] = x;
        self.next = self.next + 1;
    }

    pub fn sum(self: &Recent[N]) -> u64 !{} {
        let mut s = 0u64;
        for i in 0..N { s = s +% self.slots[i]; }
        s
    }
}

test recent_keeps_the_last_n {
    let mut w = Recent::new[3]();
    w.push(1);
    w.push(2);
    w.push(3);
    w.push(10);
    assert w.sum() == 15;
}

С параметрами-константами связаны три правила. Имя пишется с заглавной: [const n: usize] отвергается, и подсказка предлагает переименовать параметр в N, потому что имена со строчной буквы связывают регионы. Тип должен быть usize: параметр const B: bool или const K: u32 будет отвергнут с советом написать usize. И длина массива разрешается в константной области видимости, так что локальная переменная времени выполнения не может заменить N: [0u64; n], где n — локальная переменная, отвергается. Если количество вычисляется во время выполнения, нужен Vec.

Чего в дженериках нет

Несколько привычных возможностей дженериков из Rust, C++ или Java в kola просто не к чему прикрепить:

  • Трейт-объекты и vtable. Значений вида «какой-то тип, реализующий X» с выбором метода во время выполнения не бывает. Каждый параметр при компиляции превращается в один конкретный тип.

  • Специализация и перекрывающиеся impl. У обобщённой функции ровно одно тело, и для более конкретного типа его не переопределить.

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

  • Типы высших родов. Параметр — это тип, регион или константа usize, но не конструктор типов.

  • Параметры-типы по умолчанию и обобщённые реализации. struct Pair[A, B = A] не разбирается, и сказать «реализовать это для всех T: data» нельзя.

  • Перегрузка операторов. == — всегда встроенное структурное сравнение языка. Чтобы сравнивать иначе, передайте функцию сравнения fn-ссылкой, как делает Map::new с параметром eq.

Во что обходится мономорфизация

Каждый экземпляр компилируется в собственную копию — отдельно названную функцию, а не общее тело с меткой типа, которую проверяют во время выполнения. Если бы main из примера с ячейкой использовал ещё и Cell с Point, kola build породил бы такие функции (выдержка из сгенерированного C; префикс k_cell__ взят из имени файла cell.kl):

struct k_cell__Cell__uint64_t k_cell__cell_new__uint64_t(KRegion* k_rgn_a, uint64_t x);
uint64_t k_cell__cell_get__uint64_t(struct k_cell__Cell__uint64_t c);
struct k_cell__Cell__struct_k_cell__Point k_cell__cell_new__struct_k_cell__Point(KRegion* k_rgn_a, struct k_cell__Point x);
struct k_cell__Point k_cell__cell_get__struct_k_cell__Point(struct k_cell__Cell__struct_k_cell__Point c);

cell_new и cell_get написаны в исходнике один раз, а в бинарнике встречаются дважды, каждая со своим типом структуры. Размер кода растёт с числом экземпляров, которые программа действительно использует (экземпляр, который никто не вызывает, не порождается вовсе). Взамен нет ни указателя на vtable, ни косвенного вызова, и оптимизатору нечему помешать встроить функцию. Параметр-регион превращается в обычный аргумент KRegion*. Бэкенды, которые порождают этот код, описаны в главе Под капотом.