Практикум: лесенка из восьми шагов

Восемь небольших шагов, и каждый добавляет одну идею языка. Каждый шаг — короткая программа .kl, которую можно запустить прямо на этой странице: нажмите «Запустить» или «Тесты» под примером, измените код и запустите снова. Интерпретатор работает в браузере, ставить ничего не нужно, а с каждого шага есть ссылка на главу, где его идея разобрана подробно.

Шаг 1. Сказать что-нибудь, не имея никаких полномочий

Файл hello.kl:

use std::log;

fn main() -> u8 !{log} {
    log::info("hello, kola");
    0
}

Наведите курсор на выделенные фрагменты, чтобы увидеть пояснения. Сломайте это: замените ряд эффектов !{log} на !{}, то есть пообещайте, что функция не делает вообще ничего, и проверьте программу ещё раз:

error[card §6]: `main` performs `log` (call to `std::log::info`) but does not declare it
  --> hello.kl:4:5
   |
 4 |     log::info("hello, kola");
   |     ^^^^^^^^^^^^^^^^^^^^^^^^
   = help: add `log` to the effect clause, or hand the work to a caller that has it

Эффект — это то, что функция делает помимо вычисления результата: log пишет в журнал, io обращается к внешнему миру, alloc выделяет память. Ряд эффектов их перечисляет, а !{} означает, что их нет вовсе. Здесь в миниатюре видна вся идея языка: сигнатура — это утверждение, и компилятор не даёт ему оказаться ложным. В отличие от комментария, ряд эффектов не может устареть, потому что он проверяется на каждой границе вызова. Подробнее: Быстрый старт.

Шаг 2. Функция и первый тест

Файл area.kl. Тесты лежат рядом с кодом, в том же файле:

fn area(w: u32, h: u32) -> u64 !{} {
    widen[u64](w) * widen[u64](h)
}

test area_works {
    assert area(3, 4) == 12;
    assert area(0, 100) == 0;
}

u32 и u64 — беззнаковые целые на 32 и 64 бита. Произведению двух 32-битных чисел может понадобиться до 64 бит, поэтому функция расширяет оба множителя до умножения. Сломайте это: замените 12 на 13 и посмотрите, как выглядит упавший тест. Затем уберите widen и перемножьте w * h напрямую. Получится u32 там, где сигнатура обещает u64, и компилятор не станет угадывать, какое преобразование вы имели в виду:

error[card §2]: mixed integer widths `u64` and `u32` (no implicit conversions — widen[u64](x) to go wider, wrap[u32](x) to keep the low bits, narrow[u32](x) -> Option to check the fit)

Подробнее: Основы.

Шаг 3. Перечисления и match

Файл lights.kl:

enum Light { Red, Yellow, Green }

fn seconds_to_wait(l: Light) -> u64 !{} {
    match l {
        Light::Red => 30,
        Light::Yellow => 3,
        Light::Green => 0,
    }
}

test lights {
    assert seconds_to_wait(Light::Red) == 30;
    assert seconds_to_wait(Light::Green) == 0;
}

Сломайте это: удалите ветку Light::Yellow => 3,. В kola match обязан покрывать все варианты:

error[card §1]: match is not exhaustive: missing Yellow
  --> lights.kl:4:5
   |
 4 |     match l {
   |     ^^^^^^^^^
   = help: match is exhaustive in kola; add the missing arms or `_`

Забытый вариант — ошибка компиляции, а не сюрприз в продакшене. Подробнее: Основы.

Шаг 4. Выделение памяти: регион и Vec

Файл memory.kl. В kola нет ни malloc, ни free. Память берётся из региона, и весь регион освобождается разом на своей закрывающей скобке:

use std::log;

fn total(xs: &[u64]) -> u64 !{} {
    let mut s: u64 = 0;
    for i in 0..xs.len {
        s = s +% xs[i];
    }
    s
}

fn main() -> u8 !{log, alloc(heap)} {
    region r {
        let v: &r mut Vec[u64] = alloc in r mut Vec::new();
        let mut i: u64 = 1;
        while i <= 10 {
            v.push(i);
            i = i + 1;
        }
        log::info(f"sum 1..=10 = {total(v)}");
    }
    0
}

test totals {
    let a = [2u64, 3u64, 5u64];
    assert total(&a) == 10;
}

Буква f перед f"sum 1..=10 = {total(v)}" включает интерполяцию: в каждой дыре {...} стоит выражение. Обычный литерал "..." никогда ничего не подставляет.

Попробуйте: добавьте тест, который открывает собственный регион и кладёт в него буфер, test peak { region r { let buf = alloc in r [0u8; 4096]; assert buf.len == 4096; } }, и нажмите «Тесты». В установленной kola запустите его командой kola test --sim memory.kl, и симулятор сообщит, сколько памяти на самом деле занял каждый регион:

memory.kl: test peak ... ok
    region r: 4096 bytes region-charged high-water (arena-faithful)

Сколько памяти нужно компоненту, выясняется измерением в тесте, а не тогда, когда операционная система убивает процесс за нехватку памяти. Заметьте: main по-прежнему не принимает sys. Чтобы выделять память в обычном регионе, нужен эффект alloc(heap), а не капабилити. Капабилити нужна только региону с собственным бюджетом (region r from small). Подробнее: Память: регионы и ссылки.

Шаг 5. Ресурс: значение, которое нельзя потерять

Файл tempfile.kl. Всё, что в других языках сопровождается напоминанием «не забудь закрыть» (файл, сокет, транзакция), в kola объявляется как ресурс:

use std::log;

resource struct TempFile { writes: u32 }

impl TempFile {
    pub fn create() -> TempFile !{} {
        TempFile { writes: 0 }
    }
    pub fn write(self: &mut TempFile) !{} {
        self.writes = self.writes + 1;
    }
    pub fn cleanup(self: TempFile) !{log} {
        log::info(f"removed after {self.writes} writes");
        let TempFile { writes: _ } = self;
    }
}

fn main() -> u8 !{log} {
    let mut f = TempFile::create();
    f.write();
    f.write();
    f.cleanup();
    0
}

Сломайте это: удалите строку f.cleanup();:

error[card §2]: resource `f` is not consumed on this path
  --> tempfile.kl:19:5
    |
 19 |     let mut f = TempFile::create();
    |     ^^^
    = help: no implicit destructors: move it on, return it, destructure it, or pass it to a consuming fn

Если в C забыть fclose, утечёт файловый дескриптор — небольшое число, которым операционная система обозначает открытый файл. Долго работающий сервер, который их теряет, в конце концов не сможет открыть ни одного нового. В kola забытое закрытие — ошибка компиляции, а не утечка. Подробнее: Ресурсы и линейность.

Шаг 6. Капабилити: песочница из трёх функций

Файл sandbox.kl. На этом шаге каждая функция получает ровно столько доступа к миру, сколько ей нужно:

use std::log;

enum Verdict { Clean, Suspicious }

// Разбирает недоверенные байты. Не получает капабилити и не объявляет эффектов.
pub fn scan[r](payload: &r [u8]) -> Verdict !{} {
    let mut zeros = 0;
    for i in 0..payload.len {
        if payload[i] == 0 { zeros = zeros + 1; }
    }
    if zeros * 4 > payload.len { Verdict::Suspicious } else { Verdict::Clean }
}

// Единственная функция, которая говорит. Журнал — это эффект, а не
// капабилити, так что и у неё нет никаких полномочий над миром.
fn report(v: Verdict) !{log} {
    match v {
        Verdict::Clean => log::info("payload: clean"),
        Verdict::Suspicious => log::info("payload: suspicious"),
    }
}

fn main() -> u8 !{log, alloc(heap)} {
    region r {
        let good = alloc in r [1u8, 2u8, 3u8, 4u8];
        let bad  = alloc in r [0u8, 0u8, 7u8, 0u8];
        report(scan(good));
        report(scan(bad));
    }
    0
}

test clean_payload_passes {
    region r {
        let p = alloc in r [1u8, 2u8, 3u8, 4u8];
        assert scan(p) == Verdict::Clean;
    }
}

test zero_heavy_payload_flagged {
    region r {
        let p = alloc in r [0u8, 0u8, 7u8, 0u8];
        assert scan(p) == Verdict::Suspicious;
    }
}

Сломайте это: заставьте scan что-нибудь сказать. Добавьте первой строкой её тела log::info(f"scanning {payload.len} bytes");:

error[card §6]: `scan` performs `log` (call to `std::log::info`) but does not declare it
  --> sandbox.kl:7:5
   |
 7 |     log::info(f"scanning {payload.len} bytes");
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = help: add `log` to the effect clause, or hand the work to a caller that has it

Теперь попробуйте что-нибудь с настоящим доступом к миру. Замените эту строку на let t = clock.now();:

error[card §1]: unknown name `clock`
  --> sandbox.kl:7:13
   |
 7 |     let t = clock.now();
   |             ^^^^^

Глобальных переменных в kola нет, поэтому никаких часов «под рукой» тоже нет. Получить их можно только через параметр. Добавьте в список параметров clock: &Clock, и появится следующая стена: чтение часов — это эффект io, а ряд эффектов !{} его запрещает:

error[card §6]: `scan` performs `io` (Clock::now) but does not declare it

Если расширить ряд до !{io}, каждому вызывающему придётся передавать Clock и тоже объявлять io, и так до самого main, причём это будет видно в каждой сигнатуре по пути. Поэтому для аудита scan достаточно прочитать её сигнатуру, и это останется верным, даже если завтра тело перепишут, сгенерирует модель или оно разрастётся до тысячи строк. Подробнее: Эффекты и капабилити.

Шаг 7. Контракты и воспроизводимая случайность

Файл contracts.kl:

fn pick(xs: &[u64], i: usize) -> u64 !{}
    req i < xs.len
{
    xs[i]
}

fn dice(rng: &mut Rng) -> u64 !{}
    ens ret >= 1, ret <= 6
{
    rng.weak_u64() % 6 + 1
}

test picking {
    let xs = [10u64, 20u64, 30u64];
    assert pick(&xs, 2) == 30;
}

test dice_is_fair_enough(mut sim: Sim) {
    let mut i = 0;
    while i < 100 {
        let d = dice(&mut sim.rng);
        assert d >= 1;
        assert d <= 6;
        i = i + 1;
    }
}

Сломайте это: замените вызов в первом тесте на pick(&xs, 5):

contracts.kl: test picking ... FAILED (seed 1802464353)
error[card §8]: req violated calling `pick`
  --> contracts.kl:2:9
   |
 2 |     req i < xs.len
   |         ^^^^^^^^^^
   = help: contracts are always enforced: proven statically or trapped at runtime
contracts.kl: test dice_is_fair_enough ... ok

1 passed, 1 failed

Ошибка указывает на нарушенный контракт. Зерно рядом с сообщением о падении — это начальное число генератора псевдослучайных чисел теста: если запустить тест снова с тем же зерном, все «случайные» значения повторятся, и падение воспроизведётся в точности. За границы массива pick так и не вышла, потому что проверка выполнилась до тела функции. А корректный вызов pick(&xs, 2) во время выполнения ничего не стоит: компилятор его доказал и проверку убрал. Что можно доказать, исчезает; что нельзя, проверяется; отключить нельзя ни то, ни другое.

В установленной kola запустите kola test --sim --seed 7 contracts.kl дважды. Прогоны совпадут в точности, потому что вся случайность берётся из зерна. Подробнее: Контракты, трапы и тесты.

Шаг 8. Финал: разбор двоичного кадра

Файл frame.kl. Здесь всё собирается вместе: структура со ссылкой, регион, Result и стандартная библиотека. Формат кадра: один байт тега, длина полезной нагрузки в виде u16 big-endian, затем сама нагрузка. Big-endian означает, что старший байт идёт первым; так принято в сетевых протоколах:

use std::encoding::bytes;

// Кадр: [ tag:u8 | len:u16 be | payload:len байт ]
enum FrameErr { Short, LengthMismatch }

struct Frame[r] { tag: u8, payload: &r [u8] }

fn parse[r](b: &r [u8]) -> Result[Frame[r], FrameErr] !{} {
    if b.len < 3 { return Err(FrameErr::Short); }
    let len = bytes::rd16(b, 1);
    if widen[usize](len) + 3 != b.len { return Err(FrameErr::LengthMismatch); }
    Ok(Frame { tag: b[0], payload: b[3..] })
}

test parses_good_frame {
    region r {
        let b = alloc in r [7u8, 0u8, 2u8, 170u8, 187u8];
        match parse(b) {
            Ok(f) => {
                assert f.tag == 7;
                assert f.payload.len == 2;
                assert f.payload[0] == 170;
            }
            Err(_) => { assert false; }
        }
    }
}

test rejects_short {
    region r {
        let b = alloc in r [7u8, 0u8];
        assert parse(b) == Err(FrameErr::Short);
    }
}

test rejects_length_mismatch {
    region r {
        let b = alloc in r [7u8, 0u8, 9u8, 170u8];
        assert parse(b) == Err(FrameErr::LengthMismatch);
    }
}

Упражнение: добавьте вариант FrameErr::BadTag, отвергайте кадры с нулевым тегом и напишите на это тест. Если где-то match по FrameErr перечисляет варианты поимённо, он перестанет компилироваться, как только появится новый: это та самая исчерпываемость из шага 3.

Готовый парсер — чистая функция без единой капабилити, та же песочница из шага 6, только полученная самим устройством кода. Так выглядит большая часть настоящего кода на kola: на входе враждебные байты, на выходе простые данные, а капабилити остаются на краю программы, где рецензент видит их все сразу.

Модуль называется std::encoding::bytes, а не std::bytes; если ошибиться, компилятор подскажет, где он находится. kola help std-index перечисляет все публичные элементы стандартной библиотеки.