Skip to Content
ReferenceLanguage

13. Lowering to C++

The normative CP Lang 0.3 specification.

This is the normative specification (source). For a gentler introduction, start with the guides.

Status: draft for 0.3.0. This is the contract between the language and the generated C++17: what each form becomes, what it costs, and what cpl explain reports. Sources: decisions 31, 52, 148, 149; archived design/spec/18; 03-numbers-layout.md for widths and niches.

13.1 The output file

  • One deterministic C++17 file: a stamp, the used runtime pieces, the used library instances, then main. Same source and pins give the same bytes. Warn above 32 KB (the target for every solution), fail at 64 KB (profile-adjustable). (R13.1.1)
  • main starts a thread with the profile's stack (default 1 GB, halving down to 8 MB) and runs the program on it. (R13.1.2)
  • Input is one bulk fread and a hand-written parser; output is one buffer written at exit or flush. (R13.1.3)
  • Release builds compile with the profile's flags and emit no checks (chapter 9). The lowering adds no undefined behaviour to valid programs, and avoids it wherever that is free: signed arithmetic that may overflow is done in unsigned and cast back, shifts are masked, and every array is filled at construction. Unchecked indexes and x! on an invalid program are as unsafe as the same C++ (§9.2). (R13.1.4)

13.2 Values

FormC++
Int, rangesint64_t in locals; storage at the range's width (uint8_t ... int64_t) (R13.2.1)
U64, I128, F64, Bool, Charuint64_t, __int128, double, bool, char (R13.2.2)
position v: Vunsigned of V's storage width (R13.2.3)
cutthe same width, holding the count before it (R13.2.4)
?T with a nicheT's storage with the niche value as None (R13.2.5)
?T without oneT plus a flag byte, aligned (R13.2.6)
tuple, record, structa C++ struct, fields in storage order (R13.2.7)
enumniche-filled payload, or tag beside the largest payload (R13.2.8)
[D]Tpointer plus count, heap buffer; never a stack VLA (R13.2.9)
List<T>, Stran owned growable buffer (std::vector-like runtime type) (R13.2.10)
Mod<P> constantuint32_t or uint64_t with Montgomery or Barrett constants folded (R13.2.11)
Mod(p) runtimethe same plus constants in the fresh type's static slot (R13.2.12)
fresh-type dataone static slot per declaration site, saved and restored across recursive re-entry (R13.2.13)

Large static arrays (over 4 KB) and every runtime-sized array live on the heap. Locals of plain types live in registers or the stack.

13.3 Functions, closures, generators

  • Every generic instantiation is a separate C++ function with a mangled name; there are no C++ templates in the output for language generics. (R13.3.1)
  • A function value with a known target is passed as an empty struct and inlined; captures are passed as references at each call (chapter 6). There is no std::function and no indirect call. (R13.3.2)
  • A non-recursive generator inlines its body with the loop body in place of yield. A recursive generator becomes a recursive function taking the loop body as a parameter; when the body can break or return, a stop flag is threaded through that specialization only. (R13.3.3)
  • @memo(array) is a lazily allocated dense table of ?R (jagged when bounds depend on earlier parameters); @memo(map) is an open- addressing table keyed by the parameters' storage. (R13.3.4)
  • Views are ordinary structs holding a pointer (lent) or the value (owned) plus their closures; walking them is a loop with no allocation. (R13.3.5)

13.4 Ownership

Ownership has no runtime representation. Lends are pointers or references, moves are bitwise and leave the source dead (no destructor runs for a moved-from value), and .clone() is an explicit deep copy. A struct whose fields may be lent or owned is monomorphized on that choice only when the field's storage differs (a lent List is a pointer, an owned one is the buffer); cpl explain lists such copies.

13.5 Library specializations

Each library structure documents its representation and every law-selected specialization, and codegen picks exactly that one: iterative bottom-up segment trees in one flat array, no push-down when tags commute, sliding folds by group/selective/general, sparse tables for idempotent ops, CSR graphs, Rooted arrays in preorder. cpl explain names the choice and the law that allowed it.

13.6 What cpl explain reports

For any program: every type's size, storage order, padding and niche; every array's element width and peak bytes at the input bounds; total peak memory against the profile; each specialization and the law or bound behind it; each check remaining in checked builds and which are kept in release; each @cache, @trusted and @cpp site; each generic instance and context copy with its output bytes. The LSP shows the same data inline (tools/lsp.md).

13.7 Later

Profile-driven vectorization: a judge profile names the instruction set (isa: avx2), codegen emits the matching #pragma GCC target, narrows arithmetic where ranges allow and vectorizes provable loop shapes; explain says which loops vectorized and why not.

13.8 Cost model tables (migrated from design/COST.md)

Cost model

Every core form, what it lowers to in C++17, what it costs, and what each build checks. "Costs are visible" is checked here: each row names a test snippet under tests/cost/ whose emitted C++ and cpl explain output must match the row. A row without a passing snippet is unverified; a form whose real lowering is worse than its row is a bug, and a deliberate exception is listed under Debt.

Status: no row has its snippet yet, so every row is a target, not a measurement. Rows land verified one at a time.

Rules every row follows:

  • Anything that looks O(1) is O(1); anything O(n) or allocating looks it.
  • No std::function, virtual call, hidden heap allocation or hidden traversal unless the row says so.
  • Debug and release differ only in checks, never in results for valid programs.

Scalars

FormLowers toTimeAllocDebug checksRelease checks
Int arithmeticint64_t opsO(1)noneoverflow trapswraps
range type lo..=hi storagenarrowest of int32_t/uint32_t/int64_tO(1)nonestore into a range-typed place traps if out of rangesame
/, %floor/Euclidean helper (one extra branch)O(1)nonedivision by zero trapssame
**square-and-multiplyO(log k)noneoverflow trapswraps
Mod<P> opsuint32_t with constant-divisor reductionO(1); inv O(log P)nonenonenone
chained comparisonone comparison per link, operands evaluated once (§130)O(links)nonenonenone

Absence

FormLowers toTimeAllocDebugRelease
?Int, ?V, ?rangeniche value in the same word (Int excludes INT64_MIN)O(1)nonenonenone
?T for other Tvalue + flagO(1)nonenonenone
x!loadO(1)nonetraps on none unless flow facts prove itsame
x ?? y, ?, none + xbranchO(1)nonenonenone

Index spaces and collections

FormLowers toTimeAllocDebugRelease
domain V = lo..=hiinteger; runtime-sized domains read one hidden global slot (saved/restored on recursive re-entry)O(1)nonenonenone
D.cuts cut domainintegerO(1)nonenonenone
a[v] with v: V, a: [V]Tunchecked loadO(1)nonenonenone
xs[i] on List/StrloadO(1)nonebounds check unless provensame
range l..r / cut range j..itwo integers; cut range → position range is free (§124)O(1)nonenonenone
slice xs[l..r]view (ptr, len) (§123)O(1)nonebounds check unless provensame
[V]T = xone heap array, filledO(n)heap, oncenonenone
[f(x) for x in s] (no filter)reserved vector + loopO(n)heap, once (reserved)nonenone
xs.push(x)amortized vector pushO(1) amortizedamortizednonenone
xs.sort(by: k)std::sort with inlined keyO(n log n)nonenonenone
for x in xs / for v in V / product domainsplain loop / nested integer loopsO(n)nonenonenone

Binding, control and functions

FormLowers toTimeAllocDebugRelease
let, var, let ... else, if letlocals and branchesO(1)nonenonenone
labelled break/continue, loop else (§125)goto / flag-free branchO(1)nonenonenone
non-recursive generator in forinlined; each yield runs the body in placeas writtennonenonenone
recursive generator in for with break/return (§126)recursive function, body inlined at the yield; one stop branch per frame only when the body can exitas written + 1 branch/framenonenonenone
closure argumenttemplate functor parameter, inlined (cpl explain: static)O(1) callnonenonenone
recursive lambda / nested fn (§127)self-passing generic lambdadirect callnonenonenone
operator value (by: <, +)functor, inlinedO(1)nonenonenone
@memo on provably small boundsflat tableO(1) lookupheap, oncenonenone

Mutation and places

FormLowers toTimeAllocDebugRelease
x op= y (statement)in-place opO(1)noneas for the opas for the op
x min= y / max= as a Bool (§129)one compare + storeO(1)nonenonenone
let k = mut a[i]reference, index evaluated onceO(1)nonenonenone
m[k] += 1 on Mapone lookup, inserts default (§128)O(1) expectedmay insertnonenone
return of a containermove (§128)O(1)nonenonenone
let b = a (heap value, last use)moveO(1)nonenonenone
a.clone()deep copyO(size)heapnonenone
x.take()move out, leave emptyO(1)nonenonenone
a.swap(i, j), swap(mut a, mut b)swapO(1)nonenonenone
.absorb(mut other)small-into-large drainO(min size)amortizednonenone

I/O

FormLowers toTimeAllocDebugRelease
read<T>()buffered fast reader, typed parseO(input)none beyond the valuedeclared bounds checkedsame
print(...)buffered writerO(output)nonenonenone

Debt (forms that cost more than their row)

FormTodayTargetOwner
closures stored in struct fields, recursive local closures, fn params of recursive fns, reassigned fn slotsstd::functiontemplate parameter or self-passing lambdacodegen

Enforcement

Each row gets one snippet tests/cost/<form>.cp plus assertions on its emitted C++ (e.g. no std::function, no allocation inside the loop, the expected integer width) and on cpl explain --json. scripts/check.sh runs them; a new core form lands with its row and snippet in the same commit.

On this page