GETTING STARTED IN *LISP Version 6.1, June 1991 Copyright (c) 1991 by Thinking Machines Corporation. "But still the heart doth need a language, still Doth the old instinct Chapter 2: The *Lisp Language bring back the old names." ***************************** Samuel Taylor Coleridge In Chapter 1 we looked at starting up *Lisp and writing simple applications in the language. In this chapter and the next, we'll look at *Lisp as a language and see what features it con- tains. This chapter describes the features of *Lisp that resemble existing features of Common Lisp--in other words, how the two languages are similar. Briefly, in this chapter we'll be looking at: o pvars, the fundamental parallel data structure of *Lisp o data parallelism o the *Lisp parallel equivalents of Common Lisp functions o the parallel data types of *Lisp o defining and compiling your own parallel functions 2.1 Creating and Using Parallel Variables The basic parallel data structure in *Lisp is the parallel vari- able, or pvar. A pvar is a variable that has a separate value for each processor in the CM. Each processor can independently use and modify its own value for a pvar. The values of a pvar can be any one of a number of front-end data types, including numbers, characters, arrays, and structures. I'll often speak of these data types as being scalar data objects to distinguish them from the parallel pvars stored on the CM. 2.1.1 Creating a Pvar--!! The simplest operation of *Lisp is !! (pronounced "bang-bang"), which takes a single scalar argument and returns a pvar with that value in every processor. For example, call the function !! with your age. In my case, this looks like: > (!! 24) # Presto! You've just told your age to several thousand processors. You've also created a pvar (displayed as "#"). Each processor in the CM has reserved a region of space in its memory to hold the value you specified. The sum total of all those regions of reserved memory within the CM is the pvar. (!! 24) | _____|___________ | | | | | V V V V V __ __ __ __ __ |24|24|24|24| ... |24| |__|__|__|__| |__| The expression (!! 24) distributes a scalar value (24) to all processors. This process of creating space for a pvar in the memory of all processors on the CM is referred to as allocating a pvar, and the corresponding operation of releasing that space is referred to as deallocating a pvar. (This is not because *Lisp programmers like long words for simple things; allocating pvars is a little more involved than creating variables in Common Lisp, so it's best to be specific.) Like most *Lisp functions, !! returns a temporary pvar, a pvar used to temporarily store the value of a result. Temporary pvars are similar to bits of scrap paper; you don't use them to hold onto important pieces of information, you just use them to tem- porarily hold onto a value that you're going to store somewhere else. 2.1.2 Permanent Pvars--*defvar That "somewhere else" is quite often a permanent pvar, a pvar de- fined in such a way that it won't go away until you explicitly deallocate it. The *Lisp operation that allocates permanent pvars is *defvar. For example, > (*defvar my-pvar 5) defines a permanent pvar named my-pvar, and initializes it to have the value 5 for each processor. (Notice that the scalar value 5 is automatically converted into a pvar. This is true of virtually every operator in *Lisp; scalar values are promoted to pvars where necessary.) *Lisp automatically defines two permanent pvars for you: t!! and nil!!. As their names suggest, these are the parallel equivalents of t and nil in Common Lisp: t!! has the value t for every pro- cessor, and nil!! has the value nil for every processor. 2.1.3 Local Pvars--*let As we saw in the preceding chapter, you can also create local pvars, that is, pvars that exist only for the duration of a piece of *Lisp code. The *Lisp operator that defines local pvars is *let. For example, (*let ((two!! 2) (three!! 3.0)) (+!! two!! three!! my-pvar)) defines two local pvars, two!! and three!!, and takes the paral- lel sum of these pvars with the permanent pvar my-pvar that we defined in the previous section. 2.1.4 Reading, Writing, and Printing Pvar Values Once you've created a pvar, there are a number of things you can do with it. o You can examine the value of a pvar for any processor in the machine. The *Lisp operation for this is pref, which does a "processor reference." It takes two arguments, a pvar and the number of a particular processor in the CM, and acts much like the Common Lisp operator aref, retrieving the value of the supplied pvar for that processor. o As with array elements in Common Lisp, processors are num- bered from 0 to one less than the total number of processors you have attached. For example, the form > (pref my-pvar 12) 5 returns 5, the value of my-pvar in processor number 12. (In fact, since my-pvar has the value 5 for every processor, this expression would return 5 no matter which processor you chose to examine.) o You can change the value of a pvar for any processor. Just as you apply setf to aref in Common Lisp to change an ele- ment of an array, so in *Lisp the operator *setf is used in combination with pref to change the value of a pvar for a specific processor: > (*setf (pref my-pvar 12) 42) This expression stores the value 42 in my-pvar for processor 12. You can check this with a call to pref: > (pref my-pvar 12) 42 o You can print out the values of a pvar, either for all pro- cessors or only for a particular subset. The *Lisp operation to display the values of a pvar is pretty-print-pvar, or ppp as it is generally known to *Lisp programmers: > (ppp my-pvar :end 20) 5 5 5 5 5 5 5 5 5 5 5 5 42 5 5 5 5 5 5 5 This example displays the value of my-pvar in the first twenty processors. You can see here the value 42 that we stored in processor 12. o You can copy values from one pvar to another. The *set operator takes two pvar arguments and copies the contents of the second pvar into the first: > (*set my-pvar 9) ;;; Set my-pvar to 9 > (ppp my-pvar :end 20) 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 > (*defvar copy-pvar) > (*set copy-pvar my-pvar) ;;; Copy my-pvar to copy-pvar > (ppp copy-pvar :end 20) 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 2.2 Data Parallelism--A Different Value for Each Processor So far, the examples of pvars in this chapter have had the same value in every processor. However, the key point of *Lisp is the data parallelism of the language: the ability of each processor to perform the same operation on potentially different data. Most often, the pvars that you create and use in your programs will have a different value for each processor. *Lisp includes a number of operations that by definition return a different value for each processor. One of these is random!!, which we saw in Chapter 1. Another is the function self- address!!: > (ppp (self-address!!) :end 20) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 The pvar returned by self-address!! contains a special integer for each processor, known as the processor's send address. The send address of each processor is unique and constant, so send addresses can be used to refer to individual processors within the machine. We've already seen one use for send addresses, in the pref exam- ples of Section 2.1.4. We'll see further uses later on. For now, just think of self-address!! as a handy way to get a pvar that has a different value for every processor in the CM. (I'll use self-address!! in future examples to show how the data parallel operations of *Lisp work.) 2.3 Pvar Data Types *Lisp pvars can contain values of many Common Lisp types. Each of the permissible types is listed below, along with examples of *Lisp expressions that return pvars of that type. NOTE: As we've seen, scalar values of any of these data types are automatically promoted to pvars when passed to *Lisp opera- tors that expect pvar arguments. boolean Either t or nil for each processor. t!! nil!! (evenp!! (self-address!!)) unsigned-byte, signed-byte An integer (unsigned or signed) for each processor. (+!! 3 5) (-!! (self-address!!) 800) defined-float A floating-point number for each processor. (float!! 34) (/!! (self-address!!) 4) complex A complex number for each processor. (complex!! 3 1) character A Common Lisp character for each processor. (!! #C) (int-char!! 23) array A Common Lisp array for each processor. (make-array!! '(2 8) :element-type 'single-float :initial-element pi) structure A Common Lisp structure object for each processor (*defstruct particle (x-pos 0 :type (unsigned-byte 32)) (y-pos 0 :type (unsigned-byte 32))) (make-particle!! 20 61) 2.3.1 Other Pvar Types There are also front-end pvars, which contain a reference to a front-end data object for each processor. These are created by the *Lisp front-end!! function. Finally, there is a general pvar type that allows you to store values of many different types in the same pvar (with the excep- tion of arrays and structures). Pvars that are not explicitly de- clared to be of a particular data type are general pvars by de- fault. So, for example, the expression (*defvar my-pvar 5) that we used above creates a general pvar. To define a pvar of a specific data type, you must provide a type declaration for the pvar. (We'll see how to do this in Chapter 5.) 2.4 The Size and Shape of Pvars While you're starting out, you may find it helpful to think of pvars as being a peculiar type of array that just happens to be stored in the memory of the CM. Although there are important differences between Common Lisp arrays and *Lisp pvars, there are a number of similarities as well: o arrays and pvars both hold many elements o arrays and pvars have specified sizes and shapes o the elements of arrays and pvars are accessed by supplying indices o when passed as arguments to functions, both arrays and pvars are passed by reference, never by value So if you find yourself having trouble working with pvars, it doesn't hurt to think of them as arrays until you get used to them. With that said, how can you determine the size and shape of your pvars? The answer is that you determine the size and shape of pvars by setting the size and shape of the current processor grid. There are two ways to do this: by cold-booting the CM with a specific processor grid, and by defining virtual processor sets (VP sets). We'll look at both methods in this section. 2.4.1 Processor Grids and Configurations When you call *cold-boot to attach to a CM and initialize *Lisp, you're not just given a bunch of disorganized processors to play with. The processors of the CM are logically arranged in a one-, two-, or n-dimensional grid known as a processor grid, or, more generically, a configuration. If you call *cold-boot without any arguments, the processors of the CM are arranged in a two-dimensional grid that is as close to being square as the current number of attached processors will allow. For example, for an 8K CM the default grid size is a 64 by 128 grid of processors. If you're using the *Lisp simulator, the default arrangement of processors is an 8 by 4 grid. This grid-like arrangement of processors will become especially important when we look at processor communication later on, but for right now you can simply think of it as a means of specifying the size and shape of your pvars in the memory of the CM, much as you would specify the size and shape of an array on the front end. 2.4.2 *cold-boot The *cold-boot operator returns two values: the number of at- tached CM processors and a list of integers that describes the size and shape of the current processor grid. For example, if you've just attached yourself to an 8K CM, a call to *cold-boot will return > (*cold-boot) 8192 (64 128) You can supply arguments to *cold-boot to select almost any con- figuration of processors you want, within limits. In particular, you can select configurations that have more processors than are physically available on the CM to which you've attached. (We'll see some examples of this later on.) Also, *cold-boot will "remember" the configuration you specify; if you call *cold-boot without any arguments, it will reinitialize *Lisp using the same configuration that it used the last time you called it. Configuration Variables Among other things, *cold-boot initializes a number of Lisp vari- ables according to the current configuration of processors. Two important examples of these variables are: o *number-of-processors-limit* The total number of processors in the current configuration. o *current-cm-configuration* A list of numbers describing the current configuration of the CM processors. In the 8K *cold-boot example shown above, these variables would be initialized as follows: > *number-of-processors-limit* 8192 > *current-cm-configuration* (64 128) You can use these variables to write *Lisp code that will execute correctly no matter how many CM processors are attached. You can also use these variables to remind yourself of the current "state" of the CM, that is, how many processors you have at- tached, and what configuration they are in. 2.4.3 Processor Grids and Pvar Shapes The shape of the current processor grid determines the shape of your pvars. If the value of *current-cm-configuration* is (64 128), as in the examples above, then every pvar that you create will have its values arranged in a two-dimensional grid, 64 ele- ments by 128 elements. For example, the figure below shows the arrangement of values for the pvar returned by the expression (!! 24) for a 64 by 128 processor grid. 0 1 2 3 63 __ __ __ __ __ 0 |24|24|24|24| ... |24| |__|__|__|__| |__| 1 |24|24|24|24| ... |24| |__|__|__|__| |__| . . . . . . __ __ __ __ __ 127 |24|24|24|24| ... |24| |__|__|__|__| |__| Shape of the pvar returned by (!! 24) for a 64 by 128 grid 2.4.4 Pvars of Different Shapes and Sizes--VP Sets But what do you do if you want to use pvars of different shapes and sizes within the same program? This is where the concept of virtual processor sets (VP sets) comes in. You can use VP sets to define differently shaped processor grids that can be used to- gether in the same program. You can then use those configurations to control the shape of your pvars. We'll see some examples of the creation and use of VP sets later on, but for now let's stick to just using one configuration (the one defined by *cold-boot) for all the pvars we define. This will make it easier to focus on the fundamental features of *Lisp. 2.5 Calling Parallel Functions The *Lisp language includes parallel equivalents for most of the basic operations of Common Lisp. For example, just as there are arithmetic operators in Common Lisp, there are parallel arithmet- ic operations in *Lisp: > (ppp (+!! (self-address!!) 3) :end 20) 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 > (ppp (*!! (self-address!!) pi) :end 6) 0.0 3.1415927 6.2831855 9.424778 12.566371 15.707963 > (ppp (float!! (1+!! (self-address!!))) :end 12) 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 11.0 12.0 > (ppp (sin!! (*!! (self-address!!) (/!! pi 4))) :end 6) 0.0 0.7071067 1.0 0.7071074 4.7683707E-7 -0.70710653 > (setq i #C(0.0 1.0)) ;; 2 pi i > (ppp (exp!! (*!! 2 pi i)) :end 5) ;; e = 1 #C(1.0 0.0) #C(1.0 0.0) #C(1.0 0.0) #C(1.0 0.0) #C(1.0 0.0) > (ppp (random!! 20) :end 20) 11 11 18 6 19 10 5 3 4 1 3 10 3 6 5 9 7 5 6 19 In general, the *Lisp parallel equivalent of a Common Lisp opera- tor o has the same name, with either "!!" added to the end, or "*" added in front o performs the same, or nearly the same operation, but in parallel on the CM There are far more parallel operators of this variety than we have space to examine here. If you want to know whether a partic- ular Common Lisp function has a *Lisp equivalent, see the *Lisp Dictionary, which includes a complete list of the functions and macros available in *Lisp. FOR THE CURIOUS: What do the !!'s and *'s mean? As a general rule of thumb, !! (pronounced "bang-bang") is used to mark *Lisp func- tions that always return a pvar, while * (pronounced "star") is used to mark parallel operators that may or may not re- turn a pvar. With one or two minor exceptions, this rule is followed consistently throughout the *Lisp language. The name of the language itself, "star-Lisp," comes from this convention. 2.6 Printing Pvars in Many Ways Let's stop here for a moment and take a closer look at the pvar printing function ppp. The ppp operator has a large number of keyword arguments that let you specify exactly how you would like the values of a pvar to be printed out. The simplest method is the way we've been doing it so far, that is, using the :end keyword to say where ppp should stop display- ing values: > (ppp my-pvar :end 20) 5 5 5 5 5 5 5 5 5 5 5 5 42 5 5 5 5 5 5 5 You can also specify a :start point, if you'd like to take a look at some values in the middle of a pvar: > (ppp (self-address!!) :start 20 :end 30) 20 21 22 23 24 25 26 27 28 29 You can display a fixed number of pvar values :per-line, > (ppp (self-address!!) :end 30 :per-line 12) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 or, if you want to see how the values of a pvar are arranged on the current processor grid, ppp has a :mode argument that lets you ask for the :grid view of things: > (ppp (self-address!!) :mode :grid :end '(4 4)) DIMENSION 0 (X) -----> 0 2 4 6 1 3 5 7 8 10 12 14 9 11 13 15 If the display looks a little disorderly, as in the example above, you can use the :format argument to control the format in which values are printed: > (ppp (self-address!!) :mode :grid :end '(4 4) :format "~2D ") DIMENSION 0 (X) -----> 0 2 4 6 1 3 5 7 8 10 12 14 9 11 13 15 One more useful trick: If you want to, you can add a :title to your output: > (ppp (self-address!!) :end 32 :per-line 8 :format "~2A " :title "Send addresses") Send addresses: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 2.7 Defining *Lisp Functions and Macros Now that we've seen some of the parallel functions available in *Lisp, and seen how to print out the pvars they return, let's look at how you can define your own parallel functions and mac- ros. 2.7.1 To Define a Function, Use defun If you've written Common Lisp programs before, then the operator used to define parallel functions in *Lisp should look very fami- liar to you. It's called defun: (defun add-mult!! (a b c) (*!! (+!! a b) c)) This example defines a function called add-mult!! that takes three arguments, either pvars or numeric values. In each proces- sor on the CM, add-mult!! adds the values of the first two argu- ments (a and b) and then multiplies by the value of the third ar- gument (c). *Lisp functions defined by defun are called exactly as you would call any other Lisp function. So, for example, > (ppp my-pvar :end 12) 9 9 9 9 9 9 9 9 9 9 9 9 > (*set my-pvar (add-mult!! my-pvar -6 (self-address!!))) NIL This call to add-mult!! subtracts 6 from the value of my-pvar for each processor, then multiplies by the value of (self-address!!). The result is stored back into my-pvar by *set, as we can see by calling ppp: > (ppp my-pvar :end 12) 0 3 6 9 12 15 18 21 24 27 30 33 *Lisp functions defined by defun are no different from any other Lisp function. You can use apply and funcall to make calls to them, and use the Common Lisp tracing functions trace and untrace to track calls to them. FOR THE OBSERVANT: You may have noticed that *Lisp includes a special-purpose variant of defun called *defun. However, for most purposes *defun isn't necessary; defun should be used instead. For more information on the difference between these operators, see the entry on *defun in the *Lisp Dictionary. 2.7.2 To Define a Macro, Use defmacro The operation used to define macros in *Lisp should also look familiar to Common Lisp programmers. It's called defmacro: > (defmacro *two-incf (pvar) `(*set ,pvar (+!! ,pvar 2))) *TWO-INCF This macro takes a single pvar argument and increments its value by 2 for each processor. *Lisp macros defined by defmacro are called exactly as you would call any other Lisp macro. For example: > (*two-incf my-pvar) NIL > (ppp my-pvar :end 12) 2 5 8 11 14 17 20 23 26 29 32 35 2.8 Compiling *Lisp Code *Lisp functions and macros are compiled exactly as they are in Common Lisp. This means that there are three basic ways to com- pile a *Lisp function: o You can call the Common Lisp function compile to compile a specific function: (compile 'add-mult!!) o You can call the Common Lisp function compile-file to com- pile a file of code, which you can then load into *Lisp: (compile-file starlisp-code.lisp) (load starlisp-code) o You may also be able to use your editor to compile your code. Depending on the Lisp programming tools your editor provides, there may be a special keystroke you can use to ask the editor to compile a function definition. In Emacs- style editors this keystroke is commonly Ctrl-Shift-C or Meta-Shift-C. Check the manual for your editor for more in- formation. As in Common Lisp, compilation of code is optional. You don't have to compile your code before you can run it. Use the compila- tion method that's most comfortable for you, or don't compile at all, if you choose not to. A Note about Declarations One important difference between Common Lisp and *Lisp is that *Lisp requires complete, explicit declarations of the data types of variables and the returned values of functions in order to fully compile *Lisp code. Declarations in *Lisp look much like the standard Common Lisp de- clarations, except that there are additional data type specifica- tions for pvars. These additional type specifiers are described in Chapter 5. For example, a completely declared version of add-mult!! might look like (defun add-mult!! (a b c) (declare (type (pvar (signed-byte 32)) a b c)) (*!! (+!! a b) c)) This doesn't mean that if you don't provide declarations, your code won't compile. You just won't see the full potential of *Lisp for speed and efficiency in your compiled code. For the most part you can ignore type declarations while you're learning *Lisp. We'll take a deeper look at both declarations and the *Lisp compiler in Chapter 5. 2.9 Summary: How *Lisp and Common Lisp Are Similar In this chapter, we've seen most of the features of *Lisp that are similar to things you'll already have encountered in Common Lisp: o parallel variables (pvars), which are the *Lisp versions of variables in Common Lisp, and resemble arrays in their use o the pvar printing operator ppp, which is used to display the contents of pvars o parallel functions that cause each CM processor to perform a Common Lisp operation o the operators defun and defmacro, which are used in *Lisp just as they are in Common Lisp, to define functions and macros o the *Lisp compiler, an extension of the Lisp compiler for compiling *Lisp code In the next chapter, we'll take a look at the parallel program- ming tools of *Lisp that are the real heart of the language.