1	# Exact signed decimals: a BigInt coefficient over a power of ten.
2	import Base
3	import ./bigint.bend as Big
4	
5	# The value is unscaled / 10^scale. Scale is kept as written, so 1.50 stays
6	# 1.50 (money keeps its cents); cmp is numeric, and normalize strips trailing
7	# zeros. No operation rounds: an inexact request answers None.
8	type Decimal is Data:
9	  Decimal{unscaled: Big.BigInt, scale: Nat}
10	
11	def Decimal.zero() -> Decimal:
12	  Decimal{Big.BigInt.zero(), 0n}
13	
14	def Decimal.pow10(n: Nat) -> Big.BigInt:
15	  Big.BigInt.pow(Big.BigInt.from_u32(10), n)
16	
17	# u * 10^k, without a multiply when k is 0.
18	def Decimal.up(u: Big.BigInt, k: Nat) -> Big.BigInt:
19	  match k:
20	    case 0n:
21	      u
22	    case 1n+p:
23	      Big.BigInt.mul(u, Decimal.pow10(1n+p))
24	
25	def Decimal.neg(d: Decimal) -> Decimal:
26	  match d:
27	    case Decimal{u, s}:
28	      Decimal{Big.BigInt.neg(u), s}
29	
30	def Decimal.abs(d: Decimal) -> Decimal:
31	  match d:
32	    case Decimal{u, s}:
33	      Decimal{Big.BigInt.abs(u), s}
34	
35	def Decimal.is_zero(d: Decimal) -> Bool:
36	  match d:
37	    case Decimal{u, s}:
38	      Big.BigInt.is_zero(u)
39	
40	def Decimal.add(a: Decimal, b: Decimal) -> Decimal:
41	  match a b:
42	    case Decimal{ua, +sa} Decimal{ub, +sb}:
43	      Decimal{Big.BigInt.add(Decimal.up(ua, Nat.sub(sb, sa)),
44	        Decimal.up(ub, Nat.sub(sa, sb))), Nat.max(sa, sb)}
45	
46	def Decimal.sub(a: Decimal, b: Decimal) -> Decimal:
47	  Decimal.add(a, Decimal.neg(b))
48	
49	def Decimal.mul(a: Decimal, b: Decimal) -> Decimal:
50	  match a b:
51	    case Decimal{ua, sa} Decimal{ub, sb}:
52	      Decimal{Big.BigInt.mul(ua, ub), Nat.add(sa, sb)}
53	
54	def Decimal.cmp(a: Decimal, b: Decimal) -> Cmp:
55	  match a b:
56	    case Decimal{ua, +sa} Decimal{ub, +sb}:
57	      Big.BigInt.cmp(Decimal.up(ua, Nat.sub(sb, sa)),
58	        Decimal.up(ub, Nat.sub(sa, sb)))
59	
60	# The quotient of a division whose divisor is known to be nonzero.
61	def Decimal.quot(m: Maybe<&1, Big.BigInt & Big.BigInt>) -> Big.BigInt:
62	  match m:
63	    case Some{(q, r)}:
64	      q
65	    case None{}:
66	      Big.BigInt.zero()
67	
68	# (remainder is zero, quotient) of u / k, for a nonzero k.
69	def Decimal.divk.m(m: Maybe<&1, Big.BigInt & Big.BigInt>) -> Bool & Big.BigInt:
70	  match m:
71	    case Some{(q, r)}:
72	      (Big.BigInt.is_zero(r), q)
73	    case None{}:
74	      (False{}, Big.BigInt.zero())
75	
76	def Decimal.divk(u: Big.BigInt, k: U32) -> Bool & Big.BigInt:
77	  Decimal.divk.m(Big.BigInt.divmod(u, Big.BigInt.from_u32(k)))
78	
79	def Decimal.is_one(u: Big.BigInt) -> Bool:
80	  Cmp.is_eq(Big.BigInt.cmp(u, Big.BigInt.one()))
81	
82	def Decimal.lowest.fix(neg: Bool, n: Big.BigInt, d: Big.BigInt) ->
83	  Big.BigInt & Big.BigInt:
84	  match neg:
85	    case True{}:
86	      (Big.BigInt.neg(n), Big.BigInt.neg(d))
87	    case False{}:
88	      (n, d)
89	
90	def Decimal.lowest.den(n: Big.BigInt, +d: Big.BigInt) -> Big.BigInt & Big.BigInt:
91	  Decimal.lowest.fix(Cmp.is_lt(Big.BigInt.cmp(d, Big.BigInt.zero())), n, d)
92	
93	def Decimal.lowest.by(n: Big.BigInt, d: Big.BigInt, +g: Big.BigInt) ->
94	  Big.BigInt & Big.BigInt:
95	  Decimal.lowest.den(Decimal.quot(Big.BigInt.divmod(n, g)),
96	    Decimal.quot(Big.BigInt.divmod(d, g)))
97	
98	# n / d in lowest terms with a positive denominator; d must be nonzero.
99	def Decimal.lowest(+n: Big.BigInt, +d: Big.BigInt) -> Big.BigInt & Big.BigInt:
100	  Decimal.lowest.by(n, d, Big.BigInt.gcd(n, d))
101	
102	# Each step divides d by 2 or 5 and scales n to match, so a d of D digits
103	# needs fewer than 4D steps; f is that bound.
104	def Decimal.frac.go(f: Nat, n: Big.BigInt, k: Nat, one: Bool,
105	  t2: Bool & Big.BigInt, t5: Bool & Big.BigInt) -> Maybe<&2, Decimal>:
106	  match f:
107	    case 0n:
108	      None{}
109	    case 1n+g:
110	      match one:
111	        case True{}:
112	          Some{Decimal{n, k}}
113	        case False{}:
114	          (z2, q2) = t2
115	          match z2:
116	            case True{}:
117	              +d = {q2 : Big.BigInt}
118	              Decimal.frac.go(g, Big.BigInt.mul(n, Big.BigInt.from_u32(5)),
119	                1n+k, Decimal.is_one(d), Decimal.divk(d, 2),
120	                Decimal.divk(d, 5))
121	            case False{}:
122	              (z5, q5) = t5
123	              match z5:
124	                case True{}:
125	                  +d = {q5 : Big.BigInt}
126	                  Decimal.frac.go(g, Big.BigInt.mul(n, Big.BigInt.from_u32(2)),
127	                    1n+k, Decimal.is_one(d), Decimal.divk(d, 2),
128	                    Decimal.divk(d, 5))
129	                case False{}:
130	                  None{}
131	
132	def Decimal.frac.run(p: Big.BigInt & Big.BigInt) -> Maybe<&2, Decimal>:
133	  (n, d) = p
134	  +e = {d : Big.BigInt}
135	  Decimal.frac.go(
136	    (4n * String.length(Big.BigInt.show(e)) + 1n : Nat),
137	    n, 0n, Decimal.is_one(e), Decimal.divk(e, 2), Decimal.divk(e, 5))
138	
139	def Decimal.frac.if(z: Bool, n: Big.BigInt, d: Big.BigInt) ->
140	  Maybe<&2, Decimal>:
141	  match z:
142	    case True{}:
143	      None{}
144	    case False{}:
145	      Decimal.frac.run(Decimal.lowest(n, d))
146	
147	# n / d at the smallest exact scale, or None when d is zero or the decimal
148	# expansion does not terminate (d has a prime factor other than 2 and 5).
149	def Decimal.from_fraction(n: Big.BigInt, +d: Big.BigInt) -> Maybe<&2, Decimal>:
150	  Decimal.frac.if(Big.BigInt.is_zero(d), n, d)
151	
152	# a / b exactly, at the smallest scale that holds it; None for a zero
153	# divisor or a repeating quotient (use Rational for those).
154	def Decimal.div_exact(a: Decimal, b: Decimal) -> Maybe<&2, Decimal>:
155	  match a b:
156	    case Decimal{ua, sa} Decimal{ub, sb}:
157	      Decimal.from_fraction(Big.BigInt.mul(ua, Decimal.pow10(sb)),
158	        Big.BigInt.mul(ub, Decimal.pow10(sa)))
159	
160	def Decimal.normalize.go(s: Nat, u: Big.BigInt, qr: Bool & Big.BigInt) ->
161	  Decimal:
162	  match s:
163	    case 0n:
164	      Decimal{u, 0n}
165	    case 1n+p:
166	      (z, q) = qr
167	      match z:
168	        case True{}:
169	          +v = {q : Big.BigInt}
170	          Decimal.normalize.go(p, v, Decimal.divk(v, 10))
171	        case False{}:
172	          Decimal{u, 1n+p}
173	
174	# The same value at the smallest scale: 1.500 is 1.5, 0.00 is 0.
175	def Decimal.normalize(d: Decimal) -> Decimal:
176	  match d:
177	    case Decimal{+u, s}:
178	      Decimal.normalize.go(s, u, Decimal.divk(u, 10))
179	
180	def Decimal.rescale.keep(z: Bool, q: Big.BigInt, t: Nat) -> Maybe<&2, Decimal>:
181	  match z:
182	    case True{}:
183	      Some{Decimal{q, t}}
184	    case False{}:
185	      None{}
186	
187	def Decimal.rescale.cut(t: Nat, m: Maybe<&1, Big.BigInt & Big.BigInt>) ->
188	  Maybe<&2, Decimal>:
189	  match m:
190	    case Some{(q, r)}:
191	      Decimal.rescale.keep(Big.BigInt.is_zero(r), q, t)
192	    case None{}:
193	      None{}
194	
195	def Decimal.rescale.if(up: Bool, u: Big.BigInt, +s: Nat, +t: Nat) ->
196	  Maybe<&2, Decimal>:
197	  match up:
198	    case True{}:
199	      Some{Decimal{Decimal.up(u, Nat.sub(t, s)), t}}
200	    case False{}:
201	      Decimal.rescale.cut(t, Big.BigInt.divmod(u, Decimal.pow10(Nat.sub(s, t))))
202	
203	# The same value at scale t, or None when that would drop a nonzero digit:
204	# rescale(1.5, 2n) is 1.50; rescale(1.25, 1n) is None, never 1.2 or 1.3.
205	def Decimal.rescale(d: Decimal, +t: Nat) -> Maybe<&2, Decimal>:
206	  match d:
207	    case Decimal{u, +s}:
208	      Decimal.rescale.if(Nat.is_le(s, t), u, s, t)
209	
210	def Decimal.show.split(+s: Nat, +ds: String) -> String:
211	  +i = {Nat.sub(String.length(ds), s) : Nat}
212	  String.append(String.take(ds, i), SCon{Chr{46}, String.drop(ds, i)})
213	
214	# Digits with a point s places from the right, zero-padded to one whole digit.
215	def Decimal.show.point(+s: Nat, +ds: String) -> String:
216	  match s:
217	    case 0n:
218	      ds
219	    case 1n+p:
220	      Decimal.show.split(1n+p, String.append(
221	        String.repeat("0", Nat.sub(2n+p, String.length(ds))), ds))
222	
223	def Decimal.show.sign(neg: Bool, body: String) -> String:
224	  match neg:
225	    case True{}:
226	      SCon{Chr{45}, body}
227	    case False{}:
228	      body
229	
230	# Plain notation with every scale digit: -12.50, 0.001, 7. Never an exponent.
231	def Decimal.show(d: Decimal) -> String:
232	  match d:
233	    case Decimal{+u, s}:
234	      Decimal.show.sign(Cmp.is_lt(Big.BigInt.cmp(u, Big.BigInt.zero())),
235	        Decimal.show.point(s, Big.BigInt.show(Big.BigInt.abs(u))))
236	
237	# A character of a number.
238	type Class is Data:
239	  Digit{code: U32}
240	  Minus{}
241	  Plus{}
242	  Point{}
243	  Expo{}
244	  Other{}
245	
246	def Decimal.class.sym(minus: Bool, plus: Bool, point: Bool, expo: Bool) ->
247	  Class:
248	  match minus:
249	    case True{}:
250	      Minus{}
251	    case False{}:
252	      match plus:
253	        case True{}:
254	          Plus{}
255	        case False{}:
256	          match point:
257	            case True{}:
258	              Point{}
259	            case False{}:
260	              match expo:
261	                case True{}:
262	                  Expo{}
263	                case False{}:
264	                  Other{}
265	
266	def Decimal.class.if(digit: Bool, +c: U32) -> Class:
267	  match digit:
268	    case True{}:
269	      Digit{c}
270	    case False{}:
271	      Decimal.class.sym(U32.is_eq(c, 45), U32.is_eq(c, 43), U32.is_eq(c, 46),
272	        Bool.or(U32.is_eq(c, 101), U32.is_eq(c, 69)))
273	
274	def Decimal.class(+c: U32) -> Class:
275	  Decimal.class.if(Bool.and(U32.is_ge(c, 48), U32.is_le(c, 57)), c)
276	
277	# Where the reader is. ds holds the coefficient's digits, last first, without
278	# leading zeros; sc counts fraction digits; e is the exponent's magnitude.
279	type Scan is Data:
280	  Bad{}
281	  Begin{}
282	  Signed{neg: Bool}
283	  Whole{neg: Bool, ds: String}
284	  Dot{neg: Bool, ds: String}
285	  Frac{neg: Bool, ds: String, sc: Nat}
286	  Exp{neg: Bool, ds: String, sc: Nat}
287	  ExpSigned{neg: Bool, ds: String, sc: Nat, eneg: Bool}
288	  ExpDigits{neg: Bool, ds: String, sc: Nat, eneg: Bool, e: U32}
289	
290	def Decimal.read.lead(zero: Bool, c: U32) -> String:
291	  match zero:
292	    case True{}:
293	      SNil{}
294	    case False{}:
295	      SCon{Chr{c}, SNil{}}
296	
297	def Decimal.read.push(+c: U32, ds: String) -> String:
298	  match ds:
299	    case SNil{}:
300	      Decimal.read.lead(U32.is_eq(c, 48), c)
301	    case SCon{h, t}:
302	      SCon{Chr{c}, SCon{h, t}}
303	
304	# ponytail: exponents past 100000 in magnitude are refused, since 1e100000
305	# materializes 100000 digits; raise the bound if a caller needs more.
306	def Decimal.read.exp(big: Bool, neg: Bool, ds: String, sc: Nat, eneg: Bool,
307	  e: U32) -> Scan:
308	  match big:
309	    case True{}:
310	      Bad{}
311	    case False{}:
312	      ExpDigits{neg, ds, sc, eneg, e}
313	
314	def Decimal.read.step(st: Scan, cl: Class) -> Scan:
315	  match st:
316	    case Begin{}:
317	      match cl:
318	        case Digit{c}:
319	          Whole{False{}, Decimal.read.push(c, SNil{})}
320	        case Minus{}:
321	          Signed{True{}}
322	        case Plus{}:
323	          Signed{False{}}
324	        case _:
325	          Bad{}
326	    case Signed{neg}:
327	      match cl:
328	        case Digit{c}:
329	          Whole{neg, Decimal.read.push(c, SNil{})}
330	        case _:
331	          Bad{}
332	    case Whole{neg, ds}:
333	      match cl:
334	        case Digit{c}:
335	          Whole{neg, Decimal.read.push(c, ds)}
336	        case Point{}:
337	          Dot{neg, ds}
338	        case Expo{}:
339	          Exp{neg, ds, 0n}
340	        case _:
341	          Bad{}
342	    case Dot{neg, ds}:
343	      match cl:
344	        case Digit{c}:
345	          Frac{neg, Decimal.read.push(c, ds), 1n}
346	        case _:
347	          Bad{}
348	    case Frac{neg, ds, sc}:
349	      match cl:
350	        case Digit{c}:
351	          Frac{neg, Decimal.read.push(c, ds), 1n+sc}
352	        case Expo{}:
353	          Exp{neg, ds, sc}
354	        case _:
355	          Bad{}
356	    case Exp{neg, ds, sc}:
357	      match cl:
358	        case Digit{c}:
359	          ExpDigits{neg, ds, sc, False{}, U32.sub(c, 48)}
360	        case Minus{}:
361	          ExpSigned{neg, ds, sc, True{}}
362	        case Plus{}:
363	          ExpSigned{neg, ds, sc, False{}}
364	        case _:
365	          Bad{}
366	    case ExpSigned{neg, ds, sc, eneg}:
367	      match cl:
368	        case Digit{c}:
369	          ExpDigits{neg, ds, sc, eneg, U32.sub(c, 48)}
370	        case _:
371	          Bad{}
372	    case ExpDigits{neg, ds, sc, eneg, e}:
373	      match cl:
374	        case Digit{c}:
375	          +x = (e * 10 + c - 48 : U32)
376	          Decimal.read.exp(U32.is_gt(x, 100000), neg, ds, sc, eneg, x)
377	        case _:
378	          Bad{}
379	    case _:
380	      Bad{}
381	
382	def Decimal.read.go(s: String, st: Scan) -> Scan:
383	  match s:
384	    case SNil{}:
385	      st
386	    case SCon{Chr{x}, t}:
387	      Decimal.read.go(t, Decimal.read.step(st, Decimal.class(x)))
388	
389	def Decimal.read.abs(m: Maybe<&2, Big.BigInt>) -> Big.BigInt:
390	  match m:
391	    case Some{v}:
392	      v
393	    case None{}:
394	      Big.BigInt.zero()
395	
396	# The coefficient; ds holds only digits, so read cannot fail.
397	def Decimal.read.coef(neg: Bool, ds: String) -> Big.BigInt:
398	  match neg:
399	    case True{}:
400	      Big.BigInt.neg(Decimal.read.abs(Big.BigInt.read(String.reverse(ds))))
401	    case False{}:
402	      Decimal.read.abs(Big.BigInt.read(String.reverse(ds)))
403	
404	def Decimal.read.digits(neg: Bool, ds: String) -> Big.BigInt:
405	  match ds:
406	    case SNil{}:
407	      Big.BigInt.zero()
408	    case SCon{h, t}:
409	      Decimal.read.coef(neg, SCon{h, t})
410	
411	# A negative exponent adds scale; a positive one spends scale, then multiplies.
412	def Decimal.read.shift(u: Big.BigInt, +sc: Nat, eneg: Bool, +e: Nat) -> Decimal:
413	  match eneg:
414	    case True{}:
415	      Decimal{u, Nat.add(sc, e)}
416	    case False{}:
417	      Decimal{Decimal.up(u, Nat.sub(e, sc)), Nat.sub(sc, e)}
418	
419	def Decimal.read.fin(st: Scan) -> Maybe<&2, Decimal>:
420	  match st:
421	    case Whole{neg, ds}:
422	      Some{Decimal{Decimal.read.digits(neg, ds), 0n}}
423	    case Frac{neg, ds, sc}:
424	      Some{Decimal{Decimal.read.digits(neg, ds), sc}}
425	    case ExpDigits{neg, ds, sc, eneg, e}:
426	      Some{Decimal.read.shift(Decimal.read.digits(neg, ds), sc, eneg,
427	        U32.to_nat(e))}
428	    case _:
429	      None{}
430	
431	# [+-]digits[.digits][(e|E)[+-]digits], a superset of JSON's number grammar
432	# (it also takes a leading + and leading zeros). The scale is the number of
433	# fraction digits less the exponent, floored at zero: "1.50" has scale 2,
434	# "1.5e1" is 15, "25e-3" is 0.025.
435	def Decimal.read(s: String) -> Maybe<&2, Decimal>:
436	  Decimal.read.fin(Decimal.read.go(s, Begin{}))