Select Git revision
simplifier.js
Brady James Garvin authored
simplifier.js 2.56 KiB
import {Expression} from './expressions.js';
function booleanAssignments(variables) {
const results = [];
for (let bits = 1 << variables.length; bits--;) {
const assignments = new Map();
for (let index = variables.length; index--;) {
assignments.set(variables[index].name, (bits >> index & 1) !== 0);
}
results.push(assignments);
}
return results;
}
function matches(expression, semantics, variables) {
const semanticsTakingMap = (assignments) => semantics(...variables.map((variable) => assignments.get(variable.name)));
for (const assignments of booleanAssignments(variables)) {
if (expression.evaluate(assignments) !== semanticsTakingMap(assignments)) {
return false;
}
}
return true;
}
function expressionsOfSize(environment, operatorCount) {
const results = [];
if (operatorCount === 0) {
for (const variable of environment.variables) {
results.push(variable);
}
} else {
for (const operator of environment.unaryOperators) {
for (const subexpression of expressionsOfSize(environment, operatorCount - 1)) {
results.push(new Expression(operator, [subexpression]));
}
}
for (let leftOperatorCount = 0; leftOperatorCount < operatorCount; ++leftOperatorCount) {
const rightOperatorCount = operatorCount - leftOperatorCount - 1;
for (const operator of environment.binaryOperators) {
for (const leftSubexpression of expressionsOfSize(environment, leftOperatorCount)) {
for (const rightSubexpression of expressionsOfSize(environment, rightOperatorCount)) {
results.push(new Expression(operator, [leftSubexpression, rightSubexpression]));
}
}
}
}
}
return results;
}
function expressionsUpToSize(environment, maximumOperatorCount) {
const results = [];
for (let operatorCount = 0; operatorCount <= maximumOperatorCount; ++operatorCount) {
results.push(...expressionsOfSize(environment, operatorCount));
}
return results;
}
export function simplify(semantics, environment, maximumOperatorCount) {
for (const expression of expressionsUpToSize(environment, maximumOperatorCount)) {
if (matches(expression, semantics, environment.variables)) {
return expression;
}
}
return undefined;
}
// for debugging in the console:
window.expressionsOfSize = expressionsOfSize;
window.expressionsUpToSize = expressionsUpToSize;
window.booleanAssignments = booleanAssignments;
window.matches = matches;
window.simplify = simplify;
window.logAll = (generator) => [...generator].map((expression) => console.log(`${expression}`));