path: root/doc/limbo/limbo.ms

...FP lucidasans
...FP palatino
.FP palatino
." .fp 6 RR R
.nr PI 2n
.de P1
.DS L
.ft CW
.ps -1
.vs -1u
.ta .75i 1.5i 2.25i 3i 3.75i 4.5i 5.25i 6i 6.75i 7.5i
..
.de P2
.ft R
.ps +1
.vs +1u
.DE
..
.de s1
.DS
.br
.ft I
..
.de s2
.br
.DE
.ft R
..
...ds CF "Copyright 2000 Lucent Technologies Inc. Modifications Vita Nuova Limited.
.TL
The Limbo Programming Language
.AU
Dennis M. Ritchie
.br
(Revised 2005 by Vita Nuova)
.SP .5i exactly
.PP
Limbo is a programming language intended for applications
running distributed systems on small computers.
It supports modular programming,
strong type checking at compile- and run-time,
interprocess communication over typed channels,
automatic garbage collection,
and simple abstract data types.
It is designed for safe execution even on
small machines without hardware memory protection.
.PP
In its implementation for the Inferno operating system,
object programs generated by the Limbo compiler run
using an interpreter for a fixed virtual machine.
Inferno and its accompanying virtual machine run either stand-alone
on bare hardware
or as an application under conventional operating systems like
Unix, Windows 2000, Linux, FreeBSD, MacOSX, and Plan 9.
For most architectures, including
Intel x86, ARM, PowerPC, MIPS and Sparc, Limbo object programs
are transformed on-the-fly into instructions for the underlying hardware.
.NH 1
Overview and introduction
.PP
A Limbo application consists of one or more
.I modules ,
each of which supplies an interface declaration and
an implementation part.
A module that uses another module
includes its declaration part.
During
execution, a module dynamically attaches another module by
stating the other module's type identifier and a place from which to load
the object code for its implementation.
.PP
A module declaration specifies the functions and data it will make visible,
its data types, and constants.
Its implementation part defines the functions and data visible at its interface and
any functions associated with its data types;
it may also contain definitions for functions used only internally and
for data local to the module.
.PP
Here is a simple module to illustrate the flavour of the language.
.P1
1	implement Command;

2	include "sys.m";
3	include "draw.m";

4	sys:	Sys;

5	Command: module
	{
6	    init: fn (ctxt: ref Draw->Context, argv: list of string);
7	};
.P2
.P1
8	# The canonical "Hello world" program, enhanced
9	init(ctxt: ref Draw->Context, argv: list of string)
10	{
11		sys = load Sys Sys->PATH;
12		sys->print("hello world\en");
13		for (; argv!=nil; argv = tl argv)
14			sys->print("%s ", hd argv);
15		sys->print("\en");
16	}
.P2
A quick glance at the program reveals that
the syntax of Limbo is influenced by C in its expressions,
statements, and some conventions (for example, look at lines 13-14),
and also by Pascal and its successors (the declarations on lines 4, 6, 9).
When executed in the Inferno environment, the program writes
.CW hello
.CW world
somewhere, then echoes its arguments.
.PP
Let's look at the program line-by-line.
It begins (line 1) by saying that this is the implementation of module
.CW Command .
Line 2 includes a file (found in a way analogous to C's
.CW #include
mechanism) named
.CW sys.m .
This file defines the interface to module
.CW Sys ;
.ds CF
it says, in part,
.P1
Sys: module {
	PATH: con "$Sys";
	. . .
	print: fn (s: string, *): int;
	. . .
};
.P2
This declares
.CW Sys
to be the type name for a module containing among other things a
function named
.CW print ;
the first argument of
.CW print
is a string.
The
.CW *
in the argument list specifies that further arguments, of
unspecified type, may be given.
.PP
Line 3 includes
.CW draw.m ;
only one piece of information, mentioned below,
is used from it.
Line 4 declares the variable
.CW sys
to be of type
.CW Sys ;
its name will be visible throughout the remainder of the file
describing this module.
It will be used later to refer to an instance of the
.CW Sys
module.
This declaration initializes it to
.CW nil ;
it still needs to be set to a useful value.
.PP
Lines 5-7 constitute the declaration of
.CW Command ,
the module being implemented.
It contains only a function named
.CW init ,
with two arguments, a
.CW ref
.CW Draw->Context
and a list of strings,
and it doesn't
return any value.
The
.CW ref
.CW Draw->Context
argument would be used if the program did any
graphics; it is a data type defined in
.CW draw.m
and refers to the display.
Since the program just writes text, it won't be used.
The
.CW init
function isn't special to the Limbo language,
but it is conventional in the environment,
like
.CW main
in C.
.PP
In a module designed to be useful
to other modules in an application, it would be wise to
take the module declaration for
.CW Command
out, put it in a separate file called
.CW command.m
and use
.CW "include
.CW command.m
to allow this module and others to refer to it.
It is called, for example, by the program loader in the Inferno
system to start the execution of applications.
.PP
Line 8 is a comment; everything from the
.CW #
to the end of line is ignored.
.PP
Line 9 begins the definition for the
.CW init
function that was promised in the module's declaration
(line 6).
The argument that is a list of strings is named
.CW argv .
.PP
Line 11 connects the program
being written to the
.CW Sys
module.
The first token after
.CW load
is the target module's name as defined by its interface
(here found in the
.CW include
on line 2)
The next token is the place
where the code for the module can be found; it is a string
that usually names a file.
Conventionally, in the Inferno system,
each module contains a constant declaration for the name
.CW PATH
as a string that names the file where
the object module can be found.
Loading the file is performed dynamically during
execution except for a few modules built
into the execution environment.
(These include
.CW Sys ;
this accounts for the peculiar file name
.CW "$Sys"
as
the value of
.CW PATH .)
.PP
The value of
.CW load
is a reference to the
named module; line 11 assigns it
to the variable
.CW sys
for later use.
The
.CW load
operator dynamically loads the code for the named
module if it is not already present and instantiates
a new instance of it.
.PP
Line 12 starts the work by printing a familiar message,
using the facilities provided by module
.CW Sys
through its handle
.CW sys ;
the notation
.CW sys->print(...)
means to call the
.CW print
function of the module referred to by
.CW sys .
The interface of
.CW Sys
resembles a binding to some of
the mechanisms of Unix and the ISO/ANSI C library.
.PP
The loop at lines 13-14 takes the
.CW "list
.CW of
.CW string
argument to
.CW init
and iterates over it using the
.CW hd
(head) and
.CW tl
(tail) operators.
When executed, this module combines the
traditional `Hello world' and
.CW echo .
.NH 1
Lexical conventions
.PP
There are several kinds of tokens:
keywords, identifiers, constants, strings, expression operators,
and other separators.
White space (blanks, tabs, new-lines) is ignored except that
it serves to separate tokens; sometimes it is required
to separate tokens.
If the input has been parsed into tokens up to a particular
character, the next token is taken to include the longest
string of characters that could constitute a token.
.PP
The native character set of Limbo is Unicode,
which is identical with the first 16-bit plane of the ISO 10646 standard.
Any Unicode character may be used in comments, or in strings
and character constants.
The implementation assumes that source files use the UTF-8 representation,
in which 16-bit Unicode characters are represented as sequences
of one, two, or three bytes.
.NH 2
Comments
.PP
Comments begin with the
.CW #
character and extend to the end of the line.
Comments are ignored.
.NH 2
Identifiers
.PP
An identifier is a sequence of letters and digits
of which the first is a letter.
Letters are the Unicode characters
.CW a
through
.CW z
and
.CW A
through
.CW Z ,
together with the underscore character, and
all Unicode characters with encoded values greater than 160
(A0 hexadecimal, the beginning of the range corresponding to Latin-1).
.PP
Only the first 256 characters in an identifier
are significant.
.NH 2
Keywords
.PP
The following identifiers are reserved for use as keywords,
and may not be used otherwise:
.P1
.ta 1i 2i 3i 4i 5i
	adt	alt	array	big
	break	byte	case	chan
	con	continue	cyclic	do
	else	exit	fn	for
	hd	if	implement	import
	include	int	len	list
	load	module	nil	of
	or	pick	real	ref
	return	self	spawn	string
	tagof	tl	to	type
	while
.P2
The word
.CW union
is not currently used by the language.
.NH 2
Constants
.PP
There are several kinds of constants for denoting values of the
basic types.
.PP
.NH 3
Integer constants
.PP
Integer constants have type
.CW int
or
.CW big .
They can be represented in several ways.
.PP
Decimal integer constants consist of a sequence of decimal
digits.
A constant with an explicit radix
consists of a decimal radix followed by
.CW R
or
.CW r
followed by the digits of the number.
The radix is between 2 and 36 inclusive;
digits above 10 in the number
are expressed using letters
.CW A
to
.CW Z
or
.CW a
to
.CW z .
For example,
.CW 16r20
has value 32.
.PP
The type of a decimal or explicit-radix number is
.CW big
if its value exceeds
.CW 2\u31\d\(mi1 ,
otherwise it is
.CW int .
.PP
Character constants consist of a single Unicode
character enclosed within single-quote characters
.CW ' .
Inside the quotes the following escape sequences represent
special characters:
.DS
\f(CW\e\e\fR		backslash
\f(CW\e'\fR		single quote
\f(CW\e"\fR		double quote
\f(CW\ea\fR		bell (BEL)
\f(CW\eb\fR		backspace (BS)
\f(CW\et\fR		horizontal tabulation (HT)
\f(CW\en\fR		line feed (LF)
\f(CW\ev\fR		vertical tabulation (VT)
\f(CW\ef\fR		form feed (FF)
\f(CW\er\fR		carriage return (CR)
\f(CW\eu\fIdddd	\fRUnicode character named by 4 hexadecimal digits
\f(CW\e0\fR		NUL
.DE
Character constants have type
.CW int .
.NH 3
Real constants
.PP
Real constants consist of a sequence of decimal digits
containing one period
.CW .
and optionally followed by
.CW e
or
.CW E
and then by a possibly signed integer.
If there is an explicit exponent, the period is
not required.
Real constants have type
.CW real .
.NH 3
Strings
.PP
String constants are sequences of Unicode characters contained in double
quotes.
They cannot extend across source lines.
The same escape sequences listed above for character
constants are usable within string constants.
Strings have type
.CW string .
.NH 3
The nil constant
.PP
The constant
.CW nil
denotes a reference to nothing.
It may be used where an object of a reference
type is expected;
otherwise uninitialized values of reference type
start off with this value, it can be assigned to
reference objects, and reference types can be
tested for equality with it.
(The keyword has other uses as well.)
.NH 2
Operators and other separators
.PP
The operators are
.P1
.ta .5i 1i 1.5i 2i 2.5i 3i 3.5i 4i 4.5i 5i 5.5i 6.0i 6.5i
	+	-	*	/	%	&	|	^
	==	<	>	<=	>=	!=	<<	>>
	&&	||	<-	::
	=	+=	-=	*=	/=	%=	&=	|=	^=	<<=	>>=
	:=
	~	++	--	!	**
.P2
The other separators are
.P1
.ta .5i 1i 1.5i 2i 2.5i 3i 3.5i 4i 4.5i 5i 5.5i
	:	;	(	)	{	}	[	]
	,	.	->	=>
.P2
.NH 1
Syntax notation
.PP
In this manual, Limbo syntax is described by a modified BNF
in which syntactic categories are named in an
.I italic
font, and literals in
.CW typewriter
font.
Alternative productions are listed on separate lines, and
an optional symbol is indicated with
the subscript ``opt.''
.NH 1
Types and objects
.PP
Limbo has three kinds of objects.
.I Data
objects exist in the storage associated with
a module; they can be manipulated by arithmetic operations,
assignment, selection of component entities, and other concrete
operations.
Each data object has a type that determines what can be stored
in it and what operations are applicable.
.PP
The second kind of object is the
.I function .
Functions are characterized by the types of the arguments they
accept and the values they return, and are associated with
the modules in which they are defined.
Their names can be made visible in their module's declaration,
or they can be encapsulated within the
.CW adt
(abstract data types) of their modules,
or they can exist privately within their module.
.PP
Finally, Limbo programs are organized into
.I modules :
a named collection of constants, abstract data types,
data, and functions made available by that module.
A module declaration displays the
members visible to other modules;
the module's implementation
defines both the publicly visible members and its
private parts, including the data objects it uses.
A module that wishes to use
the facilities of another includes its declaration in order to
understand what it exports, but
before using them it explicitly loads the new module.
.NH 2
Types
.PP
Limbo has several basic types, some built-in higher abstractions,
and other ways of composing new types.
In declarations and some other places, constructions naming
a type are used.
The syntax is:
.s1
type:
	data-type
	function-type
.s2
Functions will be discussed in §7 below.
First, data types will be explored.
.NH 2
Data types
.PP
The syntax of data types is
.s1
data-type:
	CbyteI
	CintI
	CbigI
	CrealI
	CstringI
	tuple-type
	Carray of Idata-type
	Clist of Idata-type
	Cchan of Idata-type
	adt-type
	Cref Iadt-type
	Cref Ifunction-type
	module-type
	module-qualified-type
	type-name

data-type-list:
	data-type
	data-type-list C,I data-type
.s2
Objects of most data types have
.I value
semantics; when they
are assigned or passed to functions, the destination receives a copy of the
object.
Subsequent changes to the assigned object itself have no effect on
the original object.
The value types are
.CW byte ,
.CW int ,
.CW big ,
.CW real ,
.CW string ,
the
.CW tuple
types, and
abstract data types or
.CW adt .
The rest have
.I reference
semantics.
When they are assigned, the quantity actually assigned
is a reference to (a pointer to) an underlying object
that is not copied; thus changes or operations on
the assigned value affect the original object.
Reference types include lists, arrays, channels, modules,
.CW ref
.CW adt ,
and
.CW ref
.CW fn
types.
.NH 3
Basic types
.PP
The five basic data types are denoted by
.CW byte ,
.CW int ,
.CW big ,
.CW real ,
and
.CW string .
.PP
Bytes are unsigned 8-bit quantities.
.PP
Integers
.CW int ) (
are 32-bit signed quantities represented in two's complement
notation.
Large integers
.CW big  ) (
are 64-bit signed quantities represented in two's complement notation.
.PP
Real numbers
.CW real ) (
are 64-bit quantities represented in the
IEEE long floating notation.
.PP
The
.CW byte ,
.CW int ,
.CW big ,
and
.CW real
types are collectively called arithmetic types.
.PP
Strings are rows of Unicode characters.
They may be concatenated and extended character-by-character.
When a string is indexed with a single subscript, it yields an integer
with the Unicode encoding of the character;
when it is indexed by a range, it yields another string.
.NH 3
Tuple type
.PP
The
.I tuple
type, denoted
.s1
tuple-type:
	C( Idata-type-listC )I
.s2
is a type consisting of an ordered collection of two or more objects,
each having its own data type.
For each tuple type, the types of the members are
fixed, but need not be identical;
for example, a function might return a tuple containing
an integer and a string.
Each tuple type is characterized solely by the
the order and identity of the types it contains.
Objects of tuple type may be assigned to a list of identifiers (to pick out the
components), and a parenthesized, comma-separated list of expressions
denotes a tuple.
.NH 3
Array types
.PP
The
.I array
type describes a dynamically-sized row of objects, all of the same
type; it is indexed starting from 0.
An array type is denoted by
.s1
	Carray of Idata-type
.s2
The size of an array is not part of its type; instead
it is part of the value.
The
.I data-type
may itself be an array, to achieve a multidimensional array.
.NH 3
List types
.PP
A
.I list
is a sequence of like-typed objects; its denotation is
.s1
	Clist of Idata-type
.s2
A list is a stack-like object, optimized for
a few operations: get the head (the first object),
get the tail (the rest of the list), place an object at the beginning.
.NH 3
Channel types
.PP
A
.I channel ,
whose type is written
.s1
	Cchan of Idata-type
.s2
is a communication mechanism capable of sending and receiving objects of the
specified type to another agent in the system.
Channels may be used to communicate between local processes;
using library procedures, they may be connected
to named destinations.
In either case
.I send
and
.I receive
operations may be directed to them.
For example,
.P1
	chan of (int, string)
.P2
is the type of a channel that transmits tuples consisting of
an integer and an string.
Once an instance of such a channel (say
.CW c )
has been declared and initialized,
the statement
.P1
	c <-= (123, "Hello");
.P2
sends such a tuple across it.
.NH 3
Abstract data types
.PP
An abstract data type or
.I adt
is an object that can contain data objects of several
different types and declare
functions that operate on them.
The syntax for declaring an
.CW adt
is given later.
Once an
.CW adt
has been declared, the identifier associated with it
becomes a data-type name.
.s1
adt-type:
	identifier
	module-qualified-type
.s2
.PP
There is also a
.CW ref
.CW adt
type representing a reference (pointer) to an
.CW adt .
It is denoted
.s1
	Cref Iadt-type
.s2
where the identifier is the name of an
.CW adt
type.
.NH 3
Module types
.PP
A module type name is an identifier:
.s1
module-type:
	identifier
.s2
The identifier is declared as a module identifier by a
.I module-declaration ,
as described in §6.5 below.
An object of module type serves as a handle for the
module, and is used to access its functions.
.NH 3
Module-qualified type
.PP
When an
.CW adt
is declared within a module declaration, the type name of that
.CW adt
is not generally visible to the rest of the program unless a specific
.CW import
request is given (see §6.6, §10 below).
Without such a request, when
.CW adt
objects implemented by a module are declared by a client
of that module, the
.CW adt
type name is qualified:
.s1
module-qualified-type:
	identifier C->I identifier
.s2
Here the first identifier is either the name of a module
or a variable of the module type;
the second is the name of a type
mentioned in the module declaration.
.NH 3
Function reference types
.PP
A function reference type represents a reference to a function of a given type.
It is written as
.s1
	Cref Ifunction-type
.s2
Function types are discussed in §4.3 below.
.NH 3
Named types
.PP
Finally, data types may be named, using a
.CW type
declaration; this is discussed in §6.4 below.
.s1
type-name:
	identifier
.s2
.NH 2
Function types
.PP
A function type characterizes the arguments and return value of
a function.  The syntax is
.s1
function-type:
	Cfn Ifunction-arg-ret

function-arg-ret:
	C( Iformal-arg-listOC ) IraisesO
	C( Iformal-arg-listOC ) : Idata-type raisesO

formal-arg-list:
	formal-arg
	formal-arg-listC , Iformal-arg

formal-arg:
	nil-or-ID-listC : Itype
	nil-or-IDC : self refO Iidentifier
	nil-or-IDC : self Iidentifier
	C*I

nil-or-ID-list:
	nil-or-ID
	nil-or-ID-list C, Inil-or-ID

nil-or-ID:
	identifier
	CnilI

raises:
	Craises ( Inil-or-ID-listC )I
	CraisesI nil-or-ID

.s2
That is, the denotation of a function type has the keyword
.CW fn
followed by a comma-separated list of its arguments
enclosed in parentheses,
and perhaps followed by the type the function returns.
Absence of a return value means that the function returns no
value: it is a procedure.
The names and types of arguments are specified.
However, the name of an argument may be replaced by
.CW nil ;
in this case it is nameless.
For example,
.P1
	fn (nil: int, nil: int): int
	fn (radius: int, angle: int): int
	fn (radius, angle: int): int
.P2
all denote exactly the same type,
namely a function of two integers that returns an integer.
As another example,
.P1
	fn (nil: string)
.P2
is the type of a function that takes a string argument
and returns no value.
.PP
The
.CW self
keyword has a specialized use within
.CW adt
declarations.
It may be used only for the first argument
of a function declared within an
.CW adt ;
its meaning is discussed in §6.3 below.
.PP
The star character
.CW *
may be given as the last argument in a function type.
It declares that
the function is variadic; during a call, actual arguments at its
position and following are passed in a manner
unspecified by the language.
For example, the type of the
.CW print
function of the
.CW Sys
module is
.P1
	fn (s: string, *): int
.P2
This means that the first argument of
.CW print
is a string and that other arguments may be given when the function
is called.
The Limbo language itself has no way of accessing these arguments;
the notation is an artifice for describing facilities
built into the runtime system, such as the
.CW Sys
module.
.PP
The type of a function includes user-defined exceptions that it raises,
which must be listed in a corresponding
.CW raises
clause.
.NH 1
Limbo programs
.PP
Limbo source programs that implement modules are stored in files,
conventionally named with the suffix
.CW .b .
Each such file begins with a single
.CW implement
directive naming the type of the module being implemented,
followed by a sequence of declarations.
Other files, conventionally named with the suffix
.CW .m ,
contain declarations for things obtainable from other modules.
These files are incorporated by an
.CW include
declaration in the implementation modules that need them.
At the top level, a program consists of a sequence
of declarations.
The syntax is
.s1
program:
	Cimplement Iidentifier-listC ; Itop-declaration-sequence

top-declaration-sequence:
	top-declaration
	top-declaration-sequence top-declaration

top-declaration:
	declaration
	identifier-listC := IexpressionC ;I
	identifier-listC = IexpressionC ;I
	C( Iidentifier-listC ) := IexpressionC ;I
	module-declaration
	function-definition
	adt-declaration
.s2
The
.CW implement
declaration at the start identifies the type of the module that
is being implemented.
The rest of the program consists of a sequence of various kinds of
declarations and definitions that announce the names
of data objects, types, and functions, and also create
and initialize them.
It must include a module declaration for the module
being implemented and the objects it announces,
and may also include declarations for the functions, data
objects, types, and constants used privately within the module
as well as declarations for modules used by it.
.PP
Declarations are used both at the top
level (outside of functions) and also inside functions
and module declarations.
Some styles of declaration
are allowed only in certain of these places,
but all will be discussed together.
.PP
Most implementation modules provide an implementation for one type of module.
Several module types may be listed, however, in the
.CW implement
declaration, when the implementation module implements them all.
When the same name appears in more than one such module type, it must
have the same type.
.NH 1
Declarations
.PP
Declarations take several forms:
.s1
declaration:
	identifier-listC : ItypeC ;I
	identifier-listC : ItypeC = IexpressionC ;I
	identifier-listC : con IexpressionC ;I
	Iidentifier-listC : import Iidentifier C;I
	identifier-listC : typeI typeC ;I
	identifier-listC : exceptionI tuple-typeO
	Cinclude Istring-constantC ;I

identifier-list:
	identifier
	identifier-listC , Iidentifier

expression-list:
	expression
	expression-listC , Iexpression
.s2
.NH 2
Data declarations
.PP
These forms constitute the basic way to declare and
initialize data:
.s1
	identifier-listC : ItypeC ;I
	identifier-listC : ItypeC = IexpressionC ;I
.s2
A comma-separated sequence of identifiers is followed by a colon
and then the name of a type.
Each identifier is declared as having that type and denotes a
particular object
for rest of its scope (see §11 below).
If the declaration contains
.CW =
and an expression, the type must be a data type, and
all the objects are initialized from
the value of the expression.
In a declaration at the top level
(outside of a function), the expression must be
constant (see §8.5) or an array initialized with constant expressions;
the bound of any array must be a constant expression.
Lists and
.CW ref
.CW adt
types may not be initialized at the top level.
If an object is not explicitly initialized, then
it is always set to
.CW nil
if it has a reference type;
if it has arithmetic type, then it is set to 0
at the top level and is undefined if it occurs
within a function.
.PP
For example,
.P1
	i, j: int = 1;
	r, s: real = 1.0;
.P2
declares
.CW i
and
.CW j
as integers,
.CW r
and
.CW s
as real.
It sets
.CW i
and
.CW j
to 1,
and
.CW r
and
.CW s
to 1.0.
.PP
Another kind of declaration is a shorthand.
In either of
.s1
	identifierC := IexpressionC ;I
	C( Iidentifier-listC ) := IexpressionC ;I

.s2
identifiers on the left are declared using the type of the expression,
and are initialized with the value of the expression.
In the second case, the expression must be a tuple or an
.CW adt ,
and the types and values attributed to the identifiers
in the list are taken from the members of the tuple, or the
data members of the
.CW adt
respectively.
For example,
.P1
	x: int = 1;
.P2
and
.P1
	x := 1;
.P2
are the same.
Similarly,
.P1
	(p, q) := (1, 2.1);
.P2
declares the identifiers on the left as
.CW int
and
.CW real
and initializes them to 1 and 2.1 respectively.
Declarations with
.CW :=
can also be expressions, and are discussed again in §8.4.4 below.
.NH 2
Constant declarations
.PP
The
.CW con
declaration
.s1
	Iidentifier-listC : conI expressionC ;I
.s2
declares a name (or names) for constants.
The
.I expression
must be constant (see §8.5).
After the declaration,
each identifier in the list may be used anywhere a constant
of the appropriate type is needed;
the type is taken from the type of the constant.
For example, after
.P1
	Seven: con 3+4;
.P2
the name
.CW Seven
is exactly the same as the constant 7.
.PP
The identifier
.CW iota
has a special meaning in the expression in a
.CW con
declaration.
It is equivalent to the integer constant
.CW 0
when evaluating the expression for the first (leftmost) identifier declared,
.CW 1
for the second, and so on numerically.
For example, the declaration
.P1
	M0, M1, M2, M3, M4: con (1<<iota);
.P2
declares several constants
.CW M0
through
.CW M4
with the values 1, 2, 4, 8, 16 respectively.
.PP
The identifier
.CW iota
is not reserved except inside the expression
of the
.CW con
declaration.
.NH 2
adt declarations
.PP
An
.CW adt
or abstract data type contains data objects and functions that
operate on them.
The syntax is
.s1
adt-declaration:
	IidentifierC : adt { Iadt-member-listOC } ;I

adt-member-list:
	adt-member
	adt-member-list adt-member

adt-member:
	identifier-listC : cyclicO  Idata-typeC ;I
	identifier-listC : con IexpressionC ;I
	identifier-listC : Ifunction-typeC ;I
	Cpick { Ipick-member-listC }I
.s2
After an
.I adt-declaration ,
the identifier becomes the name of the type of that
.CW adt .
For example, after
.P1
	Point: adt {
		x, y: int;
		add: fn (p: Point, q: Point): Point;
		eq: fn (p: Point, q: Point): int;
	};
.P2
the name
.CW Point
is a type name for an
.CW adt
of two integers and two
functions; the fragment
.P1
	r, s: Point;
	xcoord: int;
	...
	xcoord = s.x;
	r = r.add(r, s);
.P2
makes sense.
The first assignment selects one of the data members of
.CW s ;
the second calls one of the function members of
.CW r .
.PP
As this example indicates,
.CW adt
members are accessed by mentioning an object with the
.CW adt
type, a dot, and then the name of the member;
the details will be discussed in §8.13 below.
A special syntactic indulgence is available for functions declared within an
.CW adt :
frequently such a function
receives as an argument the same object used to access it
(that is, the object before the dot).
In the example just above,
.CW r
was both the object being operated on and the first argument to the
.CW add
function.
If the first formal argument of a function declared in an
.CW adt
is marked with the
.CW self
keyword, then in any calls to the function, the
.CW adt
object is implicitly passed to the function, and
is not mentioned explicitly in the actual argument list
at the call site.
For example, in
.P1
	Rect: adt {
		min, max: Point;
		contains: fn(r: self Rect, p: Point): int;
	};

	r1: Rect;
	p1: Point;
	...
	if (r1.contains(p1)) ...
.P2
because the first argument of the
.CW contains
function is declared with
.CW self ,
the subsequent call to it automatically passes
.CW r1
as its first argument. The
.CW contains
function itself is defined elsewhere with this first
argument explicit.
(This mechanism is analogous to the
.I this
construct in C++ and other languages,
but puts the special-casing at the declaration site and makes it explicit.)
.PP
If
.CW self
is specified in the declaration of a function, it must also be
specified in the definition as well.  For example,
.CW contains
would be defined
.P1
	Rect.contains(r: self Rect, p: Point)
	{
		. . .
	}
.P2
.PP
The
.CW adt
type in Limbo
does not provide control over the visibility
of its individual members; if any are accessible, all are.
.PP
Constant
.CW adt
members follow the same rules as ordinary constants (§6.2).
.PP
The
.CW cyclic
modifier will be discussed in §11.1.
.NH 3
pick adts
.PP
An
.CW adt
which contains a
.CW pick
member is known as a
.I pick
.I adt .
A
.CW pick
.CW adt
is Limbo's version of a
.I "discriminated union" .
An
.CW adt
can only contain one
.CW pick
member and it must be the last component of the
.CW adt .
Each
.I identifier
enumerated in the
.I pick-tag-list
names a variant type of the
.CW pick
.CW adt .
The syntax is
.s1
pick-member-list:
	pick-tag-listC =>I
	pick-member-list pick-tag-listC =>I
	pick-member-list identifier-listC : cyclicO  Idata-typeC ;I
.s2
.s1
pick-tag-list:
	identifier
	pick-tag-listC or Iidentifier
.s2
.PP
The
.I pick-member-list
contains a set of data members for each
.I pick-tag-list .
These data members are specific to those variants of the
.CW pick
.CW adt
enumerated in the
.I pick-tag-list .
The
.CW adt
data members found outside of the
.CW pick
are common to all variants of the
.CW adt  .
A
.CW pick
.CW adt
can only be used as a
.CW ref
.CW adt
and can only be initialized from a value of one of its variants.
For example, if
.CW Constant
is a
.CW pick
.CW adt
and
.CW Constant.Real
is one of its variant types then
.P1
	c : ref Constant = ref Constant.Real("pi", 3.1);
.P2
will declare
.CW c
to have type
.CW ref
.CW Constant
and initialize it with a value of the variant type
.CW ref
.CW Constant.Real .
.NH 2
Type declarations
.PP
The type declaration
.s1
	Iidentifier-listC : typeI data-type  ;I
.s2
introduces the identifiers as synonyms for the
given type.
Type declarations are transparent; that is,
an object declared with the newly-named
type has the same type as the one it abbreviates.
.NH 2
Module declarations
.PP
A module declaration collects and packages declarations of
.CW adt ,
functions, constants and simple types, and creates an
interface with a name
that serves to identify the type of the module.
The syntax is
.s1
module-declaration:
	IidentifierC : module { Imod-member-listOC } ;I

mod-member-list:
	mod-member
	mod-member-list mod-member

mod-member:
	identifier-listC : Ifunction-typeC ;I
	identifier-listC : Idata-typeC ;I
	adt-declarationC ;I
	identifier-listC : con Iexpression C;I
	identifier-listC : type Itype C;I
.s2
After a module declaration, the named
.I identifier
becomes the name of the type of that module.
For example, the declaration
.P1
Linear: module {
	setflags: fn (flag: int);
	TRUNCATE: con 1;
	Vector: adt {
		v: array of real;
		add: fn (v1: self Vector, v2: Vector): Vector;
		cross: fn (v1: self Vector, v2: Vector): Vector;
		dot: fn (v1: self Vector, v2: Vector);
		make: fn (a: array of real): Vector;
	};
	Matrix: adt {
		m: array of array of real;
		add: fn (m1: self Matrix, m2: Matrix): Matrix;
		mul: fn (m1: self Matrix, m2: Matrix): Matrix;
		make: fn (a: array of array of real): Matrix;
	};
};
.P2
is a module declaration for a linear algebra package that
implements two
.CW adt ,
namely
.CW Vector
and
.CW Matrix ,
a constant,
and a function
.CW setflags .
The name
.CW Linear
is the type name for the module, and it may be used to declare
an object referring to an instance of the module:
.P1
	linearmodule:  Linear;
.P2
Before the module can be used, it must be loaded, for example in
the style:
.P1
	linearmodule = load Linear "/usr/dmr/limbo/linear.dis";
	if (linearmodule == nil) {
		sys->print("Can't load Linear\en");
		exit;
	}
.P2
The
.CW load
operator is discussed more fully in §8.4.5 below.
.PP
To initialize data declared as part of a module
declaration, an assignment expression may be used at the top level.
For example:
.P1
	implement testmod;
	testmod: module {
		num:	int;
	};
	. . .
	num = 5;
.P2
The right side of the assignment must be a constant expression (§8.5).
.NH 2
Declarations with
.CW import
.PP
These declarations take the form
.s1
	Iidentifier-listC : import Iidentifier C;I
.s2
Identifiers for entities
declared within a module declaration are normally
meaningful only in a context that
identifies the module.
The
.CW import
declaration lifts the names of specified members of a module
directly into the current scope.
The use of
.CW import
will be discussed more fully in §8.1.4 below, after the syntax
for expressions involving modules has been presented.
.NH 2
Exception declarations
.PP
Exceptions represent run-time errors not data objects or values.
Exception declarations have the form:
.s1
	identifier-listC : exceptionI tuple-typeO
.s2
Each identifier gives a compile-time name to a distinct user-defined run-time error,
signaled at run-time by a
.CW raise
statement that quotes that identifier, as described below.
An exception optionally includes a tuple of data values that qualifies the exception;
the types of those values are provided by the tuple type in this declaration.
.NH 2
Declarations with
.CW include
.PP
The string following the
.CW include
keyword names
a file, which is inserted into the program's
text at that point.
The included
text is treated like text literally present.
Conventionally, included files declare
module interfaces and are named with the suffix
.CW .m .
The directories to be searched for included files
may be specified to the Limbo compiler command.
Include files may be nested.
.NH 1
Function definitions
.PP
All executable code
is supplied as part of a function definition.
The syntax is
.s1
function-definition:
	function-name-part function-arg-retC { IstatementsC }I

function-name-part:
	identifier
	function-name-partC . Iidentifier
.s2
The syntax of the statements in a function will be discussed in §9 below.
As a brief example,
.P1
	add_one(a: int): int
	{
		return a+1;
	}
.P2
is a simple function
that might be part of the top level of a module.
.PP
Functions that are declared within an
.CW adt
use the qualified form of definition:
.P1
	Point: adt {
		x, y: int;
		add: fn (p: Point, q: Point): Point;
		eq: fn (p: Point, q: Point): int;
	}
	. . .
	Point.add(p: Point, q: Point): Point
	{
		return Point(p.x+q.x, p.y+q.y);
	}
.P2
Because an
.CW adt
may contain an
.CW adt ,
more than one qualification is possible.
.NH 1
Expressions
.PP
Expressions in Limbo resemble those of C, although some
of the operators are different.
The most salient difference between Limbo's expression
semantics and those of C is that Limbo
has no automatic coercions between types; in Limbo every
type conversion is explicit.
.NH 2
Terms
.PP
The basic elements of expressions are terms:
.s1
term:
	identifier
	constant
	real-constant
	string-constant
	CnilI
	C( Iexpression-listC )I
	termC . Iidentifier
	termC -> Iterm
	termC ( Iexpression-listOC )I
	termC [ IexpressionC ]I
	termC [ IexpressionC : IexpressionC ]I
	termC [ IexpressionC : ]I
	termC ++I
	termC --I
.s2
The operators on terms all associate to the left,
and their order of precedence, with tightest listed first, is as follows:
.P1
			.
			->
			() [] ++ --
.P2
.NH 3
Simple terms
.PP
The first five kinds of term are constants and identifiers.
Constants have a type indicated by their syntax.
An identifier used in an expression is often a previously declared
data object with a particular data type; when used as a term
in an expression
it denotes the value stored in the object, and the term has
the declared object's type.
Sometimes, as discussed below, identifiers used in expressions
are type names, function names, or module identifiers.
.NH 3
Parenthesized terms
.PP
A comma-separated list of expressions enclosed in parentheses
is a term.
If a single expression is present in the list,
the type and value are those of the expression;
the parentheses affect only the binding
of operators in the expression of which the term
is a part.
If there is more than one expression in the list,
the value is a tuple.
The member types
and values are taken from those of the expressions.
.NH 3
Selection
.PP
A term of the form
.s1
	termC . Iidentifier
.s2
denotes selection of a member of an
.CW adt
or one element from a tuple.
.PP
In the first case,
the term must be a
type name or yield an object;
its type must be
.CW adt
or
.CW ref
.CW adt ;
the identifier must be a member of the
.CW adt .
The result denotes the named member (either a data object
or a function).
.PP
In the second case,
the term must yield a value of a tuple type,
and the identifier must have the form \f(CWt\fP\fIn\fP
where
.I n
is a decimal number giving the index (starting from 0) of an element of the tuple.
The result is the value of that element.
.NH 3
Module qualification
.PP
A term of the form
.s1
	termC -> Iterm
.s2
denotes module qualification.
The first term identifies a module: either it is a module type name,
or it is an expression of module type.
The second term is a constant name, type, or function specified within
that module's declaration.
Either the module type name or
an object of the module's type suffices to qualify constants and types;
functions directly exported by the module or contained within its
.CW adt
must be qualified by an object of the module's type, initialized with
.CW load .
.PP
An example using an abridged version of an example above: given
.P1
	Linear: module {
		setflags: fn(flag: int);
		TRUNCATE: con 1;
		Vector: adt {
			make: fn(v: array of real): Vector;
			v: array of real;
		};
	};
.P2
one might say
.P1
	lin := load Linear "/dis/linear.dis";
	a: array of real;

	v1: lin->Vector;
	v2: Linear->Vector;
	lin->setflags(Linear->TRUNCATE);
	v1 = lin->(Linear->Vector).make(a);
	v1 = lin->v1.make(a);
	v1 = lin->v1.add(v1);
	v1.v = nil;
.P2
Here, the declarations for
.CW v1
and
.CW v2
are equivalent; either a module type name (here,
.CW Linear )
or a handle (here,
.CW lin )
suffices to identify the module.
In the call to
.CW setflags ,
a handle
is required for the call itself;
the type name is sufficient for the constant.
.PP
When calling a function associated with an
.CW adt
of another module, it is necessary to identify
both the module and the
.CW adt
as well as the function.
The two calls to the
.CW make
function illustrate two ways of doing this.
In the first,
.P1
	v1 = lin->(Linear->Vector).make(a);
.P2
the module handle
.CW lin
is specified first, then
the type name of the
.CW Vector
.CW adt
within it, and then the function.
In the second call
.P1
	v1 = lin->v1.make(a);
.P2
instead of using a type name to specify the
.CW adt ,
an instance of an object of the appropriate type is
used instead.
In the first example, the parentheses are required because
the qualification operators associate to the left.
.P1
	v1 = lin->Vector.make(a);	# Wrong
	v1 = lin->Linear->Vector.make(a);	# Wrong
.P2
The first is wrong because the same
.CW lin
can't serve as a qualifier for both the type and the call;
the second is wrong because
.CW lin->Linear
is meaningless.
.PP
Using
.CW import
makes the code less verbose:
.P1
	lin := load Linear "/usr/dmr/limbo/linear.dis";
	Vector, TRUNCATE, setflags: import lin;
	a: array of real;

	v1: Vector;
	v2: Vector;
	setflags(TRUNCATE);
	v1 = Vector.make(a);
	v1 = v1.make(a);
	v1 = v1.add(v1);
	v1.v = nil;
.P2
.NH 3
Function calls
.PP
The interpretation of an expression in the form
.s1
	termC ( Iexpression-listOC )
.s2
depends on the declaration of the term.
If it is the (perhaps qualified) name of an
.CW adt ,
then the expression is a cast; this is discussed in §8.2.11 below.
If the term is either the (perhaps qualified) name of a function
or a value of a function reference type, and
the expression means a function call; this is discussed here.
.PP
A plain identifier as the
.I term
can name a function defined
in the current module or imported into it.
A term qualified by using the selection operator
.CW .
specifies a function member of an
.CW adt ;
a term using
.CW ->
specifies a function defined in another module.
.PP
The
.I term ,
including a plain identifier denoting a variable of function reference type,
can also yield a function reference value.
The value specifies both a function and its module,
established when the value was created,
and cannot be qualified by the
.B ->
specifier.
.PP
Function calls in Limbo
create a copy of each argument of value type,
and the execution of a function cannot
affect the value of the corresponding actual argument.
For arguments of reference type,
execution of the function may affect the value of the object
to which the reference refers, although it cannot
change the argument itself.
The actual arguments to a function are evaluated
in an unspecified order,
although any side effects caused by argument evaluation
occur before the function is called.
.PP
Function calls may be directly or indirectly recursive;
objects declared within each function are distinct from
those in their dynamic predecessors.
.PP
Functions (§4.3, §7) may either return a value
of a specified type, or return no value.
If a function returns a value, it has the specified type.
A call to a function that returns no value may appear only as the
sole expression in a statement (§9.1).
.PP
A function name is converted to a reference to that function when it appears
in a context requiring a function reference type, including assignment to a variable,
as an actual parameter, or the return value of a function.
The resulting reference value includes the appropriate module value for the function name,
following the rules given above for implicit and explicit qualifiers, and imports.
For example, the following program fragment defines a table of commands:
.P1
	Cmd: adt {
		c:	int;
		f:	ref fn(a: array of string): int;
	};

	mkcmds(): array of Cmd
	{
		return array[] of {
			('.', editdot),
			('a', editadd),
			('d', editdel),
			('?', edithelp),
			('w', editwrite),
			('q', editquit),
		};
	}

	editdot(a: array of string): int
	{
		...
	}
	\&...
	editquit(a: array of string): int
	{
		...
	}
.P2
which might be used as follows:
.P1
	cmd := mkcmds();
	...
	for(i := 0; i < len cmd; i++)
		if(cmd[i].c == c){
			cmd[i].f(args);
			return;
		}
	error("unknown command");
.P2
.NH 3
Subscripting and slicing
.PP
In a term of the form
.s1
	termC [ IexpressionC ]I
.s2
the first term must be an array or a string, and the
bracketed expression must have
.CW int
type.
The whole term
designates a member of the array or string, indexed by the bracketed expression;
the index origin is 0.
For an array, the type of the whole term is
the type from which the array is constructed;
for a string, the type is an
.CW int
whose value is the Unicode character at that position in the string.
.PP
It is erroneous to refer to a nonexisting
part of an array or string.
(A single exception to this rule, discussed in §8.4.1 below,
allows extending a string by assigning a character at its end.)
.PP
In a term of the form
.s1
	termC [ IexpressionC : IexpressionC ]I
.s2
the first term must be an array or a string, and the whole term
denotes a slice of it.
The first expression is the lower bound, and the second
is the upper.
If
.CW e1
is the first expression and
.CW e2
is the second, then in
.CW a[e1:e2]
it must be the case that
.CW "0<=e1, e1<=e2, e2<=len a" ,
where
.CW len
gives the number of elements in the array or string.
When the term is an array, the value is an
array of the same type beginning at the indicated
lower bound and extending to the element just before
the upper bound.
When the term is a string, the value is similarly the substring
whose first character is indexed by the lower bound
and whose last character lies just before the upper bound.
.PP
Thus, for both arrays and strings, the number of elements in
.CW "a[e1:e2]
is equal to
.CW e2-e1 .
.PP
A slice of the form
.CW a[e:]
means
.CW "a[e:len a].
.PP
When a string slice is assigned to another string or passed as an
argument, a copy of its value is made.
.PP
A slice of an array produces a reference to the designated subarray;
a change to an element of either the original array or
the slice is reflected in the other.
.PP
In general, slice expressions cannot be the subject of
assignments.
However, as a special case, an array slice expression of the
form
.CW a[e1:]
may be assigned to.
This is discussed in §8.4.1.
.PP
The following example shows how slices
can be used to accomplish what would
need to be done with pointer arithmetic in C:
.P1
	fd := sys->open( ... );
	want := 1024;
	buf := array[want] of byte;
	b := buf[0:];
	while (want>0) {
		got := sys->read(fd, b, want);
		if (got<=0)
			break;
		b = b[got:];
		want -= got;
	}
.P2
Here the array
.CW buf
is filled by successive calls to
.CW sys->read
that may supply fewer bytes than requested; each call
stores up to
.CW want
bytes
starting at
.CW b[0] ,
and returns the number of bytes stored.
The invariant is that the slice
.CW b
always refers to the part of the array still to be stored into.
.NH 3
Postfix increment and decrement
.PP
A term of the form
.s1
	termC ++I
.s2
is called a
.I post-increment .
The term must be an lvalue (see §8.4 below) and must have an
arithmetic type.
The type and value of the whole term is
that of the incremented term.
After the value is taken, 1 of the appropriate
type is added to the lvalue.
The result is undefined if the same object is changed
more than once in the same expression.
.PP
The term
.s1
	termC --I
.s2
behaves analogously to the increment case except
that 1 is subtracted from the lvalue.
.PP
.NH 2
Monadic expressions
.PP
Monadic expressions are expressions with
monadic operators, together with a few more
specialized notations:
.s1
monadic-expression:
	term
	monadic-operator monadic-expression
	Carray [ IexpressionC ] of Idata-type
	Carray [ IexpressionOC ] of { Iinit-listC }I
	Clist of { Iexpression-listC }I
	Cchan of Idata-type
	Cchan [ IexpressionC ] of Idata-type
	data-type monadic-expression

monadic-operator: one of
	C+ - ! ~ ref * ++ -- <- hd tl lenI
.s2
.NH 3
Monadic additive operators
.PP
The
.CW -
operator produces the negative of its operand, which
must have an arithmetic type.
The type of the result is the same as the type of
its operand.
.PP
The
.CW +
operator has no effect; it is supplied only for
symmetry.
However, its argument must have an arithmetic type
and the type of the result is the same.
.NH 3
Logical negation
.PP
The
.CW !
operator yields the
.CW int
value 1 if its operand
has the value 0, and yields 0 otherwise.
The operand must have type
.CW int .
.NH 3
One's complement
.PP
The
.CW ~
operator yields the 1's complement of its
operand, which must have type
.CW int
or
.CW byte .
The type of the result is the same as that of its operand.
.NH 3
Reference and indirection operators
.PP
If
.I e
is an expression of an
.CW adt
type, then
.CW ref
.I e
is an expression of
.CW ref
.CW adt
type whose value refers to (points to) an anonymous object with value
.I e .
The
.CW ref
operator differs from the unary
.CW &
operator of C; it makes a new object and returns a reference
to it, rather than generating a reference to an existing object.
.PP
If
.I e
is an expression of type
.CW ref
.CW adt ,
then
.CW *
.I e
is the value
of the
.CW adt
itself.
The value of
.I e
must not be
.CW nil .
.PP
For example, in
.P1
	Point: adt { ... };
	p: Point;
	pp: ref Point;
	p = Point(1, 2);
	pp = ref p;	# pp is a new Point; *pp has value (1, 2)
	p = Point(3, 4);	# This makes *pp differ from p
	*pp = Point(4, 5);	# This does not affect p
.P2
the expression
.CW *pp
at first refers to a copy of the value stored in
.CW p ,
so
.CW "*pp == p
is true; however, when
.CW p
is changed later,
.CW *pp
does not change.
.NH 3
Prefix increment and decrement
.PP
A monadic expression of the form
.s1
	C++ Imonadic-expression
.s2
is called a
.I pre-increment .
The monadic expression must be an lvalue (see §8.4 below) and must have an
arithmetic type.
Before the value is taken, 1 of the appropriate type
is added to the lvalue.
The type and value of the whole expression is
that of the now incremented term.
The result is undefined if the same object is changed
more than once in the same expression.
.PP
The term
.s1
	C-- Imonadic-expression
.s2
behaves analogously to the increment case except
that 1 is subtracted from the lvalue.
.NH 3
Head and tail
.PP
The operand of the
.CW hd
operator must be a non-empty list.
The value is the first member of the list
and has that member's type.
.PP
The operand of the
.CW tl
operator must be a non-empty list.
The value is the tail of the list,
that is, the part of the list after its
first member.
The tail of a list with one member is
.CW nil .
.NH 3
Length
.PP
The operand of the
.CW len
operator is a string, an array, or a list.
The value is an
.CW int
giving the number of elements currently in the item.
.NH 3
Tagof
.PP
The operand of the
.CW tagof
operator is a monadic expression of type
.CW ref
.CW adt
that refers to a
.CW pick
.CW adt .
or the type name of a
.CW pick
.CW adt
or one of its variants.
The value is an
.CW int
giving a unique value for each of the variants and for the
.CW pick
.CW adt
type itself.
.NH 3
Channel communication
.PP
The operand of the communication operator
.CW <-
has type
.CW chan
.CW  of
.I sometype .
The value of the expression
is the first unread object previously sent over that
channel, and has the type associated with the channel.
If the channel is empty, the program delays
until something is sent.
.PP
As a special case, the operand of
.CW <-
may have type
.CW array
.CW of
.CW chan
.CW of
.I sometype .
In this case, all of the channels in the array are tested;
one is fairly selected from those that have data.
The expression yields a tuple of type
.CW (int,
.I sometype
.CW ) ;
its first member gives the index of the channel from
which data was read, and its second member is the
value read from the channel.
If no member of the array has data ready, the expression delays.
.PP
Communication channels are treated more fully in §9.8 and
§9.13 below with the discussion of the
.CW alt
and
.CW spawn
statements.
.NH 3
Creation of arrays
.PP
In the expressions
.s1
	Carray [ IexpressionC ] of Idata-type
	Carray [ IexpressionOC ] of { Iinit-listC ,OC }I
.s2
the value is a new array of the specified type.
In both forms, the
.I expression
must be of type
.CW int ,
and it supplies the size of the array.
In the first form, the type is given,
and the values in the array are initialized as
appropriate to the underlying type.
In the second form, a comma-separated list of values to initialize
the array is given, optionally followed by a trailing comma.
The type of the array is taken from the types of
the initializers, which must all be the same.
The list of initializers has the syntax
.s1
init-list:
	element
	init-listC , Ielement

element:
	expression
	expressionC => Iexpression
	C* => Iexpression
.s2
In an
.I init-list
of plain expressions (without
.CW => ),
the members of the array
are successively initialized with the corresponding
elements of the init-list.
An element of the form
.CW e1=>e2
initializes the member of the array at subscript
.CW e1
with the expression
.CW e2 .
After such an element has been given, subsequent
simple elements (without
.CW => )
begin initializing at position
.CW e1+1
and so on.
Each of the first expressions must be of type
.CW int
and must evaluate to a constant (§8.5).
.PP
If an element of the form
.CW *
.CW =>e2
is present, all members of the array not otherwise
initialized are set to the value
.CW e2 .
The expression
.CW e2
is evaluated for each subscript position,
but in an undefined order.
For example,
.P1
	arr := array[3] of { * => array[3] of { * => 1 } };
.P2
yields a 2-dimensional array (actually an array of arrays) filled with
.CW 1 's.
.PP
If the expression giving the size of the array is omitted, its size
is taken from the largest subscript of
a member explicitly initialized.
It is erroneous to initialize a member twice.
.NH 3
Creation of lists
.PP
The value of an expression
.s1
	Clist of { Iexpression-listC }I
.s2
is a list consisting of the expressions given.
The types of the expressions must be identical,
and this type is the underlying type of the list.
The first expression is the head of the list, and the
remaining expressions are a list constituting its tail.
Where a list is expected,
.CW nil
specifies an empty list.
.NH 3
Creation of channels
.PP
The value of
.s1
	Cchan of Idata-type
.s2
is an initialized channel of the specified type.
Just a declaration of a channel leaves it initialized only to
.CW nil ;
before it can be used it must be created.  For example,
.P1
	ch: chan of int;		# just declares, sets ch to nil
	. . .
	ch = chan of int;	# creates the channel and assigns it
.P2
Such a channel is unbuffered.
The value of
.s1
	Cchan [ IexpressionC ] of Idata-type
.s2
is an initialized channel of the specified type.
The
.I expression
must be of type
.CW int ,
and sets the size of the channel's buffer.
If the size is zero, the channel is unbuffered, as for the first form.
.NH 3
Casts
.PP
An expression of the form
.s1
	data-type monadic-expression
.s2
in which a type name is followed by an expression
is called a
.I cast ,
and converts the monadic expression to the named type.
Only certain specialized forms are provided for.
.NH 4
Arithmetic casts
.PP
In arithmetic casts, the named type must be one of
.CW byte ,
.CW int ,
.CW big ,
or
.CW real ,
and the monadic-expression must have arithmetic type.
For example,
.P1
	byte 10
.P2
is an expression of
.CW byte
type and value 10.
When real values are converted to integral ones,
they are rounded to the nearest integer, and away from 0
if there is a tie.
The effect of overflow during conversion is undefined.
.NH 4
Casts to strings
.PP
Here the named data type is
.CW string .
In a first form, the monadic expression has arithmetic type
.CW byte , (
.CW int ,
.CW big ,
or
.CW real )
and the value is a string containing the decimal representation
of the value, which may be either positive or negative.
A
.CW real
operand is converted as if by format
.CW %g ,
and if the result is converted back to
.CW real ,
the original value will be recovered exactly.
.PP
In a second form,
the monadic expression has type
.CW array
.CW of
.CW byte .
The value is a new string containing the Unicode characters
obtained by interpreting the bytes in the array as a UTF-8 representation
of that string.
(UTF-8 is a representation of 16-bit Unicode characters as one,
two, or three bytes.)
The result of the conversion is undefined if the byte array
ends within a multi-byte UTF-8 sequence.
.NH 4
Casts from strings
.PP
In a first form, the monadic expression is a string,
and the named type is an arithmetic type.
The value is obtained by converting the string to
that type.  Initial white space is ignored; after a possible
sign, conversion
ceases at the first character not part of a number.
.PP
In a second form, the named type is
.CW array
.CW of
.CW byte
and the monadic-expression is a string.
The value is a new array of bytes containing the UTF-8 representation
of the Unicode characters in the string.
For example,
.P1
	s := "Ångström";
	a := array of byte s;
	s = string a;
.P2
takes the string
.CW s
apart into bytes in the second line,
and puts it back in the third.
The length of
.CW s
is 8, because it contains that many characters;
the length of
.CW a
is larger, because some of its characters require more than
one byte in the UTF-8 representation.
.NH 4
Casts to
.CW adt
and
.CW ref
.CW adt
.PP
Here the named type is that of an
.CW adt
or
.CW ref
.CW adt ,
and the monadic expression is a comma-separated list of expressions
within parentheses.
The value of the expression is an instance of an
.CW adt
of the named type whose data members are initialized with
the members of the list, or whose single data member
is initialized with the parenthesized expression.
In case the type is
.CW ref
.CW adt ,
the value is a reference to the new
instance of the
.CW adt .
.PP
The expressions in the list, read in order, correspond with the data
members of the
.CW adt
read in order; their types and number must agree.
Placement of any function members of the
.CW adt
is ignored.
For example,
.P1
	Point: adt {
		x: int;
		eq: fn (p: Point): int;
		y: int;
	};
	. . .
	p: Point;
	p = Point(1, 2);
.P2
puts in
.CW p
a
.CW Point
whose
.CW x
value is 1 and whose
.CW y
value is 2.
The declaration and assignment could also be written
.P1
	p := Point(1, 2);
.P2
.NH 2
Binary expressions
.PP
Binary expressions are either monadic expressions,
or have two operands and an infix operator;
the syntax is
.s1
binary-expression:
	monadic-expression
	binary-expression binary-operator binary-expression

binary-operator: one of
	C** * / % + - << >> < > <= >= == != & ^ | :: && ||I
.s2
All these binary operators are left-associative except for
.CW **
and
.CW :: ,
which associate to the right.
Their precedence is as listed here, with tightest first:
.P1
			**
			* / %
			+ -
			<< >>
			< > <= >=
			== !=
			&
			^
			|
			::
			&&
			||
.P2
.NH 3
Exponentiation
.PP
The
.CW **
operator accomplishes exponentiation.
The type of the left operand must be
.CW int ,
.CW big
or
.CW real .
The type of the right operand must be
.CW int .
The result has the type of the left operand.
The operator is right associative, thus
.P1
	3**4*2 = (3**4)*2 = 81*2 = 162
	-3**4 = (-3)**4 = 81
	2**3**2 = 2**(3**2) = 2**9 = 512
.P2
.NH 3
Multiplicative operators
.PP
The
.CW * ,
.CW / ,
and
.CW %
operators respectively accomplish multiplication, division, and remainder.
The operands must be of identical arithmetic type, and the result has that
same type.
The remainder operator does not apply to type
.CW real .
If overflow or division by 0 occurs, the result is undefined.
The absolute value of
.CW a%b
is less than the absolute value of
.CW b ;
.CW "(a/b)*b + a%b
is always equal to
.CW a ;
and
.CW a%b
is non-negative if
.CW a
and
.CW b
are.
.NH 3
Additive operators
.PP
The
.CW +
and
.CW -
operators respectively accomplish addition and subtraction
of arithmetic operands of identical type;
the result has the same type.
The behavior on overflow or underflow is undefined.
The
.CW +
operator may also be applied to strings;
the result is a string that is the concatenation of the operands.
.NH 3
Shift operators
.PP
The shift operators are
.CW <<
and
.CW >> .
The left operand may be
.CW big ,
.CW int ,
or
.CW byte ;
the right operand is
.CW int .
The type of the value is the same as its left operand.
The value of the right operand must be non-negative
and smaller than the number of bits in the left operand.
For the left-shift operator
.CW << ,
the fill bits are 0;
for the right-shift operator
.CW >> ,
the fill bits are a copy of the sign for the
.CW int
case, and 0 for the
.CW byte
case.
.NH 3
Relational operators
.PP
The relational operators are
.CW <
(less than),
.CW >
(greater than),
.CW <=
(less than or equal),
.CW >=
(greater than or equal),
.CW ==
(equal to),
.CW !=
(not equal to).
The first four operators, which generate orderings,
apply only to arithmetic types
and to strings; the types of their operands
must be identical, except that a string may be
compared to
.CW nil .
Comparison on strings is lexicographic over the
Unicode character set.
.PP
The equality operators
.CW ==
and
.CW !=
accept operands of arithmetic, string, and reference types.
In general, the operands must have identical type,
but reference types and strings may be compared for identity with
.CW nil .
Equality for reference types occurs when the operands
refer to the same object, or when both are
.CW nil .
An uninitialized string, or one set to
.CW nil ,
is identical to the empty string denoted
.CW \&""
for all the relational operators.
.PP
The value of any comparison is the
.CW int
value 1 if the stated
relation is true, 0 if it is false.
.NH 3
Bitwise logical operators
.PP
The logical operators
.CW &
(and),
.CW ^
(exclusive or) and
.CW |
(inclusive or)
require operands of the same type,
which must be
.CW byte ,
.CW int ,
or
.CW big .
The result has the same type and its
value is obtained by applying the operation
bitwise.
.NH 3
List concatenation
.PP
The concatenation operator
.CW ::
takes a object of any data type
as its left operand and a list as its right operand.
The list's underlying type must be the same as
the type of the left operand.
The result is a new list with the left operand
tacked onto the front:
.P1
	hd (a :: l)
.P2
is the same as
.CW a .
.NH 3
Logical operators
.PP
The logical
.I and
operator
.CW &&
first evaluates its left operand.
If the result is zero, then the value of the
whole expression is the
.CW int
value 0.
Otherwise the right operand is evaluated; if
the result is zero, the value of the whole
expression is again 0; otherwise it is 1.
The operands must have the same arithmetic type.
.PP
The logical
.I or
operator
.CW ||
first evaluates its left operand.
If the result is non-zero, then the value of the
whole expression is the
.CW int
value 1.
Otherwise the right operand is evaluated; if
the result is non-zero, the value of the whole
expression is again 1; otherwise it is 0.
The operands must have the same arithmetic type.
.NH 2
General Expressions
.PP
The remaining syntax for expressions is
.s1
expression:
	binary-expression
	lvalue-expression assignment-operator expression
	C( Ilvalue-expression-listC ) = Iexpression
	send-expression
	declare-expression
	load-expression

assignment-operator: one of
	C= &= |= ^= <<= >>= += -= *= /= %=I
.s2
The left operand of an assignment can take only certain forms, called lvalues.
.s1
lvalue-expression:
	identifier
	CnilI
	termC [ IexpressionC ]I
	termC [ IexpressionC : ]I
	termC . Iidentifier
	C( Ilvalue-expression-listC )I
	C* Imonadic-expression

lvalue-expression-list:
	lvalue
	lvalue-expression-listC , Ilvalue
.s2
.NH 3
Simple assignments with
.CW =
.PP
In general, the types of the left and right operands
must be the same; this type must be a data type.
The value of an assignment is its new left operand.
All the assignment operators associate right-to-left.
.PP
In the ordinary assignment with
.CW = ,
the value of the right side is assigned to the object
on the left.
For simple assignment only, the left operand may be a
parenthesized list of lvalues and the right operand
either a tuple or an
.CW adt
whose data members correspond
in number and type to the lvalues in the list.
The members of the tuple, or
the data members of the
.CW adt ,
are assigned in sequence to
lvalues in the list.
For example,
.P1
	p: Point;
	x, y: int;
	(x, y) = p;
.P2
splits out the coordinates of the point into
.CW x
and
.CW y .
These rules apply recursively, so that if one of the
components of the left side is a parenthesized list of lvalues,
it is assigned from a corresponding
.CW adt
or tuple on the right.
.PP
If the left operand of a simple assignment is an
.CW adt
and the right side is a tuple, then the assignment
assigns the members of the tuple to the
.CW adt
data members; these must correspond in number and type
with the members of the tuple.
.PP
The constant
.CW nil
may be assigned to an lvalue of any reference type.
This lvalue will compare equal to
.CW nil
until it is subsequently reassigned.
Such an assignment also
triggers the removal of the object referred to unless other references
to it remain.
.PP
The left operand of an assignment may be the constant
.CW nil
to indicate that a value is discarded.
This applies in particular to any of the lvalues in
a tuple appearing on the left; to extend the examples above,
.P1
	(x, nil) = p;
.P2
assigns the
.CW x
member of the Point
.CW p
to the variable
.CW x .
.PP
A special consideration applies to
strings.
If an
.CW int
containing a Unicode character is assigned to a subscripted
string, the subscript
is normally required to lie within the string.
As a special case, the subscript's value may be equal to
the length of the string (that is, just beyond its end);
in this case, the character is appended to
the string, and the string's length increases by 1.
.PP
A final special case applies to array slices in the form
.CW e1[e2:] .
Such expressions may lie on the left of
.CW = .
The right side must be an array of the same type as
.CW e1 ,
and its length must be less than or equal to
.CW "(len e1)-e2.
In this case, the
elements in the array on the right replace the elements of
.CW e1
starting at position
.CW e2 .
The length of the array is unchanged.
.NH 3
Compound assignments
.PP
A compound assignment with
.I op\f(CW=\fP
is interpreted in terms of the plain assignment;
.P1
	e1 \fIop\f(CW= e2;
.P2
is equivalent to
.P1
	e1 \f(CW= (e1) \fIop \f(CW(e2);
.P2
except that
.CW e1
is evaluated only once.
.NH 3
Send expressions
.PP
A
.I send-expression
takes the form
.s1
send-expression:
	lvalue-expressionC <- = Iexpression
.s2
In the expression
.P1
	e1 <- = e2
.P2
the lvalue
.CW e1
must have type
.CW chan
.CW of
.I type ,
and
.CW e2
must be of that type.
The value of
.CW e2
is sent over the channel.
If no task is executing a
channel receive operation on the specified channel, and the channel is unbuffered or its buffer
is full, the sender blocks.
Task synchronization is discussed in §9.8 and §9.13 below.
.NH 3
Declare-expressions
.PP
A
.I declare-expression
is an assignment that also declares identifiers on its left:
.s1
declare-expression:
	lvalue-expressionC := Iexpression
.s2
Each of the constituent terms in the
.I lvalue-expression
must be an identifier or
.CW nil .
A plain identifier on the left
is declared as having the type of the expression,
and it is initialized with the expression's value.
When a parenthesized list of identifiers is given, the expression
must be a tuple or an
.CW adt ,
and the individual identifiers in the list are declared and initialized
with the members of the tuple, or the data members of the
.CW adt .
As with ordinary assignments, the keyword
.CW nil
may stand for an identifier whose declaration and assignment
are skipped.
.PP
The value and type of a declare-expression are the same as those of the expression.
.NH 3
Load expressions
.PP
A
.I load-expression
has the form
.s1
load-expression:
	Cload Iidentifier expression
.s2
The identifier is the identifier of a module, that is, the type
name declared in a
.CW module
declaration.
The expression following
.CW load
has type
.CW string
and names a file containing the
compiled form of the module.
The
.CW load
expression yields a handle for referring to the functions provided
by a module and its
.CW adt .
.PP
Execution of
.CW load
brings the file containing the module into local memory and dynamically type-checks
its interface: the run-time system ascertains that
the declarations exported by the module are compatible
with the module declaration visible in the scope of the
.CW load
operator (see §11.2).
In the scope of a module declaration, the types and constants
exported by the module may be referred to without a handle, but
the functions and data exported by the module
(directly at its top level, or within its
.CW adt )
may be called only using a valid
handle acquired by the
.CW load
operator.
.PP
The value of
.CW load
is
.CW nil
if the attempt to load fails, either because the file containing
the module can not be found, or because the found module does not
export the specified interface.
.PP
Each evaluation of
.CW load
creates a separate instance of the specified module;
it does not share data with any other instance.
.NH 2
Constant expressions
.PP
In several places a constant expression is required.
Such an expression contains operands that are
identifiers previously declared with
.CW con ,
or
.CW int ,
.CW big ,
.CW real ,
or
.CW string
constants.
These may be connected by any of the following operators:
.P1
.ta .5i 1i 1.5i 2i 2.5i 3i 3.5i 4i 4.5i 5i 5.5i
	+	-	*	/	%	&	|	^
	==	<	>	<=	>=	!=	<<	>>
	&&	||
	~	!
.P2
together with arithmetic and string casts, and parentheses for
grouping.
.NH 2
Expression evaluation
.PP
Expressions in Limbo are not reordered by the compiler;
values are computed in accordance with the parse of the expression.
However there is no guarantee of temporal evaluation order for expressions
with side effects, except in the following circumstances:
function arguments are fully evaluated before the function
is called; the logical operators
.CW &&
and
.CW ||
have fully defined order of evaluation, as explained above.
All side effects from an expression in one statement are
completed before the next statement is begun.
.PP
In an expression containing a constant subexpression (in the
sense of §8.5), the constant subexpression is evaluated at
compile-time with all exceptions ignored.
.PP
Underflow, overflow, and zero-divide conditions during integer
arithmetic produce undefined results.
.PP
The
.CW real
arithmetic of Limbo is all performed in IEEE double precision,
although denormalized numbers may not be supported.
By default,
invalid operations, zero-divide, overflow, and underflow
during real arithmetic are fatal; inexact-result is quiet.
The default rounding mode is round-to-nearest-even.
A set of routines in the
.CW Math
library module permits independent control of these modes within each thread.
.NH 1
Statements
.PP
The executable code within a function definition consists
of a sequence of statements and declarations.
As discussed in the Scope section §11 below,
declarations become effective at the place they appear.
Statements are executed in sequence except as discussed below.
In particular, the optional labels on some of the statements are used with
.CW break
and
.CW continue
to exit from or re-execute the labeled statement.
.s1
statements:
	(empty)
	statements declaration
	statements statement

statement:
	expressionC ;I
	C;I
	C{ IstatementsC }I
	Cif ( IexpressionC ) Istatement
	Cif ( IexpressionC ) IstatementC else Istatement
	labelO  Cwhile ( IexpressionOC ) Istatement
	labelO  Cdo IstatementC while ( IexpressionOC ) ;I
	labelO  Cfor ( IexpressionOC ; IexpressionOC ; IexpressionOC ) Istatement
	labelO  Ccase IexpressionC { Iqual-statement-sequenceC }I
	labelO  Calt { Iqual-statement-sequenceC }I
	labelO  Cpick IidentifierC := IexpressionC { Ipqual-statement-sequenceC }I
	Cbreak IidentifierOC ;I
	Ccontinue IidentifierOC ;I
	Creturn IexpressionOC ;I
	Cspawn ItermC ( Iexpression-listOC ) ;I
	Cexit ;I
	C{ IstatementsC } exceptionI identifierOC{ Iqual-statement-sequenceC }I
	Craise IexpressionOC ;I
.s2
.s1
label:
	identifier C:I
.s2
.NH 2
Expression statements
.PP
Expression statements consist of an expression followed by
a semicolon:
.s1
	expressionC ;I
.s2
Most often expression statements are assignments, but other expressions
that cause effects are often useful, for example calling a function
or sending or receiving on a channel.
.NH 2
Null statement
.PP
The null statement consists of a lone semicolon.
It is most useful for supplying an empty body
to a looping statement with internal side effects.
.NH 2
Blocks
.PP
Blocks are
.I statements
enclosed in
.CW {}
characters.
.s1
	C{ IstatementsC }I
.s2
A block starts a new scope.
The effect of any declarations within a block disappears
at the end of the block.
.NH 2
Conditional statements
.PP
The conditional statement takes two forms:
.s1
	Cif ( IexpressionC ) Istatement
	Cif ( IexpressionC ) IstatementC else Istatement
.s2
The
.I expression
is evaluated; it must have type
.CW int .
If it is non-zero, then the first
.I statement
is executed.
In the second form, the second
.I statement
is executed if the
.I expression
is 0.
The statement after
.CW else
is connected to the nearest
.CW else -less
.CW if .
.NH 2
Simple looping statements
.PP
The simple looping statements are
.s1
	labelO  Cwhile ( IexpressionOC ) Istatement
	labelO  Cdo IstatementC while ( IexpressionOC ) ;I
.s2
In both cases the expression must be of type
.CW int .
In the first form, the
.I expression
is first tested against 0;
while it is not equal, the
.I statement
is repeatedly executed.
In the second form, the
.I statement
is executed, and then, while the
.I expression
is not 0, the statement is repeatedly executed.
If the
.I expression
is missing, it is understood to be non-zero.
.NH 2
.CW for
statement
.PP
The
.CW for
statement has the form
.s1
	labelO  Cfor ( Iexpression-1OC ; Iexpression-2OC ; Iexpression-3OC ) Istatement
.s2
It is equivalent to
.s1
	expression-1C ;I
	Cwhile ( Iexpression-2C ) {
		Istatement
		expression-3C ;
	C}I
.s2
in the absence of
.CW continue
or
.CW break
statements.
Thus (just as in C), the first expression is an initialization,
the second a test for starting and continuing the loop, and the third
a re-initialization for subsequent travels around the loop.
.NH 2
.CW case
statement
.PP
The
.CW case
statement transfers control to one of several places
depending on the value of an expression:
.s1
	labelO  Ccase IexpressionC { Iqual-statement-sequenceC }I
.s2
The expression must have type
.CW int ,
.CW big
or
.CW string .
The
.CW case
statement is followed by sequence of
qualified statements, which are statements labeled by
expressions or expression ranges:
.s1
qual-statement-sequence:
	qual-listC =>I
	qual-statement-sequence qual-listC =>I
	qual-statement-sequence statement
	qual-statement-sequence declaration

qual-list:
	qualifier
	qual-listC or Iqualifier

qualifier:
	expression
	expressionC to Iexpression
	C*I
.s2
A
.I qual-statement-sequence
is a sequence of
statements and declarations, each of which
is preceded by one or more qualifiers.
Syntactically, the qualifiers are
expressions, expression ranges with
.CW to ,
or
.CW * .
If the expression mentioned after
.CW case
has
.CW int
or
.CW big
type,
all the expressions appearing in the qualifiers
must evaluate to integer constants of the same type (§8.5).
If the expression has
.CW string
type, all the qualifiers must be
string constants.
.PP
The
.CW case
statement is executed by comparing
the expression at its head with the constants
in the qualifiers.
The test is for equality in the case
of simple constant qualifiers;
in range qualifiers, the test determines
whether the expression is greater than or
equal to the first constant and less than
or equal to the second.
.PP
None of the ranges or constants may overlap.
If no qualifier is selected and
there is a
.CW *
qualifier,
then that qualifier is selected.
.PP
Once a qualifier is selected, control passes
to the set of statements headed by that
qualifier.
When control reaches the end of that set
of statements, control passes to the end
of the
.CW case
statement.
If no qualifier is selected, the
.CW case
statement is skipped.
.PP
Each qualifier and the statements following it
up to the next qualifier together form a separate
scope, like a block; declarations within this scope
disappear at the next qualifier (or at the end of
the statement.)
.PP
As an example, this fragment separates small numbers
by the initial letter of their spelling:
.P1
	case i {
	1 or 8 =>
		sys->print("Begins with a vowel\en)";
	0 or 2 to 7 or 9 =>
		sys->print("Begins with a consonant\en");
	* =>
		sys->print("Sorry, didn't understand\en");
	}
.P2	
.NH 2
.CW alt
statement
.PP
The
.CW alt
statement transfers control to one of several groups
of statements depending on the readiness of communication
channels.
Its syntax resembles that of
.CW case :
.s1
	labelO  Calt { Iqual-statement-sequenceC }I
.s2
However, the qualifiers take a form different
from those of
.CW case .
In
.CW alt ,
each qualifier must be a
.CW * ,
or an expression containing a communication
operator
.CW <-
on a channel;
the operator may specify either sending or receiving.
For example,
.P1
	outchan := chan of string;
	inchan := chan of int;
	alt {
	i := <-inchan =>
		sys->print("Received %d\en", i);

	outchan <- = "message" =>
		sys->print("Sent the message\en");
	}
.P2
The
.CW alt
statement is executed by testing each of
the channels mentioned in the
.I qual-list
expressions for ability to send or receive,
depending on the operator;
if none is ready, the program blocks
until at least one is ready.
Then a random choice from the ready channels is selected
and control passes to the associated set
of statements.
.PP
If a qualifier of the form
.CW *
is present, then the statement does not block;
if no channel is ready the statements associated with
.CW *
are executed.
.PP
If two communication operators are present
in the same qualifier expression, only the leftmost one is
tested by
.CW alt .
If two or more
.CW alt
statements referring to the same receive (or send)
channel are executed in different
threads, the requests are queued;
when the channel becomes unblocked, the thread
that executed
.CW alt
first is activated.
.PP
As with
.CW case ,
each qualifier and the statements following it
up to the next qualifier together form a separate
scope, like a block; declarations within this scope
disappear at the next qualifier (or at the end of
the statement.)
Thus, in the example above, the scope of
.CW i
in the arm
.P1
		i := <-inchan =>
			sys->print("Received %d\en", i);
.P2
is restricted to these two lines.
.PP
As mentioned in the specification
of the channel receive operator
.CW <-
in §8.2.8, that operator can take an array of channels as an argument.
This notation serves as a kind of simplified
.CW alt
in which all the channels have the same type
and are treated similarly.
In this variant,
the value of the communication expression is a tuple
containing the index of the
channel over which a communication was received and
the value received.
For example, in
.P1
	a: array [2] of chan of string;
	a[0] = chan of string;
	a[1] = chan of string;
	. . .
	(i, s) := <- a;
	# s has now has the string from channel a[i]
.P2
the
.CW <-
operator waits until at least one of the
members of
.CW a
is ready, selects one of them at random,
and returns the index and the transmitted string
as a tuple.
.PP
During execution of an
.CW alt ,
the expressions in the qualifiers are evaluated in an undefined
order, and in particular subexpressions may be evaluated before
the channels are tested for readiness.
Therefore qualifying expressions should not invoke side effects,
and should avoid subparts that might delay execution.
For example, in the qualifiers
.P1
	ch <- = getchar() =>	# Bad idea
	ich <- = next++ =>	# Bad idea
.P2
.CW getchar()
may be called early in the elaboration of the
.CW alt
statement; if it delays, the entire
.CW alt
may wait.
Similarly, the
.CW next++
expression may be evaluated before testing the readiness of
.CW ich .
.NH 2
.CW pick
statement
.PP
The
.CW pick
statement transfers control to one of several groups of statements
depending upon the resulting variant type of a
.CW pick
.CW adt
expression. The syntax resembles that of
.CW case :
.s1
	labelO  Cpick IidentifierC := IexpressionC { Ipqual-statement-sequenceC }I
.s2
The expression must have type
.CW ref
.CW adt
and the
.CW adt
must be a
.CW pick
.CW adt .
The
.CW pick
statement is followed by a sequence of qualified statements, which are
statements labeled by the
.CW pick
variant names:
.s1
pqual-statement-sequence:
	pqual-listC =>I
	pqual-statement-sequence pqual-listC =>I
	pqual-statement-sequence statement
	pqual-statement-sequence declaration

pqual-list:
	pqualifier
	pqual-listC or Ipqualifier

pqualifier:
	identifier
	C*I
.s2
A
.I pqual-statement-sequence
is a sequence of statements and declarations, each of which
is preceded by one or more qualifiers.
Syntactically, the qualifiers are identifiers, identifier lists (constructed with
.CW or ),
or
.CW * .
The identifiers must be names of the variant types of the
.CW pick
.CW adt .
The
.CW pick
statement is executed by comparing the variant type of the
.CW pick
.CW adt
referenced by the expression at its head with the variant type names in the qualifiers.
The matching qualifier is selected.
None of the variant type names may appear more than once.
If no qualifier is selected and there is a
.CW *
qualifier, then that qualifier is selected.
.PP
Once a qualifier is selected, control passes
to the set of statements headed by that qualifier.
When control reaches the end of that set of statements,
control passes to the end of the
.CW pick
statement.
If no qualifier is selected, the
.CW pick
statement is skipped.
.PP
Each qualifier and the statements following it
up to the next qualifier together form a separate
scope, like a block; declarations within this scope
disappear at the next qualifier (or at the end of
the statement.)
.PP
The
.I identifier
and
.I expression
given in the
.CW pick
statement are used to bind a new variable to a
.CW pick
.CW adt
reference expression, and within the statements associated with the
selected qualifier the variable can be used as if it were of the corresponding
variant type.
.PP
As an example, given a
.CW pick
.CW adt
of the following form:
.P1
	Constant: adt {
		name: string;
		pick {
			Str or Pstring =>
				s: string;
			Real =>
				r: real;
		}
	};
.P2
the following function could be used to print out the value of
an expression of type
.CW "ref Constant" :
.P1
	printconst(c: ref Constant)
	{
		sys->print("%s: ", c.name);
		pick x := c {
		Str =>
			sys->print("%s\en", x.s);
		Pstring =>
			sys->print("[%s]\en", x.s);
		Real =>
			sys->print("%f\en", x.r);
		};
	}
.P2
.NH 2
.CW break
statement
.PP
The
.CW break
statement
.s1
	Cbreak IidentifierO C;I
.s2
terminates execution of
.CW while ,
.CW do ,
.CW for ,
.CW case ,
.CW alt ,
and
.CW pick
statements.
Execution of
.CW break
with no identifier
transfers control to
the statement after the innermost
.CW while ,
.CW do ,
.CW for ,
.CW case ,
.CW alt ,
or
.CW pick
statement in which it appears as a substatement.
Execution of
.CW break
with an identifier
transfers control to the next statement after the unique enclosing
.CW while ,
.CW do ,
.CW for ,
.CW case ,
.CW alt ,
or
.CW pick
labeled with that identifier.
.NH 2
.CW continue
statement
.PP
The
.CW continue
statement
.s1
	Ccontinue IidentifierO C;I
.s2
restarts execution of
.CW while ,
.CW do ,
and
.CW for
statements.
Execution of
.CW continue
with no identifier
transfers control to the end of
the innermost
.CW while ,
.CW do ,
or
.CW for
statement in which the
.CW continue
appears as a substatement.
The expression that controls the loop is tested
and if it succeeds, execution continues in the loop.
The initialization portion of
.CW for
is not redone.
.PP
Similarly, execution of
.CW continue
with an identifier transfers control to the end of the enclosing
.CW while ,
.CW do ,
or
.CW for
labeled with the same identifier.
.NH 2
.CW return
statement
.PP
The
.CW return
statement,
.s1
	Creturn IexpressionOC ;I
.s2
returns control to the caller of a function.
If the function returns a value (that is, if its definition
and declaration mention a return type),
the expression must be given and it must have the same type that the
function returns.
If the function returns no value, the expression
must generally be omitted.
However, if a function returns no value, and its
last action before returning is to call
another function with no value, then it may
use a special form of
.CW return
that names the function being called.
For example,
.P1
	f, g: fn(a: int);
	f(a: int) {
		. . .
		return g(a+1);
	}
.P2
is permitted.
Its effect is the same as
.P1
	f(a: int) {
		. . .
		g(a+1);
		return;
	}
.P2
This
.I "ad hoc
syntax offers the compiler a cheap opportunity to recognize
tail-recursion.
.PP
Running off the end of a function is equivalent to
.CW return
with no expression.
.NH 2
.CW spawn
statement
.PP
The
.CW spawn
statement creates a new thread of control.
It has the form
.s1
	Cspawn ItermC ( Iexpression-listOC ) ;I
.s2
The term and expression-list are taken to be
a function call.
Execution of
.CW spawn
creates an asynchronous, independent thread
of control, which calls the function in the new thread context.
This function may access the accessible objects
in the spawning thread; the two threads share
a common memory space.
These accessible objects include the data global to
the current module and reference data passed to the
spawned function.
Threads are preemptively scheduled, so that
changes to objects used in common between
threads may occur at any time.
The Limbo language provides no explicit synchronization
primitives; §12.3 shows examples of how to use channel
communication to control concurrency.
.NH 2
.CW exit
statement
.PP
The
.CW exit
statement
.s1
	Cexit ;I
.s2
terminates a thread and frees any resources
belonging exclusively to it.
.NH 2
.CW raise
statement
.PP
The
.CW raise
statement
.s1
	Craise IexpressionOC ;I
.s2
raises an exception in a thread.
The
.I expression
is either a string describing the failure, or an exception name and its parameter values, if any.
If an expression is not given, the
.CW raise
statement must appear in the body of an exception handler; it raises the currently active exception.
.NH 2
Exception handler
.PP
Various errors in a Limbo program can be detected only at run-time.
These include programming errors such as an attempt to index outside the bounds of an array,
system errors such as exhausting memory, and user-defined exceptions
declared at compile-time by exception declarations and caused at run-time by the
.CW raise
statement.
A group of statements can have an associated exception handler:
.s1
	C{ IstatementsC } exceptionI identifierOC{ Iqual-statement-sequenceC }I
.s2
The first run-time exception raised by any of the
.I statements ,
or functions they call,
that is not handled by an exception handler enclosing the statement raising the exception
will terminate execution of the
.I statements
at that point, and transfer control to the clause in the sequence of qualified statements
that matches the exception.
An exception represented by a string is matched by a qualifier that is either the same
string value, or a prefix of it followed by
.CW * .
The optional identifier following
.CW exception
is set to the value of the exception string for the execution of the qualified statement.
If execution of the qualified statement completes, control passes to the statement following
the exception-handling statement.
.PP
A qualified statement labeled by a user-defined exception name matches that exception.
If the exception has parameters, the identifier following
.CW exception
will be be declared and initialized as a tuple of the parameter values for the scope
of the qualified statement, allowing the values to be recovered by tuple assigment.
.PP
The qualifier
.CW *
matches any string or user-defined exception.
An exception that is raised and not successfully handled by a thread will terminate the thread.
.NH
Referring to modules;
.CW import
.PP
As discussed above, modules present
constants, functions, and types
in their interface.
Their names may be the same as names
in other modules or of local objects or types within
a module that uses another.
Name clashes are avoided because references
to the entities presented by a module are
qualified by the module type name or an object
of that module type.
.PP
For example,
after the module and variable declarations
.P1
	M: module {
		One: con 1;
		Thing: adt {
			t: int;
			f: fn();
		};
		g: fn();
	};
	m: M;
.P2
the name
.CW One
refers to the constant defined in
module
.CW M
only in the contexts
.CW M->One
or
.CW m->One ;
the name
.CW Thing
as the particular data type
associated with the
.CW M
module can be referred to only in contexts
like
.P1
	th1: M->Thing;
	th2: m->Thing;
.P2
Finally, to call a function defined either as a top-level
member of the module, or as a member of one of its
.CW adt ,
it is necessary to declare, and also dynamically initialize using
.CW load ,
a handle for the module.
Then calls of the form
.P1
	m->g();
	m->th1.f();
.P2
become appropriate.
It is possible to use just the type name of a module to qualify
its constants and types because constants and types can be understood
without having the code and data present.
Calling a function declared by a module or one of its
.CW adt
requires loading the module.
.PP
The
.CW import
declaration
.s1
	Iidentifier-listC : import Iidentifier C;I
.s2
lifts the identifiers in the
.I identifier-list
into the scope in which
.CW import
appears, so that they are usable without a qualifier.
The identifier after the
.CW import
keyword is either
a module identifier, or an identifier declared as having
that type.
The initial list of identifiers specifies those
constants,
types,
and functions of the module whose names are promoted.
In the case of constants and types,
.CW import
merely makes their names accessible without using a qualifier.
In the example above, if the
.CW module
declaration above had been followed by
.P1
	One, Thing: import M;
.P2
then one could refer to just
.CW One
instead of
.CW M->One ;
similarly an object could be declared like
.P1
	th: Thing;
.P2
For functions, and also
.CW adt
with functions as members,
.CW import
must specify a module
variable (as opposed to a module identifier).
Each imported name is associated with the specified module
variable, and the current value of this module variable
controls which instance of the module will
be called.
For example, after
.P1
	g, Thing: import m;
.P2
then
.P1
	g();
.P2
is equivalent to
.P1
	m->g();
.P2
and
.P1
	th: Thing;
	th.f();
.P2
is equivalent to
.P1
	th: M->Thing;
	m->th.f();
.P2
When the module declaration for the module being
implemented is encountered, an implicit
.CW import
of all the names of the module is executed.
That is, given
.P1
	implement Mod;
	. . .
	Mod: module {
		. . .
	};
.P2
the constants and types of
.CW Mod
are accessed as if they had been imported;
the functions declared in
.CW Mod
are imported as well, and refer dynamically to the
current instance of the module being implemented.
.NH
Scope
.PP
The scope of an identifier is the lexical range of
a program throughout which the identifier means a particular
type of, or instance of, an object.
The same identifier may be associated with several
different objects in different parts of the same program.
.PP
The names of members of an
.CW adt
occupy a separate, nonconflicting space from other identifiers;
they are declared in a syntactically distinct position,
and are always used in a distinguishable way, namely
after the
.CW .
selection operator.
Although the same scope rules apply to
.CW adt
members as to other identifiers, their names may
coincide with other entities in the same scope.
.PP
Similarly, the names of constants, functions, and
.CW adt
appearing
within a
.CW module
declaration are ordinarily qualified either with
the name of the module or with a module variable
using the
.CW ->
notation.
As discussed above, the
.CW import
declaration lifts these names into the current scope.
.PP
Identifiers declared in a top-declaration
(§5) have scope that lasts from the
declaration throughout the remainder of the
file in which it occurs, unless it is overridden
by a redeclaration of that name within an inner
scope.
Each function definition, and each block
within a function,
introduces a new scope.
A name declared within the block or function
(including a formal argument name of a function)
has a scope that begins
at the completion of its declaration and lasts until
the end of the block or function.
If an already-declared identifier is redeclared within
such an inner scope, the declaration previously in
force is used in any initialization expression
that is part of the new declaration.
.PP
As discussed above, within
.CW case
.CW alt
and
.CW pick ,
each qualifier
and the statements following it form an inner
scope just like a block.
.PP
The scope of a label is restricted to the
labeled statement,
and label names may coincide with those of other
entities in the same scope.
.NH 2
Forward referencing
.PP
In general, names must be declared before they are used.
.PP
The first exception to this rule is that a
function local to a module need not have a
declaration at all; it is sufficient to give
its definition, and that definition may appear anywhere
in the module.
.PP
The general rule implies that no
.CW adt
may contain, as a member, an
.CW adt
not previously declared (including an instance of itself).
A second exception to this rule applies to
.CW ref
.CW adt
types.
An
.CW adt
may contain a member whose type is a
.CW ref
to itself, or to another
.CW adt
even if the second
.CW adt
has not yet been declared.
Unless a special notation is used, such
references are restricted:
all mutual or self references among
.CW adt
are checked statically throughout all the
.CW adt
visible in a module to determine which
members refer to other
.CW adt .
Any member of an
.CW adt
of
.CW ref
.CW adt
type that refers directly, or indirectly through a chain of references,
back to its own underlying type may not be assigned to individually;
it can gain a value only by an assignment to the
.CW adt
as a whole.
For example, in
.P1
	Tree: adt {
		l: ref Tree;
		r: ref Tree;
		t: ref Ntree;
	};
	Ntree: adt {
		t: ref Tree;
	};

	t1 := Tree(nil, nil, nil);	# OK
	t2 := Tree(ref t1, ref t1, nil);	# OK
	t1 = Tree(ref t1, ref t2, nil);	# OK
	t1.l = ... ;	# not OK

	nt := ref Ntree(nil);	# OK
	nt.t = ...	# not OK
.P2
the first three assignments are correct, but
any assignment to
.CW t1.l
is forbidden, because it is self-referential.
The situation is the same with the mutually
referential fields of the
.CW Tree
and
.CW Ntree
.CW adt .
.PP
These restrictions suffice
to prevent the creation of circular data structures.
Limbo implementations guarantee to
destroy all data objects not involved in such circularity
immediately after they become non-referenced by active
tasks, whether because
their names go out of scope or because they are assigned new values.
This property has visible effect because certain system resources,
like windows and file descriptors, can be seen outside the program.
In particular, if a reference to such a resource is held only within an
.CW adt ,
then that resource too is destroyed when the
.CW adt
is.
.PP
The default rules are burdensome because they impede the construction even
of harmless structures like trees.
Therefore an escape is provided: using the word
.CW cyclic
before the type in an
.CW adt
member removes the circular-reference restriction for that member.
For example,
.P1
	Tree: adt {
		l: cyclic ref Tree;
		r: cyclic ref Tree;
		t: ref Ntree;
	};
	Ntree: adt {
		t: cyclic ref Tree;
	};

	t1 := Tree(nil, nil, nil);	# OK
	t2 := Tree(ref t1, ref t1, nil);	# OK
	t1 = Tree(ref t1, ref t2, nil);	# OK
	t1.l = ... ;	#  OK now

	nt := ref Ntree(nil);	# OK
	nt.t = ...	# OK now
.P2
With the use of
.CW cyclic ,
circular data structures can be created.
When they become unreferenced except by themselves, they will
be garbage-collected eventually, but not instantly.
.NH 2
Type equality and compatibility
.PP
In an assignment and in passing an actual argument to a function,
the types of the target and the expression being assigned or
passed must be equal (with certain exceptions, e.g. assignment of
.CW nil
to a reference type).
When a function is defined, its type must be equal to the type
of a function with the same name if one is in scope.
Type equality is determined as follows.
.PP
Two basic types are equal if and only if they are identical.
.PP
Two tuple types are equal if and only if they are composed
of equal types in the same order.
.PP
Two array types are equal if and only if they are arrays
of equal types.
The size of an array is not part of its type.
.PP
Two list types are equal if and only if they are composed
of equal types.
.PP
Two channel types are equal if and only if they transmit
equal types.
.PP
Two
.CW adt
types are equal if and only if their data members
have the same names and correspondingly
equal types, including any
.CW cyclic
attribute.
The order of member declaration is insignificant, and
constant and function members of an
.CW adt
do not enter into the comparison,
nor does the name of the
.CW adt
type itself.
In particular, with the declarations
.P1
	A: adt { x: ref B; };
	B: adt { x: ref A; };
.P2
the types
.CW A
and
.CW B
are equal.
.PP
Two
.CW ref
.CW adt
types are equal if and only if they are references to equal
.CW adt
types.
.PP
Two module types are equal if and only if their data and function members
have the same names and correspondingly equal types; the order
of their mention is insignificant.
Constant members and type members do not enter into the comparison.
.PP
Two function types are equal if and only if their return
values have the same type
and their argument lists have correspondingly equal types.
Any
.CW self
attributes given to arguments much match.
Names given to arguments do not enter into the comparison.
.PP
A type name has the same type as the type from
which it was constructed.
.PP
When a module is loaded, the module stored
in the file system must have a type that is
.I compatible
with the type mentioned in the
.CW load
expression.
The type of the stored module
type is compatible with the mentioned type if and only if
all data members of the two types are equal in name and type,
and all
.CW adt
or functions actually mentioned by the program executing
.CW load
have names and types equal to corresponding members of
the stored module.
.NH
Examples
.PP
Because Limbo was designed for the Inferno environment, several
of these examples consist of simplified versions of already simple
Inferno applications in a prototype Inferno implementation.
Some appreciation for the resources available in this environment
should become evident, but its full description is available
elsewhere;
the discussion here will focus on language features.
However, several of the programs use facilities
from the module
.CW Sys ,
which provides an interface to a file system and its methods
resembling those of Unix or Plan 9,
as well as other useful library facilities.
.PP
Some of the programs are annotated with line numbers;
they are there only for descriptive purposes.
.NH 2
A simple command interpreter module
.PP
This version of a shell program reads from a keyboard and
executes `commands' typed by the user.
Its own interface has the type of a
.CW Command
module, and that is the type of the things it executes.
In particular, it can call modules like the
.CW hello
example at the beginning of the paper.
.P1
1	implement Command;

2	include "sys.m";
3	include "draw.m";

4	sys: Sys;
5	stdin: ref Sys->FD;

6	Command: module
7	{
8		init: fn(nil: ref Draw->Context, nil: list of string);
9	};
.P2
After the boilerplate on lines 1-3, the variables
.CW sys
and
.CW stdin
are declared on lines 4 and 5.
The I/O operations of the
.CW Sys
module use the
.CW ref
.CW FD
type to refer to open files.
.P1
10	init(ctx: ref Draw->Context, nil: list of string)
11	{
12
13
14		buf := array[256] of byte;

15		sys = load Sys Sys->PATH;
16		stdin = sys->fildes(0);

17		for(;;) {
18			sys->print("$ ");
19			n := sys->read(stdin, buf, len buf);
20			if(n <= 0)
21				break;
22			(nw, arg) :=
			   sys->tokenize(string buf[0:n], " \et\en");
23			if(nw != 0)
24				exec(ctx, arg);
25		}
26	}
.P2
Line 10: conventionally, stand-alone modules are started
by calling their
.CW init
functions.
The
.CW Command
module follows this convention.
The arguments are presented as a list of strings.
In this simple example, the command interpreter itself
ignores its argument, so it need not be given a name.
.PP
Local variables are declared on lines 12-14; line 15
loads the
.CW Sys
module and stores a handle for it in the variable
.CW sys .
Line 16 creates an
.CW FD
for the standard input by calling the
.CW fildes
function of the
.CW Sys
module using the
.CW ->
operator; the notation
.CW modhandle->func(...)
specifies a call to the function named
.CW func
in the module currently referred to by
.CW modhandle .
(In general there can be several modules of the same type and name
active, and there can also be unrelated modules containing identically
named functions.
The
.CW import
declaration, described in §6.6 above, can be used to abbreviate
the references when names do not clash.)
.PP
The loop on lines 17-25 prints a prompt (line 18), reads a line from
the standard input (line 19), parses it into tokens (line 22), and
executes the command.
.PP
The function call
.CW sys->tokenize
is worth discussing as an example of style.
It takes two strings as arguments.
The characters in the second string are interpreted as separators
of tokens in the first string.
It returns a tuple whose first member is the number of
tokens found, and whose second is a list of strings
containing the tokens found: its declaration is
.P1
	tokenize: fn (s: string, sep: string): (int, list of string);
.P2
In the example, the second argument is
\f(CW" \et\en"\fP,
so that the routine returns the number of, and a list of,
`words' separated by blanks, tabs, and new-lines.
The free use of strings, lists, and tuple-returning
functions is common in Limbo.
.PP
The
.CW sys->read
routine gathers an array of bytes into
.CW buf .
Thus the expression for the first argument of
.CW sys->tokenize
converts this array to a string by slicing the
array with
.CW [0:n] ,
using the actual number of bytes
gathered by the
.CW read ,
and using a cast.
.PP
At lines 23-24, if there were any words found,
.CW exec
is called:
.P1
27	exec(ctx: ref Draw->Context, args: list of string)
28	{
29		c: Command;
30		cmd, file: string;

31		cmd = hd args;

32		file = cmd + ".dis";
33		c = load Command file;
34		if(c == nil)
35			c = load Command "/dis/"+file;

36		if(c == nil) {
37			sys->print("%s: not found\en", cmd);
38			return;
39		}
40		c->init(ctx, args);
41	}
.P2
On lines 31 and 32 of
.CW exec ,
.CW cmd
is set to the first of the words in the argument list,
and the string
.CW .dis
is concatenated to it (to account for the fact that Limbo
object program files are conventionally named using this suffix).
On line 33 an attempt is made to load the named module
from the derived file name; it will fail if the file
does not exist.
The attempt will succeed,
and a non-nil handle assigned to
.CW c ,
if the file is found, and if
the module stored in that file does in fact implement the
.CW Command
module type.
In case this fails, lines 34-35 make another attempt, after prefixing
.CW /dis/
to the file name.
.PP
If either attempt to get a handle to the named module
succeeds,
.CW c
will contain a valid handle to it; line 40 calls its
.CW init
function, passing it the whole argument list.
When it returns, the
.CW exec
function returns, and the main loop resumes.
.NH 2
Infrared remote control
.PP
This example shows two instances of a module
for interfacing to a TV remote control; one
is for the real remote, which in this case
is connected to a serial port on a set-top
box, and the other is simulated for testing
programs running on a regular operating
system.
The techniques of special interest are the
dynamic use of modules and the communication
using a channel.
.PP
The module is used by creating a channel and passing
it to the module's
.CW init
function,
which returns a success/error indicator and starts an
asynchronous process to read the remote control.
The user of the module executes a receive
on the channel whenever it wishes to accept
a button-push.
.PP
The (abridged) module declaration is
.P1
Ir: module
{
	# Codes buttons on IR remote control
	Zero:	con 0;
	One:	con 1;
	. . .
	Mute:	con 23;
	Error:	con 9999;

	init: fn(chan of int): int;
	PATH: con "/dis/ir.dis";
	SIMPATH: con "/dis/irsim.h";
};
.P2
The implementation for the `real' remote control is
.P1
implement Ir;

include "ir.m";
include "sys.m";
FD, Dir: import Sys;

sys: Sys;

init(keys: chan of int): int
{
	cfd, dfd: ref FD;

	sys = load Sys Sys->PATH;

	cfd = sys->open("/dev/eia1ctl", sys->OWRITE);
	if(cfd == nil)
		return -1;
	sys->fprint(cfd, "b9600");

	dfd = sys->open("/dev/eia1", sys->OREAD);
	cfd = nil;

	spawn reader(keys, dfd);
	return 0;
}
.P2
The
.CW init
routine accepts a
.CW chan
argument; it will be used by the module to
send codes for the buttons pressed by the user.
In this routine, the calls to
.CW sys->open
and
.CW sys->fprint
open and set up the device data and control files
.CW /dev/eia1
and
.CW /dev/eia1ctl
used to communicate with the device itself.
The important step is at the end: the
.CW spawn
statement creates a new,
asynchronous task to read the device, using a routine
that is passed the communications channel and the
FD for the device:
.P1
reader(keys: chan of int, dfd: ref FD)
{
	n, ta, tb: int;
	dir: Dir;
	b1:= array[1] of byte;
	b2:= array[1] of byte;

	# find the number of bytes already
	# queued and flush that many
	(n, dir) = sys->fstat(dfd);
	if(n >= 0 && dir.length > 0) {
		while(dir.length) {
			n = sys->read(dfd,
			   array[dir.length] of byte,
			   dir.length);
			if(n < 0)
				break;
			dir.length -= n;
		}
	}
.P2
.P1
loop:	for(;;) {
		n = sys->read(dfd, b1, len b1);
		if(n <= 0)
			break;
		ta = sys->millisec();
		# Button pushes are pairs of characters
		# that arrive closer together than
		# 200 ms.  Longer than that is likely
		# to be noise.
		for(;;) {
			n = sys->read(dfd, b2, 1);
			if(n <= 0)
				break loop;
			tb = sys->millisec();
			if(tb - ta <= 200)
				break;
			ta = tb;
			b1[0] = b2[0];
		}
		# map the character pair; the significant
		# bits are the lowest 5.
		case ((int b1[0]&16r1f)<<5) | (int b2[0]&16r1f) {
		975 =>	n = Ir->Zero;
		479 =>	n = Ir->One;
		. . .
		791 =>	n = Ir->Mute;
		* =>	n = Ir->Error;
		}
		# found a button-push; send the value
		keys <-= n;
	}
	keys <-= Ir->Error;
}
.P2
The code in the middle is related to noise-filtering
and is uninteresting in detail except as it illustrates
some of the methods provided by the
.CW Sys
module; the crucial actions are found at the bottom,
where the routine sends either
a true button-push or an error code over the channel to
the module's client.
.PP
Here is another implementation of the same interface.
Its
.CW init
function performs the same kind of initialization
as the other version, but using the operating system's
keyboard files
.CW /dev/cons
and
.CW /dev/consctl .
In the Inferno environment, operations corresponding to the Unix
`stty' primitive are accomplished by writing messages to
a control file associated with the file that handles the data.
.P1
implement Ir;

include "ir.m";
include "sys.m";
FD: import Sys;

sys: Sys;
cctlfd: ref FD;

init(keys: chan of int): int
{
	dfd: ref FD;

	sys = load Sys Sys->PATH;

	cctlfd = sys->open("/dev/consctl", sys->OWRITE);
	if(cctlfd == nil)
		return -1;
	sys->write(cctlfd, array of byte "rawon", 5);

	dfd = sys->open("/dev/cons", sys->OREAD);
	if(dfd == nil)
		return -1;

	spawn reader(keys, dfd);
	return 0;
}
.P2
A fine point: the variable
.CW cctlfd
that contains the FD for the control device is
declared external to the
init function, even though it appears to be used
only inside it.
Programming cleanliness suggests that
its declaration be moved inside, but here that
won't work;
device control files
in Inferno retain settings like `raw mode' only
while they remain open.
If
.CW cctlfd
were declared inside
.CW init ,
then returning from
.CW init
would destroy the last reference to the FD for the control file,
and the device would be closed automatically.
.PP
The reader function for this module has the same structure as the first
example, but doesn't have to worry about a noisy infrared detector:
.P1
reader(keys: chan of int, dfd: ref FD)
{
	n: int;
	b:= array[1] of byte;

	for(;;) {
		n = sys->read(dfd, b, 1);
		if(n != 1)
			break;
		case int b[0] {
		'0' =>	n = Ir->Zero;
		'1' =>	n = Ir->One;
		. . .
		16r7f =>	n = Ir->Mute;
		* =>	n = Ir->Error;
		}
		keys <-= n;
	}
	keys <-= Ir->Error;
}
.P2
The following module can be used to test the above code.
It simply prints the name of the button that was pressed.
.P1
implement Irtest;

include "sys.m";
include "draw.m";
FD: import Sys;
include "ir.m";

Irtest: module
{
	init:  fn(nil: ref Draw->Context, nil: list of string);
};
ir: Ir;
sys: Sys;
.P2
.P1
init(nil: ref Draw->Context, nil: list of string)
{
	c: int;
	stderr: ref FD;
	irchan := chan of int;

	sys = load Sys Sys->PATH;
	stderr = sys->fildes(2);

	# If the real IR remote application can
	# be found, use it, otherwise use the simulator:
	ir = load Ir Ir->PATH;
	if(ir == nil)
		ir = load Ir Ir->SIMPATH;
	if(ir == nil) {
		# %r format code means the last system error string
		sys->fprint(stderr, "load ir: %r\en");
		return;
	}
	if(ir->init(irchan) != 0) {
		sys->fprint(stderr, "Ir.init: %r\en");
		return;
	}
	names := array[] of {
		"Zero",
		"One",
		. . .
		"Mute",
	};
	for(;;) {
		c = <-irchan;
		if(c == ir->Error)
			sys->print("Error %d\en", c);
		else
			sys->print("%s\en", names[c]);
	}
}
.P2
Finally, here is a snippet from a movie application that
uses the IR module; it demonstrates how
.CW alt
is useful for dealing with multiple events.
This is only one of the functions of the
movie module, so not everything is defined.
It uses the
.CW Mpeg
module, which actually
copies the MPEG data stream to the screen
asynchronously.
Its
.CW play
function takes, as one of its arguments,
a channel;
before starting to play it writes a
string on the channel.
An empty string indicates success at
locating the movie; a non-empty
string contains an error message.
When it finishes, it writes another string.
.P1
movie(entry: ref Dbinfo, cc: chan of int)
{
	i: int;
	m: Mpeg;
	b: ref Image;

	m = load Mpeg Mpeg->PATH;
	if (m == nil)
		return;
	# make a place on the screen
	w := screen.window(screen.image.r);

	mr := chan of string;
	s := m->play(w, 1, w.r, entry.movie, mr);
	if(s != "")
		return;
	# wait for the end of the movie
	# while watching for button pushes
	for(;;) {
		alt {
		<-mr =>
			return;
		i = <-cc =>
			case i {
			Ir->Select =>
				m->ctl("stop");
			Ir->Up or Ir->Dn =>
				m->ctl("pause");
			}
		}
	}
}
.P2
.NH 2
Monitors
.PP
Statically allocated storage within a module is accessible to
all the functions of that module,
and there is no explicit mechanism in Limbo for synchronizing
concurrent updates to this storage from several tasks.
However, it is straightforward to build a variety of concurrency-control
mechanisms by using channel communications.
.PP
An example is a module that implements a
.CW Monitor
abstract data type.
Each instance of
.CW Monitor
has a
.CW lock
and an
.CW unlock
operation;
calling
.CW lock
delays if another task holds the lock; calling
.CW unlock
releases the lock and enables any other task attempting
to execute
.CW lock .
.P1
implement Monitors;

Monitors: module
{
	Monitor: adt {
		create: fn(): Monitor;
		lock: fn(m: self Monitor);
		unlock: fn(m: self Monitor);
		ch: chan of int;
	};
};
.P2
.P1
Monitor.create(): Monitor
{
	m := Monitor(chan of int);
	spawn lockproc(m.ch);
	return m;
}
.P2
.P1
Monitor.lock(m: self Monitor)
{
	m.ch <- = 0;
}
.P2
.P1
Monitor.unlock(m: self Monitor)
{
	<- m.ch;
}
.P2
.P1
lockproc(ch: chan of int)
{
	for (;;) {
		<- ch;	# wait for someone to lock
		ch <- = 0; # wait for someone to unlock
	}
}
.P2
It would be used like this:
.P1
mp: Mon;
Monitor: import mp;
mp = load Mon "...";
l := Monitor.create();
\. . .
l.lock();
# region of code to be protected;
# only one thread can execute here at once.
l.unlock();
.P2
The
.CW create
method of
.CW Monitor
allocates an instance of a
.CW Monitor
containing an initialized channel.
It also creates a thread executed in the
.CW lockproc
routine, which repeatedly reads from the channel,
then writes on it.
The values transmitted over the channel are of no
interest; it is the pure fact of communication that is put to use.
The
.CW lock
routine sends a message; in the idle state, the
.CW lockproc
thread reads it and the sender proceeds.
Meanwhile,
.CW lockproc
tries to send a message over the same channel.
If another thread attempts to
.CW lock ,
there is no reader for the channel, and so its transmission will block.
At some point, the thread that gained the lock
calls
.CW unlock ,
which receives from the channel.
Depending on timing, this reception enables execution of either
.CW lockproc
or one of the threads attempting to send via
.CW lock .
.PP
There is a simpler implementation of
.CW Monitor ,
using a buffered channel.
The
.CW create
operation simply allocates a channel with a one-element buffer:
.P1
Monitor.create(): Monitor
{
	return Monitor(chan[1] of int);
}
.P2
The
.CW lock
and
.CW unlock
operations have the same implementation.
Because of the buffer, when a process locks an unlocked
.CW Monitor ,
the send succeeds but fills the channel.
Subsequent attempts to
.CW lock
will therefore block as long as the channel is full.
.CW Unlock
removes the value from the channel, making it empty,
and allowing another
.CW lock
to proceed.
The
.CW lockproc
is not needed.
Note that a program using the module would not need to be recompiled to
use the new implementation, because the module's signature and use
remains the same.
This is the implementation of the
.CW Lock
module in the Limbo library for Inferno.
.PP
Limbo channels are usually unbuffered:
a sender blocks until there
is a receiver, and processes synchronise at each communication.
Buffered channels are used sparingly in Limbo programs, typically to improve throughput or,
less often, in specialized ways as in the monitor example above.
.NH 2
Guarding sends and receives
.PP
In some applications, a process takes input from one channel,
and sends it on to another channel, possibly having transformed it.
In case the input and output processes run at different rates,
the process itself acts as a buffer, holding a queue of values internally.
If the input process were faster than the output process, the queue
would accumulate values faster than they are consumed, exhausting memory.
To prevent that, when the queue reaches a specified limit, the process should guard against
receiving from the input channel, but continue sending to the output channel.
Conversely, when the queue is empty, it should not attempt to send.
The
.CW alt
statement allows a process to choose between sending and receiving based on
which channels are ready, but the process must also account for the current state
of the queue.
This example shows a way to make a buffered
channel of strings from an unbuffered channel.
It is written as a module whose
.CW bufchan
function takes a
.CW chan
.CW of
.CW string
and a size as argument, and returns a new channel;
it creates an asynchronous task that accepts input from the argument
channel and saves up to
.CW size
strings, meanwhile trying to send them to its user.
.P1
implement Bufchan;
Bufchan: module {
	bufchan: fn(c: chan of string, size: int): chan of string;
};

xfer(oldchan, newchan: chan of string, size: int)
{
	temp := array[size] of string;
	fp := 0;        # first string in buffer
	n := 0;         # number of strings in buffer
	dummy := chan of string;
	sendch, recvch: chan of string;
	s: string;

	for (;;) {
		sendch = recvch = dummy;
		if (n > 0)
			sendch = newchan;
		if (n < size)
			recvch = oldchan;
		alt {
		s = <-recvch =>
			temp[(fp+n)%size] = s;
			n++;

		sendch <- = temp[fp] =>
			temp[fp++] = nil;
			n--;
			if (fp>=size)
				fp -= size;
		}
	}
}
.P2
.P1
bufchan(oldchan: chan of string, size: int): chan of string
{
	newchan := chan of string;
	spawn xfer(oldchan, newchan, size);
	return newchan;
}
.P2
The module is somewhat specialized, but it illustrates
useful programming techniques.
The most interesting occurs in
.CW xfer ,
which does the work.
The problem
.CW xfer
faces is that it doesn't want to receive input when its
buffer is full, nor to try to send when it has nothing to
transmit.
The solution here is to use a dummy channel
on which nothing is ever sent or received; in the
.CW alt
statement,
that channel substitutes for the real input channel
when the buffer is full, and for the output channel
when the buffer is empty.
.PP
The module could be used in the following way:
.P1
Bufchan: module {
	PATH: con "/dis/lib/bufchan.dis";
	bufchan: fn(c: chan of string, size: int): chan of string;
};
\. . .
bufc := load Bufchan Bufchan->PATH;
sourcech := chan of string;

# ... (here, hand off sourcech to a process that
#      reads strings from it and copies them to ch)
ch: chan of string = bufc->bufchan(sourcech, 10);
\. . .
s := <- ch;
\. . .
.P2
.NH 1
Syntax summary
.PP
This section summarizes the grammar of Limbo
above the lexical level; constants and identifiers
are left undefined.
.PP