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. |