Resolve order of operations conflict

[amyjko]

What's the problem?

When an expression has ambiguous evaluation order, it can be confusing how to resolve the conflict, since there are many possible ways to disambiguate:

1 + 2 - 3 ÷ 5

What's the design idea?

Add a conflict resolution for OrderOfOperations that generates all possible parenthetical disambiguation's of the expression to resolve the warning.

Who benefits?

Anyone looking for a quick fix to the problem.

Design specification

Design Draft 3

Current Design Idea

• Update the current alert to provide a brief introduction of how PEMDAS works
  • E.g. "I evaluate in reading order; traditionally mathematical expressions are evaluated in the order of Parenthesis, then Exponents, then Multiplication and Division, and finally Addition and Subtraction. A hand acyronym for memorizing this order of operations is PEMDAS. Do you want me to evaluate mathematical expressions using PEMDAS?"
• Offer an option (a button) to the user to use PEMDAS
  • if the button isn't clicked, make no changes. If the button is clicked, create a conflict resolution that modifies the selected expression to enforce OUPEMDAS order (Where O and U stand for Other things and U stands for Unary operators). It is not necessary to include descriptions of "other things" and unary operators within the description of PEMDAS to the client since it would basically be implementation details and some abstraction is always nice.
  • Here is an example of how OU-PEMDAS order can be enforced, taking the expression (2 + 3^2) - 4 ÷ 2
    1. evaluate expressions with parenthesis in order from left to right. Treat each expression created by user-added brackets as separate expressions. Evaluate 2 + 3^2 first.
    2. automatically add parenthesis around 3^2 and evaluate that expression.
    3. there is no multiplication or division so move onto adding and subtracting within the sub - expression 2 + 9
    4. use the result and put it back into the original equation and repeat steps a through d until there are no more manually added parenthesis by the user.
    5. look through the equation, and check for exponents. Repeat this step until there are no more exponents in the equation. Since there are no exponents in this example equation, we will move onto the next step.
    6. look through the equation, and check for multiplication and division and automatically generate parenthesis around them and evaluate them as sub-expressions. Repeat this step until there are no more multiplication or division operators in the equation. 9 - (4 ÷ 2) and evaluate (4 ÷ 2).
    7. look through the equation, and check for multiplication and division and automatically generate parenthesis around them and evaluate them as sub-expression. Repeat this step until there are no more addition and subtraction operators in the equation. Evaluate the equation of 9 - 2
• Upon clicking on a mathematical expression again after choosing to evaluate mathematical expressions using PEMDAS, offer a button to the user which changes mathematical expression evaluation order back to "in order".

Even in the case of operations being evaluated in-order, other things and unary operators should still be evaluated first to maintain consistency throughout Wordplay.

[Deleted-0970]

where can keira and I get started on doing issue #333? :)

[Deleted-0970]

We have some code, how can we test it out?

nvm we got it i think 👍

[amyjko]

The place to get started is to design this feature (see the TBD in the design spec section above), not by writing code.

If you're asking for feedback on code, the way to get feedback is to submit a draft pull request, per the dev wiki. But you should not be asking for feedback on code, because there's no design for this yet. We only write code for issues that have designs and have the buildable label.

If you're asking for how to test it, I'm unsure what you mean. Testing this would involve verifying that the feature you create works as intended (e.g., writing unit tests, manually testing the end-to-end behavior). But you can't do that, since we have no design yet, so we don't have a definition of what "done" would mean.

[Deleted-0970]

Hi, thank you for the clarification.

What do you believe is the best course of action to take? My current thoughts are deleting the branch and finding a different issue with a buildable tag or contacting a designer.

edit: current plan is to keep the branch as-is and start designing for this feature.

[amyjko]

I recommend finishing the work; design the feature, get it approved by me, then build.

[Deleted-0970]

Design Specification Draft 1

Current Design Idea

Take the String expression and recursively add parenthesis to generate all possible unique disambiguation's. Store said disambiguation's in a String array.

Example String array contents with 1 + 2 - 3 ÷ 5 as the parameter:

• (1 + 2) - 3 ÷ 5
• 1 + (2 - 3) ÷ 5
• 1 + 2 - (3 ÷ 5)
• (1 + 2 - 3) ÷ 5
• 1 + (2 - 3 ÷ 5)
• (1 + 2) - (3 ÷ 5)
• ((1 + 2) - 3) ÷ 5

Possible Questions and Concerns

• Will a string array be an appropriate return type?
• Since the method is likely to be recursive, would it be appropriate to have the method exhibit different behavior if the equation is too long?

[amyjko]

(Per the design wiki, design specifications go in the issue body, not in a comment. Can you move to the top, replacing the "TBD", so that it's always easily discoverable at the top? Thanks.)

Yay, I'm glad you're working on this! Feedback on the draft:

• What order would the possible combinations go in?
• What if the possible combinations are extremely large, since possibilities are exponential?
• What about combinations that are equivalent, e.g., (1 + 2) - (3 ÷ 5) is equivalent to (1 + (2)) - (3 ÷ 5)?
• The algorithm should probably not suggest wrapping literals,, e.g., (1) + (2) - (3), only binary operations
• No, a string array would not comply with the interface specified in Conflict.ts. It's supposed to return a Resolution, which returns a revised project. So the function will need to generate a new expression tree. But you can generate a tree with the function in parseExpression.ts

Let's keep iterating until the above is fully specified, then it'll be ready for building.

[Deleted-0970]

Hi Amy, not sure if GitHub gives notifications if a comment is edited but we made revisions to the design draft and put it at the top. Please take a look when you are available. Thank you! 😄

[amyjko]

Thanks @Deleted-09701! No notifications on edits, so commenting is always a good idea, also to provide context on the update, summarizing changes.

A few thoughts on the next iteration

• Why would there need to be a button for continuing to evaluate in order? That's what it does by default, so the button wouldn't do anything. Maybe you had some other behavior in mind?
• It seems like you went in a different direction, offering to recommend PEMDAS parentheses, rather than all possible groupings? That's a clever idea at first glance: it guarantees that the suggestions are minimal and provides a reasonably common suggestion. The problem is that there there are actually more than just one PEMDAS orderings. In the example in the design spec, 1 + 2 - 3 ÷ 5, you could have (1 + 2) - (3 ÷ 5), (1 + (2 - 3)) ÷ 5, ((1 + 2) - 3) ÷ 5); all are valid orders of evaluation. It's parentheses that make that possible, since they have precedence in PEMDAS evaluation order.
• "Store the option the user selected and continue evaluating equations in chosen manner" isn't quite right; the way that the evaluation order is stored is by updating the program. So it would be something more like "Creating a conflict resolution that modifies the selected expression to enforce PEMDAS order."

I will definitely guide you in development, once we get there. That's what I'm here for :)

[Deleted-0970]

Hi, thank you for your feedback and clarifications! I have updated the design draft accordingly based on my current understanding.

I am not sure what you mean by the second bullet point "there are actually more than just one PEMDAS orderings". Perhaps it is due to vague design specs, so I added an example of how I image PEMDAS working specifically.

please take a look when you have time! ty

[amyjko]

Thanks for the revision! It's getting clear to me know. I think I understand what you mean now by PEMDAS ordering; you're saying that for any given expression, there is an unambiguous single order of operations if PEMDAS is applied, and you want to generate parentheses that would enforce that order. I think you're right that there's a single PEMDAS ordering, though there are some subtleties that would require some decisions. For example, what about expressions that have non-PEMDAS operations?

1 + fun(2 3) ÷ 5

Would that be:

1 + (fun(2 3) ÷ 5)

OR

(1 + fun(2 3)) ÷ 5

You'd have to decide how to prioritize evaluation expressions, and all other non-PEMDAS expressions that are possible in Wordplay.

One simple way to prioritize is to say that anything that is not a PEMDAS operation has higher priority. So it would actually be OPEMDAS, where O stands for "other things" :) Applying that ordering would mean it would recommend this for the example above:

1 + (fun(2 3) ÷ 5)

[Deleted-0970]

Thank you for your feedback, we have made some adjustments to the design draft to include considerations of non-PEMDAS operations and unary operators. Please take a look. Thank you!

[amyjko]

I think this looks great! I'm going to mark this buildable. I'm here to support you in your implementation journey. Post any questions here and I'll try to answer in 24 hours.

[amyjko]

It's the end of Winter! Please provide an update on this issue, including:

• Whether you plan to continue work on it
• If you do not, 1) provide a detailed update of its status, 2) add any unfinished work, 3) list any any unmerged branches, and 4) unassign yourself, so someone else can take over the task. Please leave the issue in better shape than you found it, helping future contributors to start from where you left off.

If you do plan to continue work on it, carry on. Otherwise, thank you for your contributions!

[Deleted-0970]

Hi, we will not be continuing to work on this issue~

1. We have all of our work in a branch and the design report here. There is a recursive method of our idea on how it can be implemented. We have a blurb and we have a button, but the button is not connected to anything in the backend.
2. done
3. 333-resolve-order-of-operations-conflict
4. done

[amyjko]

Thank you for the update @Deleted-0970! I will unassign you both.

[YoungMo18]

Hi Amy, we are the team assigned to #333. Could you guide us or provide pointers on how to implement the design proposal into Wordplay's code?

[amyjko]

Happy to help!

Here are key concepts

• Programs are tree data structures, where each node is a particular language construct
• Generating possible fixes to this warning means generating alternative tree data structures that have parentheses placed in the correct position to enforce PEMDAS evaluation order
• Wordplay's tree data structures are made of subclasses of Node, and Expression in particular.
• The Expression you'll need to work with the most are BinaryEvaluate (the kind of node that generates this order of operations conflict) and Block (which represents a sequence of one or more parenthesized expression nodes).
• A Conflict is what other languages might call a warning or error, and represents some inconsistency or ambiguity in a Wordplay program. Conflicts can be "resolved" by offering a revised program that makes the conflict go away. You'll see in Conflict.ts that a Conflict can be defined to return 0 or more Resolution, which includes a localized description of the resolution and a function that, given some program Context, creates a revised Project with modified program text that resolves the conflict. See PossiblePII.ts for an example: it's mediator function returns a revision to the project that lists the warned text in the allowed text.
• To make a revised Project for this conflict, you'd need to update OrderOfOperations.ts:getConflictingNodes to return a list of Resolution (probably just one) that has a mediator that returns a revised BinaryEvaluate that has parentheses in the right place (Block nodes). The challenge here is writing a recursive function that scans the BinaryEvaluate with the conflict, and for each operation, replaces nodes with ambiguous evaluation order with Block to determine its evaluation order. You have to think of that algorithm, and then implement it in TypeScript, producing a revised BinaryEvaluate, and then replacing the current BinaryEvaluate with the conflict with the revised BinaryEvaluate.
• Creating a revised project is pretty easy: I've already written a utility method for that: Project.withRevisedNodes.

That should get you started! I'm happy to help you brainstorm algorithms if you get stuck. CSE 123 and 373 are your friends here!

[jibsamoun]

I did not complete this issue and will not be working on it going further. My team and I were only able to brainstorm the following pseudocode:

BASE CASE: If 0 operators are in original tree structure

Pseudo code: Look for parenthesis (blocks) —> individually iterate thru each of them (Put each into recursive method) Look for first ^ Yes —> Check if ONLY 1 operator is contained in single block Yes —> put block into new tree —> remove from OG tree Recursive back into function No —> Find left and right siblings (Make them a block) —> put block into new tree —> remove from OG tree Recursive back into function No —> Move to step 3 Look for * and / Yes —> Check if ONLY 1 operator is contained in single block Yes —> put block into new tree —> remove from OG tree Recursive back into function No —> Find left and right siblings (Make them a block) —> put block into new tree —> remove from OG tree Recursive back into function No —> Move to step 4 Look for + and - Yes —> Check if ONLY 1 operator is contained in single block Yes —> put block into new tree —> remove from OG tree Recursive back into function No —> Find left and right siblings (Make them a block) —> put block into new tree —> remove from OG tree Recursive back into function No —> Recursive back into function (MOST LIKELY HIT BASE CASE)

What Next?

1. Implement the base case where no operators are in the original tree. This is the simplest case and serves as a foundation for the recursive function.

2. Write a function to identify and handle parentheses. This function should: Detect blocks of expressions enclosed in parentheses. Recursively call the main function on each block.

3. Implement functions for each operator precedence level (exponentiation ^, multiplication and division * /, addition and subtraction + -). Each function should:

   • Identify operators within a block.
   • Check if only one operator is present in the block:
   • If yes, move the block to a new tree and remove it from the original tree.
   • If no, find left and right siblings, make them a block, and move to the new tree.
   • Recursively call the main function to handle the next operator in the reduced tree.

4. Implement the logic for constructing the new tree based on the blocks identified and moved from the original tree. Ensure that the new tree respects the order of operations

5. Write tests!

[amyjko]

Thank you for the update @jibsamoun. All, please unassign yourselves if you do not plan on working on this, so we know it is available for contributions.

[mehtparv]

Can I be assigned to this build and where can I find the necessary code to build on this?

[amyjko]

Sure! Assigned. See the comments above for details on where this is implemented, and feel free to ask further questions.

[mehtparv]

I've written pseudocode for the algorithm, but wasn't able to finish up the code. I plan to finish the code soon and work on it later, but I am willing to contribute with other people on this conflict. Here is the pseudocode.

Pseudocode:

Get the values of the tree using a preOrderTraversal.

Check if right node is parsable and if left node is parsable. Yes- Proceed onwards No - Return Error or message saying not possible.

Check If there is an element which is in a block. Yes - Check if there is a conflict in that block Yes - Solve the conflict in that block and assign that block to the new tree. Then go on to the other elements using the binary evaluate solver algorithm No - Go on to the other elements of the binary evaluate and use the binary evaluate solver algorithm No: Proceed on to the Binary Evaluate Solver Algorithm

Recurse for all instances of binary evaluate.

Return the new tree with the updated block structure.

Binary Evaluate Solver Algorithm:

Check if value of left node is Binary evaluate Yes - Get the fun of the left node and the operator of the fun node.
Compare the two operators and see which one ranks higher in terms of emdas (Exponents, Multiplication, Division, Addition, and Subtraction). If left is higher in terms of emdas than fun node - assign block to the left in the new tree. If the operator of the left node is lower in terms of emdas proceed onwards in the algorithm. If they are the same operator assign the block to the first occurrence in the new tree .

No - Proceed onwards to the fun and right nodes of the original tree.

Get the fun node operator of the tree

Check if the value of the right node is Binary Evaluate Yes - get the right node operator and compare it to the fun node operator of the tree.

       Check if right operator is ranked higher than left operator in terms of emdas 
        Yes - assign block in new tree to right node. 
         No - Leave as is

No - Leave as is.

Assign a block to the left, right, and fun nodes in the new tree

[joonpiter]

Hi @mehtparv , will you be going forward working on this issue?

[mehtparv]

I will be working on it remotely. I am willing to collaborate with other people as well.