17 Expression Trees

Abstract Syntax Tree

Expression - a unit of code that, when evaluated, produces a single value

Statement - is more general: evaluating a statement can produce a value, and/or has some other effect.

Module - is a class that represents an entire Python program. Its body is a list of statements.

Every expression is a statement, but not vice-versa

The Expr Class

class Expr: 
	"""An abstract class representing a Python expression
	"""
	raise NotImplementedError

Num: Numeric Constants

class Num(Expr):
	"""An numeric constant literal.
	=== Attributes ===
	n: the value of the constant 
	"""
	n: Union[int, float]

	def __init__(self, number: Union[int, float]) -> None:
	"""Initialize a new numeric constant."""
	self.n = number

	def evaluate(self) -> Any: 
		"""Return the *value* of this expression."
		return self.n

BinOp: arithmetic operations

class BinOp(Expr):
	""" An arithmetic binary operation.
	=== Attributes ===
	left: the left operand
	op: the name of the operator 
	right: the right operand

	=== Representation Invariants ===
	- self.op == '+' or self.op == '*'
	"""
	left: Expr
	op: str
	right: Expr

	def __init__(self, left: Expr, right: Expr) -> None:
		"""Initialize a new binary operation expression. 
		Precodition: <op> is the string '+' or '*'
		"""
		self.left = left
		self.op = op
		self.right = right 

	def evaluate(self):
		left = self.left.evaluate
		right = self.right.evaluate
		if self.op == '+':
			return left + right 
		elif self.op == '*':
			return left * right
		else: 
			raise ValueError(f'Invalid operator {self.op}')

Variable Environment

A dictionary mapping variable names to values
{'x': 1, 'y': True}

We'll pass this into evaluate to keep memory

class Statement: 
	def evaluate(self, env: dict[str, Any]) -> Any: 
	"""Return the *value* of this expression, in the given
	environment. """