Programming in Limbo


BYTE Magazine - October 1997 / Core Technologies / Programming in Limbo

This language allows for the easy writing of threaded programs with bidirectional communications.

By Larry Rau

Limbo is a new general-purpose programming language developed by Lucent Technologies for writing applications that run on the Inferno OS (see "Inferno: One Hot OS," June BYTE). Limbo uses attributes from well-known existing languages as well as adding a few twists of its own. It has several features that allow for the creation of very dynamic, concurrent applications.

Limbo bucks the current object-oriented programming (OOP) trend: It contains no language features that aid in the development of OO applications. I nstead, it's a procedural language that uses the concepts of modules with separate interfaces and implementations that allow developers to create well-structured applications. The Limbo language reference manual, along with the Limbo compilers, is available with the Inferno Development Kit on-line at http://www.lucent.com/inferno.

Language Features

C and Pascal programmers will find that Limbo syntax looks familiar. Limbo declarations are in the Pascal style of name/colon/type, and statements and expressions are generally similar to C's in both syntax and semantics. Unlike C, Limbo contains a rich set of built-in types and is strongly typed (both static and run-time). It's also very dynamic, uses garbage collection, and offers support for threads and communica tions.

Limbo contains the typical primitive types -- byte , int , big , and real . Unlike C, these primitives have well-defined sizes ( ints are 4 bytes, bigs are 8 bytes, and so on). This improves code portability across different architectures. More complex data types include arrays, strings, and the Abstract Data Type (ADT -- something between a C struct and a C++ class). Limbo also contains additional high-level structured types -- lists, tuples, modules, and chan (channels).

Arrays in Limbo are always created dynamically from memory in the heap and referred to via a reference. (References are much like C++ references for parameter passing. One of Limbo's advantages is that it does not support pointers.) Assigning an array, or passing it to a function as a parameter, passes a reference to the contents of the original array.

Along with the traditional array-index operations, Limbo also provides slicing. A slice is a subarray that's specified by an index range. A slice is a reference to the original array; therefore, if it's modified, so is the original array. The Limbo language reference manual provides details about various flexible forms of creating and manipulating arrays.

The ADT is Limbo's counterpart to the C++ class . As with C++, functions can be encapsulated with the type. However, neither inheritance nor polymorphic functions are supported. ADTs are value types; assigning an ADT results in a copy of the data contained in the original ADT. Limbo does not allow a programmer to manipulate the references themselves -- only the data referred to in the references.

Lists and Tuples

The Limbo list type allows for a sequence of like-typed items to be collected and manipulated. Limbo contains three list operators: hd , tl , and :: . The hd operator returns the head (i.e., first) item of the list. The tl operator returns the tail (i.e., the l ist of items following the head). The infix operator :: is used to construct lists. The following code fragment shows lists:

   stuff := 30 :: (20 :: (10 ::
     stuff));
  (head,tail) := (hd stuff, tl
     stuff);

This example contains a useful, yet uncommon, type called a tuple , which is an ordered collection of items -- essentially an unnamed record. Tuples in Limbo are first-class types and can be used as variables, function parameters, and function-return values.

A unique Limbo type is the chan (or channel ) type. Channels represent a synchronous bidirectional typed communications path between threads. Limbo offers a number of language features that use this very powerful type.

A communications operator ( <- ) sends and receives values along a channel. Limbo also provides an alt statement, which is similar in structure to a case statement. It allows for a set of channels to be given a fair chance for a send/re ceive operation to complete. This ensures that a single heavily used channel will not keep less frequently used channels from communicating in a timely manner.

Channels are simple to use. Once one is created, any thread that has a reference to it can read or write to it. When a thread writes to a channel, the thread blocks until a corresponding read takes place (likewise for thread reading). This feature allows a channel to be used as a means for synchronizing threads.

Limbo programs are organized into logical blocks called modules , which contain declaration and implementation files. A module declaration file contains the module's exported types, constants, and functions and defines the interface to the implementation. A module implementation file provides the actual code. A module implementation can have additional types, constants, data, and functions that are considered private.

Programs explicitly load modules at run time. When a module is loaded, it's assigned to a variable that is declared to have a type of a specific module; this assignment is protected via a run-time type check. This allows instances of modules to be passed into and out of functions, as well as stored. Furthermore, multiple instances of a module can be loaded; each instance maintains its own set of module data while sharing code.

Threads and Communications

Limbo provides a single, simple language element -- the spawn statement -- to support multithreaded programming. This statement accepts a single parameter, which provides a function that the new thread executes. In Limbo, threads are extremely lightweight and are intended to be treated as an inexpensive, primitive resource that an application can use to accomplish a task.

The aforementioned alt statement allows an application's thread to simultaneously operate on multiple channels. This simple statement is a powerful feature of the Limbo language and greatly aids in creating robust and efficient concurrent applications. A s ingle thread can block waiting on one of many channels to complete a read or write operation and then perform an action that depends on which channel completed. This statement is similar to -- but is a great deal more powerful than -- the select() and poll() functions used in Unix.

A Sample of Limbo

The table "Limbo Code Sample" contains part of a simple and contrived program, SortExample.b, that shows some of Limbo's features. It should help get a new Limbo programmer up and running.

SortExample.b has a small driver program that shows how to load one of two modules, each of which implements a different sort algorithm, thus leaving to run time which sorting implementation to use. This example is more complex than it needs to be, but it's useful for demonstrating how to use threads and channels in Limbo.

For the actual sort, a thread is spawned using the sorting function as the secondary thread. A channel is used to communicate the results of t he sort back to the main thread. The main thread blocks on the channel read and thus waits until the sorting thread completes. This file, the sort modules, and the header file are all available for downloading from The BYTE Site ( http://www.byte.com/art/download/download.htm ; the filename is "limboprg.zip").


Limbo Code Sample


SortExample.b


implement SortExample;
include "sys.m";
   sys: Sys;    # declare module instance
      # import sys names into current module scope
      print: import sys;
include "draw.m";  #need some decls
include "Sort.m"; #bring in Sort module decl
   sort : Sort;  #declare mod instance var
SortExample : module
{
   init : fn( ctxt : ref Draw->Context, args : list of string );
};
init(ctxt: ref Draw-
>Context, args: list of string)
{
   sys = load Sys Sys->PATH;
   if ( len args < 3 )
      exit;
   args = tl args;   #ignore prog name
   alg  := hd args;  #declare and assign algorithm name
   modname : string;
   case ( alg )
   {
      "Bubble" or
      "Insert" or
      "Quick"  => modname = alg+"Sort.dis";
      *        => exit; #unknown
   }
   sort = load Sort modname; #dynamic module load
   # convert list of strings to array of int
   nums := tl args; #rest of arguments
   vals := array[len nums] of int;
   for( x:=0; nums != nil; nums = tl nums )
      vals[x++] = int (hd nums);
   # do sort of list of integers
   ch := chan of Sort->Result; #create channel for result
   # start thread to do sort
   spawn sort->SortInts( vals, ch );
   # wait for results
   (result,err) := <- ch;
   if ( err != "" )
   {
      print( "Error: %s\n", err );
      exit;
   }
   # print numbers
   for( x=0; x<len result; x++ )
      print( "%d ", result[x]
 );
   print("\n");
}




Larry Rau (Whitehouse Station, NJ) is a member of the Inferno development team. He can be reached at larryr@lucent.com.