prune-lang 0.2.3

Prune is a constraint logic programming language with branching heuristic.
Documentation 
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
145
146
147
148
149
150

datatype Trit where
| T
| O
| I
end

datatype TritList where
| Nil
| Cons(Trit, TritList)
end

function well_formed_sign(xs: TritList) -> Trit
begin
    match xs with
    | Nil => O
    | Cons(T, Nil) => T
    | Cons(I, Nil) => I
    | Cons(_, Cons(head, tail)) => well_formed_sign(Cons(head, tail))
    end
end

function negate(xs: TritList) -> TritList
begin
    match xs with
    | Nil => Nil
    | Cons(T, tail) => Cons(I, negate(tail))
    | Cons(O, tail) => Cons(O, negate(tail))
    | Cons(I, tail) => Cons(T, negate(tail))
    end
end

function shift(xs: TritList) -> TritList
begin
    match xs with
    | Nil => Nil
    | Cons(_, _) => Cons(O, xs)
    end
end

function cons(x: Trit, xs: TritList) -> TritList
begin
    match (x, xs) with
    | (T, xs) => Cons(x, xs)
    | (O, Nil) => Nil
    | (O, Cons(_, _)) => Cons(x, xs)
    | (I, xs) => Cons(x, xs)
    end
end

// adder (ci, x, y) -> (z, co)
function full_adder_1(ci: Trit, x: Trit, y: Trit) -> (Trit, Trit) 
begin
    match (ci, x, y) with
    | (T, T, T) => (O, T)
    | (T, T, O) => (I, T)
    | (T, T, I) => (T, O)
    | (T, O, T) => (I, T)
    | (T, O, O) => (T, O)
    | (T, O, I) => (O, O)
    | (T, I, T) => (T, O)
    | (T, I, O) => (O, O)
    | (T, I, I) => (I, O)
    | (O, T, T) => (I, T)
    | (O, T, O) => (T, O)
    | (O, T, I) => (O, O)
    | (O, O, T) => (T, O)
    | (O, O, O) => (O, O)
    | (O, O, I) => (I, O)
    | (O, I, T) => (O, O)
    | (O, I, O) => (I, O)
    | (O, I, I) => (T, I)
    | (I, T, T) => (T, O)
    | (I, T, O) => (O, O)
    | (I, T, I) => (I, O)
    | (I, O, T) => (O, O)
    | (I, O, O) => (I, O)
    | (I, O, I) => (T, I)
    | (I, I, T) => (I, O)
    | (I, I, O) => (T, I)
    | (I, I, I) => (O, I)
    end
end

function full_adder_n(ci: Trit, xs: TritList, ys: TritList) -> TritList
begin
    match (xs, ys) with
    | (Nil, Nil) => match ci with
        | T => Cons(T, Nil)
        | O => Nil
        | I => Cons(I, Nil)
        end
    | (Cons(x_head, x_tail), Nil) => 
        let (z, co) = full_adder_1(ci, x_head, O);
        cons(z, full_adder_n(co, x_tail, Nil))
    | (Nil, Cons(y_head, y_tail)) => 
        let (z, co) = full_adder_1(ci, O, y_head);
        cons(z, full_adder_n(co, Nil, y_tail))
    | (Cons(x_head, x_tail), Cons(y_head, y_tail)) =>
        let (z, co) = full_adder_1(ci, x_head, y_head);
        cons(z, full_adder_n(co, x_tail, y_tail))
    end
end

function add(xs: TritList, ys: TritList) -> TritList
begin
    full_adder_n(O, xs, ys)
end

function mul(xs: TritList, ys: TritList) -> TritList
begin
    match (xs, ys) with
    | (Nil, Nil) => Nil
    | (Cons(_, _), Nil) => Nil
    | (Nil, Cons(_, _)) => Nil
    | (Cons(x_head, x_tail), Cons(y_head, y_tail)) =>
        let new_tail = mul(x_tail, y_tail);
        match (x_head, y_head) with
        // (3m - 1)(3n - 1) = 9mn - 3(m + n) + 1
        | (T, T) => Cons(I, add(shift(new_tail), negate(add(x_tail, y_tail))))
        // (3m - 1)(3n) = 9mn - 3n
        | (T, O) => shift(add(new_tail, negate(y_tail)))
        // (3m - 1)(3n + 1) = 9mn + 3(m - n) - 1
        | (T, I) => Cons(T, add(shift(new_tail), add(x_tail, negate(y_tail))))
        // (3m)(3n - 1) = 9mn - 3m
        | (O, T) => shift(add(new_tail, negate(x_tail)))
        // (3m)(3n) = 9mn
        | (O, O) => shift(shift(new_tail))
        // (3m)(3n + 1) = 9mn + 3m
        | (O, I) => shift(add(new_tail, x_tail))
        // (3m + 1)(3n - 1) = 9mn + 3(n - m) - 1
        | (I, T) => Cons(T, add(shift(new_tail), add(negate(x_tail), y_tail)))
        // (3m + 1)(3n) = 9mn + 3n
        | (I, O) => shift(add(new_tail, y_tail))
        // (3m + 1)(3n + 1) = 9mn + 3(m + n) + 1
        | (I, I) => Cons(I, add(shift(new_tail), add(x_tail, y_tail)))
        end
    end
end

function pythagorean_triple(xs: TritList, ys: TritList, zs: TritList)
begin
    guard well_formed_sign(xs) = I;
    guard well_formed_sign(ys) = I;
    
    guard zs = Cons(T, Cons(T, Cons(I, Nil)));
    
    guard add(mul(xs, xs), mul(ys, ys)) = mul(zs, zs);
end

query pythagorean_triple(depth_step=20, depth_limit=200, answer_limit=1)