{"id":550,"date":"2021-07-01T11:54:11","date_gmt":"2021-07-01T10:54:11","guid":{"rendered":"https:\/\/glennrowe.net\/programmingpages\/?p=550"},"modified":"2021-07-02T10:49:53","modified_gmt":"2021-07-02T09:49:53","slug":"generator-functions-and-the-yield-statement","status":"publish","type":"post","link":"https:\/\/glennrowe.net\/programmingpages\/2021\/07\/01\/generator-functions-and-the-yield-statement\/","title":{"rendered":"Generator functions and the yield statement"},"content":{"rendered":"

A normal function in Python can be terminated with a return<\/code> statement, which may or may not return a value back to the statement that called the function. After executing a return<\/code>, the function’s role in the program is over, at least until the next time the function is called. This means that the state of the function and all its local variables are deleted from memory.<\/p>\n

In some cases, it would be useful to have a function that can return a sequence of intermediate results, with the state of the function being retained between each of these results. Such a function is called a\u00a0generator function<\/em>.<\/p>\n

It’s easiest to understand how a generator function works by looking at a specific example. Suppose we would like to generate the sequence of prime numbers from the smallest such number (2) up to some maximum value. To do this, we need an algorithm for generating all the prime numbers in a given range. The easiest way of doing this is to use a version of the famous algorithm known as the sieve of Eratosthenes<\/a>. The algorithm we’ll use is as follows.<\/p>\n

First, recall that a prime number is an integer that is divisible only by itself and 1. An integer which is not prime is known as\u00a0composite<\/em>, and any composite number must be divisible by at least one prime number. This prime divisor must be less than or equal to the square root of the composite number. One other useful observation is that 2 is the only even prime, so after listing 2 as a prime, we need to examine only odd numbers. With that in mind, here’s the code for generating the prime numbers from 2 up to some value max.<\/p>\n

from math import sqrt, floor\r\n\r\ndef genPrimes(max):\r\n    primes = [2]\r\n    yield 2\r\n\r\n    for n in range(3, max + 1, 2):\r\n        maxCheck = floor(sqrt(n))\r\n        isPrime = True\r\n        for fac in primes[1:]:\r\n            if fac > maxCheck: break\r\n            if n % fac == 0:\r\n                isPrime = False\r\n                break\r\n        if isPrime:\r\n            primes += [n]\r\n            yield n<\/pre>\n
On line 4, we define the list primes<\/code> which will contain the prime numbers. primes<\/code> is initialized to 2, which is the first prime number. We’ll get to the yield<\/code> statement in a minute.<\/p>\n
Next, we need to find all the primes larger than 2 but less than or equal to max<\/code>, so we use the loop over n<\/code> on line 7 to do this. The loop runs from 3 up to max<\/code> (remember that the second argument of range()<\/code> is one more than its final value), in steps of 2, since we’re skipping even numbers.<\/p>\n
The integer maxCheck<\/code> is the largest integer that is less than or equal to the square root of n<\/code>. If n<\/code> is composite, it must have at least one prime factor in the range from 3 up to maxCheck<\/code>. The loop on line 10 runs over the prime numbers in the primes<\/code> list, skipping primes[0]<\/code> which is 2 and cannot be a factor of an odd number. If the number fac<\/code> is larger than maxCheck<\/code>, we break out of the loop. Otherwise, we check whether fac<\/code> divides n<\/code>, and if so, we know that n<\/code> is composite so we can again break out of the loop. If none of the primes divides n<\/code>, then n<\/code> is prime and we add it to the primes<\/code> list on line 16.<\/p>\n
This algorithm (without the yield<\/code> statements) would create the primes<\/code> list containing all the primes from 2 up to max<\/code>, so we could just return this list at the end of the function and then use the list in some other part of the program. However, we have written genPrimes()<\/code> so that it will ‘yield’ the primes one at a time. Let’s see how this works.<\/p>\n
The first time genPrimes()<\/code> is called, it runs up to line 5 where the first yield<\/code> statement is found. At this point, the function sends the value 2 back to the statement that called genPrimes()<\/code>. However, unlike a return<\/code> statement, yield<\/code> does not end the function. Rather, the function’s state, and all its internal variables, are retained.<\/p>\n
After the calling statement does whatever it needs to with the yielded value, it can call the same instance of genPrimes()<\/code> again. This time, execution of genPrimes()<\/code> will pick up where it left off after the previous yield<\/code>, so it will now start running at line 7, with the for<\/code> loop.<\/p>\n
The code in the for<\/code> loop will run and determine the next prime number, which is 3. When execution reaches line 17, n<\/code> will be 3 and another yield<\/code> statement is encountered. This time, the value of n<\/code> (3) is sent back to the calling statement. The process continues until the for<\/code> loop on line 7 finishes.<\/p>\n
If an attempt to call genPrimes()<\/code> is made after all the yield<\/code> statements in the function have been run, a StopIteration<\/code> exception is raised. Depending on how genPrimes()<\/code> is being called, this might terminate the program, or it may be handled cleanly by the calling statement. The important point is that the function itself is not shut down until after the final yield<\/code> has been run.<\/p>\n
To get an idea of how a generator function can be used, we’ll add the following code after the function above (both code blocks can be placed in the same file):<\/p>\n
lastPrime = 2\r\nnumPrimes = 1\r\ngapStats = {}\r\nmax = input('Enter largest number: ')\r\n\r\nfor n in genPrimes(int(max)):\r\n    numPrimes += 1\r\n    gap = n - lastPrime\r\n    if gap in gapStats:\r\n        gapStats[gap] += 1\r\n    else:\r\n        gapStats[gap] = 1\r\n    lastPrime = n\r\nsortGaps = sorted(gapStats.items())\r\nprint(f'Number of primes: {numPrimes}' + '\\n', sortGaps)\r\n<\/pre>\n
This code will use genPrimes()<\/code> to generate a sequence of primes, and then count the number of primes generated, and also count the frequencies of the various gaps between successive primes. The data on the frequencies of gaps are stored in a dictionary called gapStats<\/code>.<\/p>\n
The call to genPrimes()<\/code> is made in the for<\/code> loop on line 6. A for<\/code> loop requires an iterator over which it can perform its loop, and the genPrimes()<\/code> generator function serves as an iterator (Technically a generator is actually a subclass of an iterator, so it’s a type of iterator. Thus all generators are iterators, but the converse is not true.) Each time we run through the loop, the genPrimes()<\/code> function is called, so it generates a sequence of primes that are sent back to the for<\/code> loop. Thus each yield<\/code> generates a value that is placed in the for loop’s variable n<\/code>, which is then used to increment the count numPrimes<\/code>, and to calculate the gap between the current prime and the previous prime, lastPrime<\/code>, and update the counts in the dictionary.<\/p>\n
A for loop contains an implicit handler for the StopIteration<\/code> exception, so once all the yields from genPrimes()<\/code> have run, the loop receives a StopIteration<\/code> and ends. After this, we sort the items in the dictionary on line 14 and print out the results.<\/p>\n
A couple of important points should be noted here. First, the call to genPrimes()<\/code> on line 6 above produces a specific instance of the genPrimes()<\/code> generator. In order to access the yield<\/code> statements within the generator sequentially, we must access the\u00a0same<\/em> instance of the function. The for<\/code> loop does this automatically; the instance of genPrimes()<\/code> in line 6 is retained from one iteration of the loop to the next, so the yields are called sequentially.<\/p>\n
The other important point is that the program must provide a way of dealing with the StopIteration<\/code> exception that is generated after the last yield<\/code> is run. As mentioned above, a for<\/code> loop does this automatically, but if you use a generator somewhere else in your program, you may need to provide an explicit way of catching this exception.<\/p>\n
The next() method<\/h2>\n
To illustrate these points, we’ll consider using genPrimes()<\/code> without a for<\/code> loop. We replace the second block of code above with this:<\/p>\n
gp = genPrimes(10)\r\nwhile True:\r\n    print(next(gp), ' ', end = '')<\/pre>\n
The first line creates a specific instance of genPrimes()<\/code> and stores this in the variable gp<\/code>. The while<\/code> loop iterates over this generator by using the built-in\u00a0 next()<\/code> method. Each time next()<\/code> is called, the generator runs up to its next yield<\/code> statement and then returns the value at that point. Thus this loop generates all the primes between 2 and 10.<\/p>\n
However, if we use next()<\/code> to access successive yields, there is no handler in place to deal with the StopIteration<\/code> exception after all the yields have run. If we run the above code, we get the output:<\/p>\n
2  3  5  7  Traceback (most recent call last):\r\n  File \"D:\\Documents\\Programming\\programmingpages\\Python\\Primes 01\\Primes 01\\Primes_01.py\", line 3, in <module>\r\n    print(next(gp), ' ', end = '')\r\nStopIteration<\/pre>\n
The four primes less than 10 are printed, but then the StopIteration<\/code> causes an error which stops the program. We can add a try<\/code> block to handle the exception<\/a>, as in:<\/p>\n
gp = genPrimes(10)\r\ntry:\r\n    while True:\r\n        print(next(gp), ' ', end = '')\r\nexcept StopIteration:\r\n    print('\\nAll primes found')<\/pre>\n
Now we get the output:<\/p>\n
2  3  5  7\r\nAll primes found<\/pre>\n
Exercise<\/h2>\n
Write a generator function that generates the Fibonacci sequence as an infinite sequence (that is, the function will keep generating values, no matter how many times it is called). The Fibonacci sequence \"f_n\" is defined as<\/p>\n
   <\/span>   <\/span>\"\[<\/p>\n
with \"f_1=f_2=1\". That is, each term is the sum of the previous two terms. [Some definitions of the sequence start with \"f_1=0\" and \"f_2=1\", but for our purposes it’s easier to take the first two terms as 1.]\n
Use this generator to test the theorem that the ratio of two adjacent Fibonacci numbers tends to the Golden Ratio, which is defined as \"\phi=\frac{1+\sqrt{5}}{2}\". That is, test that the following is true:<\/p>\n
   <\/span>   <\/span>\"\[<\/p>\n
As \"\phi\" is an irrational number, you won’t be able to\u00a0prove<\/em> that this limit is true, but you can verify it to a given precision. Your code should ask the user for a tolerance value (see this post<\/a> for a refresher on tolerances in floating point numbers) and then iterate through the generator until this precision is reached. At this point, you should print out the value of \"\frac{f_{n}}{f_{n-1}}\", the value of \"\phi\", and the number of Fibonacci numbers at which the tolerance was reached.<\/p>\nSee answers<\/span>
\n
The program is as follows:<\/p>\n
from math import *\r\n\r\ndef fibon():\r\n    fnm1 = 1\r\n    yield fnm1\r\n    fn = 1\r\n    yield fn\r\n    while True:\r\n        fnp1 = fnm1 + fn\r\n        yield fnp1\r\n        fnm1 = fn\r\n        fn = fnp1\r\n\r\nphi = (1 + sqrt(5))\/2\r\ntol = input('Tolerance: ')\r\ntol = float(tol)\r\ngenFibon = fibon()\r\nf1 = next(genFibon)\r\ncount = 1\r\nfor f2 in genFibon:\r\n    count += 1\r\n    ratio = f2 \/ f1\r\n    if isclose(ratio, phi, rel_tol=tol): break \r\n    f1 = f2\r\n\r\nprint(f'Ratio = {ratio}; Phi = {phi}; Count = {count}')<\/pre>\n
The fibon()<\/code> function on line 3 takes no arguments, as it generates an infinite sequence of values. We specify the first two values as fnm1 = 1<\/code> and fn = 1<\/code>, and include a specific yield<\/code> for each of these values. The infinite loop on line 8 generates the sequence using the formula above by adding together the two previous values to get the next one, with a yield<\/code> after each value is calculated.<\/p>\n
The main program sets up the required values, and then creates an instance of the generator on line 17. As we need two Fibonacci numbers to calculate a ratio, we use next()<\/code> to get the first number on line 18, then enter a loop on line 20. The for<\/code> loop calls successive Fibonacci numbers from the generator, calculates the ratio, and compares this with \"\phi\" using the isclose()<\/code> method we met when discussing floating point numbers<\/a>. If the required tolerance has been met, we break out of the loop and print the results.<\/p>\n
This program is a bit risky, since if the required tolerance is never met, the program will be in an infinite loop, so we should probably include some safeguards to cope with this situation. For example, we could break out of the for<\/code> loop if count<\/code> exceeded some value. However, you’ll find that the result converges surprisingly quickly. The ratio is equal to \"\phi\" within a tolerance of \"10^{-10}\" after only 26 Fibonacci numbers have been generated.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
A normal function in Python can be terminated with a return statement, which may or may not return a value back to the statement that called the function. After executing a return, the function’s role in the program is over, at least until the next time the function is called. This means that the state […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-550","post","type-post","status-publish","format-standard","hentry","category-python","entry"],"_links":{"self":[{"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/posts\/550","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/comments?post=550"}],"version-history":[{"count":6,"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/posts\/550\/revisions"}],"predecessor-version":[{"id":560,"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/posts\/550\/revisions\/560"}],"wp:attachment":[{"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/media?parent=550"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/categories?post=550"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/glennrowe.net\/programmingpages\/wp-json\/wp\/v2\/tags?post=550"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}