Calculator

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Calculator is a Scheme-like language that supports basic arithmetic operations.

Syntax

Calculator has primitive expressions and call expressions:

• a primitive expression is number: 2 or 3.14
• a call expression is a Scheme list that begins with an operator, followed by 0 or more expressions: (+), (* 1 2 3), (/ 3 (+ 4 5))

The legal operators are:

• +: sum of the arguments
• *: product of the arguments
• -: if one argument, negate it; else subtract the rest from the first
• /: if one argument, invert it; else divide the rest from the first

Here are some examples of Calculator in action:

calc> (+ 2 2)
4
calc> (- 5)
-5
calc> (* (+ 1 2) (+ 2 3))
15

Building an interpreter

Given a Calculator expression, an interpreter evaluates its meaning. An interpreter consists of a parser and an evaluator.

Parser

A parser analyzes an input string and describes the structure. It performs lexical analysis and syntactic analysis:

• lexical analysis (tokenization) divides the input string into meaningful tokens, such as punctuation marks and numbers
• syntactic analysis interprets a token sequence as an expression tree

Tokenization

In Calculator, the tokens are parentheses, numbers, and operators. The following tokenize function surrounds parentheses with spaces and invokes split (which splits a string into words using spaces as delimiters):

def tokenize(s):
"""Splits string S into a list of tokens.
>>> tokenize('(* (+ 12 3) 5)')
['(', '*', '(', '+', '12', '3', ')', '5', ')']
"""
return s.replace('(', ' ( ').replace(')', ' ) ').split()

Syntactic analysis

In our Calculator interpreter, we will represent expression trees as deep linked lists. We organize this stage into two mutually recursive functions: one for expressions (read) and one for operand lists (read_tail). Here they are:

"""Read an expression from a sequence of tokens.
>>> exp = read(['(', '+', '2', '3', '6', ')'])
>>> print(exp)
< '+' 2 3 6 >
>>> print(exp)
< '*' 4 < '-' 12 8 > >
"""
if tokens == []:
raise SyntaxError('unexpected end of input')
token = tokens.pop(0)
if token == '(':
elif token == ')':
raise SyntaxError('unexpected )')
else:
return atom(token)

"""Read the rest of a list."""
if tokens == []:
raise SyntaxError('unexpected end of input')
elif tokens == ')':
tokens.pop(0) # pop off ')'
else:

def atom(token):
"""Try to coerce TOKEN into an int or a float; otherwise return TOKEN."""
try:
return int(token)
except ValueError:
try:
return float(token)
except ValueError:

read checks for various base cases, including empty input (error) and primitive expressions (which are converted from strings to their correct type through atom). A recursive call to read_tail is invoked whenever a ( token indicates the beginning of a list.

read_tail continues to read from the same tokens, but expects to be called after a list has begun. Its base cases are an empty input (error) or a ) token that terminates the list. Its recursive call reads the first element of the list with read, reads the rest of the list with read_tail, and then returns a list represented as a linked list.

Now we can write a function that represents the parsing stage:

def parse(s):

Evaluator

An evaluator discovers the form of an expression and executes the corresponding evaluation rule.

Primitive expressions evaluate to themselves. Call expressions are evaluated recursively:

• evaluate each operand expression
• collect their values as a list of arguments
• apply the operator to the argument list

calc_eval computes the value of an expression exp, which is either a number or a call expression:

def calc_eval(exp):
"""Evaluate EXP."""
if type(exp) in (int, float): # number
return exp
elif isinstance(exp, Link): # call expression
args = exp.rest.map(calc_eval).to_list() # evaluate each argument and collect them in a list
return calc_apply(exp.first, args) # apply the operator
else:
raise SyntaxError('unknown expression')

Assume that the linked list class supports map and to_list.

calc_apply applies an operator to a list of arguments:

def calc_apply(operator, args):
if operator == '+':
return sum(args)
elif operator == '-':
if len(args) == 1:
return -args
else:
return args + sum([-arg for arg in args[1:]]) # args - args - args - ...
elif operator == '*':
return reduce(lambda x, y: x * y, args, 1)
elif operator == '/':
if len(args) == 1:
return 1 / args
else:
return reduce(lambda x, y: x * y, [1 / arg for arg in args[1:]], args) # args / args / args / ...

Depending on what operator is, we decide how to treat the arguments.

An interactive session is supported by a read-eval-print loop (REPL): read an expression, evaluate it, print the result, and repeat.

For Calculator, the REPL looks like this:

def repl():
while True:
try:
print(calc_eval(parse(input('calc> '))))
except (SyntaxError, ZeroDivisionError) as e:
print(type(e).__name__ + ':', e)

Final product

The entire source code can be viewed at Calculator/Source code.