Skip to content
Snippets Groups Projects
Select Git revision
  • 4e41cf3002917a2d15a27615759251eaf37f69b0
  • master default protected
2 results

simplifier.js

Blame
  • 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}`));