1 | sclass PhilosophyBot1 { |
2 | srecord LogicRule(lhs, rhs) {} |
3 | srecord And(a, b) {} |
4 | srecord If(condition, thenBlock, elseBlock) {} |
5 | srecord For(var, condition, body) {} |
6 | srecord While(condition, body) {} |
7 | |
8 | replace NPRet with O. // native predicate return type (Bool/SS/null) |
9 | |
10 | // body takes variable mapping |
11 | // body can return |
12 | // Bool => immediate result (ok or fail) |
13 | // SS => variable mapping |
14 | // null => not applicable |
15 | srecord NativePredicate(S head, IF1<SS, NPRet> body) {} |
16 | |
17 | srecord WithAlternative(IF0<O> alternative, O result) {} |
18 | |
19 | replace Proc with L. // procedures are a list of statements |
20 | |
21 | sclass Path { |
22 | new L<Step> steps; |
23 | bool valid = true; |
24 | |
25 | toString { ret stdToString(this); } |
26 | } |
27 | |
28 | abstract sclass Step { |
29 | abstract NPRet alternative(); // perform one backtracking step |
30 | //undo(); |
31 | } |
32 | |
33 | srecord ProcedureToRun(Proc proc, Path path) { |
34 | ProcedureToRun(Proc proc) { this.proc = proc; path = new Path; } |
35 | } |
36 | |
37 | transient S program; |
38 | transient int maxRounds = 1000; |
39 | transient Set<S> facts = linkedCISet(); |
40 | transient Set<S> originalFacts; |
41 | transient new LinkedHashSet<LogicRule> logicRules; |
42 | transient new AllOnAll<LogicRule, S> rulesOnFacts; |
43 | transient new L<ProcedureToRun> proceduresToRun; |
44 | // parsed procedures |
45 | transient long proceduresExecuted; |
46 | transient new L<NativePredicate> nativePredicates; |
47 | transient bool debugNativeCalls = true, debugAllCmds = true; |
48 | transient new L onProcedureEnded; |
49 | |
50 | transient Set<S> vars = litciset("x", "y", "z"); |
51 | |
52 | void addLogicRule(LogicRule rule) { |
53 | if (logicRules.add(rule)) { |
54 | print("Got logic rule", rule); |
55 | rulesOnFacts.newA(rule); // to combine it with the facts |
56 | } |
57 | } |
58 | |
59 | void addFact(S fact) { |
60 | fact = trim(fact); |
61 | if (empty(fact)) ret; |
62 | fact = tok_deRoundBracket(fact); |
63 | // Check if it's a procedure |
64 | LS tok = javaTokWithBrackets(fact); |
65 | if (countCodeTokens(tok) == 2 && eqic(getCodeToken(tok, 0), "proc") |
66 | && isCurlyBracketed(getCodeToken(tok, 1))) pcall { |
67 | // It's a procedure! |
68 | S proc = uncurly_keepSpaces(getCodeToken(tok, 1)); |
69 | if (proceduresToRun.add(new ProcedureToRun(parseProcedure(proc)))) { |
70 | print("Got procedure:"); |
71 | print(indentx("> ", proc)); |
72 | } |
73 | } |
74 | else // It's a fact, not a procedure |
75 | if (facts.add(fact)) { |
76 | print("Got fact: " + fact); |
77 | rulesOnFacts.newB(fact); // to combine it with the rules |
78 | } |
79 | } |
80 | |
81 | void runProcedure(S proc) pcall { |
82 | print("Running procedure."); |
83 | runParsedProcedure(parseProcedure(proc), new Path); |
84 | } |
85 | |
86 | // path contains the previously executed steps with an option to backtrack |
87 | void runParsedProcedure(Proc commands, Path path) { |
88 | ++proceduresExecuted; |
89 | L remainingCommands = cloneLinkedList(commands); |
90 | O cmd; |
91 | while not null (cmd = popFirst(remainingCommands)) { |
92 | if (cmd cast L) continue with runParsedProcedure(cmd, path); |
93 | if (debugAllCmds) |
94 | print("Running cmd: " + sfu(cmd)); |
95 | if cmd is If(O condition, O thenBlock, O elseBlock) { |
96 | O blockToRun = checkCondition(condition) ? thenBlock : elseBlock; |
97 | runParsedProcedure(ll(blockToRun), path); |
98 | } else if cmd is For(O var, O condition, O body) { |
99 | // make a new logic rule and add it |
100 | // assume the variable is globally declared as a variable |
101 | // TODO: path handling |
102 | addLogicRule(new LogicRule(condition, "proc {\n" + body + "\n}")); |
103 | } else if cmd is While(O condition, O body) { |
104 | bool b = checkCondition(condition); |
105 | if (!b) ret; |
106 | proceduresToRun.add(new ProcedureToRun(ll(body, cmd), path)); |
107 | } else if (cmd cast S) { |
108 | O result = runNativePredicate(cmd); |
109 | if (result != null) { |
110 | if (result instanceof WithAlternative) { |
111 | print("Have alternative"); |
112 | IF0<NPRet> f = ((WithAlternative) result).alternative; |
113 | S _cmd = cmd; |
114 | path.steps.add(new Step { |
115 | NPRet alternative() { |
116 | ret f!; |
117 | } |
118 | |
119 | toString { ret _cmd; } |
120 | }); |
121 | result = ((WithAlternative) result).result; |
122 | } |
123 | if (isFalse(result)) ret; |
124 | if (isTrueOpt(result)) continue; |
125 | SS mapping = cast result; // assume it's a variable mapping |
126 | // apply to all remaining commands and continue |
127 | L remainingCommands2 = mapToLinkedList(remainingCommands, |
128 | c -> replaceVars(c, mapValues optRound(mapping))); |
129 | print("Applying var mapping " + mapping + " to " + remainingCommands |
130 | + " => " + remainingCommands2); |
131 | remainingCommands = remainingCommands2; |
132 | } else |
133 | addFact(cmd); |
134 | } else if (cmd != null) |
135 | fail("Unimplemented command: " + cmd); |
136 | } |
137 | pcallFAll(onProcedureEnded, commands, path); // notify listeners |
138 | } |
139 | |
140 | // return var mapping (SS), Bool or null for no matching predicate |
141 | O runNativePredicate(S s) { |
142 | for (NativePredicate np : nativePredicates) { |
143 | SS map = zipIt(np.head, s); |
144 | if (map != null) { |
145 | O result = np.body.get(mapValues tok_deRoundBracket(map)); |
146 | if (debugNativeCalls) |
147 | print("Native predicate result: " + np.head + " => " + result); |
148 | if (result instanceof Map && nempty(map)) { |
149 | result = mapKeys((SS) result, var -> lookupOrKeep(map, var)); |
150 | if (debugNativeCalls) |
151 | print("Rewrote native predicate result: " + result); |
152 | } |
153 | try object result; |
154 | } |
155 | } |
156 | null; |
157 | } |
158 | |
159 | bool checkCondition(O o) { |
160 | if (o cast S) { |
161 | if (contains(facts, o)) true; |
162 | O result = runNativePredicate(o); |
163 | if (result cast Bool) ret result; |
164 | if (result instanceof Map) true; // TODO |
165 | } |
166 | print("Ignoring condition: " + o); |
167 | false; |
168 | } |
169 | |
170 | Proc parseProcedure(S proc) { |
171 | //printStruct(proc); |
172 | proc = withoutLinesEmptyAfterTrim(proc); |
173 | //printStruct(proc); |
174 | proc = autoUnindent(proc); |
175 | //printStruct(proc); |
176 | print(indentx("> ", proc)); |
177 | |
178 | LS l = groupPythonStyleIndents_honoringBrackets(proc); |
179 | pnl("unpythonized ", l); |
180 | |
181 | new L out; |
182 | for i over l: { |
183 | S s = l.get(i); |
184 | LS tok = javaTokWithBrackets(s); |
185 | if (eqic(firstCodeToken(tok), "if")) { |
186 | assertEquals(s, ":", getCodeToken(tok, 2)); |
187 | out.add(new If(deRoundBracket(getCodeToken(tok, 1)), |
188 | parseProcedure(joinSubList(tok, 3*2)), null)); |
189 | } else if (eqic(firstCodeToken(tok), "while")) { |
190 | assertEquals(s, ":", getCodeToken(tok, 2)); |
191 | out.add(new While(deRoundBracket(getCodeToken(tok, 1)), |
192 | parseProcedure(joinSubList(tok, 3*2)))); |
193 | } else if (eqic(firstCodeToken(tok), "else")) { |
194 | O last = last(out); |
195 | if (!last instanceof If) fail("Else without if"); |
196 | assertEquals(s, ":", getCodeToken(tok, 1)); |
197 | ((If) last).elseBlock = joinSubList(tok, 2*2); |
198 | } else if (eqic(firstCodeToken(tok), "for")) { |
199 | assertEquals(s, ":", getCodeToken(tok, 2)); |
200 | S cond = getCodeToken(tok, 1); |
201 | // cond looks like: "(y | x has a y)" |
202 | cond = deRoundBracket(cond); |
203 | LS tok2 = javaTok(cond); |
204 | assertEquals(cond, "|", getCodeToken(tok2, 1)); |
205 | S var = assertIdentifier(cond, getCodeToken(tok2, 0)); |
206 | S actualCondition = trimJoinSubList(tok2, 2*2+1); |
207 | out.add(new For(var, actualCondition, parseProcedure(joinSubList(tok, 3*2)))); |
208 | } else |
209 | out.add(s); |
210 | } |
211 | pnl("Parsed procedure ", out); |
212 | ret out; |
213 | } |
214 | |
215 | O splitAtAmpersand2(S s) { |
216 | LS l = tok_splitAtAmpersand(s); |
217 | if (l(l) == 1) ret s; |
218 | ret new And(first(l), splitAtAmpersand2(join(" & ", dropFirst(l)))); |
219 | } |
220 | |
221 | // "zip" a condition with a fact (match word-by-word) |
222 | SS zipIt(S cond, S fact) { |
223 | SS map = gazelle_zip(cond, fact); |
224 | if (map == null) null; // no match |
225 | print("gazelle zip => " + map); |
226 | |
227 | // are only variables changed? |
228 | if (!allKeysAreInSet(map, vars)) |
229 | null; /*with print("Non-variable changes, exiting")*/; |
230 | |
231 | ret map; |
232 | } |
233 | |
234 | O replaceVars(O o, SS map) { |
235 | if (empty(map)) ret o; |
236 | // TODO: non-string cases |
237 | ret join(replaceCodeTokensUsingMap(javaTok((S) o), map)); |
238 | } |
239 | |
240 | void applyLogicRuleToFact(LogicRule rule, S fact) { |
241 | O lhs = rule.lhs, rhs = rule.rhs; |
242 | O cond, remaining = null; |
243 | if lhs is And(O a, O b) { |
244 | cond = a; |
245 | remaining = b; |
246 | } else |
247 | cond = lhs; |
248 | |
249 | // now we match the condition with the fact |
250 | SS map = zipIt((S) cond, fact); |
251 | if (map == null) ret; // no match |
252 | |
253 | // Now we have a proper mapping with the keys being variables! |
254 | print("Match."); |
255 | |
256 | // drop round brackets |
257 | // XXX? map = mapValues tok_deRoundBracket(map); |
258 | |
259 | // Apply mapping to right hand side |
260 | S rhs_replaced = cast replaceVars(rhs, map); |
261 | print(+rhs_replaced); |
262 | |
263 | if (remaining == null) { |
264 | // Add as fact |
265 | addFact(rhs_replaced); |
266 | } else { |
267 | // Apply mapping to remaning condition |
268 | S remaining_replaced = cast replaceVars(remaining, map); |
269 | addLogicRule(new LogicRule(remaining_replaced, rhs_replaced)); |
270 | } |
271 | } |
272 | |
273 | run { |
274 | parseProgram(); |
275 | think(); |
276 | } |
277 | |
278 | void parseProgram { |
279 | // split into paragraphs and unindent |
280 | |
281 | LS paragraphs = map autoUnindent(map rtrim(splitAtEmptyLines(program))); |
282 | print("Got " + n2(paragraphs, "parapraph")); |
283 | |
284 | // print the parapraphs |
285 | print(joinWithEmptyLines(map(s -> indentx("> ", s), paragraphs))); |
286 | |
287 | // throw away comment-only and quoted paragraphs (assume it's a title) |
288 | LS paragraphs2 = antiFilter(paragraphs, s -> |
289 | isSingleLine(trim(s)) && isQuoted(trim(s)) || countJavaTokens(s) == 0 |
290 | || endsWith(rtrim(s), "----")); |
291 | print("Got " + n2(paragraphs2, "filtered paragraph")); |
292 | print(joinWithEmptyLines(map(s -> indentx("> ", s), paragraphs2))); |
293 | |
294 | // find fact paragraphs |
295 | |
296 | print(map allLinesAreUnindented(paragraphs2)); |
297 | Pair<LS> p1 = filterAntiFilter(s -> |
298 | !isSingleLine(trim(s)) && allLinesAreUnindented(s), paragraphs2); |
299 | LS multiFactParagraphs = p1.a, paragraphs3 = p1.b; |
300 | |
301 | for (S para : multiFactParagraphs) |
302 | for (S s : tlft(para)) |
303 | addFact(s); |
304 | |
305 | // find logic rules |
306 | |
307 | new LS paragraphs4; |
308 | for (S para : paragraphs3) { |
309 | PairS p = splitAtDoubleArrow_pair(para); |
310 | if (p == null) continue with paragraphs4.add(para); |
311 | addLogicRule(new LogicRule(splitAtAmpersand2(p.a), splitAtAmpersand2(p.b))); |
312 | } |
313 | |
314 | pnlStruct("Unparsed - assuming facts", paragraphs4); |
315 | |
316 | // assume the unparsed stuff consists of facts |
317 | for (S para : paragraphs4) |
318 | addFact(para); |
319 | |
320 | originalFacts = cloneSet(facts); |
321 | } |
322 | |
323 | bool doSomeLogic() { |
324 | bool anyAction; |
325 | Pair<LogicRule, S> p; |
326 | while not null (p = rulesOnFacts.next()) { |
327 | set anyAction; |
328 | //print("Combination: " + p); |
329 | applyLogicRuleToFact(p.a, p.b); |
330 | } |
331 | ret anyAction; |
332 | } |
333 | |
334 | // indicator for end of thought process (when this stays stable) |
335 | long size() { |
336 | ret l(logicRules) + l(facts) + proceduresExecuted; |
337 | } |
338 | |
339 | void think { |
340 | int round = 0; |
341 | |
342 | while (round++ < maxRounds) { |
343 | long lastSize = size(); |
344 | print("Logic round " + round + ", size: " + lastSize); |
345 | while (doSomeLogic() && round++ < maxRounds) {} |
346 | |
347 | for (ProcedureToRun proc : getAndClearList(proceduresToRun)) |
348 | runParsedProcedure(proc.proc, proc.path); |
349 | |
350 | if (size() == lastSize) { |
351 | print("No changes, exiting"); |
352 | break; |
353 | } |
354 | } |
355 | |
356 | // We're done logicking, so print all the facts gathered |
357 | |
358 | LS factsToPrint = listMinusList(facts, originalFacts); |
359 | pnlWithHeading("Facts I deduced", factsToPrint); |
360 | |
361 | // Print the actual output |
362 | |
363 | new LS output; |
364 | for (S fact : factsToPrint) { |
365 | LS tok = javaTokWithBrackets(fact); |
366 | if (countCodeTokens(tok) == 2 && eqic(getCodeToken(tok, 0), "print")) |
367 | // For the user, we print without all the round brackets |
368 | output.add(tok_dropRoundBrackets(getCodeToken(tok, 1))); |
369 | } |
370 | |
371 | pnlWithHeading("Bot Output", output); |
372 | } |
373 | |
374 | void addNativePredicate(S head, IF0 body) { |
375 | nativePredicates.add(new NativePredicate(head, map -> body!)); |
376 | } |
377 | |
378 | void addNativePredicate(S head, IF1<SS, O> body) { |
379 | nativePredicates.add(new NativePredicate(head, body)); |
380 | } |
381 | |
382 | // for backtracking in native predicates |
383 | WithAlternative withAlternative(IF0<O> alternative, O result) { |
384 | ret new WithAlternative(alternative, result); |
385 | } |
386 | } |
download show line numbers debug dex old transpilations
Travelled to 6 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt
No comments. add comment
Snippet ID: | #1025612 |
Snippet name: | PhilosophyBot1 backtracking attempt 1 with Path |
Eternal ID of this version: | #1025612/2 |
Text MD5: | cd6ac86a4e56d32909935d644cf3f42d |
Author: | stefan |
Category: | |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2019-10-08 14:08:32 |
Source code size: | 12821 bytes / 386 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 226 / 217 |
Version history: | 1 change(s) |
Referenced in: | [show references] |