PA from Scratch - Day 03

In today’s PA, I added the expression evaluation command p to my simple debugger. And this was the first time I deeply felt an important difference between PA and other OJ experiments: PA does not provide test data, so we need to design unit tests on our own and ensure the completeness of the tests. This article will briefly introduce the working principles of the expression evaluation command and share some lessons learned regarding unit testing.

Expression Evaluation

The format of the expression evaluation command is:

p <EXPR>

Where <EXPR> can be any expression. Probably for the sake of implementation simplicity, PA currently only requires implementing simple unsigned calculations for decimal numbers, and doesn’t involve variables or calculations with other bases. However, after building the overall architecture, the difficulty of adding more complex functionalities is not high, so I will still mainly introduce the overall principles of expression evaluation.

I believe most students not majoring in CS rarely have the opportunity to interact with the command line, so here I want to first introduce the general principles of the Command Line Interface (CLI). If you open PowerShell (Windows) or Terminal (MacOS) on your computer, you will see a black box that often appears in hacker movies, which is the command line. In the command line, we can run programs or perform operations by entering instructions. The commands in the command line typically have the following format:

<CMD> [-f <value>] <ARGS> ...

Where <CMD> is the name of the program or operation we want to execute; [-f <value>] flags some options of the command, where <value> is a potentially needed parameter; and <ARGS> are some parameters required for the program’s execution.

When we enter a command <CMD>, our command line will look for this command in the environment. The environment refers to a series of paths, a very important part of which is the paths in the $PATH environment variable. Software downloaded by users typically needs to be added to $PATH to be executed normally. The command-line program can traverse all the paths in the environment and search for the executable program corresponding to <CMD> within them.

This also explains what sequences it would have when I wiped out my $PATH on Day 01.

After finding the corresponding program, the command line will run the program and pass the command options and parameters we provided into the program to correctly execute the function we want.

In the simple debugger, the execution principle of commands is actually very similar. The simple debugger only needs to look for the command corresponding to the command provided by the user (corresponding to <CMD>) in the set of commands defined in the code (corresponding to $PATH), and pass the parameters provided by the user (in the form of a string) into the function corresponding to the command (corresponding to the executable program).

The above is a brief introduction to the running principles of the command line and the simple debugger. After understanding the principles of calling instructions in the simple debugger, we can more directly appreciate the two main difficulties in completing the p command: syntax analysis and evaluation.

Syntax Analysis

In the simple debugger, the parameters we pass into the function are stored in the form of a string, which means that for the command:

p 1 + 1

the parameter passed into the function cmd_p is the string “1 + 1”. And to be able to perform calculations on this equation, we must find a way to extract “1”, “+”, and “1” from “1 + 1”. There are many ways to implement this kind of syntax analysis, the simplest of which is to use Regular Expressions.

Regular Expression (regex for short) is a powerful tool used for matching, searching, extracting, and manipulating text data. It is a string pattern based on specific rules. By defining rules, it can accurately match and process text data.

We can define different rules for different symbols and match them one by one in the input parameter string, thus parsing out a series of symbols that can participate in the calculation.

Evaluation

It is easy to find that for a legal expression expr (however, the most troublesome part of this project is actually determining illegal expressions QAQ), the following rules stand:

• A number is a legal expression, and its value is itself, meaning no calculation is needed.
• expr + expr is a legal expression.
• expr * expr is a legal expression.
• expr - expr is a legal expression.
• expr / expr is a legal expression.
• (expr) is a legal expression, its value is the value of expr, and the parentheses can be removed directly.

Therefore, to write an evaluation function eval(expr), we only need to be able to recognize the expression as one of the six cases above to evaluate it (number) or decompose it into subexpr [+-*/] subexpr. And we just need to find a way to get the value of subexpr, then we can evaluate any expr.

So how do we get the value of subexpr? If only we had a function that could evaluate an expression… Oh! We have a function to evaluate expressions, eval! Great, isn’t the value of subexpr just eval(subexpr)?

This concept is called recursion, which I personally consider a very elegant algorithm design idea. I hope students who are not familiar with recursion can carefully consider the above train of thought and see if they can figure it out :)

Unit Testing

To ensure the accuracy of my implementation in the above two parts (actually it can be said to be three parts, one of which I didn’t introduce for the sake of the aesthetic appeal of the idea), I designed separate unit tests for both functions during the writing process, meaning I separately checked whether the function’s capabilities were correct.

Unit testing is extremely crucial when writing such a large project. In large projects, some seemingly simple functions require multiple modules to cooperate with each other. If the correctness of the basic modules cannot be guaranteed, then when a problem occurs with the function, it is very difficult to determine the exact location where the problem occurred.

After we discover a bug and resolve it, we must also perform unit testing on the related modules. I spent about an hour looking for a new bug caused by my bug fix.

Unit testing is a prerequisite for ensuring the basic accuracy of the code; code that hasn’t undergone multiple rounds of testing is almost certainly problematic. In this case, manually designing test data is very time-consuming and labor-intensive, so you can use code to randomly generate a large amount of test data for testing.

And this concludes PA 1.2.