week05_contracts.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 05 Functions\n",
    "\n",
    "The discussion of functions in the textbook is pretty thorough but has four significant omissions:\n",
    "\n",
    "* it fails to emphasize that a function defines a contract between itself and the caller\n",
    "* it fails to discuss function input validation\n",
    "* it fails to discuss how to document a function in Python\n",
    "* it's discussion of unit testing is lacking (at best)\n",
    "\n",
    "This series of notebooks is intended to address these omissions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A function defines a contract between itself and the caller\n",
    "\n",
    "Consider the following quote taken from [here](https://www.eiffel.org/doc/solutions/Design_by_Contract_and_Assertions):\n",
    "\n",
    "> When you produce an element of software, how do you know that what you produced is correct?\n",
    ">\n",
    "> This is a difficult question for anyone to answer. Informally speaking, correct software is software \n",
    "> that does what it is supposed to do. That is what makes answering the question so tricky. Before you \n",
    "> can have any idea whether the software is correct, you must be able to express what it is supposed to \n",
    "> do ... and that proves to be quite difficult itself.\n",
    ">\n",
    "> In conventional software engineering, a document called a software specification is written in order \n",
    "> to describe what it is that a piece of software is supposed to do. Writers of software specifications \n",
    "> tend to pursue one of two approaches: the informal or the formal.\n",
    "> \n",
    "> Informal specifications attempt to describe software behavior in the natural languages with which humans\n",
    "> communicate on a daily basis. There are problems with this approach. Natural language is not precise. Informal\n",
    "> specifications are subject to interpretation and affected by the ambiguities, noise, and contradiction inherent\n",
    "> in natural language.\n",
    ">\n",
    "> In order to avoid these problems, proponents of formal methods of specification turn to the most precise \n",
    "> language they know: mathematics. It may be no exaggeration that the study of formal methods has produced more\n",
    "> PhD's in Computer Science than it has well-specified software systems. Still the idea that the precision of \n",
    "> mathematics can be brought to bear on the problem of specifying software is quite appealing. But, problems lurk \n",
    "> here as well. Formal specifications are difficult and time-consuming to construct and verify against themselves,\n",
    "> and most software engineers do not have a working knowledge of the mathematics required to work with formal \n",
    "> specifications. \n",
    "\n",
    "[Design by contract](https://en.wikipedia.org/wiki/Design_by_contract) is a techinique for designing\n",
    "software where the software components have precisely defined contracts. A software component contract\n",
    "is analagous to a business contract where a client and a supplier agree on a contract that defines for example:\n",
    "\n",
    "* the supplier must supply a product (an obligation of the supplier)\n",
    "* the supplier is entitled to receive a fee (a benefit to the supplier)\n",
    "* the client must pay the fee (an obligation of the client)\n",
    "* the client is entitled to receive the product (a benefit to the client)\n",
    "\n",
    "Notice that the obligations of one party are often the benefits to the other party. A contract document protects\n",
    "the client, by specifying what and how much should be done, and it protects the supplier, by stating that the\n",
    "supplier is not obligated to carry out tasks outside of the specified scope.\n",
    "\n",
    "A function can be viewed as defining a contract between itself (the supplier) and a caller (the client):\n",
    "\n",
    "* the function must perform a well-defined computation (the obligations of the function; called the\n",
    "*postconditions* of the function)\n",
    "* the function is entitled to assume certain conditions regarding the arguments supplied by the caller\n",
    "(a benefit to the function; called the *preconditions* of the function)\n",
    "* the caller must ensure that the arguments supplied to the function are acceptable by the function\n",
    "(an obligation of the caller; the caller must satisfy the preconditions of the function)\n",
    "* the caller is entitled to the results of the computation performed by the function (a benefit to the caller;\n",
    "the caller is entitled to assume that the *postconditions* of the function are satisfied)\n",
    "\n",
    "***Preconditions***\n",
    "\n",
    "For functions, a *precondition* is a condition (an expression that evaluates to true or false) that must \n",
    "be true when the function is called in order for the function to successfully perform its computation. A\n",
    "precondition usually involves the parameters of the function. For example, the function call `max(t)`\n",
    "where `t` refers to a list will return the maximum element of `t`; `max` has the precondition that list\n",
    "not be empty which can be expressed as:\n",
    "\n",
    "```python\n",
    "len(t) > 0\n",
    "```\n",
    "\n",
    "For a second example, consider the function `math.factorial(x)` which\n",
    "computes the factorial of $x$ equal to $x! = x(x-1)(x-2)...(3)(2)(1)$ where $x$ is an\n",
    "integer value greater than or equal to $0$. The precondition for `math.factorial` can be expressed as:\n",
    "\n",
    "```python\n",
    "isinstance(x, numbers.Integral) and x >= 0\n",
    "```\n",
    "\n",
    "where `isinstance(x, numbers.Integral)` tests if `x` refers to some kind of integer type.\n",
    "\n",
    "Note that preconditions can be easy to express in plain language but difficult to express formally.\n",
    "For example, how would you formally specify the precondition that the elements of a list be unique\n",
    "(no two elements of the list are equal)?\n",
    "\n",
    "**Exercise 1** The function `max` has another precondition; can you identify the precondition?\n",
    "\n",
    "**Exercise 2** Does the function `math.sqrt(x)` have the precondition `x >= 0`? Try testing the function\n",
    "with negative numeric values to check if your answer is correct.\n",
    "\n",
    "\n",
    "***Preconditions and exceptions***\n",
    "\n",
    "The caller of a function is responsible for ensuring that the arguments supplied to the function satisfy \n",
    "the preconditions of the function, and the function is entitled to assume that the supplied arguments\n",
    "satisfy the preconditions of the function. If the function preconditions are satisfied, then the function\n",
    "is obligated to complete its contract with the caller. If the function preconditions are *not* satisfied, then the\n",
    "function is *not* obligated to complete its contract with the caller. For example, run the following cell\n",
    "to see what happens when `max` is called with an empty list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max([])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the following cell to see what happens when `math.factorial` is called with a non-integer value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "math.factorial(1.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the following cell to see what happens when `math.factorial` is called with a negative integer value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "math.factorial(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The functions in the Python standard libraries typically stop running if they are called with arguments that \n",
    "do not satisfy the preconditions of the function. They do so by *raising an exception*.\n",
    "\n",
    "An exception is an object that represents an error that has occurred when a program is run. You have almost\n",
    "certainly seen an exception that results from using an invalid index in a list (run the following cell, for example):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['hello']\n",
    "t[1]   # oops, t does not have 2 elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, the `ValueError` exceptions that occur in the previous examples all occur when the programs are run.\n",
    "\n",
    "When an exception is raised in a Python function, the function immediately stops running and in many cases,\n",
    "the entire program stops running and an error message is output. This means that exceptions are impossible to\n",
    "simply ignore. It is possible to recover from a raised exception, but this is beyond the scope of the current\n",
    "discussion; see [The Python Tutorial](https://docs.python.org/3/tutorial/errors.html) for details on how to handle\n",
    "raised exceptions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Postconditions***\n",
    "\n",
    "A postcondition is a condition (an expression that evaluates to true or false) that the function is obligated\n",
    "to ensure is true immediately before the function completes running. A postcondition is a formal statement\n",
    "of what the function promises to compute assuming that the preconditions of the function are satisfied.\n",
    "\n",
    "Like preconditions, postconditions are often easier to write in plain language compared to formally specifying\n",
    "them. For example, the postcondition for `max(t)` where `t` is a list can be stated as: Returns the largest item\n",
    "in the list `t`. To formally specify the postcondition, we would need to write something like:\n",
    "\n",
    "* returns the value `val` where\n",
    "    * `val` is an element of `t`, and\n",
    "    * for every element `e` in `t`, `val >= e` is `True`\n",
    "* does not modify `t`\n",
    "\n",
    "Programmers who work on applications that have safety-critical implications or in projects where software errors\n",
    "can have severe consequences will go to the effort to formally specify pre and postconditions (and probably\n",
    "use a language that supports automated testing of pre and postconditions). For our purposes, postconditions \n",
    "written in plain language will suffice.\n",
    "\n",
    "Some additional examples of postconditions include:\n",
    "\n",
    "* `len(s)`\n",
    "    * returns the number of items in the sequence or collection `s` without modifying `s`\n",
    "* `math.ceil(x)`\n",
    "    * returns the ceiling of `x`, the smallest integer greater than or equal to `x`\n",
    "* `math.floor(x)`\n",
    "    * returns the floor of `x`, the largest integer less than or equal to `x`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1** What are the preconditions and postconditions of the textbook function `harmonic` shown in the cell\n",
    "below. You can find the `harmonic` function near the beginning of Chapter 2.1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def harmonic(n):\n",
    "    total = 0.0\n",
    "    for i in range(1, n + 1):\n",
    "        total += 1.0 / i\n",
    "    return total"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2** What are the preconditions and postconditions of the textbook function `isPrime` shown in the cell \n",
    "below. You can find the `isPrime` function in Chapter 2.1 under the section *Multiple return statements*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPrime(n):\n",
    "    if n < 2: \n",
    "        return False\n",
    "    i = 2\n",
    "    while i*i <= n:\n",
    "        if n % i == 0: return False\n",
    "        i += 1\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3** What are the preconditions and postconditions of the textbook function `exchange` shown in the cell \n",
    "below. You can find the `exchange` function in Chapter 2.1 under the section *Side effects with arrays*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def exchange(a, i, j):\n",
    "   temp = a[i]\n",
    "   a[i] = a[j]\n",
    "   a[j] = temp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4** What are the preconditions and postconditions of the textbook function `shuffle` shown in the cell \n",
    "below. You can find the `shuffle` function in Chapter 2.1 under the section *Side effects with arrays*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shuffle(a):\n",
    "    n = len(a)\n",
    "    for i in range(n):\n",
    "        r = random.randrange(i, n)\n",
    "        exchange(a, i, r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 5** What are the preconditions and postconditions of the textbook function `randomarray` shown in the\n",
    "cell below. You can find the `randomarray` function in Chapter 2.1 under the section *Arrays as return values*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def randomarray(n):\n",
    "    a = stdarray.create1D(n)\n",
    "    for i in range(n):\n",
    "        a[i] = random.random()\n",
    "    return a"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}