Assignment 2: Frame and Object Notation
Due IN CLASS on Tuesday, March 4th
Authors: S. Marschner, L. Lee, W. White, D. Gries
Preliminaries
One-shot Submission From Now On
This assignment, and all subsequent ones unless otherwise noted,
will receive a single grade; there is no revise-and-resubmit like there was for Assignment 1.
Collaboration Policy
You may do this assignment in groups of size one up to four. 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, even though you are handing the assignment in on paper. It takes actions on CMS
from all parties to form the group. You can have different groups for each assignment.
You may not collaborate with anyone other than your CMS-registered partners.
You should actively collaborate with all your group members because
you, individually, need to know this stuff cold for the exams.
Learning Objectives (Which Have Grading Implications)
The purpose of this assignment is to give you practice executing Python code
on paper using the notation we have introduced in class. You need to be able to
do this quickly and confidently—uncertainty about what to draw is a sign
that you don't really understand what the programs you write are going to do.
The importance of the notation we have introduced in class is that it gives
us a precise visual language for
describing and understanding exactly what Python is doing when it executes code. In this
assignment, you will use this notation to demonstrate your understanding of
what happens during the execution of a
given sequence of statements, and on exams you will likewise use this same language
to prove your understanding. In complex coding situations, we use these
kinds of diagrams ourselves to figure out what's going on.
Concepts tested:
- What statements create variables or change the values of what variables (including
global variables, local variables, and object attributes).
- That the result of a constructor expression is the ID of the new object
that is created.
- That frames summarize the state of the process of executing a function call. The variables they contain store information
local to the corresponding function, and
indicate what that function can affect; the program counter records what line
number should be executed next.
- Parameters are local variables that
serve the purpose of holding the input values that the function is supplied
when called.
- Arguments are the input values that are supplied to a function when the function
is called, and are assigned to the corresponding parameter variables.
- Which statements of an if-statement are executed in a given setting.
Given these learning objectives, some seemingly minor but actually tragic mistakes you can expect to lose points
for committing are:
- Drawing fewer objects in your drawing than the number of constructor
expressions that are evaluated during execution.
- In the frame for a call to a function, not drawing a correspondingly named box
for each parameter in that function's header.
- Drawing non-existent variables (indicating that you believe in their
existence).
Some seemingly minor notational mistakes that could indicate
deeper misunderstandings and thus risk point deductions are:
- Writing the name of a variable, say
x , inside of the box for another variable, say
a box named y , instead of a value [The problem: if
x 's value is subsequently changed, you would predict the wrong
value for y ].
- Writing a variable name on the tab of an object instead of a value [The problem: if the
variable's value changes, you would incorrectly predict that the object's ID
changes too].
- Not having the correct sequence of crossed-out line numbers in the frame's
program counter [The problem: you might be misunderstanding where the flow of execution
goes next].
Additionally, it would be silly if the final values of the variables
on your paper are not the same as the ones that result when you actually
run the code on your computer using Python itself.
Getting Help
If you do not know where to start, if you do not understand how function calls work, or
if you feel completely lost, please talk to someone immediately. This could be
an
instructor, a TA, or a consultant. Do not wait until the last minute! See the
staff page for drop-in office hours
and other contact information.
Notational Conventions
Most of our notational conventions for this assignment follow the lecture notes. There's a
one-slide
summary of “How to Draw Things” on the Lecture
6 handout. When you are using the frames-and-objects notation on paper:
- Do not erase any values, objects, or frames. For values that are
changed, the old value should be neatly crossed out such that we can see what the
old value was; and the new value should be written next to it. Similarly,
frames should be crossed out rather than erased, and objects should never be
removed.
- When function execution ends, cross out the final value of the program counter.
The series of crossed-out program counter values is a record of which lines were
executed during the function call.
- If a function call returns some value v, write “Return:
v” just below or to the right of the crossed-out frame.
For example, “Return: 3” for a function call that returned the
integer value 3. (Be sure you are writing a value, not a variable name.)
- Place your frames so that their position reflects the order in which they
were created; we recommend starting at the top and drawing each frame below
the previous one.
In this assignment you don't need to bother with the module name in the function frames,
since there is only one module involved.
Depicting the Creation of New Objects
Since we haven't covered class definitions in detail yet, assume that the
creation of a new object and initialization of its attributes happen
in one step. (That is, don't worry about the __init__ function in the
class Point2 or draw a frame for it. Later on in the course we will
worry about this function.)
Worked Example
To help you with this assignment, we are providing a worked example. The code
is a2_example.py. Here are two diagrams of the execution of the example
code:
one by Prof Lee and
one by Prof Marschner. We give two solutions to give an idea
about variations in notation we don't care about, like whether or not you draw
a box around the class name in the upper-right of an object.
The Code to Execute
Below, and also in the file a2.py,
is the code you are to work with. Your submission should consist of a diagram,
compliant with the notational conventions discussed above,
showing
what happens during the execution of lines 44-50 when you run this script by typing
“python a2.py ”. Don't draw the class object for
Point2 or the function objects for the five function
definitions.
The class definition for Point2 in lines 5-9 below means that a constructor
call like Point2(100,200) creates a new Point2 object with an
x attribute holding the value 100.0 and a y attribute
holding the value 200.0.
Employing our notation correctly is a way of proving that
you know what a , b , c , h1 , and h2 store or refer to,
and that you know whether or not each function does what its specification
claims it does.
We'll tell you that our solution depicts 5 global variables, between 2 and 8
objects (inclusive), and between 5 and 8 crossed-out frames
(inclusive). Our solution also indicates to us that at least one of the function specifications is
actually incorrect.
1
2
3
4
5 class Point2(object):
6 """A class representing points in a 2D plane."""
7 def __init__(self,x,y):
8 self.x = float(x)
9 self.y = float(y)
10
11 def midpoint(p,q):
12 """Return: a new point at the midpoint of the points p and q."""
13 mx = (p.x + q.x) / 2
14 my = (p.y + q.y) / 2
15 mp = Point2(mx, my)
16 return mp
17
18 def move_to_mid(p, q):
19 """Move p to the midpoint of p and q."""
20 p = midpoint(p,q)
21
22 def min_max(p, q):
23 """Move p to bottom left and q to upper right of the rectangle they define."""
24 if q.x < p.x:
25 t = p.x
26 p.x = q.x
27 q.x = t
28 if q.y < p.y:
29 t = p.y
30 p.y = q.y
31 q.y = t
32
33 def dist_sqr(p,q):
34 """The squared distance between the points p and q."""
35 dx = p.x - q.x
36 dy = p.y - q.y
37 return dx**2 + dy**2
38
39 def half_dist_sqr(p,q):
40 """The square of half the distance from p to q."""
41 mp = midpoint(p,q)
42 return dist_sqr(mp, p)
43
44 a = Point2(1, 2)
45 b = Point2(5, 0)
46 c = midpoint(a, b)
47 min_max(c, a)
48 h1 = half_dist_sqr(a, b)
49 move_to_mid(a, b)
50 h2 = dist_sqr(a, b)
Using Python Tutor
You should definitely run this code on your computer, and add some print statements
at the end to show you what values ended up where. You can catch most mistakes you might
make by comparing your on-paper results to the results of actual execution.
You are also highly encouraged to use Python Tutor to step
through the code above line by line and thus
get a clearer picture of what Python does during execution.
If you want to use Python Tutor, copy the contents of the file a2.py into it. (Don't copy from this web page, because you don't want to
include the line numbers in Python Tutor.)
You may want to change Python Tutor's
“draw references using arrows” option to “use text labels
for references”.
Be aware that some of Python Tutor's notational and display conventions differ from what we
use in this class and are expecting on this assignment. Examples: it removes “lost” objects,
which we don't; we are not including class folders or function objects (unless necessary—and it's
not necessary in this assignment);
Python Tutor produces a frame for __init__ whereas we're not asking you to do
this for this assignment.
And note that on exams,
you will need to understand what objects, frames, and variables are created and altered
without having Python Tutor by your side. Just as an accomplished violinist can perform a concerto
without the score and a neurosurgeon can identify the hippocampus without referring to a diagram,
a proficient programmer can understand code by reading it, without having to try it out
to see what it does. The ability to flawlessly predict the
execution of programs just by looking at them will tell you (and us!) that you truly know how
Python programs work.
Moreover, as we've often mentioned with
respect to iClicker questions in class, you often learn more from making
mistakes and being corrected than from being right the first time.
We thus recommend that you try doing this assignment a bit at a time by hand, each
time checking your partial answers
against what Python Tutor produces.
Turning in the Assignment
When you finish the assignment, put the names and netids of all group members, last names in ALL CAPS,
first names not in all caps, at the top of
the page (your entire group should collectively submit just one sheet of paper). Otherwise, we will not know that the assignment is yours, and we
cannot give you credit for your work; and if we can't tell your first name(s) from your last name(s),
we may misfile your work or your grade.
Remember whose name you put first; that is whose (last) name we will
alphabetize the (single) group submission by, and you'll need to know this in
order to pick up the grading feedback.
We highly recommend that before submission, you double-check your answers
against the learning-objectives remarks made above.
Bring the assignment
to class on the day it is due, Tuesday, March 4th, to hand it in.
We will start grading this
immediately in order to get you feedback significantly before the first prelim, so please make sure the assignment is turned in on time.
|