Writing an interpreter for a full programming language is a big job, and not something that we'll have time for in this class. However, for this assignment we'll write a very small interpreter for evaluating subtraction expresions in prefix notation, also known as Polish notation.
(a) Write a function called parse that takes a Scheme list containing a correct mathematical expression in prefix notation, and produces an abstract syntax tree appropriately organizing the subtractions and constants.
You should assume that your expression contains no mathematical operations other than subtraction. (No addition, multiplication, etc.)
For example, here is one possible input:
(- - 3 2 - 4 - 12 7)
Running parse on this list should return the following list, which represents the abstract syntax tree:
(diff-exp
(diff-exp
(const-exp 3)
(const-exp 2))
(diff-exp
(const-exp 4)
(diff-exp
(const-exp 12)
(const-exp 7))))
(b) Once you have the above complete, write another function called evaluate that takes an abstract syntax tree such as the above, and calculates the actual answer. These two functions together form your interpreter! For example:
(evaluate (parse '(- - 3 2 - 4 - 12 7)))should return the answer 2.
Hint: you're going to need a way to keep track of where in the prefix list you are. Write a helper function called by parse that returns not only the abstract syntax tree, but also the list of left over calculations (i.e., yet-to-be-done subtractions and numbers) from the input.
You must use recursion, and not iteration. You may not use side-effects (e.g. set!). You may use helper functions if you like.
parser.ss should be the name of the file that you submit.