Skip to main content

Crate kaalang

Crate kaalang 

Source
Expand description

§kaalang

crates.io docs.rs CI

We be of one blood, thou and I - man and snake together.

Kaa - from Rudyard Kipling’s “The Spring Running”, The Second Jungle Book

kaalang is a visual flow dialect of Rust for understanding what a program does and how its parts fit together. Inspired by DRAKON, it makes the structure of an algorithm explicit in code.

You write an algorithm as described steps, decisions, and cycles, with explicit inputs and outputs, and Rust expressions implement the computations inside those blocks. The same validated flow becomes ordinary Rust code and a readable diagram, whether a person or AI wrote it.

Work in progress.

§A first flow: FizzBuzz

A flow is a Rust function marked with #[kaa].

use kaalang::kaa;

#[kaa]
fn fizzbuzz(number: u32) -> String {
    #[kaa::choice("Which of 3 and 5 divide the number?")]
    #[kaa::case("Both 3 and 5.")]
    #[kaa::case("Only 3.")]
    #[kaa::case("Only 5.")]
    #[kaa::case("Neither 3 nor 5.")]
    let (fizz_buzz, fizz, buzz, plain) = |number| match (number % 3, number % 5) {
        (0, 0) => (),
        (0, _) => (),
        (_, 0) => (),
        _ => number,
    };

    #[kaa::action("🎉 Use `FizzBuzz` for this number.")]
    let end = |fizz_buzz| String::from("FizzBuzz");

    #[kaa::action("🫧 Use `Fizz` for this number.")]
    let end = |fizz| String::from("Fizz");

    #[kaa::action("🐝 Use `Buzz` for this number.")]
    let end = |buzz| String::from("Buzz");

    #[kaa::action("🔢 Use the number itself, written as text.")]
    let end = |plain| plain.to_string();

    |end| return end;
}

Diagram of the FizzBuzz flow

Source

§Reading the flow

A wire is a named value passed between blocks. The function parameter provides the first wire, number. Each block lists the wires it captures between |...| and names the wires it produces after let.

In the exampleWhat happens
let (fizz_buzz, fizz, buzz, plain) = ...The choice evaluates its match and provides only the selected output. Cases, outputs, and match arms correspond by position.
let end = |fizz| ...Capturing fizz places this action on the Fizz branch, even though its body does not use that unit value.
Four declarations of endThe branches are mutually exclusive. Their results merge into one wire for the shared continuation.
|end| return end;The flow returns whichever branch supplied end.

For number = 9, only fizz is selected, so only the “Use Fizz for this number” action runs. The diagram’s connections show execution paths; input and output names appear as labels along those paths.

The #[kaa] macro translates the capture notation into ordinary Rust bindings and control flow. Blocks execute in source order along the selected path. Rust checks types, ownership, borrowing, and lifetimes. kaalang checks that the flow admits a diagram under its visual rules before compiling it.

§Anatomy of a block

Here is the last action from FizzBuzz, with its Rust body wrapped in braces:

ⓘ
#[kaa::action("🔢 Use the number itself, written as text.")]  // kind + description
let end = |plain| {                                      // output = |inputs|
    plain.to_string()                                    // Rust body
};
PartIn this actionVariations
Kind and description#[kaa::action("...")]Both are required for an action. The description labels its diagram node.
Outputslet end =Omit for an effect returning (). Use let (left, right) = to expose two outputs.
Inputs|plain|Omit it when there are no inputs. Every wire used by the body must be listed here.
Body{ plain.to_string() }A Rust expression. An action may omit the braces, as in the full example.

Actions can also create a value without inputs, consume inputs without producing outputs, or perform an effect with neither:

ⓘ
// No inputs: the capture list can be omitted.
#[kaa::action("Start with fifteen.")]
let number = 15;

// No outputs.
#[kaa::action("Print the result.")]
|&end| { println!("{end}") };

// Neither: the empty capture list can be omitted too.
#[kaa::action("Announce the flow.")]
{
    println!("start");
};

Captures express how an action accesses a wire:

InputAccess
nameMove or copy the value.
mut nameMove or copy into a mutable local binding.
&nameBorrow the value.
&mut nameMutably borrow a wire declared mutable.

§Formatting descriptions

Descriptions accept a small inline notation:

WriteShows
**bold** or __bold__, *italic* or _italic_, ~~struck~~Bold, italic, strikethrough
`code`Inline code
x^2^, H~2~OSuperscript, subscript
> quote at the start of a lineA quoted line
$\sqrt{x}$, $$\sum_i x_i$$Inline TeX formula; $$…$$ uses display layout
<u>…</u>, <mark>…</mark>, <color name="red">…</color>Underline, highlight, palette color (red, green, blue, purple, muted)

The Write column shows the description text. In an ordinary Rust string, double each backslash and escape each quote, as in "$\\sqrt{x}$", or use a raw string such as r#"<color name="red">…</color>"#. Formatting changes only the diagram; the generated Rust is the same. A marker without its pair stays literal, and a backslash before a marker keeps it literal: \\* in an ordinary string, \* in a raw one. Diagrams show the text effects, formulas, and literal fallbacks.

§Block kinds

KindRole in a flow
actionPerform a computation or effect with a Rust expression.
callCall one named Rust function. Its path supplies the description if omitted.
questionSelect one of two branch outputs using a boolean expression.
choiceSelect one output from the cases of a Rust match.
cycleRepeat a nested kaalang sequence whose blocks capture the surrounding wires.
stageGroup blocks into a named step selected by an incoming signal.
continueStart the next iteration of the directly containing loop cycle.
returnComplete the root flow and hand back its result.

Actions, calls, and cycles can have no outputs. Questions and choices always declare their branch outputs. A cycle takes one of two forms. A loop cycle’s loop { ... } body contains kaalang blocks. A route through it can repeat at its continue, complete with one of its declared outputs, or diverge in a nested cycle. A completed output becomes available after the cycle. In the diagram, continue routes meet at the cycle’s back edge, and completing routes leave through the cycle boundary. A for cycle, written |items| for item in items { ... }, instead runs its body once per item of a Rust iterator. It has no continue or early exit and may declare one output, the signal that its items ran out. Its diagram has no boundary or back edge: a for-entry node holds the description and hands over the item, and every iteration ends at a for-end node below it, which repeats the description and from which the flow continues once the items run out.

use std::cmp::Ordering;

use kaalang::kaa;

#[kaa]
fn binary_search(values: &[i32], target: i32) -> Option<usize> {
    #[kaa::action("📏 Start with the entire sorted list.")]
    let (mut left, mut right) = |values| (0, values.len());

    #[kaa::cycle("🔍 Narrow the range until the target is found or ruled out.")]
    let result = loop {
        #[kaa::question("Are any values left in the search range?")]
        #[kaa::yes("YES")]
        #[kaa::no("NO")]
        let (iterate, leave) = |left, right| left < right;

        #[kaa::action("🚫 Report that the target is absent.")]
        let result = |leave| None;

        #[kaa::action(r"📍 Select the middle value, $$\mathrm{mid} = \mathrm{left} + \left\lfloor \frac{\mathrm{right} - \mathrm{left}}{2} \right\rfloor$$.")]
        let (mid, value) = |iterate, values, left, right| {
            let mid = left + (right - left) / 2;
            (mid, values[mid])
        };

        #[kaa::choice("How does this value compare with the target?")]
        #[kaa::case("Less than the target.")]
        #[kaa::case("Greater than the target.")]
        #[kaa::case("Equal to the target.")]
        let (less, greater, equal) = |value, target| match value.cmp(&target) {
            Ordering::Less => (),
            Ordering::Greater => (),
            Ordering::Equal => (),
        };

        #[kaa::action("➡️ Discard this value and everything to its left.")]
        let stepped = |less, mid, &mut left| *left = mid + 1;

        #[kaa::action("⬅️ Discard this value and everything to its right.")]
        let stepped = |greater, mid, &mut right| *right = mid;

        #[kaa::action("🎯 Report the position of this matching value.")]
        let result = |equal, mid| Some(mid);

        |stepped| continue;
    };

    |result| return result;
}

Diagram of binary search in kaalang

Source

The cycle’s blocks capture the surrounding left and right, declared mut so the less and greater branches can update them. Both then produce stepped, merging before the shared continue that starts the next iteration. The equal and leave branches instead produce result, the cycle’s declared output. They merge at the end of the body, and the cycle hands result to the flow, which returns it.

See the same flow with its cycle collapsed

Binary search with its cycle collapsed

The cycle’s description and interface remain visible while its body is hidden.

Both examples are gallery examples, with SVGs generated from their source through cargo kaalang. The gallery also includes swap, a flow that returns its inputs without a computational block, bubble sort, with nested cycles, quicksort, with stages for in-place partitioning and recursion, and KMP search, with stages for comparison, advancement, and prefix fallback.

§Stages

Stages make the steps of a state machine explicit. The compiler generates the dispatch loop, and the diagram labels transitions between stages. A stage’s header names the signal that enters it. A stage moves to another by producing that stage’s signal as one of its declared outputs, and the stage that holds return comes last.

This empty state machine only follows First → Second → Finish. With stages:

State machine with stages

Source

Without stages, the diagram shows the cycle and the choice that selects the current state:

State machine with an explicit dispatcher

Source

Both versions follow the same path.

§Stages in practice: quicksort

use core::cmp::Ordering;

use kaalang::kaa;

#[kaa]
pub(crate) fn quick_sort<T: Ord>(values: &mut [T]) {
    #[kaa::stage("Check the range.")]
    let (partition, finish) = |values| {
        #[kaa::question("Are there at least two values?")]
        #[kaa::yes("YES")]
        #[kaa::no("NO")]
        let (split, finish) = |&values| values.len() > 1;

        #[kaa::action("Take the unsorted range.")]
        let partition = |split, values| values;
    };

    #[kaa::stage("Partition the range.")]
    let recur = |partition| {
        #[kaa::action("Choose the middle value as the pivot; set it aside at the end.")]
        let (mut range, mut lower, mut cursor, mut upper, pivot) = |partition| {
            let pivot = partition.len() - 1;
            partition.swap(partition.len() / 2, pivot);
            (partition, 0, 0, pivot, pivot)
        };

        #[kaa::cycle("Group the other values around the pivot.")]
        let classified = loop {
            #[kaa::question("Are any values unclassified?")]
            #[kaa::yes("YES")]
            #[kaa::no("NO")]
            let (select, classified) = |cursor, upper| cursor < upper;

            #[kaa::action("Select the first unclassified value.")]
            let value = |select, &range, cursor| &range[cursor];

            #[kaa::choice("How does this value compare with the pivot?")]
            #[kaa::case("Less than the pivot.")]
            #[kaa::case("Equal to the pivot.")]
            #[kaa::case("Greater than the pivot.")]
            let (less, equal, greater) = |value, &range, pivot| match value.cmp(&range[pivot]) {
                Ordering::Less => (),
                Ordering::Equal => (),
                Ordering::Greater => (),
            };

            #[kaa::action("Put this value in the left group.")]
            let stepped = |less, &mut range, &mut lower, &mut cursor| {
                range.swap(*cursor, *lower);
                *lower += 1;
                *cursor += 1;
            };

            #[kaa::action("Keep this value in the middle group.")]
            let stepped = |equal, &mut cursor| *cursor += 1;

            #[kaa::action("Swap this value into the right group; check its replacement next.")]
            let stepped = |greater, &mut range, cursor, &mut upper| {
                *upper -= 1;
                range.swap(cursor, *upper);
            };

            |stepped| continue;
        };

        #[kaa::action("Place the pivot with its equals; separate the left and right groups.")]
        let recur = |classified, range, lower, upper, pivot| {
            range.swap(upper, pivot);
            let (left, rest) = range.split_at_mut(lower);
            let (_, right) = rest.split_at_mut(upper + 1 - lower);
            if left.len() <= right.len() {
                (left, right)
            } else {
                (right, left)
            }
        };
    };

    #[kaa::stage("Sort the smaller group.")]
    let values = |recur| {
        #[kaa::action("Take the smaller and larger outer groups.")]
        let (smaller, larger) = |recur| recur;

        #[kaa::call("Sort the smaller group recursively.")]
        let sorted_part = |smaller| quick_sort(smaller);

        #[kaa::action("Continue sorting the larger group.")]
        let values = |sorted_part, larger| larger;
    };

    #[kaa::stage("Finish sorting.")]
    |finish| {
        return;
    };
}

Only the smaller outer group is sorted recursively. The values signal sends the larger group back to the first stage, keeping the recursive call stack logarithmic.

With the partitioning cycle collapsed, the four stages are easier to see:

Quicksort with its partitioning cycle collapsed

Source · Expanded diagram

§Types

A struct, enum, union, or type alias marked #[kaa] is a datatype. Its fields carry descriptions, and a field can name the type it stands for, even when Rust stores only a key:

ⓘ
#[kaa("A **shop order**, with its revision history and split shipments.")]
pub struct Order {
    #[kaa::value("The order's number, unique in the shop.")]
    pub number: OrderNumber,
    #[kaa::refer(Customer, "Who placed the order.")]
    pub(crate) customer: CustomerId,
    #[kaa::refer(Line, r"Items and quantities. Total: $\sum_i q_i p_i$.")]
    lines: Vec<Line>,
    #[kaa::refer(Self, "The original order, when this is a *split shipment*.")]
    pub(crate) split_from: Option<OrderNumber>,
    #[kaa::refer(Self, "The previous revision, kept for audit. `None` on creation.")]
    previous: Option<Box<Self>>,
}

#[kaa("Money received for an order.")]
#[repr(C)]
struct Payment {
    #[kaa::refer(Order, "The order the money is for.")]
    order: OrderNumber,
    #[kaa::value("The amount received.")]
    amount: Money,
    #[kaa::value("The bank's reference for the transfer.")]
    reference: String,
}

value describes a field. refer also names the type the field refers to: Payment stores the order’s number, and refers to Order. The annotations do not change the Rust declaration, and Rust checks that each target exists.

A type’s diagram draws it under every type that refers to it:

Diagram of the Order type under the types that refer to it

Source

The diagram combines self-references, a tuple identifier with repr(transparent), generic events, a borrowed receipt, an enum with repr(u8) and both tuple and named fields, and an alias.

A type’s name and its fields, like a flow’s name in its start node, carry a UML visibility marker: + for pub, ~ for pub(crate) and other restricted forms, and - for private.

§Try it

Add the macro to a project:

cargo add kaalang

Install the released CLI from crates.io:

cargo install kaalang-cli

Or install the version from the current repository checkout:

cargo install --path crates/kaalang-cli

Run the gallery and its checks from a repository checkout.

cargo run -p kaalang --example gallery

Draw the FizzBuzz diagram through the CLI.

cargo kaalang diagram --flow fizzbuzz::fizzbuzz -o fizzbuzz.svg

The flow is named by its path from the crate root; --collapse-cycles draws the collapsed cycle view. The output is a standalone SVG that needs no external rendering tools.

Draw the Order type the same way, by its path:

cargo kaalang diagram --type order::Order

§Read more

Attribute Macros§

kaa
Turns a function written as a kaalang flow into ordinary Rust, after checking that the flow has a diagram, or checks a datatype and emits it without its annotations. The kaalang crate documentation describes the syntax.