Mutable Functions & Growth

Mutable Values

Identity vs. Equality in Environment Diagrams

-   Review : For assignment statements, evaluate the right side, then assign to the left

-   Copying : When creating a copy, copy exactly what's "in the box"

Mutating Within Functions

Mutable Functions

Functions with behavior that changes over time

: returns the same value when called with the same input

: return values are different when called with the same input

Example _ withdraw

Argument : amout to withdraw

Return value : remaining balance

second withdrawal of the same amout

where's this balance stored ?

within the parent frame of the function

A function has a body and a prent environment

Persistent Local State Using Environments

: the parent frame contains the balance, the local state of the withdraw function

: all calls to the same function have the same parent

: every call decreases the same balance by ( a possibly different ) amount

Reminder : Logical Assignment

: assignment binds name(s) to value(s) in the first frame of the current environment

Execution rule for assignment statements :

1. evaluate all expressions right of =, from left to right

2. bind the names on the left to the resulting values in the current frame

Non-Local Assignment & Persistent Local State

: declare the name "balance" nonlocal at the top of the body of the functionin which it is re-assigned

: re-bind balance in the first non-local frame in which it was bound previously

Mutable Functions

The Effect of Nonlocal Statement

Effect : Future assignments to that name change its pre-existing binding in the first non-local frame of the current environment in which that name is bound

From the Python 3 language reference :

names listed in nonlocal statement must refer to pre-existing bindings in an enclosing scope

names listed in nonlocal statement must not collide with pre-existing bindings in the local scope ( current frame )

Python Particulars

: Python pre-computes which frame contains each name before executing the body of a function

: Within the body of a function, all instances of a name must refer to the same frame

Mutable Values & Persistent Local State

: mutable values can be changed without a nonlocal statement

Multiple Mutable Functions

Referential Transparency, Lost

: expressions are referentially transparent if substituting an expression with its value does not change the meaning of the program

: mutation operations violate the condition of referential transparency because they do more than just return a value; they change the environment

Summary ( what do I need to know about the mutable functions )

-   nonlocal allows you to modify a binding in a parent frame, instead of just looking it up

-   don't need a nonlocal statement to mutate a value

-   a variable declared nonlocal must :

  exist in a parent frame ( other than the global frame )

  not exist in the current frame

Program Performance

Measuring Growth

-   Different functions run in different amounts of time

: different implementations of the same program can also run in different amounts of time

-   How do we measure this ?

: amout of time taken to run once ?

: average time taken to run ?

: average across a bunch of different computers ?

: number of operations ?

Improving Number of Operations

: Getting better performance usually requires clever thought

-   some tools can be used to speed up programs

-   other times, need to have a different approach or incorporate some insight

How to count calls

: can't always rely on having a program to count calls

-   For an iterative function : step through the program, and identify how many times you need to go through the leep before exiting

-   For a recursive function : draw out an environment diagram / call tree

After you this for a few example inputs, you can find patterns to estimate the number of steps for other inputs