11.1.3 Applications and Invocations

Whereas Scheme programs are composed of expressions and definitions, Python programs are mostly sequences of statements. Unlike expressions, a statement has no value. The emphasis on statements impacts the style of programming used with Python. It is more imperative than that used with Scheme: instead of composing expressions in ways that pass the result of one expression as an operand to the next expression, Python procedures consist mostly of statements, each of which alters the state in some way towards reaching the goal state. Nevertheless, it is possible (but not recommended) to program in Scheme using an imperative style (emphasizing assignments), and it is possible (but not recommended) to program in Python using a functional style (emphasizing procedure applications and eschewing statements).

Defining a procedure in Python is similar to defining a procedure in Scheme, except the syntax is different:

Unlike in Scheme, whitespace (such as new lines) has meaning in Python. Statements cannot be separated into multiple lines, and only one statement may appear on a single line. Indentation within a line also matters. Instead of using parentheses to provide code structure, Python uses the indentation to group statements into blocks. The Python interpreter reports an error if the indentation does not match the logical structure of the code.

Since whitespace matters in Python, we include newlines ($<$newline$>$) and indentation in our grammar. We use indented(elements) to indicate that the elements are indented. For example, the rule for Block is a newline, followed by one or more statements. The statements are all indented one level inside the block's indentation. The block ends when the indenting returns to the outer level.

The evaluation rule for a procedure definition is similar to the rule for evaluating a procedure definition in Scheme. Python Procedure Definition. The procedure definition,

def Name (Parameters): Block

defines Name as a procedure that takes as inputs the Parameters and has the body expression Block.

The procedure definition, def tokenize(s): ..., defines a procedure named tokenize that takes a single parameter, s.

Assignment. The body of the procedure uses several different types of Python statements. Following Python's more imperative style, five of the statements in tokenize are assignment statements including the first two statements. For example, the assignment statement, tokens = [] assigns the value [] (the empty list) to the name tokens.

The grammar for the assignment statement is:

For now, we use only a Name as the left side of an assignment, but since other constructs can appear on the left side of an assignment statement, we introduce the nonterminal Target for which additional rules can be defined to encompass other possible assignees. Anything that can hold a value (such as an element of a list) can be the target of an assignment.

The evaluation rule for an assignment statement is similar to Scheme's evaluation rule for assignments: the meaning of x = e in Python is similar to the meaning of (set! x e) in Scheme, except that in Python the target Name need not exist before the assignment. In Scheme, it is an error to evaluate (set! x 7) where the name x has not been previously defined; in Python, if x is not already defined, evaluating x = 7 creates a new place named x with its value initialized to 7.

Python Evaluation Rule: Assignment. To evaluate an assignment statement, evaluate the expression, and assign the value of the expression to the place identified by the target. If no such place exists, create a new place with that name.

Arithmetic and Comparison Expressions. Python supports many different kinds of expressions for performing arithmetic and comparisons. Since Python does not use parentheses to group expressions, the grammar provides the grouping by breaking down expressions in several steps. This defines an order of precedence for parsing expressions.

For example, consider the expression 3 + 4 * 5. In Scheme, the expressions (+ 3 (* 4 5)) and (* (+ 3 4) 5) are clearly different and the parentheses group the subexpressions. The Python expression, 3 + 4 * 5, means (+ 3 (* 4 5)) and evaluates to 23.

Supporting precedence makes the Python grammar rules more complex since they must deal with * and + differently, but it makes the meaning of Python expressions match our familiar mathematical interpretation, without needing to clutter expressions with parentheses. This is done is by defining the grammar rules so an AddExpression can contain a MultExpression as one of its subexpressions, but a MultExpression cannot contain an AddExpression. This makes the multiplication operator have higher precedence than the addition operator. If an expression contains both + and * operators, the * operator is grouped with its operands first. The replacement rules that happen first have lower precedence, since their components must be built from the remaining pieces.

Here are the grammar rules for Python expressions for comparison, multiplication, and addition expressions:

The last rule allows expressions to be grouped explicitly using parentheses. For example, (3 + 4) * 5 is parsed as the PrimaryExpression, (3 + 4), times 5, so evaluates to 35; without the parentheses, 3 + 4 * 5 is parsed as 3 plus the MultExpression, 4 * 5, so evaluates to 23.

A PrimaryExpression can be a Literal, such as a number. Numbers in Python are similar (but not identical) to numbers in Scheme.

A PrimaryExpression can also be a name, similar to names in Scheme. The evaluation rule for a name in Python is similar to the stateful rule for evaluating a name in Scheme1.

Exercise 11.1. Draw the parse tree for each of the following Python expressions and provide the value of each expression.
a. 1 + 2 + 3 * 4
b. 3 > 2 + 2
c. 3 * 6 >= 15 == 12
d. (3 * 6 >= 15) == True

Exercise 11.2. Do comparison expressions have higher or lower precedence than addition expressions? Explain why using the grammar rules.


  1. There are some subtle differences and complexities (see Section 4.1 of the Python Reference Manual), however, which we do not go into here.