Oregon Curriculum Network
Discovering Math with Python

Chapter 2: FUNCTIONS AT WORK

Lets start off with a Python function, using the keyword def (for "define"). Functions help organize code, primarily by doing fixed unchanging things, step by step, to something changing we give them to work on.

For example, we might have a function called "dress this doll" that dresses any doll we give it. Think of a function as a verb that typically works on an object, creating a result that, typically is another object (what the function returns).

The mathematical idea of a function is not far off. Mathematical functions never produce a different result, given the same inputs or arguments. Different inputs may give the same output, that's fine, but not different outputs given the same inputs. Functions behave as deterministic machines, not subject to "environmental factors" behind the scenes.

That's a standard to aim for with the functions you design. Be sparing with global variables that might be passed as arguments instead, lest you confuse your reader. Global constants (read-only), clearly flagged as such, are less problematic and should be conceived of as additional function inputs.

In the example below, the function named cyclic is what we call a "callable" in Python, meaning you invoke it by putting parentheses after it, with or without arguments. Not only callables are functions. Functions are instances of one type of callable.

When we initialize an instance of a class, we'll call the class. Lets take a look at that now.

Callable objects in general

The built-in types serve as templates for actual lists, dicts, tuples, other data structures. These are callables. Lets list some of those types:

  • bool (True or False)
  • str (string)
  • list (a collection type)
  • tuple (similar to list, but less mutable)
  • dict (not a sequence, called a mapping)
  • range (yes, a type, not a function)
  • zip (yes, also a type, for creating instances of the zip class)

Lets not forget the other numeric types either, such as float, int and Decimal. The bool type is actually a subclass of the integers in Python, the True and False serving as keyword names for 1 and 0 respectively:


In [1]:
issubclass(bool, int)


Out[1]:
True

In [2]:
isinstance(False, int)


Out[2]:
True

Calling types

Calling any type with no arguments logically suggests an empty instance of whatever we're creating, whatever Something, e.g. d = dict() would be "empty dictionary" and the_list = list() should start an empty list.

How about int(); float(); Decimal()? These would produce their respective versions of zero, one would think, and they do.

Lets do some testing, starting with collection types (objects that hold or contain other objects):


In [3]:
the_list = list()
nada_dict = dict(the_list)  # converting
empty_set = set()  # can't use {} as that means empty dict
empty_tuple = tuple()
print(the_list, nada_dict, empty_set, empty_tuple)


[] {} set() ()

print( ) is an example of a built-in Python function. It sends strings to the console, converting objects to strings first, as a part of its job. We fed it not-string type objects, but it didn't complain.

In a Jupyter Notebook, the "console" is the output area immediately beneath the code cell. More typically, print() will output to a terminal window, from inside a running program. We use the input() function to go the other way, from a console to a program. Execution pauses waiting for a user to type something and hit the Enter key. input() always returns strings in Python 3, the version we're using here.

Lets continue calling the built-in types, with no arguments...


In [4]:
import decimal  # needs to be imported
# lets create more "empty stuff" by calling types with no arguments
empty_string = str()
logical = bool()
float_zero = float()
int_zero = int()
d = decimal.Decimal() # Decimal is a class name inside the decimal module

# a triple-quoted string may go on for many lines...
# and a format string -- note the f prefix -- enables 
# substitution of surrounding objects into curly brace 
# placeholders -- new as of 3.6 (or use the format method)
print(f"""
empty_string: {empty_string}
logical:  {logical}
float_zero:  {float_zero}
int_zero: {int_zero}
d: {d}""")


empty_string: 
logical:  False
float_zero:  0.0
int_zero: 0
d: 0

The empty string doesn't show up, because it's empty. Spaces wouldn't show up either, when printed. However an empty string and single space are different.

The former has a length of 0, the latter a length of 1.


In [5]:
print(len(str()), len(" "))


0 1

If we check for equality (==), we find the answer is False.

You may also compare values using >, <, =>, <=, and != (not equal). Not all objects are "ordered" such that these operators would make sense. When we define our own types, we'll have the choice whether to implement these comparators for them.


In [6]:
str() == " "  # empty string equals space? (no way)


Out[6]:
False

What have we been looking at so far?

Built-in callables mainly (including a built-in print function). Callable objects include more than just functions; but also types.

None of the keywords are callables, nor are numbers or strings. "Dog"() or 3() would be a syntax error.

If you wish instances of your own types to behave as callables, you'll have that choice. Python is standing by to equip your instances with all the bells and whistles the built-in types have.

In conclusion, lets see if we can tease out all the built-in types from what's available on boot up into Python. We'll filter out any type having to do with raising errors or exceptions.


In [7]:
def get_types():
    output = []
    for name in dir(__builtins__):
        the_type = eval(name)  # turn string into original object
        if type(the_type) == type:
            if not issubclass(the_type, BaseException):
                output.append(name)
    return output

types = get_types()
types


Out[7]:
['bool',
 'bytearray',
 'bytes',
 'classmethod',
 'complex',
 'dict',
 'enumerate',
 'filter',
 'float',
 'frozenset',
 'int',
 'list',
 'map',
 'memoryview',
 'object',
 'property',
 'range',
 'reversed',
 'set',
 'slice',
 'staticmethod',
 'str',
 'super',
 'tuple',
 'type',
 'zip']

A First Function

Now lets look at a user-defined function, a source code for an object of that type.

The function below expects a single object, a data structure for input. It also returns an object.

The triple quoted docstring at the top of cyclic tells its user what it does, plus the annotations feature lets us write that we expect a dict more explicitly, although the intepreter does not enforce annotations.

If we wanted any type checking at the start of our function, to make sure a dict is really what was passed in, we would need to write that ourselves.

The triple-quoted docstring shows the annotated version of the function head, the line with def in it. In future functions, annotations will often be used.

We've also made abundant use of comments. Comments and docstrings have a different audience. Docstrings print out, nicely formatted, in response to help(), even for an end user without source code. They should only appear right at the top of a function, as a string with no name.

Comments (with a pound sign) are aimed at readers of the actual source code. They can go anywhere. Python has no "multi-line comment" construct. Docstrings should carry the weight of describing the API ("how to use me").


In [8]:
def cyclic(the_dict):
    """
    accepts a permutation as a dict, returns cyclic notation, 
    a compact view of a permutation
    
    could say (annotated version):
    def cyclic(the_dict : dict) -> tuple:
    
    without annoying, or troubling, the Python interpreter (try it!).
    """
    output = []      # we'll make this a tuple before returning
    while the_dict:
        start = tuple(the_dict.keys())[0]
        the_cycle = [start]
        the_next = the_dict.pop(start) # take it out of the_dict
        while the_next != start:       # keep going until we cycle
            the_cycle.append(the_next) # following the bread crumb trail...
            the_next = the_dict.pop(the_next)  # look up what we're paired with
        output.append(tuple(the_cycle)) # we've got a cycle, append to output
    return tuple(output) # giving back a tuple object, job complete

Don't let the above code intimidate you.

This is about the right size for a function, and does just the right amount of work.

Note that it delegates to the methods our high level data structures bring to the table, such as pop and append. We get a lot done in just a few lines.

Lets look at these data structures in action, in isolation, before coming back to this function to see exactly what it's about.

Looking at Data Structures

All list type objects know how to append, as a part of their heritage. Lists also respond to square brackets, or "get item" syntax.


In [9]:
zoo = ["bear", "tiger", "lion"]
zoo.append("scorpion")
print(zoo[0], zoo[3]) # print first and last


bear scorpion

We may also insert into a list, at any point:


In [10]:
zoo.insert(2, "monkey") # after item 2
zoo


Out[10]:
['bear', 'tiger', 'monkey', 'lion', 'scorpion']

To pop, in the case of a dict, is to remove an item by key, while returning the value. Lets look at that:


In [11]:
ages = {"monkey":3, "bear":2.5, "otter":1.5}  # remember me?
ages


Out[11]:
{'bear': 2.5, 'monkey': 3, 'otter': 1.5}

In [12]:
bear_age = ages.pop("bear")  # take a key, return a value
bear_age


Out[12]:
2.5

In [13]:
ages  # the bear item is gone


Out[13]:
{'monkey': 3, 'otter': 1.5}

Or just use the keyword del, for delete, if you don't have a need for the object in future:


In [14]:
del ages['otter']  # delete this element
ages


Out[14]:
{'monkey': 3}

Now lets get back to our function, wherein these data structures, each with a bag of tricks (methods) play a starring role.

In this function cyclic, we're "diasy chaining" through a dict, meaning each key points to a value, which value then becomes the key to a next value, and so on, until we loop back around to the first in the sequence, if we do (we must eventually because the dict is finite).

Sounds like a square dance of some kind.

Our input dict, what gets the ball rolling so to speak, is not just any dict. Animals paired with ages would not work. The docstring mentions expecting a "permutation" which you may think of as a set of objects paired with themselves in a different order. We might call it a "scramble". In the case of animals, a permuation might look like this...


In [15]:
pairings = {"monkey":"bear", "tiger":"scorpion", "scorpion":"monkey", "bear":"tiger"}
print("Keys:", pairings.keys())
print("Values:", pairings.values())


Keys: dict_keys(['monkey', 'tiger', 'scorpion', 'bear'])
Values: dict_values(['bear', 'scorpion', 'monkey', 'tiger'])

Notice the keys and values are the same elements. Think of the values as simply the keys but in a different order. We could say "monkey maps to bear" and "tiger maps to scorpion".

Now lets feed the above dict to the function and see what we get:


In [16]:
result = cyclic(pairings)
result


Out[16]:
(('monkey', 'bear', 'tiger', 'scorpion'),)

The resulting tuple is read left to right and says "monkey maps to bear" and "bear to tiger" and "tiger to scorpion". The last element wraps around to the first i.e. "scorpion maps to monkey". That all corresponds to what we said in the original dict.

Instead of animals, now, lets think in terms of individual letters instead.

If letter 'd' maps to letter 'd' then ('d',) is the cyclic subgroup (an inner tuple); whereas if 'd' maps to 'a', 'a' back to 'd', then ('d' 'a') or ('a' , 'd') says it all. Any permutation may be expressed as a tuple of such tuples.

Pick a letter, any letter (in our set). It maps to something, which maps to something else, and so on, until you come back around. We'll always be able to express a permutation in this form.

Lets run the above function on a permutation mapping all lowercase ASCII letters (US keyboard), as well as space, to themselves.

First, lets create the input dictionary:


In [17]:
from string import ascii_lowercase # a string
from random import shuffle
the_letters = list(ascii_lowercase) + [" "] # lowercase plus space, as a list
shuffled = the_letters.copy() # copy me
shuffle(shuffled)             # works "in place" i.e. None returned
permutation = dict(zip(the_letters, shuffled)) # make pairs, each letter w/ random other
print("ASCII", ascii_lowercase)
print("Coding Key:", permutation)


ASCII abcdefghijklmnopqrstuvwxyz
Coding Key: {'a': 'p', 'b': 'y', 'c': 'j', 'd': 'z', 'e': 'h', 'f': 'l', 'g': 'i', 'h': 'f', 'i': 'o', 'j': 'r', 'k': 'd', 'l': ' ', 'm': 'e', 'n': 'q', 'o': 'n', 'p': 's', 'q': 'x', 'r': 'g', 's': 'b', 't': 'a', 'u': 'c', 'v': 't', 'w': 'w', 'x': 'k', 'y': 'm', 'z': 'u', ' ': 'v'}

ASCII is the precursor to Unicode, a vast lookup table containing a huge number of important symbols, such as world alphabets and ideograms, special symbols (chess pieces, playing cards), emoji.

In some romantic science fiction we might imagine sharing Unicode with distant aliens, as if this were a helpful puzzle piece. When talking with humans though, it really helps to share a database.

We take all 26 letters from lowercase ascii, a canned (pre-stored) string within the string module, part of the Standard Library, plus the space (space bar, ASCII character 32), and turn that into a list of 27 elements.

Feed two such lists, one a clone of the other, but reshuffled, to the zip type, making pairs, in turn feeding all those pairs in one object to dict, a type which knows how to deal with precisely that format.

Lets look at that same creation process with some integers instead:


In [18]:
# feel free to keep re-running this, a different permutation every time!
seq1 = list(range(21))
seq2 = seq1.copy()
shuffle(seq2)
the_zip = tuple(zip(seq1, seq2))  # actually a tuple already
the_zip


Out[18]:
((0, 12),
 (1, 16),
 (2, 5),
 (3, 1),
 (4, 7),
 (5, 2),
 (6, 10),
 (7, 17),
 (8, 0),
 (9, 8),
 (10, 6),
 (11, 13),
 (12, 20),
 (13, 9),
 (14, 3),
 (15, 4),
 (16, 19),
 (17, 15),
 (18, 11),
 (19, 14),
 (20, 18))

Although the above data structure is a tuple of tuples, its not in cyclic notation. Rather, its a step on the way to becoming a dict type object.

Lets feed the above to the native the dict type, an essential job of which is to spawn instances of its own type, given compatible input. A tuple of pairs is a form the dict type knows how to eat, because the meaning is obvious. We want each pair to become an element in our dict.

To that end, in its capacity as a dict-maker, the dict type is a callable, as we have seen, taking in the raw material needed for the constitution of new such objects, new dict objects in this case:


In [19]:
perm_ints = dict(the_zip) # the_zip is by now a tuple of tuples, which dict will digest
perm_ints


Out[19]:
{0: 12,
 1: 16,
 2: 5,
 3: 1,
 4: 7,
 5: 2,
 6: 10,
 7: 17,
 8: 0,
 9: 8,
 10: 6,
 11: 13,
 12: 20,
 13: 9,
 14: 3,
 15: 4,
 16: 19,
 17: 15,
 18: 11,
 19: 14,
 20: 18}

Our function will work equally well on any permutation dict, as we're not depending on the type of our keys and/or values for this recipe to work.

In the one dict, permutation, we map letters to letters, in this other perm_ints, we maps ints to ints.

The cyclic function doesn't care about these details and works the same either way. Python is good at letting us generalize.

That doesn't mean cyclic is immune from crashing. It's expecting a dict wherein every value is also a valid key. Not every dict is like that.


In [20]:
cyclic(permutation)


Out[20]:
(('a', 'p', 's', 'b', 'y', 'm', 'e', 'h', 'f', 'l', ' ', 'v', 't'),
 ('c', 'j', 'r', 'g', 'i', 'o', 'n', 'q', 'x', 'k', 'd', 'z', 'u'),
 ('w',))

In [21]:
cyclic(perm_ints)


Out[21]:
((0, 12, 20, 18, 11, 13, 9, 8),
 (1, 16, 19, 14, 3),
 (2, 5),
 (4, 7, 17, 15),
 (6, 10))

You may be wondering, considering the above pipeline, which went from zip type, to tuple, then to dict, whether a dict might eat a zip type directly. Lets try that...


In [22]:
cipher = dict(zip(seq1, seq2))  # will a dict eat a zip?
cipher


Out[22]:
{0: 12,
 1: 16,
 2: 5,
 3: 1,
 4: 7,
 5: 2,
 6: 10,
 7: 17,
 8: 0,
 9: 8,
 10: 6,
 11: 13,
 12: 20,
 13: 9,
 14: 3,
 15: 4,
 16: 19,
 17: 15,
 18: 11,
 19: 14,
 20: 18}

So yes, that works great.

So why did we call our dict thing a cipher just now? Because a permutation suggests a way of encrypting a message, meaning to make it "hard to crack" where "prying eyes" are concerned.

So-called substitution codes are not that easy to crack if changed frequently and used for only short messages, or so they tell me. If we know the encrypted language, such as English, then a letter frequency analysis may help with the crack.

However lets not get into making any claims about uncrackability, and just take a look of how if two people, call them Alice and Bob, share the same secret key, then message between them might stay encrypted, impeneterable to Eve, at least for awhile.


In [23]:
def encrypt(plain : str, secret_key : dict) -> str:
    """
    turn plaintext into cyphertext using the secret key
    """
    output = ""  # empty string
    for c in plain:
        output = output + secret_key.get(c, c) 
    return output

In [24]:
c = encrypt("able was i ere i saw elba", permutation) # something Napoleon might have said

In [25]:
c


Out[25]:
'able was i ere i saw elba'

Excuse me? That doesn't look scrambled at all? The reason is subtle: feeding permuation to cyclic above rendered it empty. We operated upon "the_dict" and in turning out a corresponding tuple of tuples, consumed the object fed it. The function worked on our only copy, on the original itself.


In [26]:
permutation


Out[26]:
{}

Let's do two things to improve the situation:

  • generate permutations from a function, that takes a set of what to permute
  • make sure the cyclic function doesn't mess with the passed-in original

Let's do first things first:


In [27]:
def make_perm(incoming : set) -> dict:
    seq1 = list(incoming)
    seq2 = seq1.copy()
    shuffle(seq2)
    return dict(zip(seq1, seq2))

In [28]:
make_perm(set(range(10)))


Out[28]:
{0: 3, 1: 7, 2: 5, 3: 2, 4: 1, 5: 8, 6: 6, 7: 9, 8: 0, 9: 4}

In [29]:
make_perm(the_letters) # defined above as lowercase ascii letters plus space


Out[29]:
{' ': 'z',
 'a': ' ',
 'b': 'r',
 'c': 'm',
 'd': 'i',
 'e': 'd',
 'f': 'x',
 'g': 'v',
 'h': 'w',
 'i': 'y',
 'j': 'k',
 'k': 'n',
 'l': 'h',
 'm': 'p',
 'n': 's',
 'o': 'a',
 'p': 'g',
 'q': 'e',
 'r': 'b',
 's': 'o',
 't': 'u',
 'u': 'l',
 'v': 'j',
 'w': 'c',
 'x': 't',
 'y': 'f',
 'z': 'q'}

That's all working great, and now the second change, a new cyclic:


In [30]:
def cyclic(the_perm : dict) -> tuple:
    """
    cyclic notation, a compact view of a permutation
    """
    output = []      # we'll make this a tuple before returning
    
    the_dict = the_perm.copy() # protect the original from exhaustion
    
    while the_dict:
        start = tuple(the_dict.keys())[0]
        the_cycle = [start]
        the_next = the_dict.pop(start) # take it out of the_dict
        while the_next != start:       # keep going until we cycle
            the_cycle.append(the_next) # following the bread crumb trail...
            the_next = the_dict.pop(the_next)  # look up what we're paired with
        output.append(tuple(the_cycle)) # we've got a cycle, append to output
    return tuple(output) # giving back a tuple object, job complete

In [31]:
original = make_perm(the_letters)  # the_letters is a string

In [32]:
cyclic_view = cyclic(original)

In [33]:
cyclic_view


Out[33]:
(('a',
  'n',
  'h',
  'v',
  'y',
  'u',
  'j',
  'z',
  'c',
  'w',
  't',
  's',
  'g',
  'r',
  'o',
  'x',
  'q',
  'k',
  'p',
  'l',
  'd',
  'm',
  'i',
  ' ',
  'f',
  'e'),
 ('b',))

In [34]:
original


Out[34]:
{' ': 'f',
 'a': 'n',
 'b': 'b',
 'c': 'w',
 'd': 'm',
 'e': 'a',
 'f': 'e',
 'g': 'r',
 'h': 'v',
 'i': ' ',
 'j': 'z',
 'k': 'p',
 'l': 'd',
 'm': 'i',
 'n': 'h',
 'o': 'x',
 'p': 'l',
 'q': 'k',
 'r': 'o',
 's': 'g',
 't': 's',
 'u': 'j',
 'v': 'y',
 'w': 't',
 'x': 'q',
 'y': 'u',
 'z': 'c'}

Life is good. As a final touch, we'd like to deciper or decrypt, what was encrypted, using the very same secret_key. All encrypt( ) needs to do is reverse the secret key, giving what's called the inverse permutation, and call encrypt with that.

The original message magically reappears.

Lets make a new permutation for this test, so we don't confuse ourselves.


In [35]:
cipher = make_perm(the_letters)
c = encrypt("hello alice this is bob lets hope eve does not decrypt this", cipher)

In [36]:
def decrypt(cyphertext : str, secret_key : dict) -> str:
    """
    Turn cyphertext into plaintext using ~self
    """
    reverse_P = {v: k for k, v in secret_key.items()}  # invert me!
    output = ""
    for c in cyphertext:
        output = output + reverse_P.get(c, c)
    return output

In [37]:
c


Out[37]:
'cbiijkqiwgbkmcwokwoknjnkibmokcjybkbebkvjbokujmkvbg zymkmcwo'

In [38]:
p = decrypt(c, cipher)

In [39]:
p


Out[39]:
'hello alice this is bob lets hope eve does not decrypt this'

Final thing: I bet you might be wondering about a function that ate a tuple of tuples, some cyclic notation, and gave back the corresponding dictionary object.

This would be the inverse function of cyclic so we could call it inv_cyclic. That's a great cliff-hanger for a next chapter wouldn't you think? Feel free to try writing inv_cyclic.

Here's something to get you started:


In [40]:
def inv_cyclic(cycles : tuple) -> dict:
    output = {} # empty dig
    pass # more code goes here
    return output

Have fun!

Back to Chapter 1: Welcome to Python
Continue to Chapter 3: A First Class
Introduction