Lists

Like languages such as Lisp and ML, Limbo has facilities to manipulate lists of data items. All the elements of a list are of the same type, and a list variable is declared like this:

	ls: list of string;

After this declaration, ls has type list of string and value nil. The Limbo keyword nil represents a value that contains no data; here, it means the list is empty.

There are several operators that apply to lists: a list constructor (::), a head (hd) operator that extracts the first element of a list, and a tail operator (tl) that extracts the remainder of the list after the first element. The constructor is an infix operator (like +) that always takes two arguments: the left argument is a new value to be attached to the beginning of the list, and the right argument is the list itself. For example, after declaring ls above, we can put the first element in the list like this:

	ls = "hello" :: ls;

If we were now to look at the head of the list, we would extract the word "hello" again:

	sys->print("head is: %s.\n", hd ls)

will print

	head is: hello.

Both hd and tl are prefix operators. The expression hd ls has the same type as the elements of the list (here string) and tl ls has the type of the list itself (list of string). Also, the len operator can be applied to a list to inquire how many elements it has.

Limbo programs run from the shell receive command-line arguments as a list of strings. Here is another complete program that can be run from the shell; it receives a list of decimal numbers and prints the numbers and their sum:

	implement Sum;
	
	include "sys.m";
		sys: Sys;
	
	include "draw.m";
	
	Sum: module
	{
		init: fn(context: ref Draw->Context, argl: list of string);
	};
	
	init(context: ref Draw->Context, argl: list of string)
	{
		sys = load Sys Sys->PATH;
	
		argl = tl argl;	# ignore command name
		if(len argl == 0){
			sys->print("usage: sum numbers....\n");
			return;
		}
		sum := 0.0;
		while(argl != nil){
			arg := hd argl;
			sys->print("%s", arg);
			sum += real arg;
			argl = tl argl;
			if(argl != nil)
				sys->print(" + ");
		}
		sys->print(" = %g\n", sum);
	}
	

Much of this program should be familiar. The first section is the same as in "hello, world" except that the module name is now Sum. Since the type of the module looks the same&emdash;one function init with the usual arguments&emdash;Sum can be run from the shell. The program begins by loading module Sys as usual, storing a reference to it in the conventionally named global variable sys.

At this point, it starts doing new things. The argument list, argl, is a list of string, the first of which is passed by the shell as the name of the program itself, that is, the file from which it was run, with the .dis extension stripped off. If the file is sum.dis, this argument will be sum. We toss it away by saying

	argl = tl argl;

Now we can ask how many actual arguments were passed to see if there's any work to do. If none is present, we immediately return control to the function that invoked us by executing a return statement.

Now we're ready to walk along the elements of the argl list. To make the program a little more interesting, it interprets its arguments as floating point numbers (although no check is made that they are validly formatted) and adds them up. The shorthand operator += is inherited from C; the expression

	x += y;

has the same effect as

	x = x + y;

Finally, the program prints the sum using the %g floating-point formatting directive, which suppresses trailing zeros and uses exponential notation only when the number is very large or very small.

Of course, lists can be of any type, not necessarily strings; we could make a list of int or a list of byte or even a list of list of string. Imagine, for example, that our program needed to store the numbers as well as sum them. We could translate the list of string into a list of real like this:

	reals: list of real;
	while(argl != nil){
		reals = real hd argl :: reals;
		argl = tl argl;
	}

but the resulting list of reals is in the opposite order to the list of strings. The loop puts the first element of the first list at the head of the new list, but then puts all the other elements before it as the loop continues. The process is analogous to reversing a deck of cards by dealing them, face down, into a new stack. The definition of Limbo lists makes it inefficient to build the list in the other order, but very easy to reverse the list by copying it:

		newlist: list of real;
		while(reals != nil){
			newlist = hd reals :: newlist;
			reals = tl reals;
		}
		reals = newlist; 

What happens to the original reals list when we re-assign the variable to the new list in the last line of this example? The old list is garbage collected: Limbo manages storage allocation and freeing automatically. When reals gets its new value, the data associated with the old value is recovered automatically. We'll have much more to say about this later, but most of the time you can ignore the problem of managing storage and let the Limbo run-time system manage the memory automatically.

Exercise: When converting the list of strings into a list of reals, it's annoying to need to reverse the list at the end. Write the code so that the list is maintained in the correct order as we add each element. Why is this technique not a good idea in practice?

© Rob Pike and Howard Trickey 1997. All rights reserved.