Prolog Interpreter (with executor, developing) [1002823]

!752

!include #1002825 // new structure

static class Prolog {
  int varCount;
  boolean showStuff;
  
  class Var extends Lisp {
    Lisp instance;
    
    *() {
      this("V" + (++varCount));
    }
    
    *(S name) {
      super(name);
      instance = this;
    }
    
    void reset() { instance = this; }
    
    public String toString() {
      if (instance == this) ret getName();
      ret instance.toString();
    }
    
    S getName() {
      ret head;
    }
  }
  
  class Clause {
    Lisp head;
    Goal body;
    
    *(Lisp *head, Goal *body) {}
    *(Lisp *head) {}
    
    Clause copy() {
      return new Clause(copy2(head), body == null ? null : body.copy());
    }
    
    public String toString() {
      //ret head + " :- " + (body == null ? "true" : body);
      ret body == null ? head.toString() : head + " :- " + body;
    }
  };
  
  static class Program {
    Clause pcar;
    Program pcdr;
    
    *(Clause *pcar, Program *pcdr) {}
    *(L<Clause> clauses) {
      this(clauses, 0);
    }
    
    *(L<Clause> clauses, int i) {
      pcar = clauses.get(i);
      if (i+1 < l(clauses))
        pcdr = new Program(clauses, i+1);
    }
    
    *(Clause... clauses) {
      this(asList(clauses));
    }
    
    public String toString() {
      ret pcdr == null ? pcar + "." : pcar + ".\n" + pcdr;
    }
  }
  
  class Trail {
    Var tcar;
    Trail tcdr;
    
    *(Var *tcar, Trail *tcdr) {}
  }
  
  Trail sofar = null;
  
  Trail Trail_Note() { return sofar; }
  void Trail_Push(Var x) { sofar = new Trail(x, sofar); }
  void Trail_Undo(Trail whereto) {
    for (; sofar != whereto; sofar = sofar.tcdr)
      sofar.tcar.reset();
  }
  
  static class TermVarMapping {
    new L<Var> vars;
    
    *(L<Var> *vars) {}
    *(Var... vars) { this.vars.addAll(asList(vars)); }
    
    void showanswer() {
      print("TRUE.");
      for (Var v : vars)
        print("  " + v.getName() + " = " + v);
    }
  }
      
  class Goal {
    Lisp car;
    Goal cdr;
    
    *(Lisp *car, Goal *cdr) {}
    *(Lisp *car) {}
    
    public String toString() {
      ret cdr == null ? car.toString() : car + "; " + cdr;
    }
    
    void solve(Program p, int level, TermVarMapping map) {
      if (showStuff)
        print(indent(level) + "solve@" + level + ": " + this);
        
      for (Program q = p; q != null; q = q.pcdr) {
        Trail t = Trail_Note();
        Clause c = q.pcar.copy();
        Trail_Undo(t);
        if (showStuff)
          print(indent(level) + "  try:" + c);
        if (unify(car, c.head)) {
          Goal gdash = c.body == null ? cdr : c.body.append(cdr);
          if (gdash == null)
            map.showanswer();
          else
            gdash.solve(p, level+1, map);
        } else
          if (showStuff)
            print(indent(level) + "  nomatch.");
        Trail_Undo(t);
      }
    }
    
    Goal copy() {
      return new Goal(copy2(car),
        cdr == null ? null : cdr.copy());
    }
    
    Goal append(Goal l) {
      return new Goal(car, cdr == null ? null : cdr.append(l));
    }
    
  } // class Goal
  
  boolean unify(Lisp thiz, Lisp t) {
    if (thiz instanceof Var) { // TermVar::unify
      Var v = cast thiz;
      if (v.instance != v)
        return unify(v.instance, t);
      Trail_Push(v);
      v.instance = t;
      return true;
    }
    
    // TermCons::unify
    return unify2(t, thiz);
  }
  
  boolean unify2(Lisp thiz, Lisp t) { 
    if (thiz instanceof Var)
      return unify(thiz, t);
   
    int arity = thiz.size();
    if (neq(thiz.head, t.head) || arity != t.size())
      return false;
    for (int i = 0; i < arity; i++)
      if (!unify(thiz.get(i), t.get(i)))
        return false;
    return true;
  }
  
  Lisp copy(Lisp thiz) {
    if (thiz instanceof Var) {
      Var v = cast thiz;
      if (v.instance == v) {
        Trail_Push(v);
        v.instance = new Var();
      }
      return v.instance;
    }
    
    ret copy2(thiz);
  }
  
  Lisp newTermCons(Lisp t) {
    Lisp l = new Lisp(t.head);
    for (Lisp arg : t)
      l.add(copy(arg));
    ret l;
  }
  
  Lisp copy2(Lisp thiz) {
    return newTermCons(thiz);
  }
  
  Var newVar() {
    ret new Var;
  }
  
  Var newVar(S name) {
    ret new Var(name);
  }
  
  Clause clause(Lisp head, Goal body) {
    ret prologify(new Clause(head, body));
  }
  
  Clause clause(Lisp head) {
    ret prologify(new Clause(head));
  }
  
  Clause clause(Lisp head, Lisp body) {
    ret clause(head, new Goal(body));
  }
  
  Lisp prologify(Lisp term) {
    ret prologify(term, new HashMap);
  }
  
  Clause prologify(Clause c) {
    new HashMap vars;
    ret new Clause(
      prologify(c.head, vars),
      prologify(c.body, vars));
  }
  
  Goal prologify(Goal goal, Map<S, Var> vars) {
    if (goal == null) ret null;
    ret new Goal(
      prologify(goal.car, vars),
      prologify(goal.cdr, vars));
  }
  
  Lisp prologify(Lisp term, Map<S, Var> vars) {
    if (term == null) ret null;
    if (snlIsVar(term)) {
      Var v = vars.get(term.head);
      if (v == null)
        vars.put(term.head, v = newVar(term.head));
      ret v;
    } else {
      Lisp l = new Lisp(term.head);
      for (Lisp arg : term)
        l.add(prologify(arg, vars));
      ret l;
    }
  }
  
  L<Var> findVars(Lisp term) {
    new IdentityHashMap<Var, Boolean> map;
    findVars(term, map);
    ret asList(map.keySet());
  }
  
  void findVars(Lisp term, IdentityHashMap<Var, Boolean> map) {
    if (term instanceof Var)
      map.put((Var) term, Boolean.TRUE);
    else
      for (Lisp arg : term)
        findVars(arg, map);
  }
  
  static Map<S, Var> makeVarMap(L<Var> vars) {
    new HashMap<S, Var> map;
    for (Var v : vars)
      map.put(v.getName(), v);
    ret map;
  }
  
  // Executor stack entry
  static class Entry {
    Goal goal;
    Program q;
    Trail trail;
    boolean trailSet;
    
    *(Program *q, Goal *goal) {}
  }
  
  Executor executor;
  
  Executor newExecutor(Program p, Goal goal) {
    if (executor != null) fail("Already got an executor");
    ret executor = new Executor(p, goal);
  }

  // a stackless, step-based executor for Prolog queries
  // only one instance per Prolog instance!
  class Executor {
    Program p;
    new L<Entry> stack;
    
    *(Program *p, Goal goal) {
      stack.add(new Entry(p, goal));
    }
    
    int level() {
      ret l(stack)-1;
    }
    
    boolean done() {
      ret empty(stack);
    }
    
    boolean step() {
      if (done()) fail("done!"); // safety
      
      Entry e = last(stack);
      
      if (e.trailSet) {
        Trail_Undo(e.trail);
        e.trailSet = false;
      }
      
      if (e.q == null) { // program loop ends
        removeLast(stack);
        ret false;
      }
        
      if (showStuff)
        print(indent(level()) + "solve@" + level() + ": " + e.goal);
        
      // now in program loop
      
      e.trail = Trail_Note();
      e.trailSet = true;
      Clause c = e.q.pcar.copy();
      e.q = e.q.pcdr; // next clause in program
      Trail_Undo(e.trail);
      if (showStuff)
        print(indent(level()) + "  try:" + c);
      if (unify(e.goal.car, c.head)) {
        Goal gdash = c.body == null ? e.goal.cdr : c.body.append(e.goal.cdr);
        if (gdash == null)
          ret true;
        else {
          stack.add(new Entry(p, gdash));
          ret false;
        }
      } else
        if (showStuff)
          print(indent(level()) + "  nomatch.");
          
      ret false;
    }
  }
  
} // class Prolog

p {
  new Prolog p;
  
  /* A sample test program: append */
  
  S at_app = "app";
  S at_cons = "cons";
  Lisp f_nil = lisp("nil");
  Lisp f_1 = lisp("1");
  Lisp f_2 = lisp("2");
  Lisp f_3 = lisp("3");
  
  // Try making a clause from pure Lisp
  
  Lisp lhs1 = lisp("app", "nil", "X", "X");
  Prolog.Clause c1 = p.clause(lhs1);
  print("c1: " + structure_seen(c1));
  
  Lisp rhs2 = lisp(at_app, "L", "M", "N");
  Lisp lhs2 = lisp(at_app, lisp(at_cons, "X", "L"),
    "M",
    lisp(at_cons, "X", "N"));
                                        
  Prolog.Clause c2 = p.clause(lhs2, rhs2);
  
  // Test prologify
  
  Lisp rhs3pre = lisp("app", "I", "J", 
    lisp("cons", "1",
    lisp("cons", "2",
    lisp("cons", "3", "nil"))));
  
  Lisp rhs3 = p.prologify(rhs3pre);
  L<Prolog.Var> vars = p.findVars(rhs3);
  print("Vars: " + structure_seen(vars));
  Map<S, Prolog.Var> varMap = Prolog.makeVarMap(vars);
  Prolog.Var v_i = varMap.get("I");
  Prolog.Var v_j = varMap.get("J");
  assertNotNull(v_i);
  assertNotNull(v_j);
  Prolog.Goal g1 = p.new Goal(rhs3);
  
  Prolog.Program test_p = new Prolog.Program(c1, c2);
  Prolog.Program test_p2 = new Prolog.Program(c2, c1);
  
  Prolog.TermVarMapping var_name_map = new Prolog.TermVarMapping(v_i, v_j);

  /*
  print("=======Append with normal clause order:");
  print(test_p);
  print();
  g1.solve(test_p, 0, var_name_map);
  print();
  print("=======Append with reversed normal clause order:");
  print(test_p2);
  print();
  g1.solve(test_p2, 0, var_name_map);
  */
  
  p.showStuff = true;
  Prolog.Executor e = p.newExecutor(test_p, g1);
  int safety = 0;
  while (!e.done() && ++safety < 1000) {
    if (e.step()) {
      print("Solution at iteration " + safety + ":");
      var_name_map.showanswer();
    }
  }
  print("Steps: " + safety);
}

Travelled to 13 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, gwrvuhgaqvyk, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt

Snippet ID:	#1002823
Snippet name:	Prolog Interpreter (with executor, developing)
Eternal ID of this version:	#1002823/1
Text MD5:	4be912e0b0bb18aa752807baab4f4ffa
Transpilation MD5:	da2062398da412689a5d19828683380d
Author:	stefan
Category:	javax
Type:	JavaX source code
Public (visible to everyone):	Yes
Archived (hidden from active list):	No
Created/modified:	2016-02-29 01:08:30
Source code size:	9732 bytes / 422 lines
Pitched / IR pitched:	No / No
Views / Downloads:	984 / 1025
Referenced in:	[show references]

< > BotCompany Repo | #1002823 // Prolog Interpreter (with executor, developing)

JavaX source code [tags: use-pretranspiled] - run with: x30.jar

Author comment

1	!752
2
3	!include #1002825 // new structure
4
5	static class Prolog {
6	int varCount;
7	boolean showStuff;
8
9	class Var extends Lisp {
10	Lisp instance;
11
12	*() {
13	this("V" + (++varCount));
14	}
15
16	*(S name) {
17	super(name);
18	instance = this;
19	}
20
21	void reset() { instance = this; }
22
23	public String toString() {
24	if (instance == this) ret getName();
25	ret instance.toString();
26	}
27
28	S getName() {
29	ret head;
30	}
31	}
32
33	class Clause {
34	Lisp head;
35	Goal body;
36
37	(Lisp head, Goal *body) {}
38	(Lisp head) {}
39
40	Clause copy() {
41	return new Clause(copy2(head), body == null ? null : body.copy());
42	}
43
44	public String toString() {
45	//ret head + " :- " + (body == null ? "true" : body);
46	ret body == null ? head.toString() : head + " :- " + body;
47	}
48	};
49
50	static class Program {
51	Clause pcar;
52	Program pcdr;
53
54	(Clause pcar, Program *pcdr) {}
55	*(L<Clause> clauses) {
56	this(clauses, 0);
57	}
58
59	*(L<Clause> clauses, int i) {
60	pcar = clauses.get(i);
61	if (i+1 < l(clauses))
62	pcdr = new Program(clauses, i+1);
63	}
64
65	*(Clause... clauses) {
66	this(asList(clauses));
67	}
68
69	public String toString() {
70	ret pcdr == null ? pcar + "." : pcar + ".\n" + pcdr;
71	}
72	}
73
74	class Trail {
75	Var tcar;
76	Trail tcdr;
77
78	(Var tcar, Trail *tcdr) {}
79	}
80
81	Trail sofar = null;
82
83	Trail Trail_Note() { return sofar; }
84	void Trail_Push(Var x) { sofar = new Trail(x, sofar); }
85	void Trail_Undo(Trail whereto) {
86	for (; sofar != whereto; sofar = sofar.tcdr)
87	sofar.tcar.reset();
88	}
89
90	static class TermVarMapping {
91	new L<Var> vars;
92
93	(L<Var> vars) {}
94	*(Var... vars) { this.vars.addAll(asList(vars)); }
95
96	void showanswer() {
97	print("TRUE.");
98	for (Var v : vars)
99	print(" " + v.getName() + " = " + v);
100	}
101	}
102
103	class Goal {
104	Lisp car;
105	Goal cdr;
106
107	(Lisp car, Goal *cdr) {}
108	(Lisp car) {}
109
110	public String toString() {
111	ret cdr == null ? car.toString() : car + "; " + cdr;
112	}
113
114	void solve(Program p, int level, TermVarMapping map) {
115	if (showStuff)
116	print(indent(level) + "solve@" + level + ": " + this);
117
118	for (Program q = p; q != null; q = q.pcdr) {
119	Trail t = Trail_Note();
120	Clause c = q.pcar.copy();
121	Trail_Undo(t);
122	if (showStuff)
123	print(indent(level) + " try:" + c);
124	if (unify(car, c.head)) {
125	Goal gdash = c.body == null ? cdr : c.body.append(cdr);
126	if (gdash == null)
127	map.showanswer();
128	else
129	gdash.solve(p, level+1, map);
130	} else
131	if (showStuff)
132	print(indent(level) + " nomatch.");
133	Trail_Undo(t);
134	}
135	}
136
137	Goal copy() {
138	return new Goal(copy2(car),
139	cdr == null ? null : cdr.copy());
140	}
141
142	Goal append(Goal l) {
143	return new Goal(car, cdr == null ? null : cdr.append(l));
144	}
145
146	} // class Goal
147
148	boolean unify(Lisp thiz, Lisp t) {
149	if (thiz instanceof Var) { // TermVar::unify
150	Var v = cast thiz;
151	if (v.instance != v)
152	return unify(v.instance, t);
153	Trail_Push(v);
154	v.instance = t;
155	return true;
156	}
157
158	// TermCons::unify
159	return unify2(t, thiz);
160	}
161
162	boolean unify2(Lisp thiz, Lisp t) {
163	if (thiz instanceof Var)
164	return unify(thiz, t);
165
166	int arity = thiz.size();
167	if (neq(thiz.head, t.head) \|\| arity != t.size())
168	return false;
169	for (int i = 0; i < arity; i++)
170	if (!unify(thiz.get(i), t.get(i)))
171	return false;
172	return true;
173	}
174
175	Lisp copy(Lisp thiz) {
176	if (thiz instanceof Var) {
177	Var v = cast thiz;
178	if (v.instance == v) {
179	Trail_Push(v);
180	v.instance = new Var();
181	}
182	return v.instance;
183	}
184
185	ret copy2(thiz);
186	}
187
188	Lisp newTermCons(Lisp t) {
189	Lisp l = new Lisp(t.head);
190	for (Lisp arg : t)
191	l.add(copy(arg));
192	ret l;
193	}
194
195	Lisp copy2(Lisp thiz) {
196	return newTermCons(thiz);
197	}
198
199	Var newVar() {
200	ret new Var;
201	}
202
203	Var newVar(S name) {
204	ret new Var(name);
205	}
206
207	Clause clause(Lisp head, Goal body) {
208	ret prologify(new Clause(head, body));
209	}
210
211	Clause clause(Lisp head) {
212	ret prologify(new Clause(head));
213	}
214
215	Clause clause(Lisp head, Lisp body) {
216	ret clause(head, new Goal(body));
217	}
218
219	Lisp prologify(Lisp term) {
220	ret prologify(term, new HashMap);
221	}
222
223	Clause prologify(Clause c) {
224	new HashMap vars;
225	ret new Clause(
226	prologify(c.head, vars),
227	prologify(c.body, vars));
228	}
229
230	Goal prologify(Goal goal, Map<S, Var> vars) {
231	if (goal == null) ret null;
232	ret new Goal(
233	prologify(goal.car, vars),
234	prologify(goal.cdr, vars));
235	}
236
237	Lisp prologify(Lisp term, Map<S, Var> vars) {
238	if (term == null) ret null;
239	if (snlIsVar(term)) {
240	Var v = vars.get(term.head);
241	if (v == null)
242	vars.put(term.head, v = newVar(term.head));
243	ret v;
244	} else {
245	Lisp l = new Lisp(term.head);
246	for (Lisp arg : term)
247	l.add(prologify(arg, vars));
248	ret l;
249	}
250	}
251
252	L<Var> findVars(Lisp term) {
253	new IdentityHashMap<Var, Boolean> map;
254	findVars(term, map);
255	ret asList(map.keySet());
256	}
257
258	void findVars(Lisp term, IdentityHashMap<Var, Boolean> map) {
259	if (term instanceof Var)
260	map.put((Var) term, Boolean.TRUE);
261	else
262	for (Lisp arg : term)
263	findVars(arg, map);
264	}
265
266	static Map<S, Var> makeVarMap(L<Var> vars) {
267	new HashMap<S, Var> map;
268	for (Var v : vars)
269	map.put(v.getName(), v);
270	ret map;
271	}
272
273	// Executor stack entry
274	static class Entry {
275	Goal goal;
276	Program q;
277	Trail trail;
278	boolean trailSet;
279
280	(Program q, Goal *goal) {}
281	}
282
283	Executor executor;
284
285	Executor newExecutor(Program p, Goal goal) {
286	if (executor != null) fail("Already got an executor");
287	ret executor = new Executor(p, goal);
288	}
289
290	// a stackless, step-based executor for Prolog queries
291	// only one instance per Prolog instance!
292	class Executor {
293	Program p;
294	new L<Entry> stack;
295
296	(Program p, Goal goal) {
297	stack.add(new Entry(p, goal));
298	}
299
300	int level() {
301	ret l(stack)-1;
302	}
303
304	boolean done() {
305	ret empty(stack);
306	}
307
308	boolean step() {
309	if (done()) fail("done!"); // safety
310
311	Entry e = last(stack);
312
313	if (e.trailSet) {
314	Trail_Undo(e.trail);
315	e.trailSet = false;
316	}
317
318	if (e.q == null) { // program loop ends
319	removeLast(stack);
320	ret false;
321	}
322
323	if (showStuff)
324	print(indent(level()) + "solve@" + level() + ": " + e.goal);
325
326	// now in program loop
327
328	e.trail = Trail_Note();
329	e.trailSet = true;
330	Clause c = e.q.pcar.copy();
331	e.q = e.q.pcdr; // next clause in program
332	Trail_Undo(e.trail);
333	if (showStuff)
334	print(indent(level()) + " try:" + c);
335	if (unify(e.goal.car, c.head)) {
336	Goal gdash = c.body == null ? e.goal.cdr : c.body.append(e.goal.cdr);
337	if (gdash == null)
338	ret true;
339	else {
340	stack.add(new Entry(p, gdash));
341	ret false;
342	}
343	} else
344	if (showStuff)
345	print(indent(level()) + " nomatch.");
346
347	ret false;
348	}
349	}
350
351	} // class Prolog
352
353	p {
354	new Prolog p;
355
356	/* A sample test program: append */
357
358	S at_app = "app";
359	S at_cons = "cons";
360	Lisp f_nil = lisp("nil");
361	Lisp f_1 = lisp("1");
362	Lisp f_2 = lisp("2");
363	Lisp f_3 = lisp("3");
364
365	// Try making a clause from pure Lisp
366
367	Lisp lhs1 = lisp("app", "nil", "X", "X");
368	Prolog.Clause c1 = p.clause(lhs1);
369	print("c1: " + structure_seen(c1));
370
371	Lisp rhs2 = lisp(at_app, "L", "M", "N");
372	Lisp lhs2 = lisp(at_app, lisp(at_cons, "X", "L"),
373	"M",
374	lisp(at_cons, "X", "N"));
375
376	Prolog.Clause c2 = p.clause(lhs2, rhs2);
377
378	// Test prologify
379
380	Lisp rhs3pre = lisp("app", "I", "J",
381	lisp("cons", "1",
382	lisp("cons", "2",
383	lisp("cons", "3", "nil"))));
384
385	Lisp rhs3 = p.prologify(rhs3pre);
386	L<Prolog.Var> vars = p.findVars(rhs3);
387	print("Vars: " + structure_seen(vars));
388	Map<S, Prolog.Var> varMap = Prolog.makeVarMap(vars);
389	Prolog.Var v_i = varMap.get("I");
390	Prolog.Var v_j = varMap.get("J");
391	assertNotNull(v_i);
392	assertNotNull(v_j);
393	Prolog.Goal g1 = p.new Goal(rhs3);
394
395	Prolog.Program test_p = new Prolog.Program(c1, c2);
396	Prolog.Program test_p2 = new Prolog.Program(c2, c1);
397
398	Prolog.TermVarMapping var_name_map = new Prolog.TermVarMapping(v_i, v_j);
399
400	/*
401	print("=======Append with normal clause order:");
402	print(test_p);
403	print();
404	g1.solve(test_p, 0, var_name_map);
405	print();
406	print("=======Append with reversed normal clause order:");
407	print(test_p2);
408	print();
409	g1.solve(test_p2, 0, var_name_map);
410	*/
411
412	p.showStuff = true;
413	Prolog.Executor e = p.newExecutor(test_p, g1);
414	int safety = 0;
415	while (!e.done() && ++safety < 1000) {
416	if (e.step()) {
417	print("Solution at iteration " + safety + ":");
418	var_name_map.showanswer();
419	}
420	}
421	print("Steps: " + safety);
422	}