Composing Programs

From Code Self Study Wiki
Jump to: navigation, search

This page has notes from ComposingPrograms.com.

Python

  • Use Python 3. Start it with $ python3.

Basic things that are introduced:

from urllib.request import urlopen
shakespeare = urlopen('http://composingprograms.com/shakespeare.txt')
words = set(shakespeare.read().decode().split())
 
# Create a `set` of words that can be reversed to create other words in the doc
{w for w in words if len(w) == 6 and w[::-1] in words}
 
# {'reward', 'repaid', 'redder', 'diaper', 'drawer'}

They introduce some basic math functions:

  • pow(2, 10)
  • max(21, 2, 3, 75)
  • min(21, 2, 3, 75)
  • max(min(1, -2), min(pow(3, 5), -4))

Other math:

from math import sqrt, pi
from operator import add, sub, mul, truediv, floordiv
sqrt(256)
add(14, 28)
sub(100, mul(7, add(8, 4)))
pi * 71 / 223
5 / 4 # 1.25
5 // 4 # =1 it rounds down to an integer
truediv(5, 4) # same as /
floordiv(5, 4) # same as //

Multiple assignment:

x, y, z = 1, 2, 3

Things to the right of the = are evaluated first, so this works for switching values:

x, y = y, x

Expression Trees

See the diagrams in section 1.2.5

Pure vs. Non-Pure Functions

Watch out:

two = print(2)
print(two) # >>> None

(print returns None.)

# Pure
def square(x):
    return mul(x, x)
 
# Not pure
def print_square(x):
    print(square(x)) # Side effects, `print` returns None

Defining Functions

   def <name>(<formal parameters>):
       return <return expression>

Examples:

def square(x):
    return mul(x, x)
 
def sum_squares(x, y):
    return add(square(s), square(y))

Built-in functions don't have formal paramenter names. E.g., mul(...).

Frames and Execution Model

See section 1.3 and the official docs. Basic scope info.

Code Style

See PEP 8.

Designing Functions

Standard stuff:

  • Don't Repeat Yourself (DRY)
  • Functions should have exactly one job
  • Split multiple jobs into multiple functions

Docstrings

def pressure(v, t, n):
    """Computer the pressure in pascals of an ideal gas.
 
    Applies the ideal gas law: http://en.wikipedia.org/wiki/Ideal_gas_law
 
    v -- volume of gas, in cubic meters
    t -- absolute temperature in degrees kelvin
    n -- particles of gas
    """
    k = 1.38e-23 # Boltzmann's constant
    return n * k * t / v

Then you can get help with help(pressure).

Default Argument Values

Example:

def pressure(v, t, n=6.022e23):
    ...

Testing

Use assert:

assert fib(8) == 13, 'The 8th Fibonacci number should be 13'

Doctests

You can put tests in docstrings:

def sum_naturals(n):
    """Return the sum of the first n natural numbers.
 
    >>> sum_naturals(10)
    55
    >>> sum_naturals(100)
    5050
    """
    total, k = 0, 1
    while k <= n:
        total, k = total + k, k + 1
    return total

Then:

from doctest import testmod
testmod()

You'll get back the test results.

To test single function use run_docstring_examples:

from doctest import run_docstring_examples
run_docstring_examples(sum_naturals, globals(), True)

Replace sum_naturals with the name of the function to test.

You can also run doctests like this:

   $ python3 -m doctest <python_source_file>

Higher Order Functions

The book gives examples of similar functions that perform summation. It then shows a basic template:

   def <name>(n):
       total, k = 0, 1
       while k <= n:
           total, k = total + <term>(k), k + 1
       return total

Here's a full example:

def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return total
 
def cube(x):
    return x * x * x
 
def sum_cubes(n):
    return summation(n, cube)
 
result = sum_cubes(3)

Or call summation() directly:

summation(10, square)

You can also use an identity function to sum natural numbers:

def identity(x):
    return x
 
def sum_naturals(n):
    return summation(n, identity)

Another, less-clever way to write it that might clarify things:

def summation(n, fn):
    total = 0
    k = 1
 
    while k <= n:
        total = total + fn(k) # summation
        k = k + 1 # increment
    return total

Recursive Functions

Nice trick:

# Get last digit
12345 % 10 # 5
 
# Get all but last digit
12345 // 10 # 1234

Recursion example:

def sum_digits(n):
    """Return the sum of the digits of positive integer n."""
        if n < 10:
            return n
        else:
            all_but_last, last = n // 10, n % 10
            return sum_digits(all_but_last) + last

Iteration vs. Recursion

Factorial examples in Python:

def fact_iter(n):
    total, k = 1, 1
    while k <= n:
        total, k = total * k, k + 1
    return total
 
def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n-1)

Mutual Recursion

For interesting information about this in Scheme, check out this page.

def is_even(n):
    if n == 0:
        return True
    else:
        return is_odd(n-1)
 
def is_odd(n):
    if n == 0:
        return False
    else:
        return is_even(n-1)
 
result = is_even(4)

Or:

def is_even(n):
    if n == 0:
        return True
    else:
        if (n-1) == 0:
            return False
        else:
            return is_even((n-1)-1)

Here's an example with a game:

def play_alice(n):
    if n == 0:
        print("Bob wins!")
    else:
        play_bob(n-1)
 
def play_bob(n):
    if n == 0:
        print("Alice wins!")
    elif is_even(n):
        play_alice(n-2)
    else:
        play_alice(n-1)

Printing Recursion

def cascade(n):
    if n < 10:
        print(n)
    else:
        print(n)
        cascade(n//10)
        print(n)

Results:

>>> cascade(123456)
123456
12345
1234
123
12
1
12
123
1234
12345
123456

Tree Recursion

This is when a function makes multiple calls to itself. Fibonacci example:

def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    else:
        return fib(n-2) + fib(n-1)

Data Abstraction

Accessing pairs:

pair = [10, 20]
x, y = pair # x=10, y=20

Or:

from operator import getitem
getitem(pair, 0)
getitem(pair, 1)

The rational number example:

from fractions import gcd
 
def add_rationals(x, y):
    nx, dx = numer(x), denom(x)
    ny, dy = numer(y), denom(y)
    return rational(nx * dx + ny * dx, dx * dy)
 
def mul_rationals(x, y):
    return rational(numer(x) * numer(y), denom(x) * denom(y))
 
def print_rational(x):
    print(numer(x), '/', denom(x))
 
def rationals_are_equal(x, y):
    return numer(x) * denom(y) == numer(y) * denom(x)
 
def rational(n, d):
    g = gcd(n, d)
    return [n//g, d//g]
 
def numer(x):
    return x[0]
 
def denom(x):
    return x[1]

You can then do:

half = rational(1, 2)
print_rational(half)
third = rational(1, 3)
print_rational(mul_rationals(half, third))
print_rational(add_rationals(third, third))

Abstraction Barriers

Use higher level functions when possible.

Do this:

# This doesn't assume anything about the way rationals are created
def square_rational(x):
    return mul_rational(x, x)

instead of this:

def square_rational_violating_once(x):
    return rational(numer(x) * numer(x), denom(x) * denom(x))

or this:

def square_rational_violating_twice(x):
    return [x[0] * x[0], x[1] * x[1]]

Or create your own data type with functions instead of using lists to represent the pairs:

def pair(x, y):
    """Return a function that represents a pair."""
    def get(index):
        if index == 0:
            return x
        elif index == 1:
            return y
        return get
 
def select(p, i):
    """Return the element at index i of pair p."""
    return p(i)