Abstract¶
Conditional execution allows a program to selectively execute different parts of the code based on specific conditions. This capability enables the program to adapt and respond appropriately to various situations it encounters, making it more flexible and functional. By using boolean expressions and conditional statements, students will learn to direct the flow of execution to handle a wide range of inputs and scenarios effectively.
import math
from flowcharts import *
from ipywidgets import interact
from dis import dis
%load_ext divewidgetsif not input('Load JupyterAI? [Y/n]').lower()=='n':
%reload_ext jupyter_aiLoad JupyterAI? [Y/n]
Motivation¶
Conditional execution means running different pieces of code based on different conditions. Why do programmers need conditional executation?
For instance, when trying to compute a/b, b may be 0 and division by 0 is invalid.
%%optlite -h 450
def multiply_or_divide(a, b):
print("a:{}, b:{}, a*b:{}, a/b:{}".format(a, b, a * b, a / b))
multiply_or_divide(1, 2)
multiply_or_divide(1, 0)Although division by 0 is invalid, multiplication remains valid but it is not printed due to the division error. Can we skip only the division but not the multiplication when b is equal to 0?
Solution 1: Use a conditional expression that specifies which code block should be executed under what condition:
... if ... else ...def multiply_or_divide(a, b):
q = a / b if b else "undefined"
print("a:{}, b:{}, a*b:{}, a/b:{}".format(a, b, a * b, q))
multiply_or_divide(1, 2)
multiply_or_divide(1, 0) # multiplication is valid but not showna:1, b:2, a*b:2, a/b:0.5
a:1, b:0, a*b:0, a/b:undefined
Solution 2: Use a boolean expression:
... and ... or ...def multiply_or_divide(a, b):
q = b and a / b or "undefined"
print("a:{}, b:{}, a*b:{}, a/b:{}".format(a, b, a * b, q))
multiply_or_divide(1, 2)
multiply_or_divide(1, 0) # multiplication is valid but not showna:1, b:2, a*b:2, a/b:0.5
a:1, b:0, a*b:0, a/b:undefined
Solution 3: Monitor and catch the error using a try statement:
def multiply_or_divide(a, b):
try:
q = a / b
except ZeroDivisionError:
q = "undefined"
print("a:{}, b:{}, a*b:{}, a/b:{}".format(a, b, a * b, q))
multiply_or_divide(1, 2)
multiply_or_divide(1, 0) # multiplication is valid but not showna:1, b:2, a*b:2, a/b:0.5
a:1, b:0, a*b:0, a/b:undefined
In this notebook, we will introduce the first two solutions. The last one is a better way to handle exceptions when the operations get complicated.
%%ai
Explain in one paragraph, using a simple example, the benefits of using a
try statement over conditional checks for handling exceptions and errors.Comparison Operators¶
A comparison/relational operators along with its operands form an expression, which evaluates to a boolean value:
True # if the operands satisfy certain conditions, andTrueFalse # otherwise.FalseUnlike many other languages, Python capitalized the keywords for the boolean values to signify that they are constants, just like the keyword None. Hence,
true = False # is invalid in many languages but not Python
False = true # is valid in many languages but not PythonWhy are boolean values “boolean”?
Boolean expressions are named after George Boole, whose work laid the foundation of digital circuitry. Below are the links to the ebooks, thanks to Project Gutenberg:
- Boole, George. The mathematical analysis of logic. CreateSpace Independent Publishing Platform, 1847.
- Boole, George. An investigation of the laws of thought: on which are founded the mathematical theories of logic and probabilities. Vol. 2. Walton and Maberly, 1854.
An import result derived from Boole’s framework for digital circuits is Boole’s/Shannon expansion theorem.
%%ai
Explain Entscheidungsproblem and its relation to George Boole.Equality and Inequalties¶
The equality and inequality relationships in mathematics are implemented using the following comparison operators:
You can explore these operators using the widget below:
comparison_operators = ["==", "<", "<=", ">", ">=", "!="]
@interact(operand1="10", operator=comparison_operators, operand2="3")
def comparison(operand1, operator, operand2):
expression = f"{operand1} {operator} {operand2}"
value = eval(expression)
print(
f"""{'Expression:':>11} {expression}\n{'Value:':>11} {value}\n{'Type:':>11} {type(value)}"""
)%%ai
Explain very briefly how the comparison operators == may be represented
differently in other programming languages such as maxima, scheme, and bash.What is the precedence of comparison operators?
All the comparison operators have the same precedence lower than that of + and -.
1 + 2 >= 3 # (1 + 2) >= 3TrueSimilar to the assignment operations, comparison operators can be chained together but they are non-associative.
2.0 == 2 > 1, (2.0 == 2) > 1, 2.0 == (2 > 1)(True, False, False)1 <= 2 < 3 != 4, (1 <= 2) < (3 != 4)(True, False)Solution to Exercise 1 #
The second expression indeed does not involve chained comparison. The expressions inside the parentheses are first evaluated to boolean values, both of which are True. Therefore, the entire expression True < True evaluates to False. You can also try evaluating the following expressions for further understanding:
False < True- True ** 2 + 11 / False
To learn more about the relationship between bool and int, check out PEP 285.
The second expression is not a chained comparison:
- The expressions in the parentheses are evaluated to boolean values first to
True, and so - the overall expression
True < Trueis evaluated toFalse. You may also want to try:False < True- True ** 2 + 11 / False
To understand how bool is related to int, see the PEP 285.
# Comparisons beyond numbers
@interact(
expression=[
"10 == 10.",
'"A" == "A"',
'"A" == "A "',
'"A" != "a"',
'"A" > "a"',
'"aBcd" < "abd"',
'"A" != 64',
'"A" < 64',
]
)
def relational_expression(expression):
print(eval(expression))Solution to Exercise 2 #
- Checks whether an integer is equal to a floating point number.
- Checks whether two characters are the same.
- Checks whether two strings are the same. Note the space character.
- Checks whether a character is larger than the order character according to their unicodes.
- Checks whether a string is lexicographically smaller than the other string.
- Checks whether a character is not equal to an integer.
- TypeError because there is no implementation that evaluates whether a string is smaller than an integer.
Comparing Floating Point Numbers¶
== can also be used to compare floating point numbers:
x = 10
y = (x ** (1 / 3)) ** 3
x == yFalseWhy False? Shouldn’t ?
Floating point numbers have finite precisions and so the computation may not be exact.
In practice, a small error in the calculation can be tolerated. Instead of checking equality of floating point numbers, we can check closeness up to a specified tolerance:
abs_tol = 1e-9
y - abs_tol <= x <= y + abs_tolTrueabs_tol, often denoted as , is a positive number called the absolute tolerance.
Why call it absolute tolerance?
Note that the test remains unchanged if we swap x and y:
abs_tol = 1e-9
x - abs_tol <= y <= x + abs_tolTrueUsing the absolute function abs, we can also rewrite the comparison as follows:
abs_tol = 1e-9
abs(x - y) <= abs_tolTrueIs an absolute tolerance of 1e-9 good enough?
The same absolute tolerance fails if we set x = 1e10 instead of 10.
x = 1e10
y = (x ** (1 / 3)) ** 3
abs_tol = 1e-9
abs(x - y) <= abs_tolFalseWhy absolute tolerance fail?
In floating-point representation, the radix point floats across different scales according to the exponent. The precision error in mantissa is therefore relative to the scale of the number.
We should instead check whether is within a certain percentage of :
rel_tol = 1e-9
y * (1 - rel_tol) <= x <= y * (1 + rel_tol)TrueNote that the above test is not symmetric between and , i.e., is relatively close to does not necessarily mean is relatively close to .
x = 1
y = 2
rel_tol = 0.5
y * (1 - rel_tol) <= x <= y * (1 + rel_tol), x * (1 - rel_tol) <= y <= x * (1 + rel_tol)(True, False)To make the comparison symmetric, we can use the absolute difference as follows:
Why use but not ?
x = 1e10
y = (x ** (1 / 3)) ** 3rel_tol = 1e-9
### BEGIN SOLUTION
abs(x - y) <= rel_tol * max(abs(x), abs(y))
### END SOLUTIONTrueWhat if or is very close to 0? For instance, can you change rel_tol so that your solution above returns True for the following values of x and y?
x = 1e-15
y = 0When does relative tolerance fail?
If or is very close to 0, the relative tolerance test becomes ineffective, and so absolute tolerance is a more meaningful test. In particular, with , (4) becomes
In the nontrivial case , the test is independent of the value of , and therefore cannot check whether is close to 0. In particular, since normally, and the test would always fail unless exactly, which defeats the purpose of allowing a tolerance.
For a more flexible comparison, one can impose both the absolute and relative tolerances:
This is implemented by the function isclose from math module with the default
- relative tolerance equal to
1e-9, and - absolute tolerance equal to
0.0.
math.isclose?TrueSignature: math.isclose(a, b, *, rel_tol=1e-09, abs_tol=0.0)
Docstring:
Determine whether two floating-point numbers are close in value.
rel_tol
maximum difference for being considered "close", relative to the
magnitude of the input values
abs_tol
maximum difference for being considered "close", regardless of the
magnitude of the input values
Return True if a is close in value to b, and False otherwise.
For the values to be considered close, the difference between them
must be smaller than at least one of the tolerances.
-inf, inf and NaN behave similarly to the IEEE 754 Standard. That
is, NaN is not close to anything, even itself. inf and -inf are
only close to themselves.
Type: builtin_function_or_methoddef isclose(x, y, *, rel_tol=1e-09, abs_tol=0.0):
### BEGIN SOLUTION
return x==y or abs(x - y) <= max(rel_tol * max(abs(x), abs(y)), abs_tol)
### END SOLUTIONx = 10
y = (x ** (1 / 3)) ** 3
assert isclose(x, y)
x = 1e10
y = (x ** (1 / 3)) ** 3
assert isclose(x, y) and not isclose(x, y, rel_tol=0, abs_tol=1e-9)
assert not isclose(1e-15, 0)
assert isclose(float('inf'), float('inf'))
assert not isclose(float('nan'), float('nan'))Conditional Constructs¶
To illustrate how Python can carry out conditional execution, we will consider writing a program that sorts values in ascending order.
If-Then Construct¶
How to sort two values?
Given two values are stored as x and y, we want to
print(x,y)ifx <= y, andprint(y,x)ify < x.
Such a program flow is often represented by a flowchart like the following:
sort_two_values_fc1How to read the flowchart?
A flowchart uses arrows to connects a set of annotated blocks. The rules were first specified by ANSI and later adopted in ISO 5807.
Why to use a program flowchart?
A program flowchart is a powerful way of describing an algorithm quickly. Unlike a text-based programming language:
- The rules governing the program flow can be shown explicitly by arrows.
- The annotated graphical blocks can convey the meaning faster using visual clues.
How to implements the flowchart in Python?
It is often useful to delay detailed implementations until we have written an overall skeleton. To leave a block empty, Python uses the keyword pass.
# write a code skeleton
def sort_two_values(x, y):
pass
# print the smaller value first followed by the larger one
sort_two_values(1, 0)
sort_two_values(1, 2)Python provides the if statement to implement the control flow specified by the diamond boxes in the flowchart.
def sort_two_values(x, y):
if x <= y:
pass
# print x before y
if y < x: pass # print y before x
sort_two_values(1, 0)
sort_two_values(1, 2)To complete the implementations specified by the parallelogram boxes in the flow chart, we fill in the bodies/suites of the if statements as follows:
def sort_two_values(x, y):
if x <= y:
print(x, y)
if y < x: print(y, x)
@interact(x="1", y="0")
def sort_two_values_app(x, y):
print("Values in ascending order:")
sort_two_values(eval(x), eval(y))Test the program by filling in different values of x and y above.
How to indent code in Python?
As Python uses indentation to indicate code blocks or suites:
print(x, y)(Line 3) is indented to the right ofif x <= y:(Line 2) to indicate it is the body of the if statement.- For convenience,
if y < x: print(y, x)(Line 4) is a one-liner for anifstatement that only has one line in its block. - Both
ifstatements (Line 2-4) are indented to the right ofdef sort_two_values(x,y):(Line 1) to indicate that they are part of the body of the functionsort_two_values.
The style guide recommends using 4 spaces for each indentation. In JupyterLab, you can simply type the tab key.
We can visualize the execution as follows. Step through the execution to
- see which lines are skipped, and
- understand why they are skipped.
%%optlite -h 450
def sort_two_values(x, y):
if x <= y:
print(x, y)
if y < x: print(y, x)
sort_two_values(1, 0)
sort_two_values(1, 2)If-Then-Else Construct¶
Can the sorting algorithm be improved further?
Hint
not (x <= y) and (y < x) is a tautology, i.e., always true.
Consider the following modified flowchart:
sort_two_values_fc2This can implemented by the else clause of the if statement as follows:
%%optlite -h 450
def sort_two_values(x, y):
if x <= y:
print(x, y)
else:
print(y, x)
sort_two_values(1, 0)
sort_two_values(1, 2)Can we shorten the code to one line? This is possible with the conditional expression.
def sort_two_values(x, y):
print(("{0} {1}" if x <= y else "{1} {0}").format(x, y))
@interact(x="1", y="0")
def sort_two_values_app(x, y):
print("Values in ascending order:")
sort_two_values(eval(x), eval(y))Solution to Exercise 5
A conditional expression must be an expression:
- It must give a value under all cases. To enforce that,
elsekeyword must be provided. - An assignment statement does not return any value and therefore cannot be used for the conditional expression.
x = 1 if True else 0is valid becausex =is not part of the conditional expression.
Nested Conditionals¶
Now, consider a slight more challenging problem of sorting three values instead of two. A feasible algorithm is as follows:
sort_three_values_fcTo implement flowchart, we can use nested conditional constructs, where one conditional statement is placed within another, allowing for multiple layers of condition checks:
def sort_three_values(x, y, z):
if x <= y <= z:
print(x, y, z)
else:
if x <= z <= y:
print(x, z, y)
else:
if y <= x <= z:
print(y, x, z)
else:
if y <= z <= x:
print(y, z, x)
else:
if z <= x <= y:
print(z, x, y)
else:
print(z, y, x)
def test_sort_three_values():
sort_three_values(0, 1, 2)
sort_three_values(0, 2, 1)
sort_three_values(1, 0, 2)
sort_three_values(1, 2, 0)
sort_three_values(2, 0, 1)
sort_three_values(2, 1, 0)
test_sort_three_values()0 1 2
0 1 2
0 1 2
0 1 2
0 1 2
0 1 2
Imagine what would happen if we have to sort many values. The program will not only be long, but also fat due to the indentation. To avoid an excessively long line due to the indentation, Python provides the elif keyword that combines else and if.
def sort_three_values(x, y, z):
if x <= y <= z:
print(x, y, z)
elif x <= z <= y:
print(x, z, y)
elif y <= x <= z:
print(y, x, z)
elif y <= z <= x:
print(y, z, x)
elif z <= x <= y:
print(z, x, y)
else:
print(z, y, x)
test_sort_three_values()0 1 2
0 1 2
0 1 2
0 1 2
0 1 2
0 1 2
def sort_three_values(x, y, z):
### BEGIN SOLUTION
# How many comparisons are needed in a program to sort n numbers?
if x > y:
x, y = y, x
if y > z:
y, z = z, y
if x > y:
x, y = y, x
print(x, y, z)
### END SOLUTION
sort_three_values(10, 17, 14)10 14 17
Sorting algorithms
A sorting algorithm refers to the procedure of sorting any number of values in order. The performance of a sorting algorithm is measured primarily by its time complexity (the number of comparisons and swaps it makes) and its space complexity (the amount of additional memory it requires). It would be even better if the program is short and easy to read, but that depends partly on the design of the programming language. Python implemented its default sorted function using the Timsort algorithm. See if you can understand how it works and how well it works.
%%ai
Explain in one paragraph what the minimum possible number of comparisons needed
to sort n numbers is and why it is not the same as the maximum number of
inversions.Boolean Operations¶
Since chained comparisons are non-associative, it follows a different evaluation rule than arithmetic operators.
E.g., 1 <= 2 < 3 != 4 is equivalent to:
1 <= 2 and 2 < 3 and 3 != 4TrueThe above is called a compound boolean expression, which is formed using the boolean/logical operator and.
Why use boolean operators?
What if we want to check whether a number is either or ?
The following program checks whether a number is either or :
# Check if a number is outside a range.
@interact(x="15")
def check_out_of_range(x):
x_ = float(x)
is_out_of_range = x_ < 0 or x_ >= 100
print("Out of range [0,100):", is_out_of_range)Can you rewrite the logical expression to use only the and instead of or?
and instead of or?Turns out this is mission impossible because and alone is not functionally complete, i.e., it is not enough to give all possible boolean functions. We can add or and not operators to make it functionally complete.
%%ai
Explain in a paragraph why the set of operators including only "and" is not
functionally complete.%%ai
Explain in a paragraph why the set of operators "and", "or", and "not" is
functionally complete.The following table is called a truth table. It enumerates all possible input and output combinations for each boolean operator available in Python:
Table 2:Truth table for different logical operators
x | y | x and y | x or y | not x |
|---|---|---|---|---|
True | True | True | True | False |
True | False | False | True | False |
False | True | False | True | True |
False | False | False | False | True |
Solution to Exercise 7
- Expression A evaluates to
Truebecauseandhas higher precedence and so the expression has the same value asTrue or (False and True). - Expression B evaluates to
Falsebecauseandis left associative and so the expression has the same value as(True and False) and True. - Expression C evaluates to
Truebecauseandhas a higher precedence and so the expression has the same value asTrue or (True and False). Note that(True or True) and Falseevaluates to somethingFalseinstead, so precedence matters.
A compound boolean expression actually uses a short-circuit evaluation.
To understand this, we will use the following function to evaluate a boolean expression verbosely.
def verbose(id, expr):
"""Identify evaluated boolean expressions."""
print(id, "evaluated:", expr)
return exprFor instance:
verbose("1st expression", True)
verbose("2nd expression", False)1st expression evaluated: True
2nd expression evaluated: False
FalseVisualization by Thonny IDE
You may also use the debugger of Thonny to visualize the step-by-step evaluations of the operands:
- In JupyterLab, click
FileNew LauncherDesktopto launch a remote desktop for your server.[1] - Start Thonny in the remote desktop by clicking
ApplicationsDevelopmentThonny.[2] - In the Thonny editor, write some Python code such as
True or False and Trueand then save it to a file, saytest.py.[3] - Debug the code by clicking the Thonny menu item
RunDebug current script (nicer).[4] - Click the
step intobutton to step through the executions.
Short-circuit or¶
Consider evaluating True or False and True in a verbose manner:
verbose("A", verbose(1, True) or verbose(2, False) and verbose(3, True))1 evaluated: True
A evaluated: True
TrueWhy the second and third expressions are not evaluated?
Because True or ... must be True (why?) so Python does not look further. From the documentation:
Short-circuit evaluation of or
The expression x or y
- first evaluates
x; - if
xis true, its value is returned; - otherwise,
yis evaluated and the resulting value is returned.
Put it another way, (x or y) translate to the following
_ if (_ := x) else yProgram 1:Translation of (x or y)
except for the extra variable _. For example, True or False and True translates to _ if (_ := True) else False and True:
verbose("A", (_ if (_ := verbose(1, True)) else verbose(2, False) and verbose(3, True)))1 evaluated: True
A evaluated: True
TrueShort-circuit and¶
Now, consider evaluating False or False and True in a verbose manner:
False or False and TrueFalseverbose("B", verbose(4, False) or verbose(5, False) and verbose(6, True))4 evaluated: False
5 evaluated: False
B evaluated: False
FalseWhy expression 6 is not evaluated?
False or False and ... must be False so Python does not look further.
Short-circuit evaluation of and
The expression x and y first evaluates x;
if x is false, its value is returned;
otherwise, y is evaluated and the resulting value is returned.
Put it another way, (x and y) translate to the following
_ if not (_ := x) else yProgram 2:Translation of (x and y)
except for the extra variable _. For example, False or False and True translates to False or (_ if not (_ := False) else True):
verbose(
"B", verbose(4, False) or (_ if not (_ := verbose(5, False)) else verbose(6, True))
)4 evaluated: False
5 evaluated: False
B evaluated: False
FalseNon-Boolean Values for Boolean Operations and Control Flow Statements¶
Interestingly, Python also allows logical operations to have non-boolean operands and return values. From the documentation:
Boolean interpretation
In the context of Boolean operations, and also when expressions are used by control flow statements, the following values are interpreted as false:
FalseNone- Numeric zero of all types
- Empty strings and containers (including strings, tuples, lists, dictionaries, sets and frozensets)
All other values are interpreted as true.
The following is an application of this rule.
print("You have entered", input() or "nothing")
You have entered nothing
Solution to Exercise 8 #
- The code replaces an empty user input by the default string
nothingbecause an empty string is regarded as False in a boolean operation. - If user input is non-empty, it is regarded as True in the boolean expression and returned immediately as the value of the boolean operation.
input(1) or input(2) and input(3)Solution to Exercise 9
Enter ’ ', ‘’ and then ‘’.
### BEGIN SOLUTION
_ if (_ := input(1)) else (_ := input(3)) if (_ := input(2)) else _
### END SOLUTIONIs an empty string "" equal to False?
"" equal to False?Try "" == False.
- An empty string is regarded as false in a boolean operation but
- a comparison operation is not a boolean operation, even though it forms a boolean expression.
Should the following return False?
0 == False and 1 == TrueTry and explain what you see.
%%ai
In Python, explain in one paragraph what is the value of the following expression:
0 == False and 1 == TrueThe equality operator
==consists of two equal signs, different from the assignment operator=.Different from C or javascript:
- We can write
1 != 2asnot 1 == 2but not!(1 == 2)because !is not a logical operator. It is used to call a system shell command in IPython.
- We can write
Thonny is an IDE based on TKinter, which requires a proper desktop environment to run.
You can also launch a terminal in the remote desktop and run the command
thonny.You can copy and paste code into the remote desktop by clicking
Remote Clipboardbutton at the top right of the browser page and pasting your code into the textbox that appears below.Short-cut keys for Thonny may not work as the keys may be captured by the browser or your OS before they can reach Thonny.