(*
motivating the AST: evaluation of expressions and prefix notation solves ambiguity
imagine you have a calculator and you need to evaluate an expression you type: 2 + 3 * 8 into a single line the calculator understands the order of operations, so it does 3 * 8 = 24 2 + 24 = 26 but how is that dependency actually represented? as a quick example, note that we might also choose to write (2 + 3) * 8 which denotes that we must do 2 + 3 = 5, then 5 * 8 = 40 while we may understand the above (infix notation) we’d like to express the order of operations without relying on parentheses so much matching open/close parentheses can be a pain we want something unambiguous, even if it’s worse for humans to read the issue is that we don’t know which operator to use first/when why not simply write the operator first? trivially, we can write + 2 3, evaluating to 5 that’s great, what about if we want to write (2 + 3) * 8? well we know that we have (operator, operand_0, operand_1) (we assume binary ops) we also know that the last operation that will happen is * so we start by writing * a b now, we know that a should be + 2 3 from before so we can write * (+ 2 3) 8 and because we don’t need parentheses anymore, we have * + 2 3 8 pause: try to write 2 + 3 * 8 in this notation scheme (prefix notation) answer: + * 3 8 2 let’s briefly evaluate to prove this works first we encounter +, which wants 2 operands then, we find *, which wants 2 operands so we run into 3, then 8 so * matches with 3, 8 to result in 24 now, we’ve seen + and 24, and we find 2 so we have 24 + 2 = 26, as expected
*)
(*
motivating the AST: postfix notation fixes memory problem
notice that this actually only solves one of the problems from infix notation we have removed ambiguity while removing parentheses but we haven’t removed the problem of having to wait for our operands to come in we may know what operations to do, but we don’t have all the data yet the tokens come in left to right, we’re limited to online evaluation not only do we have to remember that we’re currently evaluating + but we also have to hold onto any partial results assume we wrote our expression as
- 2 * 3 8 now we need to know that we’re evaluating +, 2, and we’re waiting for the second arg but now we parse * and we need to store + 2 * 3, and we’re waiting for + 2’s second arg, which is currently being searched for it’s not really clear how we’re going to store all this information what if we could just store values in a list, and have the operand clear out the most recent values of the list? let’s call this append-only list a stack and assume it has the operations ‘push’ to add a value, and ‘pop’ to retrieve the most recent value before, we pushed operators into memory, and then kept track of the operands we needed, and the operators were first in the expression so now, we’ll push operands into memory which means we’ll want to write our expression leading with operands now we can use this data structure to push values so to write 2 + 3, we’d now instead write 2 3 + and to evaluate the expression, we’d push [2], then [2, 3], then once we encounter +, we can pop both 2 and 3 into the operator of + to get [5] it follows then to write (2 + 3) * 8, we can write 8 2 3 + * now we would have [8], [8, 2], [8, 2, 3], +, [8, 5], *, 40 notice how cleanly this resolves!
*)
(*
motivating the AST: function definitions and more complicated structure
this is great, and the student is happy with their new calculator but we want some convenience features for example, if i want to square a big number, i have to write it twice 80085 x 80085, too many keystrikes! i want to be able to take a number and square better yet, i might even want to square the result of an expression so we need a way to store the expression x x * without evaluating it no worries, you say [x, x, ] does the trick but does it? now we have [x, x, *] in our stack but evaluating this doesn’t work the way we want to we can only pop from the stack! our stack was useful for dynamic online evaluation but its not really the right tool for statically storing the structure of an expression what we want is a more flexible way of storing information notice also that squaring is not a binary operation, we’re forcing it into (, a, b) when it really wants to be (2, a) actually i guess it wants to be (, a, b) but ignore that for now we want to know, if we run into a *, where do we look next? how many values do we need? trees fall out as an obvious answer rather than storing a flat list of some kind we can store an operator as a node, and then have its child nodes be the operands note that this scales nicely into anything that outputs a single result value so now, when we write square(x) we can store it in our calculator as square |-x now, if we want to write x = 3 + 2 * 8 square(x) we have
square |- + |- 3 |- * |- 2 |- 8
*)
(*
motivating the AST: programs
while our calculator has been a useful toy so far, with expressions what we really want to write is a program we want to write something that our calculator can execute to manipulate state we’re actually getting quite close, with the macros we defined above the only thing we still need to go from expression/function evaluator to program executor is control flow our calculator can already take in input and produce output it can organize code into functions (like we saw with square) and it can remember values (like when we set x = 3 + 2 * 8) so all we need is to be able to branch, and repeat actions let’s say, instead of calculating the square of some number, we want a square root suppose we want sqrt(37) call 37 the target, a a is a convenient explanation here, because it’s like the area of a square where the side length s, is sqrt(a) we can start by guessing an arbitrary number in the sequence, say 1 call this x_i, where i denotes the step of the sequence we can think of this x_i as essentially a side of a rectangle and we try to iterate this x_i towards the true value s so the counterpart to this x_i would then be a/x_i (a/x_i * x_i = a) and now we have our rectangle of side lengths (x_i, a/x_i) since we know that one side is too big, and the other side is too small, until we reach s we can find our next x_{i+1} by simply averaging over (x_i, a/x_i) and we can stop the program after we have done ‘enough’ iterations, and the user is satisfied with the result we might formally define this as |a-square(x_i)| < tol or, when the square of our guessed square root is less than some allowed distance from the actual target so our program looks like
while |a-square(x_i)| > tol or i < N:
x_i = (x_i + a/x_i)/2
i += 1
if i >= N:
return x_i
return x_i
now all we have to do is figure out how to turn that back into the trees we’ve seen before the three types of objects we’ve been dealing with are
- expressions: 2 + 3 * 5, evaluates to a single value
- function declarations: defining square(x) as x * x
- statement: performs an action, ‘does something’. x = square(y) sets x’s value
we can express the concept of conditional execution using the ‘if’ statement notice that we have if i >= N the condition part of the if statement, i >= N, can be evaluated as an expression this expression results in either true or false, or 0/1 based on that result, we execute the body of the if for when its true or the body of the if for when its false the ‘while’ loop is similar it essentially checks a condition, similar to the ‘if’ statement and then executes the body if the condition is true otherwise, we skip execution and continue with the program
now, our AST might look something like the below:
while |- or |- > |- abs |- - |- a |- square |- x_i |- tol |- < |- i |- N |- body |- = |- x_i |- / |- + |- x_i |- / |- a |- x_i |- 2 |- = |- i |- + |- i |- 1 |- if |- >= |- i |- N |- return |- x_i
note that this only represents the structure of the program! not the evaluation
we’ll want to write
instruction/statement classes for
- return
- assign
- while
- if then else
expression classes for
- arithop
- logicop
- integer
- boolean
- string
- var
- function_call
*)