1module Std.Natural
2
3family NaturalArithmeticErrorCode : Type 0
4constructor NaturalArithmeticModuloByZero
5constructor NaturalArithmeticDivideByZero
6
7end-family
8
9family NaturalModuloResult : Type 0
10constructor NaturalModuloSucceeded
11field unrestricted naturalModuloValue : Nat
12constructor NaturalModuloFailed
13field unrestricted naturalModuloError : (family NaturalArithmeticErrorCode)
14
15end-family
16
17family NaturalDivisionState : Type 0
18constructor NaturalDivisionStateValue
19field unrestricted naturalDivisionRemainder : Nat
20field unrestricted naturalDivisionQuotient : Nat
21
22end-family
23
24family NaturalDivideResult : Type 0
25constructor NaturalDivideSucceeded
26field unrestricted naturalDivideValue : Nat
27constructor NaturalDivideFailed
28field unrestricted naturalDivideError : (family NaturalArithmeticErrorCode)
29
30end-family
31
32def naturalArithmeticErrorCodeBytes =
33 (lambda unrestricted code : (family NaturalArithmeticErrorCode) .
34 eliminate
35 NaturalArithmeticErrorCode
36 (lambda unrestricted current : (family NaturalArithmeticErrorCode) . Bytes)
37 code
38 (branch NaturalArithmeticModuloByZero . b"ALPHA-STD-001")
39 (branch NaturalArithmeticDivideByZero . b"ALPHA-STD-002"))
40
41def naturalSelect =
42 (lambda unrestricted condition : Nat .
43 unrestricted whenTrue : Nat .
44 unrestricted whenFalse : Nat .
45 nat-eliminate
46 (lambda unrestricted current : Nat . Nat)
47 whenFalse
48 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . whenTrue)
49 condition)
50
51def naturalMinimum =
52 (lambda unrestricted left : Nat . unrestricted right : Nat .
53 nat-eliminate
54 (lambda unrestricted current : Nat . Nat)
55 right
56 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . left)
57 (nat-less-than left right))
58
59-- Zero tests and ordering go through the ONE constant-time primitive the
60-- runtime offers on naturals, `nat-less-than`. A `nat-eliminate` over a
61-- natural is executed as a loop over its whole magnitude (measured
62-- 2026-09-16: asking whether the length of a 1 MiB string is zero cost 68 ms
63-- per call, about 65 ns per unit; the same question through nat-less-than
64-- costs nothing measurable), so no comparison may recurse on the value it
65-- compares. The 0/1 flag nat-less-than returns is the only thing eliminated.
66def naturalNonzero =
67 (lambda unrestricted value : Nat . nat-less-than 0 value)
68
69def naturalIsZero =
70 (lambda unrestricted value : Nat .
71 nat-eliminate
72 (lambda unrestricted current : Nat . Nat)
73 1
74 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . 0)
75 (nat-less-than 0 value))
76
77-- The flag operations below are written on the primitives themselves, not
78-- on one another: a realization calls them millions of times, and each call
79-- of one helper from another costs the machine an application chain (an
80-- equality through naturalAnd, naturalIsZero and naturalSelect took 44 steps
81-- where these take a handful; they were three fifths of realizing a tiled
82-- product). Each eliminates only a 0/1 flag from nat-less-than.
83def naturalAnd =
84 (lambda unrestricted left : Nat . unrestricted right : Nat .
85 nat-eliminate
86 (lambda unrestricted current : Nat . Nat)
87 0
88 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . nat-less-than 0 right)
89 (nat-less-than 0 left))
90
91def naturalOr =
92 (lambda unrestricted left : Nat . unrestricted right : Nat .
93 nat-eliminate
94 (lambda unrestricted current : Nat . Nat)
95 (nat-less-than 0 right)
96 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . 1)
97 (nat-less-than 0 left))
98
99-- D21: the arithmetic below is the language's own (`nat-add` and friends run in
100-- one machine operation at run time and fold at compile time); the folds that
101-- counted step by step are gone. Semantics are unchanged: subtraction
102-- saturates at zero, x / 0 = 0, x mod 0 = x.
103def naturalAdd =
104 (lambda unrestricted left : Nat . unrestricted right : Nat . nat-add left right)
105
106def naturalPredecessor =
107 (lambda unrestricted value : Nat . nat-subtract value 1)
108
109def naturalSaturatingSubtract =
110 (lambda unrestricted left : Nat . unrestricted right : Nat . nat-subtract left right)
111
112def naturalMultiply =
113 (lambda unrestricted left : Nat . unrestricted right : Nat . nat-multiply left right)
114
115def naturalEqual =
116 (lambda unrestricted left : Nat . unrestricted right : Nat .
117 nat-eliminate
118 (lambda unrestricted current : Nat . Nat)
119 (nat-eliminate
120 (lambda unrestricted current : Nat . Nat)
121 1
122 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . 0)
123 (nat-less-than left right))
124 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . 0)
125 (nat-less-than right left))
126
127def naturalLess =
128 (lambda unrestricted left : Nat . unrestricted right : Nat . nat-less-than left right)
129
130def naturalLessOrEqual =
131 (lambda unrestricted left : Nat . unrestricted right : Nat .
132 nat-eliminate
133 (lambda unrestricted current : Nat . Nat)
134 1
135 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . 0)
136 (nat-less-than right left))
137
138def naturalModuloUnchecked =
139 (lambda unrestricted value : Nat . unrestricted divisor : Nat . nat-modulo value divisor)
140
141def naturalModulo =
142 (lambda unrestricted value : Nat . unrestricted divisor : Nat .
143 nat-eliminate
144 (lambda unrestricted current : Nat . family NaturalModuloResult)
145 (constructor
146 NaturalModuloResult
147 NaturalModuloFailed
148 (constructor NaturalArithmeticErrorCode NaturalArithmeticModuloByZero))
149 (lambda unrestricted predecessor : Nat .
150 unrestricted induction : (family NaturalModuloResult) .
151 constructor
152 NaturalModuloResult
153 NaturalModuloSucceeded
154 (naturalModuloUnchecked value divisor))
155 divisor)
156
157def naturalDivisionStep =
158 (lambda unrestricted divisor : Nat . unrestricted state : (family NaturalDivisionState) .
159 eliminate
160 NaturalDivisionState
161 (lambda unrestricted current : (family NaturalDivisionState) . family NaturalDivisionState)
162 state
163 (branch
164 NaturalDivisionStateValue
165 remainder
166 quotient
167 .
168 app
169 (lambda unrestricted incremented : Nat .
170 nat-eliminate
171 (lambda unrestricted condition : Nat . family NaturalDivisionState)
172 (constructor NaturalDivisionState NaturalDivisionStateValue incremented quotient)
173 (lambda unrestricted predecessor : Nat .
174 unrestricted induction : (family NaturalDivisionState) .
175 constructor NaturalDivisionState NaturalDivisionStateValue 0 (succ quotient))
176 (naturalEqual incremented divisor))
177 (succ remainder)))
178
179def naturalDivisionState =
180 (lambda unrestricted value : Nat . unrestricted divisor : Nat .
181 nat-eliminate
182 (lambda unrestricted current : Nat . family NaturalDivisionState)
183 (constructor NaturalDivisionState NaturalDivisionStateValue 0 0)
184 (lambda unrestricted predecessor : Nat .
185 unrestricted induction : (family NaturalDivisionState) .
186 naturalDivisionStep divisor induction)
187 value)
188
189def naturalDivideUnchecked =
190 (lambda unrestricted value : Nat . unrestricted divisor : Nat . nat-divide value divisor)
191
192def naturalDivide =
193 (lambda unrestricted value : Nat . unrestricted divisor : Nat .
194 nat-eliminate
195 (lambda unrestricted current : Nat . family NaturalDivideResult)
196 (constructor
197 NaturalDivideResult
198 NaturalDivideFailed
199 (constructor NaturalArithmeticErrorCode NaturalArithmeticDivideByZero))
200 (lambda unrestricted predecessor : Nat .
201 unrestricted induction : (family NaturalDivideResult) .
202 constructor
203 NaturalDivideResult
204 NaturalDivideSucceeded
205 (naturalDivideUnchecked value divisor))
206 divisor)
207
208def naturalPowerOfTwo =
209 (lambda unrestricted exponent : Nat .
210 nat-eliminate
211 (lambda unrestricted current : Nat . Nat)
212 1
213 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat .
214 naturalAdd induction induction)
215 exponent)
216
217-- 256, by doubling: the divisor behind "fits in N bytes".
218def naturalTwoHundredFiftySix =
219 (naturalPowerOfTwo 8)
220
221-- "value < 256^byteCount" WITHOUT ever building 256^byteCount: divide by 256
222-- byteCount times and ask whether anything is left.
223--
224-- A runtime natural costs about 164 bytes and 300 ns PER UNIT of its magnitude
225-- (measured 2026-09-16: 2^20 takes 0.8 s and 195 MB, 2^24 takes 5 s and
226-- 2.75 GB, and 2^32 cannot be built at all -- the image exits 125). So a bound
227-- such as 2^32 must never be materialised, and `naturalLess x (naturalPowerOfTwo
228-- 32)` is not a comparison but an out-of-memory. This is how "fits in a 32-bit
229-- field" is asked instead; it costs about value/256 steps.
230def naturalBelowBytePower =
231 (lambda unrestricted byteCount : Nat . unrestricted value : Nat .
232 naturalIsZero
233 (nat-eliminate
234 (lambda unrestricted current : Nat . Nat)
235 value
236 (lambda unrestricted predecessor : Nat . unrestricted quotient : Nat .
237 naturalDivideUnchecked quotient naturalTwoHundredFiftySix)
238 byteCount))
239
240-- "value <= 256^byteCount", as (value - 1) < 256^byteCount with the saturating
241-- predecessor: 0 qualifies, 256^byteCount itself qualifies, one more does not.
242-- Callers that wrote `naturalLessOrEqual x bound` keep exactly that bound.
243def naturalAtMostBytePower =
244 (lambda unrestricted byteCount : Nat . unrestricted value : Nat .
245 naturalBelowBytePower byteCount (naturalPredecessor value))
246
247-- value < 2^32: it fits a 32-bit word
248def naturalFitsWord32 =
249 (lambda unrestricted value : Nat . naturalBelowBytePower 4 value)
250
251-- "value < 2^bits" WITHOUT building 2^bits: halve bits times and ask whether
252-- anything is left. The general form of naturalBelowBytePower (a byte is eight
253-- halvings); it is what a limit such as "fits int64" (bits = 63) or "at most
254-- 16 MiB of input" (bits = 24) must use at runtime, since 2^24 alone costs
255-- 2.75 GB to materialise and 2^63 cannot be materialised at all.
256def naturalBelowTwoPower =
257 (lambda unrestricted bits : Nat . unrestricted value : Nat .
258 naturalIsZero
259 (nat-eliminate
260 (lambda unrestricted current : Nat . Nat)
261 value
262 (lambda unrestricted predecessor : Nat . unrestricted quotient : Nat .
263 naturalDivideUnchecked quotient 2)
264 bits))
265
266-- value <= 2^32
267def naturalAtMostTwoPower32 =
268 (lambda unrestricted value : Nat . naturalAtMostBytePower 4 value)
269
270-- How many of f 0, f 1, ..., f (count - 1) are zero: a plain fold over a
271-- closed count, so the checker runs it as a strict loop -- one cell at a
272-- time, each forgotten once counted. (The first formulation nested each
273-- cell's select inside the previous one; a verdict of 40 cells that each run
274-- a program kept every earlier cell alive: 51 s against 7.6 s, two thirds of
275-- it garbage collection.)
276def naturalFailuresBelow =
277 (lambda unrestricted count : Nat . unrestricted f : (pi unrestricted index : Nat . Nat) .
278 nat-eliminate
279 (lambda unrestricted current : Nat . Nat)
280 0
281 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat .
282 naturalAdd (naturalIsZero (f predecessor)) induction)
283 count)
284
285-- 1 when f 0, f 1, ..., f (count - 1) are all nonzero, else 0: a bounded
286-- universal verdict the checker can compute. With a statement for every
287-- f (count + b), Std.Equality.stdNaturalAllBelowSound turns it into a
288-- statement for every natural -- a finite region decided by computation, the
289-- rest by an argument over an open offset.
290def naturalAllBelow =
291 (lambda unrestricted count : Nat . unrestricted f : (pi unrestricted index : Nat . Nat) .
292 naturalIsZero (naturalFailuresBelow count f))
293
294-- The decimal digits of a natural, most significant first ("0" for zero):
295-- the text form of a counter, a sequence number or a tick in an AOS-JSON/1
296-- stream (Observe.Value), and of a token cache path's ranges
297-- (Data.TokenCachePath). `fuel` is the caller's bound on the number of
298-- digits LESS ONE: a natural with more than `fuel + 1` digits keeps only its
299-- last `fuel + 1`, so every caller names a bound its values cannot exceed
300-- (a u64 has at most 20 digits).
301def naturalDecimalBuilder =
302 (lambda unrestricted fuel : Nat .
303 nat-eliminate
304 (lambda unrestricted current : Nat . pi unrestricted value : Nat . BytesBuilder)
305 (lambda unrestricted value : Nat .
306 then bytes-builder-chunk bytes nat-to-byte (naturalAdd 48) (naturalModuloUnchecked value) 10)
307 (lambda unrestricted predecessor : Nat .
308 unrestricted induction : (pi unrestricted value : Nat . BytesBuilder) .
309 unrestricted value : Nat .
310 let unrestricted quotient =
311 (naturalDivideUnchecked value 10)
312 in
313 nat-eliminate
314 (lambda unrestricted nonzero : Nat . BytesBuilder)
315 (then bytes-builder-chunk
316 bytes
317 nat-to-byte
318 (naturalAdd 48)
319 (naturalModuloUnchecked value)
320 10)
321 (lambda unrestricted quotientPredecessor : Nat .
322 unrestricted quotientInduction : BytesBuilder .
323 then (bytes-builder-append (induction quotient))
324 bytes-builder-chunk
325 bytes
326 nat-to-byte
327 (naturalAdd 48)
328 (naturalModuloUnchecked value)
329 10)
330 (naturalNonzero quotient))
331 fuel)
332
333def naturalDecimalBytesWithin =
334 (lambda unrestricted fuel : Nat . unrestricted value : Nat .
335 bytes-builder-build (naturalDecimalBuilder fuel value))The compiler supplied declaration spans and resolved links from this source snapshot. This page does not assert that this file belongs to a checked closure.