{"id":6209,"date":"2024-07-05T09:45:56","date_gmt":"2024-07-05T07:45:56","guid":{"rendered":"https:\/\/oopm.org\/?page_id=6209"},"modified":"2024-12-15T11:13:34","modified_gmt":"2024-12-15T10:13:34","slug":"14-3-interlocked-algorithms","status":"publish","type":"page","link":"https:\/\/oopm.org\/?page_id=6209","title":{"rendered":"15.3 Using coroutines to describe algorithms"},"content":{"rendered":"
\"image_pdf\"<\/a>\"image_print\"<\/a><\/div>\n

In this section, we show examples of how to use coroutines to describe a certain class of algorithms often referred to as interlocked sequential execution stacks<\/em>. <\/p>\n\n\n\n

A generator<\/em> is a coroutine capable of producing a sequence of values. A new value is produced for each resume of the coroutine. The next value depends on the sequence of previously generated values. We show how to define generators for computing the mathematical functions factorial. The main purpose of the factorial example is to illustrate how coroutines work.<\/p>\n\n\n\n

We assume the reader is familiar with the factorial function, but here is a short description: The factorial of a non-negative integer N, denoted by N!, is the product of all positive integers less than or equal to N. First we show how to define factorial as a simple method:<\/p>\n\n\n\n

   FactorialFunction(N: var<\/strong> integer) -> F: var<\/strong> integer:\n      F := N\n      loop: do\n         if (N > 1) :then\n            N := N - 1\n            F := F * N\n            restart(loop)<\/code><\/pre>\n\n\n\n
As can be seen, FactorialFunction<\/code> computes the product N * (N – 1) * (N – 2) * … * 2 * 1<\/em>.<\/p>\n\n\n\n
Next we show how to define a generator that produce the sequence of factorial, 1!, 2!, 3!, …, N!, …<\/em>. When the coroutine is resumed, it returns the next value in the sequence when it suspends.<\/p>\n\n\n\n
   PlainFactorial: obj<\/strong>\n      getNext -> R: var<\/strong> integer:\n         resume(PlainFactorial)\n<\/mark>         R := F \n      F: var<\/strong> integer\n      N: var<\/strong> integer\n      F := 1\n      cycle\n         PlainFactorial.suspend\n         N := N + 1\n         F := F * N<\/code><\/pre>\n\n\n\n
When PlainFactorial<\/code> is generated it executes statements until the first execution of PlainFactorial.suspend<\/code>. A subsequent  resume of PlainFactorial<\/code> will continue execution after this suspend<\/code>.<\/p>\n\n\n\n
PlainFactorial.getNext <\/code>will return the factorial of 1 which is 1. Subsequent resumes will return the next factorial as shown below:<\/p>\n\n\n\n
UsingPlainFactorial: obj<\/strong>\n   PlainFactorial: obj<\/strong>\n      -\"-\n   V: var<\/strong> integer\n   V := PlainFactorial.getNext<\/span> -- V = 1\n   V := PlainFactorial.getNext<\/span> -- V = 2\n   V := PlainFactorial.getNext<\/span> -- V = 6\n   V := PlainFactorial.getNext<\/span> -- V = 24<\/code><\/pre>\n\n\n\n
The next figure shows a snapshot of the execution of UsingPlainFactorial<\/code> where:<\/p>\n\n\n\n