Difference between revisions of "Environment diagram"

From CS 61A Wiki
Jump to: navigation, search
[unchecked revision][checked revision]
(<code> tags)
(Added environment navbox)
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
An '''environment diagram''' is a visualization of the frames of a program and all the existing bindings.
+
{{Sufficient-class}}
 +
An '''environment diagram''' is a tool to show the state of a program after the execution of a certain number of lines. More precisely, it is a visualization of the [[frame]]s created by running a program, along with the bindings of each frame.
  
== Frame ==
+
== Structure ==
A ''frame'' contains ''bindings'', which map a name/variable to a value. A function call creates a new frame whose parent is the current frame.
+
Environment diagrams are divided into two columns: on the left side is the ''stack frame'' (where all frames are) and on the right side, the ''heap'' (where all objects are).
  
The first frame is the ''global frame''.
+
=== Stack ===
 +
The stack frame is a group of frames. When a function is called, a new frame is created and placed on top of all the other frames. When that function terminates, the frame is removed.
  
== Environment ==
+
Every local frame (i.e., not global) should have a frame number, a parent label, and a return value that will be filled out when the function terminates. Then, within the frame, names go on the left hand side, and the associated values go on the right hand side. Values can be primitives or object references (arrows pointing to an object in the heap).
An ''environment'' consists of a sequence of frames. For example, in the following code:
+
<syntaxhighlight lang="python">
+
x = 1
+
y = 2
+
def outer():
+
    x = 3
+
    y = 4
+
    def inner():
+
        x = 5
+
        y = 6
+
    return inner
+
outer()()
+
</syntaxhighlight>
+
the sequence of frames that makes up the environment of <code>inner</code> is <code>inner</code> → <code>outer</code> → <code>global</code>. Here are the bindings in each frame:
+
{| class="wikitable" style="text-align:center"
+
! frame
+
! x
+
! y
+
|-
+
! <code>global</code>
+
| 1 || 2
+
|-
+
! <code>outer</code>
+
| 3 || 4
+
|-
+
! <code>inner</code>
+
| 5 || 6
+
|}
+
  
== Variable lookup ==
+
=== Heap ===
A name evaluates to the value bound to that name in the earliest frame of the current environment in which that name is found. In other words, to lookup a name in an environment, start looking in the local frame, then in the parent frame (if it exists), until you get to the global frame. For example, in the following code:
+
The heap holds objects. Most commonly, these will be function objects, [[tuple]]s, and [[list]]s.
<syntaxhighlight lang="python">
+
* function objects are labeled as <code>func name(params) [parent=f]</code>, where <code>f</code> is the parent frame
x = 1
+
* tuples and lists are drawn as boxes for each element, labeled by its index
def outer():
+
    def inner():
+
        return x
+
    return inner
+
outer()()
+
</syntaxhighlight>
+
in the body of <code>inner</code>, to lookup <code>x</code>, look in the local frame <code>inner</code>. Since it is not there, look in the parent frame <code>outer</code>. Since it is not there, look in the parent frame (the global frame) and find <code>x = 1</code>.
+
  
== Sources ==
+
== Rules ==
* http://inst.eecs.berkeley.edu/~cs61a/sp14/slides/03_6pp.pdf
+
* [http://www.ocf.berkeley.edu/~shidi/cs61a/guerrilla/env.txt Official rules]
 
+
* [http://inst.eecs.berkeley.edu/~cs61a/sp14/pdfs/environment-diagrams.pdf Step-by-step guide]
== Resources ==
+
* [http://inst.eecs.berkeley.edu/~cs61a/sp14/pdfs/environment-diagrams.pdf Official guide]
+
 
* [http://albertwu.org/cs61a/notes/environments Albert's guide]
 
* [http://albertwu.org/cs61a/notes/environments Albert's guide]
 
* [http://markmiyashita.com/cs61a/environment_diagrams/rules_of_environment_diagrams/ Mark's guide]
 
* [http://markmiyashita.com/cs61a/environment_diagrams/rules_of_environment_diagrams/ Mark's guide]
 
* [http://www.michellerubyhwang.com/handouts/sp14/EnvDiagramSp14.pdf Michelle's guide]
 
* [http://www.michellerubyhwang.com/handouts/sp14/EnvDiagramSp14.pdf Michelle's guide]
* [http://inst.eecs.berkeley.edu/~cs61a-tz/guerrilla/env.txt Andrew's guide]
+
 
* [http://pythontutor.com/visualize.html#mode=edit Python Tutor]
+
== Sources ==
 +
* http://inst.eecs.berkeley.edu/~cs61a/sp14/slides/03_6pp.pdf
 +
 
 +
== External links ==
 +
* [http://pythontutor.com/composingprograms.html#mode=edit Python Tutor] (environment diagram drawer)
 +
 
 +
{{Environment}}

Latest revision as of 11:33, 9 July 2014

An environment diagram is a tool to show the state of a program after the execution of a certain number of lines. More precisely, it is a visualization of the frames created by running a program, along with the bindings of each frame.

Structure

Environment diagrams are divided into two columns: on the left side is the stack frame (where all frames are) and on the right side, the heap (where all objects are).

Stack

The stack frame is a group of frames. When a function is called, a new frame is created and placed on top of all the other frames. When that function terminates, the frame is removed.

Every local frame (i.e., not global) should have a frame number, a parent label, and a return value that will be filled out when the function terminates. Then, within the frame, names go on the left hand side, and the associated values go on the right hand side. Values can be primitives or object references (arrows pointing to an object in the heap).

Heap

The heap holds objects. Most commonly, these will be function objects, tuples, and lists.

  • function objects are labeled as func name(params) [parent=f], where f is the parent frame
  • tuples and lists are drawn as boxes for each element, labeled by its index

Rules

Sources

External links