{ }                         { }
     /   \       {.lang name}      |
   lang   by          -->         name
    |      |                       |
   'k'  'wojtek'                  'k'

Table of Contents

  1. Introduction
  2. Syntax and Values
  3. Types as Finite Automata
  4. Partial Functions and Composition
  5. Typing, Filters, and Normalization
  6. Values in Memory
  7. The Partial Function ABI
  8. Operational Semantics and Execution
  9. Compiler Architecture
  10. From AST to Intermediate Representation
  11. LLVM Basics
  12. Code Generation
  13. Linking and Execution
  14. Canonical Serialization
  15. Optimization and Folding
  16. Toward a Universal Schema Registry

Appendices

Chapter 1 — Introduction

1.1 The purpose of this book

This book describes a small programming language called k. It is meant to show how data can be represented and transformed in a uniform, precise way.

1.2 Data as trees

All information in k is treated as a tree. A tree has:

Both JSON objects and XML documents are trees in this sense. Every k value is such a finite labeled tree.

1.3 Functions that may fail

In ordinary mathematics a function always returns a result. In k, a function may be undefined for some inputs. For example, asking for the field age in a record that has no age is undefined.

We call such mappings partial functions.

1.4 Simplicity over features

k avoids most language constructs: no variables and no control statements. It has only:

  1. types (which describe tree shapes), and
  2. partial functions (which transform one tree into another).

These two ingredients are sufficient and powerful enough to express structured computation in a concise and understandable way.

There is another concept in the language, called filters. Filters play a role in the process of reasoning about types of partial functions. Filters have been added to the syntax of the language as they allow explicit annotations of “polymorphic” expressions, i.e., expressions which make sense in different contexts. Filters are similar to type classes in other languages.

Chapter 2 — Syntax and Values

2.1 Language fragments

The k language has only one kind of program element: a definition. A program is a sequence of definitions of two kinds:

$ type_name = ...type_expression... ;
function_name = ...expression... ;

The definitions are followed in the file by the main expression; it represents the partial function defined by the program as a whole.

There is no syntax for values. Every syntactic form in an expression describes a function – possibly a constant function that always returns the same value.

2.2 Types

A type describes the possible tree shapes of values. Types are formed from two constructors:

  1. Product – written { T₁ l₁, T₂ l₂, … } represents records with fixed labeled fields.

  2. Union – written < T₁ l₁, T₂ l₂, … > represents a choice between labeled alternatives.

Both are finite and fully explicit. Every type denotes a finite tree automaton whose accepted trees are the possible values of that type.

2.3 Special and limiting cases

  1. Empty product {} has no fields. It represents the type that admits exactly one value, called unit. There is nothing exceptional about the type and its value; it is simply the degenerate case of a product with zero fields.

  2. Empty union <> has no variants. It represents a type with no possible values.

2.4 Projections

Dot notation, e.g.,

 . field_name

is used for extracting the value of a field from a record (product type value). Div notation, e.g.,

 / variant_name

is used for asserting a particular variant of a union and extracting its value. Product type { T₁ l₁, T₂ l₂, … , Tₙ lₙ } naturally defines n partial functions: .l₁, .l₂, … , .lₙ,
and union type < T₁ l₁, T₂ l₂, … , Tₙ lₙ > naturally defines n partial functions /l₁, /l₂, … , /lₙ. Those partial functions are called projections and they constitute the basis for the definition of all other partial functions in the k language.

2.5 Functions

Expressions combine partial functions using the following operators:

  1. Composition (f₁ f₂ …) — sequential application.
  2. Union < f₁, f₂, … > — try each in order, first defined wins.
  3. Product (parallel) { f₁ l₁, f₂ l₂, … } — apply all to the same input, succeed only if all succeed.
  4. Variant construction | tag — lift the input as a variant tag of a union type.

Parentheses around a composition may be omitted except for the empty composition () — the identity function. Empty product, { }, defines a constant function (ignoring its input) returning unit.

It is important to notice that after the three markers: dot (.), div (/), or pipe (|), there must be a constant label literal. For that reason, it is possible and advised not to leave any blanks after the marker, e.g.:

  .field /'a-tag' |"strange and long tag name ✅"

2.6 Example

$ bool = < {} true, {} false >;
true  = {} |true $ bool;
false = {} |false $ bool;
neg = $ bool < /true false, /false true >;

This defines a “two-variant” union type and three functions: two constants and one transformation exchanging the variants.

2.7 Summary

Chapter 3 — Types as Finite Automata

3.1 Motivation

A type in k describes a set of finite labeled trees, which can be recognized by a finite tree automaton (FTA). Equivalently, a type definition can be seen as a Context-Free Grammar (CFG), where the values of the type are the derivation trees of the grammar.

For example, the recursive type definition of a list:

$ bool = < {} true, {} false >;
$ list = < {} nil, { bool head, list tail } cons >;

corresponds to the following 4-rule grammar:

1: <bool> ::= {} |true
2: <bool> ::= {} |false
3: <list> ::= {} |nil
4: <list> ::= { <bool> head, <list> tail } |cons

A value of type list is a derivation tree of this grammar. For instance, a list containing a single boolean value true can be represented by the following derivation:

<list>
  -- (rule 4) --> { <bool> head, <list> tail } |cons
                     |            |
                     |            -- (rule 3) --> {} |nil
                     |
                     -- (rule 1) --> {} |true

This derivation tree corresponds to the value generated by constant function: { {} |true head, {} |nil tail } |cons.

Representing types as automata (or CFGs) provides each type with a well-defined structure, independent of the names used in the source code. This allows for canonical normal forms and for comparing types for equality by structure alone.

3.2 States and Transitions

Each type definition introduces one or more states in the automaton. A union or a product definition corresponds to a state, and the variants or fields correspond to transitions to other states.

For example, consider the $bool type:

$ bool = < {} true, {} false >;

This definition translates to an automaton with two states:

From the root state C0, there are two transitions:

C0 is the root state of the type, and C1 is a leaf state, representing an empty value.

3.3 Canonical Form

Different type expressions can describe the same automaton. For example:

$ bool = < {} false, {} true >;
$ pair = { bool x, bool y };
$ pair2 = { < {} true, {} false > x, bool y };

The types pair and pair2 are structurally equivalent because $bool is defined as < {} true, {} false >, making the definition of x in pair2 identical to the standalone $bool type used in pair. Canonicalization is the process of removing these superficial differences by erasing local names and renumbering states to produce a single stable representation for each unique type structure.

The canonical form is generated by traversing the type’s graph structure starting from its root state. The process ensures a unique representation by following a consistent ordering:

  1. Start at the Root: Assign the number C0 to the root state of the type.
  2. Explore Neighbors: Visit all states reachable from C0. Sort the transitions alphabetically by their labels (field or variant names) and assign consecutive numbers (C1, C2, …) to the destination states in that order.
  3. Iterate: Move to the next state in the numbered sequence (C1, then C2, etc.) and repeat the process for any of its neighbors that have not yet been numbered.
  4. Complete: Continue until all reachable states have been assigned a unique number.

This traversal produces a unique and deterministic numbering for any finite directed graph, ensuring that any two structurally identical types will have the exact same canonical representation.

3.4 Examples

For a type representing binary natural numbers:

$ bnat = < bnat 0, bnat 1, {} _ >;

the canonical form is:

$C0 = < C0 "0", C0 "1", C1 "_" >;
$C1 = {};

The automaton has two states. C0 is a recursive state that recognizes sequences of “0”s and “1”s, while C1 is the terminal state, marked by the “_” transition.

3.5 Normalization Process

When compiling a program, the following steps are taken to normalize types:

  1. Collect: Gather all type definitions from the program.
  2. Expand: Recursively replace all named types with their underlying definitions until only products and unions remain.
  3. Deduplicate: Eliminate duplicate type structures by comparing them structurally.
  4. Canonicalize: Assign stable state numbers to the unique types to produce their canonical text representation.

This process is deterministic, ensuring that the same type structure always produces the exact same canonical form.

3.6 Hash-Based Naming

To create a globally unique and stable identifier for each type, the compiler computes a hash of its canonical representation. This hash becomes the official, unambiguous name of the type.

For example:

Canonical Form: $C0=<C0"0",C0"1",C1"_">;$C1={}
      ↓
     Hash
      ↓
Identifier: @BsAqRMv

Program objects can then refer to types by their hash-based identifiers (prefixed with @) without ambiguity.

3.7 Interpretation

The canonical representation of a type can be interpreted as:

Every value of a given type is a finite tree that is accepted by this automaton.

3.8 Summary

Chapter 4 — Partial Functions and Composition

4.1 Partial functions

A partial function is a mapping that may be undefined for some inputs. In k, every expression denotes such a function. If a function is undefined for a given input, the evaluation process halts at that point, producing no result.

There is no notion of error or exception. Undefined means simply “no output”.

4.2 Composition

Composition combines two or more partial functions sequentially. If f and g are functions, (f g) means “apply f, then apply g to the result”.

A composition (f g) is defined on a value x if and only if:

Otherwise, the composition is undefined.

Composition is associative:

(f (g h))  ≡  ((f g) h)

Therefore, parentheses are unnecessary, except for the special case of the empty composition, written (), which is the identity function:

() x  =  x () = x

4.3 Product composition

Product composition creates a function that applies several subfunctions in parallel to the same input and gathers their results into a product value.

Syntax:

{ f₁ l₁, f₂ l₂, …, fₙ lₙ }

This expression is defined on an input value if all component functions are defined on that input. Its result is a product with fields labeled l₁ … lₙ, each containing the result of the corresponding function.

4.4 Union composition

Union composition represents concurrent evaluation with fallback:

< f₁, f₂, …, fₙ >

The result is defined for an input x if at least one subfunction is defined. Evaluation proceeds left to right; the first defined result is used. If none are defined, the result is undefined.

Example:

< /x, /y >

extracts variant x if present; otherwise y if present.

4.5 Constants

A constant function is one that always returns the same value, regardless of its input. Since k lacks a direct syntax for literal values, constants are created using functions that produce them.

For example, we can define functions that return true and false:

$ bool = < {} true, {} false >;
true_bool  =  {} |true $bool ;
false_bool =  {} |false $bool ;

Here, true_bool and false_bool are constant functions. They are also total functions, meaning they are defined for all inputs. Each function ignores its input and produces a fixed boolean value.

4.6 Projection and Variant Value constructor

Projection selects a field or a variant from a product or union. It is written with a leading dot . or a leading slash /, respectively:

.x     // Selects field 'x' from a product: { T x, ... }
/x     // Extracts the value from a union variant 'x': < T x, ... >

If the input is a product, .x returns the value of field x. If the input is a union, /x returns the value of variant x. In all other cases, the projection is undefined.

Variant value constructors for a given union type T = <T₁ tag₁, T₂ tag₂, … > are written as |tag₁, |tag₂, ….

|tag₁    // lift a value of type T₁ into a value of type T

Projections and variant constructors are the most basic partial functions.

4.7 Derived combinations

Complex functions are built by nesting compositions. For example:

{ .x field1, .y |tag field2 }

4.8 Identity and emptiness

The empty composition () is the identity function. The empty union <> is the always-undefined function. The empty product {} is the constant function returning the unit value.

4.9 Summary

Chapter 5 — Typing, Filters, and Normalization

5.1 Types as functions

A type expression in k can appear wherever a function is expected. When used this way, it is prefixed by $. It then behaves as a partial identity function that is defined only for values of that type. For example, $ bool is a partial identity: it returns its argument unchanged when the argument is of type bool, and it is undefined otherwise.

This convention eliminates any special syntax for annotating sub-expressions with types. An expression may be restricted to a type simply by composing it with the corresponding type expression.

5.2 Filters

A filter is a syntactic form that denotes a class of types — a set of types that share a common structure.

Filter expressions are introduced by ? and can be:

Filters may contain ... to indicate that additional fields or tags are allowed: ? { Filter1 field1, ... } matches any product with at least field1.

The filter ? (...) matches any type. The filter ? {...} matches any product type. The filter ? <...> matches any union type.

5.3 Examples of filters

A filter constrains where a partial function is defined; it does not affect the operational behavior of the function once defined.

5.4 Recursive filters

Filters may be recursive. They can describe families of recursive types by defining a metavariable in terms of a filter that references it.

Example (list definition):

?< {} nil, {X car, Y cdr} cons > = Y

This filter states that Y is a union type with two variants: nil and cons.

This recursive structure defines a linked list where each element has a car (the value) and a cdr (the rest of the list). It thus denotes lists of elements of type X.

5.5 Type variables and scope

A type variable (an identifier, typically starting with an uppercase letter) introduced in a filter is visible within the enclosing function definition. For example:

car = ?< {} nil, {X car, Y cdr} cons > = Y /cons .car ?X;

Here:

5.6 Type inference and normalization

Every k program can be analyzed to assign an input and an output filter to every sub-expression. This process is called type inference abd normalization.

Type inference and normalization proceeds as follows:

  1. Build a graph of all type references appearing explicitly and implicitly in the program.
  2. Annotate each expression node with a pair of (input filter, output filter).
  3. Replace filters that match a single, concrete type with that type expression, adding any newly-discovered types to the graph.
  4. Repeat until a fixed point is reached and no more changes occur.
  5. Compute canonical forms for all newly introduced types.

5.7 Summary

Chapter 6 — Values in Memory and Canonical Serialization

6.1 Unified value representation

Every k value exists in one of three forms during execution:

  1. Serialized form — a canonical bit sequence that can be stored, transmitted, or passed between processes.
  2. Lazy (or hybrid) form — a partially deserialized structure that keeps most data in its serialized form until access is needed.
  3. Materialized form — a fully deserialized tree of nodes in memory.

This unified approach enables programs to operate on serialized inputs without unnecessary deserialization, optimizing performance for identity operations and partial data access patterns.

6.2 The KValue abstraction

All values are represented by a single abstraction:

struct KValue {
    enum ValueForm {
        SERIALIZED,     // pure bitstream + type info
        LAZY,          // hybrid: some nodes materialized, others serialized
        MATERIALIZED,  // traditional tree structure
        EXTERNAL       // built-in/foreign type with custom handlers
    } form;
    
    union {
        struct {
            uint8_t* bits;          // canonical bitstream
            int      type_id;       // identifies canonical type
        } serialized;
        
        struct {
            struct KNode* root;     // root of materialized or partially materialized tree
        } materialized;
        
        struct {
            void*    data;          // opaque external data
            int      type_id;       // external type identifier
            ExternalOps* ops;       // function pointers for operations
        } external;
    };
};

6.2.1 Self-delimiting streams

The canonical encoding is self-delimiting, meaning each value can be parsed without knowing its length in advance:

This enables streaming evaluation where programs can process data incrementally without buffering entire inputs.

6.3 Lazy node structure

Nodes in lazy values can be in different states of materialization:

struct KNode {
    int  state;        // canonical type state (C0, C1,…)
    int  tag;          // variant index, −1 for product
    int  arity;        // number of children
    
    enum NodeState {
        SERIALIZED_CHILD,    // child exists as bitstream only
        MATERIALIZED_CHILD,  // child is fully materialized
        EXTERNAL_CHILD       // child is external/built-in type
    };
    
    union KChild {
        struct {
            enum NodeState state;       // which kind of child this is
            union {
                struct KNode*     node;       // materialized child
                struct {
                    uint8_t*      bits;       // serialized child data
                    int           bit_offset; // position within parent's bitstream
                } serialized;
                struct KValue*    external;   // external child
            };
        };
    } child[];
};

6.4 Canonical serialization format

The serialized form uses a deterministic canonical encoding that produces identical bit sequences for structurally identical values, extended to support lazy evaluation:

6.4.0 Canonical encoding principles

The encoding is based on the canonical finite automaton representation of types (Chapter 3):

Fixed-length union codes

For each union state with m variants, we use k = ceil(log2(m)) bits to encode the variant selection:

Variants Bits needed Example codes
2 1 0, 1
3 2 00, 01, 10
4 2 00, 01, 10, 11
5-8 3 000 through 111

Encoding by node type

Each node in the value tree is encoded based on its automaton state:

Example: Natural numbers

For type bnat, intuitively binary natural numbers defined by $bnat = < bnat 0, bnat 1, {} _ >, we get

--C bnat
$ @BsAqRMv = < @BsAqRMv 0, @BsAqRMv 1, @KL _ >; -- $C0=<C0"0",C0"1",C1"_"> $C1={};

The corresponding Context-Free grammar is:

// 3 rules for C0, so we need 2 bits to encode the variant choice:
   C0 ->  C0 "|0"     //       encoded by '00'
   C0 ->  C0 "|1"     //       encoded by '01'
   C0 ->  C1 "|_"     //       encoded by '10'
// 1 rule for C1 so we need zero bits:
   C1 ->  '{}';       //       encoded by ''

The value {}|_|0|1 or in JSON-like notation {1:{0:{_:{}}}} (binary 10₂ = decimal 2) encodes as:

01 00 10

This represents the left-most derivation of {}|_|0|1 from C0.

Prefix-free property

The encoding is prefix-free: no valid encoding is a prefix of another. This enables:

6.4.1 DAG compression for repeated subtrees

The canonical serialization can be compressed using DAG (Directed Acyclic Graph) representation to eliminate duplicate subtrees:

Subtree identification

Each unique subtree is assigned a node ID based on its canonical hash:

hash(node) = hash(state, tag, arity, hash(child_0), hash(child_1), ...)

Identical subtrees (same structure and content) get the same hash and share the same node ID.

Two-pass encoding

Pass 1: Collection
Pass 2: Emission

Back-reference encoding

| Reference Bit (1) | Node ID (variable length) |

Example: Shared subtrees

Consider a binary tree with repeated leaf patterns:

$tree = < { tree left, tree right } branch, int leaf >;

Value: A tree corresponding to the structure: branch( leaf(42), branch( leaf(42), leaf(17) ) ):

Without DAG: Each leaf (42) is encoded separately With DAG: The (42) subtree is encoded once, then referenced

Encoding sequence:

Node Table:
  N0: 42    (appears 2 times)
  N1: 17    (appears 1 time)

Bitstream:
  00           // branch variant
  0 <N0>       // first occurrence of value: 42
  00           // branch variant  
  1 N0         // back-reference to value: 42
  0 <N1>       // {value: 17}

6.4.2 Stream structure

| Header (8 bytes) | Node Count (4 bytes) | Node Table | Bitstream |

Node table format

When DAG compression is used (Node Count > 0):

For each shared node:
| Node ID (4 bytes) | Offset (4 bytes) | Size in bits (4 bytes) |

This allows the decoder to:

  1. Random access: Jump directly to any shared subtree definition
  2. Lazy loading: Resolve back-references only when needed
  3. Validation: Verify subtree boundaries during parsing

Compression algorithms

Greedy sharing: Share any subtree that appears more than once

Size-based sharing: Only share subtrees above a minimum size threshold

Frequency-weighted sharing: Prioritize subtrees by size × frequency

Lazy back-reference resolution

Back-references integrate seamlessly with lazy evaluation:

DecoratedPtr resolve_reference(DecoratedPtr backref) {
    node_id = read_variable_int(backref.bits, backref.bit_offset);
    
    // Look up in node table
    node_entry = node_table[node_id];
    
    return (DecoratedPtr) {
        .bits = backref.bits,
        .bit_offset = node_entry.offset,
        .type_state = node_entry.type_state,
        .ref_count = 1
    };
}

The decorated pointer model naturally handles back-references as lightweight pointer redirections.

Memory vs. compression trade-offs

Strategy Memory usage Compression ratio Decode speed
No DAG Low 1.0× (baseline) Fastest
Greedy DAG Medium 2-10× Fast
Optimal DAG High 5-50× Medium

For streaming applications: Prefer greedy DAG with small node tables For archival storage: Use optimal DAG compression For real-time processing: Skip DAG compression entirely

Compression example: Repeated data structures

Consider a list of similar records:

$record = { string name, int age, string department };
$company = < { record head, company tail } cons, {} nil >;

Value representing 1000 employees where 80% work in “Engineering”:

Without DAG: Each "Engineering" string encoded separately
- 1000 records × 30 bytes/record = 30KB

With DAG: "Engineering" string shared via back-references  
- 1 × "Engineering" (11 bytes) + 800 × back-reference (3 bytes) = 2.4KB
- Compression ratio: ~12.5×

The DAG representation transforms the tree into a more efficient directed acyclic graph:

Tree:     Record1 → "Engineering"
          Record2 → "Engineering"  
          Record3 → "Engineering"
          ...

DAG:      Record1 ↘
          Record2 → Shared("Engineering")
          Record3 ↗
          ...

6.4.3 Hardware-optimized encoding

While bit-level precision is theoretically optimal, modern hardware operates on byte-aligned data using word-sized registers. A practical encoding must balance compression with decode performance.

Register-friendly union encoding

Instead of ceil(log2(m)) bits, use byte-aligned codes optimized for common union sizes:

Union variants Theoretical bits Hardware-optimized
2-3 variants 1-2 bits 1 byte (8 bits)
4-15 variants 2-4 bits 1 byte (8 bits)
16-255 variants 4-8 bits 1 byte (8 bits)
256+ variants 8+ bits 2+ bytes (LEB128)

Rationale: Single-byte discriminators enable efficient decoding with simple memory loads and bit masking.

SIMD-friendly data layout

Modern CPUs can process multiple bytes simultaneously using SIMD instructions. Structure the encoding to leverage this:

// Bad: bit-packed discriminators
struct BitPacked {
    uint64_t discriminators;  // 8 × 8-bit = 64 discriminators packed
    // Requires expensive bit extraction
};

// Good: byte-aligned discriminators  
struct ByteAligned {
    uint8_t discriminators[8];  // 8 discriminators, SIMD-friendly
    // Can be processed with single AVX2 instruction
};

Cache-line aware field ordering

Arrange product fields to minimize cache misses:

// Product field layout optimization
struct ProductLayout {
    uint8_t  discriminators[N];     // All discriminators together (hot data)
    uint8_t  padding[64 - N % 64];  // Align to cache line boundary
    uint8_t  field_data[];          // Field data follows (cold data)
};

Fields are ordered by access frequency rather than alphabetical order:

Word-aligned pointer arithmetic

Replace bit-level navigation with word-aligned operations:

// Bit-level navigation (slow)
DecoratedPtr navigate_bitwise(DecoratedPtr ptr, int field_index) {
    size_t bit_offset = ptr.bit_offset;
    for (int i = 0; i < field_index; i++) {
        bit_offset += extract_field_bit_size(ptr.bits, bit_offset);  // Expensive!
    }
    return make_ptr(ptr.bits, bit_offset);
}

// Word-aligned navigation (fast)
DecoratedPtr navigate_wordwise(DecoratedPtr ptr, int field_index) {
    uint8_t* byte_ptr = ptr.bits + (ptr.bit_offset >> 3);  // Convert to byte offset
    
    // Read field offset table (precomputed during encoding)
    uint32_t* offset_table = (uint32_t*)byte_ptr;
    uint32_t field_offset = offset_table[field_index];     // Single memory load
    
    return make_ptr(ptr.bits, field_offset << 3);         // Convert back to bits
}

CPU instruction optimization

Branch prediction friendly encoding:

// Bad: unpredictable branching
uint8_t discriminator = *byte_ptr++;
switch (discriminator) {
    case 0: handle_variant_0(); break;
    case 1: handle_variant_1(); break;
    case 2: handle_variant_2(); break;
    // ... many cases cause branch misprediction
}

// Good: function table dispatch
typedef void (*VariantHandler)(uint8_t* data);
static VariantHandler variant_handlers[256] = {
    handle_variant_0, handle_variant_1, handle_variant_2, /* ... */
};

uint8_t discriminator = *byte_ptr++;
variant_handlers[discriminator](byte_ptr);  // Single indirect call

Prefetch-aware access patterns:

// Sequential prefetching for product fields
void prefetch_product_fields(DecoratedPtr ptr, int num_fields) {
    uint32_t* offset_table = (uint32_t*)(ptr.bits + (ptr.bit_offset >> 3));
    
    // Prefetch offset table into L1 cache
    __builtin_prefetch(offset_table, 0, 3);  // Read, high temporal locality
    
    // Prefetch first few fields
    for (int i = 0; i < min(num_fields, 4); i++) {
        uint8_t* field_ptr = ptr.bits + offset_table[i];
        __builtin_prefetch(field_ptr, 0, 2);  // Read, medium temporal locality
    }
}

Memory bandwidth optimization

Streaming-friendly encoding:

// Structure data for optimal memory bandwidth
struct StreamLayout {
    struct {
        uint32_t total_size;        // 4 bytes
        uint16_t num_fields;        // 2 bytes  
        uint16_t flags;             // 2 bytes (padding + metadata)
    } header;                       // 8 bytes total (fits in single cache line)
    
    uint32_t field_offsets[];       // 4N bytes (word-aligned)
    uint8_t  field_data[];          // Variable length data
};

Memory access patterns:

Hardware-specific optimizations

x86-64 optimizations:

// Exploit x86-64 addressing modes
DecoratedPtr navigate_x86(DecoratedPtr ptr, int field_index) {
    uint32_t* offset_table = (uint32_t*)(ptr.bits + (ptr.bit_offset >> 3));
    
    // Single instruction: LEA + memory operand
    uint8_t* field_ptr = ptr.bits + offset_table[field_index];
    
    return make_ptr_from_bytes(field_ptr);
}

// Utilize SIMD for bulk discriminator reading
void decode_discriminators_avx2(uint8_t* input, uint8_t* output, size_t count) {
    __m256i* input_vec = (__m256i*)input;
    __m256i* output_vec = (__m256i*)output;
    
    for (size_t i = 0; i < count / 32; i++) {
        __m256i data = _mm256_load_si256(&input_vec[i]);
        
        // Process 32 discriminators in parallel
        __m256i decoded = _mm256_and_si256(data, _mm256_set1_epi8(0x0F));
        
        _mm256_store_si256(&output_vec[i], decoded);
    }
}

ARM64 optimizations:

// Exploit ARM64 load-with-offset instructions
DecoratedPtr navigate_arm64(DecoratedPtr ptr, int field_index) {
    uint32_t* offset_table = (uint32_t*)(ptr.bits + (ptr.bit_offset >> 3));
    
    // ARM64: single LDR instruction with register offset
    uint32_t offset = offset_table[field_index];
    uint8_t* field_ptr = ptr.bits + offset;
    
    return make_ptr_from_bytes(field_ptr);
}

Performance analysis: Hardware vs. theoretical encoding

Decoding performance comparison (cycles per field access):

Encoding strategy Field access cost Cache behavior SIMD support
Bit-packed optimal 50-100 cycles Poor (bit manipulation) No
Byte-aligned 5-15 cycles Good (word loads) Yes
Word-aligned + offset table 2-8 cycles Excellent (prefetchable) Yes

Space vs. time trade-offs:

Bit-packed:     100% space efficiency, 10× decode overhead
Byte-aligned:   90% space efficiency,   2× decode overhead  
Word-aligned:   80% space efficiency,   1× decode overhead (baseline)

Real-world measurements (modern x86-64, 3.2GHz):

// Benchmark: Navigate to field in 1000-field product
Bit-manipulation:     2,400 ns  (7,680 cycles)
Byte-aligned:           480 ns  (1,536 cycles)  
Word-aligned table:     160 ns    (512 cycles)

The offset table approach provides the best practical performance despite modest space overhead.

Hybrid approach balancing theory and practice:

  1. Small products (≤8 fields): Byte-aligned, no offset table
  2. Medium products (9-64 fields): Word-aligned with offset table
  3. Large products (65+ fields): Hierarchical offset tables + prefetching
  4. Unions: Single byte discriminator (sufficient for 99.9% of real types)

Encoding format:

struct OptimalEncoding {
    uint8_t  type_tag;              // 1 byte: product/union/external marker
    uint8_t  arity;                 // 1 byte: number of children (0-255)
    uint16_t flags;                 // 2 bytes: compression flags, alignment info
    uint32_t total_size;            // 4 bytes: total size for skipping
    
    // For products with >8 fields:
    uint32_t field_offsets[arity];  // 4×N bytes: random access table
    
    // Payload data follows
    uint8_t  data[];
};

Benefits:

6.4.4 External type integration

| External Marker (2 bits) | Type ID | External Data Length | External Data |

This allows built-in types (strings, floats, etc.) to be efficiently serialized within k values while maintaining the canonical property.

6.5 Demand-driven deserialization

Operations on values trigger selective deserialization:

6.5.1 Access patterns

6.5.2 Lazy evaluation strategy

function access_field(value: KValue, field_path: String[]): KValue {
    if (value.form == SERIALIZED) {
        // Partially deserialize to reach the field
        root = deserialize_to_depth(value, field_path.length);
        value = make_lazy(root, value.serialized.bits);
    }
    
    if (value.form == LAZY) {
        node = navigate_path(value.lazy.root, field_path);
        if (node.child[field_idx].state == SERIALIZED_CHILD) {
            // Deserialize this child on demand
            child_value = deserialize_child(node, field_idx);
            node.child[field_idx].state = MATERIALIZED_CHILD;
            node.child[field_idx].node = child_value;
        }
        return &node.child[field_idx];
    }
    
    // Traditional navigation for fully materialized values
    return navigate_materialized(value, field_path);
}

6.6 External type system

Built-in and foreign types integrate through a plugin interface:

6.6.1 External operations

struct ExternalOps {
    KValue* (*serialize)(void* data);
    void*   (*deserialize)(KValue* serialized);
    KValue* (*apply_function)(void* data, const char* func_name, KValue* args);
    bool    (*equals)(void* a, void* b);
    uint64_t (*hash)(void* data);
    void    (*destroy)(void* data);
};

6.6.2 Built-in type examples

6.6.3 Type registration

void register_external_type(int type_id, const char* name, ExternalOps* ops) {
    external_types[type_id] = {
        .name = name,
        .ops = ops,
        .canonical_hash = compute_type_hash(name, ops->signature)
    };
}

6.7 Memory management and performance

6.7.1 Arena allocation

All materialized nodes use arena allocation for fast allocation and bulk deallocation:

struct Arena {
    uint8_t* memory;
    size_t   capacity;
    size_t   used;
    Arena*   next;      // linked list of arena blocks
};

6.7.2 Sharing and deduplication

6.7.3 Optimization opportunities

6.8 Example: Lazy evaluation in practice

Consider processing a large JSON-like structure where we only need one field:

$record = { string name, list data, metadata meta };
$list = < {nat value, list next} cons, {} nil >;
$metadata = { timestamp created, string author };

For the input program \x.x.name (extract name field):

  1. Input arrives as serialized bitstream (e.g., from network/disk)
  2. Lazy parsing deserializes only the discriminator of the root product
  3. Field access deserializes path to name field, leaving data and meta serialized
  4. Output the extracted string value (possibly in external string format)

The entire data list and metadata remain as untouched bitstreams, providing massive performance benefits for large, sparsely accessed data structures.

6.8.1 Serialized representation

The same value can exist in different forms simultaneously:

// Original input: fully serialized
KValue input = {
    .form = SERIALIZED,
    .serialized = {
        .bits = bitstream_buffer,
        .type_hash = hash("record")
    }
};

// After partial access: hybrid lazy
KValue hybrid = {
    .form = LAZY,
    .lazy.root = {
        .state = 0, .tag = -1, .arity = 3,
        .child = {
            [0] = { .state = MATERIALIZED_CHILD, .node = materialized_string_node },      // name: materialized
            [1] = { .state = SERIALIZED_CHILD, .serialized = {bits+offset, 64} },        // data: still serialized  
            [2] = { .state = SERIALIZED_CHILD, .serialized = {bits+offset, 1088} }       // meta: still serialized
        }
    }
};

6.8.2 External type integration example

// Built-in string type
KValue string_value = {
    .form = EXTERNAL,
    .external = {
        .data = utf8_string_data,
        .type_id = BUILTIN_STRING,
        .ops = &string_operations
    }
};

// The string_operations provide:
ExternalOps string_operations = {
    .serialize = string_to_canonical_bits,
    .deserialize = canonical_bits_to_string,
    .apply_function = string_builtin_functions,  // length, concat, etc.
    .equals = utf8_string_compare,
    .hash = utf8_string_hash,
    .destroy = free_string_data
};

6.9 Summary

This unified representation provides several key advantages:

The design supports the full spectrum from zero-copy identity operations to fully materialized tree traversal, allowing the runtime to automatically choose the most efficient representation for each use case.

6.9.1 Key design principles

6.10 Execution model with decorated pointers

The formal execution model is based on decorated pointers, which represent values during execution:

6.10.1 Decorated pointers

Every value during execution is represented by a decorated pointer:

struct DecoratedPtr {
    uint8_t*     bits;          // pointer into serialized input heap
    size_t       bit_offset;    // bit position within the stream
    TypeState    type_state;    // canonical automaton state (C0, C1, ...)
    int          ref_count;     // for sharing and caching
    struct {
        bool     is_cached;     // memoization flag
        uint64_t content_hash;  // for cache lookup
    } cache;
};

The key insight: decorated pointers are lightweight and can be computed without memory allocation.

6.10.2 Program execution pipeline

A compiled k program is a composition of operations: projection ∘ product ∘ union ∘ builtin_call ∘ ...

Each operation transforms a decorated pointer:

DecoratedPtr → DecoratedPtr

Projection operation

For field access .field_name:

DecoratedPtr project_field_optimized(DecoratedPtr input, int field_index) {
    // Hardware-optimized field navigation
    uint8_t* byte_ptr = input.bits + (input.bit_offset >> 3);
    
    // Read encoding header
    struct OptimalEncoding* header = (struct OptimalEncoding*)byte_ptr;
    
    if (header->arity <= 8) {
        // Small product: sequential scan (cache-friendly)
        uint8_t* field_ptr = byte_ptr + sizeof(struct OptimalEncoding);
        for (int i = 0; i < field_index; i++) {
            uint32_t field_size = *(uint32_t*)field_ptr;  // First 4 bytes = size
            field_ptr += field_size;
        }
        return make_ptr_from_bytes(field_ptr);
    } else {
        // Large product: offset table lookup (O(1) access)
        uint32_t field_offset = header->field_offsets[field_index];
        return make_ptr_from_bytes(byte_ptr + field_offset);
    }
}

Key property: Hardware-optimized navigation using word-aligned loads and offset tables.

Union operation

For pattern matching case { tag1 → ..., tag2 → ... }:

DecoratedPtr match_union_optimized(DecoratedPtr input, int expected_tag) {
    // Read single-byte discriminator (hardware-friendly)
    uint8_t* byte_ptr = input.bits + (input.bit_offset >> 3);
    struct OptimalEncoding* header = (struct OptimalEncoding*)byte_ptr;
    
    uint8_t actual_tag = header->data[0];  // First byte of data = discriminator
    
    if (actual_tag != expected_tag) {
        return UNDEFINED_PTR;  // Pattern match failure
    }
    
    // Skip past header + discriminator
    uint8_t* child_ptr = byte_ptr + sizeof(struct OptimalEncoding) + 1;
    
    return make_ptr_from_bytes(child_ptr);
}

Product operation

For product construction { field1, field2, ... }:

DecoratedPtr construct_product(DecoratedPtr* field_ptrs, int arity) {
    // This is the primary point where memory allocation is required.
    ProductNode* result = allocate_product_node(arity);
    
    // Evaluate each field (possibly in parallel)
    for (int i = 0; i < arity; i++) {
        result->fields[i] = evaluate_expression(field_ptrs[i]);
    }
    
    return make_materialized_ptr(result);
}

Built-in call operation

For external functions string_length, add_int, etc.:

DecoratedPtr builtin_call(DecoratedPtr input, BuiltinFunc func) {
    // Force materialization of the input
    ExternalValue* materialized = force_external(input);
    
    // Delegate to external implementation
    ExternalValue* result = func->call(materialized);
    
    return make_external_ptr(result);
}

6.10.3 Execution strategy

  1. Input setup: Place serialized input in heap, create root decorated pointer
  2. Lazy evaluation: Transform decorated pointers without allocation when possible
  3. Forced materialization: Allocate memory only when constructing products or calling built-ins
  4. Reference counting: Share decorated pointers for common subexpressions
  5. Output serialization: Convert final decorated pointer back to canonical bits

6.10.4 Example execution trace

For program \x.(x.data.head.value, x.name) on input { name: "alice", data: [42, 17] }:

Step 1: input_ptr = {bits: heap_start, offset: 0, state: C0_record}

Step 2: data_ptr = project_field(input_ptr, 1)  // .data
        = {bits: heap_start, offset: 120, state: C0_list}

Step 3: head_ptr = match_union(data_ptr, CONS_TAG)  // pattern match
        = {bits: heap_start, offset: 122, state: C0_cons}

Step 4: value_ptr = project_field(head_ptr, 0)  // .value  
        = {bits: heap_start, offset: 122, state: C0_int}

Step 5: name_ptr = project_field(input_ptr, 0)  // .name
        = {bits: heap_start, offset: 8, state: C0_string}

Step 6: result_ptr = construct_product([value_ptr, name_ptr])
        // Note: memory allocation for the result tuple occurs here.

6.10.5 Optimization opportunities

This model provides optimal performance for sparse data access while maintaining the mathematical precision of k’s type system.

6.11 Implementation considerations

6.11.1 Prefix-free code requirements

The execution model depends critically on prefix-free codes in the serialization:

This enables the skip_field() function to advance pointers without full deserialization.

6.11.2 Reference counting and caching

Decorated pointers should be reference-counted for several reasons:

Benefits:

6.11.3 Parallel evaluation

Product construction offers natural parallelization:

DecoratedPtr construct_product_parallel(DecoratedPtr* field_ptrs, int arity) {
    ProductNode* result = allocate_product_node(arity);
    
    #pragma omp parallel for
    for (int i = 0; i < arity; i++) {
        result->fields[i] = evaluate_expression(field_ptrs[i]);
    }
    
    return make_materialized_ptr(result);
}

Each field evaluation is independent and can run on separate threads.

6.11.4 Memory layout optimization

The input heap should be designed for efficient navigation:

struct InputHeap {
    uint8_t*  serialized_data;     // the original bitstream
    size_t    total_bits;          // total size
    
    // Optional: precomputed navigation table for large inputs
    struct {
        size_t*   field_offsets;   // byte offsets for major fields
        int       table_size;      // number of cached offsets
    } navigation_cache;
};

For very large inputs, precomputing field offsets can eliminate repeated prefix-free parsing.

6.12 Final summary

This unified design achieves several important goals:

  1. Zero-copy operations — Identity and projection work directly on serialized data
  2. Demand-driven materialization — Memory allocation only when necessary
  3. External type integration — Built-ins fit seamlessly into the execution model
  4. Parallel execution — Natural parallelization opportunities
  5. Streaming capability — Process large inputs with bounded memory

The decorated pointer model provides a clean abstraction that bridges the gap between the mathematical elegance of k’s type system and the performance requirements of real-world data processing.

Key insight: By treating serialized data as the primary representation and materialized structures as secondary optimization, we invert the traditional approach and achieve much better performance for sparse data access patterns.

6.12.1 Hardware-optimized encoding summary

The final encoding strategy balances theoretical optimality with practical hardware constraints:

Trade-offs achieved:

Performance characteristics:

Operation               Hardware-optimized    Bit-level optimal
Field access           2-8 cycles           50-100 cycles
Union matching         1-3 cycles           20-40 cycles  
Memory bandwidth       95% theoretical      60% theoretical
Cache miss ratio       <5%                  >25%

Recommended for:

The hardware-optimized approach provides the best practical balance for real-world k implementations.

Chapter 7 — The Partial Function ABI

7.1 Purpose

The application binary interface (ABI) defines how partial functions in k are represented and invoked at runtime. Its goal is to make all functions - whether user-defined or compiled - compatible with the same calling convention and data layout.

Every compiled k function receives a single argument (a value tree) and may either produce a result or remain undefined. The ABI provides a uniform way to express both outcomes.

7.2 Function result representation

The result of every function call is a pair of fields:

struct KOpt {
    bool ok;     // 1 if function is defined for the given input
    struct KNode* val;  // valid only if ok == true
};

If ok == 1, the function succeeded and val points to the root node of the resulting value. If ok == 0, the function is undefined for the input, and val is meaningless.

This structure carries both the success flag and the value pointer, allowing partiality to be expressed directly in generated code.

7.3 Function parameter representation

Each function takes exactly one parameter:

struct KNode* input;

The parameter points to the root of the input value. Since all values are immutable, the function must not modify this structure.

7.4 Calling convention

Every k function compiled to machine code follows this C-style signature:

struct KOpt k_function(struct KNode* input);

The return value indicates success or failure. The convention is uniform for all functions, regardless of the specific types involved.

7.5 Core runtime operations

The runtime provides a small set of primitive functions implementing the fundamental operations of k:

Operation Purpose Result
k_project(input, label_id) projection .label defined if the field or variant label_id exists
k_make_product(state, children[], n) construct a product node always defined
k_make_union(state, tag, child) construct a union node always defined
k_fail() represent undefined result returns { ok = 0 }
k_unit() return the constant unit node returns { ok = 1, val = &unit_node }

All user-defined functions can be compiled entirely in terms of these operations.

7.6 Metadata tables

To interpret or construct nodes correctly, the runtime holds constant tables derived from canonical type definitions:

These tables are read-only and known at compile time for each canonical type.

7.7 Example: projection

To implement the projection .x:

struct KOpt k_project_x(struct KNode* input) {
    int state = input->state;
    int kind  = state_kind[state];

    if (kind == PRODUCT) {
        int idx = field_index[state]["x"];
        if (idx < 0 || idx >= input->arity)
            return (struct KOpt){0, NULL};
        return (struct KOpt){1, input->child[idx]};
    }

    if (kind == UNION) {
        int tag  = variant_index[state]["x"];
        if (tag < 0 || input->tag != tag)
            return (struct KOpt){0, NULL};
        return (struct KOpt){1, input->child[0]};
    }

    return (struct KOpt){0, NULL};
}

This code demonstrates the generic principle: the projection is defined if and only if the input has a field or variant named x.

7.8 Error propagation

When one function calls another, the success flag ok propagates forward. If a subcall returns ok == 0, the caller must return {0, NULL} immediately. This makes undefinedness explicit and local—no exceptions, no global flags.

7.9 Summary

Chapter 8 — Operational Semantics and Execution

8.1 Purpose

The operational semantics of k describe how expressions are evaluated step by step on actual value trees. It defines when a function is defined for a particular input and what value it returns. All execution—interpretive or compiled—follows these rules.

8.2 Evaluation relation

Evaluation is written as:

⟨ e , v ⟩ ⇓ r

meaning that expression e applied to value v yields result r. If e is undefined for v, the relation does not hold.

r is always a tree (or node) in memory, represented as described in Chapter 6. Undefined results are expressed by the absence of any rule that produces r.

8.3 Rules for base expressions

Identity

⟨ () , v ⟩ ⇓ v

The empty composition () returns its argument unchanged.

Projection

Let label be a field or variant name. If v has a child under label,

⟨ .label , v ⟩ ⇓ v.label

Otherwise the projection is undefined.

Type expression

For a type T,

⟨ $T , v ⟩ ⇓ v     if v ∈ T

and undefined otherwise. Type expressions thus act as identity functions restricted to their type.

8.4 Rules for composition

Sequential composition

⟨ (f g) , v ⟩ ⇓ r

if there exists u such that ⟨ f , v ⟩ ⇓ u and ⟨ g , u ⟩ ⇓ r.

If either step is undefined, the composition is undefined. Because composition is associative,

(f (g h))  ≡  ((f g) h)  ≡  (f g h)

Parentheses are needed only for ().

8.5 Rules for product composition

⟨ { f₁ l₁ , f₂ l₂ , … , fₙ lₙ } , v ⟩ ⇓ { r₁ l₁ , r₂ l₂ , … , rₙ lₙ }

if and only if all subfunctions fᵢ are defined on v and yield rᵢ. If any subfunction is undefined, the whole product composition is undefined.

A product composition constructs a new product node; each result rᵢ becomes one child in canonical field order.

8.6 Rules for union composition

⟨ < f₁ , f₂ , … , fₙ > , v ⟩ ⇓ rⱼ

if there exists the smallest index j such that ⟨ fⱼ , v ⟩ ⇓ rⱼ.

If no subfunction is defined, the union composition is undefined.

8.7 Rules for filters

If a filter F matches a single type T

⟨ ?F , v ⟩ ⇓ ⟨ $T , v ⟩

otherwise it is an identity

⟨ ?F , v ⟩ ⇓ v

Filters therefore act as compile time annotations for type checking only. They are ignored at run-time, unless they lead to fully typed expressions (i.e., can be replaced by a type).

8.8 Evaluation order

Evaluation proceeds left to right. In products, all subfunctions receive the same input; in unions, later functions are evaluated only if earlier ones fail.

The semantics are deterministic: for any given input, at most one result tree can be produced.

8.9 Example

Given:

$bool = < {} true, {} false >;
neg = $bool < .true {{ } false}, .false {{ } true} > $bool;

and input value { {} true } of type bool, evaluation steps are:

  1. ⟨ $bool , { {} true } ⟩ ⇓ { {} true }
  2. ⟨ < .true {{ } false}, .false {{ } true} > , { {} true } ⟩ ⇓ {{ } false}
  3. ⟨ $bool , {{ } false} ⟩ ⇓ {{ } false}

Final result: {{ } false}. If the input were of another type, step 1 would be undefined.

8.10 Implementation correspondence

The evaluation rules map directly onto the runtime ABI:

Semantic rule Runtime operation
Projection k_project
Product composition multiple subcalls + k_make_product
Union composition sequential subcalls with early return
Type runtime check of state
Composition function call chain

In compiled form, the ok flag of KOpt represents whether a rule applies; the node pointer represents the result value.

8.11 Summary

Chapter 9 — Compiler Architecture

9.1 What the compiler does

A compiler for the k language is a program that reads another program (written in k) and produces a lower-level version of it. The lower-level version can then be executed efficiently by a computer.

For k, the compiler’s task is simple in concept:

  1. Read the definitions of types and functions.
  2. Understand their structure and the relationships between them.
  3. Translate them into equivalent instructions that follow the runtime conventions described in Chapters 6–8.

The compiler must ensure that every function in the source program becomes a machine-level function that behaves in exactly the same way: it takes a value as input, may or may not be defined for it, and, if defined, produces another value.

9.2 The main stages

A k compiler is organized as a sequence of well-defined stages. Each stage transforms one representation of the program into another, simpler one.

  1. Reading and parsing — The compiler converts the source text into a tree of syntactic objects. This tree is called the abstract syntax tree (AST). It records the structure of expressions such as { .x a, .y b } or < .x, .y >.

  2. Type analysis and normalization — The compiler expands type names, checks their correctness, and replaces all filters and meta-variables by concrete type information, following the procedure from Chapter 5. The result is a fully typed AST.

  3. Preparation for execution — The compiler builds a type table for all canonical type states (C0, C1, …). For each type, it records whether it is a product or a union and the number and names of its fields or variants. These tables become the metadata used at runtime.

  4. Code generation — Finally, the compiler walks through the typed AST and produces an equivalent description in a lower-level form that follows the runtime conventions: functions returning a success flag and a value pointer. This form can be expressed directly in C or in the LLVM intermediate representation, which is a platform-independent format understood by many compilers.

9.3 Internal structure

A minimal compiler can be viewed as three connected modules:

Although these terms are traditional, the distinction is simple: the front end understands the program, the back end emits it, and the middle part connects the two.

9.4 Data kept by the compiler

During translation the compiler maintains several tables:

Name Purpose
Type table Maps type names to canonical forms and assigns numeric state IDs.
Field table For each product type, records the order and index of its fields.
Variant table For each union type, records the tags and their numeric indices.
Function table Associates function names with their input and output types.

These tables ensure that generated code can find fields and variants by number rather than by name, which simplifies execution.

9.5 Example of transformation

Consider a simple k program:

$bool = < {} true, {} false >;
neg = $bool < /true | false, /false | true > $bool;

  1. Parsing: The compiler recognizes a type definition $bool and a function neg.

  2. Type analysis: Both the input and output of neg are of type bool.

  3. Internal representation: The compiler constructs an internal tree describing that < /true f₁, /false f₂ > means: try the projection /true, then /false, each producing a constant value.

  4. Generated form: In the target language, neg becomes a small function that:

This sequence of steps is fully automatic and follows directly from the semantic rules in Chapter 8.

9.6 Intermediate representation

Before producing final code, many compilers use an intermediate representation (IR). It is a language designed to be easy to generate and easy to translate further into real machine code. For k, the IR mirrors the structure of partial functions:

Concept in k IR operation
Projection .x ‘/x’ PROJECT label_id
Composition (f g) CALL f; CALL g
Union <f,g> TRY f; IF undefined THEN TRY g
Product {.x f, .y g} PRODUCT_CALL (f, g); COMBINE
Type restriction $T CHECK_TYPE state_id

The compiler converts each AST node into one or more IR instructions. The PRODUCT_CALL(f, g) instruction is a higher-level concept that implies applying both f and g to the same input value. The low-level implementation of this would use stack operations to duplicate the input, but the IR itself remains more abstract. Later, these instructions are translated into LLVM or C code using the runtime ABI.

9.7 Linking with the runtime

The generated code does not contain memory allocation or type tables itself. Instead, it relies on the runtime library (krt), which provides:

When the compiler finishes, it outputs a text file in the target language plus references to this runtime library. The two together form an executable program.

9.8 Simplicity of the model

Because every expression in k takes exactly one input and may return one output or be undefined, the compiler never has to deal with variable environments, loops, or side effects. This makes the structure of the generated program very regular:

input → [series of calls and checks] → output or undefined

Each compiled function is independent and stateless. This regularity is what allows k to map cleanly to low-level code.

9.9 Summary

Chapter 10 — From AST to Intermediate Representation

10.1 The purpose of an intermediate form

The abstract syntax tree (AST) of a k program directly reflects how the source code was written. It is easy to read but not convenient for generating machine code. Before code can be produced, the compiler rewrites this tree into a simpler, regular structure called the intermediate representation (IR).

The IR is close to what the machine will execute, but it still looks like a structured program rather than raw binary instructions. Each node in the IR corresponds to a single, well-defined operation such as project a field, apply a function, or combine results.

Using an intermediate form helps in three ways:

  1. It separates understanding of the language from machine details.
  2. It allows the compiler to verify that every function is well formed.
  3. It provides a uniform surface for optimization and for later translation into C or LLVM.

10.2 Shape of the intermediate representation

Each IR instruction corresponds to one semantic rule from Chapter 8. The IR does not need to represent filters or meta-variables, since those are resolved earlier. Only concrete actions remain.

Operation Meaning
PROJECT label_id Apply .label to the input value.
TYPECHECK state_id Accept the input only if its root has the given canonical state.
CALL function_id Invoke another function following the ABI.
UNION [f₁, f₂, …] Try several functions in order until one succeeds.
PRODUCT [l₁=f₁, l₂=f₂, …] Apply each function to the same input and combine results.
FAIL Always undefined.
SEQ [f₁, f₂, …] Apply functions in sequence (composition).

Each function in the program becomes a small list or tree of such IR instructions.

10.3 Example

Source program:

$bool = < {} true, {} false >;
neg = $bool < .true {{ } false}, .false {{ } true} > $bool;

The IR for neg can be written informally as:

neg:
  TYPECHECK bool
  UNION [
    SEQ [ PROJECT true, CONST false ],
    SEQ [ PROJECT false, CONST true ]
  ]
  TYPECHECK bool

This IR expresses the same logic as the source: check the type, then try the first projection .true, otherwise the second, and finally ensure the result is again of type $bool.

10.4 Relation to evaluation

Every IR operation corresponds to a runtime action:

IR operation Runtime function or behavior
PROJECT k_project(input, label_id)
TYPECHECK verify input->state == state_id
CALL call another generated function
UNION sequential if–else test on success flags
PRODUCT multiple subcalls + k_make_product
FAIL return { ok = 0 } immediately
SEQ connect the output of one step as input to the next

By describing computation in these terms, the compiler can generate executable code simply by replacing each IR instruction with its runtime equivalent.

10.5 Building the IR

The process of converting the AST to IR follows a recursive pattern:

  1. Projections become single instructions PROJECT.
  2. Compositions (f g h) become a SEQ list of their components.
  3. Unions <f,g> become a UNION list.
  4. Products {f l₁, g l₂} become a PRODUCT list with labeled entries.
  5. Type expressions $T become TYPECHECK instructions.
  6. Filters disappear; their meaning is already captured by typechecks.

Each transformation step produces IR nodes with fixed behavior and explicit order.

10.6 Verifying the IR

Because k programs are defined by simple composition, a small set of checks ensures correctness:

  1. Each UNION list must have at least one element.
  2. Every PROJECT must have a valid label.
  3. Input and output states of consecutive steps must match.
  4. A function must end in an operation that produces a result (PROJECT, CALL, or combination).

After verification, the IR is guaranteed to represent a valid partial function according to the semantics in Chapter 8.

10.7 Intermediate form as a small language

The IR can be viewed as a minimal language on its own. It has:

Its execution model is the same as the runtime ABI. This means an interpreter for the IR can serve as a reference implementation of the k semantics before any machine code generation is added.

10.8 Example: product composition

For input function { .x a, .y b }, the IR is:

PRODUCT [
  a = PROJECT x,
  b = PROJECT y
]

The runtime sequence is:

  1. Apply each projection.
  2. If both succeed, build a new node with two children in order (a,b).

This pattern covers all record-building operations in the language.

10.9 Why this representation is useful

This intermediate form provides three practical benefits:

  1. Clarity – every step is explicit and local.
  2. Verifiability – type consistency and definedness can be checked mechanically.
  3. Flexibility – the same IR can be translated to many targets (LLVM IR, C, or even interpreted directly).

Because of these advantages, most compilers for declarative languages use an intermediate form of this kind.

10.10 Summary

Chapter 11 — LLVM Basics

11.1 Purpose

The previous chapters described how a k program can be reduced to a small set of intermediate operations. To execute these operations efficiently, the compiler must translate them into an actual machine language. Instead of generating raw machine code directly, we use a common intermediate format called LLVM IR (LLVM Intermediate Representation).

LLVM IR is a low-level, strongly typed language that resembles a simplified form of assembly. It can be read and written as text, analyzed, optimized, and compiled to machine code for almost any processor. For the compiler writer, it provides a bridge between high-level language semantics and executable programs.

11.2 Structure of an LLVM program

An LLVM program consists of global definitions and functions.

Each instruction produces a new value; values are immutable once created. This property is called single static assignment (SSA).

11.3 Data types

LLVM provides several primitive types. Only a few are required for the k compiler:

LLVM type Meaning
i1 one-bit boolean (used for success flag)
i32 32-bit integer (used for state IDs, indices, tags)
ptr or %T* pointer to data in memory
%struct {...} user-defined record (used for KNode and KOpt)

The main structures used by generated code are:

%KNode = type { i32, i32, i32, [0 x %KNode*] }
%KVal  = type { %KNode* }
%KOpt  = type { i1, %KVal }

%KNode represents one tree node in memory; %KOpt represents the result of a partial function, with an ok flag and a value pointer.

11.4 Function signatures

Every compiled k function is translated into one LLVM function with the following signature:

define %KOpt @f_name(%KVal %in) { ... }

The function takes a single argument %in, which holds the pointer to the input value. It returns a %KOpt structure containing the success flag and the resulting value.

This mirrors the runtime ABI introduced in Chapter 7. By using the same layout, all functions can call each other without conversions.

11.5 Control flow

LLVM IR uses conditional branches to express choices and phi-nodes to merge results from different paths.

A typical pattern for union composition <f,g> is:

%r1 = call %KOpt @f(%in)
%ok1 = extractvalue %KOpt %r1, 0
br i1 %ok1, label %success, label %try_next

try_next:
%r2 = call %KOpt @g(%in)
br label %merge

success:
br label %merge

merge:
%res = phi %KOpt [ %r1, %success ], [ %r2, %try_next ]
ret %res

This code means: try f; if it succeeds, use that result; otherwise, try g. The phi instruction chooses between values coming from different blocks.

11.6 Memory operations

Most functions in k do not modify existing nodes; they create new ones. Node creation is implemented as calls to runtime functions:

declare %KVal @k_make_product(i32 %state, i32 %n, %KVal* %children)
declare %KVal @k_make_union(i32 %state, i32 %tag, %KVal %child)

These calls allocate new immutable nodes. The compiler provides the correct state, tag, and child references according to the canonical type.

11.7 Constants

Constant values such as {{} true} are represented as global variables in LLVM:

@unit_node  = constant %KNode { 1, -1, 0, [] }
@true_node  = constant %KNode { 0, 0, 1, [@unit_node] }
@false_node = constant %KNode { 0, 1, 1, [@unit_node] }

Each constant is a fully formed node with fixed fields. When a constant function is called, the compiler returns a pointer to the corresponding global node.

11.8 From IR to LLVM

Translating the compiler’s intermediate form (Chapter 10) into LLVM is mechanical:

IR operation LLVM translation
PROJECT call @k_project
TYPECHECK compare input->state with constant
CONST return constant node
PRODUCT evaluate subcalls, check flags, call @k_make_product
UNION generate branching structure as above
SEQ chain calls: feed output to next input
FAIL return %KOpt { 0, undef }

These mappings produce correct, low-level code while remaining faithful to the language semantics.

11.9 Example

For the function neg from earlier:

$bool = < {} true, {} false >;
neg = $bool < .true {{ } false}, .false {{ } true} > $bool;

The simplified LLVM version may look as follows (comments added):

define %KOpt @neg(%KVal %in) {
entry:
  ; Try the .true branch
  %r1 = call %KOpt @project_true(%in)
  %ok1 = extractvalue %KOpt %r1, 0
  br i1 %ok1, label %case_true, label %case_false

case_true:
  %res_true = insertvalue %KOpt undef, i1 1, 0
  %res_true2 = insertvalue %KOpt %res_true, %KVal @false_node, 1
  ret %KOpt %res_true2

case_false:
  %r2 = call %KOpt @project_false(%in)
  %ok2 = extractvalue %KOpt %r2, 0
  br i1 %ok2, label %case_false_valid, label %undefined

case_false_valid:
  %res_false = insertvalue %KOpt undef, i1 1, 0
  %res_false2 = insertvalue %KOpt %res_false, %KVal @true_node, 1
  ret %KOpt %res_false2

undefined:
  ret %KOpt { i1 0, %KVal undef }
}

While verbose, this code mirrors the evaluation rules exactly and can be optimized by standard LLVM tools.

11.10 Optimization and verification

LLVM provides built-in passes that simplify generated code:

The compiler can run these passes automatically to produce compact and efficient output. LLVM also verifies that all types and values are consistent before emitting machine code.

11.11 Summary

Chapter 12 — Code Generation

12.1 Purpose

The code generation phase translates the intermediate representation (IR) of each k function into executable code using the LLVM format described in Chapter 11. This translation is systematic: every IR operation corresponds to a specific sequence of LLVM instructions or calls to the runtime library.

The compiler’s objective is to produce code that behaves exactly like the formal semantics of k—no more and no less. Each step of the translation can therefore be viewed as a mechanical implementation of one of the rules introduced in Chapter 8.

12.2 Structure of generated functions

Each k function becomes a stand-alone LLVM function with the signature:

define %KOpt @f_name(%KVal %in)

Internally, the function has one or more basic blocks. Each block performs a small action: a projection, a check, a call, or a node construction. Blocks are connected by explicit branches that depend on the ok flag of intermediate results.

At the end of the function, exactly one %KOpt value is returned.

12.3 Translating core operations

The compiler maintains a mapping from IR operations (Chapter 10) to LLVM code patterns.

IR Operation Generated Code Pattern
PROJECT label call %KOpt @k_project(%KVal %in, i32 label_id)
TYPECHECK state Compare input->state with constant state; if unequal, return {0, undef}
CONST node Return {1, node_pointer}
SEQ [f₁,f₂,…] Emit each function call in order, test ok after each
UNION [f₁,f₂,…] Emit chained if blocks; return first successful result
PRODUCT [l₁=f₁, …] Call all subfunctions; if all succeed, collect children and call @k_make_product
FAIL Return {0, undef} immediately

These templates cover the entire language.

12.4 Example: sequential composition

For IR:

SEQ [ PROJECT x, CALL f, CALL g ]

the compiler emits:

%r1 = call %KOpt @k_project_x(%in)
%ok1 = extractvalue %KOpt %r1, 0
br i1 %ok1, label %cont1, label %fail

cont1:
%r2 = call %KOpt @f(%r1.val)
%ok2 = extractvalue %KOpt %r2, 0
br i1 %ok2, label %cont2, label %fail

cont2:
%r3 = call %KOpt @g(%r2.val)
ret %KOpt %r3

fail:
ret %KOpt { i1 0, %KVal undef }

Each block corresponds to one stage in the composition. The use of conditional branches ensures that undefinedness propagates correctly.

12.5 Example: product composition

For IR:

PRODUCT [ a = PROJECT x, b = PROJECT y ]

the compiler generates code equivalent to:

%ra = call %KOpt @k_project_x(%in)
%ok_a = extractvalue %KOpt %ra, 0
br i1 %ok_a, label %try_b, label %fail

try_b:
%rb = call %KOpt @k_project_y(%in)
%ok_b = extractvalue %KOpt %rb, 0
%ok_all = and i1 %ok_a, %ok_b
br i1 %ok_all, label %build, label %fail

build:
%children = alloca [%KVal, 2]
%p0 = getelementptr [%KVal,2], [%KVal,2]* %children, i32 0, i32 0
store %KVal (extractvalue %KOpt %ra, 1), %KVal* %p0
%p1 = getelementptr [%KVal,2], [%KVal,2]* %children, i32 0, i32 1
store %KVal (extractvalue %KOpt %rb, 1), %KVal* %p1
%res = call %KVal @k_make_product(i32 state_id, i32 2, %KVal* %children)
ret %KOpt { i1 1, %KVal %res }

fail:
ret %KOpt { i1 0, %KVal undef }

The resulting LLVM code faithfully follows the semantic rule: the product is defined only if all components are defined.

12.6 Example: union composition

For IR:

UNION [ .x, .y ]

the compiler produces a branching structure:

%r1 = call %KOpt @k_project_x(%in)
%ok1 = extractvalue %KOpt %r1, 0
br i1 %ok1, label %merge, label %try_next

try_next:
%r2 = call %KOpt @k_project_y(%in)
br label %merge

merge:
%res = phi %KOpt [ %r1, %ok1 ], [ %r2, %try_next ]
ret %KOpt %res

This pattern ensures that the first defined branch wins, as specified by the semantics.

12.7 Managing constants and types

Whenever an expression references a constant value or a type restriction:

This approach removes all high-level notation before reaching machine level.

12.8 Optimizing during generation

Because the structure of k is very regular, many optimizations can be applied while generating code:

Such simplifications can be done by the compiler itself or delegated to LLVM’s optimization passes.

12.9 Interaction with the runtime

All allocation and field access are performed through runtime calls. The compiler never manipulates pointers directly beyond passing them to these helpers. This design ensures that compiled code is independent of the internal memory layout.

The generated functions thus resemble small graphs of calls and conditionals built entirely on top of the fixed ABI.

12.10 Linking and verification

After all functions are emitted, the compiler writes a single LLVM module containing:

The LLVM verifier then checks that:

Only verified code is passed to the optimizer or the machine-code generator.

12.11 Summary

Chapter 13 — Linking and Execution

13.1 Purpose

The last stage of compilation connects the generated code with the runtime library and produces an executable program. This process is called linking. Once linked, the program can be run like any other compiled program: it reads input values, executes the compiled k functions, and returns a result.

The linking and execution stages ensure that the compiled code, the runtime library, and the data it manipulates all agree on structure and conventions.

13.2 The runtime library

All compiled k programs depend on a small runtime component, often distributed as a file named krt.c or krt.o. This library provides:

Function Purpose
k_make_product(state, n, children) Allocate a product node with n fields.
k_make_union(state, tag, child) Allocate a union node with a single variant.
k_project(input, label_id) Perform projection .label.
k_fail() Return a predefined undefined result { ok = 0 }.
k_unit() Return the constant unit value {}.

These functions implement the same concepts as the semantic rules described earlier, but at the level of actual memory operations. They are compiled once in a low-level language such as C and reused by all generated programs.

13.3 Metadata tables

Along with the runtime functions, the compiler produces metadata describing each canonical type used in the program:

These tables are stored as constant arrays in the compiled module. Runtime functions use them to interpret and construct nodes correctly without needing any dynamic reflection.

13.4 Linking

The generated LLVM file is compiled and linked with the runtime library in two simple steps:

clang -O2 -c krt.c -o krt.o
clang -O2 program.ll krt.o -o program

The first command compiles the runtime once. The second command combines the runtime with the program’s own functions and constant definitions.

The result is a native executable file named program. When run, it behaves exactly like the original k program.

13.5 Initialization

When the executable starts, it performs a few basic steps:

  1. Allocate an arena for storing newly created nodes.
  2. Initialize constant nodes such as the unit {} and any user-defined constants.
  3. Optionally, prepare a table of function pointers for fast invocation.

After initialization, the main compiled function can be called directly.

13.6 Executing a compiled function

Every compiled function has the signature:

struct KOpt function(struct KNode* input);

To run a program, a caller must supply an input value tree in the expected canonical form. The value is typically created by another function or loaded from serialized data.

For example, to execute a function neg expecting a $bool:

struct KOpt result = neg(&true_node);
if (result.ok)
    print_value(result.val);
else
    printf("undefined\n");

If the input is { {} true }, the output will be { {} false }.

13.7 Input and output conventions

At the machine level, a “value” is always represented by a pointer to a KNode. Each compiled function expects exactly one such pointer. When a function returns, its output pointer may refer to an existing constant node, a new node allocated in the arena, or nothing at all if undefined.

There is no special I/O system in k itself; printing or reading values is the responsibility of the host environment. In practice, programs are tested by calling compiled functions from C or Python and inspecting their returned structures.

13.8 Debugging and inspection

Because both the generated code and the runtime library are deterministic and memory-safe, debugging usually consists of examining node contents.

Two simple runtime utilities are useful:

They allow the user to confirm that compiled functions construct the correct tree shapes.

13.9 Verification

After linking, the compiler can run a self-verification pass:

  1. Construct small sample inputs for each exported function.
  2. Execute the compiled function.
  3. Compare results with the interpreter’s result using structural equality.

If all match, the compiler’s translation is confirmed correct for those test cases. This method is especially valuable during compiler development and textbook exercises.

13.10 Example: complete run

Example program:

$bool = < {} true, {} false >;
neg = $bool < .true {{ } false}, .false {{ } true} > $bool;

Steps:

  1. Compile to neg.ll.
  2. Link with krt.o.
  3. Run a small C driver that calls neg.

Output:

input  = {{ } true}
result = {{ } false}

If input is {} or any non-$bool value, the function is undefined and prints “undefined”.

13.11 Summary

Chapter 14 — Canonical Serialization

14.1 Purpose

Serialization is the process of converting a value in memory into a compact sequence of bits or bytes that can be stored or transmitted. For the k language, serialization serves an additional goal: it defines a canonical representation of each value that is unique and independent of the machine on which it was produced.

A canonical encoding allows values to be compared, hashed, or stored in a registry in a reproducible way. Two values that are structurally identical will always produce the same bit sequence.

14.2 Canonical type information

Serialization always depends on the canonical form of the type. A type in canonical form is a finite tree automaton (Chapter 3) that describes the structure of all its values. Because this form is unique, every possible value of the type can be encoded deterministically.

Before any value is serialized, the compiler or runtime must know:

This information acts as the grammar from which all bit sequences are derived.

14.3 Encoding principle

Each node in a value tree corresponds to one of the type’s states.

Thus, the sequence of bits records exactly which union branches were taken while descending the tree.

14.4 Fixed-length codes per state

For simplicity, each union state uses fixed-length binary codes of equal size.

If a union has m variants, then

k = ceil(log2(m))

bits are needed. Each variant is numbered in canonical order from 0 to m − 1 and represented by the binary form of its index.

Products and units use k = 0 and emit no bits.

This rule allows the decoder to know, from the type alone, how many bits to read at each step.

14.5 Example: natural numbers

For the type

$bnat = < bnat 0, bnat 1, {} _ >;

the canonical form has three transitions from state C0. Therefore, k = ceil(log2(3)) = 2 bits are required per union node.

Assigning codes in order:

Rule Code
C0 → {C0 “0”} 00
C0 → {C0 “1”} 01
C0 → {C1 “_” } 10

The value { {{ {} _ } 1 } 0 } is encoded by concatenating the codes of the transitions chosen during a leftmost derivation:

00 → first C0
01 → next C0
10 → final C0

Resulting bit sequence: 000110.

14.6 Decoding

Decoding is deterministic and mirrors the encoding process:

  1. Start at the root state (C0).
  2. If the current state is a union, read k bits to choose a rule.
  3. Create the corresponding node, then recursively decode its child or children.
  4. For products, decode all children in order; for units, stop.

The decoder stops when the entire tree has been reconstructed and all bits have been consumed.

Because every union code is of fixed length, the decoding process requires no backtracking and can be implemented as a simple loop.

14.7 Folding repeated subtrees

Many values contain repeated substructures. To avoid serializing the same tree several times, identical subtrees can be folded into a directed acyclic graph (DAG) before encoding.

Each unique node is assigned an identifier. When the encoder encounters a repeated node, it emits a reference to its identifier instead of encoding it again.

During decoding, the identifier is resolved to the corresponding subtree, reconstructing the shared structure.

Folding is optional; it saves space without changing the logical value.

14.8 Stream format

A minimal canonical bitstream consists of:

  1. Header – type hash (e.g., 8 bytes) identifying the canonical type.
  2. Node count – integer N if DAG encoding is used.
  3. Encoded data – concatenation of all fixed-length union codes and, if folded, node references.

If two systems share the same canonical type table, the bitstream alone is enough to reconstruct the original value.

14.9 Implementation sketch

A compact encoder can be written as follows:

procedure encode(node):
    if node.arity == 0:
        return
    if node.arity == 1:
        write_bits(code_for(node.state, node.tag))
        encode(node.child[0])
    else:
        for each child in node.children:
            encode(child)

The corresponding decoder reverses the process. Both procedures require only the canonical type tables and simple bit operations.

14.10 Determinism and equality

Because encoding is fully determined by the canonical type and field order, two equal values always produce identical bit sequences. Conversely, decoding the same bit sequence always yields the same tree.

This property allows equality comparison by direct byte comparison of serialized forms, without traversing the trees in memory.

14.11 Summary

Chapter 15 — Optimization and Folding

15.1 Purpose

Optimization in the k compiler is the process of simplifying functions without changing their meaning. The goal is to make the generated code smaller, faster, and easier to verify. Because k is purely functional and has no side effects, optimizations are safe whenever the simplified function is equivalent to the original one.

This chapter describes a few basic optimizations that follow directly from the semantics introduced earlier.

15.2 Constant folding

A constant is a function that ignores its input and always produces the same value. If a composition of functions can be evaluated entirely at compile time, it can be replaced by a single constant function.

Example:

true_bool  = {{ } true} $bool;
not_true   = (true_bool neg);

The compiler observes that (true_bool neg) always yields false_bool, so it replaces it with a constant:

not_true = {{ } false} $bool;

Constant folding removes unnecessary runtime computation.

15.3 Type-based simplifications

Since type expressions act as identity functions defined only on specific values, they can be eliminated when redundant:

$bool $bool f   →  $bool f

If a function’s input or output type is already known from context, repeated checks can be omitted. The compiler ensures that at least one valid check remains to preserve correctness.

15.4 Inlining

Inlining replaces a call to a small function by its body. It avoids the overhead of a function call and often exposes further simplifications.

Example:

id = ();
f  = (id g);

Because id is the identity function, (id g) is equivalent to g. Inlining removes the useless call.

For larger functions, inlining is applied selectively—only when it shortens the resulting code or eliminates intermediate values.

15.5 Dead-branch elimination

In a union composition <f, g>, if type analysis shows that the input type can only satisfy the first branch, the second branch can never be defined and is removed.

Example:

$bool = < {} true, {} false >;
f = $bool < .true {{ } false} >;

Here, since $bool restricts the input to only the two variants true and false, and the second variant .false is not handled, the compiler infers that f is undefined for .false and simplifies the code accordingly.

Dead-branch elimination keeps the generated control flow minimal.

15.6 Common subexpression elimination

If the same partial function is applied multiple times to the same input, the result will always be the same. The compiler can compute it once and reuse the result.

Example:

{ .x .y, .x .z }

Both fields start with the projection .x. The compiler computes .x once, stores the result, and reuses it for .y and .z. This optimization reduces repeated traversal of the same input structure.

15.7 Canonical folding

During evaluation, many values share identical subtrees. A folding pass replaces identical subtrees by shared nodes, forming a minimal DAG (directed acyclic graph).

At compile time, folding may also apply to constant expressions. If two constant subtrees are identical, they are merged and stored as a single global node.

This process ensures that structural equality corresponds to pointer equality: two values are identical if they share the same root node.

15.8 Function canonicalization

Every function can be normalized by expanding all type aliases, inlining trivial definitions, and folding identical subfunctions. The normalized form of a function depends only on its semantics, not on the way it was written.

A stable hash computed from this canonical representation serves as a permanent identifier for the function, just as type hashes identify canonical types.

This property is essential for the schema registry described in the next chapter.

15.9 Runtime simplifications

At runtime, additional micro-optimizations are possible:

Such optimizations reduce memory usage without changing program behavior.

15.10 Equivalence and correctness

Each optimization must preserve semantic equivalence: for every input, the optimized function must be defined for exactly the same values and must return the same result when defined.

Because k’s semantics are purely functional, equivalence can be tested mechanically by comparing evaluation results on all finite inputs of a small type, or by structural reasoning when types are infinite.

15.11 Summary

Chapter 16 — Toward a Universal Schema Registry

16.1 Motivation

Every canonical type and function in k has a unique structural form and a stable hash. These hashes can serve as global identifiers. A registry that maps such identifiers to definitions allows programs and systems to exchange schemas and functions safely and reproducibly.

16.2 Basic structure

A schema registry stores entries of two kinds:

Kind Example content
Type canonical automaton text for a type hash
Function canonical IR or serialized representation for a function hash

Each entry is immutable. New versions are added as new hashes.

16.3 Key operations

  1. Lookup by hash — return the canonical definition.
  2. Lookup by shape — search for functions with given input/output type hashes.
  3. Verification — ensure that two parties share the same canonical form before exchanging values.

These operations can be implemented as simple key–value queries.

16.4 Example format

A minimal JSON entry:

{
  "hash": "C0ABCDEF",
  "kind": "type",
  "definition": "$C0=<C0\"0\",C0\"1\",C1\"_\">;$C1={};"
}

or for a function:

{
  "hash": "F7B1A2",
  "kind": "function",
  "input": "C0ABCDEF",
  "output": "C9FFF1",
  "ir": "SEQ [PROJECT x, CONST true]"
}

16.5 Uses

16.6 Summary

Appendix A — Implementing a Prototype Compiler in Python

A.1 Purpose

This appendix outlines how to implement a simple, working prototype of the k compiler in Python. The goal is to let the reader experiment with parsing, type normalization, and LLVM code generation using only standard tools and a few small libraries. The prototype does not need to support optimization or a full runtime—only the basic translation pipeline.

A.2 Required environment

Install:

python3 -m venv kenv
source kenv/bin/activate
pip install llvmlite

llvmlite provides an interface to LLVM for code generation. No additional dependencies are required.

k-compiler/
 ├── main.py             # command-line driver
 ├── parser.py           # converts source text to AST
 ├── types.py            # canonical type construction
 ├── normalize.py        # filter resolution and typing
 ├── ir.py               # intermediate representation
 ├── codegen.py          # translation from IR to LLVM
 ├── runtime.ll          # minimal runtime in LLVM
 └── examples/           # sample k programs

Each module is small and focused on one task.

A.4 The AST

Represent the language syntax with Python classes:

class Expr: pass

class Composition(Expr):
    def __init__(self, parts): self.parts = parts

class Product(Expr):
    def __init__(self, fields): self.fields = fields  # [(label, expr), ...]

class Union(Expr):
    def __init__(self, options): self.options = options  # [expr, ...]

class Projection(Expr):
    def __init__(self, label): self.label = label

class Constant(Expr):
    def __init__(self, name): self.name = name

The parser builds these objects from source text.

A.5 Type normalization

Maintain canonical type states as small Python objects:

class TypeState:
    def __init__(self, kind, transitions):
        self.kind = kind      # 'product' or 'union'
        self.transitions = transitions  # [(label, next_state)]

Normalization expands type aliases and assigns numeric state IDs (C0, C1, …). For a prototype, a simple structural hash (using json.dumps) can serve as the canonical identifier.

A.6 Intermediate representation

Represent IR instructions as simple tuples or small classes:

class Project:  def __init__(self, label): self.label = label
class Const:    def __init__(self, node):  self.node = node
class Seq:      def __init__(self, parts): self.parts = parts
class UnionIR:  def __init__(self, parts): self.parts = parts
class ProductIR:def __init__(self, fields):self.fields = fields

A recursive function converts an AST expression into IR following Chapter 10.

A.7 Generating LLVM code

Using llvmlite.ir, create one LLVM function per compiled function:

from llvmlite import ir

mod = ir.Module(name="k")

# LLVM type definitions
KNodePtr = ir.PointerType(ir.IntType(8))
KVal  = ir.LiteralStructType([KNodePtr])
KOpt  = ir.LiteralStructType([ir.IntType(1), KVal])

def emit_function(name, ir_expr):
    fn_type = ir.FunctionType(KOpt, [KVal])
    fn = ir.Function(mod, fn_type, name=name)
    block = fn.append_basic_block('entry')
    builder = ir.IRBuilder(block)
    # translate ir_expr recursively into builder calls
    builder.ret(ir.Constant(KOpt, (ir.Constant(ir.IntType(1), 0),
                                   ir.Constant(KVal, ir.Constant(KNodePtr, None)))))

The translation patterns follow those described in Chapter 12. Each IR node is emitted as a call or conditional block using builder.call, builder.if_then, and so on.

A.8 Minimal runtime

Write a minimal runtime.ll that defines stubs for:

declare %KOpt @k_project(%KVal %v, i32 %label)
declare %KVal @k_make_product(i32 %state, i32 %n, %KVal* %children)
declare %KVal @k_make_union(i32 %state, i32 %tag, %KVal %child)

These can simply return placeholder constants for testing. Later, they can be replaced with the real runtime implemented in C.

A.9 Putting it together

A small driver script (main.py) can compile a file and emit LLVM text:

import parser, normalize, ir, codegen

def compile_file(path):
    src = open(path).read()
    ast = parser.parse(src)
    typed = normalize.process(ast)
    ir_tree = ir.from_ast(typed)
    llvm_module = codegen.emit(ir_tree)
    print(str(llvm_module))

Run:

python main.py examples/neg.k > neg.ll
clang -O2 neg.ll runtime.ll -o neg

A.10 Suggested extensions

  1. Implement the runtime functions in Python for quick testing.
  2. Add a textual REPL that reads a k expression and prints its IR.
  3. Integrate a simple interpreter to compare interpreter and compiled results.
  4. Use hashing of canonical forms to name generated LLVM functions.

A.11 Summary

A prototype compiler can be realized in fewer than a thousand lines of Python. It can parse k definitions, construct canonical types, translate expressions into IR, and generate valid LLVM code. Such a prototype is enough to experiment with all ideas presented in this textbook and to verify the semantics of the k language in practice.

Appendix B — Incorporating External Predefined Types and Functions

B.1 Purpose

The k language is intentionally minimal. Nevertheless, real systems often need to interact with data types and operations defined outside of k—for example, numeric values, text, or platform-specific constants. This appendix explains how external predefined types and functions can be introduced into a k compiler without changing the language itself.

B.2 External types

An external type is a canonical type that is not expressed through k’s own product-and-union syntax but is known to the compiler through registration.

Each external type has:

Field Description
Name symbolic name (e.g., $int, $string)
Hash unique stable identifier, just like canonical types
Runtime kind how the value is stored in memory (pointer, immediate integer, etc.)
Adapter functions conversion between the external representation and the standard KNode tree

Example registry entry:

{
  "hash": "E001",
  "kind": "type",
  "external": true,
  "name": "$int",
  "runtime_kind": "primitive_i64"
}

The compiler treats such a type as an atomic node, represented internally as a single KNode with arity = 0 but tagged as external.

B.3 External constructors

External types may provide special constructors or constants. For example, $int might include predefined constant functions:

zero  = {} $int;
one   = {} $int;

At compile time these appear as constant functions returning fixed external nodes provided by the runtime.

B.4 External functions

External functions are partial functions implemented outside of k but declared inside a k program. They have known input and output types, possibly external.

Declaration syntax:

extern add : $int $int → $int;
extern less : $int $int → $bool;

At compile time the compiler records the signature and associates it with a runtime symbol name such as k_ext_add.

When generating code, each external call becomes a standard function call following the ABI:

declare %KOpt @k_ext_add(%KVal %a, %KVal %b)

The runtime library provides these implementations in a native language (C, C++, Rust, etc.).

B.5 Integration with canonical types

External types are integrated into the canonical system as leaf states. They can appear as components in products or unions just like built-in ones.

Example:

$point = { $int x, $int y };

Canonical form:

$C0 = { C1 "x", C1 "y" };
$C1 = external $int;

This allows normal serialization and type comparison; the external leaf is treated as opaque but identified by its hash.

B.6 Serialization and external values

During serialization, an external node is encoded by:

  1. Its type hash (to indicate which external kind it represents).
  2. A binary blob produced by a runtime-supplied encoder for that type.

Deserialization reverses the process using the corresponding decoder. All external codecs must be deterministic and version-stable to preserve canonical equality.

B.7 Example

Suppose we introduce $int and external function add:

$pair_int = { $int a, $int b };
sum = { .a x, .b y } (add x y);

The compiler generates code that:

All logic outside arithmetic remains standard k code.

B.8 Practical implementation

In a Python prototype:

EXTERNAL_TYPES = {
    "$int": {"hash": "E001", "kind": "external", "runtime_kind": "primitive_i64"}
}

EXTERNAL_FUNCS = {
    "add":  {"inputs": ["$int", "$int"], "output": "$int", "symbol": "k_ext_add"},
    "less": {"inputs": ["$int", "$int"], "output": "$bool", "symbol": "k_ext_less"}
}

During code generation, when a call refers to an external function, the compiler emits a call to the symbol given in the table.

B.9 Summary