baa-rs: a Rust implementation of Baa

Status: half of it exists. crates/baa-native is a working Rust runtime: values, the tree-walking interpreter, eight standard-library modules and a Win32 window backend. It passes all 63 conformance programs, byte for byte.

It is deliberately not a whole implementation. There is no lexer, no parser, no resolver, no formatter, no linter and no baa CLI in Rust, because the native application platform does not need them: the reference implementation analyses the program and hands the runtime a resolved tree (see docs/native-runtime.md). One frontend cannot disagree with itself.

So the door this document props open is still open, and the interesting half is still the unwritten one. What follows is the plan for that half; what already exists is described in ARCHITECTURE.md.

Why a second implementation#

The reference implementation (../src/) is TypeScript on Node. That was a pragmatic choice, made for the reasons written up in ARCHITECTURE.md: no build step, one dev dependency, three platforms for free, and a browser playground that runs the real interpreter.

A Rust implementation would buy things TypeScript cannot:

• A single self-contained binary. No Node install, no npm link.
• Millisecond start-up. Node costs ~30 ms before Baa does anything.
• Several times the throughput, and a realistic route to a bytecode VM with

  a tight dispatch loop.

• A path to embedding Baa in another Rust program as a library.

It would also be a genuine test of the specification. Two implementations that agree is evidence the language is defined; one implementation is just a program.

What already exists for you#

You do not start from a blank page. Four artefacts in this repository are implementation-agnostic on purpose:

Both JSON files are generated by ../tools/gen-conformance.ts from the reference implementation, and CI fails if they drift.

The conformance format#

{
  "version": 1,
  "programs": [
    { "name": "truthiness", "source": "baa !nil, !false", "stdout": "true true\n", "exit": 0 }
  ],
  "diagnostics": [
    { "name": "names/undefined", "source": "baa nope", "codes": ["BAA102"], "stage": "check" }
  ]
}

• programs: run the source, compare stdout byte for byte and the exit code.

  Randomness is seeded with 7; nothing in the list depends on the clock, the filesystem or the platform.

• diagnostics: the codes must be reported, in order. stage: "check" means

  they must be found without executing the program.

A port is conformant when it passes both lists. That is a much better first milestone than "it runs hello world".

Proposed crate layout#

Mirroring the reference implementation's stages, because the separation is what makes each one testable on its own:

The runtime that exists occupies one crate:

rust/
├── Cargo.toml
└── crates/
    └── baa-native/             # values, interpreter, stdlib, window model, Win32

A full implementation would add the stages the runtime does not have, mirroring the reference's separation because that is what makes each one testable alone:

rust/
├── Cargo.toml                  # workspace
├── crates/
│   ├── baa-diagnostics/        # Span, SourceFile, the code catalogue, the renderer
│   ├── baa-lexer/              # tokens, trivia, the newline rules
│   ├── baa-ast/                # node types, visitors
│   ├── baa-parser/             # recursive descent, precedence table, recovery
│   ├── baa-sema/               # scopes, mutability, arity
│   ├── baa-runtime/            # values, environments, the interpreter, the host trait
│   ├── baa-stdlib/             # the standard modules
│   ├── baa-fmt/                # the formatter
│   ├── baa-lint/               # lint rules
│   └── baa-cli/                # the `baa` binary
└── tests/
    └── conformance.rs          # reads ../tests/conformance/suite.json

Suggested dependencies, and nothing beyond them: clap for the CLI (or keep the hand-rolled parser: it is only a hundred lines), serde_json for the conformance harness. Baa ships with zero runtime dependencies today; it would be a shame to lose that, and baa-native has managed it so far — its JSON module and its Win32 bindings are both written out by hand.

Sketch of the conformance harness#

// rust/tests/conformance.rs
#[derive(serde::Deserialize)]
struct Suite { programs: Vec<Program>, diagnostics: Vec<Case> }

#[test]
fn matches_the_reference_implementation() {
    let text = std::fs::read_to_string("../tests/conformance/suite.json").unwrap();
    let suite: Suite = serde_json::from_str(&text).unwrap();

    for program in &suite.programs {
        let outcome = baa_runtime::run(&program.source, Seed(7));
        assert_eq!(outcome.stdout, program.stdout, "program: {}", program.name);
        assert_eq!(outcome.exit, program.exit, "program: {}", program.name);
    }

    for case in &suite.diagnostics {
        let codes = baa_sema::check(&case.source).codes();
        assert_eq!(codes, case.codes, "case: {}", case.name);
    }
}

A suggested order of work#

Each step is independently useful and independently testable. Do not build the whole pipeline before running anything.

1. baa-diagnostics. Span, SourceFile with a lazy line index, and the

   renderer. Load the catalogue from diagnostics.json with include_str! or generate a Rust module from it in build.rs. Get the caret rendering right first: everything downstream is judged by it.

2. baa-lexer. Tokens, comment trivia, and the three newline-suppression

   rules from SPEC §2.2. The reference test suite in ../tests/lexer.test.ts translates almost line for line.

3. baa-ast and baa-parser. The EBNF in SPEC §4.1 and §5 is the whole

   grammar. Keep the error recovery: reporting one syntax error at a time is a noticeably worse experience.

4. baa-sema. At this point the stage: "check" half of the conformance

   suite should pass, and you have a working baa check.

5. baa-runtime. A tree-walker first, matching the reference semantics

   exactly. Now the programs half of the suite should pass. This is the milestone that matters: a conformant baa run.

6. baa-stdlib. The standard modules, documented in

   ../docs/stdlib.md, which is itself generated from the implementation and lists every signature.

7. baa-fmt and baa-lint. The formatter must stay a fixed point and must

   never lose a comment; both are asserted in the reference suite and both are easy to get subtly wrong.

8. baa-cli. Match the exit codes in SPEC §9 and the flags in

   ../docs/cli.md.

9. Then, and only then, a bytecode VM. The route is described in

   ARCHITECTURE.md. Doing it before step 8 means optimising a language you have not finished defining.

Design notes for a Rust port#

Things the reference implementation learned, that are worth carrying over.

• Spans everywhere, computed lazily. Line and column come from a

  binary search over a line-start index built on first use. The lexer never pays for them, and diagnostic quality is entirely downstream of recording them properly.

• Comments are trivia attached to tokens, not tokens in the stream. This

  keeps the grammar clean while still letting the formatter round-trip a file.

• Two wordings, one catalogue. Every diagnostic has a sheep-flavoured and a

  neutral form with identical placeholders. Enforce that with a test, as the reference does: a joke that degrades a bug report is not worth having.

• A Host trait, not direct std::fs calls. Everything the runtime does to

  the outside world goes through one interface. That is what makes an in-memory test host possible, and what a future sandbox mode would swap.

• Values without boxing on the hot path. Baa has one numeric type, an f64.

  An enum Value { Nil, Bool(bool), Number(f64), Str(Rc<str>), Array(Rc<RefCell<Vec<Value>>>), ... } keeps primitives unboxed. Rc<RefCell<..>> matches the reference's reference semantics for arrays and maps, including clone() being an explicit deep copy.

• Maps are insertion-ordered. Use indexmap, or a Vec plus a HashMap

  of indices. A plain HashMap will fail the conformance suite.

• return, break and continue are cheap signals. In Rust the natural

  shape is enum Flow { Normal, Return(Value), Break, Continue } returned from exec, rather than the exceptions the reference uses. Either is fine; the Rust version is the tidier of the two.

Ground rules#

If this gets built, it lands under the same terms as everything else here:

• The specification is the arbiter. Where a port and the reference

  disagree, one of them is wrong, and the conformance suite says which. If the specification is unclear, fix the specification first, that is the most valuable kind of contribution this project can receive.

• No silent divergence. Any intentional difference goes in this file, with

  its reason.

• Same house rules. Sheep terminology in module names, error wording and

  documentation only; never in semantics. See CONTRIBUTING.md.

• The reference implementation is not going away. It stays the definition

  of record and keeps the browser playground working. This is a second implementation, not a replacement.

Interested?#

Open an issue tagged rust describing which crate you would like to start with, so two people do not write the lexer twice. Starting at step 1 or 2 and getting it genuinely right is far more useful than a broad half-finished pipeline.