2d:null 2e:["$","title",null,{"children":"Canonicalization with Math.js | Jo Wood | Observable"}] 33:Tce8,const constantsToRHSFn = (() => { const isOperatorNode = math.isOperatorNode; const isConstantNode = math.isConstantNode; const isNegativeConstantNode = (node) => isOperatorNode(node) && node.fn === "unaryMinus" && isConstantNode(node.args[0]); const isSymbolNode = math.isSymbolNode; const isParenthesisNode = math.isParenthesisNode; const OperatorNode = math.OperatorNode; const ConstantNode = math.ConstantNode; const ParenthesisNode = math.ParenthesisNode; const SymbolNode = math.SymbolNode; const prunedLHS = (node, pruned) => { const pruneNode = (node) => isConstantNode(node) ? node : new ConstantNode(-node.args[0].value); if (isConstantNode(node) || isNegativeConstantNode(node)) { if (node.value !== 0) { pruned.push(pruneNode(node)); } return new ConstantNode(0); } else if (isParenthesisNode(node)) { return node; } else if (isOperatorNode(node) && node.isBinary()) { if (node.fn === "add") { if ( isConstantNode(node.args[0]) || isNegativeConstantNode(node.args[0]) ) { pruned.push(pruneNode(node.args[0])); return prunedLHS(node.args[1], pruned); } else if ( isConstantNode(node.args[1]) || isNegativeConstantNode(node.args[1]) ) { pruned.push(pruneNode(node.args[1])); return prunedLHS(node.args[0], pruned); } return new OperatorNode(node.op, node.fn, [ prunedLHS(node.args[0], pruned), prunedLHS(node.args[1], pruned) ]); } else if (node.fn === "subtract") { if ( isConstantNode(node.args[0]) || isNegativeConstantNode(node.args[0]) ) { pruned.push(pruneNode(node.args[0])); return new OperatorNode("-", "unaryMinus", [ prunedLHS(node.args[1], pruned) ]); } else if ( isConstantNode(node.args[1]) || isNegativeConstantNode(node.args[1]) ) { pruned.push(new ConstantNode(-pruneNode(node.args[1]).value)); return prunedLHS(node.args[0], pruned); } return new OperatorNode(node.op, node.fn, [ prunedLHS(node.args[0], pruned), prunedLHS(node.args[1], pruned) ]); } return node; } else if (isOperatorNode(node) && node.isUnary()) { return new OperatorNode(node.op, node.fn, [node.args[0]]); } else if (isSymbolNode(node)) { return node; } throw new Error(`Should not happen: ${node}`); }; const appendRHS = (node, pruned) => { for (const term of pruned) { if (term.value > 0) { node = new OperatorNode("-", "subtract", [node, term]); } else { node = new OperatorNode("+", "add", [ node, new ConstantNode(-term.value) ]); } } return node; }; const splitConditional = (node) => { if (isOperatorNode(node) && node.op === "<") { const terms = []; const a0 = prunedLHS(node.args[0], terms); const a1 = appendRHS(node.args[1], terms); return new OperatorNode(node.op, node.fn, [a0, a1]); } else { throw new Error(`Only works with < as top node ${node.fn}`); } }; return splitConditional; })();34:T85b,function extractLHS(acc, rootLhs) { const stack = [rootLhs]; while (stack.length) { const lhs = stack.pop(); // Parentheses do not change the expression's meaning. if (lhs.isParenthesisNode) { stack.push(lhs.content); } else if ( lhs.isOperatorNode && lhs.op === "-" && lhs.fn === "unaryMinus" && lhs.args[0].isConstantNode && lhs.args[0].value === 0 ) { // Ignore negative zero. } else if (lhs.isConstantNode && lhs.value === 0) { // Ignore zero. } else if (lhs.isOperatorNode && lhs.op === "+") { stack.push(lhs.args[0]); stack.push(lhs.args[1]); } else if ( lhs.isOperatorNode && lhs.op === "-" && lhs.fn !== "unaryMinus" ) { stack.push(lhs.args[0]); const rhs = extractLHS([], lhs.args[1]); if (rhs.length !== 1) { throw new Error("Unexpected complexity for negated expression"); } acc.push({ coef: -rhs[0].coef, name: rhs[0].name }); } else if (lhs.isSymbolNode) { acc.push({ coef: 1, name: lhs.name }); } else if ( lhs.isOperatorNode && lhs.op === "-" && lhs.fn === "unaryMinus" && lhs.args[0].isSymbolNode ) { acc.push({ coef: -1, name: lhs.args[0].name }); } else if (lhs.isOperatorNode && lhs.op === "*") { if (lhs.args[1].isSymbolNode) { let value; if (lhs.args[0].isConstantNode) { value = lhs.args[0].value; } else if ( lhs.args[0].isOperatorNode && lhs.args[0].fn === "unaryMinus" && lhs.args[0].args[0].isConstantNode ) { value = -lhs.args[0].args[0].value; } else { throw new Error(`Must be constant: ${lhs.args[0].toString()}`); } acc.push({ coef: value, name: lhs.args[1].name }); } else { throw new Error(`Cannot extract term from ${lhs.toString()}`); } } else { throw new Error(`Cannot extract coefficients from ${lhs.toString()}`); } } return acc; }35:T53e,const extractCases = [ { expression: "4x <= 6", expected: { vars: [{name: "x", coef: 4}], bounds: {upper: 6} } }, { expression: "3x + 5 <= 2x + 9", expected: { vars: [{name: "x", coef: 1}], bounds: {upper: 4} } }, { expression: "4x + 6(y + 4)5 >= -6", expected: { vars: [ {name: "x", coef: 4}, {name: "y", coef: 30} ], bounds: {lower: -126} } }, { expression: "4x - 2y >= 0", expected: { vars: [ {name: "x", coef: 4}, {name: "y", coef: -2} ], bounds: {lower: 0} } }, { expression: "x + y == 0", expected: { vars: [ {name: "x", coef: 1}, {name: "y", coef: 1} ], bounds: {lower: 0, upper: 0} } }, { expression: "4x - 2y - z >= 0", expected: { vars: [ {name: "x", coef: 4}, {name: "y", coef: -2}, {name: "z", coef: -1} ], bounds: {lower: 0} } }, { expression: "0 <= -2x", expected: { vars: [{name: "x", coef: 2}], bounds: {upper: 0} } }, { expression: "0 == 0", expected: { vars: [], bounds: {lower: 0, upper: 0} } }, { expression: "0 * 0 * x >= 1", expected: { vars: [], bounds: {lower: 1} } } ];36:T43d,const normaliseExtract = ({vars, bounds}) => { const normaliseNumber = (value) => Object.is(value, -0) ? 0 : value; return { vars: vars .map(({name, coef}) => ({ name, coef: normaliseNumber(coef) })) .sort((a, b) => a.name.localeCompare(b.name)), bounds: Object.fromEntries( ["lower", "upper"] .filter((key) => bounds[key] !== undefined) .map((key) => [key, normaliseNumber(bounds[key])]) ) }; }; const extractTestResults = extractCases.map(({expression, expected}) => { try { const actual = normaliseExtract(extract(expression)); const normalisedExpected = normaliseExtract(expected); const passed = JSON.stringify(actual) === JSON.stringify(normalisedExpected); return { expression, passed, expected: formatExtract(normalisedExpected), actual: formatExtract(actual) }; } catch (error) { return { expression, passed: false, expected: formatExtract(normaliseExtract(expected)), actual: `Error: ${error.message}` }; } });37:[] 31:{"id":"9e2f2fba2ba3ac98","slug":"canonicalization-with-math-js","title":"Canonicalization with Math.js","thumbnail":"c8507384b248d71d6720f76acf1967404e4d013ac9261a702a6a8391248472f9","access_level":"unlisted","create_time":"$D2026-09-08T08:19:18.290Z","update_time":"$D2026-09-08T12:17:43.637Z","view_time":null,"first_public_time":null,"has_unpublished_edits":null,"fork":true,"stars":0,"starred":false,"owner":{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024"},"version":2937,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null}],"members":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Canonicalization with Math.js","cells":[{"id":2526,"value":"# Canonicalization with Math.js\n_This is a fork of Tom Larkworthy's [Canonicalization with Math.js notebook](https://old.observablehq.com/@tomlarkworthy/glpk-canonicalization) that is Observable 2.0 compatible. The content below is Tom's with some minor changes to improve clarity or efficiency._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":0,"value":"I want to get expressions like ${tex`(x_2 - x_1) * 4 \\gt x_1 + 1`}, into _a) into a specialized canonical form for linear programming:-\n\n${tex`-5 x_1 + 4 x_2 \\geq 1`}\n\nin general\n\n${tex`c_1x_1 + ... + c_nx_n \\geq c_0`}\n\nMath.js has the power, but does not ship with enough rewrite rules by default. So this notebook is about adding the required rules to create a canonicalization routine.\n\nThere is a fuzzer to help stress test these routines https://observablehq.com/@tomlarkworthy/expression-fuzzer","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"import * as math from \"npm:mathjs@9.4.4\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"### Simplify Rule Syntax: Custom simplification rules\n- ‘n’ - matches any Node\n- ‘c’ - matches any ConstantNode\n- ‘v’ - matches any Node that is not a ConstantNode","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":322,"value":"### Expand brackets","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":325,"value":"const expandBrackets = [\n {l: \"0 * n\", r: \"0\"},\n {l: \"-(-n)\", r: \"n\"},\n {l: \"-(c*n)\", r: \"-c * n\"},\n {l: \"-(n1 + n2)\", r: \"-n1 - n2\"},\n {l: \"-(n1 - n2)\", r: \"-n1 + n2\"},\n {l: \"n - (n1 + n2)\", r: \"n - n1 - n2\"},\n {l: \"n - (n1 - n2)\", r: \"n - n1 + n2\"},\n {l: \"c * (n1 + n2)\", r: \"c * n1 + c * n2\"},\n {l: \"c * (n1 - n2)\", r: \"c * n1 - c * n2\"},\n {l: \"-c * (n1 + n2)\", r: \"-c * n1 - c * n2\"},\n {l: \"-c * (-n1 - n2)\", r: \"c * n1 + c * n2\"},\n {l: \"-c * (n1 - n2)\", r: \"-c * n1 + c * n2\"}\n];","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2174,"value":"### Multiply out constants","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2177,"value":"const multiplyOut = [math.simplify.simplifyCore]","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":572,"value":"### Constants to RHS","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2369,"value":"$33","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":640,"value":"### Variables to LHS","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":642,"value":"const complexityToLHS = [\n {l: \"n1 < n2 + v\", r: \"-v + n1 < n2\"},\n {l: \"n1 < n2 - v\", r: \"v + n1 < n2\"},\n {l: \"-n1 < v - n2\", r: \"-v - n1 < -n2\"},\n {l: \"n1 < v - n2\", r: \"-v + n1 < -n2\"}\n //{ l: 'v1 < v2', r: 'v1 - v2 < 0' }\n];","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1071,"value":"### Add zero to RHS\n\nIt's quite dangerous introducing terms as it often causes loop, so we do this once other optimizations are exhausted.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1075,"value":"const addZeroToRHS = (exp) => {\n exp = typeof exp === \"string\" ? math.parse(exp) : exp;\n\n if (\n exp.op === \"<\" &&\n (exp.args[1].isSymbolNode ||\n (exp.args[1].fn === \"unaryMinus\" && exp.args[1].args[0].isSymbolNode) ||\n (exp.args[1].op === \"*\" &&\n exp.args[1].args[0].isConstantNode &&\n exp.args[1].args[1].isSymbolNode) ||\n (exp.args[1].op === \"*\" &&\n exp.args[1].args[0].fn === \"unaryMinus\" &&\n exp.args[1].args[0].args[0].isConstantNode &&\n exp.args[1].args[1].isSymbolNode))\n ) {\n const RHS = exp.args[1];\n const LHS = exp.args[0];\n const newRHS = new math.ConstantNode(0);\n const newLHS =\n exp.args[1].fn === \"unaryMinus\" && exp.args[1].args[0].isSymbolNode\n ? new math.OperatorNode(\"+\", \"add\", [LHS, RHS.args[0]])\n : new math.OperatorNode(\"-\", \"subtract\", [LHS, RHS]);\n const result = new math.OperatorNode(\"<\", \"smaller\", [newLHS, newRHS]);\n return result\n } else {\n return exp;\n }\n};","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1809,"value":"### Simplify Step\n\nNote that < causes problems with zeros, so we have to simplify on each AST branch seperately.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1753,"value":"const simplifyStep = (exp) => {\n // Simplify gets confused by comparison operators, better to run it on each child separately\n const customSimplify = (exp) =>\n math.simplify(\n math.simplify(exp, math.simplify.rules, {}, {exactFractions: false}),\n [...expandBrackets, ...multiplyOut]\n );\n\n if (exp.isOperatorNode && exp.op === \"<\") {\n return exp.map(customSimplify);\n } else {\n return customSimplify(exp);\n }\n};","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":761,"value":"### Step 2\n\nAim of step 2 is to pull constants to RHS, simplify them, and push complex expression to LHS, and repeat.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"const step2 = (initial) => {\n const seen = new Set();\n let exp = initial;\n\n while (!seen.has(exp.toString())) {\n seen.add(exp.toString());\n const updateRHS = math.simplify(exp, [...expandBrackets, constantsToRHSFn]);\n const rhs = simplifyStep(updateRHS);\n const updateLHS = math.simplify(rhs, complexityToLHS);\n exp = addZeroToRHS(updateLHS);\n }\n return math.simplify(exp, expandBrackets);\n};","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":567,"value":"### Canonicalize","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"const withOperator = (ast, {op, fn}) => {\n const result = ast.clone();\n result.op = op;\n result.fn = fn;\n return result;\n};\n\nconst canonicalize = (expression) => {\n const ast = math.parse(expression);\n const originalOperator = {op: ast.op, fn: ast.fn};\n const leq = withOperator(ast, {op: \"<\", fn: \"smaller\"});\n const simplified = isCanonical(leq) ? leq : step2(leq);\n\n return withOperator(simplified, originalOperator);\n};","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1571,"value":"### isCanonical (special case short circuit)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1573,"value":"const isCanonical = (exp) => {\n if (!exp.isOperatorNode) {\n return false;\n }\n\n try {\n // canonicalize temporarily represents every comparison using \"<\".\n // We only need to check that the RHS is a numeric constant here.\n extractRHS(\"<=\", exp.args[1]);\n extractLHS([], exp.args[0]);\n return true;\n } catch {\n return false;\n }\n};","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1257,"value":"### Extract\n\nThis applies our custom canonicalization and converts to a JSON:\n\n~~~js\n{\n vars: [\n {name: \"x1\", coef: 3},\n {name: \"x2\", coef: 1}\n ],\n bounds: {upper: 2}\n}\n~~~","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1261,"value":"const extract = (expression) => {\n const canonical = canonicalize(expression);\n\n if (!canonical.isOperatorNode) {\n throw new Error(`Expected a comparison: ${expression}`);\n }\n\n return {\n vars: extractLHS([], canonical.args[0]),\n bounds: extractRHS(canonical.op, canonical.args[1])\n };\n};","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1274,"value":"const extractRHS = (op, rhs) => {\n let value = undefined;\n if (rhs.isConstantNode) {\n value = rhs.value;\n } else if (rhs.fn === \"unaryMinus\" && rhs.args[0].isConstantNode) {\n value = -rhs.args[0].value;\n } else {\n throw new Error(`Must be constant: ${rhs.toString()}`);\n }\n if (op === \"<=\") {\n return {\n upper: value\n };\n } else if (op === \">=\") {\n return {\n lower: value\n };\n } else if (op === \"==\") {\n return {\n lower: value,\n upper: value\n };\n } else {\n throw new Error(`Unsupported op ${op}`);\n }\n};","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1298,"value":"$34","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2528,"value":"## Tests\n\n(These are not dependent on any external test frameworks)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2529,"value":"$35","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2530,"value":"$36","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2533,"value":"const formatExtract = ({vars, bounds}) => {\n const terms = vars\n .filter(({coef}) => coef !== 0)\n .map(({name, coef}, index) => {\n const sign = coef < 0 ? \"−\" : \"+\";\n const magnitude = Math.abs(coef);\n const term = magnitude === 1 ? name : `${magnitude}${name}`;\n\n if (index === 0) {\n return coef < 0 ? `${sign}${term}` : term;\n }\n\n return `${sign} ${term}`;\n });\n\n const lhs = terms.join(\" \") || \"0\";\n const {lower, upper} = bounds;\n\n if (lower !== undefined && upper !== undefined) {\n return lower === upper\n ? `${lhs} = ${lower}`\n : `${lower} ≤ ${lhs} ≤ ${upper}`;\n }\n\n if (lower !== undefined) {\n return `${lhs} ≥ ${lower}`;\n }\n\n if (upper !== undefined) {\n return `${lhs} ≤ ${upper}`;\n }\n\n return lhs;\n};","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2531,"value":"display(\n Inputs.table(extractTestResults, {\n columns: [\"passed\", \"expression\", \"expected\", \"actual\"],\n header: {\n passed: \"Passed?\",\n expression: \"Expression\",\n expected: \"Expected\",\n actual: \"Actual\"\n }\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2532,"value":"const failedExtractTests = extractTestResults.filter(({passed}) => !passed);\n\nif (failedExtractTests.length) {\n throw new Error(\n `${failedExtractTests.length} extract test${\n failedExtractTests.length === 1 ? \"\" : \"s\"\n } failed`\n );\n}\n\ndisplay(\"All extract tests passed.\");","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W37","stdlib":"2","titling":"auto"}} 32:"$31:body"