List Procedures
Listing Three shows the push procedure we use to add an item to the head of a list. The item to be added is defined as a generic POINTER that points to void. push uses cons to allocate a new CONS and set its car and cdr cells. push also updates the LIST variable so that it now points to the correct CONS at the head of the list. The LIST variable is passed to push by reference -- a POINTER to the LIST variable is passed so push can update it. Finally, push returns a POINTER to the head of the list as a convenience to the caller.
cons returns a POINTER to a CONS, but where did it get the CONS? In a LISP implementation, CONS are managed as an allocated-memory resource. At initialization, they are collected together and put on a list called the "free list." Since LISP uses CONS liberally, they must be managed efficiently. In addition, CONS are frequently used to make temporary copies of lists that may or may not be used. As a result, a method or recovering unused CONS and storing them on the free list becomes necessary. We'll use malloc for the necessary memory to hold a CONS. We'll let the system clean up after us by restoring all dynamically allocated memory after exiting.
cons uses malloc and checks to see whether it granted our request. Since there is always a chance malloc cannot allocate memory, we must account for this possibility. Again, production code should have better diagnostics for such error conditions.
pop is the opposite of push: it removes an item from a list. pop removes the first CONS from the list, retrieving its car cell and then releasing the CONS. pop, like push, must be passed a POINTER to a list rather than the LIST variable itself. That's because pop needs to modify the LIST variable to point to the second item in the list. pop uses procedure cpop to retrieve the first CONS and modify the LIST variable. cpop is very useful for walking through a list without releasing the CONS structures that make up the list. We use cpop in several places in our program.
outputlist is a procedure that iteratively removes each item from the list and sends it to the output stream (stdout in our case). However, outputlist makes a copy of the LIST variable and leaves the original list intact. outputlist is not a general list procedure, as it makes assumptions about each item in the list (it assumes each item is a string). Generic functions in LISP will send the printed representation of an argument to the output stream regardless of the argument type.
These functions depend on a more elaborate strategy for data structure than we'll be using here. We'll have to accept the fact that our output function only works for lists of strings. outputlist uses the library procedure fputs, which outputs a string. outputlist takes a LIST as its first argument. We supply this argument by using the sort procedure, which returns a LIST. Syntactically, the fact that sort returns a POINTER to the sorted list is convenient for calling out putlist.
LISP functions always return something. We follow this convention here even in our outputlist procedure, allowing us to use constructs such as:
outputlist (sort(outputlist(item,&1st), compare))))
Here the innermost procedure, push, returns a list used by the next procedure, outputlist, which in turn returns a list used by sort, which returns a list used by the outermost outputlist. Now one can see why LISP stands for "Lots of Insidious Sets of Parentheses."
