1. Instructions

In this lab, you have three tasks:

• Think about what python would display section 3.
• Draw environment diagrams for the code in section 4.
• Complete the required problems described in section 5 and submit your code with Ok, as instructed in lab00. The starter code for these problems is provided in lab01.py, which is distributed as part of the homework materials.

Submission: As instructed before, you need to submit your work using either the VSCode plugin or by running Ok with python ok --submit. You are allowed to submit multiple times before the deadline, and your score on this assignment will be the highest out of all your submissions.

Readings: You might find the following sections in the textbook useful:

• Section 1.2
• Section 1.3
• Section 1.4
• Section 1.5

2. Recap

Consult this section if you need a refresher on the material for this lab. Feel free to skip this section, but remember to return to it later if you get stuck.

2.1 Functions

It is common to write some code over and over again during programming. Let's say we want to know the BMI(Body Mass Index) of a given person. The formula is given by

\[ \text{BMI} = \dfrac{m}{h^2} \]

Where \(m\) stands for weight (in kilograms) and \(h\) stands for height (in meters).

For a person who's 1.7 meters tall and weighs 70 kilograms, one way to tell his/her BMI is as follows:

>>> 70 / (1.7 * 1.7)
24.221453287197235

According to Python, his/her BMI would be 24.221453287197235.

Say, if TAs of SICP need to know the BMI of all the students (more than 200!) in the class, then they will have to do something like this:

>>> 70 / (1.7 * 1.7)
24.221453287197235
>>> 60 / (1.6 * 1.6)
23.4375
>>> 80 / (1.8 * 1.8)
24.691358024691358
...

Code above introduces duplications (i.e., height appears twice in every expression). For more than 200 students, such duplication may lead to bugs as TAs might accidentally get someone's height wrong for its second appearance:

>>> 70 / (1.7 * 1.6) # Wrong!
25.735294117647058

To capture the essence of calculating one's BMI using his/her weight and height, we can instead write a function for the (possibly exhausted) TAs:

def BMI(h, m):
    return m / (h * h)

This function, called BMI, takes in two arguments, the height h and weight m of a person, and will return the BMI of that person, using the formula mentioned above. It provides an abstraction for BMI calculation so that programmers can reuse some code fragments without typing the formula again and again.

Now we can call this function whenever we want to calculate the BMI if given height and weight. Applying a function to some expressions is done with a call expression.

>>> BMI(1.7, 70)
24.221453287197235
>>> BMI(1.6, 60)
23.4375
>>> BMI(1.8, 80)
24.691358024691358

TAs can now take some rest thanks to your help.

2.1.1 Call expressions

A call expression applies a function, which may or may not accept arguments, to zero or more expressions. The call expression evaluates to the function's return value.

The syntax of a function call:

  add   (    2   ,    3   )
   |         |        |
operator  operand  operand

Every call expression requires a set of parentheses delimiting its comma-separated operands. We refer to the function being called as the operator, and the expressions surrounded by parentheses as the operands.

To evaluate a call expression:

1. Evaluate the operator (i.e., the function), and then the operands (from left to right).
2. Apply the operator to the operands (the values of the operands).

If an operand in a call expression is itself a call expression (.e.g, BMI(1.7, BMI(1.7, 70))), then these two steps are applied to that inner operand first in order to evaluate the entire expression.

2.1.2 return and print

Most functions that you define will contain a return statement. The return statement will give the result of some computation back to the caller of the function and exit the function. For example, the function square below takes in a number x and returns the square of x.

def square(x):
    """
    >>> square(4)
    16
    """
    return x * x

When Python executes a return statement, the function containing that return statement terminates immediately. If Python reaches the end of the function body without executing a return statement, it will automatically return None.

In contrast, the print function is used to display values in the Terminal. This can lead to some confusion between print and return because calling a function in the Python interpreter will print out the function's return value.

However, unlike a return statement, when Python evaluates a print expression, the function does not terminate immediately.

def what_prints():
    print('Hello World!')
    return 'Exiting this function.'
    print('61A is awesome!')

>>> what_prints()
Hello World!
'Exiting this function.'

Notice also that print displays text without quotes, but return preserves them.

2.2 Control

2.2.1 Boolean Operators

Python supports three boolean operators: and, or, and not:

>>> True and True
True
>>> True and False
False
>>> True or False
True
>>> not True
False
>>> a = 4
>>> a < 2 and a > 0
False
>>> a < 2 or a > 0
True
>>> not (a > 0)
False

• and evaluates to True if both of its operands evaluate to True. If at least one operand is False, then and evaluates to False.
• or evaluates to True if at least one operand evaluates to True. If both operands are False, then or evaluates to False.
• not evaluates to True if its operand evaluates to False. It evaluates to False if its operand evaluates to True.

What do you think the following expression evaluates to? Try it out in your Python interpreter.

>>> True and not False or not True and False

It is difficult to read complex expressions, like the one above, and understand how a program will behave.

What about hits one?

>>> 1 * -0 + -1 * 0

As is explained in lab00, using parentheses can make your code easier to understand. Python interprets that complex boolean expression in the following way:

>>> (True and (not False)) or ((not True) and False)

This is because boolean operators, like arithmetic operators, have precedence:

• not has the highest priority, similar to negation
• and is much like multiplication
• or has the lowest priority, similar to subtraction

Truthy and Falsey Values: It turns out and and or work on more than just booleans (True, False). Python values such as 0, None, '' (the empty string), and [] (the empty list) are considered false values. All other values are considered true values.

How to prove it?

2.2.2 Short Circuiting

What do you think will happen if we type the following into Python?

1 / 0

Try it out in Python! You should see a ZeroDivisionError. But what about this expression?

True or 1 / 0

It evaluates to True because and and or operators in Python short-circuit. That is, they don't necessarily evaluate every operand.

Short-circuiting happens when the evaluation of the expression reaches an operand that allows Python to make a conclusion about the expression. For example, and will short-circuit as soon as it reaches the first false value because it then knows the expression cannot be true since not all the operands are true.

If and and or do not short-circuit, they just return the last value; another way to remember this is that and and or always return the last thing they evaluate, whether they short circuit or not. Keep in mind that and and or don't always return booleans when using values other than True and False.

Can you explain what [] and True evaluates to and why?

2.2.3 If Statements

You can review the syntax of if statements in Section 1.5.4 of Composing Programs.

Tip: We sometimes see code that looks like this:

if x > 3:
    return True
else:
    return False

This can be written more concisely as return x > 3. If your code looks like the code above, see if you can rewrite it more clearly!

2.2.4 While Loops

You can review the syntax of while loops in Section 1.5.5 of Composing Programs.

2.3 Error Messages

By now, you've probably seen a couple of error messages. They might look intimidating, but error messages are very helpful for debugging. The following are some common types of errors:

Using these descriptions of error messages, you should be able to better understand what went wrong with your code. If you run into error messages, try to identify the problem yourself before asking for help. You can always Google unfamiliar error messages to check their meaning and see if others have made similar mistakes.

For example:

>>> def square(x):
...     return x * x
...
>>> square(2024, 2024)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: square() takes 1 positional argument but 2 were given

Note:

• The last line of an error message tells us the type of the error. In the example above, we have a TypeError.
• The error message tells us what we did wrong -- we gave square 2 arguments but it can only take in 1 argument. In general, the last line of an error message is the most helpful.
• The second to last line of the error message tells us where the error occurred, which helps us track down the error. In the example above, TypeError occurred at line 1 since we are in interactive mode.

2.4 Environment Diagrams

Environment diagrams are one of the best learning tools for understanding lambda expressions and higher order functions because you're able to keep track of all the different names, function objects, and arguments to functions. We highly recommend drawing environment diagrams or using Python tutor if you get stuck doing the WWPD problems below. For examples of what environment diagrams should look like, try running some code in Python tutor. Here are the rules:

2.4.1 Assignment Statements

1. Evaluate the expression on the right hand side of the = sign.
2. If the name found on the left hand side of the = doesn't already exist in the current frame, write it in. If it does, erase the current binding. Bind the value obtained in step 1 to this name.

If there is more than one name/expression in the statement, evaluate all the expressions first from left to right before making any bindings.

Try to paste the following code in the Python tutor and understand each execution step. You can also click this link.

x = 10
y = x
x = 20
x, y = y + 1, x - 1

2.4.2 Def Statements

1. Draw the function object with its intrinsic name, formal parameters, and parent frame. A function's parent frame is the frame in which the function was defined.
2. If the intrinsic name of the function doesn't already exist in the current frame, write it in. If it does, erase the current binding. Bind the newly created function object to this name.

Try to paste the following code in the Python tutor and understand each execution step. You can also click this link.

def f(x):
    return x + 1

def g(y):
    return y - 1

def f(z):
    return x * 2

2.4.3 Call Expressions

Note: you do not have to go through this process for a built-in Python function like max or print.

1. Evaluate the operator, whose value should be a function.
2. Evaluate the operands left to right.
3. Open a new frame. Label it with the sequential frame number, the intrinsic name of the function, and its parent.
4. Bind the formal parameters of the function to the arguments whose values you found in step 2.
5. Execute the body of the function in the new environment.

Try to paste the following code in the Python tutor and understand each execution step. You can also click this link.

def f(a, b, c):
    return a * (b + c)

def g(x):
    return 3 * x

f(1 + 2, g(2), 6)

3. What Would Python Display?

In this section, you need to think about what python would display if the code below were input to a python interpreter.

Question 1: Control

In What Would Python Display problems, always follow these rules:

For each of the expressions in the table below, write the output displayed by the interactive Python interpreter when the expression is valued. The output may have multiple lines. Each expression has at least one line of output.

• If an error occurs, write Error, but include all output displayed before the error.
• If an expression would take forever to evaluate, write Forever.

The interactive interpreter displays the value of a successfully evaluated expression, unless it is None.

Check your answers with python ok -q q1 -u. You need not modify any files to answer WWPD problems!!

>>> def xk(c, d):
...     if c == 4:
...         return 6
...     elif d >= 4:
...         return 6 + 7 + c
...     else:
...         return 25
>>> xk(10, 10)
______

>>> xk(10, 6)
______

>>> xk(4, 6)
______

>>> xk(0, 0)
______

>>> def how_big(x):
...     if x > 10:
...         print('huge')
...     elif x > 5:
...         return 'big'
...     elif x > 0:
...         print('small')
...     else:
...         print("nothin'")
>>> how_big(7)
______

>>> how_big(12)
______

>>> how_big(1)
______

>>> how_big(-1)
______

>>> n = 3
>>> while n >= 0:
...     n -= 1
...     print(n)
______

Hint: Make sure your while loop conditions eventually evaluate to a false value, or they'll never stop! Type Ctrl-C will stop infinite loops in the interpreter.

>>> positive = 28
>>> while positive:
...     print("positive?")
...     positive -= 3
______

>>> positive = -9
>>> negative = -12
>>> while negative:
...     if positive:
...         print(negative)
...     positive += 3
...     negative += 3
______

Question 2: Veritasiness

Submit your answers with python ok -q q2 -u.

>>> True and 13
______

>>> False or 0
______

>>> not 10
______

>>> not None
______

>>> True and 1 / 0 and False
______

>>> True or 1 / 0 or False
______

>>> True and 0
______

>>> False or 1
______

>>> 1 and 3 and 6 and 10 and 15
______

>>> 0 or False or 2 or 1 / 0
______

>>> not 0
______

>>> (1 + 1) and 1
______

>>> 1/0 or True
______

>>> (True or False) and False
______

Question 3: What If?

Submit your answers with python ok -q q3 -u.

>>> def ab(c, d):
...     if c > 5:
...         print(c)
...     elif c > 7:
...         print(d)
...     print('foo')
>>> ab(10, 20)
______

>>> def bake(cake, make):
...     if cake == 0:
...         cake = cake + 1
...         print(cake)
...     if cake == 1:
...         print(make)
...     else:
...         return cake
...     return make
>>> bake(0, 29)
______

>>> bake(1, "mashed potatoes")
______

4. Environment Diagram

In this section, you need to draw the environment diagrams of provided code.

You don't have to submit your answers, which means the questions in this section don't count for your final score. However, they are great practice for future assignments, projects, and exams. Attempting these questions is valuable in helping cement your knowledge of course concepts.

Question 4: Bake Cake

Draw the environment diagram of the following code.

def square(x):
    return x * x

def bake(cake, make):
    if cake == 0:
        cake = cake + 1
        print(cake)
    if cake == 1:
        print(make)
    else:
        return cake
    return make

cake = square(0)
bake(cake, 29)

You can view the correct environment diagram here.

4. Required Problems

In this section, you are required to complete the problems below and submit your code via VSCode plugin or Ok to get your answer scored.

Remember, you can submit your code via the VSCode plugin:

1. Ctrl+Shift+P
2. Type submit
3. Press Enter

Or you can use Ok to test your code:

$ python ok

and submit your work when you are done:

$ python ok --submit

Problem 1: Fix the Bug (100pts)

The following snippet of code doesn't work as expected! Figure out what is wrong and fix the bug.

def both_odd(a, b):
    """Returns True if both a and b are odd numbers.

    >>> both_odd(-1, 1)
    True
    >>> both_odd(2, 1)
    False
    """
    return a and b % 2 == 1 # You can replace this line!

Test your implementation with python ok -q both_odd.

Problem 2: Factorial (100pts)

Write a function that takes a positive integer \( n \) and returns its factorial.

Factorial of a positive integer \( n \) is defined as

\[ n! = \prod_{i=1}^n i = 1 \times 2 \times 3 \times \dots \times n. \]

def factorial(n):
    """Return the factorial of a positive integer n.

    >>> factorial(3)
    6
    >>> factorial(5)
    120
    """
    "*** YOUR CODE HERE ***"

Test your implementation with python ok -q factorial.

Problem 3: Is Triangle? (100pts)

Write a function that takes three integers (may be nonpositive) and returns True if the three integers can form the three sides of a triangle, otherwise returns False.

def is_triangle(a, b, c):
    """Given three integers (may be nonpositive), judge whether the three
    integers can form the three sides of a triangle.

    >>> is_triangle(2, 1, 3)
    False
    >>> is_triangle(5, -3, 4)
    False
    >>> is_triangle(2, 2, 2)
    True
    """
    "*** YOUR CODE HERE ***"

Test your implementation with python ok -q is_triangle.

Problem 4: Number of Nine (100pts)

Write a function that takes a positive integer \( n \) and returns the number of \( 9 \) in each digit of it. (Using floor division and modulo might be helpful here!)

def number_of_nine(n):
    """Return the number of 9 in each digit of a positive integer n.

    >>> number_of_nine(999)
    3
    >>> number_of_nine(9876543)
    1
    """
    "*** YOUR CODE HERE ***"

Test your implementation with python ok -q number_of_nine.

Problem 5: Min Digit (100pts)

Write a function that takes in a non-negative integer and return its min digit. (Using floor division and modulo might be helpful here!)

def min_digit(x):
    """Return the min digit of x.

    >>> min_digit(10)
    0
    >>> min_digit(4224)
    2
    >>> min_digit(1234567890)
    0
    >>> # make sure that you are using return rather than print
    >>> a = min_digit(123)
    >>> a
    1
    """
    "*** YOUR CODE HERE ***"

Test your implementation with python ok -q min_digit.

Test your code for lab01 with python ok, and submit with python ok --submit.