src/digits.bend
bend-trace-context@0.1.0.0 · 109 lines · 0 definitions
1# Digit sequences of a known length
2# =================================
3#
4# Digits(n) is a sequence of exactly n hexadecimal digits: the length is part
5# of the type, so a trace ID is a Digits(32n) and a flag byte a Digits(2n).
6# NonZero<n> adds the proof that the digits are not all zero, which W3C 3.2.2.3
7# and 3.2.2.4 require of trace and parent IDs. This module is internal to the
8# package. proofs/digits.bend proves that n digits always format as n
9# characters.
10
11import Base
12import bend-trace-context@0.1.0.0/src/hex.bend as Hex
13
14# The length is part of the type. A Digits(32n) cannot contain 31 or 33 digits.
15# This is the same type-family pattern that Base uses for Word(n).
16#
17# The empty sequence: the only value of Digits(0n).
18type Digits.Nil is Data:
19 DNil{}
20
21# A first digit followed by a sequence of p digits: a value of Digits(1n+p).
22type Digits.Con<-p: Nat> is Data:
23 DCon{head: Hex.Digit, tail: Digits(p)}
24
25# The type of sequences of exactly n digits, computed from n: Digits(0n) is
26# Digits.Nil and Digits(1n+p) is Digits.Con<p>.
27def Digits(n: Nat) -> Data:
28 match n:
29 case 0n:
30 Digits.Nil
31 case 1n+p:
32 Digits.Con<p>
33
34# The n lowercase characters of the digits, in order.
35def Digits.to_string(n: Nat, digits: Digits(n)) -> String:
36 match n:
37 case 0n:
38 ""
39 case 1n+p:
40 match digits:
41 case DCon{head, tail}:
42 SCon{Hex.Digit.to_char(head), Digits.to_string(p, tail)}
43
44# Whether every digit is 0. The empty sequence counts as zero.
45def Digits.is_zero(n: Nat, digits: Digits(n)) -> Bool:
46 match n:
47 case 0n:
48 True{}
49 case 1n+p:
50 match digits:
51 case DCon{head, tail}:
52 Bool.and(Hex.Digit.is_zero(head), Digits.is_zero(p, tail))
53
54# The eight digits of a word, most significant first: the first digit holds
55# bits 31 to 28 and the last digit bits 3 to 0.
56def Digits.of_u32(word: U32) -> Digits(8n):
57 match word:
58 case U32{WCon{b0, WCon{b1, WCon{b2, WCon{b3, WCon{b4, WCon{b5, WCon{b6, WCon{b7, WCon{b8, WCon{b9, WCon{b10, WCon{b11, WCon{b12, WCon{b13, WCon{b14, WCon{b15, WCon{b16, WCon{b17, WCon{b18, WCon{b19, WCon{b20, WCon{b21, WCon{b22, WCon{b23, WCon{b24, WCon{b25, WCon{b26, WCon{b27, WCon{b28, WCon{b29, WCon{b30, WCon{b31, WNil{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}:
59 DCon{Hex.Digit.from_bits(b28, b29, b30, b31), DCon{Hex.Digit.from_bits(b24, b25, b26, b27), DCon{Hex.Digit.from_bits(b20, b21, b22, b23), DCon{Hex.Digit.from_bits(b16, b17, b18, b19), DCon{Hex.Digit.from_bits(b12, b13, b14, b15), DCon{Hex.Digit.from_bits(b8, b9, b10, b11), DCon{Hex.Digit.from_bits(b4, b5, b6, b7), DCon{Hex.Digit.from_bits(b0, b1, b2, b3), DNil{}}}}}}}}}
60
61# The word whose eight digits these are, most significant first.
62def Digits.to_u32(digits: Digits(8n)) -> U32:
63 match digits:
64 case DCon{+d7, DCon{+d6, DCon{+d5, DCon{+d4, DCon{+d3, DCon{+d2, DCon{+d1, DCon{+d0, DNil{}}}}}}}}}:
65 U32{WCon{Hex.Digit.is_odd(d0), WCon{Hex.Digit.has_bit1(d0), WCon{Hex.Digit.has_bit2(d0), WCon{Hex.Digit.has_bit3(d0), WCon{Hex.Digit.is_odd(d1), WCon{Hex.Digit.has_bit1(d1), WCon{Hex.Digit.has_bit2(d1), WCon{Hex.Digit.has_bit3(d1), WCon{Hex.Digit.is_odd(d2), WCon{Hex.Digit.has_bit1(d2), WCon{Hex.Digit.has_bit2(d2), WCon{Hex.Digit.has_bit3(d2), WCon{Hex.Digit.is_odd(d3), WCon{Hex.Digit.has_bit1(d3), WCon{Hex.Digit.has_bit2(d3), WCon{Hex.Digit.has_bit3(d3), WCon{Hex.Digit.is_odd(d4), WCon{Hex.Digit.has_bit1(d4), WCon{Hex.Digit.has_bit2(d4), WCon{Hex.Digit.has_bit3(d4), WCon{Hex.Digit.is_odd(d5), WCon{Hex.Digit.has_bit1(d5), WCon{Hex.Digit.has_bit2(d5), WCon{Hex.Digit.has_bit3(d5), WCon{Hex.Digit.is_odd(d6), WCon{Hex.Digit.has_bit1(d6), WCon{Hex.Digit.has_bit2(d6), WCon{Hex.Digit.has_bit3(d6), WCon{Hex.Digit.is_odd(d7), WCon{Hex.Digit.has_bit1(d7), WCon{Hex.Digit.has_bit2(d7), WCon{Hex.Digit.has_bit3(d7), WNil{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
66
67# The digits of `left` followed by those of `right`: m + n digits. Identifiers
68# are built from source words this way, eight digits per word.
69def Digits.append(m: Nat, -n: Nat, left: Digits(m), right: Digits(n)) -> Digits(Nat.add(m, n)):
70 match m:
71 case 0n:
72 match left:
73 case DNil{}:
74 right
75 case 1n+p:
76 match left:
77 case DCon{head, tail}:
78 DCon{head, Digits.append(p, n, tail, right)}
79
80# n digits that are not all zero. `evidence` is the proof. The equality is
81# checked statically; compiled evidence is a null placeholder. Keeping its
82# binder usable lets later proofs recover and reuse this guarantee. Even direct
83# construction must supply a proof that these digits are not zero.
84type NonZero<-n: Nat> is Data:
85 NonZero{digits: Digits(n), evidence: {Digits.is_zero(n, digits) == False{} : Bool}}
86
87# Carry the equation into the branch: matching status refines its right side.
88# The value is built only in the False case, where the equation is the proof.
89def NonZero.new.checked(-n: Nat, digits: Digits(n), status: Bool,
90 evidence: {Digits.is_zero(n, digits) == status : Bool}) -> Maybe<&2, NonZero<n>>:
91 match status:
92 case True{}:
93 None{}
94 case False{}:
95 Some{NonZero{digits, evidence}}
96
97# Attach the proof that the digits are not all zero, or None when they are.
98def NonZero.new(+n: Nat, +digits: Digits(n)) -> Maybe<&2, NonZero<n>>:
99 NonZero.new.checked(n, digits, Digits.is_zero(n, digits), {==})
100
101# The digits, without their proof.
102def NonZero.digits(-n: Nat, value: NonZero<n>) -> Digits(n):
103 match value:
104 case NonZero{digits, evidence}:
105 digits
106
107# The n lowercase characters of the digits.
108def NonZero.to_string(n: Nat, value: NonZero<n>) -> String:
109 Digits.to_string(n, NonZero.digits(n, value))