Java: forward chaining with if-then rules

Before you start

Java lists, sets, and loops.

Repeatedly apply rules whose conditions are known until no new facts can be derived.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A rule-based system stores facts and rules of the form: if all of these conditions hold, then this conclusion holds. Forward chaining starts with the known facts and applies any rule whose conditions are all satisfied, adding its conclusion as a new fact. It repeats until nothing new can be added.

In the example the facts are rain and cold. Rain gives wet, wet and cold give ice, ice gives slippery, and slippery gives careful. A set makes adding a fact idempotent, and add returns false when the fact was already known, which is how the loop detects that it has finished.

Code example

Java

import java.util.*;

class Main {
  static class Rule {
    final List<String> body;
    final String head;

    Rule(List<String> body, String head) {
      this.body = body;
      this.head = head;
    }
  }

  public static void main(String[] args) {
    List<Rule> rules = List.of(
        new Rule(List.of("rain"), "wet"),
        new Rule(List.of("wet", "cold"), "ice"),
        new Rule(List.of("ice"), "slippery"),
        new Rule(List.of("slippery"), "careful"));
    Set<String> known = new LinkedHashSet<>(List.of("rain", "cold"));

    boolean changed = true;
    while (changed) {
      changed = false;
      for (Rule rule : rules) {
        if (known.containsAll(rule.body) && known.add(rule.head)) {
          System.out.println("derived " + rule.head);
          changed = true;
        }
      }
    }
    System.out.println(known);
  }
}

Output

derived wet
derived ice
derived slippery
derived careful
[rain, cold, wet, ice, slippery, careful]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1import java.util.*;

3class Main {

4 static class Rule {

5 final List<String> body;

6 final String head;

8 Rule(List<String> body, String head) {

9 this.body = body;

10 this.head = head;

11 }

12 }

14 public static void main(String[] args) {

15 List<Rule> rules = List.of(

16 new Rule(List.of("rain"), "wet"),

17 new Rule(List.of("wet", "cold"), "ice"),

18 new Rule(List.of("ice"), "slippery"),

19 new Rule(List.of("slippery"), "careful"));

20 Set<String> known = new LinkedHashSet<>(List.of("rain", "cold"));

22 boolean changed = true;

23 while (changed) {

24 changed = false;

25 for (Rule rule : rules) {

26 if (known.containsAll(rule.body) && known.add(rule.head)) {

27 System.out.println("derived " + rule.head);

28 changed = true;

29 }

30 }

31 }

32 System.out.println(known);

33 }

34}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Start with two known facts.	`known = {rain, cold}`	—
A rule fires when every condition is known and its conclusion is new.	`rain ⇒ wet fires first`	—
wet, then ice (needs wet and cold), then slippery, then careful.	`known grows by one fact per firing`	derived wet derived ice derived slippery derived careful
A second pass adds nothing, so the loop stops and the closure is printed.	`known grows by one fact per firing`	derived wet derived ice derived slippery derived careful [rain, cold, wet, ice, slippery, careful]

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

Cost and common mistakes

Polynomial: each pass is O(r·b) for r rules with at most b conditions, and there are at most r passes that add a fact.

If the same conclusion is added twice, a list would hold duplicates; the set avoids that and ends the loop.
Forward chaining derives everything it can, even facts you do not need. Backward chaining starts from a goal instead.

Try it yourself

What is derived if cold is removed from the starting facts?

Reveal answer and reasoning

Only wet is derived, because ice needs both wet and cold.