Once Again
Back to the interpreter. Shall we try the lambda thing again, or something else? Lambda seems fraught. Partial function FTW.
I think I want to try the lambda again: Bill Wake suggested an approach that makes sense to me, and I’d like to see whether it works. I don’t expect to like it, but I do want to know. Here are my tests for the interpret function:
def test_interpret(self):
rpn = ['37', '5', '+']
result = interpret(rpn)
assert result == 42
def test_interpret_2(self):
expr = '10 * 2 + 10 * 2 + 2'
lexed = lex(expr)
assert lexed == ['10', '*', '2', '+', '10', '*', '2', '+', '2']
rpn = dij(lexed)
assert rpn == ['10', '2', '*', '10', '2', '*', '2', '+', '+']
result = interpret(rpn)
assert result == 42
- No Joy
-
After a bit of experimentation with
lambda, along the lines Bill and I considered, with no joy, I came up with using partial functions instead. There may be no way to do that with a lambda: I’m not sure. But this works:
def interpret(rpn):
stack = []
r = rpn[::-1]
executable_r = make_executable(r)
while executable_r:
executable_r.pop()(stack)
return stack.pop()
def make_executable(rpn):
def stack_value(value, stack):
stack.append(to_number(value))
exec = []
op = None
for r in rpn:
if r == '+':
exec.append(lambda stack: stack.append(stack.pop() + stack.pop()))
elif r == '*':
exec.append(lambda stack: stack.append(stack.pop() * stack.pop()))
else:
sv = partial(stack_value, r)
exec.append(sv)
return exec
Both my tests pass. What is happening? The stack_value function takes two parameters, value and stack and puts the value, converted to a number, onto the stack. In the else clause, we create sv, a function of one parameter, stack, with the value parameter pinned to the current value of r. So each time we hit a value, we append a specialized function to add that value to the stack.
If that works, then this lambda should work:
def make_executable(rpn):
stack_value = lambda value, stack: stack.append(to_number(value))
exec = []
op = None
for r in rpn:
if r == '+':
exec.append(lambda stack: stack.append(stack.pop() + stack.pop()))
elif r == '*':
exec.append(lambda stack: stack.append(stack.pop() * stack.pop()))
else:
sv = partial(stack_value, r)
exec.append(sv)
return exec
And in fact it does. So we can inline, and this should work:
def make_executable(rpn):
exec = []
op = None
for r in rpn:
if r == '+':
exec.append(lambda stack: stack.append(stack.pop() + stack.pop()))
elif r == '*':
exec.append(lambda stack: stack.append(stack.pop() * stack.pop()))
else:
sv = partial(lambda value, stack: stack.append(to_number(value)), r)
exec.append(sv)
return exec
And in fact it does. We could inline again, but it would be ugly. Also, by convention in Python, we do not assign lambdas to a variable, we use a def. So we’ll go back to the original, with a bit more knowledge.
Commit: interpreter working with lambdas and functions in the rpn.
I just noticed the op = None. I have no recollection of what I intended for it. We do see a certain similarity in the cases for + and *. Can we combine those? How about this:
def make_executable(rpn):
ops = {'+': '__add__', '*': '__mul__'}
def stack_value(value, stack):
stack.append(to_number(value))
def binary_op(op, stack):
stack.append(getattr(stack.pop(), op)(stack.pop()))
exec = []
for r in rpn:
if r in ops:
do_op = partial(binary_op, ops[r])
exec.append(do_op)
else:
sv = partial(stack_value, r)
exec.append(sv)
return exec
I do not love that, but I am happy to know how to do it. Here, we have plugged in the operation to perform, as a string, which we then look up on the first argument found on the stack. That is, in essence, what + or * will do anyway.
Commit: do add and mul in one go by looking up dunder methods.
Reflection
OK, what have we got here, where should we go from here? We have a working lexer, parser, and interpreter for a tiny language. They will work if given just exactly what we expect them to get, and bad things will happen if they are fed bad information.
It’s pretty clear how we could plug in a name lookup: in this code, we’d just check the rpn item for starting with an alpha character. Whatever we did there would translate into something better. The real question is how to get to something better.
I can think of two ways we might go.
One would be to build a lexing/parsing object that produces an RPN list, and a separate interpreter object that processes the RPN. I think the RPN should include a bit more information about the items in the list, perhaps a tiny object indicating whether the item is a name, a value, or an operation.
Another possibility is a single object that lexes, parses, and executes all in one go. It would be a bit slower, since it would lex and parse on each record but that speed isn’t going to be a problem. Still, it seems better to have two collaborating objects, one to create the RPN and one to execute it. We might even come up with new ways of generating the RPN.
Either way, we want the little language that we use, and the particulars of how it is “compiled and executed” to be hidden in some objects so that we can change things out for a stronger language should we ever care to. And because that’s how we do things in any case.
As I mentioned in the previous article, I think we’ll want to work on the interpreter “first”, in the sense that we want to give it the most useful input format possible, even at the expense of a bit more complexity in the lexing and parsing. In practice, I don’t expect much conflict.
Another question is whether to proceed by refactoring the stand-alone functions we have, into one or more classes, or whether to start with a clean sheet of paper and new tests, in the light of these functions but without tying ourselves to their particulars.
Doing it by refactoring would be an interesting demonstration that we can refactor from pretty ragged to something nice. Doing it from scratch has a certain appeal as well, mostly not dealing with all that ragged stuff.
Perhaps for my sins, we should refactor. Maybe we’ll start off that way, at least, to see how quickly we can move the methods into a class or two, and then see what’s next.
We’ll decide tomorrow. This afternoon, we have a good thing, an already pretty clean interpreter. Time to back away slowly.
See you next time!