169 Reference Implementation

A reference implementation of the Predica language is being developed in C++. It is a work in progress. Development began in April 2026.

The initial emphasis is on developing a Turing-complete language in which databases can be created or opened and can be the targets of updates and queries. Predica supports defining types and functions, writing statement-based code, and using control-flow constructs such as loops. The question of how to use Predica from other host languages will be addressed in the future.

Performance summary

The lexer and parser support the complete language described by the grammar chapters and convert Predica source files into ASTs at about 80 MB/sec, or about 4 million lines per second.

Source files

Stable immutable source buffers

The lexer, AST, and parser operate on a std::string_view containing one complete source file. The source is a contiguous immutable byte buffer and remains alive while a parsed result is in use. Tokens and AST nodes can therefore identify text by byte offset and length without allocating strings.

SourceFiles owns loaded source buffers at stable addresses. Adding another file does not invalidate an earlier file, its path, its text, or its file ID. A file is opened in binary mode at its end, its size is obtained with tellg(), and its string is allocated once before a direct read. Source loading deliberately requires an ordinary seekable file and detects a file which grows or shrinks during the read.

Line and column work is kept out of the lexer

Human-readable positions are needed when a diagnostic is displayed, not for every token and AST node. A loaded source file eagerly records the 32-bit byte offset of each line start. Given an error offset, std::upper_bound performs a binary search for the containing line; the byte column is then a subtraction from that line start. This keeps tokens compact and avoids updating line and column state in the lexer hot path.

Lexer

A token is already in its retained representation

The lexer tracks its current byte offset, so it returns the representation which the parser will retain directly:


enum class TokenKind : std::uint8_t
{
    EndOfFile,
    Identifier,
    Keyword,
    BooleanLiteral,
    IntegerLiteral,
    RealLiteral,
    StringLiteral,
    Operator,
    Punctuation
};

struct Token
{
    std::uint32_t begin;
    std::uint32_t size;
    TokenKind kind;
};

static_assert(sizeof(Token) == 12);

Earlier versions returned a TokenKind and std::string_view, then converted each token into a separate 12-byte stored form. The current representation removes that conversion and halves the size of tokens retained in a vector from 24 to 12 bytes. Token text is reconstructed temporarily from the source only when the parser needs to inspect its spelling. The EOF token has an empty range beginning at source.size().

Capacity is estimated and reused

Before tokenisation, the token vector reserves capacity estimated from the source size. A parser workspace retains that vector between files, so later parses clear its logical contents without releasing its allocation. Compact tokens reduce both the final vector size and the copying performed if an estimate is exceeded.

In the current benchmark, a reserved vector and a reused vector sustain about 125 MB/s and 127 MB/s respectively, compared with about 129 MB/s when tokens are consumed immediately without retaining them. Token storage is therefore a small part of total lexer time. The earliest implementation measured about 61 MB/s when retaining tokens and 77 MB/s when consuming them immediately, so the retained-token path is now approximately twice as fast.

These measurements use approximately 10 MB of source on the development x86-64 Linux laptop, compiled by GCC 13.3.0 in release mode. Laptop temperature causes visible variation, so the figures describe sustained ranges rather than portable absolute limits.

Common bytes take short paths

ASCII punctuation and operators are selected by direct first-byte dispatch. Identifiers are scanned with simple ASCII range tests, and keywords are found by binary search in a sorted table. Less common Unicode operators are matched against a compact table, with longer prefix-sharing spellings first. Once a known Unicode spelling has matched, its bytes are not validated a second time. Arbitrary non-ASCII input in comments and string literals is still fully validated, including rejection of overlong UTF-8, surrogate encodings, and code points outside the Unicode range.

Assertions support strong hot-path assumptions

The implementation follows programming by contract: public interfaces state strong preconditions and postconditions, while the implementation maintains explicit invariants. For example, source loading and the public parser establish that a file fits the 32-bit source-offset representation. The lexer and token buffer can therefore narrow offsets directly. Assertions check the contract and invariants in debug builds without adding repeated branches to release hot paths.

This is deliberately different from applying Postel's law within the compiler pipeline. Silently accepting malformed inputs or defensively accommodating states that preceding layers promised not to produce would weaken the contracts, obscure programming errors, and cost performance. Invalid source text is, of course, reported as a normal diagnostic; a violated internal contract is instead treated as an implementation defect.

Abstract Syntax Tree

Named integer indexes replace pointers

Expressions, type expressions, statements, and declarations are held in four separate contiguous vectors. Recursive relationships use named aliases for 32-bit integer indexes rather than pointers to separately allocated nodes. They are deliberately aliases rather than integer wrapper classes: their names document their meaning while allowing direct, uncluttered vector indexing.


using SourceOffset = std::uint32_t;

using ExpressionIndex = std::uint32_t;
using TypeExpressionIndex = std::uint32_t;
using StatementIndex = std::uint32_t;
using DeclarationIndex = std::uint32_t;
using HeapIndex = std::uint32_t;

struct HeapSlice
{
    HeapIndex begin;
    std::uint32_t count;
};

using ExpressionIndexSlice = HeapSlice;
using TypeExpressionIndexSlice = HeapSlice;
using StatementIndexSlice = HeapSlice;
using DeclarationIndexSlice = HeapSlice;

Slice aliases similarly state what the words in a slice mean without adding a new representation or traversal abstraction. Indexes remain valid when vectors move or reallocate, and a complete parsed file is relocatable without rewriting links between nodes. Later compiler passes can store semantic facts in separate arrays addressed by the same indexes, leaving the syntax tree compact and effectively immutable.

Common nodes are fixed-size records

The principal node types each occupy 16 bytes. A node is a compact tagged record whose kind determines the interpretation of detail, data0, and data1. A binary expression, for example, stores its operator in detail and the indexes of its operands in data0 and data1.


struct Expression
{
    SourceOffset source;
    ExpressionKind kind;
    std::uint8_t detail;
    std::uint16_t reserved;
    std::uint32_t data0;
    std::uint32_t data1;
};

static_assert(sizeof(Expression) == 16);

A heap stores variable-sized AST data

The Heap class owns one contiguous vector of 32-bit words. The parser appends variable-length arrays and less common records to this vector. A HeapIndex identifies a record. A HeapSlice identifies the first word of an array and records its number of elements. Records are copied with memcpy, avoiding alignment, object-lifetime, and aliasing problems which would result from casting the word storage to arbitrary record types. Clearing the heap removes its contents but retains the vector's capacity for the next file.


class Heap
{
public:
    template<class T> HeapIndex append(const T& value);
    template<class T> HeapSlice appendArray(const std::vector<T>& values);
    template<class T> T read(HeapIndex index) const;
    void clear() noexcept;

private:
    std::vector<std::uint32_t> words_;
};

struct AstArena
{
    std::vector<Expression> expressions;
    std::vector<TypeExpression> typeExpressions;
    std::vector<Statement> statements;
    std::vector<Declaration> declarations;
    Heap heap;
};

Source provenance is compact and external

A node normally stores a 32-bit byte offset rather than a pointer, line and column, or complete source range. Source-backed text is represented by an offset and byte count. The parsed result aliases its immutable source buffer; it does not own or copy that buffer.


struct ParsedSourceFile
{
    std::string_view source;
    AstArena arena;
    SourceFile root;
};

Parser

The public API makes allocation reuse possible

Returning a large allocation-owning result by value can avoid copying through move elision, but it cannot return the result's vector capacity to the next parse. The public API therefore takes both reusable temporary storage and the output by reference:


void parseSourceFile(
    std::string_view source,
    ParserWorkspace& workspace,
    ast::ParsedSourceFile& output);

ParserWorkspace is opaque in the public header and retains compact token storage. The output owns its AST arena. Before parsing, the five arena vectors are cleared without releasing capacity. A compiler can keep one workspace per parsing thread and reuse an output sequentially, while retaining independent outputs for files whose ASTs must remain available.

The public-API benchmark measures both patterns. Creating a workspace and output for every parse sustains about 66 MB/s. Reusing the token buffer and all five AST vector allocations sustains about 78 MB/s, an improvement of approximately 17%. This difference is why the performance test goes through the public API rather than constructing private parser machinery.

The parser writes directly into the final arena

The parser is a hand-written recursive-descent parser with separate functions for declarations, statements, type expressions, and expression precedence levels. It tokenises the complete file once, advances through the contiguous token vector by index, appends completed nodes directly to the output arena, and returns typed 32-bit indexes. There is no pointer-rich intermediate syntax tree and no per-node allocation.


class Parser
{
public:
    Parser(
        std::string_view source,
        ast::AstArena& arena,
        std::vector<Token>& tokenStorage);

    ast::SourceFile parseSourceFile();

private:
    ast::ExpressionIndex expression();
    ast::TypeExpressionIndex typeExpression();
    ast::StatementIndex statement();
    ast::DeclarationIndex declaration();

    TokenBuffer tokens_;
    std::size_t current_ = 0;
    ArenaBuilder arena_;
};

Sentinel tokens remove repeated bounds branches

The token buffer appends a second EOF token as a sentinel. Parser lookahead can then inspect one token beyond the ordinary EOF position without a bounds test. For example, qualified-name and procedure-call recognition can examine the token after a trailing dot safely. The parser asserts that ordinary advancement never consumes EOF, making the sentinel an internal invariant rather than error recovery.

32-bit overflow is checked outside hot paths

Every AST belongs to one source file, not to an entire multi-file component. The source-size limit therefore bounds typed node counts and slice element counts for that file; debug builds assert those relationships when nodes are appended.

The heap can expand by more than one word per source byte, so its final size still requires a release-build check. Checking every record and array append reduced parser throughput by 2–4%. Instead, heap indexes are not dereferenced during construction, and the four node-vector sizes and heap size are validated once after parsing and before the root is published. If a size cannot be represented, parsing throws a structured ParseError.

Separately retained old and new benchmark executables were run in alternating order to control for laptop temperature and scheduling. End-of-parse validation measured about 0.7% faster than the baseline in both fresh and reused modes, a difference small enough to treat as performance-neutral.

Errors store facts, not formatted messages

enum class ParseErrorKind : std::uint8_t
{
    ExpectedSpelling,
    ExpectedSyntax,
    IntegerLiteralTooLarge,
    ...
};

enum class ParseExpectation : std::uint8_t
{
    Unspecified,
    Expression,
    Declaration,
    ...
};

enum class ParseExpectedSpelling : std::uint8_t
{
    Unspecified,
    LeftBrace,
    RightBrace,
    ...
};

class ParseError : public std::exception
{
public:
    ParseError(
        ParseErrorKind kind,
        std::uint32_t offset,
        ParseExpectation expectation = ParseExpectation::Unspecified,
        ParseExpectedSpelling expectedSpelling =
            ParseExpectedSpelling::Unspecified);

    const char* what() const noexcept override;
    ParseErrorKind kind() const noexcept;
    std::uint32_t offset() const noexcept;
    ParseExpectation expectation() const noexcept;
    ParseExpectedSpelling expectedSpelling() const noexcept;

private:
    std::uint32_t offset_;
    ParseErrorKind kind_;
    ParseExpectation expectation_;
    ParseExpectedSpelling expectedSpelling_;
};

Lexer, parser, and source-loading exceptions store compact structured facts: an error kind, byte offset, and only the additional enum or byte required by that kind. Formatting is performed later by writeErrorMessage and the source diagnostic renderer. This keeps string construction out of parsing and, in particular, out of the sites that throw errors. It also tends to make the binary code for the hot parser paths more compact by keeping formatting machinery out of them, which can improve use of the CPU instruction caches. The structured representation also supports future localisation and allows the compiler to combine the error with a filename, line, byte column, source line, and caret.

Previous168 Query Optimisation