Pattern-matching syntax trees
I’m doing some very fun things with pattern-matching syntax trees today.
For context: I write a computer-based assessment system called Numbas, and it’s focused on assessing mathematics. A big part of that assessment involves asking the student to enter an algebraic expression as the answer to a question. How do you decide whether to mark the student’s answer as correct or not? Historically, there have been two approaches, given a representative “correct” expression written by the teacher:
- Put the student’s answer and the correct answer into a canonical form. If their syntax trees are exactly the same, then the student’s answer is the same as the teacher’s. This is the model used by, for example, STACK.
- Identify the variables used in the student’s answer and the teacher’s. Pick a few random numbers as values for those variables, and evaluate both expressions. If they come out to the same number, then the student’s answer is the same as the teacher’s. This is the model used by systems in the CALM line.