Cours LUA: Coroutines in programming languages

1. Introduction

The concept of a coroutine is one of the oldest proposals for a general control abstraction.
It is attributed to Conway [Conway, 1963], who described coroutines as “subroutines who act as the master program”, and implemented this construct to simplify the cooperation between the lexical and syntactical analysers in a COBOL compiler. Marlin’s doctoral thesis [Marlin, 1980], widely acknowledged as a reference for this mechanism, resumes the fundamental characteristics of a coroutine as follows: “the values of data local to a coroutine persist between successive calls”; “the execution of a coroutine is suspended as control leaves it, only to carry on where it left off when control re-enters the coroutine at some later stage”.

2. Lua Coroutines

Lua [Ierusalimschy et al., 1996, Figueiredo et al., 1996] is a lightweight scripting language that supports general procedural programming with data description facilities. It is dynamically typed, lexically scoped, interpreted from bytecodes, and has automatic memory management with garbage collection. Lua was originally designed, and is typically used, as an extension language, embedded in a host program.
Lua was designed, from the beginning, to be easily integrated with software written in C, C++, and other conventional languages. Lua is implemented as a small library of C functions, written in ANSI C, and compiles virtually unmodiﬁed in all currently available plataforms. Along with the Lua interpreter, this library provides a set of functions (the C API) that enables the host program to communicate with the Lua environment. Through this API a host program can, for instance, read and write Lua variables and call Lua functions. Besides allowing Lua code to extend a host application, the API also permits the extension of Lua itself by providing facilities to register C functions to be called by Lua. In this sense, Lua can be regarded as a language framework for building domain-speciﬁc languages.
2.1. Lua Coroutine Facilities
Lua coroutine facilities provide three basic operations: create,resume and yield like in most Lua libraries, these functions are packed in a global table (table).
Function creates a new coroutine, and allocates a separate stack for its execution. It receives as argument a function that represents the main body of the coroutine and returns a coroutine reference. Creating a coroutine does not start its execution; a new coroutine begins in suspended state with its continuation point set to the ﬁrst statement in its main body. Quite often, the argument to is an anonymous function, like this: Function (re)activates a coroutine, and receives as its required ﬁrst argument the coroutine reference. Once resumed, a coroutine starts executing at its continuation point and runs until it suspends or terminates. In either case, control is transfered back to the coroutine’s invocation point.
2.2. An Operational Semantics for Lua Asymmetric Coroutines
In order to clarify the details of Lua asymmetric coroutines, we now develop an operational semantics for this mechanism. This operational semantics is partially based on the semantics for subcontinuations provided in [Hieb et al., 1994]. We start with the same core language, a call-by-value variant of the -calculus extended with assignments. The set of expressions in this core language (e) is in fact a subset of Lua expressions: constants (c), variables (x), function deﬁnitions, function calls, and assignments..
3. Programming With Lua Asymmetric Coroutines
Lua asymmetric coroutines are an expressive construct that permits the implementation of several control paradigms. By implementing this abstraction, Lua is capable of providing convenient features for a wide range of applications, while preserving its distinguishing economy of concepts. This section describes the use of Lua asymmetrical coroutines to implement two useful features: generators and cooperative multitasking.
3.1. Lua Coroutines as Generators
A generator is a control abstraction that produces a sequence of values, returning a new value to its caller for each invocation. A typical use of generators is to implement iterators, a related control abstraction that allows traversing a data structure independently of its internal implementation [Liskov et al., 1977]. Besides the capability of keeping state, the possibility of exchanging data when transfering control makes Lua coroutines a very convenient facility for implementing iterators.
3.2. User-Level Multitasking
The aptness of coroutines as a concurrent construct was perceived by Wirth, who introduced them in Modula-2 [Wirth, 1985] as a basic facility to support the development of concurrent programs. Due mainly to the introduction of the concept of threads, and its adoption in modern mainstream languages, this suitable use of coroutines is, unfortunately,currently disregarded.