Personal tools
You are here: Home Projects LISP StarLisp sim Anonymous. Getting Started in *Lisp. Thinking Machines Corporation. Version 6.1, June 1991.
Document Actions

Anonymous. Getting Started in *Lisp. Thinking Machines Corporation. Version 6.1, June 1991.

by Paul McJones last modified 2010-09-14 19:31

Click here to get the file

Size 214.7 kB - File type text/plain

File contents


The
Connection Machine
System

Getting Started in *Lisp
Version 6.1
June 1991


Thinking Machines Corporation
Cambridge, Massachusetts

First printing, June 1991


The information in this document is subject to change without notice and should 
not be construed as a commitment by Thinking Machines Corporation. Thinking 
Machines Corporation reserves the right to make changes to any products 
described herein to improve functioning or design. Although the information in 
this document has been reviewed and is believed to be reliable, Thinking 
Machines Corporation does not assume responsibility or liability for any errors 
that may appear in this document. Thinking Machines Corporation does not assume 
any liability arising from the application or use of any information or product 
described herein.                              

Connection Machine(R) is a registered trademark of Thinking Machines Corporation.
CM, CM-1, CM-2, CM-2a, and DataVault are trademarks of Thinking Machines 
Corporation.
Paris, and *Lisp are trademarks of Thinking Machines Corporation.
Lisp/Paris is a trademark of Thinking Machines Corporation.
VAX, ULTRIX, and VAXBI are trademarks of Digital Equipment Corporation.
Symbolics, Symbolics 3600, and Genera are trademarks of Symbolics, Inc.
Sun-4 and Sun Common Lisp are registered trademarks of Sun Microsystems, Inc.
Lucid Common Lisp is a trademark of Lucid, Inc.
UNIX is a trademark of AT&T Bell Laboratories.


=============================================================================
| NOTE: This is an ASCII copy of the text of the "Getting Started In *Lisp" |
|       manual from the Thinking Machines Corporation documentation set.    |
|       A hardcopy version of this document--which includes indexes and     |
|       many helpful illustrations--can be obtained by writing to:          |
|                                                                           |
|               Thinking Machines Corporation                               |
|               245 First Street                                            |
|               Cambridge, MA 02142 - 1264                                  |
|               Attention: Katy Smith                                       |
|                                                                           |
|       Or by sending e-mail to:                                            |
|		Internet:	documentation-order@think.com               |
|		uucp:		harvard!think!documentation-order           |
|                                                                           |
| (To skip forward past preface material, search for the string "&&&")      |
=============================================================================


About This Manual

Objectives of This Manual

Getting Started in *Lisp is your introduction to the *Lisp programming 
language. This manual provides an introduction to data parallel programming 
using the *Lisp language. It takes you through a sample *Lisp session, 
introduces you to the important data structures and parallel operations of 
*Lisp, and gives you the basic tools you need to start programming in the 
language.

Intended Audience

This manual is written for people who are relatively new to the Connection 
Machine[ system, but who have some programming experience on other computing 
machines. This guide does assume a general familiarity with the design and 
purpose of the Connection Machine (CM) system, but the prerequisite information 
that you'll need is included in Appendix B of this guide. (The first chapter of 
the CM System User's Guide is also a good source for information at this level 
of detail, and the CM Technical Summary provides a deeper introduction to the 
CM with a more detailed description of how the CM operates.)

Because *Lisp is an extension of the Lisp programming language, familiarity 
with Lisp is essential. This guide assumes a general understanding of the 
Common Lisp dialect of Lisp, as described in Common Lisp: The Language, by Guy 
L. Steele, Jr., and assumes some programming experience in Lisp. If you're not 
familiar with Lisp, two good tutorial references for the language are:

Common Lisp: A Gentle Introduction to Symbolic Computation, David S. Touretzky.
Reading, Massachusetts: Benjamin Cummings Publishing Company, Inc., 1990

Lisp, Patrick Henry Winston and Bethold K. P. Horn. Reading, Massachusetts: 
Addison-Wesley, 1984

Note: There are many small diversions and asides (much like this one) 
throughout the text, marked by headers such as "For the Curious" and "For 
Experts." These sections may be safely ignored if you wish-they provide 
additional information that you may find interesting or useful, and generally 
serve to set the record straight in places where it's necessary to sacrifice 
exacting technical accuracy for the sake of clarity.

Revision Information

This guide is new as of Version 6.1 of *Lisp.

Organization of This Manual

	Chapter 1	Instant *Lisp

Presents a sample *Lisp session, showing you how to start up and use *Lisp, and 
walks you through the process of writing a simple *Lisp program.

	Chapter 2	The *Lisp Language

Presents an overview of the features of *Lisp that have counterparts in Common 
Lisp; in other words, how Common Lisp and *Lisp are similar.

	Chapter 3	Parallel Programming Tools

Presents an overview of the features of *Lisp that are specific to the CM; in 
other words, how Common Lisp and *Lisp differ.

	Chapter 4	When Things Go Wrong

Describes the error-handling features of *Lisp, and shows you how you can use 
the Lisp debugger to examine and diagnose bugs in your *Lisp code.

	Chapter 5	Declaring and Compiling *Lisp Code

Describes the *Lisp compiler and *Lisp type declarations, and explains why 
proper type declarations are essential for getting your code to compile 
completely.

	Chapter 6	*Lisp Sampler-A Scan in Four Fits

Presents four short examples of *Lisp programs that do interesting and unusual 
things, with an emphasis on the way in which a particular *Lisp tool, the 
scan!! function, can be used to perform many different tasks.

	Chapter 7	Going Further with *Lisp

Discusses a few topics not covered elsewhere in this guide, and presents a 
number of sources for further information about the *Lisp language.

	Appendix A	Sample *Lisp Application

Contains a complete copy of the source code for the cellular automata example 
of Chapter 1, along with extensions that define a generic cellular automata 
simulator.

	Appendix B	A *Lisp/CM Primer

Presents a brief introduction to the CM system and to data parallel 
programming, and describes how the *Lisp language is implemented on the CM.

	Appendix C	All the Paris You Need to Know

Presents a brief overview of a few important Paris operations that you need to 
know in order to use *Lisp.

	Appendix D	Sample *Lisp Startup Sessions

Presents sample startup sessions for both the hardware and simulator versions 
of *Lisp.

Related Documents

	*Lisp Dictionary.

This manual provides a complete dictionary-format listing of the functions, 
macros, and global variables available in the *Lisp language. It also includes 
helpful reference material in the form of a glossary of *Lisp terms and a guide 
to using type declarations in *Lisp.

	CM User's Guide.

This document provides helpful information for new users of the Connection 
Machine system, and includes a chapter devoted to the use of *Lisp and 
Lisp/Paris on the CM.

	Connection Machine Technical Summary, Version 6.0.

This document provides an overview of the software and hardware of the CM.

	Connection Machine Parallel Instruction Set (Paris).

This document describes Paris, the low-level parallel programming language of 
the CM. *Lisp users who wish to make use of Paris calls in their code should 
refer to this manual.

	Common Lisp: A Gentle Introduction to Symbolic Computation, David S. 
Touretzky.
Reading, Massachusetts: Benjamin Cummings Publishing Company, Inc., 1990

This document provides a tutorial introduction to programming in Common Lisp.

	Lisp, Patrick Henry Winston and Berthold K. P. Horn. Reading, 
Massachusetts: Addison-Wesley, 1984

This is the one of the original introductory documents for the Lisp language, 
and its most recent editions are compatible with the Common Lisp language 
standard.

	Common Lisp: The Language, Second Edition, Guy L. Steele Jr. 
Burlington, Massachusetts: Digital Press, 1990.

The first edition of this book (1984) was the original definition of the Common 
Lisp language, which became the de facto industry standard for Lisp. ANSI 
technical committee X3J13 has been working for several years to produce an ANSI 
standard for Common Lisp. The second edition of Common Lisp: The Language 
contains the entire text of the first edition, augmented by extensive 
commentary on the changes and extensions recommended by X3J13 as of October 
1989.

	The Connection Machine, W. Daniel Hillis.
Cambridge, Massachusetts: MIT Press, 1985.

This book describes the design philosophy and goals of the Connection Machine 
system.

Notation Conventions

The notation conventions used in this manual are the same as those used in all 
current *Lisp documentation.

	

Convention	Meaning

	

boldface	*Lisp language elements, such as :keywords, operators, and 
function names, when they appear embedded in text.

italics	Parameter names and placeholders in function formats.

typewriter	Code examples and code fragments.

> (user-input)	Interactive examples, user input.

system-output	Interactive examples, Lisp output.

	



Customer Support



Thinking Machines Customer Support encourages customers to report errors in 
Connection Machine operation and to suggest improvements in our products.

When reporting an error, please provide as much information as possible to help 
us identify and correct the problem. A code example that failed to execute, a 
session transcript, the record of a backtrace, or other such information can 
greatly reduce the time it takes Thinking Machines to respond to the report.

To contact Thinking Machines Customer Support:

U.S. Mail:	Thinking Machines Corporation
	Customer Support
	245 First Street
	Cambridge, Massachusetts 02142-1264 

Internet
Electronic Mail:	customer-support@think.com

uucp
Electronic Mail:	ames!think!customer-support

Telephone:	(617) 234-4000
	(617) 876-1111

For Symbolics Users Only

The Symbolics Lisp machine, when connected to the Internet network, provides a 
special mail facility for automatic reporting of Connection Machine system 
errors. When such an error occurs, simply press Ctrl-M to create a report. In 
the mail window that appears, the To: field should be addressed as follows:

To:   customer-support@think.com

Please supplement the automatic report with any further pertinent information.


==============================================================================
| &&&            Main portion of the manual begins here                  &&& |
==============================================================================


Chapter 1: Instant *Lisp

*Lisp (pronounced "star Lisp") is a data parallel extension of the Common Lisp 
programming language, designed for the Connection Machine(R) (CM) system.

*Lisp is a direct extension of Common Lisp, so if you've programmed in Lisp 
before, *Lisp programs should look very familiar to you. The data parallel 
extensions of *Lisp include a large number of functions and macros, and one 
important abstraction, the parallel variable, or pvar ("p-var"). As we'll see 
shortly, pvars are as important to *Lisp programmers as lists are to Lisp 
programmers.

	Getting Started: A Simple Application

So that we have something specific to talk about, I'm going to pick a 
particular type of application, and show you how to develop a *Lisp program for 
it. While the application I've chosen may not be identical to the projects you 
may have in mind, the techniques I use in developing it, and the rules of thumb 
that I use in choosing which features of *Lisp to use, should carry over well 
to your own work.

Important: Interspersed throughout this chapter are sample *Lisp sessions that 
display both the *Lisp forms that you need to type, and the value(s) that *Lisp 
returns. In all these sessions, the lines that you'll want to type are preceded 
by the prompt character ">" and printed in bold type. Lines printed in normal 
type are either results displayed by *Lisp or examples of *Lisp code that you 
don't need to type in.

	Our Project: A Cellular Automata System

Depending on your background and interests, you may or may not have heard of 
the Game of Life. Invented by John H. Conway of the University of Cambridge, 
the Game is played on a very large board, marked off into squares like a 
checkerboard. Each square can be in one of two states, traditionally called 
"live" and "dead." Before each game, some of the squares are made "live," 
usually forming a pattern of some kind. The Game itself is played by changing 
the state of each square according to the following rules:

	A cell's neighbors are the eight squares that surround it on the board.

	If a live square has fewer than two, or more than three live neighbors, 
it dies.

	If a dead square has exactly three live neighbors, it becomes live 
again.

All cells change their values together, in a single "step." The Game consists 
of a series of such steps, one after another. There are no winners and losers 
in the Game-the purpose of the Game is to see the kinds of patterns that arise 
on the board from following these three simple rules. The rules of the Game of 
Life cause the automaton's cells to resemble colonies of living creatures, 
producing patterns of "life" and "death" that ripple across the automaton's 
grid.

For example,  shows a single step from one such game:



. Picture of a single step of the Game of Life, with the "live" cells shaded

Conway's Game of Life is a simple example of a cellular automaton. A cellular 
automaton consists of a grid, or array, of elements called cells, each of which 
contains a value of some kind that determines that cell's state. Along with the 
array of cells, there is a set of rules that determine how the automaton's 
cells change over time. The cells change their states in a regular, 
step-by-step fashion, and the current state of each cell typically depends on 
the state values of its neighbors, the cells that are closest to it.

But the Game of Life is only one of a spectrum of different possible automata. 
Whereas the Game of Life uses two states per cell, other kinds of automata use 
tens, hundreds, or even thousands of states. For example,  shows one possible 
"step" from such a multi-state automaton. (I've used different shading to 
represent different cell states.)



. Picture of one step of a multi#state cellular automaton,
using shading to represent the states of the cells

Such automata are used to simulate the flow of liquids or gases of varying 
densities, the absorption and release of molecules in chemical reactions, and 
even the spread of infectious diseases. Other kinds of automata use grids of 
different shapes and sizes; there are even automata that run on one-dimensional 
and three-dimensional grids.

What we'd like to produce is a simple *Lisp program that allows us to try out a 
number of different automata on the CM, simply by specifying the rules that 
describe how they work. What we need is a set of tools that will let us define 
and display a cellular automaton in action.

For simplicity's sake, let's assume that we'll always be working with automata 
that use two-dimensional grids of cells, and that the states of the cells will 
be represented by integers from 0 to n-1, with n being the total number of 
possible states for a cell. Thus, we need tools for setting the total number of 
states that each cell can have, and for defining how the value of each cell 
depends on the values of its neighbors. Our set of tools should also allow us 
to run the automaton through any required number of steps, and to display the 
current state of the automaton in a readable format.

Okay, now that we've got a reasonably clear idea of what we want to do, we can 
start up a *Lisp session and begin programming.

	*ting Up *Lisp

At this point you have a choice to make, because *Lisp comes in two main forms. 
There's the standard version of *Lisp that runs on the CM hardware, and there 
is also a *Lisp simulator. The simulator is a Common Lisp program that runs 
entirely on your front-end computer, simulating the operations of an attached 
CM through software. 

Depending on the front-end computer you are using, and where your system 
administrator has stored the *Lisp software, there is generally a specific 
command you can type that loads the software for either the CM hardware or the 
simulator version of *Lisp.  For example, on UNIX front ends the command will 
typically be

% starlisp

or

% starlisp-simulator

Once you have the *Lisp software loaded, type:

 (*lisp)		;;; To select the *Lisp package

> (*cold-boot)	;;; To initialize *Lisp and the CM

Important: The *cold-boot  command initializes *Lisp and the CM so that you can 
begin typing commands. If you don't *cold-boot, you won't be able to execute 
any *Lisp code!

For Simulator Users: Among other things, the *cold-boot command sets the number 
of simulated processors that you have available. The default number of 
processors (32) is rather small for our purposes, so you'll want to *cold-boot 
the simulator like this:

> (*cold-boot :initial-dimensions '(16 16))

This starts you off with 256 processors, arranged in a square pattern 16 by 16 
in size.

For CM Users: The *cold-boot command automatically attaches you to a CM, if one 
is available. If you get an error message such as "the FEBI is currently in 
use" or "no sequencers are available", it probably means that the CM is 
currently busy; you may have to try again later. If you're using *Lisp on real 
CM hardware, you can use the command (cm:finger) to find out what CM resources 
are available; see the CM System User's Guide for more information. If you find 
that the CM is busy, you can use the *Lisp simulator instead; the simulator is 
always available, regardless of the state, busy or not, of the CM.

	Using *Lisp

	Defining an Automata Grid

First, we're going to need some way of representing the grid of cells for the 
automaton. In a program written for a serial computer, the grid would be a 
two-dimensional array of integers. On the CM, however, we can take advantage of 
the parallel nature of the machine by storing the state value for each cell in 
the memory of a different CM processor.

To do this, we'll define a parallel variable, or pvar, to keep track of the 
grid:

> (*defvar *automata-grid* 0)
*AUTOMATA-GRID*

By default, when you *cold-boot *Lisp the CM processors are automatically 
arranged in a two-dimensional grid that is as close to being square as the 
number of available processors permits.

Let's print out a portion of this grid:

> (ppp *automata-grid* :mode :grid :end '(8 5))

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

The ppp function (also known as pretty-print-pvar) prints out the values of a 
pvar in whatever format you specify. Here we're using it to display the state 
values of our automata-grid as a grid of numbers.

We'll want to do this quite often, so let's define a function to display the 
grid:

> (defun view (&optional (width 8) (height 5))
	(ppp *automata-grid* :mode :grid :end (list width height)))

Each value displayed by view comes from the memory of a single CM processor. We 
can read and write each value individually, much as we can read and write the 
individual elements of an array.

For example:

> (defun read-cell (x y)
	(pref *automata-grid* (grid x y)))
> (read-cell 5 1)
0

The *Lisp operation pref reads a value from a pvar, given its location within 
the CM. To specify the location I've used grid, a *Lisp helper function that 
lets you describe the location of a particular value by its grid (x and y) 
coordinates. Applying *setf to pref (by analogy with Common Lisp's setf) 
changes the value of the pvar at  the specified location:

> (defun set-cell (x y newvalue)
	(*setf (pref *automata-grid* (grid x y)) newvalue))
> (set-cell 5 1 7)
> (read-cell 5 1)
7
> (view 8 3)
0 0 0 0 0 0 0 0
0 0 0 0 0 7 0 0
0 0 0 0 0 0 0 0

It would be a nuisance to have to set the state value of each cell in the grid 
individually, so let's define a function that will let us set the state of all 
the cells at once:

> (defun set-grid (newvalue)
	(*set *automata-grid* newvalue))
> (set-grid 7)					;;; Set cells to same value
> (view 8 3)
7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7

> (set-grid (random!! 10))	;;; Set cells to random values
> (view 8 3)
1 3 0 5 3 1 9 3
8 5 6 6 0 0 4 6
4 4 5 9 6 7 5 6

Notice that the random!! function calculates a different random value for each 
cell, rather than choosing one random value for all of the cells. This is an 
important feature of *Lisp: data parallelism. *Lisp operations such as random!! 
cause every processor to perform the same operation on potentially different 
data; each processor can produce a different result.

	Defining a Simple Automaton

Now we can start thinking about how to define the rules for an automaton. The 
simplest type of automaton is one in which each cell's state depends only on 
its previous state-that is, where neighboring cells have no effect on one 
another.

As an example, let's define an automaton that obeys the following rules:

	Each cell can have any state value from 0 to 9.

	If a cell's state is even, divide its state value by two.

	If a cell's state is odd, add 1 to its state value and multiply by 2.

I'm not just picking these rules out of thin air. We'll see the effect they 
have in a moment.

In *Lisp, we can easily write a function that implements these rules. For 
example, here's a function that does the calculations for a single step of the 
automaton:

> (defun one-step ()
	(if!! (evenp!! *automata-grid*)
		(floor!! *automata-grid* 2)
		(*!! (1+!! *automata-grid*) 2)))

Here, I'm using the *Lisp operator if!!, which works much like if in Common 
Lisp; it evaluates a test expression for all the CM processors, and then 
performs one *Lisp operation for all processors where the test was true (not 
nil), and another operation for all processors where it was false (nil).

In the one-step function we use evenp!! as the test to find those processors 
whose cell values are even. For these processors, the value of *automata-grid* 
is divided by 2. For all the remaining processors, the value of *automata-grid* 
is incremented by 1, and then multiplied by 2, using the parallel operators 
1+!! and *!! respectively.

For the Curious: Why am I using floor!! rather than /!!? In *Lisp /!! is 
defined to always return a floating-point result, because *Lisp doesn't include 
"rational number" pvars. To get an integer result instead, I use floor!!.

Each calculation used by one-step takes place simultaneously in all processors. 
Even more important, the value of *automata-grid* is not changed by the 
one-step function. if!! returns a pvar whose values depend on the results 
obtained from the two if!! branches. The value of this pvar for each processor 
is the value of the branch that processor executed.

This means that all we need to do is type (set-grid (one-step)) to calculate 
the new value for each cell and update the entire grid. But there's an 
important question that we need to answer first: What happens if a cell's value 
exceeds the total number of states allowed?  Cells are only permitted values 
between 0 and 9, but one-step can return a value for a cell that is greater 
than 9.

This suggests a simple answer: We can use the *Lisp function mod!! to redefine 
set-grid so that it will automatically wrap values greater than 9 back into the 
range 0 through 9:

> (defvar *total-number-of-states* 10)

> (defun set-grid (newvalue)
	(*set *automata-grid*
		(mod!! newvalue *total-number-of-states*)))

> (set-grid 27)
> (view 8 3)
7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7

> (set-grid (random!! 27))
> (view 8 3)
7 2 0 7 3 8 6 4
1 0 8 3 2 4 5 2
1 9 7 0 2 3 1 3

This last example is a useful tool. We'll want the ability to set every cell in 
the grid to a random state. Let's write a function that does this, and write it 
so that it automatically chooses random values in the range from 0 up to one 
less than the current number of states:

> (defun random-grid ()
	(set-grid (random!! *total-number-of-states*)))

And while we're defining things, let's create a function that will run the 
automaton through any specified number of steps:

> (defun run (&optional (n 1))
	(dotimes (i n)
		(set-grid (one-step))))

Now we can run the automata and see how it works. Let's randomize the grid and 
run the automaton through 1, 5, and 50 cumulative steps:

> (random-grid)						
> (view 8 3)							
5 3 2 4 6 7 6 3						
0 9 5 2 1 2 9 7						
7 5 3 8 6 8 7 8						

> (run)	
> (view 8 3)	
2 8 1 2 3 6 3 8
0 0 2 1 4 1 0 6
6 2 8 4 3 4 6 4

> (run 4)								
> (view 8 3)							
1 4 4 1 1 2 1 4						
0 0 1 4 2 4 0 2						
2 1 4 2 1 2 2 2						

> (run 45)
> (view 8 3)
1 4 4 1 1 2 1 4
0 0 1 4 2 4 0 2
2 1 4 2 1 2 2 2

We don't have to run this automaton for many more steps to realize that it's in 
a steady loop; all 0 cells will remain 0, and all other cells will run through 
the series 4-2-1 over and over.

I chose the original rules with this result in mind; it's one of the most 
common ending conditions of a cellular automaton. After a certain number of 
loops, a cellular automaton typically settles down into one of a few basic 
patterns of activity:

	It can become moribund, with no cells ever changing.

	It can become trapped in a steady, repeating pattern.

	It can become chaotic, displaying no readily apparent pattern.

	It can alternate irregularly between steady patterns and chaotic 
activity.

Let's define another automaton, this time one that's a little more interesting 
(that is, one of the latter two varieties).

	Defining a More Complex Automaton

This time we'll create an automaton in which neighboring cells do influence one 
another. The automaton I have in mind is a variation on Conway's Game of Life, 
called "9 Life." As before, each cell can have any one of ten states, 0 through 
9, but the rules are somewhat more detailed:

	For each cell in the automaton, get the state values of the cell's 
neighbors, and count the number of neighbors that have non-zero values.

	If the number of non-zero neighbors is either less than 1, or greater 
than 3, subtract 1 from the cell's value (unless it is already zero, in which 
case it remains zero).

	If the number of non-zero neighbors is either 2 or 3, add 1 to the 
cell's value.

	Otherwise leave the cell unchanged.

Rest assured, there is method to this madness, as we'll see when we run this 
automaton.

Of course, I also have to define what I mean by "neighbors". There are two 
well-known types of neighborhoods that are used in two-dimensional cellular 
automata, the Von Neumann neighborhood and the Moore neighborhood (see ).

The Von Neumann neighborhood is the four cells immediately adjoining a given 
cell; in other words, its neighbors to the north, east, south, and west. The 
Moore neighborhood adds the four diagonal neighbors as well, for a total of 
eight cells.



. Two important cellular automaton neighborhoods

The Game of Life happens to use the Moore neighborhood, but we'll design our 
tools so that we can choose either neighborhood when we run the 9 Life 
automaton-that way we can see the differences between the two.

No matter which neighborhood we choose, however, we'll need a function that 
will cause each cell to check the values of its neighbors, make a count of the 
ones that are currently positive, and update its own value.

If we were to write such a function for an ordinary serial computer, it would 
most likely consist of a loop that steps through the automaton cell by cell, 
doing the count for each cell individually. A serial one-step function would 
look something like:

(defun serial-one-step (array-x-size array-y-size)
	(dotimes (x array-x-size)
 		(dotimes (y array-y-size)
 		 (let ((neighbors (list	(get-cell (- x 1) y)
									
	(get-cell (+ x 1) y)
									
	(get-cell x (- y 1))
									
	(get-cell x (+ y 1))
									
	... )))
			(store-new-cell-value x y
				(new-value neighbors)))))
	(update-grid))

Here, get-cell gets the value of a cell from the automata grid, new-value 
calculates the new value for a cell based on the values of its neighbors, 
store-new-cell-value stores the new value of the cell in a temporary array, and 
update-grid updates the grid by storing the new value for each cell into the 
automata grid.

There are three important things to notice about this function:

	The function must explicitly refer to the actual shape of the grid, as 
described by the arguments array-x-size and array-y-size.

	The function includes a double dotimes loop to step through all the 
cells.

	The function must temporarily store the new value for each cell, and 
then update the values for all the cells after the loop has been completed, so 
that the new values of cells reached earlier in the loop don't influence the 
calculations for cells reached later in the loop.

Things are much simpler on the CM. Remember that each cell of the automaton is 
stored in the memory of a different CM processor. We can simply have the 
processor associated with each cell find the state values of the cell's 
neighbors, count the ones that are positive, and then update the cell 
accordingly. All the cells will update simultaneously, eliminating the need for 
any looping as well as the need to temporarily store the new value for each 
cell outside the grid. Before we can write the function that does this, 
however, we'll need to look at how we can use *Lisp operations to cause the CM 
processors to exchange values.

There are a number of *Lisp operators that cause the CM processors to exchange 
values with each other. What we want is a operator that will instruct each cell 
in the automaton to get the value of a single neighboring cell (for example, 
one to the north, one to the east, etc.).

In *Lisp, the tool we want is news!!. For example:

> (random-grid)
> (view 8 3)
2 3 1 0 2 7 2 4	 ;;; Dimension	 0	runs -across-
4 5 6 5 4 6 8 0	 ;;; Dimension	 1	runs -down-
6 8 4 3 8 1 7 9								
		

> (set-grid (news!! *automata-grid* -1 0))
> (view 8 3)
0 2 3 1 0 2 7 2
1 4 5 6 5 4 6 8
0 6 8 4 3 8 1 7

In this example, I've used news!! to shift the entire contents of the 
*automata-grid* by one cell. The grid coordinates given to news!!, (-1, 0), are 
interpreted by each processor as being relative to that processor's position in 
the grid. So the coordinates (-1, 0) cause each processor to get a value from 
the processor that is one step to the "west" across the grid. Each processor 
gets the cell value of its west neighbor, and stores that value in its own 
cell.

For the Curious: You may be wondering where the numbers in the left-most column 
came from. A useful property of news!! is that it "wraps" automatically at the 
edges of the grid. The cells on each edge automatically wrap to their 
counterparts on the opposite edge, so there's no need to do anything special at 
the edges of the grid. This also means that we don't have to worry about the 
actual size of the grid. Our code will run unchanged on CMs of any processor 
size.

Who Are the People in YOUR Neighborhood?

Let's use news!! to define a set of functions that will cause each cell to 
count the number of its non-zero neighbors according to the current 
neighborhood we've chosen.

We'll want to be able to switch neighborhoods, so let's define a global 
variable that will determine the neighborhood that we want these functions to 
use.

> (defvar *neighborhood* :neumann)

Now for the counting functions themselves. There are many ways to write them, 
of course, but what we want is something simple and readable. Here's a function 
that will get the sum of neighbors in the Von Neumann neighborhood:

> (defun neumann-count (grid)
	 (+!!	(news!! grid  0 -1)	;; north
			(news!! grid  0  1)	;; south
			(news!! grid -1  0)	;; west
			(news!! grid  1  0)	;; east
			))

and here's one that does the same thing for the Moore neighborhood.

> (defun moore-count (grid)
	 (+!!	(news!! grid  0 -1)	;; north
			(news!! grid  0  1)	;; south
			(news!! grid -1  0)	;; west
			(news!! grid  1  0)	;; east
			(news!! grid -1 -1)	;; northwest
			(news!! grid -1  1)	;; southwest
			(news!! grid  1 -1)	;; northeast
			(news!! grid  1  1)	;; southeast
			))

It will be really convenient if we can call a single function and have it 
choose the right helper function for our current needs. Here's the function 
we'll use:

> (defun neighbor-count ()
	(*let ((grid (signum!! *automata-grid*)))
		(ecase *neighborhood*
			(:moore (moore-count grid))
			(:neumann (neumann-count grid)))))

Here we've used *let, the *Lisp version of let, to define a local pvar whose 
value is a copy of the *automata-grid* with all non-zero cells set to 1. When 
we pass this grid to the neighbor-counting functions, we obtain just a count of 
the number of non-zero neighbors.

For the Curious: The *Lisp function signum!! is the parallel version of Common 
Lisp's signum; the signum!! function takes a numeric pvar argument, and returns 
a pvar that contains 1, 0, or -1 for each processor, depending on whether the 
argument pvar was positive, zero, or negative for that processor.

One Small Step...for 9 Life

Having these neighbor-counting functions, we can redefine the one-step function 
for the 9 Life automata as:

> (defun one-step ()
	(*let ((count (neighbor-count)))
	 (cond!!
		; When count is < 1 or > 3, subtract 1 if not zero.
		((or!! (<!! count 1) (>!! count 3))
		 (if!! (zerop!! *automata-grid*)
				*automata-grid* 
				(1-!! *automata-grid*)))

		; When count is 2 or 3, add 1
		((<=!! 2 count 3) (1+!! *automata-grid*))

		; Otherwise, leave cells unchanged
		(t *automata-grid*))))

In this function we're using another *Lisp conditional operator, cond!!. 
Similar to Common Lisp's cond form, cond!! evaluates multiple tests and 
executes branches of code in separate groups of processors.

As with if!!, cond!! returns a pvar whose value depends on the execution of its 
branches. The value of a cond!! form for each processor is simply the value of 
the cond!! clause that processor executed. This is handy, because we want to 
set the value of *automata-grid* based on the results of a number of parallel 
tests, but we don't want to have to write a separate (set-grid (if!! ... )) 
expression for each test.

Now in order to see the effects of this automaton we'll want to set up a more 
orderly test case than a random grid. This pair of functions will initialize 
the grid with a simple pattern:

> (defun set-cells (cell-list value)
	  (dolist (cell cell-list)
 	   (set-cell (car cell) (cadr cell) value)))

> (defun init ()
	  (set-grid 0)
	  (set-cells '((2 2) (3 1) (3 2) (3 3) (4 1))
	             1)
	  (view))

And let's add a function to our toolbox that will let us run the automaton 
through a number of steps, and then automatically display the current state of 
the automaton. This is easy- we'll just reuse the run and view functions we 
defined earlier:

> (defun view-step (&optional (n 1))
	  (run n)
	  (view))

Let's run this new automaton through 1, 5, and 50 cumulative steps:

> (init)								
0 0 0 0 0 0 0 0					
0 0 0 1 1 0 0 0					
0 0 1 1 0 0 0 0					
0 0 0 1 0 0 0 0					
0 0 0 0 0 0 0 0					

> (view-step)						
0 0 0 0 0 0 0 0					
0 0 1 2 1 0 0 0					
0 0 1 2 1 0 0 0					
0 0 1 1 0 0 0 0					
0 0 0 0 0 0 0 0					

> (view-step 4)
0 0 0 0 0 0 0 0
0 0 5 6 5 0 0 0
0 0 5 0 5 0 0 0
0 0 5 5 4 0 0 0
0 0 0 0 0 0 0 0

> (view-step 45)
0 0 0 0 0 0 0 0
0 0 9 7 2 0 0 0
0 0 4 0 6 0 0 0
0 0 3 4 8 0 0 0
0 0 0 0 0 0 0 0

Strange, isn't it? The automaton seems trapped in a square pattern of numbers, 
determined by the shape of the original pattern of 1's. The cells within the 
square continue to change in a manner that is not readily predictable, but this 
pocket of non-zero values can't seem to spread beyond the edges of the square.

We're running the automaton with a Von Neumann neighborhood, so that each cell 
has a limited number of neighbors. What happens if we use the Moore 
neighborhood?

> (setq *neighborhood* :moore)
:MOORE

Here's the results for runs of 1, 5, and 50 steps:

> (init)								
0 0 0 0 0 0 0 0					
0 0 0 1 1 0 0 0					
0 0 1 1 0 0 0 0					
0 0 0 1 0 0 0 0					
0 0 0 0 0 0 0 0					

> (view-step)						
0 0 0 1 1 0 0 0					
0 0 1 2 2 0 0 0					
0 0 2 0 0 0 0 0					
0 0 1 2 1 0 0 0					
0 0 0 0 0 0 0 0					

> (view-step 4)
0 1 0 0 0 0 1 0
1 0 2 2 4 0 1 0
1 0 0 0 0 2 1 2
1 0 3 4 0 0 0 1
1 0 3 4 0 0 0 1

> (view-step 45)
0 0 0 0 3 0 0 0
4 6 6 1 0 0 0 0
0 0 0 0 0 0 4 3
3 3 8 1 0 0 5 1
0 0 0 0 2 1 0 1

As you can see, the eight-fold pathways of the Moore neighborhood allow the 
original pattern to spread much further across the grid.

For Speed Freaks: By the way, if the (view-step 45) calls in the above examples 
seem slow to you, remember that you're running these examples in an interpreted 
form, which will by definition not run at the maximum speed of your machine. 
You can compile your *Lisp code for speed, turning it into efficient Lisp/Paris 
code-we'll see how to do this later on.

	Mortal or Immortal?

An interesting question to ask is: Does the pattern die out for either 
neighborhood? That is, does the automaton ever reach a state at which every 
cell is in the zero state, so that no further change is possible?

I'll leave that for you to answer, by exploring further the two versions of the 
automaton. To try either one, remember to choose a *neighborhood*, either 
:neumann or :moore, and to call the init function to restore the original 
pattern. Then view-step yourself into oblivion.

There's one more tool that you'll need to use to check whether the grid is 
truly dead. As you know, view shows only a portion of the grid. But the state 
values produced by the Moore version of this automaton can ripple across the 
grid, into cells that we can't see using the default width and height arguments 
to view.

Rather than print out the entire grid to make sure there are no live cells 
left, you can use a simple *Lisp function to do the test for you. It's called 
*sum:

> (*sum (signum!! *automata-grid*))
208

The *sum function returns the sum of all the values of a pvar. In this example, 
we've once again made a copy of the *automata-grid* in which every non-zero 
cell is replaced by 1, and then used *sum to take the sum of this grid's 
values. This gives a count of the number of live cells in *automata-grid*. When 
the count reaches zero, the automaton is well and truly dead. So a simple test 
for the dead state is:

> (defun deadp () (zerop (*sum (signum!! *automata-grid*))))
> (deadp)
NIL

Notice that we're using the Common Lisp zerop test here, not a parallel test, 
because *sum returns a scalar value, not a pvar. When deadp returns t, you'll 
know that every cell in the grid-including the ones that you can't see with 
view-has been zeroed out.

Try running both versions of the 9 Life automaton for a few hundred steps, and 
see if either one dies out. Then try modifying the rules for the automaton, or 
the initial pattern, and see what happens as a result. See if you make the 
pattern die out faster, or cause it to fall into a fixed state forever.

	Personalize Your System

If you've been typing things in all along, and saving the defun and defvar 
forms into a file as you work, you now have a fairly sizable amount of *Lisp 
code that implements a limited but generic cellular automata simulator. What do 
you do with it now? Personalize it, of course. Play around with the code 
yourself, and modify things to suit your own taste.
Enhance the system with your own ideas; there are many ways in which it can be 
improved.

For example, the way things are right now you must redefine the one-step 
function every time you want to try a different automaton. A useful way to 
extend this automata simulator would be to write operations that let you define 
many different kinds of automata by name, and to call up any named automaton 
for use automatically.

In an appendix to this document, I've outlined just such a system for your 
perusal. The appendix also includes a commented copy of all of the *Lisp code 
used in this chapter. There is also a copy of this code on-line in the *Lisp 
software directory, in the file

/cm/starlisp/interpreter/f6100/cellular-automata-example.lisp

Check with your system administrator or applications engineer if you need help 
locating this file.

	Exiting From *Lisp

At this point, let's assume you're ready to call it quits for now, and want to 
exit from *Lisp.

If you're attached to a CM, type

> (cm:detach)		;; Detach any attached CM

to release it.

You can then type the Lisp exit command that is appropriate for your system, as 
described in the CM User's Guide. For example, Lucid users should type either 
(lcl:quit) or (sys:quit). Symbolics users don't need to "exit" from Lisp, and 
can simply type  (*lisp) to deselect the *Lisp software package.

Note: If you detach, and then decide that you want to do some more work with 
*Lisp, simply type

> (*cold-boot)

to reattach and re-initialize *Lisp.

Remember: until you call *cold-boot to attach a CM and initialize *Lisp, you 
won't be able to execute any *Lisp code!


Chapter 2: The *Lisp Language

In Chapter  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 contains. 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:

	pvars, the fundamental parallel data structure of *Lisp

	data parallelism

	the *Lisp parallel equivalents of Common Lisp functions

	the parallel data types of *Lisp

	defining and compiling your own parallel functions

	Creating and Using Parallel Variables

The basic parallel data structure in *Lisp is the parallel variable, 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.

	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)
#<FIELD-Pvar 1-5 *DEFAULT-VP-SET* (64 128)>

Presto! You've just told your age to several thousand processors. You've also 
created a pvar (displayed as #<FIELD-Pvar...>"). 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.



. 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 temporarily hold onto a value that you're going to store 
somewhere else.

	Permanent Pvars - *defvar

That "somewhere else" is quite often a permanent pvar, a pvar defined 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 processor, and nil!! has the value nil for 
every processor.

	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 parallel sum of these 
pvars with the permanent pvar my-pvar that we defined in the previous section.

	Reading, Writing, and Printing Pvar Values

Once you've created a pvar, there are a number of things you can do with it.

	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.

As with array elements in Common Lisp, processors are numbered 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.)

	You can change the value of a pvar for any processor. Just as you apply 
setf to aref in Common Lisp to change an element 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

	You can print out the values of a pvar, either for all processors 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.

	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

	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 . 
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 examples of Section 
. 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.)

	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 operators 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)

	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 exception of arrays and structures). 
Pvars that are not explicitly declared to be of a particular data type are 
general pvars by default. 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 .)

	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:

	arrays and pvars both hold many elements

	arrays and pvars have specified sizes and shapes

	the elements of arrays and pvars are accessed by supplying indices

	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.

	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.

	*cold-boot

The *cold-boot operator returns two values: the number of attached 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 configuration 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 variables according 
to the current configuration of processors. Two important examples of these 
variables are:

	*number-of-processors-limit*
The total number of processors in the current configuration.

	*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 attached, and what configuration they are in.

	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 elements by 128 elements. For example,  shows the 
arrangement of values for the pvar returned by the expression

(!! 24)

for a 64 by 128 processor grid.



. Shape of the pvar returned by (!! 24) for a 64 by 128 grid

	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 together 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.

	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 arithmetic 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 operator

	has the same name, with either "!!" added to the end, or "*" added in 
front

	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 particular 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 functions that always return a 
pvar, while * (pronounced "star") is used to mark parallel operators that may 
or may not return 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.

	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 displaying 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

	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 macros.

	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 familiar 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 processor on the CM, add-mult!! adds 
the values of the first two arguments (a and b) and then multiplies by the 
value of the third argument (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.

	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

	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 compile a *Lisp function:

	You can call the Common Lisp function compile to compile a specific 
function:

(compile 'add-mult!!)

	You can call the Common Lisp function compile-file to compile a file of 
code, which you can then load into *Lisp:

(compile-file "starlisp-code.lisp")
(load "starlisp-code")

	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 information.

As in Common Lisp, compilation of code is optional. You don't have to compile 
your code before you can run it. Use the compilation 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 declarations, 
except that there are additional data type specifications for pvars. These 
additional type specifiers are described in Chapter .

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 
.

	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:

	parallel variables (pvars), which are the *Lisp versions of variables 
in Common Lisp, and resemble arrays in their use

	the pvar printing operator ppp, which is used to display the contents 
of pvars

	parallel functions that cause each CM processor to perform a Common 
Lisp operation

	the operators defun and defmacro, which are used in *Lisp just as they 
are in Common Lisp, to define functions and macros

	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 programming tools of 
*Lisp that are the real heart of the language.



Chapter 3: Parallel Programming Tools

Up until this point, we've been using the CM simply as a massively parallel 
calculator, having every processor perform the same operation at the same time. 
>From here on we'll see how we can use the CM as a massively parallel computing 
system, by using the parallel programming tools of *Lisp.

In Chapter , we saw the features of *Lisp that are similar to Common Lisp. Now 
we'll look at the CM-specific parallel programming tools of *Lisp that 
distinguish it from Common Lisp.

	Data Parallel Programming

The *Lisp tools for data parallel programming fall into five main categories:

	tools for selecting a set of processors to perform an operation

	tools for moving data between processors within the CM

	tools for moving data between the CM and the front end

	tools for combining and transforming data

	tools for determining the shape of your pvars (VP sets)

In the following sections, we'll look at one or two examples from each 
category.

	Processor Selection Operators

Because you don't always want to perform the same operation in every processor, 
*Lisp allows you to select which processors will perform a given operation. 
Each processor maintains an internal flag that determines whether it is active, 
that is, whether or not it will execute the instructions it receives. Because 
of this, you can choose a subset of the processors in the machine, known as the 
currently selected set, to execute any given operation. The rest of the 
processors are deselected, and do nothing.

The processor selection operators in *Lisp are modeled after the conditional 
tests of Common Lisp, and typically select processors based on the result of a 
parallel test. By default, all CM processors are active when you *cold-boot 
*Lisp, so the main job of the processor selection operators is to temporarily 
turn off, or deselect, some processors for the duration of a piece of code.

	Processor Selection - Doing More by Doing Less

"What's the good of that?" you might ask. "The point of having a massively 
parallel CM is to have all the processors computing at once. If I turn some of 
them off I'm wasting computing power, right?" In a sense, yes; if you were to 
turn off all but one of the CM processors, that certainly wouldn't be very 
efficient. However, it's unlikely that you would ever knowingly choose to do 
that.

A better way to look at it is the way Michelangelo looked at carving a statue 
of a lion: He selected all those parts of a block of stone that weren't lion, 
and carved them away. Processor selection operators let you select just those 
values of a pvar that have a certain important property, so that you can 
perform an operation on those values while leaving the rest undisturbed. What 
you temporarily lose in computing power, you more than gain back in computing 
finesse.

For example, a *Lisp function to carve Michelangelo's lion would look like:

(defun carve-lion (stone-pvar)
	(*when (not!! (lion-p!! stone-pvar))
		(*set stone-pvar (carve!! stone-pvar))))

The *Lisp operation *when uses a parallel test to determine which processors 
should be active. In this case, the test (not!! (lion-p!! stone-pvar)) selects 
only those processors where stone-pvar doesn't look like a lion. The *set form 
is evaluated only for those processors, with the result that all values of 
stone-pvar that are not!! lion-p!! are carve!!-ed away, leaving us a stone-pvar 
with a single perfect lion inside.

This function would actually work, if we could find someone like Michelangelo 
to write the lion-p!! test for us. Failing that, let's look at a more mundane 
example, in which we'll use *when to perform a calculation using only the 
even-numbered CM processors:

> (*defvar data 4)
DATA
> (ppp data :end 20)
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

Here, the pvar data is given the value 4 in every processor. We'll need to use 
the value of the self-address!! function, so let's print out its value for a 
few processors:

> (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

Let's assume we want to add 3 to data in every even-numbered processor. That 
means that we need a test that returns t wherever the value of self-address!! 
is even. *Lisp has such a test: evenp!!

> (ppp (evenp!! (self-address!!)) :end 20)
T NIL T NIL T NIL T NIL T NIL T NIL T NIL T NIL T NIL T NIL

With this test in hand, the actual *when expression is simple:

> (*when (evenp!! (self-address!!))
		(*set data (+!! data 3)))
NIL
> (ppp data :end 20)
7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4

The result, as we can see, is that the value of data is set to 7 for every 
even-numbered processor. Not much like a lion, but it's a start.

A related parallel conditional, if!!, also selects processors based on a test. 
The difference is that if!! also returns a pvar result:

> (ppp (if!! (oddp!! (self-address!!))
				 (+!! data 3)
				 (-!! data 3))
	 :end 20)
4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7

As you can see in this example, if!! actually performs two selections:

	First, all odd processors are selected (that is, all processors in 
which (oddp!! (self-address!!)) is t), and the sum of data and 3 is calculated 
for those processors.

	Then those processors are deselected, and all the remaining processors 
(those for which  (oddp!! (self-address!!)) is nil) are selected. In these 
processors, the difference of data and 3 is calculated.

The value returned by if!! for each processor is the value it obtains from one 
or the other of these two operations. In this example, if!! returns the sum of 
data and 3 in all odd-numbered processors, and the difference of data and 3 in 
all even-numbered processors. The 7's and 4's in the pvar returned by if!! thus 
alternate in a manner exactly opposite that of the original data pvar.

For the Curious: Enumerating Selected Processors

One *Lisp function that comes in handy for working with selected sets of 
processors is enumerate!!. This function is similar to self-address!!, in that 
it assigns unique sequential integer values to processors. The difference is 
that enumerate!! assigns values only to selected processors:

> (*defvar empty-pvar 0)
EMPTY-PVAR

> (ppp empty-pvar :end 20)
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

> (*when (evenp!! (self-address!!))
		(*set empty-pvar (enumerate!!)))
NIL
> (ppp empty-pvar :end 20)
0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0

	The Processor Selection Operators of *Lisp

There are *Lisp processor selection operators that correspond to all the major 
Common Lisp conditionals, including when, unless, if, cond, case, and ecase, 
plus two additional  CM-specific operations, *all and with-css-saved. We don't 
have room to examine each of them here, but they are described in more detail 
in the *Lisp Dictionary.

	Communication Operators

When applied to processors on the CM, the term "communication" essentially 
means "moving data around between processors." There are two main methods of 
communication in *Lisp: router communication and grid communication.

	Router Communication - General-Purpose Data Exchange

The processors in the CM are all linked together by a general message-passing 
network called the router. The router allows each processor to send a piece of 
data to any other processor in the CM, with all processors transmitting data 
simultaneously.

A useful way to picture this is to think of the router as a postal service for 
processors (see ).

 *number-of-processors-limit*
8192
> (*pset :no-collisions	(self-address!!)
						 		data
								(-!! 
*number-of-processors-limit*
									
	(self-address!!)
									
	1))
> (ppp data :end 10)
8191 8190 8189 8188 8187 8186 8185 8184 8183 8182

Note: This example shows output for an 8K CM. You may see different results, 
depending on the size of your CM. If you're using the *Lisp simulator, the 
numbers you see displayed will be much smaller. Nevertheless, the first value 
printed by ppp will be one less than *number-of-processors-limit*, with the 
following values in descending order.

In this example:

	A call to (self-address!!) is used as the pvar of messages to be sent; 
that is, each processor is sending its own address.

	The data pvar is the set of mailboxes into which the messages are 
delivered.

	The expression (-!! *number-of-processors-limit* (self-address!!) 1) 
provides the addresses; that is, processors with low send addresses send to 
processors with high send addresses, and vice versa.

The result is that the data pvar now contains a copy of the (self-address!!) 
pvar with its values "flipped" end for end.

For the Curious: What's the :no-collisions keyword there for? Since no two 
messages are being sent to the same processor, we can use the :no-collisions 
keyword argument of *pset to let it know that it can use the most efficient 
communication algorithms possible.

	Grid Communication - Fast, but with Restrictions

There's one main problem with router communication; just like the real-life 
Postal Service, for some kinds of communication it's just too slow. For this 
reason, the CM includes a more specialized form of communication called grid 
communication.



. In grid communication data moves along the axes of the processor grid

Whereas router communication allows each processor to send a message to any 
other processor in the machine, in grid communication all processors send their 
messages in the same direction along the axes of the current processor grid 
(see ).

Because the messages all "follow the lines" of the processor grid, so to speak, 
and because the movement of every message is expressed in terms of "so many 
processors up," "so many processors over," and so on, grid communication is 
generally much faster than router communication.

Grid communication does limit you to moving your data across the processor grid 
in lock-step fashion, much like soldiers marching in formation on a parade 
ground, but for many applications, such as the cellular automata example we saw 
in Chapter , this grid-like motion of data is exactly what is needed.

	The Grid Communication Operators of *Lisp

The main grid communication operators of *Lisp are:

	news!!, which shifts values across the grid according to a set of 
relative coordinates

	*news, which shifts values, and also stores them in a supplied 
destination pvar

As an example, let's look at *news. We can use *news to write a function that 
performs the zig-zag movement of data shown in  as follows:

> (defun zig-zag (pvar)
		(*news pvar pvar 3 0)	;;; three steps "east"
		(*news pvar pvar 0 -1)	;;; one step "north"
		(*news pvar pvar 2 0))	;;; two steps "east"
ZIG-ZAG

Each of the *news calls in this function takes data from the supplied pvar, 
shifts it a number of steps across the grid, and then stores it back in pvar. 
The two numeric arguments in each *news call specify how many steps to take 
along each grid axis.

Of course, you're not limited to motion along a single axis. In the example 
above I've divided up the movement of data into three steps to emphasize the 
stepwise nature of grid communication. You can just as easily define the 
zig-zag function with a single *news call:

> (defun zig-zag (pvar)
	 (*news pvar pvar 5 -1))  ;;; five steps "east", one "north"
ZIG-ZAG

For the Curious: You might wonder why it's called "*news," and not something 
more memory-jogging like "*grid." The reason is historical. Grid communication 
is often referred to as "NEWS" ("North-East-West-South") communication, because 
on early versions of the CM hardware grid communication was limited to 
two-dimensional processor grids. The grid communication operators of *Lisp 
likewise derive their names from this two-dimensional pattern of data exchange.

	An Example of Grid Communication

Let's define a pvar and use the zig-zag function to move its values around. 
We'll also use the :grid argument to ppp so that we can see the current 
processor grid displayed as a grid of values on the screen.

For Simulator Users: The following examples assume that the current processor 
grid is two-dimensional and at least 6 by 6 processors in size. If you're 
running *Lisp on CM hardware this is the default. If you're using the *Lisp 
simulator, however, the default processor grid (8 by 4) won't be large enough, 
so type the following:

> (*cold-boot :initial-dimensions '(8 8))

Let's create a permanent pvar with the value 0 in every processor, and then 
store three integers into it so we can see the movement of data between 
processors:

> (*defvar data-pvar 0)
DATA-PVAR
> (*setf (pref data-pvar (grid 0 2)) 2)
> (*setf (pref data-pvar (grid 0 3)) 3)
> (*setf (pref data-pvar (grid 0 4)) 4)

Here again, we're using the function grid to refer to processors by their grid 
coordinates. Now let's use ppp to display the data-pvar in :grid format:

> (ppp data-pvar :mode :grid :end '(6 6))
0 0 0 0 0 0
0 0 0 0 0 0
2 0 0 0 0 0
3 0 0 0 0 0
4 0 0 0 0 0
0 0 0 0 0 0

Here we're displaying the top left-hand "corner" of the current processor grid, 
and we can see the values 2, 3, and 4 that we stored into data-pvar in the 
left-most column.

Now in a dazzling display of computational power, we'll use zig-zag to move 
them:

> (zig-zag data-pvar)
NIL

> (ppp data-pvar :mode :grid :end '(6 6))
0 0 0 0 0 0
0 0 0 0 0 2
0 0 0 0 0 3
0 0 0 0 0 4
0 0 0 0 0 0
0 0 0 0 0 0

Of course, you'll typically use grid communication operators to move many more 
data values around the grid than the three integers we've used here. The 
principles, however, remain the same.

	Front-End/CM Communication

*Lisp includes three types of operators that let you move data quickly between 
the front end and the CM:

	The simplest type is the operator !!, which as we've seen takes a 
single front-end value and "broadcasts" it to every processor in the CM.

	*Lisp also has a set of "global" communication operators that do just 
the opposite: they take a pvar on the CM and turn it into a single front-end 
value.

	Finally, *Lisp has a number of array/pvar conversion functions that 
make it easy for you to move large amounts of data between the front end and 
the CM.

In this section, we'll take a look at examples of the latter two types of 
operators.

	Funnels for Data-Global Communication Functions

The global communication functions all have one feature in common: They take a 
pvar argument, combine the values of that pvar into one value, and then return 
that value to the front end. You can think of these operators as computational 
funnels; they take a large set of values from the CM and combine them into a 
single front-end value.

A good example is *sum, which adds together all the values of a pvar:

> (*defvar numbers (random!! 10))
NUMBERS
> (ppp numbers :end 20)
2 1 8 7 4 5 8 2 1 8 3 7 3 0 9 6 4 9 4 9

> (*sum numbers)
18651

One handy use of *sum is based on the fact that global functions only combine 
values from active processors (processors currently selected by an operator 
such as *when or if!!). If you want to know how many processors are currently 
active, a simple way to find out is to take the *sum of 1:

> (*sum 1)  ;;; on an 8K machine (8192 processors)
8192
> (*when (evenp!! (self-address!!)) ;;; turn off odd processors
		(*sum 1))
4096

Other useful global operations are:

	*max, *min - find the maximum and minimum values of a pvar

> (*max (self-address!!)) ;; Returns highest send address.
8191

	*and, *or - find the logical AND/inclusive OR of the values of a pvar

> (*or t!!) ;; Returns T if any processors are selected
T
> (*when nil!! (*or t!!)) ;; and NIL if none are selected
NIL

	Bulk Data Movement-Array/Pvar Conversions

If you want to move a large amount of data from the front end to the CM or vice 
versa,  you can call the array/pvar conversion functions of *Lisp, which are:

	array-to-pvar - converts an array on the front end to a pvar on the CM

	pvar-to-array - converts a pvar on the CM to an array on the front end

For example, given the array and pvar defined by

> (defvar data-array #(1 2 3 4 5 6))	;;; Front-end array

> (*defvar data-pvar 0)						;;; Empty pvar 
on the CM

we can use array-to-pvar to copy the six elements of data-array into the first 
six values of data-pvar:

> (array-to-pvar	data-array data-pvar :end 6)

> (ppp data-pvar :end 12)
1 2 3 4 5 6 0 0 0 0 0 0

Here the :end keyword argument is used (as with ppp) to specify the send 
address at which the copying of values ends.

We can use pvar-to-array to copy the first three values of data-pvar back into 
data-array, starting at element 3:

> (pvar-to-array	data-pvar data-array :array-offset 3
						:start 0 :end 3)

> (let ((*print-array* t))
	(print data-array))
#(1 2 3 1 2 3)

Here we're using both the :start and :end keywords to specify a range of pvar 
values to be copied. The :array-offset keyword is used to specify element 3 of 
the array as the first element into which a value is copied.

For more examples of these functions, see the entries for them in the *Lisp 
Dictionary.

	Parallel Data Transformation in *Lisp

*Lisp includes operators that allow you to perform large-scale transformations 
of your data. For example, you can use *Lisp operations to take a cumulative 
sum of the values of a pvar across the current processor grid. In this section, 
we'll look at the *Lisp operators that allow you to perform these kinds of 
parallel data manipulations.

The data transformation functions of *Lisp include tools for:

	performing cumulative operations (such as the cumulative sum mentioned 
above)

	copying important pvar values across the processor grid

	ranking  and sorting the values of a pvar

	Parallel Prefixing (Scanning)

Scanning is a transformation in which a cumulative operation is performed on 
the values of a pvar across the currently selected grid. The main scanning 
function of *Lisp is scan!!. The scan!! function has a extensive set of options 
that let you choose from a number of possible scanning operations, such as 
addition or multiplication of values; taking the maximum and minimum of values; 
taking the logical or arithmetic AND, OR, and XOR of values; and even simply 
copying values across the processor grid.

A common use of the scan!! operation is for cumulative summations. For example:

> (ppp (scan!! 2 '+!!) :end 20)
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40

Here, each processor calculates the sum of the values for all processors up to 
and including itself, producing a cumulative sum of the values of the pvar.

The scan!! operator has a keyword argument, :include-self, that lets you 
specify whether each processor will include its own value in the calculation. 
For example, here's the above addition with the :include-self argument of nil:

> (ppp (scan!! 2 '+!! :include-self nil) :end 20)
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38

In this case, each processor calculates the sum of the pvar values for all 
processors preceding but not including itself. As shown in these examples, you 
can use the :include-self argument to "shift" the result of a scan over by one 
processor.

A unique feature of scan!! is that it allows you to select segments of a pvar 
over which independent scans are performed. The scan!! operation uses a 
:segment-pvar argument to select pvar segments.

An example of scan!! with a :segment-pvar argument is:

> (*defvar segments (zerop!! (mod!! (self-address!!) 4)))

> (ppp segments :end 16)
T NIL NIL NIL T NIL NIL NIL T NIL NIL NIL T NIL NIL NIL

> (ppp (scan!! 1 '+!! :segment-pvar segments) :end 16)
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

Every t value in the :segment-pvar argument of scan!! indicates the start of 
another segment, and as you can see the summation is done only within segments.

The scan!! function is a powerful programming tool, and has some surprising 
uses. We'll see some more examples of scan!! in the sample *Lisp functions of 
Chapter .

	Spreading Values across the Grid

An operation related to scanning is spreading. Spreading copies the values from 
one "row" or "column" of the current grid to all rows or columns of the grid. 
(Of course, when you're using processor grids with more than two dimensions, 
the terms "row" and "column" don't really apply, but the principle is the 
same.)

The *Lisp operator for spreading is called spread!!. As an example, let's 
assume that  (self-address!!) currently returns the values shown here:

>  (ppp	(self-address!!)
			:mode :grid
			:end '(8 3)
			:format "~3S ")
0   1   2   3   16  17  18  19
4   5   6   7   20  21  22  23
8   9   10  11  24  25  26  27

and let's say that we want to spread the values in the fourth column to all of 
the columns.
(What this means in terms of the processor grid is that we want to spread 
values from the processors at coordinate 3 of dimension 0 to all processors 
along dimension 0.)

The following call to spread!! will do this for us:

> (ppp (spread!! (self-address!!) 0 3) ;; Dimension 0, Coord. 3
			:mode :grid
			:end '(9 3)
			:format "~3S ")
3   3   3   3   3   3   3   3   3
7   7   7   7   7   7   7   7   7
11  11  11  11  11  11  11  11  11

The spread!! function is most useful in combination with communication and 
scanning operators, because it allows you to quickly spread important values 
across the processor grid.

	Sorting Pvar Values

One other useful transformation operator is sort!!, which sorts the values of a 
numeric pvar in ascending order. For example:

> (*defvar random-numbers (random!! 10))
RANDOM-NUMBERS

> (ppp random-numbers :end 20)
3 3 5 8 2 8 9 3 5 5 4 4 1 2 7 9 8 6 9 7 

> (*when (<!! (self-address!!) 20)
	(ppp (sort!! random-numbers '<=!!) :end 20))
1 2 2 3 3 3 4 4 5 5 5 6 7 7 8 8 8 9 9 9
NIL

Here I've used *when to select the first 20 values of the random-numbers pvar, 
and then called sort!! to return a copy of those values sorted in ascending 
order.

If you prefer to write your own sorting routines, *Lisp also includes an 
operator called rank!! that simply returns a numerical ranking of the values of 
a pvar. For example:

> (*when (<!! (self-address!!) 20)
	(ppp (rank!! random-numbers '<=!!) :end 20))
3 4 8 14 1 15 17 5 9 10 6 7 0 2 12 18 16 11 19 13

	Configuration Operators

We've seen that the shape of the current processor grid determines the size and 
shape of your pvars. *Lisp includes several functions and macros that let you 
control the size and shape of the current processor grid, as well as tools that 
let you define multiple grids that can be used together in the same program. 
You've already seen one of these operators: *cold-boot. In this section we'll 
take a look at these operators, and see how you can use them in your programs 
to control the current configuration of the CM.

	Defining the Initial Grid Configuration - *cold-boot

Whenever you initialize *Lisp with the function *cold-boot, you're also 
choosing the size and shape of the current processor grid. The *cold-boot 
function has a keyword argument, :initial-dimensions, that determines the 
initial shape and size of the processor grid.

For example, if you wanted to start off with a cube-shaped grid of processors, 
64 processors on a side, you could type the following:

> (*cold-boot :initial-dimensions '(64 64 64))
8192
(64 64 64)

This gives you a rather mind-boggling number of processors to work with-more 
than a quarter million, as a matter of fact.

> *current-cm-configuration*
(64 64 64)
> *number-of-processors-limit*
262144

For Simulator Users: I don't recommend trying this example on the *Lisp 
simulator! The number of processors that the simulator can handle is limited 
only by the speed and memory capacity of your computer, but this means that the 
more processors you use, the slower your program will run. A better example for 
simulator users is:

> (*cold-boot :initial-dimensions '(8 8 8))
Thinking Machines Starlisp Simulator.  Version 18.0
1
(64 64)

	Where Did the Extra Processors Come From?

Notice that even though I've requested a large number of processors in these 
examples, many more than the number of physical processors available in the 
machine, the actual number of physical processors hasn't changed-the first 
argument returned by *cold-boot is still 8192. (As in previous *cold-boot 
examples, I'm assuming an 8K CM.) By requesting a larger number of processors 
than are present in the physical hardware of the CM, you automatically tell the 
CM to use virtual processors.

Whenever you request a number of processors that is larger than the actual 
number of physical processors within the CM, each physical processor simulates 
the operations of two or more virtual processors (or VPs, as they are commonly 
called).

This simulation takes place automatically and transparently. The only effects 
you're likely to notice are a change in execution speed and a reduction in the 
total number of pvars you can create. (When you use virtual processors, more 
than one pvar value is stored in the memory of each physical processor, so your 
pvars take up more memory.)

	Defining Custom Configurations - VP Sets

Once you start working with data sets of different sizes, you'll want to make 
use of this ability to define processor grids of various shapes and sizes, 
because the shape and size of the current processor grid determines the shape 
and size of your pvars.

*Lisp allows you to define special data objects called virtual processor sets 
(VP sets) that describe particular configurations of processors. You can then 
use *Lisp operations to select these configurations when you need them.

For example,

> (def-vp-set big-square '(256 256))

defines a two-dimensional VP set called big-square, which describes a 
two-dimensional grid of processors of size 256 by 256. Once you've created a VP 
set such as this, you can start using it to define pvars with the same size and 
shape:

> (*defvar big-square-pvar 1 nil big-square)
BIG-SQUARE-PVAR
> (*defvar another-square-pvar (random!! 20) nil big-square)
ANOTHER-SQUARE-PVAR

You can even save a step and define both the VP set and the pvars at the same 
time. For example, the three examples above could be replaced by the single 
form:

(def-vp-set big-square '(256 256)
	  :*defvars	'((big-square-pvar 1)
					  (another-square-pvar (random!! 20)))

For the Curious: Why are they called VP "sets"? Because VP sets are used to 
determine the size and shape of pvars. For each VP set that you define there is 
an associated "set" of pvars that have the same size and shape. It's the 
combination of a particular arrangement of virtual processors and a group of 
pvars whose shape is specified by that arrangement that we mean by the term "VP 
set". The def-vp-set operator makes this relationship explicit, by allowing you 
to define both a VP set and its associated pvars at the same time.

	Default and Current VP Sets

How do you use these VP sets, once you've defined them? In a sense, you've 
already been using them, ever since you started up *Lisp. When you *cold-boot 
*Lisp, a special default VP set is defined that represents whatever processor 
grid you've chosen to start with (that is, whatever grid size and shape you've 
specified via the :initial-dimensions argument).

If you always used the default VP set and never created VP sets of your own, 
you probably wouldn't even notice that VP sets existed at all. However, once 
you've defined your own VP sets, you can use them to switch between different 
processor configurations within a single *Lisp program.

At any time, there is always one VP set that is the current VP set, the one 
that determines how the processors of the CM are currently arranged. You make a 
particular VP set the current one by selecting it. Unless you specify 
otherwise, all pvars are created with the shape and size of the current VP set.

The default VP set is selected automatically for you by *cold-boot. You can 
then use the VP set operations of *Lisp to temporarily or permanently select a 
VP set of your own.

	Selecting VP sets

When you want to use a particular VP set, such as the big-square defined above, 
you can either select it temporarily (for the duration of a piece of code), via 
the macro *with-vp-set:

> (*cold-boot :initial-dimensions '(128 128))
8192
(128 128)

;;; Display the shape and size of the current processor grid
> (list	*current-cm-configuration* 
			*number-of-processors-limit*)
((128 128) 16384)

;;; Display shape and size of the grid with big-square selected
> (*with-vp-set big-square
	  (list	*current-cm-configuration*
				*number-of-processors-limit*))
((256 256) 65536)

;;; When *with-vp-set exits, the old grid is restored
> (list	*current-cm-configuration* 
			*number-of-processors-limit*)
((128 128) 16384)

or you can select it permanently (until you select another VP set), by using 
the set-vp-set function:

> (set-vp-set big-square)
#<VP-SET Name: BIG-SQUARE, Dimensions (256 256) ... >

;;; Display shape and size of VP set selected by set-vp-set
> (list *current-cm-configuration*
			*number-of-processors-limit*)
((256 256) 65536)

	Two Important VP Set Variables

There will often be times that you'll want to know exactly which VP set is the 
current one, as well as which VP set is the default defined by *cold-boot. For 
this reason, *Lisp maintains two important global variables that keep track of 
these details.

The *Lisp variable *default-vp-set* is always bound to the default VP set 
defined for you by *cold-boot:

> *default-vp-set*
#<VP-SET Name: *DEFAULT-VP-SET*, Dimensions (128 128) ... >

This variable is automatically set each time you call *cold-boot, but otherwise 
its value doesn't change.

The variable *current-vp-set* is always bound to the currently selected VP set, 
and its value changes every time the current VP set changes:

> *current-vp-set*
#<VP-SET Name: BIG-SQUARE, Dimensions (256 256) ... >

> (set-vp-set *default-vp-set*)
#<VP-SET Name: *DEFAULT-VP-SET*, Dimensions (128 128) ... >

> *current-vp-set*
#<VP-SET Name: *DEFAULT-VP-SET*, Dimensions (128 128) ... >

You can compare these variables to test whether the current VP set is the 
default:

> (defun default-p ()
	(eq *current-vp-set* *default-vp-set*))

> (set-vp-set big-square)
#<VP-SET Name: BIG-SQUARE, Dimensions (256 256) ... >
> (default-p)
NIL
> (set-vp-set *default-vp-set*)
#<VP-SET Name: *DEFAULT-VP-SET*, Dimensions (128 128) ... >
> (default-p)
T

VP sets are an advanced *Lisp tool, and there are many more uses for them than 
we have room to describe here For an example of the use of VP sets, see Section 
 in Chapter .

	Summary: *Lisp as a Language

Here's a quick review of what we've covered in this chapter:

	Processor selection operators, such as *when and if!!, let you increase 
the power of your *Lisp programs by restricting the set of processors that are 
currently active.

	Communications operators, such as *pset and *news, let you move data 
between processors within the CM in the manner that is most efficient for your 
programming needs.

	Front-end/CM communication operators such as *sum and array-to-pvar let 
you quickly move large amounts of data between the front end and the CM.

	Data transformation operators such as scan!!, spread!!, and sort!! 
allow you to design just the kinds of data transformations you need.

	Configuration operators such as *cold-boot, def-vp-set, and with-vp-set 
give you control of the shape of the current processor grid, and, in so doing, 
let you specify the size and shape of your pvars.

That's all the main parallel programming tools of *Lisp in a nutshell. In the 
next chapter, we'll look at the error-handling features of *Lisp, and show how 
you can use the Lisp debugger to examine and diagnose bugs you encounter while 
writing *Lisp programs.



Chapter 4: When Things Go Wrong

No introductory guide can account for the unexpected. Even if you follow the 
instructions of this document to the letter, typing in everything exactly as 
shown, you may still receive unexpected warnings and error messages, or 
suddenly find yourself facing an imposing display of debugger information. The 
purpose of this chapter is to show you the types of warnings and errors that 
you can expect to see, and to show how you can deal with them.

Note: The warning messages and debugger examples shown below are taken from the 
Sun Common Lisp version of *Lisp. Other versions of *Lisp may have different 
methods of displaying and handling errors, but the essential points will still 
apply. Consult your Lisp environment's documentation for more information on 
the debugger and error-checking features it provides for you.

	Warning Messages

Warnings take many forms. Some are messages from the Lisp system that you're 
using, such as this one, which tells you the Lisp garbage collector is active:

;;; GC: 174988 words [699952 bytes] of dynamic storage in use.
;;; 644210 words [2576840 bytes] of free storage available.

For the Curious: If you prefer not see such warning messages, many Lisp systems 
will let you turn them off by setting an appropriate global variable. For 
example, in Sun Common Lisp you can turn off GC warnings by typing (setq 
lcl::*gc-silence* t). For Lucid Common Lisp on VAX front ends, the 
corresponding command is (setq sys::*gc-silence* t).

Other warnings come from *Lisp itself. Most of the *Lisp warnings that you're 
likely to see will come from the *Lisp compiler. Depending on the settings of 
certain *Lisp compiler variables, you may see a warning when you compile a 
function. For example:

> (defun simple (x) (+!! x 2))
> (compile 'simple)
;;; Warning: *Lisp Compiler: While compiling function SIMPLE:
;;;          The expression (+!! X 2) is not compiled because
;;;          the compiler cannot find a declaration for X.

For now, you can pretty much ignore such warnings. These messages are simply 
telling you that the *Lisp compiler lacks information that it requires to fully 
compile a piece of *Lisp code. Your functions are still being compiled, though 
perhaps not as efficiently as possible. (We'll return to this in more detail 
when we look at the *Lisp compiler in Chapter .)

	Error Messages

Errors are just as varied as warnings, and range from simple typing mistakes, 
such as

> (pront 'oops!)
>>Error: The function PRONT is undefined.
SYMBOL-FUNCTION:
   Required arg 0 (S): PRONT
:C  0: Try evaluating #'PRONT again
:A  1: Abort to Lisp Top Level
->

to more detailed messages triggered by supplying incorrect arguments to a 
function:

> (/!! 3 0)
>>Error: In interpreted /!!.
	The result of a (two argument) float /!! overflowed.
	There are 8192 selected processors,
	8192 processors have an error.
	A SINGLE-FLOAT temporary pvar stored at location 458752
	caused the error.
*LISP-I::/!!-2:
...
:A  : Abort to Lisp Top Level
->

	Recovering from Errors

While you're learning to use *Lisp, you'll probably just want to exit from the 
debugger and get back to the *Lisp prompt immediately. There is usually a 
simple command that you can type to abort from the debugger and get back to the 
top-level prompt. In the Lucid version of *Lisp, the command is

-> :A
Abort to Lisp Top Level
>

When You Abort, Remember to (*warm-boot)

But simply aborting from the debugger is not enough. Remember, you're 
programming on two machines: your front end and the CM. Aborting from the 
debugger resets your front end and returns you to the top-level Lisp prompt, 
but it does not automatically reset the state of the CM as well. To do this, 
you must also call the *Lisp operator

> (*warm-boot)

The *warm-boot command resets the internal state of the CM and performs other 
minor housecleaning operations that return both front end and CM to a normal, 
ready-to-run state.

You should get into the habit of calling *warm-boot whenever you abort from the 
debugger, because otherwise the CM may be left in a confused state that will 
prevent your code from running correctly. Even worse, you may get spurious 
error messages from otherwise error-free code; these errors can be very hard to 
trace, precisely because the error lies not in your code, but in the state of 
the CM. As an example of what can happen, try this:

> (*sum 1)	;; NOTE: This example was run on an 8K CM
8192

> (*when (evenp!! (self-address!!)) (break))
>>Break: break
EVAL:
 Required arg 0 (EXPRESSION): (*WHEN (EVENP!! (SELF...
:C	0: Return from Break
:A	1: Abort to Lisp Top Level
-> :a
Abort to Lisp Top Level

> (*sum 1)
4096

Here we've used the Common Lisp function break to simulate an error within the 
body of the *when form. The *when in this example deselects half of the 
processors. When you abort from the debugger, these processors remain 
deselected, as the second call to *sum shows.

This is easily corrected by calling *warm-boot:

> (*warm-boot)
> (*sum 1)
8192

Whenever you encounter a bizarre inconsistency of this sort while running your 
code, it's a good idea to try calling *warm-boot to reset the CM, and then try 
running your code again.

For More Persistent Errors, Try (*cold-boot)

Occasionally, you'll encounter an error message that persists even after you've 
called *warm-boot. For these sorts of persistent errors, you can try calling

> (*cold-boot)

This will reinitialize both *Lisp and the CM, performing a much more thorough 
housecleaning than *warm-boot. If the error is related to permanent pvars-which 
are reallocated when you call *cold-boot-you may want to try typing

(*cold-boot :undefine-all t)

The :undefine-all argument to *cold-boot wipes out every pvar and VP set in the 
*Lisp environment, leaving you with a clear field in which to work. (By the 
way, this will also wipe out any pvars and VP sets defined by your *Lisp 
programs-you will probably need to reload your *Lisp code to have it run 
correctly.)

If an obscure error persists even after this, you may want to ask your systems 
administrator or applications engineer to help you diagnose the problem.

	*Lisp Error Checking

*Lisp provides a global variable, *interpreter-safety*, that controls the 
amount of error checking that is performed by the *Lisp interpreter. This 
affects the kinds of error messages that you see when you run your code as well 
as the speed with which your interpreted code will run. (There are similar 
variables for the *Lisp compiler; we'll look at them in Chapter .)

The value of *interpreter-safety* must be an integer between 0 and 3. The 
effects of each of these values are:

	0		Most run-time error checking is disabled.
	1		Minimal run-time error checking is performed, and an 
error may not be
			signaled at the exact point in your code at which it 
occurred.
	2		This setting is reserved for future expansion; don't 
use it.
	3		Full run-time error checking. Errors are signaled 
immediately.

The default value of *interpreter-safety* is 3, but you can set 
*interpreter-safety* yourself to select the level of error checking that you 
prefer. For example, to turn off interpreter error checking, type

> (setq	*interpreter-safety* 3)

Roughly, 3 means "full error checking," while 0 means "no error checking." This 
means that you should run your code with an *interpreter-safety* level of 3 
while debugging, and at an *interpreter-safety* of 0 once it is running 
correctly to get the best speed from your interpreted code. (Note: To obtain 
the fullest possible speed from your code, you'll want to declare and compile 
it, as described in Chapter .)

An *interpreter-safety* level of 1 is useful mainly for testing nearly 
completed code, because when errors occur you are given an indication of the 
fact that they occurred, but your code is not slowed down to the point where 
the exact location of the error can be indicated. At this safety level, an 
error detected on the CM will only be reported the next time you try to read a 
value from the CM. For example:

> (setq *interpreter-safety* 1)

> (/!! 3 0)	;; The error occurs here, but is not signaled...
#<FLOAT-Pvar 5-32 *DEFAULT-VP-SET* (32 16)>

> (+!! 2 3)	;; Still not reading a value from the CM...
#<FIELD-Pvar 11-3 *DEFAULT-VP-SET* (32 16)>

> (*sum 1)	;; Upon reading a value, the error is signaled:
>>Error: The result of a (two argument) float /!! overflowed
CMI::WAIT-UNTIL-FEBI-OUTPUT-FIFO-NOT-EMPTY:
:A  0: Abort to Lisp Top Level
->

	Common Errors

Now let's take a quick look at some common errors that you may encounter while 
learning to use *Lisp. This is by no means an exhaustive list, but it should 
give you an idea of how to tackle the errors that you do encounter.

	Executing *Lisp Code without Having a CM Attached

Unless you're using the *Lisp simulator, you must have a CM attached in order 
to execute *Lisp code. It's easy to tell when you're not attached to a CM: 
you'll find yourself getting "bus errors" from perfectly legal *Lisp code.

For example:

> (cm:detach) ;; Detach from the CM
> (+!! 2 3 4)
>>Trap: Interrupt: bus error
CMI::PTR-REF-LOW:
   Required arg 0 (PTR): NIL
:A	Abort to Lisp Top Level
-> (cm:attached)
NIL
NIL

As shown here, you can call the Paris function cm:attached to determine whether 
a CM is currently attached. (See the discussion of cm:attached in Appendix .)

Another common error is caused by attaching to a CM, but neglecting to call 
*cold-boot. Until you call *cold-boot for the first time, you will not be able 
to execute your *Lisp code.

> (cm:attach)
8192
> (+!! 2 3 4)
>>Error: Timed out on safe FIFO read.
CMI::WAIT-UNTIL-FEBI-OUTPUT-FIFO-NOT-EMPTY:
:A	0: Abort to Lisp Top Level
->

Both types of errors are easily corrected by calling *cold-boot. The *cold-boot 
operator automatically attaches you to a CM if you're not already attached, and 
it initializes both *Lisp and the CM so that you can begin running code on the 
machine.

	Running Out of CM Memory

There are two kinds of CM memory: the stack and the heap. The heap is used for  
permanent pvars, and the stack is used for local and temporary pvars. If you 
allocate so many pvars in either kind of memory that there isn't room for more, 
you'll get an error.

Running Out of Stack Memory

For example, stack pvars are allocated by *let, *let*, and by nearly all the 
functions in *Lisp that return a pvar. You're not likely to run out of stack 
memory by using either *let or *let*, because these operators automatically 
deallocate any stack pvars they create. However, if you call to a *Lisp 
function within a loop, you can easily find yourself running out of stack 
memory:

> (dotimes (i 10000) (+!! 3.14 2.17 9.99))
>>Error: You have run out of CM memory
	while trying to allocate 32 bits of stack.
CMI::TRY-TO-GET-MORE-CM-STACK-MEMORY:
	Required arg 0 (NUMBER-OF-BITS-TO-ALLOCATE): 32
:A	0: Abort to Lisp Top Level

Each time the +!! call is executed, it allocates a temporary pvar on the stack. 
These temporary pvars steadily pile up on the stack until there is no more 
stack space left. To recover from this kind of error, abort from the debugger 
and call *warm-boot, which will clear out the stack.

For the Curious: An easy way to prevent this kind of error is to make sure that 
all your calls to *Lisp functions are made within *Lisp operators that 
automatically clear the stack after they have finished executing, for instance 
*set and *let. For example, try:

> (*defvar temp-pvar 0.0)
> (dotimes (i 10000) (*set temp-pvar (+!! 3.14 2.17 9.99)))
NIL

*Lisp code that you write will typically be structured so that this is the 
case-that is, all pvar computations will take place within the scope of *Lisp 
operators that clear the stack. However, if you find yourself running out of 
stack space, you should check your code to make sure you are not repeatedly 
allocating stack pvars that never get cleared away.

A complete list of *Lisp operators that automatically clear the stack can be 
found in the entry for *defun in the *Lisp Dictionary.

A stack-related resource you may find yourself running short of is temporary 
pvars:

> (dotimes (i 1000) (+!! 0 1 2))
>>Error: You have run out of temporary Pvars.
	You must now do a *COLD-BOOT.
*LISP-I::POP-LOCAL-ERROR:
:A  0: Abort to Lisp Top Level
->

When you get an error like this, you haven't necessarily run out of memory, but 
you have run out of the data structures used to keep track of the stack memory 
you allocate. At this point, you may be able to get away with simply calling 
*warm-boot to restore the pool of free temporary pvars, but if not you can 
always call *cold-boot to recover from this error. (In the same way, you can 
find yourself running short of VP set and geometry data objects-the same 
solution applies in these cases.)

Running Out of Heap Memory

Heap pvars are allocated by the operations *defvar and allocate!!. You're not 
likely to exhaust heap memory by using *defvar, but the main purpose of 
allocate!! is to allow you to rapidly allocate as much of the heap as you want 
for pvars. You can easily use up all the available heap memory by calling 
allocate!! indiscriminately:

> (defvar pvar-list nil)

> (loop (push (allocate!! 3.14159) pvar-list))
>>Error: You ran out of CM memory
	while trying to allocate 32 bits on the heap.
CMI::ALLOCATE-HEAP-FIELD-ADDRESS-AND-CM-MEMORY:
	Required arg 0 (NUMBER-OF-BITS-TO-ALLOCATE): 32
:A	0: Abort to Lisp Top Level
->

The easiest way to recover from heap memory errors is to call *cold-boot, which 
destroys all pvars created by allocate!!, and then reallocates pvars you have 
defined by *defvar.

Another way to recover is to use *deallocate to remove some of the heap pvars 
you have defined. In the above example, the allocated heap pvars are stored in 
a list, so it is easy to deallocate them:

> (dolist (pvar pvar-list) (*deallocate pvar) (pop pvar-list))
NIL

Tracing Stack Memory Use

Even if your program doesn't contain simple loops like those shown above, it 
may still run out of memory if it allocates a large number of pvars, or 
allocates pvars that contain very large data structures. In particular, if you 
get an "out of stack memory" error, you'll want to check your program to see 
where it is allocating the most stack memory.

*Lisp includes a function, trace-stack, that you can use to trace the stack 
memory usage of your program, and thereby determine what parts of your code are 
using the most stack memory. For example, let's trace the function

> (defun trace-test (a b c)
	(*!! a (+!! b c)))

We can use trace-stack to trace the amount of stack memory used by this 
function:

> (trace-stack :init)
Stack tracing is now on in :TRACE mode.
Current stack level is 1536.
Maximum stack limit is 1536.
1536
1536
> (trace-test 9 3 2)
#<FIELD-Pvar 9-7 *DEFAULT-VP-SET* (128 64)>

> (trace-stack :reset)
Stack tracing is now on in :BREAK mode.
Current stack level is 1536.
Maximum stack limit is 1554.
1536
1554

This records the amount of stack memory used by the call to trace-test. We can 
then use trace-stack to cause a continuable error whenever stack usage reaches 
or exceeds this limit:

> (trace-test 9 3 2)
>>Error: Stack has reached/exceeded traced maximum of 1554.
         Stack is now at 1554.
*LISP-I::MAX-STACK-LEVEL-CHECK:
:C  0: Continue until next stack increase.
:A  1: Abort to Lisp Top Level
-> :a
Abort to Lisp Top Level
Back to Lisp Top Level

And when we're finished with the stack tracing facility, we can switch it off:

> (trace-stack :off)
Stack tracing is now off.
Current stack level is 1554.
Maximum stack limit is 1554
1554
1554

For more information, see the entry for trace-stack in the *Lisp Dictionary.

Displaying CM Memory Use

*Lisp also includes *room, a parallel equivalent of Common Lisp's room 
function. You can use *room to get a general description of CM memory use:

> (*room)
*Lisp system memory utilization

Vp Set *DEFAULT-VP-SET*, (32 16)
  Stack memory usage   : 11
  Heap memory usage    : 0
  *Defvar memory usage : 8
  Overhead             : 10
  Total for Vp Set     : 29

Overall totals
Stack memory usage   : 11
Heap memory usage    : 0
*Defvar memory usage : 8
Overhead             : 18
Total                : 37

11
0
8
18

The *room function is also described in more detail in the *Lisp Dictionary.

	Functions That Don't Promote Scalars to Pvars

Most *Lisp operations that accept pvars as arguments also accept scalars of the 
same type, and automatically promote them to pvars. There are a few functions, 
however, that don't. When one of these functions encounters a scalar value 
where it expects a pvar, it will warn you that the scalar argument should be a 
pvar:

> (describe-pvar 3)
>>Error: 3 is not a Pvar.
DESCRIBE-PVAR:
	Required arg 0 (PVAR): 3
	Optional arg 1 (STREAM): #<Stream SYNONYM-STREAM 30B2BE6>
:A	0: Abort to Lisp Top Level

You'll also get an error of this sort if you supply a scalar value of an 
incorrect type. For example, arithmetic operations such as +!! only coerce 
numeric scalars to pvars:

> (+!! #\c 3)
>>	Error: An argument to +!!, having value #\c,
	is not a pvar, but should be
*LISP-I::NEW-PVAR-CHECK:
   Required arg 0 (PVAR): #\c
   Required arg 1 (FUNCTION-NAME): +!!
:C  0: Test the assertion again
:A  1: Abort to Lisp Top Level

You can recover from these errors simply by aborting from the debugger, calling 
*warm-boot, and then calling the function again with a proper pvar argument.

This kind of error can also occur when you have compiled a function with a 
declaration restricting its arguments to pvars. Scalar arguments passed to 
these compiled functions will not be promoted. For example:

> (defun test (a)
	(declare (type single-float-pvar a))
	(+!! a a))
> (compile 'test)

> (test 3)
>>Trap: Interrupt: bus error
TEST:
	Required arg 0 (A): 3
:A	0: Abort to Lisp Top Level
->

	Obscure Hardware and Software Errors

Some error messages, caused either by unusual CM states or real hardware 
errors, are downright impenetrable for the average user:

>>Error: Detected CM Exception while waiting for data from CM.
The following status message might help identify the problem.
   There are 28. CM and/or SPRINT chips reporting errors.
   This usually indicates an illegal memory reference.
   The cause could be an invalid field-id or incorrect
   length argument in a PARIS instruction.
CMI::WAIT-UNTIL-FEBI-OUTPUT-FIFO-NOT-EMPTY:
...
<Half a page of continuation options>
...
:A  0: Abort to Lisp Top Level
->

Your best bet in handling these kinds of obscure errors is to abort from the 
debugger, call *warm-boot or *cold-boot, and try running your code again. If 
errors of this kind persist, they should be reported to your systems manager or 
applications engineer for correction.

	Using the Debugger

Once you feel comfortable working with *Lisp, you'll want to take a closer look 
at the debugger to see what features it offers you. Let's take a quick look at 
a few debugger commands that you may find helpful in debugging your code.

As an specific example, type

> (/!! 1.0 (self-address!!))

This causes a floating-point overflow due to the division by zero for processor 
0.

Assuming an 8K CM, this will producing the following debugger output:

>>Error: In interpreted /!!.
	The result of a (two argument) float /!! overflowed.
	There are 8192 selected processors,
	1 processor has an error.
	A pvar of type SINGLE-FLOAT caused the error.
*LISP-I::/!!-2:
   Required arg 0 (A): #<FLOAT-Pvar 3-32 ... >
   Required arg 1 (B): #<FIELD-Pvar 5-13 ... >
:C	0: Ignore error.
	1: Ignore Error.
	2: Display Processors With Error.
	3: Display Value in Processors with Error.
	4: Display Selected Processors.
	5: Display Value in Selected Processors.
	6: Display Value in All Processors.
	7: *Set Value in Processors with Error.
:A	8: Abort to Lisp Top Level
->

The debugger display includes:

	the error that occurred (a floating-point overflow)

	the number of processors that are currently selected (8192)

	the number of those processors that signaled the error (1)

	the type of pvar that caused the error (single-float)

	the name of the internal function in which the error occurred 
(*lisp-i::/!!-2)

	the arguments to that function (a float pvar and a field pvar)

	a list of debugging actions, each with an associated command to invoke 
it

At this point, there are a number of things that you can do:

	You can type the debugger command :c to continue, ignoring the overflow 
error.

	You can type :b for a backtrace of the chain of function calls leading 
to the error:

-> :b
*LISP-I::/!!-2 <- EVAL <- SYSTEM:ENTER-TOP-LEVEL

	You can type :n and :p to move up and down the chain of calls:

-> :n
EVAL:
	Required arg 0 (EXPRESSION):
		(/!! (!! 1.0) (SELF-ADDRESS!!))
-> :p
*LISP-I::/!!-2:
	Required arg 0 (A): #<FLOAT-Pvar 3-32 ... >
	Required arg 1 (B): #<FIELD-Pvar 5-13 ... >

	You can use the supplied debugging options to view the values contained 
in the processors that signaled the error:

-> 3
Display Value in Processors with Error.
    0 = #<FLOAT :PLUS-INFINITY>

>From this display you see the value in each processor that signaled an error. 
In this case, there was only one, processor 0, whose send address of 0 caused 
the division to overflow, returning a result of floating-point infinity.

	And as we have already seen, you can type :a to abort back to the Lisp 
prompt.

-> :a
Abort to Lisp Top Level
Back to Lisp Top Level
> (*warm-boot)
NIL

Your debugger will have many more commands than there is room to discuss here. 
You can use the command :h from within the debugger to see a list of the 
possible commands that you can use. Also, consult the documentation for your 
Lisp development system for more information about the debugger and the tools 
it offers you for debugging your code.

	Summary: Find That Bug and Step on It!

In this chapter, we've seen

	some of the types of warning and error messages displayed by *Lisp

	the most common error messages you can expect to see, and how to handle 
them

	the kinds of information displayed by the Lisp debugger

	the tools that the debugger gives you for diagnosing errors

	the basic method for exiting from the debugger: abort and *warm-boot

	the ways in which *warm-boot and *cold-boot help you recover from 
errors

	the *Lisp variable *interpreter-safety*, which controls the display of 
errors by the *Lisp interpreter

Now that we've seen some of the ways in which your code might break down, let's 
take a look at the tools you can use to make it run like a dream. In the next 
chapter, we'll look at the *Lisp compiler, and see how you can use it to 
compile your *Lisp code into fast and efficient Lisp/Paris instructions.



Chapter 5: Declaring and Compiling *Lisp Code

Depending on your interests and inclinations, you may begin writing your *Lisp 
code with an eye to immediately compiling it, or you may leave the step of 
declaring and compiling your code until after you have it running in an 
interpreted form. No matter what your coding style happens to be, you'll need 
to declare your code properly to have it compile completely. In this chapter 
we'll look both at the *Lisp compiler itself, and at the kinds of type 
declarations that are used in *Lisp.

You'll also want to refer to Chapter 4, "*Lisp Type Declaration," of the *Lisp 
Dictionary, which contains a complete and detailed set of guidelines for 
properly declaring your code.

	The *Lisp Compiler

The *Lisp compiler is an extension of the Common Lisp compiler, and is invoked 
automatically whenever you compile a section of Lisp code.

*Lisp functions and macros are compiled exactly as they are in Common Lisp:

	by calling the Common Lisp function compile to compile a specific 
function:

(compile 'add-mult!!)

	by calling the Common Lisp function compile-file to compile a file of 
code:

(compile-file "starlisp-code.lisp")

	by whatever method you usually use to compile Lisp code.

Depending on the Lisp programming tools your editor provides, there may be a 
special keystroke you can use to compile a function definition from within the 
editor. In Emacs-style editors this keystroke is commonly Ctrl-Shift-C or 
Meta-Shift-C. Check the manual for your editor for more information.

Just as in Common Lisp, it is not necessary to compile your *Lisp code before 
you run it, because uncompiled code is automatically handled by the *Lisp 
interpreter.  However, you won't see the best performance from your code if you 
don't compile.

	What the *Lisp Compiler Does

The *Lisp compiler is different from most standard compilers. It doesn't turn 
your *Lisp code directly into machine-language instructions. Instead, the *Lisp 
compiler converts your code into a mixture of Common Lisp code and calls to 
Paris, the low-level programming language of the CM. This code is then passed 
through the Common Lisp compiler to be converted into machine code.

*Lisp is not a strongly typed language, but Paris is. Thus, for the *Lisp 
compiler  to convert your *Lisp code into Lisp/Paris instructions, you must 
supply a complete type declaration for each parallel variable, function 
argument, and returned value in your code. You must also provide declarations 
for Common Lisp variables and expressions that are used within *Lisp 
expressions.

You should take the time to declare your *Lisp code so that it can be compiled 
completely for a number of reasons:

	Compiled *Lisp code executes much faster than interpreted *Lisp code.

	Compiled *Lisp code is more efficient:

	it uses less CM memory for temporary variables

	it takes advantage of specialized Paris operations to combine a number 
of *Lisp operations into a single Paris instruction

	it eliminates the type-checking overhead of interpreted *Lisp code

	Compiler Options

The *Lisp compiler has many options and parameters that you can use to control 
the way your code is compiled. This section describes two compiler parameters, 
*warning-level* and *safety*, that will be very important to you in learning to 
use the compiler.

	Compiler Warning Level

You can instruct the *Lisp compiler to warn you if it encounters a section of 
*Lisp code that it cannot fully compile, because of missing declarations or 
other reasons. The value of the global variable *warning-level* determines the 
kind and number of warnings that the compiler displays. The legal values for 
*warning-level* are:

:high		Detailed warnings are displayed whenever code cannot be fully 
compiled.
:normal		Warnings are only displayed for inconsistencies in type 
declarations, as
			when arguments to a function are not of the correct 
type.
:none		No warning messages are displayed.

The default value for *warning-level* is :normal, but while you're learning to 
use the compiler, it is better to leave it set it to :high:

> (setq *warning-level* :high)

	Compiler Safety Level

You can also instruct the *Lisp compiler to insert error-checking statements in 
the code that it produces. The value of the global variable *safety* determines 
the amount of error-checking code that is added, and must be an integer from 0 
to 3. The effects of each of these values are:

0		No error-checking code is included.
1		Limited error-checking code is included, so an error may not be 
signaled
		at the exact point in your code at which it occurred.
2		Run-time safety control. See description of 
*immediate-error-if-location*
		below.
3		Full error-checking code is included, so that an error will 
always be signaled
		at the exact point in your code at which it occurred.

Roughly speaking, the higher the value of *safety*, the more error-checking 
code is included. This means that you should compile your code at a *safety* 
level of 3 while debugging, and compile at a *safety* level of 0 when you want 
to execute your code at full speed. Just as with *warning-level*, you can 
change the value of *safety* by using setq:

> (setq *safety* 3)  ;;; Full safety level

When your *Lisp code is compiled at a *safety* level of 2, you can choose at 
run time between the effects of levels 1 and 3. This allows you to choose the 
level of error checking that you want without the need to recompile your code. 
The effect of *safety* level 2 is controlled by the global variable 
*immediate-error-if-location*.

If *immediate-error-if-location* is:

t		Errors are signaled immediately, as with *safety* level 3.
nil		Errors may not be signaled immediately, as with *safety* level 
1.

You can change the value of *immediate-error-if-location* at any time:

> (setq *immediate-error-if-location* t)	;;; Full safety

	Other Compiler Options

Along with *safety* and *warning-level*, there are a number of other compiler 
options that you can modify to control the manner in which your *Lisp code is 
compiled. Most of these options can safely be ignored for right now, but you 
will want to know how to examine and change them. The function

(compiler-options)

displays a menu of the current compiler options, along with their settings. You 
can then modify each of these settings interactively. You can also change any 
of the compiler's options by changing the value of a global variable (as shown 
for *warning-level* and *safety* above).

For the Curious: The full set of compiler options is described in Chapter 5, 
"*Lisp Compiler Options," of the *Lisp Dictionary.

	Displaying Compiled Code

One of the best ways to see the effect of the *Lisp compiler on your code is to 
compile it in such a way that the Lisp/Paris form of the code is displayed.

Displaying All Compiled Code

The simplest way to do this is by typing

> (setq slc::*show-expanded-code* t)

The global variable slc::*show-expanded-code* controls whether or not the *Lisp 
compiler automatically displays each piece of Lisp/Paris code that it 
generates. For example, with  slc::*show-expanded-code* set to t, when you 
compile the function

> (defun test (pvar1 pvar2 pvar3)
    (declare (type single-float-pvar pvar1 pvar2 pvar3))
    (*!! (+!! pvar1 pvar2) pvar3))

the following expanded code is displayed:

(LET*	((SLC::STACK-FIELD (CM:ALLOCATE-STACK-FIELD 32))
		 (#:+*!!-INDEX-2 (+ SLC::STACK-FIELD 32)))
	(DECLARE (TYPE SLC::CM-ADDRESS
					SLC::STACK-FIELD #:+*!!-INDEX-2))
	(DECLARE (IGNORE #:+*!!-INDEX-2))

	;; (*!! (+!! pvar1 pvar2) pvar3).
	(CM:F-ADD-MULT-1L SLC::STACK-FIELD
		(PVAR-LOCATION PVAR1) (PVAR-LOCATION PVAR2)
		(PVAR-LOCATION PVAR3) 23 8)

	(SLC::ALLOCATE-TEMP-PVAR
		:TYPE :FLOAT :LENGTH 32 :BASE SLC::STACK-FIELD
		:MANTISSA-LENGTH 23 :EXPONENT-LENGTH 8))

The important code to notice here is the commented center section-I've set it 
off with extra space to make it easier to read. As you can see, the *Lisp 
compiler was able to compress the *!! and +!! operations into a single step by 
using the Paris floating-point add/multiply instruction cm:f-add-mult-1l. (The 
rest of the code handles bookkeeping details such as reserving stack space and 
defining the temporary pvar that will be returned.)

Displaying Specific Compiled Code

If you just want to see the expansion of a particular section of code, the 
slc::*show-expanded-code* variable may not suit your purposes. To examine the 
expanded form of a particular piece of code, you can use two Common Lisp 
operations, pprint and macroexpand-1:

> (setq slc::*show-expanded-code* nil)
> (let ((*compiling* t))
	(pprint (macroexpand-1 '(*set	(the single-float-pvar a)
									
	 	(the single-float-pvar b)))))
(PROGN ;; Move (coerce) source to destination - *set.
	(CM:MOVE	(PVAR-LOCATION A)
				(PVAR-LOCATION B)
				32)
	NIL)

(In this example I've included the type declarations so that the +!! form will 
fully compile.)

There are two things to keep in mind when using pprint and the macroexpanding 
functions to display *Lisp code:

	The *Lisp compiler must be enabled (it is by default). To enable the 
compiler, type:

(setq *compilep* t)

	The *Lisp compiler will only compile macroexpanded forms when the 
global variable *compiling* is bound to t. You should use let to temporarily 
bind this variable, as in the example above.

Pretty Print Macroexpand - ppme

Typing the entire (let ((*compiling* t)) (pprint (macroexpand-1 ... ))) 
expression around every piece of code you that wish to compile is a clumsy way 
to view your compiled code. For this reason, the compiler includes a macro that 
you can use to display the expanded form of a piece of code. Called ppme (short 
for "pretty print macroexpand"), it essentially performs a call to pprint and 
macroexpand-1, as in the above example.

You can call ppme with almost any piece of *Lisp code. For example:

> (ppme (*set (the single-float-pvar a)
				(+!!	(the single-float-pvar b)
						(the single-float-pvar c))))

The resulting compiled code looks like this:

(progn
  ;; (*set (the single-float-pvar a) (+!! (the single-fl...
  (cm:f-add-3-1l (pvar-location a)
                 (pvar-location b)
                 (pvar-location c)
                 23
                 8)
  nil)

There is one limitation, however. The ppme macro only expands a piece of code 
when the outermost operator of the code is a macro. To expand other *Lisp 
expressions, such as

(+!!	(the single-float-pvar b)
		(the single-float-pvar c))

enclose them in a *Lisp macro such as *set, as shown in the example above.

Depending on the features of your front end's Lisp programming environment, 
there may be other tools that you can use to view expanded code. In general, 
any tool that macroexpands a section of code may be used to view the compiled 
form of *Lisp code (so long as the outermost form of the code is a macro, of 
course). For example, on Symbolics front ends the editor includes the commands 
Macro Expand Expression (Control-Shift-M) and Macro Expand Expression All 
(Meta-Shift-M) which are used for expanding macros; these tools will also allow 
you to view the code generated by the *Lisp compiler.

	*Lisp Data Types and Declarations

Just as in Common Lisp, declarations are optional in *Lisp; you don't need to 
provide type declarations to get your *Lisp code to run. However, if you want 
to compile your *Lisp code you must provide complete declarations for all 
parallel variables and functions in your program. In this section, we'll take a 
quick look at *Lisp data types and type specifiers, and then show how you go 
about including declarations in your programs.

For Inquiring Minds: Chapter 4 of the *Lisp Dictionary provides a detailed 
discussion of type declaration in *Lisp, and includes an exact set of rules for 
determining what declarations you must provide to get your *Lisp code to 
compile.

	Pvar Type Specifiers - ( pvar  typespec )

*Lisp includes all the front-end data types of Common Lisp, and thus also 
includes the standard type specifiers for those types. However, as we've seen 
not all front-end data types have pvar equivalents. This section shows you 
examples of legal type specifiers for each of the pvar data types of *Lisp.

Type specifiers for pvars are typically of the form

( pvar typespec )

where typespec is a type specifier for one of a specific set of scalar data 
types.

For each of the pvar data types listed below, I've included the basic type 
specifier for pvars of that type, as well as additional -shorthand" specifiers. 
(The symbol <=> indicates equivalent forms.) These shorthand specifiers can be 
used in place of the longer (pvar ...) forms wherever a type specifier is 
required.

boolean - Either t or nil for each processor.

	(pvar boolean)
	boolean-pvar

unsigned-byte - A non-negative integer for each processor.

	(pvar (unsigned-byte length))
	(unsigned-pvar length)
	(field-pvar length)
	unsigned-byte-pvar

signed-byte - A signed integer for each processor.

	(pvar (signed-byte length))
	(signed-byte-pvar length)
	signed-byte-pvar

defined-float - A floating-point number for each processor.

	(pvar (defined-float significand-length exponent-length))
	(float-pvar	significand-length exponent-length)

	single-float-pvar	<=>	(pvar (defined-float 23 8))
	double-float-pvar	<=>  (pvar (defined-float 52 11))

complex - A complex number for each processor.

	(pvar (complex (defined-float significand exponent))
	(complex-pvar significand exponent)
	single-complex-pvar
							<=> (pvar (complex 
(defined-float 23 8))
	double-complex-pvar
							<=> (pvar (complex 
(defined-float 52 11))

character - A Common Lisp character for each processor.

	(pvar character)
	character-pvar

	(pvar string-char)
	string-char-pvar

array - A Common Lisp array for each processor.

	(pvar (array element-type dimension-list))
	(array-pvar element-type dimension-list)

	(vector-pvar element-type length)
							<=>	(pvar (array 
element-type (length)))

structure - A Common Lisp structure object for each processor.

	(pvar structure-name)
	structure-name-pvar

	Note: structure-name must be a structure defined by the *Lisp 
*defstruct macro.

front-end - A reference to a front-end value for each processor.

	(pvar front-end)
	front-end-pvar

	Note: Pvars of this type are created by the *Lisp front-end!! operator.

general - A value of any data type for each processor.

	(pvar t)
	(pvar *)
	general-pvar

Note: By default, undeclared pvars are assumed to be of type (pvar *).

	Using Type Declarations

There are three ways of providing type declarations in *Lisp:

	global type declarations, made with *Lisp's *proclaim operator

	local declarations, made with Common Lisp's declare operator

	type declarations made "on the fly" with Common Lisp's the operator

We'll take a quick look at of each of these declaration operators in this 
section.

Global Type Declarations - *proclaim

The *proclaim operator is much like Common Lisp's proclaim, but is used to 
provide type information to the *Lisp compiler.

The *proclaim operator is used to declare the data type of:

	permanent pvars allocated by *defvar

	scalar variables used in pvar expressions

	values returned by user-defined functions

Important: You must use *proclaim to provide global type declarations to the 
*Lisp compiler, instead of Common Lisp's proclaim form. The *proclaim operator 
passes type information directly to the *Lisp compiler; proclaim does not.

When used to declare the type of a permanent pvar, *proclaim takes the form

(*proclaim '(type pvar-type-specifier pvar-name pvar-name ... ))

as in the following examples:

(*proclaim '(type single-float-pvar float-pvar))
(*defvar float-pvar 3.14)

(*proclaim '(type (pvar (signed-byte 8))	integer-pvar-1
									
					integer-pvar-2))
(*defvar integer-pvar-1 -5)
(*defvar integer-pvar-2 26)

Similarly, when used to declare the type of scalar variables used in pvar 
expressions, *proclaim takes the form

(*proclaim '(type scalar-type-specifier var-name var-name ... ))

as in:

(*proclaim '(type single-float account-balance))
(defvar account-balance 100) ;; Scalar variable, not a pvar
(*set interest (*!! account-balance .05))

(*proclaim '(type complex point1 point2))
(defvar point1 #C(1.0 2.0))
(defvar point2 #C(4.0 5.0))
(*set total-real-length
	(+!! (realpart!! point1) (realpart!! point2)))

When used to declare the returned type of a user-defined function, *proclaim 
takes the form

(*proclaim
  '(ftype (function argument-types returned-value-type) function-name))

as in:

(*proclaim '(ftype (function (pvar pvar) (pvar single-float))
					average!!))
(defun average!! (pvar1 pvar2) (/!! (+!! pvar1 pvar2) 2))

Note: A handy rule of thumb for using *proclaim is that every correct *proclaim 
definition ends with at least two closing parentheses. If you find yourself 
closing a *proclaim with only one parenthesis, it's probably because your type 
specifier isn't correctly formed. For example, the declaration

(*proclaim	'(pvar (unsigned-byte 23)) any-pvar) ; Wrong

is incorrect because it lacks the enclosing (type ... ) around the type 
specifier and the pvar name. The correct form is:

(*proclaim	'(type (pvar (unsigned-byte 23)) any-pvar)) ; Right

Local Type Declarations - declare

For local declarations within your *Lisp code, use Common Lisp's declare 
operator.

The declare operator is used to declare the data type of:

	local pvars created by *let and *let*

	arguments to user-defined functions

	local variables used in pvar expressions

When used to declare the type of a local pvar, declare takes the form

(declare (type pvar-type-specifier pvar-name pvar-name ... ))

as in:

(*let ((float-pvar (random!! 1.0))
		 (field-pvar (random!! 10)))
	(declare (type single-float-pvar float-pvar))
	(declare (type (field-pvar 8) field-pvar))
	(+!! float-pvar field-pvar))

When used to declare the types of arguments to user-defined functions, declare 
resembles the argument type declarations used in other computer languages:

(defun pvar-function (pvar1 pvar2)
	(declare (type single-complex-pvar pvar1))
	(declare (type (signed-byte-pvar 16) pvar2))
	(*!! pvar1 pvar2))

The declare operator is also recognized by *Lisp in all the locations that 
Common Lisp permits, so you can use it to declare the data type of local 
variables used in pvar expressions. For example, you can declare the type of a 
looping variable, as in:

(do ((i 0 (+ i 2)))
    ((>= i 10))
	(declare (type fixnum i))
	(*set sum-pvar (+!! sum-pvar i)))

Note: The loop operator dotimes is an exception. Since the index variable of a 
dotimes loop is always an unsigned integer, the *Lisp compiler automatically 
declares it as such. You do not have to declare the data type of a dotimes 
index variable.

In-line Type Declaration- the

You can also use the Common Lisp the operator to make in-line declarations in 
your code, for cases where neither *proclaim or declare can be used. (As, for 
example, when you need to declare the data type returned by a Common Lisp 
expression.)

The the operator has the following form:

(the type-specifier expression)

as in

(*set data-pvar
	(the (unsigned-byte 32) (+ normal-limit extra-limit)))

	Type Declaration and the Compiler

There are a number of basic principles governing the use and effects of type 
declarations:

	A type declaration is a promise made by you to the *Lisp compiler, 
guaranteeing that variables and functions declared to be of a specific type 
will never have values of any other data type.

For example, the declare form in

(defun max-float (pvar1)
	(declare (type double-float-pvar) pvar1)
	(*max pvar1))

promises that max-float will always be called with a double-float pvar1 
argument.

	The *Lisp compiler uses this information only to turn your code into 
more efficient Paris instructions. Type declarations don't change the semantics 
of your code. In particular, type declarations do not cause the *Lisp compiler 
to perform coercions.

For example, the the form in

(the single-float-pvar any-pvar)

does not automatically convert any-pvar into a single-float-pvar. 

	You must include any needed conversions yourself, via operators such as 
coerce!! as in

(the single-float-pvar
	(coerce!! any-pvar 'single-float-pvar))

	It is an error for a *Lisp program to violate its own declarations. If 
your code doesn't match your declarations, the results you obtain will be 
unpredictable.

	Changing a declaration in your source code does not affect the compiled 
form of your code. If you change a declaration, you must recompile any code 
that depends on that declaration to see the effect of the change.

	Length expressions in pvar type declarations are compiled in such a way 
that they are evaluated at run time. This means you can use declarations such 
as

(pvar (unsigned-byte byte-size))

where the symbol byte-size is a variable that determines the byte size used 
throughout your code. Using evaluated expressions in this fashion is, of 
course, not as efficient as using constant-sized declarations.

Warning: This is a *Lisp extension to Common Lisp, and is valid only within  
pvar declarations. For example:

> (defun foo (x)
	(declare (type (unsigned-byte byte-size) x))
	(print x))
> (compile 'foo)
;;; Warning: Illegal type specifier
;;; in (TYPE (UNSIGNED-BYTE BYTE-SIZE) X)

The (unsigned-byte byte-size) declaration signals a warning because Common Lisp 
does not recognize this kind of type specifier.

	*Lisp Code That Won't Fully Compile

Some *Lisp code can not be completely compiled by the *Lisp compiler. This 
includes:

	*Lisp code with undeclared pvars, functions, or scalar expressions

	*Lisp code that uses general pvars (pvars of type (pvar t) or (pvar *))

	Example: Compiling and Timing a *Lisp Function

As an example of the tools we've seen in this chapter, let's take a simple 
*Lisp function, declare it, compile it, and time it to see how fast it runs.

The function we'll use is:

(defun add-mult!! (a b c)
	(*!! (+!! a b) c))

Let's assume that we want the add-mult!! function to take single-precision 
floating-point pvars as arguments, and return a single-float pvar as a result. 
The definition of add-mult!! with the appropriate declarations added is

> (*proclaim	'(ftype	(function (pvar pvar pvar)
								(pvar 
single-float))
					add-mult!!))

> (defun add-mult!! (a b c)
		(declare (type (pvar single-float) a b c))
		(*!! (+!! a b) c))

Now we can compile this function and see how its speed improves. We'll use the 
Paris timing operator cm:time to see the difference in speed.

The cm:time macro takes a single Lisp form (either *Lisp or Common Lisp) as its 
argument, and uses the timing facility of the CM to provide an accurate 
description of the time taken to execute that form.

For Simulator Users: The timing examples in this section apply only to hardware 
*Lisp users. In particular, the Paris cm:time operator described here exists 
only in the hardware version of *Lisp. You will get an error if you call this 
function while using the simulator.

For example, we can time a call to the interpreted version of add-mult!! like 
this:

> (cm:time (add-mult!! (!! 2.0) (!! 4.0) (!! 7.0)))

Evaluation of (ADD-MULT!! (!! 2.0) (!! 4.0) (!! 7.0)))
took 0.005786 seconds of elapsed time,
during which the CM was active for 0.002159 seconds
or 37.00% of the total elapsed time.

Note: This is just an example of the kind of timing results you'll see. Your 
actual results will vary depending on factors such as the number of users on 
your front end computer.

Note: The first time you run this example, you may also see some additional 
messages:

Warning: Turning off Paris safety for CM:TIME.
Warning: Turning off *Lisp safety for CM:TIME.
Calibrating CM idle timer...
Calculated CM clock speed = 6.99983 MHz

You can safely ignore these warnings. They're simply to inform you that the CM 
timing facility is initializing itself.

When you're timing your *Lisp code, there are three important numbers to watch 
for:

	the elapsed time (the total time taken to execute the supplied Lisp 
form)

	the CM active time (the amount of time the CM was actively processing 
data)

	the percentage utilization of the CM (what percentage of the elapsed 
time the CM was active)

In the example above, the CM utilization is 37% of the total elapsed time, 
which means that the CM was busy for only about a third of the total time it 
took to execute the Lisp expression.

Of course, the function add-mult!! executes so quickly that using cm:time on a 
single function call doesn't give a good sense of how fast the function 
executes. Let's define a function that calls add-mult!! a thousand times, and 
use that to help time the function itself.

> (*proclaim '(type (pvar single-float) my-float-pvar))
> (*defvar my-float-pvar (!! 0.0))
> (defun test-loop ()
	 (dotimes (i 1000)
		 (*set my-float-pvar
			 (add-mult!! (!! 2.0) (!! 4.0) (!! 7.0)))))

Now let's time a call to test-loop:

> (cm:time (test-loop))
Evaluation of (TEST-LOOP) took 4.678420 seconds of elapsed
time, during which the CM was active for 2.059298 seconds
or 44.00% of the total elapsed time.

This is the result using interpreted *Lisp code. The total elapsed time was 
four and a half seconds, with the CM active less than half that time.

Now let's compile test-loop and add-mult!! and time the resulting compiled 
functions.

> (compile 'test-loop)
> (compile 'add-mult!!)
> (cm:time (test-loop))
Evaluation of (TEST-LOOP) took 2.120245 seconds of elapsed
time, during which the CM was active for 1.785779 seconds
or 84.00% of the total elapsed time.

This time it took about two seconds to execute the Lisp expression, with the CM 
busy more than eighty percent of the time. Obviously, compiled code has 
advantages both in speed of execution and in more complete utilization of the 
CM.

	Common Compiler Warning Messages

This section describes the compiler warning messages you're most likely to see 
as you start using the *Lisp compiler, along with the most common reasons for 
getting these warnings.

	Compiler Can't Find Type Declaration...

By far the most common compiler warning is the "compiler can't find type 
declaration" message. This warning is signaled when your code lacks a type 
declaration for a variable or function that is needed to fully compile your 
code. For example:

> (setq *warning-level* :high)
> (defun add-constant (pvar c) (+!! pvar c))
> (compile 'add-constant)
;;; Warning: *Lisp Compiler: While compiling PVAR in function
;;; 	ADD-CONSTANT: The expression (+!! PVAR C) is not compiled
;;; 	because the Lisp compiler cannot find a type declaration
;;; 	for the symbol PVAR.

Every pvar in your code must have a type declaration, either by a local 
declaration operator such as declare or the, or by the global declaration 
operator *proclaim. But simply declaring all your pvars is not sufficient. You 
must also declare the type of any scalar variables that are used in your *Lisp 
code.

For example, if we add a declaration for pvar to add-constant, as in

> (defun add-constant (pvar c)
	(declare (type single-float-pvar pvar))
	(+!! pvar c))

The function still will not compile:

> (compile 'add-constant)
;;; Warning: *Lisp Compiler: While compiling C in function
;;; 	ADD-CONSTANT: The expression (+!! PVAR C) is not compiled
;;; 	because the *Lisp compiler cannot find a type declaration
;;; 	for the symbol C.

We must also add a declaration for the scalar variable c:

> (defun add-constant (pvar c)
	(declare	(type single-float-pvar pvar)
				(type single-float c))
		(+!! pvar c))

> (compile 'add-constant)
ADD-CONSTANT

	Compiler Can't Determine Type Returned by...

A similar warning is the "compiler can't determine type returned by" message. 
This warning is signaled when your code lacks a declaration for returned value 
of a function:

> (defun add-mult-constant (pvar c m)
     (declare 	(type single-float-pvar pvar)
					(type single-float c m))
			(*!! (add-constant pvar c) m))

> (compile 'add-mult-constant)
;;; Warning: *Lisp Compiler: While compiling
;;; 	(ADD-CONSTANT PVAR C) in function ADD-MULT-CONSTANT:
;;; 	The expression (*!! (ADD-CONSTANT PVAR C) M) is not
;;; 	compiled because the *Lisp compiler cannot determine
;;; 	the type of value returned by the expression
;;; 	(ADD-CONSTANT PVAR C).

Every user-defined function in your code must have a type declaration for its 
returned value. This is typically provided by a *proclaim form:

> (*proclaim
	'(ftype (function (pvar t) single-float-pvar) add-constant))

With this declaration included, the add-mult-constant function will now 
compile:

> (defun add-mult-constant (pvar c m)
		(declare	(type single-float-pvar pvar)
					(type single-float c m))
			(*!! (add-constant pvar c) m))
> (compile 'add-mult-constant)
ADD-MULT-CONSTANT

	Compiler Does Not Compile Special Form...

The *Lisp compiler recognizes and compiles a small set of Common Lisp special 
forms without any special declarations. These forms include compiler-let, let, 
let* and progn. Other special forms require a type declaration indicating the 
data type they will return. For example:

> (defun choose (pvar cond v1 v2)
	(declare	(type single-float-pvar pvar)
				(type boolean cond) (type single-float v1 v2))
		(*set pvar (if cond v1 v2)))

> (compile 'choose)
;;; Warning: *Lisp Compiler: The expression
;;; 	(SLC::*2!! (THE (PVAR #) (ADD-CONSTANT PVAR C)) (!! M))
;;; 	in function CHOOSE is not compiled because
;;; 	The *Lisp compiler does not yet compile the special form
;;;	IF. Adding a type declaration to the expression
;;; 	(IF COND V1 V2),
;;; 	such as (THE (PVAR SINGLE-FLOAT) (IF COND V1 V2))
;;; 	will allow the *Lisp compiler to compile the expression,
;;; 	and make this warning go away.

Adding a the type declaration to the if form allows this function to compile:

> (defun choose (pvar cond v1 v2)
	(declare	(type single-float-pvar pvar)
				(type boolean cond) (type single-float v1 v2))
		(*set pvar (the single-float (if cond v1 v2))))

> (compile 'choose)
CHOOSE

	Compiler Does Not Understand How to Compile...

Some *Lisp functions will not compile properly if passed pvar arguments that 
are declared to be of varying size (for example, pvars of type (defined-float * 
*)). For example:

> (defun pack-pvar (pvar)
	(declare (type (pvar (defined-float * *)) pvar))
	(*pset :no-collisions pvar pvar (enumerate!!)))

> (compile 'pack-pvar)
;;; Warning: *Lisp Compiler: While compiling PVAR in function
;;; 	PACK-PVAR: The expression
;;; 		(*LISP-I::*PSET-1 :NO-COLLISIONS PVAR PVAR ...)
;;; 	is not compiled because *PSET does not understand how to
;;; 	compile pvars with element-type defined-float,
;;; 	varying length mutable pvars can not currently be
;;; 	compiled correctly.

Changing the declaration to a fixed-size type (a type specifier that does not 
have any *'s) will allow this function to be compiled:

> (defun pack-pvar (pvar)
	(declare (type (pvar single-float) pvar))
	(*pset :no-collisions pvar pvar (enumerate!!)))

> (compile 'pack-pvar)
PACK-PVAR

	Function Expected a... Pvar Argument but Got...

Finally, the compiler will also catch misdeclared arguments, signaling a 
warning when a function receives arguments of an incorrect type:

> (defun char-value (char-pvar)
	(declare (type character-pvar char-pvar))
	(int-char!! char-pvar))

> (compile 'char-value)
;;; Warning: While compiling CHAR-PVAR in function CHAR-VALUE:
;;; 	Function INT-CHAR!! expected an integer pvar argument
;;; 	but got a character pvar argument.

In this case, the function char-value is intended to convert a character pvar 
to an integer pvar, but is written so that it makes a call to int-char!!, which 
expects an integer (unsigned-byte or signed-byte) pvar argument. Changing this 
function by substituting the correct char-int!! function for int-char!! 
eliminates the warning:

> (defun char-value (char-pvar)
	(declare (type character-pvar char-pvar))
	(char-int!! char-pvar))
> (compile 'char-value)
CHAR-VALUE

	Summary: The Compiler as a Programming Tool

In this chapter, we've seen that:

	The *Lisp compiler is invoked automatically whenever you compile code.

	The *Lisp compiler generates Lisp/Paris code that is much more 
efficient than interpreted *Lisp code.

	To fully compile your code, the *Lisp compiler needs type declarations 
for each parallel variable, function, and macro in your code, as well as for 
scalar variables used in pvar expressions.

	These type declarations resemble the type declarations of Common Lisp, 
and there are declaration forms for each of the pvar data types in *Lisp.

	The *Lisp compiler includes a number of options, such as *safety*, that 
allow you to control the way your code is compiled.

	The compiler option *warning-level* allows you to request that the 
compiler warn you when it can't locate the declarations it needs to compile a 
section of code.

	Because the *Lisp compiler macroexpands *Lisp code into Lisp/Paris 
code, you can use tools such as macroexpand to see the Paris code the compiler 
generates.

	You can use the Paris operator cm:time to see the difference in speed 
between interpreted and compiled code.

That's it for the programming and compiling tools of *Lisp. In the next 
chapter, we'll look at some sample *Lisp functions that use the tools and 
techniques we've seen in previous chapters to perform useful (and perhaps 
surprising) tasks.

Chapter 6: *Lisp Sampler - A Scan in Four Fits

In this chapter, we'll look at four short *Lisp examples that perform simple, 
useful tasks. To give this chapter some continuity, I'll focus on one of the 
most unique and powerful tools of *Lisp: the scan!! operator (which we looked 
at briefly in Section ). The scan!! operator can be used in a variety of ways, 
some of which may suprise you if you're new to the techniques of parallel 
programming. We'll see a number of uses for scan!! in the "fits" of code below, 
many of which can be adapted for use in your own code. Of course, I'll also be 
using other *Lisp operations, so from these examples you'll be able to get a 
sense of how you can combine *Lisp operators to perform specific tasks in your 
programs.

Note: Some of the examples in this chapter are rather long, so you may not want 
to type them in by hand. The file 
/cm/starlisp/interpreter/f6100/starlisp-sampler.lisp in the *Lisp source code 
directory contains a copy of all code examples used in this chapter. Ask your 
systems manager or applications engineer if you need help locating this file.

	Fit the First: Adding Very Large Integers

In *Lisp you can define integer pvars of any size, and add them in parallel:

> (pref (+!! 12345678901234567890 87654321098765432109) 0)
99999999999999999999

But if you have extremely large integers to add (longer than, say, forty 
digits), this isn't really an efficient way to do it. There's no rule, however, 
saying that you have to add numbers by storing them one-per-processor. You can 
divide a very large integer up into its individual bits, and store the bits 
one-per-processor (see ). You can then use *Lisp operations to perform a 
parallel addition of these pvars, using all the CM processors.



. Very large integer stored as a pvar with a single bit value for each 
processor.

Let's assume that we have two large integers, stored one bit per processor, as 
described above. This is the same as saying that we have two integer pvars (or, 
to be more precise, unsigned-byte pvars) of length 1, each containing the bits 
of a very large binary number, one bit per processor. We'll assume that the 
bits of these pvars are stored in send-address order (that is, with the lowest 
order bit stored in the processor with a send address of 0).

To add these pvars, we use the rules of binary addition:

	If both source pvars contain 0 for a processor, the result will be 0 
for that processor.

	If one source pvar contains 1,  and the other 0, the result will be 1.

	If both source pvars contain 1, the result is 0 with a carry of 1.

	A carry value is propagated forward, negating the result for each 
subsequent processor, until it reaches a processor with 0 in both sources (see 
).



. Addition example, showing the propagation of carry bits.

The hardest part of the addition is keeping track of the carry values, and 
incorporating them into the final result. However, we can easily keep track of 
them by using the segmented scanning feature of scan!! that we saw in Section .

In essence, processors where both sources are 1 and processors where both 
sources are 0 define "segments" within which carry values are propagated. The 
carry values start at pairs of 1's and end at pairs of 0's, affecting all 
values in between. We can use parallel boolean operations to determine where 
these segments begin and end, and then use a segmented scan!! to propagate the 
effects of the carry bits.

Here's a function that does this:

> (defun very-long-add!! (bit-pvar1 bit-pvar2)
	(declare (type (field-pvar 1) bit-pvar1 bit-pvar2))
	(*let	 ((zero-zero (=!! 0 bit-pvar1 bit-pvar2))
			  (one-one (=!! 1 bit-pvar1 bit-pvar2))
			  carry-segments will-receive-carry dest)
		(declare
			(type boolean-pvar zero-zero one-one)
			(type boolean-pvar carry-segments will-receive-carry)
			(type (field-pvar 1) dest))

		; Determine points at which carries start and end
		(*set carry-segments
			(or!! (zerop!! (self-address!!)) zero-zero one-one))

		; Determine processors that will be affected by a carry
		(*set will-receive-carry
			(scan!! one-one 'copy!!
				:segment-pvar carry-segments :include-self 
nil))

		; Exclude processor zero, because it can't get a carry
		(*setf (pref will-receive-carry 0) nil)

		; Perform the addition
		(*set dest
		  (if!!	(or!! one-one zero-zero)
			; Pairs of 1's and 0's produce 1 with carry, else 0
			(if!! will-receive-carry 1 0)
			; All other values will be 0 with carry, 1 otherwise
			(if!! will-receive-carry 0 1)))
		dest))

The call to scan!! is the real heart of this algorithm. The rest of the 
function is simply setup code to determine the exact boundaries for the scan, 
and cleanup code that uses the scan result to calculate the final value for 
each processor. It's quite common for a function that uses scan!! to have this 
form: setup code, the scan!! itself, then cleanup code. We'll see other 
examples of this later on.

For The Observant: You'll notice that the call to scan!! has an :include-self 
argument of nil. The effect of this argument is to prevent each processor 
involved in the scan from including its own value in the result that is passed 
on to the next processor in the scan. Since we're doing a copy!! scan in the 
very-long-add!! function, this has two effects:

	Processors that produce a carry bit (1/1 processors) aren't affected by 
it.

	Processors that halt propagation of a carry bit (0/0 processors) are 
affected by it.

The :include-self argument to scan!! is a handy tool for controlling the 
effects of a scan, because it effectively "shifts" the effect of the scan ahead 
by one processor. We'll see other examples of the use of :include-self later on 
in this chapter.

Now, since the bit pvars we'll be using have the least significant bit stored 
in processor 0, we'll want a function that displays these pvars with this bit 
on the right, rather than on the left, as ppp would display them.

Here's a definition for a function that does this, called pbp (short for 
print-bit-pvar):

> (defun pbp (pvar &key (length 20) title) "Print Bit Pvar"
	(*let ((display-pvar
				(if!!	(<!! (self-address!!) length)
						(pref!! pvar (-!! length 
(self-address!!) 1))
						0)))
		(ppp display-pvar :end length :title title))
	(values))

The pbp function takes a pvar, a length, and a title, and prints the specified 
number of bit values with the low-order bits on the right. It uses the 
communication operator pref!! to make a copy of the specified part of the pvar 
with its values "flipped" end for end.

We can define a simple bit pvar with a value of 1 for the first 12 processors, 
and then use both ppp and pbp to display the first 20 values of this pvar:

> (*defvar bits (if!! (<!! (self-address!!) 12) 1 0))
BITS

> (ppp bits :end 20)		 ; low-order bits on left
1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0

> (pbp bits :length 20)	 ; low-order bits on right
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

Now, to test very-long-add!!, we'll write a function that creates two bit 
pvars, displays them, and adds them.

> (defun test-very-long-add ()
	(let	((length1 (+ 12 (random 5)))
			 (length2 (+ 12 (random 5))))
		(*let ((bit-pvar1 0) (bit-pvar2 0))
			(declare (type (field-pvar 1) bit-pvar1 bit-pvar2))

			; Store random binary numbers in the bit pvars
			(*when (<!! (self-address!!) length1)
				(*set bit-pvar1 (random!! 2)))
			(*when (<!! (self-address!!) length2)
				(*set bit-pvar2 (random!! 2)))

			; Display the two binary numbers
			(pbp bit-pvar1 :length 20 :title "Bit-pvar 1")
			(pbp bit-pvar2 :length 20 :title "Bit-pvar 2")

			; Display the result of adding them
			(pbp (very-long-add!! bit-pvar1 bit-pvar2)
				:length 20 :title "Result    "))
	(values)))

Here's the actual output of two sample calls to the test-very-long-add!! 
function:

> (test-very-long-add)
Bit-pvar 1: 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1
Bit-pvar 2: 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0
Result    : 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1
> (test-very-long-add)
Bit-pvar 1: 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 1
Bit-pvar 2: 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 
Result    : 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1

Obviously, we're only adding numbers of 12 to 17 bits in these examples, but 
very-long-add!! can be used without modification to add numbers with thousands 
or even millions of bits, limited only by the number of processors that you are 
currently using.

For the Curious: If you'd like to get a closer look at the inner workings of 
very-long-add!!, you can use the *Lisp function ppp!! to display the value of 
any pvar expression without affecting the value that expression returns. Unlike 
ppp, which prints a pvar and then returns nil, the ppp!! function prints a pvar 
and then returns the same pvar as its value. For more information, see the 
entry for ppp!! in the *Lisp Dictionary.

	Fit the Second: A Segmented news!! Function

In Chapter  we looked at router and grid communication, and I pointed out that 
grid communication is faster because of its regularity: all values move in the 
same direction across the grid. The scan!! function is also preferable to using 
the router, for the same reason: it's faster and more efficient. But scanning 
is much more flexible than grid communication. You can use scan!! to write 
data-movement operations that have the speed of grid communication operations, 
yet at the same time allow you to rearrange the values of your pvars in 
router-like ways.

For example, the grid communication operator news!! doesn't have a 
:segment-pvar argument like scan!!, but you can use segmented scan!! calls to 
perform news!!-like shifts of data in a segmented manner.

As a specific example, let's take the pvar returned by (self-address!!) as our 
"data" pvar:

> (ppp (self-address!!) :end 20 :format "~2D ")
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19

and suppose that we have a segment pvar with the following values (for clarity, 
I've used the :format argument of ppp to replace nil values with dots):

> (ppp segment-pvar :end 20 :format " ~:[.~;T~] ")
 T  T  .  .  T  .  .  .  T  .  .  .  T  .  .  .  T  .  .  .

We can use a segmented scan!! to "rotate" each segment of the self-address!! 
pvar one position to the right, producing:

 0  3  1  2  7  4  5  6 11  8  9 10 15 12 13 14 19 16 17 18

Here's how to do it:

> (defun segmented-news!! (pvar segment-pvar)

	(*let	 (end-segment-pvar
			  result
			  temp)

	; Define a second segment pvar that has T's at
	; the _end_ of the segments defined by segment-pvar
	(*set end-segment-pvar
	  (scan!! segment-pvar 'copy!! :direction :backward
				:segment-pvar t!! :include-self nil))

	; Last active processor in end-segment-pvar must be T
	(*setf (pref end-segment-pvar (*max (self-address!!))) T)

	; use scan!! to shift pvar values forward one position
	(*set result
	  (scan!! pvar 'copy!! :segment-pvar t!! :include-self nil))

	; use a backward scan to copy the last value
	; of each segment back to the start of the segment
	(*set temp
	  (scan!! pvar 'copy!! :segment-pvar end-segment-pvar
			:include-self t :direction :backward))

	; combine the copied last elements from temp pvar
	; with the elements in the result pvar
	(*when segment-pvar (*set result temp))

	; return the resulting shifted pvar
	result))

There are three scan!! calls in this function, each of which performs a 
particular task. In order, the scans are:

	A "backward" copy!! scan with a segment pvar of t!! and :include-self 
nil. This shifts the contents of segment-pvar "backwards" by one element, 
producing a segment pvar that contains t for every processor that ends a 
segment. (Note that we also have to use *setf to make sure this pvar has a t in 
the "last" active processor.)

	A "forward" copy!! scan with a segment pvar of t!! and :include-self 
nil. This shifts each value of the supplied pvar argument "forward" by one 
step.

	A "backward" copy!! scan using the end-of-segment pvar we created, to 
copy the last value of each segment back to the first location in the segment. 
Notice that this time :include-self is t, to keep copied values from crossing 
segment boundaries.

The result, after we use *when and *set to combine things, is a copy of pvar 
with its contents rotated forward by one element within each segment, as 
defined by segment-pvar.

Here's an example of this function in action, using the example shown at the 
beginning of this section:

> (*defvar segment-pvar (zerop!! (mod!! (self-address!!) 4)))
SEGMENT-PVAR
> (*setf (pref segment-pvar 1) T) ; set processor 1 as well

> (ppp (self-address!!) :end 20 :format "~2D ")
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19

> (ppp segment-pvar :end 20 :format " ~:[.~;T~] ")
 T  T  .  .  T  .  .  .  T  .  .  .  T  .  .  .  T  .  .  .

> (ppp (segmented-news!! (self-address!!) segment-pvar)
		:end 20 :format "~2D ")
 0  3  1  2  7  4  5  6 11  8  9 10 15 12 13 14 19 16 17 18

For Perfectionists: As defined above, the segmented-news!! function calculates 
an end-segment-pvar every time it is called. Calling segmented-news!! 
repeatedly (for instance, within a loop) would be very inefficient. A better 
method is to rewrite this function to accept an end-segment-pvar argument, and 
then precalculate the end-segment pvar before calling segmented-news!!. And 
even if you're not using scans within a loop, precomputing the start-segment 
and end-segment pvars is a very practical method for using scans, because (as 
shown in the segmented-news!! example) it makes it easy for you to use both 
"forward" and "backward" scanning in your functions.

	Fit the Third: Using the Router Efficiently

Router communication, while slower on average than grid communication, is 
nevertheless a very flexible way to move data between processors. There are 
many cases in which it might seem at first that using router communication is 
highly inefficient, yet by a suitable rearrangement of data even these extreme 
cases can be handled effectively.

As an example, consider the "many collisions" get operation. This happens when 
the address pvar argument of a pref!! call causes many processors to request a 
value from a single address, producing many "collisions" of requests. The 
router has built-in hardware for handling these collisions effectively, but 
when the number of requests is very large the hardware algorithm can run out of 
memory. In these cases, a slower software algorithm is used instead to perform 
the get operation.

By using a *defstruct pvar, a sort and a scan!! or two, we can simulate this 
algorithm, and see what steps the router has to take to handle a "many 
collisions" get.

The *defstruct pvar is used to hold information about the data transfers that 
we make:

>  (*defstruct gmc-data
 	 (fetch-address nil :type fixnum)
 	 (originating-address nil :type fixnum))

For each processor, the fetch-address slot of this pvar records the address 
from which the processor is requesting a value, and the originating-address 
slot records the self address of the processor itself, so that the data can be 
sent back to it.

The function we write will need to do the following:

	Create a gmc-data pvar containing the fetch-address and 
originating-address for each active processor.

	Sort the values of this pvar by fetch-address, to gather together 
requests for data from the same fetch-address, and at the same time "pack" the 
requests together into low-address processors so that there are no gaps between 
them.

	Find the first processor in each group of similar requests, and do a 
"get" (pref!!) operation to retrieve values for just those processors.

	Do a scan!! to copy the retrieved values to all other processors in 
each group of requests.

	Finally, do a "send" (*pset) operation to deliver the retrieved values 
to the processors that requested them.

The entire algorithm can be written as a single function:

> (defun pref!!-many-collisions (data address)
	(let ((number-of-active-processors (*sum 1)))
	 (*let ((sort-data (make-gmc-data!!
							 :fetch-address address
							 :originating-address 
(self-address!!))))

		; Sort sort-data pvar by fetch-address and
		; pack into low-address processors so it is contiguous
		(*pset :no-collisions sort-data sort-data
			(rank!! (gmc-data-fetch-address!! sort-data) '<=!!))

		; Select processors that contain data after the sort
		(*all
		 (*when  (<!!	(self-address!!)
						
	number-of-active-processors)

		 ; Create segment pvar that is T for the first element
		 ; of each group of elements with the same fetch-address
		 (*let ((beginning-of-segment
					(or!! (zerop!! (self-address!!))
					 (/=!! (gmc-data-fetch-address!! 
sort-data)
					    (scan!! (gmc-data-fetch-address!! 
sort-data)
									 'max!! 
:include-self nil))))
					fetched-data)

		 ; Do a get only for the first element of each segment
		 (*when beginning-of-segment
			(*set fetched-data
			 (pref!! data (gmc-data-fetch-address!! sort-data))))

		 ; Use scan!! to copy fetched data to the other elements
		 (*set fetched-data
			(scan!! fetched-data 'copy!!
				:segment-pvar beginning-of-segment))

		 ; Use originating-address slots to send the data back
		 ; to the processors that originally requested it
		 (*pset :no-collisions fetched-data fetched-data
			(gmc-data-originating-address!! sort-data))

		 ; Return the redistributed data
		 fetched-data))))))

Here's an example of how you would call pref!!-many-collisions:

> (*defvar collision-addresses (floor!! (self-address!!) 6))
COLLISION-ADDRESSES

> (ppp collision-addresses :end 28)
0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4

> (ppp (pref!!-many-collisions (*!! (self-address!!) 3)
									
	 collision-addresses)
		 :end 28)
0 0 0 0 0 0 3 3 3 3 3 3 6 6 6 6 6 6 9 9 9 9 9 9 12 12 12 12

There are two scan!! calls in pref!!-many-collisions, each having a different 
set of arguments:

	The first scan!! call does a forward max!! scan of the sorted sort-data 
values, with :include-self nil. This causes each processor to compare its own 
value with the maximum value of all the preceding processors. Only processors 
that start a segment of similarly addressed requests will see a difference 
between these values, so this step quickly locates the first processor in each 
segment.

	The second scan!! call is a forward copy!! scan using the segment pvar 
derived from the first scan!!. The first processor in each segment has 
retrieved a value, so this scan!! operation copies that value to the other 
processors of the segment.

Notice how in this example we're using one type of scan!! call to determine the 
bounds for another type of scan!! call. It's the multi-faceted nature of scan!! 
that makes this possible.

Notice also the combination of *pset and rank!! at the beginning of the 
pref!!-many-collisions function. This is an important example of a pair of 
*Lisp functions working in tandem to perform more than one operation. The 
rank!! function provides a ranking of the fetch-address values in the sort-data 
pvar, and *pset uses this ranking to sort the values in ascending order. The 
important point to notice, however, is that some processors might be deselected 
when pref!!-many-collisions function is called. When rank!! does its ranking, 
these processors are simply ignored. The result is that *pset "packs" all the 
active values of sort-data into processors with low addresses, eliminating any 
"gaps" caused by deselected processors.

For The Curious: This "packing" of pvar values is a useful trick for 
eliminating gaps in your data set. We can rewrite the *pset-rank!! combination 
used in  pref!!-many-collisions  to "pack" the values of a pvar without 
changing their order, as in:

(*pset :no-collisions pvar pvar
							(rank!! 
(self-address!!) '<=!!))

The expression (rank!! (self-address!!) '<=!!) is an important enough idiom 
that there is a *Lisp function that does the same thing: enumerate!!. So this 
"pack" operation can be written more efficiently as:

(*pset :no-collisions pvar pvar (enumerate!!))

And, by the way, it shouldn't suprise you to learn that scan!! can be used to 
write a simple version of enumerate!!:

(defun enumerate!! () (scan!! 1 '+!! :include-self nil))

	Fit the Fourth: Creating a "List" Pvar

While *Lisp does not have a direct parallel analogue of the list data 
structure, you can use *Lisp operations to define a parallel data structure 
that has much of the flexibility of lists. This example uses VP sets, router 
communication, and scanning to define a parallel data structure with an 
arbitrary number of elements per processor, which I call a "list" pvar on 
account of its flexible nature. (Lisp purists will most likely prefer some 
other name.)

This is accomplished by defining a new VP set that has sufficient processors to 
hold all  the elements of the list pvar, and by defining the list pvar in such 
a way that it is divided into segments of elements, one segment for each 
processor in the original VP set. In this way, each processor in the original 
VP set is assigned a "list" of elements for its use, of any required length.

Note: This section introduces some *Lisp functions and variables that we 
haven't looked at in previous sections. In particular, this section introduces:

*minimum-size-for-vp-set*
allocate-processors-for-vp-set
deallocate-processors-for-vp-set
next-power-of-two->=

There are definitions and examples of each of these operations in the *Lisp 
Dictionary.

Here's the definition of the VP set:

> (def-vp-set list-vp-set nil
   :*defvars ((segment-pvar nil) (elements nil)))

It is defined as a flexible VP set, meaning that its size and shape are 
determined at run time. It has two associated pvars, an elements pvar that will 
contains the elements of the lists we define, and a segment-pvar (as used in 
the scan!! examples above) that will indicate with a t value the beginning of 
each segment of list elements.

We'll also want a pair of permanent pvars that describe the start location and 
length of the segment of elements assigned to each processor:

> (*defvar *list-start-processor*)
> (*defvar *number-of-elements*)

Now, here is the macro that actually defines and allocates the list-vp-set for 
the duration of a body of *Lisp code:

> (defmacro allocate-list-pvar (length value &body body)
	`(let ((total-processors-required (*sum ,length)))

	  ;;; Allocate processors in list-vp-set for list elements
		(allocate-processors-for-vp-set list-vp-set
			(list (max *minimum-size-for-vp-set*
				(next-power-of-two->= 
total-processors-required))))
		(*with-vp-set list-vp-set
			(*set segment-pvar nil elements nil))

		;;; Get send addresses of elements in that list-vp-set
		;;; that will contain the first element of each segment
		(*let	((*list-start-processor*
				 (scan!! ,length '+!! :include-self nil))
			(*number-of-elements* ,length))

		;;; For processors that have requested a non-zero number
		;;; of elements, send the initial values to the first
		;;; element of the corresponding segments.
		(*when (plusp!! ,length)
			(*pset :no-collisions ,value elements
				*list-start-processor* :notify segment-pvar))

		;;; Use scan!! to copy the initial value to all elements
		;;; in each segment.
		(*with-vp-set list-vp-set
		 (*set elements
		  (scan!! elements 'copy!! :segment-pvar segment-pvar)))

		;;; Evaluate body forms with list-vp-set defined
		(progn ,@body )

		;;; Deallocate the list-vp-set so that it can be reused.
		(deallocate-processors-for-vp-set list-vp-set))))

Notice that the allocate-list-pvar macro simply defines the new VP set, but 
does not select it; the body of code enclosed by the macro is free to select 
the list-vp-set whenever it is needed.

As an example of what you can do with a "list" pvar once you've defined it, 
here's a function that prints out the first n lists in the list-vp-set:

> (defun print-lists (n)
	 (dotimes (i n)
		(format t "~&( ")
		(let	((start-address (pref *list-start-processor* i))
				 (length (pref *number-of-elements* i)))
		 (*with-vp-set list-vp-set
		  (dotimes (i length)
			(format t "~D "
				(pref elements (+ start-address i))))))
		(format t ")")))

Finally, here's a test function that allocates the list-vp-set with a random 
set of list lengths,  calls ppp to display the first n lengths it assigned, and 
then calls print-lists to display the first n lists in the list-vp-set:

> (defun test-lists (n)
	(*let ((lengths (random!! 8)))
		(ppp lengths :end n)
		(allocate-list-pvar lengths (self-address!!)
			(print-lists n))))

Here's what the output from test-lists looks like:

> (test-lists 6)
4 3 5 4 3 2
( 0 0 0 0 )
( 1 1 1 )
( 2 2 2 2 2 )
( 3 3 3 3 )
( 4 4 4 )
( 5 5 )

> (test-lists 6)
2 5 5 1 0 4
( 0 0 )
( 1 1 1 1 1 )
( 2 2 2 2 2 )
( 3 )
( )
( 5 5 5 5 )

While it's not a simple matter to dynamically change the size of the list 
assigned to each processor, the "list" pvar has many of the advantages of the 
list data structure in Common Lisp.

There are many applications where this ability to assign a "list" of elements 
to each original processor comes in handy. For example, in simulating the 
behavior of subatomic particles, a list pvar can be used to keep track of the 
particles that result from collisions or decay.

Another example is in parallel graphics programs, where a number of polygons 
must be rendered (displayed on a screen). Each polygon can be broken down into 
triangles that are easy to render, but each polygon may produce a different 
number of triangles. A list pvar can be used to hold the set of triangles 
derived from each polygon, and then the entire list pvar can be passed to a 
simple triangle-rendering algorithm for display.

	Summary: There's More Than One Way to Scan a Pvar

In this chapter, we've seen that:

	You can use scan!! to add extremely large integers.

	You can use the segmented version of scan!! to define other segmented 
operations.

	You can use scan!! along with *defstruct pvars, ranking tools, and 
communication operators to increase the efficiency of your data transfer 
operations.

	You can use scan!! along with the existing parallel data structures of 
*Lisp to define new data structures that have the kind of flexibility that you 
need.

In short, there are many interesting and unusual things you can do with *Lisp: 
the examples in this chapter are but a representative sample. The best way to 
learn about these unusual tricks is by creating them yourself. Decide what kind 
of operation you wish to perform, and then combine *Lisp operators to implement 
it.



Chapter 7: Going Further with *Lisp

	Topics We Haven't Covered

There are some *Lisp topics that we haven't covered in this Getting Started 
guide. You can find out more about them by looking in the *Lisp Dictionary. 
They are described briefly below.

Creating and Using Array Pvars

*Lisp has parallel equivalents of most of the array and vector operations of 
Common Lisp. In this document, we've only seen one of these, make-array!!. 
Section 1.5 of the overview chapter in the *Lisp Dictionary provides a complete 
list of all array pvar operations in *Lisp. Along with operations for array 
pvars, *Lisp includes specialized operations for vector pvars and bit-array 
pvars, and parallel equivalents of Common Lisp sequence operators, for example 
find!!, length!!, position!!, and substitute!!. These are also listed in 
Section 1.5.

Turning Array Pvars "Sideways"

If you use array pvars heavily in your *Lisp code, you may want to consider 
turning your arrays "sideways." This operation changes the arrangement of data 
in your array pvars so that the CM can access them more efficiently. For more 
information about "sideways" arrays, see the dictionary entries for 
sideways-aref!! and *sideways-array.

Creating and Using *defstruct Pvars

In this guide, we've barely touched on the use of *defstruct for defining 
structure pvars, but structure pvars are a powerful tool for defining your own 
parallel data types. For more information about structure pvars and examples of 
how to create them, see the dictionary entry for *defstruct.

Dynamically Allocating Blocks of CM Memory

Along with permanent, local, and temporary pvars, there is a fourth kind of 
pvar known as a global pvar. Allocated by the *Lisp operator allocate!!, global 
pvars are used to allocate and reference large amounts of CM memory within your 
*Lisp programs. Whereas you will typically allocate permanent pvars one at a 
time, you can allocate dozens or even hundreds of global pvars at one time, and 
store them in a list to be used whenever you need them. For more information, 
see the dictionary entry for allocate!!.

Defining Segment Set Objects for Scanning

Along with the scan!! operator, there is a more advanced scanning function, 
segment-set-scan!!, that uses a "segment set" data structure to define where 
the segments of a pvar begin and end. These segment set data objects are 
created by the function create-segment-set!!, and there are a large number of 
*Lisp functions for accessing the contents of these segment set objects. For 
more information, see the dictionary entries for segment-set-scan!! and 
create-segment-set!!.

Just For Fun: Controlling The Front Panel LEDs

Finally, *Lisp includes a function called *light which takes a boolean pvar and 
calls an internal Paris function to set the state of the front panel LEDs of 
the CM. For more information, see the dictionary entry for *light, and also the 
entries for the Paris operators cm:latch-leds and cm:set-system-leds-mode in 
the Connection Machine Parallel Instruction Set (Paris) manual.

	Where Do You Go from Here?

I hope this Getting Started guide has given you the start you need towards 
proficient *Lisp programming. Here are some suggested sources to which you can 
turn for further information about *Lisp programming and more examples of *Lisp 
code:

	The *Lisp Dictionary contains a complete list of all *Lisp functions 
and macros, as well as information on type declarations and compiler options 
that you'll find very handy.

	The directory /cm/starlisp/interpreter/f6100 contains a number of 
example *Lisp files. The names of these files are listed in the file 
examples-def-file-set.lisp in this directory.

	Your fellow *Lisp programmers are a good source of information, sample 
code, and help in debugging recalcitrant programs. Ask around among the *Lisp 
people you know for help and advice.

	Finally, you can contact Thinking Machines Corporation Customer Support 
for help and advice on *Lisp programming, via the email address given in the 
front of this guide.

May all your parentheses balance, and may all your CM processors be active!



Appendixes



Appendix A: Sample *Lisp Application

This chapter contains commented source code for the cellular automata example 
used in Chapter , along with extensions that make the system more generic. This 
file is also available on-line in the *Lisp software directory, in the file

/cm/starlisp/interpreter/f6100/cellular-automata-example.lisp

Check with your system administrator or applications engineer if you need help 
locating this file.

	Cellular Automata Example

;;; CA Example From "Instant *Lisp" Chapter
;;; by William R. Swanson, Thinking Machines Corporation

;;; Load into *Lisp package
(in-package '*lisp)

;;; --- Global Variables ---
;;; This defines a permanent pvar to hold the grid of cells
(*defvar *automata-grid* 0)

;;; Total number of states allowed per cell
(defvar *total-number-of-states* 10)

;;; Cell "neighborhood" to use for automata
(defvar *neighborhood* :neumann)

;;; --- Simple Tools ---

;;; Function to display the grid
(defun view (&optional (width 8) (height 5))
  (ppp *automata-grid* :mode :grid :end (list width height)))

;;; Functions to read/write individual cells
(defun read-cell (x y)
  (pref *automata-grid* (grid x y)))

(defun set-cell (x y newvalue)
  (*setf (pref *automata-grid* (grid x y)) newvalue))

;;; Function to set value of entire grid
(defun set-grid (newvalue)
  (*set *automata-grid*
	(mod!! newvalue *total-number-of-states*)))

;;; Function to randomly set the value of each cell
(defun random-grid ()
  (set-grid (random!! *total-number-of-states*)))

;;; Tools to set up a fixed pattern:
(defun set-cells (cell-list value)
  (dolist (cell cell-list)
    (set-cell (car cell) (cadr cell) value)))

;;; Clear grid, set up "r-pentomino" pattern, and display
(defun init ()
  (set-grid 0)
  (set-cells '((2 2) (3 1) (3 2) (3 3) (4 1))
	     1)
  (view))

;;; Tools to get information about neighboring cells.
;;; Count non-zero Von Neumann neighbors
(defun neumann-count (grid)
  (+!! (news!! grid 0  -1)   ;; north
       (news!! grid 0  1)    ;; south
       (news!! grid -1 0)    ;; west
       (news!! grid 1  0)    ;; east
       )))

;;; Count non-zero Moore neighbors
(defun moore-count (grid)
    (+!! (news!! grid 0  -1) ;; north
	 (news!! grid 0  1)  ;; south
	 (news!! grid -1 0)  ;; west
	 (news!! grid 1  0)  ;; east
	 (news!! grid -1 -1) ;; northwest
	 (news!! grid -1 1)  ;; southwest
	 (news!! grid 1  -1) ;; northeast
	 (news!! grid 1  1)  ;; southeast
	 )))

;;; Count neighbors for current *neighborhood*
(defun neighbor-count ()
  (*let ((grid (signum!! *automata-grid*)))
    (ecase *neighborhood*
      (:moore (moore-count grid))
      (:neumann (neumann-count grid)))))

;;; Function to run the automata defined by the function one-step.
(defun run (&optional (n 1))
  (dotimes (i n)
    (set-grid (one-step))))

;;; Function to run automata for n steps and display the grid.
(defun view-step (&optional (n 1))
  (run n)
  (view))

;;; Tool to check whether all the cells are dead (zero).
(defun deadp ()
  (zerop (*sum (signum!! *automata-grid*))))

;;; --- Simple Automaton Example ---
;;; This automaton obeys the following rules:
;;; If a cell is:
;;;    EVEN - divide its value by 2
;;;    ODD  - add 1 to its value and multiply by 2

(defun one-step ()
  (if!! (evenp!! *automata-grid*)
     (floor!! *automata-grid* 2)
     (*!! (1+!! *automata-grid*) 2)))

;;; --- "9 Life" automata, based on Conway's Game of Life ---
;;; Obeys the following rules:
;;;  For each cell, count the number of non-zero neighbors.
;;;    If it is <1, or >3, subtract 1 (zero cells remain zero).
;;;    If it is 2 or 3, add 1
;;;    Otherwise, do nothing

(defun one-step ()
  (*let ((count (neighbor-count)))
    (cond!!
      ;; When count is <1 or >3, subtract 1 if not zero.
      ((or!! (<!! count 1) (>!! count 3))
       (if!! (zerop!! *automata-grid*)
	     *automata-grid*
	     (1-!! *automata-grid*)))

      ;; When count is 2 or 3, add 1
      ((<=!! 2 count 3) (1+!! *automata-grid*))

      ;; Otherwise, leave cells unchanged
      (t *automata-grid*))))

;;; --- Extension of Material in Chapter 1 ---
;;; Tools to define and run generic automata:

;;; Macro that defines a named automaton
;;; as a list of two function objects.
;;; Init function sets up the *automata-grid*
;;; Step function calculates and returns single "step" of automata

(defmacro defautomaton (name &key init step)
  `(progn
     (defvar ,name)
     (setq ,name (list '(lambda ,@init)
		       '(lambda ,@step)))
     ',name))

(defun init-function (automaton) (car automaton))
(defun step-function (automaton) (cadr automaton))

;;; Definitions for the two automata we've already written:
(defautomaton four2one
    ;;; init function takes no arguments, and randomizes the grid.
    :init ((&rest ignore)
	   (setq *total-number-of-states* 10)
	   (random-grid))
    ;;; step function takes no arguments, and calculates one step
    :step ((&rest ignore)
	   (if!! (evenp!! *automata-grid*)
		 (floor!! *automata-grid* 2)
		 (*!! (1+!! *automata-grid*) 2))))

(defautomaton 9life
    ;;; init function takes optional arguments defining
    ;;; the current neighborhood, the initial pattern, and
    ;;; the value stored into cells that are part of the pattern
    :init ((&optional (neighborhood *neighborhood*)
		      (start-pattern '((2 2) (3 1) (3 2) (3 3) (4 1)))
		      (start-value 1))
	   (setq *neighborhood* neighborhood
		 *total-number-of-states* 10)
	   (set-grid 0)
	   (set-cells start-pattern start-value))
    ;;; step function takes no arguments, and
    ;;; calculates a single step of the automaton
    :step ((&rest ignore)
	   (*let ((count (neighbor-count)))
	     (cond!! ((or!! (<!! count 1) (>!! count 3))
		      (if!! (zerop!! *automata-grid*)
			    *automata-grid*
			    (1-!! *automata-grid*)))
		     ((<=!! 2 count 3) (1+!! *automata-grid*))
		     (t *automata-grid*)))))

;;; --- Tools used to select an automaton to run ---

;;; Currently selected automaton
(defvar *current-automaton*)

;;; Function to select an automaton and initialize the grid
(defun setup (automaton &rest init-args)
  (setq *current-automaton* automaton)
  (initialize init-args))

;;; Function to call the init function of the current automaton,
;;; and display the initial state of the grid.
(defun initialize (&optional init-args)
  (apply (init-function *current-automaton*) init-args)
  (view))

;;; Function to run the automaton for n steps and display the grid
(defun run (&optional (n 1) &rest step-args)
  (dotimes (i n)
    (set-grid
      (apply (step-function *current-automaton*)
	     step-args)))
  (view))

;;; The following sample session shows how to set up and
;;; run the automata defined by the above extensions:
;
;> (setup four2one) ;; Simple 4-2-1 loop automata
;
;5 7 9 3 2 3 1 9 
;7 0 3 4 3 3 0 3 
;9 4 2 3 8 9 2 5 
;7 3 3 5 8 2 9 3 
;1 7 9 1 8 6 9 6 
;
;> (run)
;2 6 0 8 1 8 4 0 
;6 0 8 2 8 8 0 8 
;0 2 1 8 4 0 1 2 
;6 8 8 2 4 1 0 8 
;4 6 0 4 4 3 0 3 
;
;> (run 50)
;4 1 0 2 2 2 1 0 
;1 0 2 4 2 2 0 2 
;0 4 2 2 1 0 2 4 
;1 2 2 4 1 2 0 2 
;1 1 0 1 1 4 0 4 
;

;> (setup 9life :neumann) ;; 9 Life, Neumann neighborhood
;
;0 0 0 0 0 0 0 0 
;0 0 0 1 1 0 0 0 
;0 0 1 1 0 0 0 0 
;0 0 0 1 0 0 0 0 
;0 0 0 0 0 0 0 0 
;
;> (run)
;0 0 0 0 0 0 0 0 
;0 0 1 2 1 0 0 0 
;0 0 1 2 1 0 0 0 
;0 0 1 1 0 0 0 0 
;0 0 0 0 0 0 0 0 
;
;> (run 50)
;0 0 0 0 0 0 0 0 
;0 0 0 8 3 0 0 0 
;0 0 5 0 7 0 0 0 
;0 0 4 5 9 0 0 0 
;0 0 0 0 0 0 0 0 
;
;> (setup 9life :moore) ;; 9 Life, Moore neighborhood
;
;0 0 0 0 0 0 0 0 
;0 0 0 1 1 0 0 0 
;0 0 1 1 0 0 0 0 
;0 0 0 1 0 0 0 0 
;0 0 0 0 0 0 0 0 
;
;> (run)
;0 0 0 1 1 0 0 0 
;0 0 1 2 2 0 0 0 
;0 0 2 0 0 0 0 0 
;0 0 1 2 1 0 0 0 
;0 0 0 0 0 0 0 0 
;
;> (run 50)
;0 0 0 0 4 1 0 1 
;5 7 7 2 1 1 1 0 
;0 0 0 0 1 1 5 2 
;4 4 9 2 1 0 4 0 
;0 0 0 0 1 2 0 2 



Appendix B: A *Lisp/CM Primer

For those readers unfamiliar the Connection Machine (CM) system, this chapter 
provides a brief overview of data parallel processing and the CM, and also 
describes how the *Lisp language fits into the CM system.

	Data Parallel Processing

Most computers are designed according to a serial processing model in which a 
single computing unit, or processor, executes a single program one instruction 
at a time. The Connection Machine system differs from such serial computing 
systems in two ways: the CM is a parallel processing system, and on top of that 
the CM is a data parallel processing system.

Parallel processing means having more than one processor executing your program 
at the same time. The CM is a massively parallel processing system; it applies 
many thousands of processors to the execution of your program simultaneously. 
The main difficulty with executing programs in parallel lies in coordination: 
getting all those thousands of processors to work together efficiently in 
solving problems for you. The CM solves this problem through data parallel 
processing.

In data parallel processing a large number of processors, each with its own 
associated portion of memory, executes identical computing operations 
simultaneously. That is, each processor performs the same identical operation 
on its own portion of memory. This avoids the problem of coordinating the 
actions of all those processors; all processors do the same thing at the same 
time. But while all processors perform the same operation, each processor does 
so on a different piece of data. This is the key point of data parallel 
processing: it's like executing the same program simultaneously on many 
thousands of pieces of data.

Here are some examples of how data parallel processing can be used:

	A text-retrieval program might store a set of articles 
one-per-processor and then have each processor search its particular article 
for a key word or phrase.

	A graphics program might arrange the pixels of an image 
one-per-processor and then have each processor calculate the color value of its 
pixel, all at the same time.

	A finite-state automata program (for example, Conway's Game of Life) 
might create a large number of cells stored one-per-processor. Each cell would 
have a small number of possible states, and all the cells would be 
simultaneously updated at each "tick" of a clock according to a set of fixed 
rules.

Programs written for data parallel processing systems have a unique style, and 
the process of developing programs for these types of machines is called data 
parallel programming.

	Data Parallel Processing on the CM

The model of data parallel processing used on the CM is as follows:

A single processor, called the front end, executes a program in either a 
high-level language like *Lisp or in a low-level parallel programming language 
like Paris. As the program runs, the front end transmits instructions and data 
to the CM (see ).



. The data parallel programming model of the CM

The processors within the CM store the data they receive in their own areas of 
memory, and execute the instructions they receive simultaneously. The CM 
processors can also transmit the results of their computations back to the 
front end.

In the Connection Machine system, the front end is a standard serial processing 
computer such as a Sun Microsystems Sun-4, a Digital Equipment Corporation VAX 
computer, or a Symbolics 3600 series Lisp machine.

As the front end executes its program, serial operations (those that don't 
require parallel computation) are executed directly by the front end. Whenever 
the front end comes to an operation that requires parallel computation, it 
transmits that instruction to the CM, to be executed by the CM processors.

Thus, serial code within a program is executed on the front end computer in the 
usual manner; parallel code is executed by the CM processors. The front end and 
CM operate independently; the front end can be carrying out a serial 
computation (say adding up your restaurant bill) while the CM carries out a 
parallel computation (such as working out what the same order would cost you in 
every restaurant in the country).

For the Curious: How It's Really Connected

The picture presented in  above is really a simplification. The actual physical 
connection between the front end and the CM is more involved. (See .)

The front end communicates with the CM via a Front End Bus Interface (FEBI) 
card. There can be one or more of these cards in the front end; each provides a 
separate link to a CM. Each FEBI is connected via an H-bus cable to a central 
switching board, the Nexus, inside a CM. The Nexus acts as a manager for the 
resources of the CM, allowing a front end to request that some, all, or none of 
the CM processors be made available for its use.



. The real connection between the front end and the CM

Processors within the CM are grouped in sections, each of which is managed by a 
single sequencer. It is the sequencer that handles the translation of 
instructions received from the front end into instructions that the individual 
processors can execute. Depending on the hardware you have available, there may 
be one, two, or four sequencers in the CM, each with its own associated group 
of processors.

The Nexus makes processors available to the front end by grouping sequencers 
together. Thus, if your CM has four sequencers, your front end may be connected 
to one, two, or all four of them, depending on the state of the Nexus. This is 
all transparent to a user on the front end, of course. Regardless of the number 
of sequencers that are in use, it always appears as if there is just one 
computational entity waiting for instructions at the end of that long, black 
H-bus cable.

It's not essential that you know all this to program the CM; for most purposes 
the picture of a single front end attached directly to a single CM is 
sufficient. However, keeping the more complex picture of front-end/CM relations 
in the back of your mind can help you in understanding the commands you use and 
the warning messages you see when you execute your program on a CM.

	Other Features of the CM System

Processor Selection

A program can specify that only a particular set of CM processors should carry 
out a sequence of operations. In the text retrieval example mentioned above, 
the processors that find a particular word or phrase in their articles might be 
instructed to search further for another word or phrase, while the remaining 
processors are idle. The set of processors that is currently selected to 
perform CM operations is commonly referred to as the currently selected set of 
processors, or often just as the active processors.

Processor Communication

Processors can pass messages to each other. The processors in the CM are 
connected by a general message-passing network called the router. The router 
allows each processor to send a piece of data to any other processor in the 
machine, with all processors transmitting data simultaneously, in a process 
known as router communication. In addition, the CM system has a faster form of 
communication called grid communication, which in certain cases allows 
processors to pass values to each other more efficiently.

Virtual Processors

Different CM models have different numbers of processors available for use by 
programs. The hardware of a CM always has some fixed number of physical 
processors; this may be 4K, 8K, 16K, 32K, or 64K processors, but there is 
always some magic number that represents the actual number of processors that 
are "really there" inside the CM.

This does not limit the size of the data set that a program can use, however. 
If more processors are required than are available in the hardware of the CM, 
each physical processor simulates the actions of two or more virtual processors 
by dividing up its memory accordingly and performing each operation multiple 
times.

Because of this, the number of virtual processors must always be a power-of-two 
multiple of the number of physical processors that are available within the CM. 
Thus a CM with 16K physical processors can operate as if it has 32K processors, 
64K processors, etc.

A single CM can even simulate different numbers of virtual processors at the 
same time. It is possible to define a number of virtual processor sets (VP 
sets), each having a different number of virtual processors, and to use them 
together in the same program to manipulate data sets of different sizes.

	The *Lisp Language

Given that the Connection Machine system consists of two machines, a front end 
and the CM itself, where does *Lisp itself fit into the picture?

	A Front End Language with Side Effects on the CM

The *Lisp language is an extension of the Common Lisp standard; *Lisp programs 
run on the front end just like any other Common Lisp program. However, *Lisp 
provides programming constructs and data structures that are used to control 
the operations of the CM. The *Lisp language can therefore be thought of as a 
front-end language with side effects that cause computations to take place on 
the CM.

Because *Lisp is an extension of Common Lisp, *Lisp programs must be run from 
within a Common Lisp environment on the front end. For Sun front ends this is 
Sun Common Lisp. For Digital Equipment Corporation VAX computers, Lucid Common 
Lisp is used. On Symbolics 3600-series Lisp machines, *Lisp runs on top of 
Genera. No matter where you develop and run your *Lisp code, however, you 
always have available to you the tools and features of the Lisp programming 
environment provided by your front end.

	Many Options for Executing Your Code

*Lisp comes in many forms, offering you many different ways to execute your 
code. You can run your *Lisp code "live" on physical CM hardware, in either 
interpreted or compiled form. You can also run your *Lisp code "simulated" on 
the *Lisp simulator, when CM hardware is not available. You can run your *Lisp 
code in batch, and under timesharing. This section describes each of these 
options in more detail.

The *Lisp Interpreter and Compiler

As with all Common Lisp systems, *Lisp has an interpreter and a compiler. The 
*Lisp interpreter is simply the standard interpreter of your Common Lisp 
environment, extended to understand and execute *Lisp operations. Each 
interpreted *Lisp operation makes one or more calls to Paris, the system 
software of the Connection Machine.

The *Lisp compiler is likewise an extension of the Common Lisp compiler, and is 
invoked whenever you compile a function or region of code. The *Lisp compiler 
translates *Lisp code into highly efficient Lisp/Paris code.

The *Lisp Simulator

Obviously, you can only run your *Lisp code "live" on CM hardware when there 
are processors available for you to use. Depending on the demand for the CM at 
your site, this could mean either a long wait or working in the wee hours of 
the morning.

For this reason, there is also a *Lisp simulator. This is a Common Lisp program 
that runs entirely on the front-end machine, simulating via software the 
operations of a permanently attached CM. The simulator allows *Lisp code to be 
tested and debugged when Connection Machine hardware is not available. The 
*Lisp simulator is freely available for the asking from Thinking Machines 
Corporation Customer Support.

The *Lisp simulator can be run at any time, regardless of whether hardware is 
available. The simulator is designed to be compatible with the hardware version 
of *Lisp; programs may be ported from the one to the other with little or no 
modification. Also, the simulator is written in portable Common Lisp, so it can 
be used on any computer with a Common Lisp environment-CM hardware is not 
required to use the simulator.

Running *Lisp in Batch

*Lisp code can be executed in batch mode on the CM. Doing this requires that 
you add extra code to make your program execute properly when run under batch 
processing. The CM User's Guide contains more information, along with examples 
of running *Lisp code in batch.

Running *Lisp under Timesharing

*Lisp will also run on a CM that has timesharing enabled. To use *Lisp on a 
timeshared CM, you must use a version of the *Lisp software that includes 
special timesharing support code. Check with your systems administrator or 
applications engineer for more information on running *Lisp under timesharing.



Appendix C: All the Paris You Need to Know

The Connection Machine Parallel Instruction Set, affectionately nicknamed 
"Paris," is the low-level parallel programming language of the CM. In using 
*Lisp on a CM there are a few essential Paris operations with which you'll need 
to be familiar. This appendix provides a brief description of each of them. For 
more information about these operations, see Chapter 7, "In the Lisp 
Environment," of the CM System User's Guide.

For Simulator Users: The operations described here are all part of the Paris 
substrate of *Lisp, so you won't be able to call them when you're using the 
*Lisp simulator.

	Attaching to a CM: (cm:attach)

The Paris function cm:attach attaches you to a CM so that you can start sending 
it commands. You can call it without any arguments, as in

> (cm:attach)

to attach to whatever CM hardware is available, or you can supply arguments 
that select a specific CM size, front-end interface, and even a specific 
section of a CM. You can even instruct Paris to wait (via the :wait-p argument) 
until the CM hardware is available.

> (cm:attach :8kp :interface 0) ;; Attach to 8K CM on interface
> (cm:attach :ucc0 :interface 0 ;; Attach to section 0 of CM
		   :wait-p t)		  ;; Wait until CM is available

Note: You normally don't need to call cm:attach. The *Lisp function *cold-boot 
will automatically call cm:attach for you if you are not currently attached to 
a CM. If you do call cm:attach yourself, remember that you must also call 
*cold-boot to initialize *Lisp.

	Finding Out What CM Resources Are Available

The Paris cm:finger function is used to find out what CM hardware is available 
at your site. For example, a typical call to cm:finger might look like:

> (cm:finger)
CM		Seqs	Size	Front-end	I/F	User		Idle
		Command
---------------------------------------------------------------
LANA		0	4K	cyclops	2	Zener	00:23	starlisp
LANA		---	---	cyclops	0	(nobody)
	256K memory, 32-bit floating point
	1 free seqs on LANA -- 1 -- totalling 4K procs

This shows that the user "Zener" is attached to sequencer 0 of the CM named 
"LANA," and is using *Lisp. It also shows that sequencer 1 of LANA is 
available, and that you can attach to it via interface 0 from the front-end 
machine "cyclops." You can do this by typing

> (cm:attach :4kp :interface 0)

or simply by typing

> (cm:attach)

	Finding Out if a CM is Attached: (cm:attached)

The Paris function cm:attached is a boolean test that checks whether a CM is 
currently attached. It returns two values. The first value is t when a CM is 
currently attached and nil otherwise. The second value is always nil unless an 
error occurred while looking for a CM.

For example:

> (cm:attached)	;; With a CM attached, returns...
T
NIL

	Timing *Lisp Code

The Paris function cm:time is used to time a section of code. You can wrap a 
call to cm:time around any section of *Lisp code to see how long it takes to 
execute. The cm:time function displays three kinds of information: the total 
elapsed time taken by your code, the amount of time the CM was actually active 
executing your code, and the percentage of the total elapsed time that the CM 
was active.

For example:

> (cm:time (sort!! (random!! 10) '<=!!))

Evaluation of (SORT!! (RANDOM!! 10) (QUOTE <=!!)) took 0.016738 seconds of 
elapsed time,
during which the CM was active for 0.011261 seconds
or 67.00% of the total elapsed time.

In this example, the total elapsed time was approximately 17 milliseconds, the 
CM active time was about 11 milliseconds, and the percentage of CM active time 
versus elapsed time was 67%.

	Detaching from a CM: (cm:detach)

The Paris function cm:detach is the opposite of cm:attach, and is used to 
detach the CM so that other users can attach to it. It is called without any 
arguments, as in

> (cm:detach)

Note: Simply exiting from *Lisp will, in most cases, detach you from any CM to 
which you were attached. However, it is considered good form to call cm:detach 
yourself so that you don't accidentally leave the CM tied up when you exit.



Appendix D. Sample *Lisp Startup Sessions

The following are annotated examples of *Lisp hardware and simulator sessions 
on a Sun-4 front end, showing you the output that you're likely to see in 
starting up either version of *Lisp. All annotations are included as comments, 
of the form #|...|#. (Note: These comments are not displayed by *Lisp itself.) 
Commands that you type are preceded either by the UNIX #%" prompt or the Sun 
Common Lisp #>" prompt.

	*Lisp Hardware Startup Session

#|	To start up *Lisp, you must type the UNIX-level command that loads
	the *Lisp software. In this sample session, it is: |#

% /usr/local/starlisp

#| 	The first messages that you see are printed by Sun Common Lisp,
	showing the version of Common Lisp you are using,
	along with various copyright notices.	|#

;;; Sun Common Lisp, Development Environment 3.0.5 (Rev 01), 30-Aug-90
;;; Sun-4 Version for SunOS 4.0 
;;;
;;; Copyright (c) 1985, 1986, 1987, 1988 by Sun Microsystems, Inc., All Rights 
Reserved
;;; Copyright (c) 1985, 1986, 1987, 1988 by Lucid, Inc., All Rights Reserved
;;;
;;; This software product contains confidential and trade secret
;;; information belonging to Sun Microsystems.  It may not be copied
;;; for any reason other than for archival and backup purposes.

#|	Following this are messages printed by Thinking Machines' Corporation
	software. |#

#|	The first thing the *Lisp software does is look for the
	"CM initializations" file. This file contains commands to perform any
	required initialization steps, such as loading software patches. |#

;;; Loading source file "/cm/patch/initializations.lisp"

#|	Depending on the version of *Lisp you are using, you may or may not
	see the next message, which informs you of the current state of
	the Lucid Common Lisp compiler: |#

;;; You are using the compiler in production mode (compilation-speed = 0)
;;; Generation of argument count checking code is enabled (safety = 1)
;;; Optimization of tail calls is enabled (speed = 3)

#|	One of the last things the "CM initializations" file does is print a
	message telling you the current patch level of *Lisp (that is, the
	total number of patch files that have been loaded). If you need to
	report a problem to Thinking Machines Corporation Customer Support,
	you should include the current patch level of your software, so
	that Customer Support personnel will know which patches you have
	loaded. In this case, 26 patches have been loaded, so *Lisp is at
	"Patch Level 26". |#

;;; *Lisp Patch Level 26

#|	Next, a header is printed showing the current version of the Thinking
	Machines Corporation software that you are running. |#

;;; Connection Machine Software, Release 6-0 with *Lisp 6.0 and
;;; CM Graphics 2.0
;;;
;;; Copyright (C) 1990 by Thinking Machines Corporation.
;;; All rights reserved.

#|	Finally, Lucid Common Lisp loads the file lisp-init.lisp from your
	home directory, if you have already created such a file. |#

;;; Loading source file "/users/admin1/massar/lisp-init.lisp"

#|	Massar's lisp-init.lisp file includes commands to display information
	about current the state of the Lucid and *Lisp compilers. |#

The Lucid Compiler is in DEVELOPMENT mode
The *Lisp Compiler is ON
The *Lisp Compiler Code Walker is ENABLED
The *Lisp Compiler safety level is set to FULL SAFETY
The *Lisp Compiler warning level is HIGH
The *Lisp Compiler *use-always-instructions* mode is OFF

#|	At this point, the *Lisp software is loaded, and you will see the
	Lisp prompt ">", indicating that *Lisp is ready to accept commands.
	The first thing to do is type the command (*lisp), to select the
	*Lisp package: |#

> (*lisp)
Default package is now *LISP.

#|	Now type the command cm:finger to see if any Connection Machine
	hardware is available. In this case, the output of cm:finger is: |#

> (cm:finger)
CM           Seqs  Size     Front end  I/F      User     Idle    Command
------------------------------------------------------------------------
LANA         ---   ---      cyclops      2      (nobody) 
LANA         ---   ---      cyclops      0      (nobody) 
	     256K memory, 32-bit floating point
	     framebuffers on sequencers 0 1 (seqs 0 1 are free)
	     CMIOC on sequencer 0 (seq 0 is free)
             2 free seqs on LANA -- 0 1 -- totalling 8K procs

#|	This message shows that the CM named 'LANA' has two free sequencers.
	To attach to LANA and initialize *Lisp, we type: |#

> (*cold-boot)

Not attached.  Attaching...
;;; Loading source file "/cm/configuration/configuration.lisp"
4096
(64 64)
> 

#|	At this point, *Lisp is loaded, CM hardware is attached, and both
	*Lisp and the CM have been initialized. *Lisp is now ready for you to
	begin loading and running your own *Lisp programs. |#

	*Lisp Simulator Startup Session

#|	As with the hardware version of *Lisp, type the UNIX-level command
	that loads the *Lisp software. In this case, it is: |#

% /usr/local/starlisp-simulator

#|	Sun Common Lisp displays its version and copyright information: |#

;;; Sun Common Lisp, Development Environment 3.0.5 (Rev 01), 30-Aug-90
;;; Sun-4 Version for SunOS 4.0 
;;;
;;; Copyright (c) 1985, 1986, 1987, 1988 by Sun Microsystems, Inc., All Rights 
Reserved
;;; Copyright (c) 1985, 1986, 1987, 1988 by Lucid, Inc., All Rights Reserved
;;;
;;; This software product contains confidential and trade secret
;;; information belonging to Sun Microsystems.  It may not be copied
;;; for any reason other than for archival and backup purposes.

#|	The the "CM Initializations" file is loaded, displaying the current
	*Lisp patch level: |#

;;; Loading source file "/cm/patch/initializations.lisp"
;;; *Lisp Patch Level 0

#|	Your "lisp-init.lisp" file is loaded, if you have created one: |#
;;; Loading source file "/users/admin1/massar/lisp-init.lisp"
The Lucid Compiler is in DEVELOPMENT mode

#|	Now the simulator is loaded and ready for use. To initialize it, type
	the *Lisp command to select the *Lisp software package: |#
> (*lisp)
Default package is now *SIM.

#|	And type *cold-boot to initialize *Lisp. |#
> (*cold-boot)
Thinking Machines Starlisp Simulator.  Version 20.0
1
(8 4)
>

#|	The *Lisp simulator is now loaded and ready for you to begin loading
	and running your own *Lisp programs. |#


« March 2024 »
Su Mo Tu We Th Fr Sa
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
 

Powered by Plone CMS, the Open Source Content Management System

This site conforms to the following standards: