-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.utlc
144 lines (131 loc) · 5.12 KB
/
main.utlc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
id = x -> x;
$ = x -> x;
const = x -> y -> x;
ignore = x -> y -> y;
comp = f -> g -> x -> f `$ g x;
. = comp;
.2 = f -> g -> x -> y -> f `id g x y;
[BOOLEANS]
true = const;
false = ignore;
! = a -> a false true;
& = a -> b -> a b false;
| = a -> b -> a true b;
!& = ! `.2 &;
!| = ! `.2 |;
xor = a -> b -> (a `| b) `& (a `!& b);
xnor = ! `.2 xor;
b= = xnor;
b!= = xor;
[TUPLES]
, = x -> y -> f -> f x y;
fst = t -> t const;
snd = t -> t ignore;
mapFst = f -> t -> f (fst t) `, snd t;
mapSnd = f -> t -> fst t `, f (snd t);
,= = =a -> =b -> t1 -> t2 -> (fst t1 `=a fst t2) `& (snd t1 `=b snd t2);
,!= = =a -> =b -> ! `.2 ,= =a =b;
[CHURCH ENCODED NATURAL NUMBERS]
0 = f -> x -> x;
1 = ++ 0;
++ = n -> f -> x -> f `n f x;
-- = n -> fst `$ (t -> snd t `, ++ (snd t)) `n (0 `, 0);
+ = n -> m -> ++ `n m;
- = n -> m -> -- `m n;
* = n -> m -> + m `n 0;
/% = n -> m -> (0? (n `- m)) (0 `, n) (mapFst ++ `$ (n `- m) `/% m);
/ = n -> m -> fst `$ n `/% m;
% = n -> m -> snd `$ n `/% m;
^ = n -> m -> * m `n 1;
0? = n -> const false `n true;
factorial = n -> (0? n) 1 (n `* factorial `$ -- n);
2 = ++ 1;
3 = ++ 2;
4 = ++ 3;
5 = ++ 4;
6 = ++ 5;
7 = ++ 6;
8 = ++ 7;
9 = ++ 8;
10 = ++ 9;
n= = a -> b -> (0? `$ a `- b) `& (0? `$ b `- a);
n!= = ! `.2 n=;
[TODO n>, n<, ...]
[MAYBE]
none = f -> x -> x;
some = a -> f -> x -> f a;
none? = m -> m (const false) true;
some? = m -> m (const true) false;
m= = =a -> m1 -> m2 -> m1 (a1 -> m2 (a2 -> a1 `=a a2) false) (none? m2);
m!= = =a -> ! `.2 m= =a;
[SCOTT ENCODED LISTS]
null = f -> x -> x;
: = h -> t -> f -> x -> f h t;
null? = l -> l (const `$ const false) true;
car = l -> l (some `.2 const) none;
cdr = l -> l ignore none;
@ = l -> n -> 0? n (car l) (cdr l `@ -- n);
single = h -> h `: null;
l= = =a -> l1 -> l2 -> l1 (h1 -> t1 -> l2 (h2 -> t2 -> (h1 `=a h2) `& (l= =a t1 t2)) false) (null? l2);
l!= = =a -> ! `.2 l= =a;
l+ = l1 -> l2 -> l1 (h -> t -> h `: t `l+ l2) l2; [concat lists; O(n)]
rev = l -> l (h -> r -> rev r `l+ single h) null; [reverse list; O(n^2)?] [TODO make this into O(n); this is doable if you have an accumulator]
len = l -> l (h -> r -> F++ `$ len r) F0;
map = f -> l -> l (h -> r -> f h `: map f r) null;
[TODO >, <]
l->bl = l -> convElem -> empty -> cons -> l (h -> t -> convElem h `cons l->bl t convElem empty cons) empty;
[FAST NATS - LIST OF BOOLEANS - O(log n)]
[precondition for a lot of this: there is a true at the end of the list]
F0 = null;
F++ = n -> n (h -> r -> h (false `: F++ r) (true `: r)) (single true); [O(log n)]
F0? = null?;
F->n = n -> n (h -> r -> (h 1 0) `+ (2 `* F->n r)) 0; [convert to church encoded zero/succ ints]
n->F = n -> n F++ F0;
F-- = n -> n (h -> r -> h (null? r null (false `: r)) (true `: F-- r)) null; [O(log n)]
F+ = n -> m -> n (hn -> tn -> m (hm -> tm -> (hn `xor hm) `: ((hn `& hm) F++ id `$ tn `F+ tm)) n) m; [O(log (max m n))]
F* = n -> m -> n (hn -> tn -> hn m F0 `F+ tn `F* false `: m) F0; [O(log n * log m)]
F/% = n -> m -> (n `F< m) (F0 `, n) `$ ((n `F- m) `F/% m) (div -> mod -> F++ div `, mod); [at least O(m/n), TODO do this better]
F/ = n -> m -> fst `$ n `F/% m;
F% = n -> m -> snd `$ n `F/% m;
F= = l= b=;
F!= = ! `.2 F=;
F<= = n -> m -> F0? `$ n `F- m;
F>= = n -> m -> m `F<= n;
F< = ! `.2 F>=;
F> = ! `.2 F<=;
Ffactorial = n -> F0? n F1 `$ n `F* Ffactorial `$ F-- n;
[convert fast nat to string]
_F->s = n -> F0? n null `$ (n `F/% F10) (div -> mod -> _F->s div `l+ ((c`0 `F+ mod) `: null)); [TODO use rev instead of l+, because rev will be O(n)]
F->s = n -> F0? n "0" (_F->s n);
[TODO division, modulo]
[SUBTRACTION OF FAST NATS]
00F- = tn -> tm -> (tn `_F- tm) (x -> some `$ F0? x F0 (false `: x)) none;
01F- = tn -> tm -> F-- (false `: tn) `_F- F-- (true `: tm);
10F- = tn -> tm -> (tn `_F- tm) (x -> some `$ true `: x) none;
11F- = tn -> tm -> (tn `_F- tm) (x -> some `$ F0? x F0 (false `: x)) none;
__F- = hn -> tn -> hm -> tm -> (hn (hm 11F- 10F-) (hm 01F- 00F-)) tn tm;
_F- = n -> m -> m (hm -> tm -> n (hn -> tn -> __F- hn tn hm tm) none) (some n);
F- = n -> m -> (n `_F- m) id F0;
[convert to native int; we assume the compiler provides us with zero, succ, plus, and times functions on native ints]
F->bn = n -> zero -> succ -> plus -> times -> n (h -> t -> h (succ zero) zero `plus succ (succ zero) `times F->bn t zero succ plus times) zero;
bn->F = n -> n F0 F++ F+ F*;
F1 = F++ F0;
F2 = F++ F1;
F3 = F++ F2;
F4 = F++ F3;
F5 = F++ F4;
F6 = F++ F5;
F7 = F++ F6;
F8 = F++ F7;
F9 = F++ F8;
F10 = F++ F9;
[BASE STRING CONVERSION]
s->bs = s -> zero -> succ -> plus -> times -> empty -> cons -> l->bl s (n -> F->bn n zero succ plus times) empty cons;
bs->s = s -> map bn->F `$ s null :;
[PARSERS]
[px returns maybe x; px! returns x]
pc = s -> null? s none `$ F!= F1 (len s) none `$ car s;
_pF = s -> s (c -> r -> ((c `F< c`0) `| (c `F> c`9)) none `$ _pF r (n -> some `$ (c `F- c`0) `F+ n `F* F10) none) (some F0);
pF = s -> null? s none (_pF `$ rev s);
main = mainWithInp F10 "startup";
mainWithInp = n -> s -> s->bs (F0? n "q" `$ c`c `: s) `, (mainWithInp (F-- n) `. bs->s);