{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Silicon Forest Math Series<br/>[Oregon Curriculum Network](http://4dsolutions.net/ocn/)\n",
    "\n",
    "## Generators and Coroutines\n",
    "\n",
    "![Architecture 101](https://c5.staticflickr.com/6/5708/30611276212_f620f47781.jpg)\n",
    "\n",
    "Generator functions relate to generator expressions, objects which delay exectution until pressed into service as iterators, a type with a \\_\\_next\\_\\_ method.  \n",
    "\n",
    "The for loop counts on an iterator for its target and implicitly applies iter(obj) to whatever it gets. Iterators save on memory as they know how to share and underlying iterable.  \n",
    "\n",
    "Some iterators also have the ability to function as objects able to pause and resume operations, without forgetting their internal state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "phi ** -4 == 0.14589803\n",
      "phi ** -3 == 0.23606798\n",
      "phi ** -2 == 0.38196601\n",
      "phi ** -1 == 0.61803399\n",
      "phi **  0 == 1.00000000\n",
      "phi **  1 == 1.61803399\n",
      "phi **  2 == 2.61803399\n",
      "phi **  3 == 4.23606798\n",
      "phi **  4 == 6.85410197\n"
     ]
    }
   ],
   "source": [
    "powers = (lambda x: pow(x, n) for n in range(-4,5))\n",
    "phi = (1 + pow(5,0.5)) * 0.5 # golden proportion\n",
    "for n, f in enumerate(powers, start=-4):  # iterates through lambda expressions\n",
    "    print(\"phi ** {:2} == {:10.8f}\".format(n, f(phi)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Any object expecting to be the target of a for loop, if not already an iterator, needs to either:\n",
    "\n",
    "- dedicate an \\_\\_iter\\_\\_ method to showing what to return when iter() gets applied, or \n",
    "- have a \\_\\_getitem\\_\\_ ready to go, as iter( ) is smart enough to make up an object wherein consecutive integers, starting from 0, go to any \\_\\_getitem\\_\\_ method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "scissors\n",
      "paper\n",
      "rock\n"
     ]
    }
   ],
   "source": [
    "class Any:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.__dict__ = {0:'scissors', 1:'paper', 2:'rock'}\n",
    "    \n",
    "    def __getitem__(self, n):  # enough for iter() to go on\n",
    "        if n == len(self.__dict__):\n",
    "            raise StopIteration  # tells for loop when to stop\n",
    "        return self.__dict__[n]\n",
    "    \n",
    "for thing in Any():\n",
    "    print(thing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The generator function below shows what most Pythonistas consider the base case for the keyword yield: using it much like return, to provide an object to the generator function's caller, in this case a next prime number, going in sequence.\n",
    "\n",
    "The trial-by-division algorithm requires keeping a growing sequence of successive primes, and using them to test new candidates.  After taking care of the only even prime, 2, it makes sense to jump forward through the odds, screening out all the composites."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,\n",
      " 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,\n",
      " 79, 83, 89, 97, 101, 103, 107, 109,\n",
      " 113, 127, 131, 137, 139, 149, 151, 157,\n",
      " 163, 167, 173, 179, 181, 191, 193, 197,\n",
      " 199, 211, 223, 227, 229]\n"
     ]
    }
   ],
   "source": [
    "import pprint\n",
    "\n",
    "def primes():\n",
    "    \"\"\"generate successive prime numbers (trial by division)\"\"\"\n",
    "    candidate = 1\n",
    "    _primes_so_far = [2]     # first prime, only even prime\n",
    "    yield _primes_so_far[0]  # share it!\n",
    "    while True:\n",
    "        candidate += 2    # check odds only from now on\n",
    "        for prev in _primes_so_far:\n",
    "            if prev**2 > candidate:\n",
    "                yield candidate  # new prime!\n",
    "                _primes_so_far.append(candidate)\n",
    "                break\n",
    "            if not divmod(candidate, prev)[1]: # no remainder!\n",
    "                break                          # done looping\n",
    "                \n",
    "p = primes()  # generator function based iterator\n",
    "pp = pprint.PrettyPrinter(width=40, compact=True)\n",
    "pp.pprint([next(p) for _ in range(50)])  # next 30 primes please!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now lets take a look at pretty much the same iterator written a different way:  with an explicit \\_\\_iter\\_\\_ and \\_\\_next\\_\\_."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,\n",
      " 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,\n",
      " 79, 83, 89, 97, 101, 103, 107, 109,\n",
      " 113]\n"
     ]
    }
   ],
   "source": [
    "class Primes:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.candidate = 1\n",
    "        self._primes_so_far = [2]  # first prime, only even prime\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "        \n",
    "    def __next__(self):\n",
    "        while True:\n",
    "            self.candidate += 2    # check odds only from now on\n",
    "            for prev in self._primes_so_far:\n",
    "                if prev**2 > self.candidate:\n",
    "                    self._primes_so_far.append(self.candidate)\n",
    "                    return self._primes_so_far[-2]    \n",
    "                if not divmod(self.candidate, prev)[1]: # no remainder!\n",
    "                    break\n",
    "\n",
    "pp = pprint.PrettyPrinter(width=40, compact=True)\n",
    "p = Primes()  # class based iterator\n",
    "pp.pprint([next(p) for _ in range(30)])  # n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Feeding an open-ended iterator to a for loop runs the risk of a \"forever loop\".  The itertools module is filled with tools designed to rein in the infinite loopers.  Just use islice(obj, start, stop) to keep the for loop finite:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, "
     ]
    }
   ],
   "source": [
    "from itertools import islice\n",
    "p = Primes()\n",
    "for n in islice(p, 0, 20):\n",
    "    print(n, end=\", \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the code below, we see *(yield)* turned around and used not to return objects, but to receive them.  The parentheses are by convention and suggest a \"mouth\" bringing something in from outside.\n",
    "\n",
    "A generator function's .send() method resumes its execution inside its body with an intake of some passed-in object from the caller, the argument to *send*.  In the above example, two callers are nested, the inner one writing a prime to a file, the outer one feeding it next primes for said catalog.\n",
    "\n",
    "The coroutine decorator may seem a bit mysterious at first.  A generator function does not run any of its code upon being instanced.  No yield statement has yet been encountered, so use of .send(obj) would raise an exception were obj any object but None.  \n",
    "\n",
    "The decorator has already fed a .send(None) to the generator in question, equivalent to feeding it to next() a first time.  The decorator applies a first action somewhat like cocking a pistol, putting the generator or coroutine in the firing position, positioned at a first *yield*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "\"\"\"\n",
    "Created on Thu Oct 13 13:48:52 2016\n",
    "\n",
    "@author: Kirby Urner\n",
    "\n",
    "David Beazley:\n",
    "https://youtu.be/Z_OAlIhXziw?t=23m42s\n",
    "\n",
    "Trial by division, but this time the primes coroutine acts \n",
    "more as a filter, passing qualified candidates through to\n",
    "print_me, which writes to a file.\n",
    "\"\"\"\n",
    "import pprint\n",
    "\n",
    "def coroutine(func):\n",
    "    \"\"\"\n",
    "    Advances decorated generator function to the first yield\n",
    "    \"\"\"\n",
    "    def start(*args, **kwargs):\n",
    "        cr = func(*args, **kwargs)\n",
    "        cr.send(None)  # or next(cr) or cr.__next__()\n",
    "        return cr\n",
    "    return start\n",
    "        \n",
    "@coroutine\n",
    "def print_me(file_name):\n",
    "    with open(file_name, 'w') as file_obj:\n",
    "        while True:\n",
    "            to_print = (yield)\n",
    "            file_obj.write(str(to_print)+\"\\n\")\n",
    "    \n",
    "@coroutine\n",
    "def primes(target):\n",
    "    _primes_so_far = [2]\n",
    "    target.send(2)\n",
    "    while True:\n",
    "        candidate = (yield)\n",
    "        for prev in _primes_so_far:\n",
    "            if not divmod(candidate, prev)[1]:\n",
    "                break\n",
    "            if prev**2 > candidate:\n",
    "                _primes_so_far.append(candidate)\n",
    "                target.send(candidate)\n",
    "                break\n",
    "\n",
    "output = print_me(\"primes.txt\")\n",
    "p = primes(output)\n",
    "\n",
    "for x in range(3, 200, 2):  # test odds 3-199\n",
    "    p.send(x)\n",
    "\n",
    "with open(\"primes.txt\", 'r') as file_obj:\n",
    "    print(\", \".join(file_obj.read().split(\"\\n\"))[:-2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the top example, the generator provides a mechanism for advancing to a next odd number for testing, whereas the coroutine version consumes the odds we feed it, passing through those which pass the test for printing, as well as accumulating them internally.\n",
    "\n",
    "![Public Works](https://c3.staticflickr.com/6/5322/30326628890_b723802d42.jpg)\n",
    "\n",
    "### For Further Reading\n",
    "\n",
    "Linked Jupyter Notebooks:\n",
    "\n",
    "- [Public Key Cryptography](http://nbviewer.jupyter.org/github/4dsolutions/Python5/blob/master/Silicon%20Forest%20Math%20Series%20%7C%20RSA.ipynb) -- uses a generator\n",
    "- [Playing With Cyphers](http://nbviewer.jupyter.org/github/4dsolutions/Python5/blob/master/Permutations.ipynb) -- Permutation type\n",
    "- [Abducted!](http://nbviewer.jupyter.org/github.com/4dsolutions/Python5/blob/master/Abducted!.ipynb) -- Python Decorators\n",
    "- [STEM Mathematics](http://nbviewer.jupyter.org/github/4dsolutions/Python5/blob/master/STEM%20Mathematics.ipynb)"
   ]
  }
 ],
 "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.5.1"
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}