class DatalogEngine { constructor() { this.facts = {}; this.rules = {};…
- User
class DatalogEngine { constructor() { this.facts = {}; this.rules = {}; this.resultsCache = {}; }
addFact(predicate, ...args) { if (!this.facts[predicate]) { this.facts[predicate] = []; } this.facts[predicate].push(args); }
addRule(headPredicate, headArgs, body) { if (!this.rules[headPredicate]) { this.rules[headPredicate] = []; } this.rules[headPredicate].push({ headArgs, body }); }
query(queryPredicate, ...queryArgs) { const cacheKey = JSON.stringify([queryPredicate, queryArgs]); if (this.resultsCache[cacheKey]) { return this.resultsCache[cacheKey]; }
let results = []; // Check if there are direct facts matching the query const facts = this.facts[queryPredicate] || []; for (let factArgs of facts) { const substitution = this.unify(queryArgs, factArgs); if (substitution) { results.push(this.applySubstitution(substitution, queryArgs)); } } // Apply rules iteratively until no more changes let changed = true; while (changed) { changed = false; // Use a stack to process rules const ruleStack = [...(this.rules[queryPredicate] || [])]; while (ruleStack.length) { const { headArgs, body } = ruleStack.pop(); for (let substitution of this.evaluateRule(body, {})) { // Apply the substitution to the head arguments of the rule const newResult = this.applySubstitution(substitution, headArgs); // If the result matches the query args (after applying the substitution), add it to the results if (this.unify(queryArgs, newResult)) { if ( !results.find( (result) => JSON.stringify(result) === JSON.stringify(newResult), ) ) { results.push(newResult); changed = true; } } } } } // Deduplicate results results = Array.from(new Set(results.map(JSON.stringify))).map(JSON.parse); this.resultsCache[cacheKey] = results; return results;}
unify(args1, args2, substitution = {}) { // Check if the arguments match for (let i = 0; i < args1.length; i++) { const arg1 = args1[i]; const arg2 = args2[i]; if (typeof arg1 === "string" && arg1.startsWith("?")) { // arg1 is a variable if (arg1 in substitution) { // Variable is already assigned, check if it matches with arg2 if (substitution[arg1] !== arg2) { return null; } } else { // Assign the variable substitution[arg1] = arg2; } } else if (typeof arg2 === "string" && arg2.startsWith("?")) { // arg2 is a variable if (arg2 in substitution) { // Variable is already assigned, check if it matches with arg1 if (substitution[arg2] !== arg1) { return null; } } else { // Assign the variable substitution[arg2] = arg1; } } else if (arg1 !== arg2) { // Both arguments are constants and they don't match return null; } } return substitution; }
applySubstitution(substitution, args) { return args.map((arg) => substitution[arg] || arg); }
evaluateRule(body, initialSubstitution) { if (body.length === 0) { return [initialSubstitution]; }
const [firstClause, ...restClauses] = body; const [predicate, ...clauseArgs] = firstClause; let newSubstitutions = []; if (predicate === "neg") { const [negatedPredicate, ...negatedArgs] = clauseArgs.flat(); if (this.rules[negatedPredicate]) { for (let rule of this.rules[negatedPredicate]) { const { headArgs, body } = rule; const factSubstitutions = this.evaluateRule( body, initialSubstitution, ); if (!factSubstitutions.some((substitution) => substitution)) { // All facts failed, so the negation succeeds newSubstitutions.push(initialSubstitution); } } } else { const facts = this.facts[negatedPredicate] || []; const factSubstitutions = facts.map((factArgs) => this.unify(negatedArgs, factArgs, { ...initialSubstitution }), ); if (!factSubstitutions.some((substitution) => substitution)) { // All facts failed, so the negation succeeds newSubstitutions.push(initialSubstitution); } } } else if (predicate in this.rules) { for (let rule of this.rules[predicate]) { const { headArgs, body } = rule; for (let substitution of this.evaluateRule(body, initialSubstitution)) { // const newResult = this.applySubstitution(substitution, headArgs); for (let sub of this.evaluateRule(restClauses, substitution)) { newSubstitutions.push(sub); } } } } else { const substitutedArgs = this.applySubstitution( initialSubstitution, clauseArgs, ); const facts = this.facts[predicate] || []; for (let factArgs of facts) { const substitution = this.unify(substitutedArgs, factArgs, { ...initialSubstitution, }); if (substitution) { for (let sub of this.evaluateRule(restClauses, substitution)) { newSubstitutions.push(sub); } } } } return newSubstitutions;} }
const datalog = new DatalogEngine();
Modify our code so that we can only query using defined rules, we should never be able to query facts directly.
Assistant
Here is the modified code that only allows querying using defined rules:
class DatalogEngine { constructor() { this.facts = {}; this.rules = {}; this.resultsCache = {}; } addFact(predicate, ...args) { // No change } addRule(headPredicate, headArgs, body) { // No change } query(queryPredicate, ...queryArgs) { const cacheKey = JSON.stringify([queryPredicate, queryArgs]); if (this.resultsCache[cacheKey]) { return this.resultsCache[cacheKey]; } let results = []; // Only check rules, do not check facts directly // const facts = this.facts[queryPredicate] || []; // for (let factArgs of facts) { // const substitution = this.unify(queryArgs, factArgs); // if (substitution) { // results.push(this.applySubstitution(substitution, queryArgs)); // } // } // Apply rules iteratively until no more changes let changed = true; while (changed) { changed = false; // Use a stack to process rules const ruleStack = [...(this.rules[queryPredicate] || [])]; while (ruleStack.length) { const { headArgs, body } = ruleStack.pop(); for (let substitution of this.evaluateRule(body, {})) { // Apply the substitution to the head arguments of the rule const newResult = this.applySubstitution(substitution, headArgs); // If the result matches the query args (after applying the substitution), add it to the results if (this.unify(queryArgs, newResult)) { if ( !results.find( (result) => JSON.stringify(result) === JSON.stringify(newResult), ) ) { results.push(newResult); changed = true; } } } } } // Deduplicate results results = Array.from(new Set(results.map(JSON.stringify))).map(JSON.parse); this.resultsCache[cacheKey] = results; return results; } // No other changes }The main change is removing the direct check of facts in the
query()method
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.