View difference between Paste ID: hqZ2FsZL and CCsZgZvf
SHOW: | | - or go back to the newest paste.
1
%% Backward chaining
2
%% -- implemented as a parallel search
3
%% -- the search tree interleaves calling of solveGoals and solveRules
4
%% -- solveGoals takes the first result available (OR)
5
%% -- solveRules collects all results before calculating an answer (AND)
6
%% -- technically this is called an AND-OR tree
7-
	%% Initialize KB
7+
8
-module(backward).
9
-export([start/0,mainLoop/0,solveGoal/2,solveRule/2,collect/3]).
10
11
start() ->
12
	%% Initialize knowledge base;  Notice the goal g has 2 rules applicable to it
13
	ets:new(rules, [bag, named_table]),
14
	ets:insert(rules, {g,[d,e,f,h,i,j],1.0}),
15
	ets:insert(rules, {g,[a,b,c],1.1}),
16
	ets:insert(rules, {a,[],0.1}),
17
	ets:insert(rules, {b,[],0.2}),
18
	ets:insert(rules, {c,[],0.3}),
19
	ets:insert(rules, {d,[],0.4}),
20
	ets:insert(rules, {e,[],0.5}),
21
	ets:insert(rules, {f,[],0.6}),
22
	ets:insert(rules, {h,[],0.7}),
23
	ets:insert(rules, {i,[],0.8}),
24
	ets:insert(rules, {j,[],0.9}),
25
	mainLoop().
26-
		true -> ok
26+
27
mainLoop() ->
28-
	Daddy = spawn(backward, solveGoal, [element(2, Query), self()]),
28+
29
	if
30
		Query == {ok, x} -> exit(normal);
31-
					  exit(Daddy, ok)
31+
		true -> true
32
	end,
33
	Root = spawn(backward, solveGoal, [element(2, Query), self()]),
34
	receive
35
		{_, Truth} -> io:format("Answer is: ~w~n", [Truth]),
36
					  exit(Root, ok)       % terminate the remaining processes
37
	end,
38
	mainLoop().
39
40
solveGoal(Goal, Caller) ->
41-
			%% If RHS is null
41+
42
	ApplicableRules = ets:match(rules,{Goal, '$1', '$2'}),
43-
			%% If RHS contains subgoals
43+
44
		fun([RuleBody,Truth]) ->
45
		if 
46
			%% If rule's body is null, return the truth value
47
			RuleBody == [] -> Caller ! {Goal, Truth};
48-
		%% Each message is of the form {goal,truth}
48+
			%% If rule's body contains subgoals, solve them recursively
49
			true -> spawn_link(backward, solveRule, [RuleBody, self()])
50
		end end,
51
		ApplicableRules),
52
	receive
53
		%% Each message is of the form {subgoal,truth}
54
		%% Just accept the 1st answer
55
		{_, Truth} -> Caller ! {Goal, Truth}		  
56-
	%% For each subgoal in Rule
56+
57-
	%% Spawn a process to solve each subgoal
57+
58
solveRule(RuleTail, Caller) ->
59
	N = length(RuleTail),
60
	Collector = spawn_link(backward, collect, [[], N, Caller]),
61
	%% For each subgoal in Rule, spawn a process to solve each subgoal
62
	lists:foreach(
63
		fun(Subgoal) -> spawn_link(backward, solveGoal, [Subgoal, Collector]) end,
64-
	%% If we have N messages send back the answer
64+
65
66
%% Accumulate results
67
collect(Truths, N, Caller) ->
68
	%% Collect N messages before sending back an answer
69
	%% Answer = min of truth values, equivalent to fuzzy-logic AND
70
	%% "min" is changed to "sum" to examine the code's behavior
71
	if length(Truths) == N -> Caller ! {dont_care, lists:sum(Truths)};
72
	   true -> true
73
	end,
74
	receive
75
		{_, Truth} -> collect([Truth | Truths], N, Caller)
76
	end.