T-Th 9:05
or
T-Th 11:15
in Olin 155

CS 1110: Introduction to Computing Using Python

Fall 2013

Assignment 2:
Call Frames

Due to CMS by Tuesday, October 1st at 11:59 pm.

This is a simple written assignment where you are going to diagram a few call frames. It should not take more than 15-20 minutes do to this assignment. So even if you are busy revising assignment 1, you should be able to do this assignment as well. With that said, keep track of the actual time that you spent on this assignment for the survey.

“Diagramming” is what we do in the lecture notes where we draw frames to represent function calls and folders to represent the objects. These are a way of giving us a visual representation of what is going on in the computer when it runs Python. The purpose of this assignment is to solidify your understanding of how function calls work.

Learning Objectives

This assignment is design to help you understand the following concepts.

• How to diagram variables and objects.
• How to diagram the change in a call frames during function execution.
• The difference between a call frame and global space.
• Why folders are necessary for representing mutable objects.

Table of Contents

Authors: W. White, L. Lee, S. Marschner

• Academic Integrity and Collaboration
• Diagramming Conventions
• Diagramming Variables
• Diagramming Objects
• Diagramming Function Calls
• Assignment Instructions
• Part A
• Part B
• Part C
• Finishing the Assignment

Academic Integrity and Collaboration

Academic Integrity

This assignment is a slightly modified version of an assignment given in a previous semester. Please do this assignment without consulting (or seeking) previous solutions. Consulting any prior solution is a violation of CS1110's academic integrity policies.

Collaboration Policy

You may do this assignment with one other person. If you are going to work together, then form your group on CMS as soon as possible. This must be completed before you submit the assignment. Both people must do something to form the group. The first person proposes, and then the other accepts. You do not need to have the same partner as last time; you can change your partner with each assignment.

If you do this assignment with another person, you must work together. It is against the rules for one person to to fill out this assignment and just have the other person put their name at it. You should actively collaborate on this assignment. You may not collaborate with anyy other than your CMS partner.

Getting Help

Even though this is just a written assignment, some of you may still have some difficulty with it. You might not completely understand how function calls work or the purpose of folders. If you are lost, please see someone in the course staff. This can be the course instructor, a TA, or a consultant. Furthermore, do not wait until the last minute, as the course staff is generally overwhelmed just before an assignment deadline.

Diagramming Conventions

Most of our diagramming conventions follow the lecture notes. However, just to be safe, we will make our conventions explicit here.

Diagramming Variables

A diagram for a variable should include the variable name and a box for the value. We 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 or in scientific notation, 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 (e.g. the contents of the folder can be changed). All of the base types — int, float, bool, and str — are immutable. Therefore we draw all of these values inside the variable referring to them.

So far the only mutable objects we have seen are those with named attributes, like those of type Point.

You will not be responsible for figuring out how to diagram an object in this assignment. For any mutable object (which requires a folder), we will show you how to diagram the object. When you diagram an object you should obey the following conventions:

• The folders 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 Point from Lab 3 might look like this:

Diagramming Function Calls

Call frames are the way we diagram the temporary workspace where the variables used during a call to a function are stored. Diagrams of frames should obey the following 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.

• Unless otherwise stated, the first line of code after the function header corresponds to a counter value of 1.

• 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. In order to help you with the instruction counter, we will always number the lines of code for you. For example, suppose we have the procedure

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

If we execute the call print_name("White","Walker"), 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 1, 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 boxes to show how it changes over time.

As a general rule, we should draw a separate diagram for each value of the program counter, corresponding to a single line of Python code. The diagram above refers to the call frame after we finish line 1. Once we finish line 2, the diagram for the call frame is as shown below.

Note the instruction counter is blank. 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 draw one more diagram, crossing out the frame.

Frames and Return Values

If you play with the Online Python Tutor, you will not that it adds a special variable for the return value when it reaches the last line of the function. It does this even for procedures (i.e. functions with no return statement); in that case the return statement is None. This variable is added when there are no lines left to execute, as in the example below:

We are not following this convention, and you are not expected to do this. We will not mark it wrong, but you will not be penalized for omitting it.

Assignment Instructions

In this assignment you will diagram the execution of three different function calls. For each function call, you will draw a separate diagram for each line of Python that is executed (and only those lines that are executed). We also want you to draw one last diagram crossing the frame off at the end.

Function min(a,b)

The function min is built into Python. However, if we were to design it ourselves, it might look like this:

   def min(a,b):
       """Returns: min of a and b"""
1      minimum = a
2      if (b < a):
3          minimum = b
4      return minimum

Part A: Diagram the Execution of c = min(1,2)

Draw the execution of the statement c = min(1,2). You will need to draw the evolution of the call frame over time. This will require several diagrams. You will need a diagram when the frame is created, and another when it is erased. In between, you will need a diagram for each line of code that is executed (and only the lines which are executed). Remember, this is one call frame, but several diagrams showing how the call frame changes over time.

When an assignment changes the value of an existing variable in the frame, we would like you write the old value in the box, cross it out, and write the new value in the box.

In addition to the diagrams for the (evolution of the) call frame, you also need to diagram the global variable c.

Part B: Diagram the Execution of d = min(b,a)

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

As we said in class, these variables are global variables and are not the same as the parameters of min, which are local to that function.

Repeat the previous exercise for the statement d = min(b,a). The approach is similar, except that the globable variable is now named d.

Function rot_x(q)

The function rot_x(q) function is a variation on the shift(q) function from Lab 3. It takes a point as input and swaps the y and z attributes; the x attribute is left unaltered. (This is a rotation around the x axis.) We define this function as follows: <

   def rot_x(q):
       """Swap the y and z attributes of q

       Example: The point (1,2,3) becomes (1,3,2)

       Precondition: q is (refers to, contains the ID of) a point object"""
1      tmp = q.y
2      q.y = q.z
3      q.z = tmp

Part C: Diagram the Execution of rot_x(p)

The function rot_x is a procedure (it has no return statement) and so it does not need to be used in an assignment statement. So the call rot_x(p) is a statement by itself.

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

  p = Point(1,2,3)
  q = Point(4,5,6)

Diagram the call rot_x(p) given the global variables shown above. Include the global variables p and q and the objects they refer to, as well as any other variables and objects that are created, in your diagram. If the contents of the objects folders are altered, you should cross out the old value and write in the new value.

Your answer to this problem will also include a sequence of diagrams for the call frame for rot_x(p). Again, you should have a diagram when the frame is created, a diagram for each line executed, and a diagram for deleting the frame.

Finishing the Assignment

When you finish the assignment, put your name and netid at the top of the page. Otherwise, we will not know that the assignment is yours, and we cannot give you credit for your work. If you are working with a partner, then the partner's name must be on the assignment as well. In addition, to help us out with organization, please underline your last name(s).

Because of the size of this class, we want you to submit this assignment online through CMS. To do this, you must submit your file 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.

Your submission must be uploaded to CMS by Tuesday, October 1st at 11:59 pm. If you are planning to scan your submission, we recommend that you finish long enough ahead of time to give you time to scan.

Survey

Once again, this assignment comes with a survey on CMS. This survey asks how long you spent on the assignment, your impression of the difficulty, and what could be done to improve it.

Please try to complete the survey within a day of turning in this assignment. Remember that participation in surveys compromise 1% of your final grade. We also ask that you be honest in your answers.