2f:T490,md`In algebra, a **group** is a set ${tex`G`} along with an operation ${tex`\cdot`} that satisfies the following four properties: 1. **Closure**: For every pair of elements ${tex`a, b \in G`}, the result of the operation ${tex`a \cdot b`} also belongs to ${tex`G`}. ${tex`a \cdot b \in G`} 2. **Associativity**: For any three elements ${tex`a, b, c \in G`}, the operation ${tex`\cdot`} is associative. ${tex`(a \cdot b) \cdot c = a \cdot (b \cdot c)`} 3. **Identity Element**: There exists an element ${tex`e \in G`} such that, for every element ${tex`a \in G`}, the equation ${tex`e \cdot a = a \cdot e = a`} holds. ${tex`\exists e \in G, \forall a \in G, e \cdot a = a \cdot e = a`} 4. **Inverse Element**: For each element ${tex`a \in G`}, there exists an element ${tex`a^{-1} \in G`} such that ${tex`a \cdot a^{-1} = a^{-1} \cdot a = e`}, where ${tex`e`} is the identity element. ${tex`\forall a \in G, \exists a^{-1} \in G, a \cdot a^{-1} = a^{-1} \cdot a = e`} If the operation is also commutative, that is ${tex`a \cdot b = b \cdot a`} for all ${tex`a, b \in G`}, then the group is said to be an **abelian group** or **commutative group**.`30:T5e7,{ function matchAndRewrite(expr, rule) { // If the expression is a symbol or a number, it can only match a placeholder if (expr.symbol || expr.number) { return { match: expr.placeholder === rule.placeholder, expr }; } // Otherwise, try to match based on the operation if (expr.operation && rule.operation && expr.operation === rule.operation) { const leftResult = matchAndRewrite(expr.left, rule.left); const rightResult = matchAndRewrite(expr.right, rule.right); if (leftResult.match && rightResult.match) { // Both sides match, so rewrite based on the rule return { match: true, expr: { operation: rule.right.operation, left: rightResult.expr, right: leftResult.expr } }; } } // If no match, return the original expression and indicate no match return { match: false, expr }; } // Example usage const expression = { operation: "+", left: { symbol: "a" }, right: { operation: "*", left: { symbol: "b" }, right: { symbol: "c" } } }; const rule = { operation: "+", left: { placeholder: "A" }, right: { placeholder: "B" } }; const { match, expr } = matchAndRewrite(expression, rule); if (match) { return [`Match found! Rewritten expression: }`, expr]; } else { return [`No match found. Original expression: `, expr]; } }31:T80d,lel2 = { // Function to check if an S-expression is a placeholder function isPlaceholder(sexp) { return typeof sexp === "string" && sexp.startsWith("_"); } // Function to recursively match an expression against a rule function match(expr, rule, mapping) { //console.log( "Matching:", JSON.stringify(expr), "against", JSON.stringify(rule) ); if (isPlaceholder(rule)) { mapping[rule] = expr; return true; } if (Array.isArray(expr) && Array.isArray(rule)) { if (expr[0] !== rule[0]) return false; for (let i = 1; i < rule.length; i++) { if (!match(expr[i], rule[i], mapping)) { return false; } } return true; } return expr === rule; } function replace(rule, mapping, strategy) { if (isPlaceholder(rule)) { return mapping[rule]; } if (Array.isArray(rule)) { const replaced = [rule[0]]; for (let i = 1; i < rule.length; i++) { replaced.push(replace(rule[i], mapping, strategy)); } return replaced; } return rule; } // Function to apply a rule to an expression function applyRule(expr, rule, strategy = {}) { let output = null; let modifiedRule = [...rule]; // Clone the rule to avoid modifications //console.log("Applying rule to expr:", JSON.stringify(expr)); if (strategy.direction === "backward") { [modifiedRule[1], modifiedRule[2]] = [modifiedRule[2], modifiedRule[1]]; } const mapping = {}; if (match(expr, modifiedRule[1], mapping)) { //console.log("Match found:", JSON.stringify(mapping)); output = replace(modifiedRule[2], mapping, strategy); } if (strategy.count === "all" && Array.isArray(expr)) { for (let i = 0; i < expr.length; i++) { const subOutput = applyRule(expr[i], rule, strategy); if (subOutput !== null) { expr[i] = subOutput; } } } return output || expr; } return { applyRule, match }; // Should output ["+',['*', 'b', 'c'],'a'] }32:Td3e,lel = { function parseExpression(tokens, index) { let exprStack = []; let previousToken = null; // console.log(`--- Entering parseExpression ---`); // console.log(`Initial index: ${index}`); while (index < tokens.length) { let token = tokens[index]; index++; // console.log(`Processing token: ${token}`); // console.log(`Current index after increment: ${index}`); if (token === "(") { // console.log(`Detected open parenthesis. Recursing...`); const result = parseExpression(tokens, index); exprStack.push(result.expression); index = result.newIndex; // console.log(`Returning from recursion. Updated index: ${index}`); } else if (token === ")") { // console.log(`Detected close parenthesis. Breaking loop.`); break; } else if (infixOperators.includes(token)) { // console.log(`Detected infix operator: ${token}`); exprStack.push(token); } else if ( prefixOperators.includes(token) && (!previousToken || infixOperators.includes(previousToken)) ) { // console.log(`Detected prefix operator: ${token}`); const operand = tokens[index]; index++; exprStack.push([token, operand]); } else { // console.log(`Detected operand or unknown token: ${token}`); exprStack.push(token); } // console.log( // `Expression stack after processing ${token}: ${JSON.stringify( // exprStack // )}` // ); previousToken = token; } // console.log(`--- Exiting parseExpression ---`); let currentExpr = exprStack.pop(); while (exprStack.length > 0) { const operator = exprStack.pop(); let leftOperand; if (exprStack.length > 0) { leftOperand = exprStack.pop(); currentExpr = [operator, leftOperand, currentExpr]; } else { currentExpr = [operator, currentExpr]; } } return { expression: currentExpr, newIndex: index }; } /** * Parses a string expression and returns it in S-expression format. * * @func * @sig String -> Array * @param {TemplateStringsArray} strings - The string literals. * @param {...*} values - The string values. * @return {Array} The parsed expression in S-expression format. * @throws {Error} Throws an error if the expression cannot be parsed. * @example * * sExp`(a + b)^2`; //=> ["^", ["+", "a", "b"], "2"] * sExp`a + b`; //=> ["+", "a", "b"] * sExp`!a`; //=> ["!", "a"] */ function sExp(strings, ...values) { const input = String.raw(strings, ...values); //console.log(`Starting to process input: ${input}`); let tokens = input .split(/\s+/) .join("") .split(/(>>>?|&&|\|\||>=?|<=?|[+\-*/()^><=|&!])/) .filter((t) => t.length > 0); //console.log(`Initial tokens: ${JSON.stringify(tokens)}`); let index = 0; try { const result = parseExpression(tokens, index); return result.expression; } catch (error) { throw new Error(`Error parsing expression: ${error.message}`); } } var infixOperators = [ "+", "-", "*", "/", "^", "=>", "=<", ">>", ">>>", ":>", "<", "|", "&", "||", "&&", ">=" ]; var prefixOperators = ["!", "-"]; return { sExp }; }33:T427,{ function runTests() { const testCases = [ { input: "(a + b)^2", output: ["^", ["+", "a", "b"], "2"] }, { input: "a + b", output: ["+", "a", "b"] }, { input: "!a", output: ["!", "a"] }, { input: "-a", output: ["-", "a"] }, { input: "+a", output: ["+", "a"] }, { input: "a >= b", output: [">=", "a", "b"] }, { input: "a >> b", output: [">>", "a", "b"] }, { input: "a & b | c", output: ["|", ["&", "a", "b"], "c"] }, { input: "a < b", output: ["<", "a", "b"] } ]; let markdownResults = "# Test Results\n\n"; for (const { input, output } of testCases) { const parsedOutput = sExp`${input}`; if (deepEqual(parsedOutput, output)) { markdownResults += `- **Test for '${input}'**: Passed\n`; } else { markdownResults += `- **Test for '${input}'**: Failed. Expected ${JSON.stringify( output )}, got ${JSON.stringify(parsedOutput)}.\n`; } } return markdownResults; } const mdResults = runTests(); return md`${mdResults}`; }34:T89d,/** * Tests whether two values are deeply equal using same-value equality. * * Two values are considered deeply equal iff 1) they are the same value, or * 2) they are both non-callable objects whose own, enumerable, string-keyed * properties are deeply equal. * * Caution: This function does not fully support circular references. Use this * function only if you are sure that at least one of the arguments has no * circular references. */ function deepEqual(x, y) { // If either x or y is not an object, then they are deeply equal iff they // are the same value. For our purposes, objects exclude functions, // primitive values, null, and undefined. if ( typeof x !== "object" || x === null || typeof y !== "object" || y === null ) { // We use Object.is() to check for same-value equality. To check for // strict equality, we would use x === y instead. return Object.is(x, y); } // Shortcut, in case x and y are the same object. Every object is // deeply equal to itself. if (x === y) return true; // Obtain the own, enumerable, string-keyed properties of x. We ignore // properties defined along x's prototype chain, non-enumerable properties, // and properties whose keys are symbols. const keys = Object.keys(x); // If x and y have a different number of properties, then they are not // deeply equal. if (Object.keys(y).length !== keys.length) return false; // For each own, enumerable, string property key of x: for (const key of keys) { // If key is not also an own enumerable property of y, or if x[key] and // y[key] are not themselves deeply equal, then x and y are not deeply // equal. Note that we don't just call y.propertyIsEnumerable(), // because y might not have such a method (for example, if it was // created using Object.create(null)), or it might not be the same // method that exists on Object.prototype. if ( !Object.prototype.propertyIsEnumerable.call(y, key) || !deepEqual(x[key], y[key]) ) { return false; } } // x and y have the same properties, and all of those properties are deeply // equal, so x and y are deeply equal. return true; }35:T52c,{ function runMatchTests() { let testResults = "# Match Function Tests\n\n"; const testCases = [ { expr: ["+", "a", "b"], rule: ["+", "_x", "_y"], expected: true }, { expr: ["+", "a", "b"], rule: ["*", "_x", "_y"], expected: false }, { expr: ["+", "a", ["*", "b", "c"]], rule: ["+", "_x", ["*", "_y", "_z"]], expected: true }, { expr: "a", rule: "_x", expected: true }, { expr: "a", rule: "a", expected: true }, { expr: "a", rule: "b", expected: false }, { expr: "a", rule: "_x", expected: true } ]; for (const { expr, rule, expected } of testCases) { const mapping = {}; const result = lel2.match(expr, rule, mapping); if (result === expected) { testResults += `- **Test for expr '${JSON.stringify( expr )}' and rule '${JSON.stringify(rule)}'**: Passed\n`; } else { testResults += `- **Test for expr '${JSON.stringify( expr )}' and rule '${JSON.stringify( rule )}'**: Failed. Expected ${expected}, got ${result}\n`; } if (result) { testResults += ` - Mapping: ${JSON.stringify(mapping)}\n`; } } return testResults; } const matchTestResults = runMatchTests(); return md`${matchTestResults}`; }36:[] 2d:{"title":"Group","cells":[{"id":0,"value":"# Group","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs"},{"id":17,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":23,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":165,"value":"applyRule = lel2.applyRule","pinned":true,"hidden":false,"mode":"ojs"},{"id":47,"value":"{\n const expr = [\"^\", [\"+\", \"a\", \"b\"], \"2\"];\n const rule = [\"=\", [\"^\", \"_A\", \"2\"], [\"*\", \"_A\", \"_A\"]];\n const strategy = { direction: \"forward\", count: \"all\" };\n\n //const newExpr = applyRule(expr, rule, strategy);\n //return JSON.stringify(newExpr);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":119,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":147,"value":"sExp = lel.sExp","pinned":true,"hidden":false,"mode":"ojs"},{"id":49,"value":"applyRule(\n applyRule(sExp`(a+b)^2`, sExp`(_A^2)=(_A*_A)`, {\n direction: \"forward\",\n count: 1\n }),\n sExp`(_A^2)=(_A*_A)`,\n {\n direction: \"backward\",\n count: 1\n }\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":62,"value":"JSON.stringify(sExp`(a + b)^2`)","pinned":true,"hidden":false,"mode":"ojs"},{"id":94,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":87,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":169,"value":"$35","pinned":true,"hidden":false,"mode":"ojs"},{"id":125,"value":"function stackToSExpression(exprStack, prefixOperators) {\n let currentExpr = exprStack.pop();\n while (exprStack.length > 0) {\n const operator = exprStack.pop();\n let leftOperand = exprStack.pop();\n\n if (\n Array.isArray(currentExpr) &&\n prefixOperators.includes(currentExpr[0])\n ) {\n // Handle prefix operators\n currentExpr = [currentExpr[0], currentExpr[1]];\n } else if (\n Array.isArray(leftOperand) &&\n prefixOperators.includes(leftOperand[0])\n ) {\n // Handle prefix operators\n currentExpr = [leftOperand[0], leftOperand[1], currentExpr];\n } else {\n // Handle binary operators\n currentExpr = [operator, leftOperand, currentExpr];\n }\n }\n return currentExpr;\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W36","stdlib":"1","titling":"auto"}