Minimal Logic Programming Engine in JavaScript

This challenge asks you to build a simplified logic programming engine in JavaScript, inspired by Prolog. Logic programming allows you to define facts and rules, and then query the system to infer new knowledge based on those definitions. This is useful for tasks like knowledge representation, expert systems, and automated reasoning.

Problem Description

You are to implement a basic logic programming engine that can:

1. Define Facts: Facts are simple assertions about the world, represented as predicates with arguments. For example, parent(john, mary).
2. Define Rules: Rules define relationships between predicates. They have a head (the conclusion) and a body (the conditions that must be true for the conclusion to be true). For example, grandparent(X, Z) :- parent(X, Y), parent(Y, Z). :- signifies "if". X, Y, and Z are variables.
3. Query: Given a query (a predicate with arguments, some of which may be variables), the engine should attempt to prove the query by searching through the defined facts and rules.
4. Variable Binding: The engine must be able to bind variables to values during the proof process. When a variable is bound, it represents a specific value throughout the remainder of the query.
5. Unification: The core of the engine is unification, the process of matching terms (predicates, arguments, variables) to determine if they are equivalent. Unification should handle variables and ensure that variables are bound consistently.

Expected Behavior:

The engine should return a list of bindings (variable-value pairs) that satisfy the query. If the query cannot be proven, it should return an empty list.

Edge Cases to Consider:

• No Facts/Rules: Handle the case where no facts or rules are defined.
• Unsatisfiable Queries: Queries that cannot be proven should return an empty list.
• Conflicting Facts/Rules: The engine should not crash if there are conflicting facts or rules. It should simply return an empty list if a contradiction is encountered.
• Variable Binding Conflicts: Ensure that variable bindings are consistent throughout the proof process. A variable should not be bound to multiple different values.
• Empty Arguments: Handle predicates with no arguments.

Examples

Example 1:

Facts:
parent(john, mary).
parent(john, peter).
parent(mary, ann).

Rule:
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Query: grandparent(john, Z).

Output: [ { Z: 'mary' }, { Z: 'peter' } ]
Explanation: The engine finds two bindings for Z: 'mary' and 'peter', because john is a parent of mary and john is a parent of peter, and mary is a parent of ann.

Example 2:

Facts:
likes(john, pizza).
likes(mary, pasta).

Query: likes(john, X).

Output: [ { X: 'pizza' } ]
Explanation: The engine finds that X should be 'pizza' to satisfy the query.

Example 3: (Edge Case - No Solution)

Facts:
parent(john, mary).

Rule:
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Query: grandparent(john, Z).

Output: []
Explanation: There is no 'Y' such that parent(john, Y) is true, and no 'Z' such that parent(Y, Z) is true. Therefore, the query cannot be proven.

Constraints

• Input Format: Facts and rules should be represented as strings. Predicates are strings, and arguments can be strings or variables (represented by strings starting with an uppercase letter).
• Variable Representation: Variables must be represented as strings starting with an uppercase letter (e.g., "X", "Y", "Z").
• Performance: The engine should be able to handle a reasonable number of facts and rules (e.g., up to 100). Optimization is not the primary focus, but avoid excessively inefficient algorithms.
• No External Libraries: You are not allowed to use external libraries for this challenge. Implement the core logic yourself.

Notes

• Start by implementing the unification algorithm. This is the foundation of the engine.
• Consider using recursion to implement the proof search.
• Think about how to represent the knowledge base (facts and rules) in a suitable data structure.
• The engine does not need to support complex data types or arithmetic operations. Focus on the core logic programming concepts.
• The order of bindings in the output list does not matter.
• The engine should be able to handle queries with multiple variables.
• Consider using a depth-first search strategy for the proof search.