Handling Events Naturally with Coroutines - Beginning Lua Programming (2007)

Beginning Lua Programming (2007)

Chapter 9. Handling Events Naturally with Coroutines

When you're implementing an application, you, as a developer, should strive for simplicity and generality. These qualities make a program easy to extend and maintain, and allow it to be reused under a variety of platforms and circumstances. However, real-world requirements often conspire to make these objectives hard to attain. In this chapter, you'll learn how Lua coroutines provide you with an elegant and powerful tool that can dramatically simplify certain kinds of problems. For example, you can use coroutines to manage concurrent tasks, such as updating a progress bar and responding appropriately to user input while transferring a file.

You also use coroutines to provide contextual continuity to functions. A routine that is called intermittently as part of a continuing task may need to go to great lengths to reestablish the context of the task—that is, to remember “where it left off.” For example, a tokenizing routine may be called from various parts of a parsing application yet must, when it is invoked, pick up right where it left off and return the next available token to the caller.

The event-driven nature of interactive programs can lead to logical discontinuities in the application source code. For example, in the interest of clarity, a program should invoke a window and wait until it is closed in much the same way that it calls a file reading routine. This way, directly after the call to show a window, the program can take the suitable course of action depending on the way the window is closed. However, most GUI development models don't allow a window to block like this. Instead, one or more functions are generally registered that are called in response to events such as the closing of a window. This prevents a sequence of statements from including both the display of a window and the action taken after its closure.

A number of attempts to tame problems such as these have evolved over the years with varying levels of success. These will be discussed briefly and compared with the way you can use coroutines to tackle the same problems.

Coroutines and Program Control

A coroutine is a subroutine-like body into and out of which program control can flow repeatedly.

The essence of Lua coroutines is the way they use a familiar notation on top of a program control mechanism that may appear unfamiliar. In this section, you'll see some examples of coroutines and learn of the special considerations you must make to use them effectively.

Coroutines Are Not Functions

In Chapter 3, you learned about Lua functions: how they are defined, how they are invoked, and how they receive values from and return values to the caller. The general picture from that chapter is that a function receives program control when it is called, and relinquishes control when it returns. When a function is called, local variables and bookkeeping information are pushed onto a call stack for safekeeping. When a function returns, these data are popped off of the call stack. This pattern of a call stack growing and shrinking frame by frame provides a very logical basis for structuring a program. It models to some extent the way people manage certain everyday tasks.

In Chapter 6, you learned about an error handling mechanism that allows this stack pattern to be circumvented, namely the protected call. In this case, the call stack grows and shrinks as usual, but when an error occurs, the stack is truncated to the point where the protected call was made without going through the usual function returns.

A coroutine is another mechanism that doesn't quite fit into the familiar nested nature of function calls. Like ordinary functions, coroutines are invoked with argument values and eventually they return values. But coroutines differ from functions in the following ways:

· Unlike a function, a coroutine must be specially prepared, or instantiated, before it can be activated. You use the coroutine.create function to do this.

· When a coroutine is invoked—that is, when it receives program control by means of the coroutine.resume function—it operates on its own call stack, not that of its caller. A coroutine's stack serves the usual purpose of keeping track of function calls and local variables. As with an ordinary program, the use of this stack is transparent to the programmer. Although invoking a coroutine seems like calling a function, it is more similar to starting a new program.

· In the absence of an error, a coroutine relinquishes control to its invoker either by yielding with the coroutine.yield function, or by returning (either with a return statement or by reaching the end of the coroutine body).

· After a coroutine returns control by yielding, it can be resumed—that is, it can be given program control again—with the return of its call to coroutine.yield. A coroutine can yield and be resumed repeatedly.

· After a coroutine terminates, it cannot be activated again. Returning from the main body of a coroutine is much like returning from the main body of a program.

How Coroutines Are Like Programs

Even though coroutines look a lot like functions (in fact, you can use coroutine.wrap to put a function wrapper around a coroutine), it's beneficial to think of a coroutine as a separate program rather than as an enhanced function. All of the operations available to an ordinary Lua program, such as creating variables and calling functions, are available to coroutines. Because each coroutine has its own call stack, its particular statement path, or thread, is independent of the program's initial statement path (the main thread) and that of other coroutines. One and only one thread is active at any given time during the execution of a program. To a limited extent, a useful analogy is a text editor that can have multiple files open simultaneously. You can switch to any of the open files, but only one can be active. Similarly, a Lua program can have many threads, but only one will be currently running.

The distinctive magic of coroutines centers on the coroutine.yield and coroutine.resume functions. The coroutine.yield function may be used as a coroutine's way of saying to its caller, “I don't know how long I'm going to have to sit around waiting for something interesting to happen, so I'll let you take control. When something happens that I should know about, wake me up from my nap and let me know about it.” The coroutine.resume function, in this context, is the currently active thread's way of saying, “Hey, sleepy coroutine, wake up. Here's something of interest for you. When you reach another lull, let me know and I'll take over again.”

Coroutines Transfer Control

There are alternate uses of coroutines. In another context, perhaps the transfer of a number of files, a coroutine might call coroutine.yield as a way of saying, “I'm busy right now, but I know that other threads are in need of some machine cycles too, so I'll relinquish control to let them do some work.” In this scenario, a dispatcher may resume a number of coroutines in turn to overlap multiple tasks.

Even though coroutine.yield and coroutine.resume look like ordinary functions, they map to thread transfer operations that are very unlike ordinary functions. One very nice attribute of coroutines in Lua is that, as a programmer, you can use familiar function notation to switch between threads, exchanging values as you do so.

Wrapping a Coroutine

Coroutine usage can be simplified somewhat with coroutine.wrap. This function is used to instantiate a coroutine just as coroutine.create does, but instead of returning the new coroutine itself, it returns a function that resumes the coroutine. To resume the wrapped coroutine, either initially or after it has yielded, you simply call the returned function with the arguments you want to pass to it. This function is unprotected, so if an error occurs in the coroutine, the function will not return. By using the coroutine.running function, you can identify the wrapped coroutine but, in general, if you need this value, you are better off using unwrapped coroutines.

Coroutines Are Cooperative

Coroutines enable a program to multitask, which means it can interleave the execution of more than one task over a period of time. Just like the main body of a program, the body of a coroutine gives every appearance of being in complete control of the machine. However, the programmer of a coroutine knows that other threads require time to execute too, so a coroutine is programmed to yield control at opportune times, knowing that in due course it will receive control again. In the following exercise, you learn how to write a script that enables coroutines to cooperate.

Try It Out

Learning to Cooperate

The following script demonstrates the use of coroutines to volley control back and forth cooperatively.

1.With your text editor, enter the following script:

local function KnightFnc()

print [[Knight:

The name of the song is called "HADDOCKS’ EYES."

]]

coroutine.yield()

print [[Knight, looking a little vexed:

No, you don't understand, that's what the name is CALLED. The

name really IS "THE AGED AGED MAN."

]]

coroutine.yield()

print [[Knight:

No, you oughtn't, that's quite another thing! The SONG is

called "WAYS AND MEANS," but that's only what it's CALLED, you

know!

]]

coroutine.yield()

print [[Knight:

I was coming to that. The song really IS "A-SITTING ON A GATE",

and the tune's my own invention.

]]

end

local function Alice()

local Knight = coroutine.create(KnightFnc)

coroutine.resume(Knight)

print [[Alice, trying to feel interested:

Oh, that's the name of the song, is it?

]]

coroutine.resume(Knight)

print [[Alice:

Then I ought to have said "That's what the SONG is called"?

]]

coroutine.resume(Knight)

print [[Alice, completely bewildered:

Well, what IS the song, then?

]]

coroutine.resume(Knight)

end

Alice()

2. Save the file as looking_glass.lua.

3. Run the script using the Lua interpreter as follows:

lua looking_glass.lua

Knight:

The name of the song is called "HADDOCKS’ EYES."

Alice, trying to feel interested:

Oh, that's the name of the song, is it?

Knight, looking a little vexed:

No, you don't understand, that's what the name is CALLED. The

name really IS "THE AGED AGED MAN."

Alice:

Then I ought to have said "That's what the SONG is called"?

Knight:

No, you oughtn't, that's quite another thing! The SONG is

called "WAYS AND MEANS," but that's only what it's CALLED, you

know!

Alice, completely bewildered:

Well, what IS the song, then?

Knight:

I was coming to that. The song really IS "A-SITTING ON A GATE",

and the tune's my own invention.

How It Works

In this dialog taken from Lewis Carroll's Through the Looking-Glass (which is, incidentally, a startlingly prescient glimpse into the realm of variable names and indirection), the main thread (Alice) and the coroutine thread (Knight) cooperate by relinquishing control at appropriate points. Note that each thread proceeds as if it is in charge. In fact, this is the case—each thread does have program control until it cooperatively gives it up. This happens when the invoking thread, Alice, calls coroutine.resume and when the coroutine Knight calls coroutine.yield. Each thread executes statements from a sequence that are interleaved with statements from the other thread's sequence.

When a coroutine is resumed, it is specified explicitly in the call to coroutine.resume. However, when a coroutine yields, it always transfers control back to the thread that resumed it.

When a program without coroutines includes a function that produces something and another that consumes it, either the producer function or the consumer function will be in control of the program flow. The other function will be called repeatedly as a service and will run each time from its beginning.

Outside Looking In

An admittedly whimsical way to look at coroutines is to consider an ordinary function call as the placement of program control into an ordinary bottle. When the function terminates, program control flows out of the bottle back to the caller. This analogy emphasizes that no matter how much control a function may have when it is active, it is constrained to eventually run its course and return to its caller. With the inside-out nature of coroutines, the analogy to an ordinary bottle just doesn't “hold water.” Instead, when a coroutine yields, it places program control into a Klein bottle, the four dimensional equivalent of a Möbius strip. If you trace the surface of such a bottle, you find the “inside” and “outside” to be one and the same. A yielding coroutine curiously enters not a constrained enclosure, but the rest of the program. This analogy plays on Lua's way of making the transfer of control between coroutines look like function calls. If you find yourself getting confused about coroutines, focus on coroutine.resume and coroutine.yield as control transfer points rather than as functions.

The following Try It Out puts these ideas on a more familiar footing by using a classic application of coroutines: the interaction of a producer and a consumer. In particular, pay attention to how the producer's call to coroutine.yield looks like an ordinary function call, but in fact, it is the mechanism by which program control is transferred back to the consumer. Unlike a called function, the consumer can run its course without ever transferring control back to the producer.

A Word About Preemptive Multitasking

The cooperative nature of multitasking with coroutines distinguishes it from preemptive multitasking, in which the operating system decides when control is transferred from one thread to another, usually based on time slices. In the discussion that follows, threads in a preemptive multitasking environment will be referred to as system threads. Like a coroutine, a system thread has its own stack, so it is free to manipulate local variables and call and return from functions. However, a system thread must handle the following issues, which a coroutine does not:

· Explicit arrangement with the operating system needs to be made to keep certain blocks of code, such as a series of file writes that need to remain synchronized, from being interrupted.

· Access to globally shared resources must be properly synchronized to avoid corruption by different system threads.

· The termination of a system thread often needs to be specially coordinated with other system threads. Sometimes, a system thread's sole purpose is to coordinate the termination of other threads.

In practice, system threads can be messy. The simplest of programs take on a whole new level of complexity when preemptive multitasking is introduced. This occurs primarily because of the need to avoid race conditions in which statements are executed by system threads in an order that is incorrect and unexpected. Even if system threads don't have control over when they are preempted, they nevertheless need to exhibit a high degree of cooperation with other system threads to manage global resource access and proper termination issues. In light of the long history of coroutines, you may understandably wonder why they have been overshadowed by preemptive solutions in recent decades.

A Lua universe is the reentrant C data structure that all Lua programs are based on. Lua supports preemptive multitasking if special care is taken to protect this structure. To do so, follow these guidelines:

· If multiple system threads interact with a single Lua universe, they must be properly regulated with locks. Lua allows you to provide a locking function and an unlocking function that will be called by Lua when, respectively, it enters and leaves a block of code that must not be interrupted. These functions are not implemented within the Lua core because they in turn call operating system-dependent functions. This solution comes with a performance penalty due to locking overhead.

· More than one Lua universe can be active in a C program that embeds Lua. You can avoid locking requirements by arranging to have each Lua universe accessible to only one system thread. This avoids locking overhead, but requires you to provide a system thread-safe mechanism to transfer data from one Lua universe to another.

Preemptive multitasking is not covered any further in this book.

Try It Out

Sharing Control

Coroutines provide a framework that puts the consumer and producer on similar footing. The script that follows demonstrates this. In it, the producer thread generates simulated input events. The consumer thread simply displays these events in text form.

1. Using your text editor, create a new document with the following contents:

local function LclProducer()

print("Producer: initialize")

-- Simulate event generation

local List = {"mouse", "keyboard", "keyboard", "mouse"}

for J, Val in ipairs(List) do

local Evt = string.format(";Event %d (%s)", J, Val)

print("Producer: " .. Evt)

coroutine.yield(Evt)

end

print(";Producer: finalize")

return ";end",

end

local function LclConsumer()

local GetEvent = coroutine.wrap(LclProducer)

local Evt

print(";Consumer: initialize")

while Evt ~= ";end", do

Evt = GetEvent()

print("Consumer: " .. Evt)

end

print(";Consumer: finalize")

end

LclConsumer()

2. Save the file as producer_consumer.lua.

3. Run the script with the Lua interpreter as follows:

lua producer_consumer.lua

Consumer: initialize

Producer: initialize

Producer: Event 1 (mouse)

Consumer: Event 1 (mouse)

Producer: Event 2 (keyboard)

Consumer: Event 2 (keyboard)

Producer: Event 3 (keyboard)

Consumer: Event 3 (keyboard)

Producer: Event 4 (mouse)

Consumer: Event 4 (mouse)

Producer: finalize

Consumer: end

Consumer: finalize

How It Works

In this script, LclConsumer runs in the main thread, and LclProducer runs in its own coroutine thread. Notice that coroutine.resume is not called explicitly in the code. That's because the GetEvent function (the product of coroutine.wrap) does this implicitly whenever it is called. The aspect of this script that warrants attention is how each thread transfer (GetEvent in LclConsumer and coroutine.yield in LclProducer) occurs within a loop. This is an indication that each thread has control. Local variables that are within the scope in the loop are preserved in the same way as if the resume and yield calls were ordinary function calls. Writing routines from this vantage is generally more natural than writing a routine that runs to completion each time it is called.

Had this example been used in a real event-driven environment, the loop in which LclProducer visits each array element would be replaced by a loop in which successive events are retrieved from the operating system. The fact that these events could arrive sporadically wouldn't change the way the two threads interact.

Coroutines Have Status

You've seen that a coroutine is instantiated with a call to coroutine.create. From that point on, a coroutine always has an operational status. If you're unsure what state a coroutine is in, you can call coroutine.status to find out. That function returns a string with one of the following values:

9-1

Try It Out

Examining the Status of Coroutines

1. Using your text editor, create a new file with the following contents:

local A, B, C

local function Status(Str)

io.write(string.format("%-8s A is %-10s C is %-10s (%s)\n",

Str, coroutine.status(A), coroutine.status(C),

tostring(coroutine.running() or "main thread")))

end

function A()

Status("A")

end

function B()

Status("B")

end

function C()

Status("C 1")

coroutine.resume(A)

Status("C 2")

B()

Status("C 3")

coroutine.yield()

Status("C 4")

end

A = coroutine.create(A)

B = coroutine.wrap(B)

C = coroutine.create(C)

Status("Main 1")

coroutine.resume(C)

Status("Main 2")

coroutine.resume(C)

Status("Main 3")

2. Save this file as status.lua.

3. Run the script using the Lua interpreter as follows:

lua status.lua

Main 1 A is suspended C is suspended (main thread)

C 1 A is suspended C is running (thread 00767F80)

A A is running C is normal (thread 007659C0)

C 2 A is dead C is running (thread 00767F80)

B A is dead C is normal (thread 00766BD0)

C 3 A is dead C is running (thread 00767F80)

Main 2 A is dead C is suspended (main thread)

C 4 A is dead C is running (thread: 00767F80)

Main 3 A is dead C is dead (main thread)

How It Works

In the course of this script, coroutine C assumes each possible status. Coroutine A never assumes the "normal” status, because it never resumes another coroutine.

The return value of coroutine.wrap is a function wrapper around a coroutine, not a coroutine, so it is not a suitable as an argument to coroutine.status. However, when B is called, its wrapped coroutine assumes the "running” status, in this case temporarily taking that status away from C.

Rules of Conduct

The care and feeding of coroutines is quite modest in return for the coolness they lend to a program. Here are some requirements you need to consider when welcoming coroutines into your application.

Work Shoulder-to-Shoulder

A running coroutine must explicitly yield control in a timely manner. A coroutine that runs too long without yielding deprives other threads of the chance to execute. Selecting a point at which to yield is usually straightforward. If the coroutine has produced one or more values to be delivered, it can yield with them as arguments and they will be delivered as return values of the invoking thread's resume call.

If the time needed to produce these values is long, the task can sometimes be partitioned into smaller pieces. In this case, the coroutine enters a loop in which parts of the product are yielded and the resuming thread reassembles them into the complete value. The resuming thread can cycle through a number of coroutines, resuming each in turn.

Trust the Dispatcher

Another time a coroutine should yield is when it begins waiting an indeterminate time for something to occur. The problem is that the only way a yielding coroutine will regain control is if it is resumed, so there must be some way for the resumer to know when the coroutine's wait is complete. This is usually possible with message-based applications in which notifications are pulled from an event queue. In this case, a thread (which is often the main thread) can be dedicated to dispatching these events by executing a loop in which it repeatedly collects an event and resumes the appropriate coroutine.

Expect the Best, Prepare for the Worst

A yielding coroutine generally has no control over which other threads will be activated, or in what order, before it is resumed. Consequently, you must pay some attention to the points at which a coroutine yields to prevent the possibility of unexpected modification of shared resources. For this reason, it pays to limit the scope of variables as much as possible. Avoid yielding in critical sequences of code. For example, if an external file and an internal Lua table need to remain synchronized, don't yield between the points where the update begins and where it ends.

Play on Your Side of the Fence

Coroutines face some restrictions where the C runtime stack is involved. A Lua function that is called from a library that uses Lua's C interface utilizes stacks on both sides of this interface. Coroutines run properly in this circumstance, but they cannot yield across the C interface because this would cause problems with the single stack that is used in the C code. This restriction applies to certain Lua functions such as dofile and pcall. Consider the following script:

local function A()

coroutine.yield()

end

local function B()

print(pcall(A))

end

coroutine.wrap(B)()

This generates the following output:

false attempt to yield across metamethod/C-call boundary

In general, yields across the C interface can usually be worked around. If you encounter a situation where they are required, investigate Coco, a Lua patchset created by Mike Pall and located on the LuaForge site. This extension creates a C stack for each coroutine. It runs on POSIX and Windows (including Windows 98 and above).

Avoid the Deep End

The Lua distribution comes with a file named sieve.lua located in the test subdirectory. This script generates prime numbers up to a specified value (1000 by default) using, with coroutines, an algorithm created by the brilliant Hellenistic mathematician Eratosthenes. As shown by this program, coroutines and recursion appear to be a natural fit. Unfortunately, a known issue with Lua coroutines keeps the C runtime stack (yes, it keeps showing up in these problem areas) from being protected against an overflow condition. Unless you can be sure the C runtime stack is sufficiently large to handle your particular case, you'll want to avoid deeply recursive coroutines. Note also that the problem, because it pertains to the C stack, cannot be bounded with a protected call.

Managing Concurrent Tasks

You can multitask with coroutines to partition long jobs into smaller segments. If your program has some way of detecting user input without blocking (which is not possible with ANSI C and, consequently, standard Lua), then you can use this feature to interrupt or otherwise modify the course of these jobs.

Try It Out

Partitioning Longs Jobs with Coroutines

1. Using your text editor, create a new file with the following script:

local function Multitask()

local function LclWork(Id, Count) -- Simulate some work

for J = 1, Count do

io.write(Id)

io.flush()

local Stop = os.time() + 1

while os.time() < Stop do end

coroutine.yield()

end

end

local function LclContinue() -- Simulate check for user cancellation

return math.random(12) > 1

end

local WorkA = coroutine.create(function () LclWork('A', 2) end)

local WorkB = coroutine.create(function () LclWork('B', 4) end)

math.randomseed(os.time())

local A, B, Ok = true, true, true

while (A or B) and Ok do

Ok = LclContinue()

if Ok and A then

A = coroutine.resume(WorkA)

end

Ok = LclContinue()

if Ok and B then

B = coroutine.resume(WorkB)

end

end

io.write(Ok and " done or " cancel", \n",)

end

Multitask()

2. Save this file as multitask.lua.

3. Run through the following invocations using the Lua interpreter (because user cancellation is simulated randomly, the output you see will likely be different from what is shown here):

lua multitask.lua

ABABBB done

lua multitask.lua

ABA cancel

lua multitask.lua

AB cancel

How It Works

This example uses a number of simulations to demonstrate multitasking. For one, a bunch of cycles are consumed repeatedly calling os.time to simulate a segment of work. In a real application, arrange to have work performed in a coroutine, yielding after a segment of it has been completed. If user input is needed, it must be retrieved in a nonblocking manner. That is, some mechanism like an event queue or keypress buffer must be available for examination without actually waiting for user input.

The example presented here is just one of many variations you can use to repeatedly resume active coroutines. A common construction is to use an array to hold a number of coroutines.

Retaining State

When you programmatically open a file, you obtain a handle that is used for subsequent operations such as writing to the file and closing it. The handle is opaque, which means that information about the file's state (such as its buffers and file position and other internal details) is hidden from view. Within the file routines themselves, the handle is mapped to a data structure that allows the internal state to be accessed during an operation and retained between operations. The discipline of object orientation extends this notion by bundling fields and methods while restricting access to internal data. Each approach has been used extensively and successfully.

A Lua coroutine retains state through its dedicated stack. As you saw in the consumer and producer example, thread transfers don't affect the local variables in these stacks. Because of these stacks, a Lua coroutine can yield from a function other than its main body.

Exercising a Coroutine's Memory

One example of a body of code that must maintain its internal state is a tokenizer, a routine whose job is to deliver on demand the next lexical unit in a sequence. The following Try It Out shows how a coroutine can be used to let a tokenizer keep track of its internal state.

Try It Out

Creating a Tokenizing Coroutine

Expression analysis benefits from the use of a coroutine to collect tokens. Here, you'll see how naturally a coroutine-based tokenizer fits into a larger program.

1. Using your text editor, create a new file with the following contents:

local Token, Pos

local function LclToken(ExpStr)

local Len, PosStart, PosEnd, Allow

Allow = "factor"

Len = string.len(ExpStr)

Pos = 1

while Pos <= Len do

if Allow == "factor" then

PosStart, PosEnd, Token = string.find(ExpStr,

"^%s*([%+%-]?%d+%.?%d*)%s*", Pos)

if PosStart then

Token = tonumber(Token)

else

PosStart, PosEnd, Token = string.find(ExpStr,

" ^%s*(%()%s*", Pos)

if not PosStart then

error("expected number or '(' at position " .. Pos)

end

end

else -- "op"

PosStart, PosEnd, Token = string.find(ExpStr,

"^%s*([%)%+%-%*%/])%s*", Pos)

if not PosStart then

error("expected operator at position " .. Pos)

end

end

Allow = coroutine.yield()

Pos = PosEnd + 1

end

Token = "end"

coroutine.yield()

error("end of expression overreached")

end

local LclExpression

local function LclFactor()

local Val = 0

if type(Token) == "number" then

Val = Token

LclToken("op")

elseif Token == "(" then

LclToken("factor")

Val = LclExpression()

if Token == ")" then

LclToken("op")

else

error("missing ')' at position " .. Pos)

end

else

error(expecting number or ( at position .. Pos)

end

return Val

end

local function LclTerm()

local Val = LclFactor()

while Token == '*' or Token == '/" do

if Token == '*' then

LclToken("factor")

Val = Val * LclFactor()

else

LclToken("factor")

Val = Val / LclFactor()

end

end

return Val

end

function LclExpression()

local Val = LclTerm()

while Token == '+' or Token == '-' do

if Token == '+' then

LclToken("factor")

Val = Val + LclTerm()

else

LclToken("factor")

Val = Val - LclTerm()

end

end

return Val

end

local function LclEvaluate(ExpStr)

LclToken = coroutine.wrap(LclToken)

LclToken(ExpStr)

local Val = LclExpression()

if Token ~= "end", then

error(" unexpected token at position " .. Pos)

end

return Val

end

-- Evaluates the specified expression. If successful, returns result of

-- expression. If the expression can't be evaluated, (nil, error message, error

-- position) is returned.

function Evaluate(ExpStr)

local ErrPos

local Code, Val = pcall(LclEvaluate, ExpStr)

if Code then

Code, Val = Val, nil

else

Code, ErrPos = nil, Pos

end

return Code, Val, ErrPos

end

local ExpStr = arg[1] or "1 + 1"

local Result, ErrStr, ErrPos = Evaluate(ExpStr)

io.write("Expression: ", ExpStr, "\n")

if Result then

io.write("Result: ", Result, "\n")

else

io.write(string.rep(' ', ErrPos + 11), "A\n")

io.write("Error: ", ErrStr, "\n")

end

2. Save the file as expr.lua.

3. Using the Lua interpreter, try the evaluator out with the following expressions:

lua expr.lua "1 + 2 * 3 / 4 * 5 - 6"

Expression: 1 + 2 * 3 / 4 * 5 - 6

Result: 2.5

lua expr.lua "(1 + 2) * 3 / 4 * (5 - 6)"

Expression: (1 + 2) * 3 / 4 * (5 - 6)

Result: -2.25

lua expr.lua "1+1"

Expression: 1+1

Result: 2

lua expr.lua "1++1"

Expression: 1++1

Result: 2

lua expr.lua "1+++1"

Expression: 1+++1

^

Error: expr.lua:75: expr.lua:18: expected number or '(' at position 3

lua expr.lua "1 1"

Expression: 1 1

^

Error: expr.lua:42: expr.lua:25: expected operator at position 3

lua expr.lua "1 % 2"

Expression: 1 % 2

^

Error: expr.lua:42: expr.lua:25: expected operator at position 3

lua expr.lua "1 + 1 )"

Expression: 1 + 1 )

^

Error: expr.lua:90: unexpected token at position 7

lua expr.lua "( 1 + 1

Expression: ( 1 + 1

^

Error: expr.lua:49: missing ')' at position 8

lua expr.lua "(((1)))"

Expression: (((1)))

Result: 1

How It Works

A parser's job is to analyze the elements of an expression. In the four-function expression evaluator presented here, the method of recursive descent is used. The idea is to treat an expression as a series of terms to be added or subtracted. Each term is treated similarly as a series of factors to be multiplied or divided. And each factor is treated as either a number or as a parenthesized expression. In the last case, the same function used to analyze the outermost expression can be called recursively to analyze the subexpression. This can be repeated to any practical depth. With this method, the precedence of the various operators is built into the structure of the parser.

The task of parsing requires the services of a tokenizer, a routine that identifies constituent elements. The tokenizer is called from various parts of the parser, and it must keep track of where it's been so that it can effectively collect the next available token. Additionally, the tokenizer is called in a context-sensitive manner. Based on where in the parser the request for a token is made, either a factor (a number or opening parenthesis) or an operator (+, -, *, /, closing parenthesis, or end of expression) is requested. This prevents a simple loop from simply collecting all tokens and placing them into a table prior to calling the parser. The context-sensitivity is required; for example, to recognize -3 as a number in one case, and as the subtraction operator followed by a number in another.

Here are some aspects of this program that warrant special note:

· The combination of pcall and coroutines doesn't present any problems here. The LclToken coroutine yields repeatedly as it generates tokens, but always to a thread running in the same protected call. Note also that there are no open resources such as files that are left unclosed when an expression error is encountered.

· The coroutine.wrap is used to convert LclToken from a variable that references an ordinary function to one that references a coroutine that can be invoked like a function—without explicitly using coroutine.resume.

· The body of LclToken is not intended to return. If LclToken is called after the “end” token (indicating the end of the expression) has been retrieved, a descriptive error is issued. Had LclToken returned rather than yielded after setting the “end” token, and if the coroutine was resumed, the less helpful “cannot resume dead coroutine” message would have been displayed.

Iterating with Coroutines

In Chapter 4, you learned how to create an iterator, a mechanism that encapsulates many details of looping through sequences. Recall that behind the scenes, Lua calls your iterator function repeatedly to produce successive return values. Coroutines are useful in this context because they don't have to be run from their beginning at each call.

Try It Out

Looping Backwards with a Coroutine Iterator

In this Try It Out, you'll write a new version of the ReverselPairs iterator factory that you first saw in Chapter 4. This one will use a coroutine to achieve the same goal of iterating through an array in reverse order.

1. Create a new file with your text editor and include the follow script:

local function ReverseIPairs(Arr)

local function Iter()

for J = #Arr, 1, -1 do

coroutine.yield(J, Arr[J])

end

end

return coroutine.wrap(Iter)

end

for J, Str in ReverseIPairs({"one","two","three"}) do

print(J, Str)

end

2. Save the file as co_iter.lua.

3. Run the script using the Lua interpreter as follows:

lua co_iter.lua

3 three

2 two

1 one

How It Works

The ReverselPairs iterator factory returns only one value, a function that wraps Iter as a coroutine body. No state information needs to be returned; that's all contained in the coroutine itself. When the loop within Iter is complete, nil is implicitly returned. This signals the end of the genericfor loop to Lua, and the iterator function is not called anymore.

Handling Events Simply

In the era of dumb terminals, timesharing servers and near-total disregard for user-friendliness (veteran programmers refer to this time period as the “good old days”), interactive programs were modal—all user input was channeled into one screen at a time. In the middle of one screen, a user simply couldn't access another. The advantages were all with the software developer. Programming modal screens was easy and promoted clear code that was straightforward to follow because screen functions blocked the way a call to open a file blocked—they simply didn't return until the screen was either approved or cancelled. The ease that programmers had with this model was paid for with user frustration. The limitations of this kind of program became apparent even before the era of GUIs. The solution was for all application input events to be centrally queued and dispatched to appropriate handlers. This new paradigm allowed users to switch between open screens at the cost of complicated program code. Given the constraint of a single application call stack, the event-driven approach led to a programming model that is still pervasive. The following sections describe how this model works, with the focus on the call stack.

The Event Loop

When an event-driven application starts, it typically takes care of some initialization work. The function calls that take place here result in some stack activity.

At some point, usually right after a window or some other event sink is created, the application begins a loop in which events are requested by calling a system function. In the X Window System, this is the XNextEvent function; in Windows, it is the GetMessage function. The height of the stack at this point indicates a “low watermark.” Until the event retrieval loop is terminated prior to the end of the program, the call stack will not shrink below this level. It will, however, be quite active above this level as various functions are called in response to particular events, such as keyboard presses, mouse actions, and win-dow-drawing requests. In a well-functioning application, the processing of any event should take no longer than a tenth of a second or so to avoid choppy window refreshes and sluggish response times.

The event retrieval function is a blocking function—it does not return until an event occurs. It is where an interactive application yields control to the system and generally spends most its time waiting. After handling an event, program control has to return to the event loop to retrieve the next event. This implies that the application call stack has to return to its low watermark, meaning that the various event handlers that are called must find some other means than local variables to retain the state needed for continuity. Because of their integrated approach to methods and fields, object-oriented solutions abound in event-driven systems. For example, a window object can store fields such as list contents and control properties that persist between event notifications.

Modal windows are supported in this single call stack model, but they have the unfortunate consequence of disabling other active windows, preventing users from switching from one window to another within the application. The window created with a blocking call to DialogBox in the Windows API is an example of a modal window. In order to block, such a window is implemented with its own event loop. The modal window's event loop allows other windows to be redrawn when needed, but only the modal window itself is permitted to receive user input. The disabling of other windows prevents problems with variables maintained in the stack between the low watermark and the point at which the modal event loop is implemented. After the modal window is dismissed, you wouldn't want references to other windows that may have been closed or altered. Any practical number of modal windows can be stacked in a chain, but the limitation of only one window that can receive user input makes this technique suitable only for small dialog boxes that can be cancelled without hardship if the user needs to work in another window. In other words, a modal window is easy for the programmer and frustrating for the user.

If you have reached the conclusion that it is the single stack model that prevents switchable, blocking windows, you are correct. What is needed is a window event handler that has its own stack. The solution is to implement this handler as a coroutine. Giving users the flexibility of switching between windows while implementing them, behind the scenes, as blocking windows is a remarkable capability of coroutines. It dramatically simplifies the development of event-driven programs.

Try It Out

Handling Events with Coroutines

In order to focus on the essential structure of a coroutine-based event handling module, the following program uses the command line shell to simulate how windows would behave in a GUI. This not only keeps the code free of a lot of low-level windowing code, it allows you to test it in a pure, platform-independent Lua environment.

1. With your text editor, create a new file with the following contents:

As you can see, there is a lot of code here, so this is a good place to remind you that this and every other script in this book is available from wrox.com.

local Window, Lcl = {}, {}

-- Queue of posted event messages

Lcl.MsgQueue = {}

-- Window structure

-- Parent: window object of parent

-- Id: string identifier, e.g. 1.2.5 for 5th child of 2nd child of window 1

-- Co: coroutine(Fnc) blocks until terminating event

-- ChildCount: number of active children

-- ChildSerial: used for naming new children

-- ChildList: associative array keyed by child window objects

-- Close: assigned the terminating message (usually "cancel" or "ok")

-- User: table passed to handler to hold data that must persist from event to

-- event

-- List of window structures keyed by Id

Lcl.WindowList = {}

-- Currently active window Lcl.WindowActive = nil

-- Value of message to indicate that associated window should be unblocked

Lcl.MsgReturn = "\000"

-- Display all active windows

function Lcl.Show()

local List = {}

for Id, Wnd in pairs(Lcl.WindowList) do

table.insert(List, Wnd.Close and (Id .. " (pending closure)") or Id)

end

table.sort(List)

for J, Id in ipairs(List) do

io.write(Id, "\n")

end

end

-- This function is called when an event occurs that could result in the return

-- of a window call.

function Lcl.Destroy(Wnd)

if Wnd.Close and Wnd.ChildCount == 0 then

io.write("Unblocking window ", Wnd.Id, "\n")

table.insert(Lcl.MsgQueue, {Wnd, Lcl.MsgReturn})

end

end

-- Show some help text

function Lcl.Help()

io.write("Type 'show' to see all active windows\n")

io.write("Type 'window_id msg' to send message to window\n")

io.write("Standard messages are 'create1, 'ok' and 'cancel'\n")

end

-- Simulate the generation of a window event. For a windowed application, this

-- would typically originate with the graphical shell (Windows: GetMessage,

-- XLib: XNextEvent. No coroutine yielding occurs here, so this can be a

-- binding to C.

function Lcl.EventGet()

local Wnd, Msg

if Lcl.MsgQueue[1] then -- If event is queued, retrieve the first one in

local Rec = table.remove(Lcl.MsgQueue, 1)

Wnd, Msg = Rec[1], Rec[2]

else -- Wait for event from user

while not Msg do

io.write("Cmd> ")

local Str = io.read()

Str = string.gsub(Str, "^ *(.-) *$","%1")

Str = string.lower(Str)

if Str == "help" or Str == "?" then

Lcl.Help()

elseif Str == "show" then

Lcl.Show()

else -- Pass message along to designated window

local IdStr, MsgStr = string.match(Str, "(%S+)%s+(%S+)")

if IdStr then

Wnd = Lcl.WindowList[IdStr]

if Wnd then

if not Wnd.Close then

Msg = MsgStr

else

io.write("Window ", IdStr, " is inactive\n")

end

else

io.write("Unknown window: ", IdStr, "\n")

end

else

io.write("Expecting 'help', 'show' or 'window_id msg'\n")

end

end

end

end

return Wnd, Msg

end

-- Main event loop. All coroutines are resumed from this function and yield

-- back to it.

function Lcl.EventLoop()

local Wnd, Msg

local Loop = true

while Loop do

Wnd, Msg = Lcl.EventGet()

if Wnd then

Lcl.WindowActive = Wnd

if Msg == Lcl.MsgReturn then

-- Resume blocking window call

if Wnd.Co then

coroutine.resume(Wnd.Co, Wnd.Close)

else

Loop = false

Msg = Wnd.Close

end

else

-- Non-terminating message was received. Notify window in new coroutine

-- rather than direct function call because a new blocking window may

-- be raised.

local Co = coroutine.create(Wnd.Fnc)

coroutine.resume(Co, Wnd.User, Msg)

end

end

end

return Msg

end

function Window.Show(Fnc)

local Parent = Lcl.WindowActive -- Nil for first window shown

local Msg, Id

if Parent then

Parent.ChildSerial = Parent.ChildSerial + 1

Id = Parent.Id .. "." .. Parent.ChildSerial

else -- First window

Lcl.Help()

Id = "1"

end

local Co = coroutine.running()

local Wnd = {Parent = Parent, Co = Co, Id = Id, Fnc = Fnc,

ChildCount = 0, ChildSerial = 0, ChildList = {}, User = {Id = Id}}

io.write("Creating window ", Wnd.Id, "\n")

table.insert(Lcl.MsgQueue, {Wnd, "create"})

Lcl.WindowList[Id] = Wnd

if Parent then

assert(Co)

Parent.ChildList[Wnd] = true

Parent.ChildCount = Parent.ChildCount + 1

-- We're running in a coroutine; yield back to event loop. The current

-- coroutine will not be resumed until the newly created window and all of

-- its descendent windows have been destroyed. This happens when a

-- Lcl.MsgReturn is posted for this window.

Msg = coroutine.yield()

Parent.ChildCount = Parent.ChildCount - 1

Parent.ChildList[Wnd] = nil

-- Close parent if it's in pending state

Lcl.Destroy(Parent)

else

assert(not Co)

-- We're running in main thread; call event loop and don't return

-- until the loop ends

Msg = Lcl.EventLoop()

end

Lcl.WindowList[Id] = nil

return Msg

end

function Window.Close(Msg)

local Wnd = Lcl.WindowActive

Wnd.Close = Msg or "destroy"

Lcl.Destroy(Wnd)

end

return Window

2. Save this file as window.lua.

3. Create another new file with the following contents:

local Window = require("window")

-- Sample window message handler.

local function SampleWindow(Wnd, Msg)

Wnd.Serial = (Wnd.Serial or 0) + 1

io.write("Window ", Wnd.Id, ", message ", Msg, ", serial ", Wnd.Serial, "\n")

if Msg == "ok" or Msg == "cancel" then

io.write("Calling Window.Close on ", Wnd.Id, "\n")

Window.Close(Msg)

io.write("Called Window.Close on ", Wnd.Id, "\n")

elseif Msg == "button" or Msg == "new" then

local Time = os.date("%X")

io.write("Calling Window.Show from ", Wnd.Id, " (", Time, ")\n")

local Status = Window.Show(SampleWindow)

io.write("Called Window.Show from ", Wnd.Id, ", child returned ", Status, " (", Time, ")\n")

end

end

-- Main statements

io.write("Application: starting\n")

local Status = Window.Show(SampleWindow)

io.write("Window returned ", Status, "\n")

io.write("Application: ending\n")

4. Save this script as window_app.lua.

5. Make sure that ?.lua is specified in your LUA_PATH environment variable. Invoke the window_app.lua script and simulate a simple session in which a main window and a child window are created and, in reverse order, closed:

lua window_app.lua

Application: starting

Type 'show' to see all active windows

Type 'window_id msg' to send message to window

Standard messages are 'create, 'ok' and 'cancel'

Creating window 1

Window 1, message create, serial 1

Cmd> 1 mouse

Window 1, message mouse, serial 2

Cmd> 1 keypress

Window 1, message keypress, serial 3

Cmd> 1 new

Window 1, message new, serial 4

Calling Window.Show from 1 (09:11:25)

Creating window 1.1

Window 1.1, message create, serial 1

Cmd> show

1

1.1

Cmd> 1.1 ok

Window 1.1, message ok, serial 2

Calling Window.Close on 1.1

Unblocking window 1.1

Called Window.Close on 1.1

Called Window.Show from 1, child returned ok (09:11:25)

Cmd> 1 mouse

Window 1, message mouse, serial 5

Cmd> 1 ok

Window 1, message ok, serial 6

Calling Window.Close on 1

Unblocking window 1

Called Window.Close on 1

Window returned ok

Application: ending

6. Invoke the script again. This time, build up a window tree and experiment with closing the windows in something other than reverse order, like this:

lua window_app.lua

Application: starting

Type 'show' to see all active windows

Type 'window_id msg' to send message to window

Standard messages are 'create', 'ok' and 'cancel'

Creating window 1

Window 1, message create, serial 1

Cmd> 1 new

Window 1, message new, serial 2 Calling Window.Show from 1 (09:03:18)

Creating window 1.1

Window 1.1, message create, serial 1

Cmd> 1 new

Window 1, message new, serial 3 Calling Window.Show from 1 (09:03:20)

Creating window 1.2

Window 1.2, message create, serial 1

Cmd> 1 new

Window 1, message new, serial 4

Calling Window.Show from 1 (09:03:21) Creating window 1.3

Window 1.3, message create, serial 1

Cmd> 1.1 new

Window 1.1, message new, serial 2

Calling Window.Show from 1.1 (09:03:28)

Creating window 1.1.1

Window 1.1.1, message create, serial 1

Cmd> 1.2 new

Window 1.2, message new, serial 2

Calling Window.Show from 1.2 (09:03:31)

Creating window 1.2.1

Window 1.2.1, message create, serial 1

Cmd> 1.2 new

Window 1.2, message new, serial 3

Calling Window.Show from 1.2 (09:03:33)

Creating window 1.2.2

Window 1.2.2, message create, serial 1

Cmd> 1.2.2 new

Window 1.2.2, message new, serial 2

Calling Window.Show from 1.2.2 (09:03:39)

Creating window 1.2.2.1

Window 1.2.2.1, message create, serial 1

Cmd> show

1

1.1

1.1.1

1.2

1.2.1

1.2.2

1.2.2.1

1.3

Cmd> 1.2.1 ok

Window 1.2.1, message ok, serial 2

Calling Window.Close on 1.2.1

Unblocking window 1.2.1

Called Window.Close on 1.2.1

Called Window.Show from 1.2, child returned ok (09:03:31)

Cmd> 1.3 ok

Window 1.3, message ok, serial 2

Calling Window.Close on 1.3

Unblocking window 1.3

Called Window.Close on 1.3

Called Window.Show from 1, child returned ok (09:03:21)

Cmd> show

1

1.1

1.1.1

1.2

1.2.2

1.2.2.1

Cmd> 1 ok

Window 1, message ok, serial 5

Calling Window.Close on 1

Called Window.Close on 1

Cmd> 1.1 ok

Window 1.1, message ok, serial 3

Calling Window.Close on 1.1 Called Window.Close on 1.1

Cmd> show

1 (pending closure)

1.1 (pending closure)

1.1.1

1.2

1.2.2

1.2.2.1

Cmd> 1.2.2 ok

Window 1.2.2, message ok, serial 3

Calling Window.Close on 1.2.2

Called Window.Close on 1.2.2

Cmd> show

1 (pending closure)

1.1 (pending closure)

1.1.1

1.2

1.2.2 (pending closure)

1.2.2.1

Cmd> 1.2.2.1 ok

Window 1.2.2.1, message ok, serial 2

Calling Window.Close on 1.2.2.1

Unblocking window 1.2.2.1

Called Window.Close on 1.2.2.1

Unblocking window 1.2.2

Called Window.Show from 1.2.2, child returned ok (09:03:39)

Called Window.Show from 1.2, child returned ok (09:03:33)

Cmd> show

1

(pending closure) 1.1

(pending closure) 1.1.1 1.2

Cmd> 1.2 ok

Window 1.2, message ok, serial 4

Calling Window.Close on 1.2

Unblocking window 1.2

Called Window.Close on 1.2

Called Window.Show from 1, child returned ok (09:03:20)

Cmd> 1.1.1 ok

Window 1.1.1, message ok, serial 2

Calling Window.Close on 1.1.1

Unblocking window 1.1.1

Called Window.Close on 1.1.1

Unblocking window 1.1

Called Window.Show from 1.1, child returned ok (09:03:28)

Unblocking window 1

Called Window.Show from 1, child returned ok (09:03:18)

Window returned ok

Application: ending

How It Works

There are two functions exported from the window module: Window.Show and Window.Close. The first is used to raise a window, and the second is used to signal its closure. In a full-featured window library, some sort of descriptive data structure would typically be passed to Window.Show that describes the controls and parameters of the window to be displayed.

When a window is raised, it is associated with a function that acts as its event handler. For simplicity in this example, the function SampleWindow is used for all windows, but typically you would have one handler for each unique window. Any event message that pertains to a specific window will be sent to its event handler. Here, the only messages that SampleWindow responds to are ok, cancel, button, and new. In an actual event-driven application, messages would be more generic (for example, button click rather than ok), and they would be accompanied by parameters that would provide additional details about the message.

Each event notification in this library is sent to the handler in a new thread. That is, with each new event, the event handler is instantiated as a coroutine and resumed with the event passed as an argument. This is done because the event dispatcher can't know which, if any, event will result in the application blocking in another call to Window.Show. Otherwise, it could call the event handler as a function for each event that it knew would not block because control would return promptly and it could return to the business of dispatching events.

A consequence of this model is that variables local to the handler are not shared between invocations. Here is a clarification of the tradeoff that is made:

· On one hand, a coroutine can repeatedly yield and be resumed. In this case, local variables are retained. The consumer-producer and expression evaluation programs are examples of this. In this type of arrangement, an event processing loop is placed in the scope of local variables that will be retained between yields.

· On the other hand, a coroutine can yield and not be resumed until a particular event occurs—in this case, the window closure event. To allow a window event handler to behave this way, a new coroutine needs to be created using the handler as a body for each event notification. This approach gives you the advantage of blocking window calls, but requires you to find another place to store persistent data. In the window example, you can simply store persistent fields in the Wnd table argument that is passed to the handler for just this purpose.

The important aspect to note as you run this program is that the calls to Window.Show are blocking calls. Even if Window.Close is called on a window, it will not return until all of its descendents are closed. (Incidentally, it would be a simple matter to adjust this behavior so that, when a window is closed, all of its active descendents are forced to close.) The capability to sequentially raise a window and wait for it to terminate frees your application code from much of the complexity often associated with interactive, event-driven programs.

Yielding to Another Coroutine

A coroutine in Lua always yields back to the thread that resumed it. If you would rather specify a coroutine to which to yield, the function Lcl.EventLoop in the previous example gives you the first of two required steps. These steps are:

1. Implement a dispatcher that handles all resuming of coroutines.

2. When yielding, provide the dispatcher with enough information to resume the desired coroutine.

In this framework, it will be the dispatcher thread to which all coroutines yield. If an argument of the yield, say the first, always specifies the desired coroutine to resume, the dispatcher can do this transparently on behalf of the yielding coroutine.

Summary

In this chapter, you learned how to use Lua coroutines in a variety of situations to implement solutions that would otherwise be cumbersome. These include the following:

· Sequentially running multiple jobs

· Retaining state as with an expression tokenizer

· Implementing an iterator

· Blocking on a call that returns an event

You also learned the following coroutine concepts:

· Their capabilities derive from transferring control between threads that each have a dedicated call stack.

· Only one thread is active at a time>

· The transfer of control between threads is done with a natural function-like mechanism, namely coroutine.yield and coroutine.resume, that permits the exchange of values.

In the next chapter, you'll dust off your software development kit and learn how to extend Lua with routines that you'll program in C. In the meantime, try your hand at the following exercises.

Exercises

1.Without actually running it, determine what the following script prints.

local function F()

local J, K = 0, 1

coroutine.yield(J)

coroutine.yield(K)

while true do

J, K = K, J + K

coroutine.yield(K)

end

end

F = coroutine.wrap(F)

for J = 1, 8 do

print(F())

end

2.Write a coroutine-based iterator named JoinPairs that pairs elements from parallel lists. For example, the following loop:

for Name, Number in JoinPairs({"Sally","Mary","James"},{12, 32, 7}) do

print(Name, Number)

end

should generate the following output:

Sally 12

Mary 32

James 7

3.In the producer-consumer example, the consumer thread resumes the producer thread. Modify the example so that this is turned around; that is, execute the producer function in the main thread and run the consumer as a coroutine.