Assignment 2 - Call Frames

Diagramming Conventions

Most of our diagramming conventions follow the Spring 2019 lecture notes. However, just to be safe (and because these conventions are different from the Fall offering of CS 1110), we will make our conventions explicit here. If you are someone who likes seeing worked examples, here is a small piece of code and three different corresponding diagrams: one done as a video by Prof. Bracy, one by Prof. Lillian Lee and one by Prof. Steve Marschner. Please note that the two drawings are from a semester that had a different convention about where to indicate the return value, but otherwise the notation is the same.

Diagramming Variables

A diagram for a variable should include the variable name and a box for the value. When we reassign a variable, old values are crossed out when they are replaced by new ones.

For example, here is a diagram for the variable b, currently holding the integer 2:

When writing the value, the only rule is to make sure it is unambiguous what the value is, and what type it is. Write floats with a decimal point, strings with quotes around them, and so forth.

---

Diagramming Objects

All values in Python are objects, but we only bother to draw an object separately from variables referring to it if the object is mutable (i.e., the contents of the folder can be changed). All of the base types — int, float, bool, and str — are immutable. So far the only mutable objects we have seen are those with named attributes, like those of type Point3.

When you diagram an object you should obey the following conventions:

• The folder's identifier (ID, or true name) should be unique and go on the folder tab.
• The type of the object should go at the top right of the folder.
• The attributes should be listed inside the folder and diagrammed just like variables.

For example, a folder for an object of the type Point3 from class might look like this:

---

Diagramming Function Calls

Call frames show the temporary workspace where Python stores the variables used during a function call. Diagrams of frames should follow these conventions:

• The top left corner is a box with the function name.

• The top right counter is the program counter. This is next line of code to execute in the function.

• When the call frame is first drawn, the instruction counter should contain the first line of executable code after the function header.

• Local variables and parameters are diagrammed in the frame body; we do not distinguish between them.

• Local variables are not added until the instruction counter reaches the line where they are first defined.

See the lecture notes for more details on how to create a call frame. We will always number the lines of code for you. For example, suppose we have the procedure

1  def print_name(last, first):
2      greet = 'Hello '+first+' '+last+'!'
3      print greet

If we execute the call print_name("Sotomayor","Sonia"), then the call frame starts out as follows:

The Evolution of a Call Frame

A call frame is not static. As Python executes the body of the function, it alters the contents of the call frame. For example, after we have executed line 2, the call frame now looks as follows:

This is not a new call frame; this is the same call frame shown at a different point in time. The call frame does not go away until the function call is completed. When we diagram a call frame, we are actually diagramming a sequence of changes to a single box to show how it changes over time as each line of code is executed.

As the program counter changes, we cross out the prevous value (keeping it legible). The diagram above refers to the call frame after we finish line 2. Once we finish line 3, the diagram for the call frame is as shown below.

(Note: the RETURN variable will be explained in the following section and is shown only for completeness purposes.) Note that there is no instruction counter (they are all crossed-out). That is because there are no more instructions to execute. However, the call frame is not yet deleted. To represent the deletion of the call frame, we cross out the frame:

Frames and Return Values

Fruitful functions have a return value. For example, consider the following function:

1  def get_feet(ht_in_inches):
2     feet = ht_in_inches // 12
3     return feet

When you execute a return statement, it makes a special variable called RETURN which stores the result of the expression. For example, suppose we have the function call get_feet(68). After executing line 2 of the code, above, the call frame is as follows:

When you execute the next line, the instruction counter becomes blank (because there is nowhere else to go), but you add the RETURN variable.

If you play with the Python Tutor, you will note that it always adds a RETURN variable, even for procedures (i.e., functions with no return statement). In this case it stores the value None into the RETURN variable. This was done above in the print_name("Sotomayor","Sonia") example above, copied here again for your convenience:

We follow this convention in class. Before a function's call frame is crossed out, you should have drawn the variable RETURN with its value in the box. Before a procedure's call frame is crossed out, you should have drawn the variable RETURN with the value None in the box.

Frames and Global Space

A function call is an expression. The call evaluates to the result of the return statement. If this call is used in an assignment statement, there is a way to copy from the RETURN variable to another place in memory, such as global space. For example, the call

  ft = to_feet(68)

will copy the final result (5) into the global variable ft.

If a function call is used in an assignment statement, then the value in the box is not changed until the step where you erase frame. In fact, if this is the first time that you are assigning the variable, you do not even create the box for the variable until the frame is erased.

If you were asked to draw the state of memory prior to the return statement on line 3 of get_feet, there would not yet be a variable y in the global space. It is only created after the call frame is erased.

Modules and Functions in Global Space

As we saw in class, global space also has variables for the function and module names. For example, when you define a function, it creates a folder for the function body and stores the name of that folder in a variable with the same name of the function.

We do not want you to draw these variables in global space. You can ignore what happens to function definitions (and module importing) for now.

---

Diagramming Conditionals

Be careful when executing code that contains conditionals (marked by if statements). Not every line of an if-else block of code will be executed. Consequently, not every line number will appear in the program counter box. Consider the following example:

Notice that Python executes the assignment statement on line 2, then the if statement on line 3. Because the boolean expression x==5 evaluates to False, Python skips all indented lines that follow line 3. Python executes the elif statement on line 5. Because the boolean expression x==4 evaluates to False, once again Python skips all the indented lines that follow line 5. Python executes line 7 (to discover that this time it need not evaluate any boolean expression at all!) and then executes each indented line after line 7--in this case, that is simply line 8. After line 8 is executed Python creates the None return value and the call frame is deleted.

Assignment Instructions

Remember that there are three memory locations that we talked about in class: global space, call frames, and heap space. Every time that you execute a line of code, these can all change. We want your drawings to reflect these changes while impressing upon you that the variables, program counters, and call frames are modified in place, not duplicated as each line of code executes.

For each problem, you will be given a function call. We want you to diagram the execution of four different function calls (one each in Questions 1, 2, 3, and 4). You will draw a single diagram that reflects the changes over time, by crossing out old values and inserting the new ones to the right. It is not enough to simply show the final state of the diagram. We want to see the intermediary steps. If a function call returns, we also want you to cross the frame off neatly so that its contents are still legible.

Some of the problems below will have associated values in both global space and heap space. For those problems, you should also diagram the evolution of both global space and heap space. Each line of code should trigger some change to your drawing.

Important: You must pay close attention to types in this assignment. The value 3 is an integer while the value 3.0 is a float. Hence they are different values. If you answer with an integer like 3 when the correct answer is a float like 3.0, we will deduct points.

---

Function isLongerThan

Consider the function isLongerThan, defined below:

1   def isLongerThan(s,n):
2       """Returns: True if string s is longer than len n.
3       Otherwise, return False.
4       
5       Precondition: s is a string, n is an int"""
6
7       length = len(s)
8       if (length > n):
9           return True
10      else:
11          print("Given string has too few characters.")
12          return False

Question 1.1: Diagram the Execution of a = isLongerThan("n",4)

Draw the execution of the statement a = isLongerThan("n",4). You will need to draw the evolution of the call frame over time. This will require several modifications to the same diagram. Begin by drawing the diagram when the frame is created. Now modify the diagram for each line of code that is executed (and only the lines which are executed). Since we are only drawing a single call frame, you must neatly indicate how it has changed over time.

When an assignment changes the value of an existing variable in the frame, legibly cross out the old value and write the new value in the box. If we cannot read the old value, we can give you points for it being correct.

In addition to the diagram of the call frame, you also need to diagram the evolution of the global variable a. The global space starts out empty (we are ignoring the variable for the function isLongerThan); at some point, the variable a will be created.

You do not need to draw the evolution of heap space, as there is nothing interesting in heap space for this problem. Also, you do not need to draw the result of print statements. Although it might be nice to show that (and the Python tutor does), we are diagramming the state of memory which is entirely distinct from what is printed to the screen by a program.

Question 1.2: Multiple Choice

Because our drawing convention does not have a good way of annotating the time of a variable's creation, we ask you to answer the following multiple choice question after you draw your diagram:

The variable a is created:
---------------------------
A) When Python executes line 1.
B) Just before Python calls isLongerThan.
C) Just after Python returns from isLongerThan.
D) The time of creation could change each time the code is executed.
E) There is not enough information given to answer the question.

Somewhere near your answer to Question 1.1, please write "The answer to Question 1.2 is F." But replace F with your answer.

Question 2: Diagram the Execution of b = isLongerThan(attempt,length)

For this question, suppose that you have the following (global) variables:

Repeat the previous exercise for the statement b = isLongerThan(attempt,length). Once again, you need to draw the evolution of global space as well as the individual frame diagram. The difference is that this time global space does not start out empty. In addition, the new global variable is now named b.

---

Functions on Student Objects

The next two problems have to do with the Student class. Objects of the Student class have three attributes, all of them strings:
  netid: the student's unique identifier (e.g., "abc123")
  am: course code for their morning course (e.g., “CS1110”)
  pm: course code for their afternoon course (e.g., “MATH1920”)
These objects are created by the constructor call Student("abc123","CS1110","MATH1920").

When dealing with objects, you should remember that a variable does not contain an object; it can only hold the identifier of the object. Therefore, the assignments

s1 = Student("abc123","HADM4300","VIEN1104")
s2 = Student("def456","PE1657","PE1130")

would produce the following contents in both global and heap space

In this case we have folders representing two Student objects, and two global variables storing these object identifiers. We made up the folder identifier numbers, as their value does not matter. If we ask you to make a Student object, you should feel free to make up the identifier number, but make sure it is different from the ones currently in s1 and s2.

Question 3: Diagram the Execution of course_swap(s1)

According to the definition of the Student class, a student takes only 2 classes: a morning class and an afternoon class. The function course_swap() allows students to swap their morning and afternoon courses. It takes a student as input and swaps the am and pm attributes; the netid attribute is left unaltered. We define this function as follows:

1  def course_swap(st):
2       """Swap the am and pm attributes of st
3
4       Example: The student (netid: "ee222", am: "CS1110", pm: "MATH1920") 
5       becomes (netid: "ee222", am: "MATH1920", pm: "CS1110")
6
7       Parameter st: the student to swap morning and afternoon courses
8       Precondition: st is (refers to, contains the ID of) a student object"""
9       tmp = st.am
10      st.am = st.pm
11      st.pm = tmp

The function course_swap is a procedure (i.e., it has no return statement) and so it does not need to be used in an assignment statement. Hence the call course_swap(s1) is a statement by itself.

Diagram the call course_swap(s1) given the global variables and heap space shown above. Your answer will in include a single diagram that is modified over time. Again, your diagram should show that the frame is created, the result of each line of code that is executed, and a then the frame is deleted.

Your diagram should also include the evolution of the global variables s1 and s2, and the corresponding objects in heap space. If the contents of any global variable change, or the contents of the object folders are altered, you should cross out the old value and write in the new value.

Question 4: Diagram the Execution of s1 = course_swap2(s2)

The function course_swap2(st) is similar to course_swap(st), except that it is a fruitful function instead of a procedure. We define the function as follows:

1  def course_swap2(st):
2      """Returns: A copy of st with the am and pm attributes swapped
3
4      Example: course_swap2 with argument ("ee222", "CS1110", "MATH1920")
5      creates the student object ("ee222",  "MATH1920", "CS1110")
6
7      Parameter st: the student whose schedule to swap
8      Precondition: st is (refers to, contains the ID of) a student object"""
9      newstu = Student("","","")
10     newstu.netid = st.netid
11     newstu.am = st.pm
12     newstu.pm = st.am
13     return newstu

Diagram the execution of the statement s1 = course_swap2(s2) given the global variables and heap space shown above. Assume that you are starting over with s1 and s2; do not include any changes from Question 3.

As always, your diagram should show that the frame is created, the results of each line of code being executed, and that the frame is deleted. You should show how the global space and heap space change over time. If the contents of any global variable change, or the contents of the object folders are altered, you should cross out the old value and write in the new value.

---

Working in Reverse

So far in this assignment, we have given you a function definition and asked you to draw the diagram for a function call. Now we want you to do the reverse. We give you the diagrams for several function calls and ask you to write the corresponding definition. All you have to do is write out the Python code. Any function definition is correct so long as it produces the frame shown for each call.

Question 5: Define the function alphabetize(word1,word2)

The function alphabetize has the following specification:

def alphabetize(word1,word2):
    """Returns: the two words alphabetized and concatenated.

    For Example:
    alphabetize('John', 'Wyatt') returns 'John Wyatt'
    alphabetize('Mary', 'Anne') returns 'Anne Mary'

    Parameter word1: first word
    Parameter word2: second word
    Precondition: word1 and word2 are strings"""

The following diagrams illustrate the function calls alphabetize('John', 'Wyatt') and alphabetize('Mary', 'Anne'), respectively.

Complete the function definition. Remember: you must produce code whose execution would produce the above diagram. Completing the function according to spec is not enough!

Hint: The alphabetic ordering of two strings can be compared in a single line.

Finishing the Assignment

When you finish the assignment, put your name and netid at the top of the page. If you are working with a partner, then the partner's name must be on the assignment as well.

---

Creating a PDF for Submission

You will submit your work as a PDF. If you created your assignment on a computer, this should be relatively easy. Otherwise, you will need to scan your paper as a PDF. There are scanners in Olin and Uris Library to help you with this. You can also scan your homework using a mobile device. Please allow enough time do the scanning. Don't miss the deadline because of a scanning fiasco.

You may not submit multiple PDF files. If your scanner makes more than one file, you must combine them. On Windows, the program PDFtk can merge multiple PDF files into one file. In OS X, the built-in application Preview can be used to merge PDF files.

---

Upload your PDF to Gradescope

Please submit your assignment to Gradescope. An account has been created for you with your Cornell NetID email address. (You should have received an email from Gradescope earlier this week; check your spam folder if you cannot find it. If you still cannot find it, you can perform a password reset using your Cornell NetID email address.)

Once you've performed the upload, it's a good idea to view your online submission to make sure it is readable and complete.

---

Survey

We ask that you complete a feedback survey, which will be posted on Canvas on Feburary 16. We would like to know how long you spent on the assignment, your impression of the difficulty, and what could be done to improve it. Please complete the survey within a day of turning in the assignment. Remember that participation in surveys compromise 1% of your final grade. Your honest feedback is very helpful to us.