Demo minimal Prolog interpreter for finding 'Hunting Buddies' program

PrologInterpreter.java

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class PrologInterpreter {

  // Represents a Prolog term (fact or rule component)
  public static class Term {
    String predicate;
    List<String> arguments;

    public Term(String predicate, List<String> arguments) {
      this.predicate = predicate;
      this.arguments = arguments;
    }

    public Term(String predicate, String... args) {
      this.predicate = predicate;
      this.arguments = Arrays.asList(args);
    }

    @Override
    public String toString() {
      if (arguments.isEmpty()) {
        return predicate;
      }
      return predicate + "(" + String.join(", ", arguments) + ")";
    }

    @Override
    public boolean equals(Object obj) {
      if (!(obj instanceof Term))
        return false;
      Term other = (Term) obj;
      return predicate.equals(other.predicate) && arguments.equals(other.arguments);
    }

    @Override
    public int hashCode() {
      return Objects.hash(predicate, arguments);
    }
  }

  // Represents a Prolog rule (head :- body)
  public static class Rule {
    Term head;
    List<Term> body;

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

    @Override
    public String toString() {
      if (body.isEmpty()) {
        return head.toString() + ".";
      }
      return head.toString() + " :- " +
          body.stream().map(Term::toString).collect(Collectors.joining(", ")) + ".";
    }
  }

  // The knowledge base containing facts and rules
  public static class KnowledgeBase {
    List<Rule> rules = new ArrayList<>();
    Set<String> constants = new HashSet<>();

    public void addRule(Rule rule) {
      rules.add(rule);
      // Collect constants (non-variable terms)
      addConstants(rule.head);
      rule.body.forEach(this::addConstants);
    }

    private void addConstants(Term term) {
      for (String arg : term.arguments) {
        if (!isVariable(arg)) {
          constants.add(arg);
        }
      }
    }

    private boolean isVariable(String term) {
      return term.matches("[A-Z][a-zA-Z0-9_]*");
    }

    // Generate Java lambda predicates for each rule
    public Map<String, Predicate<String>> generatePredicates() {
      Map<String, Predicate<String>> predicates = new HashMap<>();

      // Group rules by predicate name
      Map<String, List<Rule>> rulesByPredicate = rules.stream()
          .collect(Collectors.groupingBy(rule -> rule.head.predicate));

      for (Map.Entry<String, List<Rule>> entry : rulesByPredicate.entrySet()) {
        String predicateName = entry.getKey();
        List<Rule> predicateRules = entry.getValue();

        // Create a compound predicate that checks if any rule matches
        Predicate<String> predicate = constant -> predicateRules.stream()
            .anyMatch(rule -> evaluateRule(rule, constant));

        predicates.put(predicateName, predicate);
      }

      return predicates;
    }

    private boolean evaluateRule(Rule rule, String constant) {
      // Handle facts (rules with empty body)
      if (rule.body.isEmpty()) {
        return rule.head.arguments.contains(constant);
      }

      // Handle rules with body
      // For simplicity, we'll substitute the constant for the variable and check if
      // all body terms are satisfied
      if (rule.head.arguments.size() == 1) {
        String variable = rule.head.arguments.get(0);
        return evaluateRuleBody(rule.body, variable, constant);
      }

      return false;
    }

    private boolean evaluateRuleBody(List<Term> body, String variable, String constant) {
      for (Term bodyTerm : body) {
        if (!evaluateBodyTerm(bodyTerm, variable, constant)) {
          return false;
        }
      }
      return true;
    }

    private boolean evaluateBodyTerm(Term term, String variable, String constant) {
      // Substitute variable with constant
      List<String> substitutedArgs = term.arguments.stream()
          .map(arg -> arg.equals(variable) ? constant : arg)
          .collect(Collectors.toList());

      Term substitutedTerm = new Term(term.predicate, substitutedArgs);

      // Check if this term is satisfied by any fact or rule
      return rules.stream().anyMatch(rule -> {
        if (rule.body.isEmpty()) { // It's a fact
          return rule.head.equals(substitutedTerm);
        } else { // It's a rule - recursively evaluate
          if (rule.head.predicate.equals(substitutedTerm.predicate) &&
              rule.head.arguments.size() == substitutedTerm.arguments.size()) {
            // Try to unify and evaluate
            return tryUnifyAndEvaluate(rule, substitutedTerm);
          }
        }
        return false;
      });
    }

    private boolean tryUnifyAndEvaluate(Rule rule, Term goal) {
      // Simple unification for single-argument predicates
      if (rule.head.arguments.size() == 1 && goal.arguments.size() == 1) {
        String ruleVar = rule.head.arguments.get(0);
        String goalArg = goal.arguments.get(0);

        if (isVariable(ruleVar)) {
          return evaluateRuleBody(rule.body, ruleVar, goalArg);
        } else {
          return ruleVar.equals(goalArg);
        }
      }
      return false;
    }
  }

  // Parser for Prolog syntax
  public static class PrologParser {

    public static KnowledgeBase parseProgram(String program) {
      KnowledgeBase kb = new KnowledgeBase();

      // Split into lines and process each rule/fact
      String[] lines = program.split("\n");
      for (String line : lines) {
        line = line.trim();
        if (line.isEmpty() || line.startsWith("%")) {
          continue; // Skip comments and empty lines
        }

        Rule rule = parseRule(line);
        if (rule != null) {
          kb.addRule(rule);
        }
      }

      return kb;
    }

    private static Rule parseRule(String line) {
      // Remove trailing period
      if (line.endsWith(".")) {
        line = line.substring(0, line.length() - 1);
      }

      if (line.contains(":-")) {
        // It's a rule
        String[] parts = line.split(":-", 2);
        Term head = parseTerm(parts[0].trim());
        List<Term> body = parseBodyTerms(parts[1].trim());
        return new Rule(head, body);
      } else {
        // It's a fact
        Term head = parseTerm(line.trim());
        return new Rule(head, new ArrayList<>());
      }
    }

    private static Term parseTerm(String termStr) {
      termStr = termStr.trim();

      if (termStr.contains("(")) {
        int parenIndex = termStr.indexOf("(");
        String predicate = termStr.substring(0, parenIndex);
        String argsStr = termStr.substring(parenIndex + 1, termStr.lastIndexOf(")"));

        List<String> args = new ArrayList<>();
        if (!argsStr.trim().isEmpty()) {
          args = Arrays.stream(argsStr.split(","))
              .map(String::trim)
              .collect(Collectors.toList());
        }

        return new Term(predicate, args);
      } else {
        // No arguments
        return new Term(termStr, new ArrayList<>());
      }
    }

    private static List<Term> parseBodyTerms(String bodyStr) {
      List<Term> terms = new ArrayList<>();
      String[] termStrs = bodyStr.split(",");

      for (String termStr : termStrs) {
        terms.add(parseTerm(termStr.trim()));
      }

      return terms;
    }
  }

  public static void main(String[] args) {
    // Sample Prolog program
    String prologProgram = """
        % Facts about jobs
        have_job(aaron).
        have_job(tony).
        job_pays(tony).

        % Facts about possessions and money
        have_possessions(mike).
        have_kidney(jeremy).
        have_money(gareth).

        % Rules for having money
        have_money(X) :- have_job(X), job_pays(X).
        have_money(X) :- can_sell_kidney(X).
        have_money(X) :- can_sell_possessions(X).

        % Rules for selling things
        can_sell_possessions(X) :- have_possessions(X).
        can_sell_kidney(X) :- have_kidney(X).

        % Main rule
        go_hunt(X) :- have_money(X).
        """;

    System.out.println("Original Prolog Program:");
    System.out.println(prologProgram);
    System.out.println("=".repeat(60));

    // Parse the Prolog program
    KnowledgeBase kb = PrologParser.parseProgram(prologProgram);

    System.out.println("Parsed Rules:");
    kb.rules.forEach(System.out::println);
    System.out.println();

    System.out.println("Constants found: " + kb.constants);
    System.out.println();

    // Generate Java lambda predicates
    Map<String, Predicate<String>> predicates = kb.generatePredicates();

    System.out.println("Generated Predicates: " + predicates.keySet());
    System.out.println();

    // Find all who can go hunting
    System.out.println("\n" + "=".repeat(60));
    System.out.println("HUNTING BUDDIES:");
    Predicate<String> canGoHunt = predicates.get("go_hunt");
    if (canGoHunt != null) {
      List<String> huntingBuddies = kb.constants.stream()
          .filter(canGoHunt)
          .collect(Collectors.toList());

      System.out.println("People who can go hunting: " + huntingBuddies);
    } else {
      System.out.println("No go_hunt predicate found!");
    }
  }
}