Composing Programs

From Code Self Study Wiki
Jump to: navigation, search

This page has notes from ComposingPrograms.com.

Python[edit]

  • 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[edit]

See the diagrams in section 1.2.5

Pure vs. Non-Pure Functions[edit]

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[edit]

   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[edit]

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

Code Style[edit]

See PEP 8.

Designing Functions[edit]

Standard stuff:

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

Docstrings[edit]

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[edit]

Example:

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

Testing[edit]

Use assert:

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

Doctests[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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)