Devlog #10

Completed domain.py

finished coding domain.py and tested about 20 test-cases on it. Completed debugging to finally finish domain calculation and start with Range.

I do not know what else to tell you all as it has been a few days of coding and debugging with different bugs surfacing like incorrect handling of undefined functions, normalizing output, handling union cases correctly, etc.

Union and Intersection of intervals

I have made the intersection function which takes intervals and unions them together. I am now working on the union function. I initially used recursion to do the job but that was incorrect that the better method was just to sort the intervals list and then use a simple loop to evaluate the union. Here is the issue i was facing:

[[A, B, C, D], E]
AUE-> False, BUE-> False, CUE-> True => [F, A, B, D]
union [F, A, B, D]-> FUA-> False => [[F,A], B, D]
again [F,A], B => FUB-> False, BUA-> False => [F, A, B] => union this list now => FUA-> False => [[F,A], B]
then again [F,A], B => FUB-> False, BUA-> False => [F, A, B] => FUA-> False => [[F,A], B]
this goes on and on infinitely
This is a problem of infinite recursion

It has been a tough journey

If you read my previous devlog, it almost feels like i was foreshadowing what was about to happen to me.

While making the solve_node function which would solve the inequality for x, i got lost in the mess of symbolic mathematics and started handling cases with fallbacks upon fallbacks. It has really a hot mess, I got to find out that there can be many types of questions and to solve every type of domain question, I would need fallback logic for every type of question which would mean I would have to encompass all the techniques in domain finding into the file and manage the interaction of the techniques and orchestrate them at a high level and basically making my own sympy (which took decades to build).

I even thought of quitting a few times and the project was basically at a halt for 1-2 days. I then decided to solve a simple domain question by hand to check what really are the steps of finding the domain of a function. I found out that my logic up until making the constraints was fine. The next steps were finding critical points for example: (x-2)(x+3)>0 would have critical points 2 and -3 (they are just the points where the function is zero). Now, I also know that critical points also occur when the sign of the function changes or when its nature changes (going from defined to undefined and vice-versa) so instead of making a symbolic critical point finding function I thought of a more brute force method.

If I have a number line (range of numbers) and i simply walk through them one by one, noting sign change between 2 numbers as a sign “there is a critical point here” and then use another function to basically go into each of those marked intervals and continuously half the interval (think of it as taking an interval and then zooming into the interval until you find the critical point) until about 9 decimal places (could be anything, it is just the amount of accuracy), you would get the critical point pretty accurately without having to solve anything using logic or symbolically, just substitute values of x. After finding the critical points, turning it into domain is as simple as just substituting points and see if the inequality holds.

Domain Calculation

Started the domain calculation file (domain.py) and made the function get_constraints() that recurses through the tree to look for domain restricting operators like /, sqrt, log, arcsin, etc. into a list. next steps are to solve each of the generated constraints (inequalities) and then combine them to get the domain for x (or any variable).

Currently working on trying to solve the inequalities but it is proving to be pretty difficult so it could take longer than usual.

AST Visualizer (continued)

Case-2

If the node is not a leaf (i.e. not a string) we will again check for 2 cases. the node can either have 1 child or 2 children. If there are 2 children then we have to make 2 recursive calls but if we have a single child then only one and the other stuff is pretty similar so I will only explain the case when there are 2 children. first of all, we unpack the node to get op, left and right. Now we call assign_positions with depth+1 (to effectively track each level we go down), on left and right and extract: x-position of children, id of children and the parameters that get updated (id_count and leaf_count). next, we used children’s x-position, average it to get the op’s x-position. We make the tree: tree[op_id] = {'label': op, 'x': op_x, 'depth': depth, 'children': [l_id, r_id]}. Now we increase the id_count by 1 but not the leaf_count as we have not encountered a leaf (I had made a mistake here and increased leaf_count in the case where the node is not a leaf because I had named the variable as x_position earlier and thought that it must increment everywhere but forgot that we are averaging the children’s x-position to get op’s x-position so i do not need to increment it, which is why I have cleared this up). Now we return the same stuff: op_id, id_count, op_x, leaf_count, tree.

Rendering Tree

The actual tree generation is simply looping through the dictionary. The important function is converting x_position and depth values that are simple integers into actual pixel positions to actually position the circles in the correct spot which is done by pixel_x = margin+x*x_spacing and pixel_y = margin+depth*y_spacing where margin, x_spacing and y_spacing are all hyper-parameters. The next function is draw_nodes which simply loops though the values of tree dictionary gets the x and depth for each node, converts them to actual coordinated using get_pixel_coords and then creates the svg line:
'<circle cx="{x}" cy="{y}" r="25" fill="white" stroke="black" /> <text x="{x}" y="{y}" text-anchor="middle" dominant-baseline="middle">{i['label']}</text>' for each node and its text. The other is draw_lines. It takes all the parent nodes and gets their x and y value as pixel coordinates. Then, it gets the children of the node and for each child’s id, the function gets the child by its id, then gets the x and y coordinates of the child as pixel coordinates and then draws the line as per this syntax:
f'<line x1="{x1}" y1="{y1}" x2="{x2}" y2="{y2}" stroke="white" />'
Finally we have the render_expression function which wraps everything into a single sequence of operations and creates the final svg code:
f'<svg xmlns="http://www.w3.org/2000/svg" width="850" height="650"> {lines} {nodes} </svg>'
and created an svg file to view the final tree.

AST Visualizer

After completing my tokenizer and parser with a few fixes, I wanted to move straight onto building the actual domain and range logic and setting up all the constraints, but instead, I had another idea. Whenever I saw the output of my parser, it just seemed a bit meh. The output was just a nested tuple and it was not looking like what I had built was a tree. So, as a side quest, I built an SVG AST visualizer that takes the tuple and build its tree and it is SVG and not matplotlib so that if I ever decide to turn this program into a website, I can simply plug in this code and get the output straight in a web page.

How it works:

For the people curious as to how it works, I am sorry if my explanation does not make sense because even I do not understand it very well (I am pretty bad at recursion).

basically, the main function that lets me plot these nodes in a 2D space is assign_positions. If we do not focus on recursion yet, the basic idea of this function is that there are 2 types of node: leaf nodes and internal nodes. Leaf nodes are the nodes which do not have any children and terminate the branch i.e. are terminal. whereas, internal nodes have children and branch out further to extend the tree i.e. are non-terminal. The basic hypothesis was that if there are two leaf nodes, and I assign them an x-position of 0 and 1, their parent node should be at a position which is the mid point (or average) of its children. Which means, the parent node of two leaf nodes (or internal nodes) at x-position 0 and 1 would lie at x-position 0.5 (avg of 0 and 1). now for the y-position, I have used depth as the name where the idea was simply that with every new node, the depth should increase by 1.

Now we come to recursion and how I generalized this position idea to any possible tuple. The basic things that the assign_positions function takes are:

node-> Current node
depth-> Current depth/ y-position
id_count-> The ID assigned to the node 
leaf_count-> Basically the x-position of the leaves
tree-> Current tree dictionary

There are 2 cases, the node can either be a leaf or an internal node. If the node is a leaf node, then we simple make the tree: tree[str_id] = {'label': node, 'x': str_x, 'depth': depth}. we increase leaf_count by 1 (because if the x-position assigned to this node was 0 then the next leaf node should have it as 1) and we increase id_count by 1. This case returns the x-position assigned to this node-> str_x, the id assigned to this node-> str_id, the current id_count, the current leaf_count and the current tree. These specific constraints are returned because If a parent had done a recursive call and the node was a leaf node then the parent would require:

1. the child’s x position to average left and right positions to set its own position.
2. the child’s id to keep track of it in its own dictionary.
3. the current id_count and leaf_count so that an assigned number is not reassigned to another node by mistake in a recursive call.

Case-2 and tree rendering covered in next devlog

Debugging Day

1. fixed unary negative operation on a function like -sqrt in the tokenizer.

2. added support for implicit multiplication in the tokenizer (right now only valid for alphabets after numbers like 3x, 25x, etc. and not for alphabet after alphabet like xsin(x), xlog(x), etc.)

3. fixed the decimal point collection in the tokenizer due to the failed test case: -.5

4. Added support for exponents by adding parse_pow().

5. initially i had simply copied the structure of parse_add and parse_mul and ran the test case but i found out that the result was wrong. My current parsing algorithm has natural left associativity, which is required for other operators but, is wrong for power. Because, 2^3^2 should result in 2^(3^4) and not (2^3)^4, which means i needed right associativity.

6. For getting right associativity, i had to make it such that the right term of the node was recursively calling parse_pow(), so that everything after it would get parsed first which would give us right associativity.

Parser Testing

I spent about 4 hours testing and debugging the recursive decent parsing algorithm, trying to understand the flow by writing each and every step. Here are my test cases.

Test case-1

exp = 2+3*4
tokens = ['2', '+', '3', '*', '4']
expected result = ('+', 2, ('*', 3, 4))

• This test case was used so that i can better understand parse_add and parse_mul along with the main parse_atom.
• Reached the correct answer.
• Found a bug in approach: I was not handling the case when pos was out of index ideally.
• Researched a bit on RDP and found out there is a basic template used in RDP which is while pos < len(tokens) ... and thus used this refined knowledge in my successive attempts.

Test case-2

exp = 2+3+4+5
tokens = ['2', '+', '3', '+', '4', '+', '5']
expected result = ('+', ('+', ('+', 2, 3), 4), 5)

• This specific test case defines why a while loop is important as it includes accumulation of same operator.
• I wanted to work through this by hand as I was really confused why we need a while loop instead of a simple if-else check whether the pos is out of range or not but the answer became clean when i worked through it.
• Reached the correct answer.

Test case-3

exp = (2+3)*4+1
tokens = ['(', '2', '+', '3', ')', '*', '4', '+', '1']
expected result = ('+', ('*', ('+', 2, 3), 4), 1)

• I used this test case as it introduces parenthesis into the parsing algorithm which is a fundamental feature.
• correctly worked through the parsing and reached the correct answer.

Parser

• I also completed the v1 of the parser in just 20 minutes. It is pretty hilarious that it took me 4 hours just to understand RDP but 20 minutes to code it. But, I believe those were 4 hours well spend because earlier, I found RDP to be mind breaking, but now I understand it so well that I think I can teach it even to a 12 year old.

Tokenizer progress:

1. Added decimal point support:

• Failed attempt: I initially tried to detect . from inside the .isdigit if-elif loop like detecting a continuation of digits but failed on case "12.34" → ['1234'] and then found the simpler solution.
   
• Added elif exp[i] == ".": num.append(exp[i]) as its own top-level case, letting a decimal point unconditionally join whatever number is currently being built inside the num list.
   
• all test cases passed: "0.3 + 1.5436* 245" → ['0.3', '+', '1.5436', '*', '245']. And, "3.5", ".5", "12.34" all correctly maintained their decimal points.
   
• tested all of the previous test cases like multi-digit numbers, multi-letter function names, parentheses, mixed expressions and all passed.
   

2. Added Unary minus v/s binary subtraction distinction:

• While thinking of some more edge cases, I found a case "2*-3" → ['2', '*', '-', '3'] which was wrong and I found out that the tokenizer needs to make the distinction between a unary minus -3, -x, etc. and a binary minus 2-3, x-4, etc.
   
• Added a special condition for - in the top level operator detecting if block and handling edge cases in the .isdigit and .isalpha elif blocks.
   
• All test cases passed:-
  • "3-2" → ['3', '-', '2']
  • "3*-2" → ['3', '*', '-2']
  • "-2+3" → ['-2', '+', '3']
  • "(-2)" → ['(', '-2', ')']
  • "3--2" → ['3', '-', '-2']
     

3. Added support for new operators and functions:

• Support for ^ operator by adding it to the top level operator detecting if block.
   
• Support for Absolute Value |x| by adding it to the top level operator detecting if block.
   
• Support for Fractional Part Function {x} by adding it to the top level operator detecting if block.
   
• Support for Greatest Integer Function [x] by adding it to the top level operator detecting if block.
   
• Also added these cases inside the unary minus handling if block thus passing all possible test cases.
   

Status:

The tokenizer part is complete for now. There are a few changes to be made, like adding support for implicit multiplication. Though, it is something that could be handled by the parser so I will handle it as time comes.

This is the first devlog for my Domain and Range calculator. I have completed making the first part of my custom AST algorithm: the tokenizer. I have used simple string parsing to separate specific terms in the expression. The algorithm handles sequence of characters (like alphabets or digits) as a single term which opens up the world to more complex and some basic and necessary functions like sqrt(), log(), trigonometric and inverse trigonometric functions. I am now going to handle some edge cases and try to functionize or shorten the collection of characters part as I have noticed that The process is same for digit and alphabets so I could potentially shorten the code. I expect this program to fit cleanly into the larger mathematical suit that I am trying to build to support most of mathematics along with support for coordinate geometry but that is something for later.

completed the basic Web UI flow. Now i am going to work on addition of authentication system, database and other features.

creating web UI for the automation script with multiple endpoints.