C: forward chaining with bit sets

Before you start

C bitwise operators, structs, and arrays.

Store facts as bits of an integer and apply if-then rules with bitwise operations.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A set of facts can be stored compactly as the bits of an unsigned integer: bit i is 1 when fact i is known. A rule says that if all the premise facts are known, the conclusion becomes known. With bit sets, checking a rule is one expression: (facts & premises) == premises. Adding a conclusion is facts |= conclusion.

Forward chaining repeats until no rule adds anything new. Each rule here has one conclusion, and a conclusion that is already known does not count as progress, which guarantees the loop ends. Because the facts never decrease, the process reaches a unique final set, called the closure.

Code example

#include <stdio.h>

enum { RAIN, COLD, WET, ICE, SLIPPERY, CAREFUL, FACT_COUNT };

typedef struct {
  unsigned premises;
  unsigned conclusion;
} Rule;

#define BIT(f) (1u << (f))

int main(void) {
  const char *names[FACT_COUNT] = {"rain", "cold", "wet", "ice", "slippery", "careful"};
  Rule rules[] = {
    {BIT(RAIN), BIT(WET)},
    {BIT(WET) | BIT(COLD), BIT(ICE)},
    {BIT(ICE), BIT(SLIPPERY)},
    {BIT(SLIPPERY), BIT(CAREFUL)},
  };
  unsigned facts = BIT(RAIN) | BIT(COLD);

  int changed = 1;
  while (changed) {
    changed = 0;
    for (int i = 0; i < 4; i++) {
      if ((facts & rules[i].premises) == rules[i].premises && !(facts & rules[i].conclusion)) {
        facts |= rules[i].conclusion;
        for (int f = 0; f < FACT_COUNT; f++) {
          if (rules[i].conclusion == BIT(f)) {
            printf("derived %s\n", names[f]);
          }
        }
        changed = 1;
      }
    }
  }

  printf("known:");
  for (int f = 0; f < FACT_COUNT; f++) {
    if (facts & BIT(f)) {
      printf(" %s", names[f]);
    }
  }
  printf("\n");
  return 0;
}

Output

derived wet
derived ice
derived slippery
derived careful
known: 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

1#include <stdio.h>

3enum { RAIN, COLD, WET, ICE, SLIPPERY, CAREFUL, FACT_COUNT };

5typedef struct {

6 unsigned premises;

7 unsigned conclusion;

8} Rule;

10#define BIT(f) (1u << (f))

12int main(void) {

13 const char *names[FACT_COUNT] = {"rain", "cold", "wet", "ice", "slippery", "careful"};

14 Rule rules[] = {

15 {BIT(RAIN), BIT(WET)},

16 {BIT(WET) | BIT(COLD), BIT(ICE)},

17 {BIT(ICE), BIT(SLIPPERY)},

18 {BIT(SLIPPERY), BIT(CAREFUL)},

19 };

20 unsigned facts = BIT(RAIN) | BIT(COLD);

22 int changed = 1;

23 while (changed) {

24 changed = 0;

25 for (int i = 0; i < 4; i++) {

26 if ((facts & rules[i].premises) == rules[i].premises && !(facts & rules[i].conclusion)) {

27 facts |= rules[i].conclusion;

28 for (int f = 0; f < FACT_COUNT; f++) {

29 if (rules[i].conclusion == BIT(f)) {

30 printf("derived %s\n", names[f]);

31 }

32 }

33 changed = 1;

34 }

35 }

36 }

38 printf("known:");

39 for (int f = 0; f < FACT_COUNT; f++) {

40 if (facts & BIT(f)) {

41 printf(" %s", names[f]);

42 }

43 }

44 printf("\n");

45 return 0;

46}

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
Two starting facts, stored as two bits.	`facts = 0b000011`	—
The rule fires if all its premise bits are set and its conclusion is new.	`facts = 0b000011`	—
Set the conclusion bit.	`facts gains one bit per firing`	—
wet, then ice (needs wet and cold), then slippery, then careful.	`facts gains one bit per firing`	derived wet derived ice derived slippery derived careful
The loop stops when a full pass changes nothing; every derivable fact is now known.	`facts gains one bit per firing`	derived wet derived ice derived slippery derived careful known: rain cold wet ice slippery careful

Behind the scenes

How C processes this code

The C compiler produces a native program. Variables occupy memory, and execution enters main.

Cost and common mistakes

O(r) per pass over r rules, with at most r passes that add a fact.

An unsigned int holds at most 32 facts (or 64 with unsigned long long). Larger knowledge bases need arrays of bits.
Shifting 1 left by 31 or more on a signed int is undefined. Use unsigned constants, as BIT does.
Forward chaining derives everything it can. If you only need one goal, backward chaining may do less work.

Try it yourself

What is derived if cold is not a starting fact?

Reveal answer and reasoning

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