C: forward chaining with bit sets

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.

#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;
}

Read the full lesson