Native natural-number math

native.tri provides binary natural-number arithmetic and ASCII classifiers. The source lexer and executable-digest validator use its canonical-number fast path. Checked public arithmetic in base.tri validates inputs before delegating to these algorithms. The implementation uses ordinary Tree Calculus terms and stable direct recursion.

Input/output contract

All numeric arguments must be canonical natural-number trees:

• Zero is Leaf (t).
• A positive number is Fork bit rest, least-significant bit first; bit is exactly Leaf (0) or Stem Leaf (1), and the highest represented bit is 1.
• Outputs use the same canonical encoding, with no redundant high zero bits.
• Booleans are exactly Leaf (false) or Stem Leaf (true).

There is no validation or contract traversal on this fast path. Noncanonical numbers, arbitrary trees, and divergent inputs are outside its contract; their results and termination are unspecified. Use validation at an appropriate boundary when inputs are not trusted.

equal is numeric equality on this domain, not general tree equality. Existing base.equal? remains unchanged and available for arbitrary trees.

Exported interface

Exports	Meaning
compare a b	Leaf = equal; Stem Leaf = less; Fork Leaf Leaf = greater. These are ordering tags, not numeric -1/0/1.
equal, lt, lte, gt, gte	Two-argument numeric predicates.
inRange value low high	Inclusive bounds; false when low > high.
minimum a b, maximum a b	Canonical selected operand.
zero value, odd value, even value	Unary predicates.
successor value, predecessor value	Increment/decrement; predecessor of zero is zero.
add a b, subtract a b	Sum and subtraction saturating at zero.
multiply a b	Product.
divMod a b	Pair of quotient and remainder; a zero divisor yields (0, a).
quotient a b, remainder a b	Projections of divMod.
power a b	Exponentiation by squaring; 0^0 is 1.
decimal value digit	10 * value + digit; digit must be 0..9, not an ASCII character.
ascii value	Membership in 0..127.
digit value	ASCII decimal digit, 48..57.
letter value	ASCII A..Z or a..z.
lowerHex value	ASCII 0..9 or a..f (not A..F).
printable value	ASCII 32..126, excluding DEL.

Use a namespace rather than importing everything over the prelude. In a native flat workspace, put this source at native.tri, then declare sources before uses:

!import native as N
!export main
main input = N.add input 1

Select a retained compiler artifact explicitly, as described in the portable tool guide. Internal helpers are private. The test runner prepares such a workspace automatically.

Implementation and limits

Comparison walks binary tails, allowing the more significant differing bit to win. Equality stops at the first differing low bit. Addition uses carry bits; subtraction first checks ordering, then propagates borrow and removes high zero bits. Multiplication uses binary shift/add; decimal accumulation uses shifts and addition. digit, letter, and lowerHex classify fixed bit slices instead of composing full range comparisons. Digit recognition checks a high part of 3 and a low nibble in 0..9. Letter recognition ignores the ASCII case bit and checks a low five-bit value in 1..26; lowercase hex letters have a high part of 12 and low three bits in 1..6. High-part equality rejects larger naturals, including Unicode characters outside ASCII. ascii and printable retain binary comparisons. These shortcuts rely on the canonical-natural contract; they need not preserve malformed-tree results or demand of irrelevant bits.

Comparison, addition, and subtraction walk binary digits rather than counting to the numeric value. Multiplication uses shift/add; division performs binary long division.

The raw zero-divisor policy keeps divMod total on canonical naturals. Checked public division rejects zero with the "non-zero" contract instead. Choose the appropriate boundary for the caller.

Validation

The numeric checks use independent integer, Boolean, and complete-tree expectations. Candidate preparation and fixture publication are separate from reference-artifact tests. Measure selected workloads with a recorded compiler; changing function trees can affect both performance and intensional observations.