Source/Packages

Std.Natural

packages/foundation/standard/src/Std/Natural.alpha

335 lines48 declarations13.5 KiBSHA-256 0a0af2339e6a

Complete file · line 218

Natural.alpha

Definition view
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.