dana@rucs.runet.edu (Dana Eckart) (07/08/90)
I'm interested in learning what (if any) languages have been designed
for programming cellular automata. I am aware of CAM-FORTH (used for
programming the CAM-6 machine), but am unaware of any other languages.
Any pointers would be greatly appreciated. Thanks in advance...
J Dana Eckart INTERNET: dana@rucs.runet.edu
SNAIL: P.O. Box 10865/Blacksburg, VA 24062-0865hiebeler@raven.lanl.gov (David Hiebeler) (07/09/90)
In article <1142@rucs.runet.edu> dana@rucs.runet.edu (Dana Eckart) writes: > I'm interested in learning what (if any) languages have been designed > for programming cellular automata. I am aware of CAM-FORTH (used for > programming the CAM-6 machine), but am unaware of any other languages. This is a great question, which I've been thinking about for some time. There aren't any other real "languages" for doing CA that I'm aware of. Some packages (e.g. Cellsim, CA Lab, CA Sim) have pseudo-environments for generating CA rules though. Cellsim and CA Lab both let the user program the rule himself/herself (at least the main part of the rule, i.e. the lookup-table or compute-new-cell-value functionality). Fortunately, that's pretty simple to do in most languages. For example, in C, to program the game of Life, you just need a few handy macros, variables, a good Makefile, and a main() to link in. Then, the only burden placed on the user is to write a simple function like: cell LifeRule(center, north, south, east, west, nwest, neast, swest, seast) cell center, north, south, east, west, nwest, neast, swest, seast; { int nbor_sum; nbor_sum = north + south + east + west + nwest + neast + swest + seast; if (nbor_sum == 3) /* if 3 neighbors alive, become alive */ return 1; if (nbor_sum == 2) /* if 2 neighbors alive, stay in current state */ return center; else /* if less than 2 or more than 3 active neighbors, die */ return 0; } (where "cell" is typically typedef'ed to unsigned char or unsigned int) That's roughly (although not exactly) how it looks in Cellsim. (In Cellsim, the function gets 1 parameter of type "moore_nbors", and then you call a "Get_moore_nbors" macro to extract them. There are also linear_nbors, vonn_nbors, and margolus_nbors). I believe CA Lab is pretty similar, although it has support for Pascal and BASIC as well. Cellsim only supports C, although it would be very easy to write the support-routines for Pascal or other languages. Cellsim also supports similar functions for generating rules that are too large for lookup-tables. In fact, it looks at the number of states and the neighborhood of the rule (determined by the filename), and decides whether to make it a lookup-table, or a "computed-function" rule. With computed-function rules, the update function is called once for every cell in the array, to compute the new value. It's pretty slow, but what else can you do if the rule is too big for a lookup table? Cellsim runs on Suns, but also can attach to a Connection Machine. To write computed-function rules on the CM, you write the rule in C/Paris, a collection of data-parallel routines specific to the CM. They run very quickly on the CM, since the update-function operates in parallel. CA Sim, on the other hand, supports a graphical programming system for constructing CA rules. You get a big window full of buttons and items that you select to construct your rule. CA Sim runs on a Mac and was written by Ken Karakotsios, who reads this newsgroup. Ken, maybe you'd like to summarize the features in CA Sim that help users construct rules? I've used the CAM-Forth software with CAM-6 for a few years now. Although I'm still not crazy about Forth, the environment is nice in the sense that it's very interactive and flexible. Right now, I'm developing a new software library to control the newer jazzed-up version of CAM-6, called CAM-PC. I'm attempting to incorporate the most useful features (in my opinion) for CA programming and to keep the system fairly easy-to-use and readable. (CAM rules written in Forth are often hard to read; it's very easy to write messy Forth). After it's well-along, I plan to take that environment and attach it to a purely-software CA simulator, for those who can't afford the special-purpose hardware. I expect that I'll first do a PC-based simulator, since the CAM plugs into PC's, but I'll probably port it to X-windows shortly after that. I expect to complete the CAM-PC software within a month or two, but probably won't have time to start porting the stuff to a software simulator until the Spring. I'll probably write at least one paper about all this sometime in the next six months, so I'll mention it here when I have something more definite. At some point, I may post a rough outline of the specifics of the environment, to get some feedback from people here. -- Dave Hiebeler | Internet: hiebeler@heretic.lanl.gov Complex Systems Group | Bitnet: userF3JL@rpitsmts MS B213, Theoretical Division | UUCP: crdgw1!automtrx!hiebeler Los Alamos National Laboratory / Los Alamos, NM 87545 USA
karakots@apple.com (Ken Karakotsios) (07/14/90)
In article <1142@rucs.runet.edu> dana@rucs.runet.edu (Dana Eckart) writes: > I'm interested in learning what (if any) languages have been designed > for programming cellular automata. I am aware of CAM-FORTH (used for > programming the CAM-6 machine), but am unaware of any other languages. In article <R+R$?J|@rpi.edu> hiebeler@raven.lanl.gov (David Hiebeler) writes: > CA Sim, on the other hand, supports a graphical programming system > for constructing CA rules. You get a big window full of buttons and > items that you select to construct your rule. CA Sim runs on a Mac > and was written by Ken Karakotsios, who reads this newsgroup. Ken, > maybe you'd like to summarize the features in CA Sim that help users > construct rules? My intention was to design a method for programming CA rules without making the user write code. I wanted something that could be programmed without worrying about syntax, or where to find a compiler, or how to link in code, etc. I wanted every rule entered by the user to "run", though it may not do what the user intended if there is a "mistake" (I've run across a few interesting rules that were "mistakes"!). This is sort of the "pocket calculator" approach. The negative aspects are 1: Execution speed and 2: Flexibility. Because the user defined rules are not compiled code, nor a look-up table, they are not as fast as "hard-wired" rules. Also, the language allows a large but finite number of different rule algorithms (I estimate that there around 2^107 rules possible with this implementation of the programming method). The basic scheme is to build up a rule out of between 1 and 128 steps (for a single generation of the CA), where each step is called a "Simple Rule" (SR). Each SR is specified by a "dialog box" which contains buttons, check boxes, and number fields. You program the rule by clicking on buttons and check boxes with the mouse, and by setting values in the number fields. The dialog box (for a single SR) is divided into 6 regions: 1) Trigger Region: Describes which cell states (values) trigger this particular SR. If an SR is triggered for a particular cell, then a new value is computed for that cell. 2) Neighborhood Region: This has a grid of checkboxes which define the neighborhood of the cell which is being updated. You click on the cells which make up the neighborhood you want to include for this particular SR. 3) Function Select Region: You pick from a predefined set of operations on the selected neighborhood (sum, average, min, max, etc...) to compute an intermediate value called F(n). This value is used in the following regions. 4) Function Test Region: The value F(n) is tested against some criteria which you set. The criteria are either: A: See if F(n) falls within some range, or B: see if F(n) has some particular relationship to the current value of the cell being updated. The result of this test is used to select between one of the two following regions. 5) Test True Region: If the result of the test is True, then this region specifies how to compute the new value of the cell. You can pick two operands from a list of choices, and select either a logical or an arithmetic operation to be done with the operands. The result of this operation is the new cell value. (This value can be further modified in the current generation by more SRs). 6) False Test Region. If the result of the test is False, then this region specifies how to compute the new value of the cell. You can pick two operands from a list of choices, and select either a logical or an arithmetic operation to be done with the operands. The result of this operation is the new cell value. (This value can be further modified in the current generation by more SRs). (I apologize if this description is somewhat unclear; it could really benefit from some pictures.) Life can be implemented in two SRs. I have just figured out how to model hexagonal lattices with these user programmable rules. I'll try and post more info (and a few custom rules) on this next week. Like most first generation designs, my programming scheme falls far short of the ideal. I have ideas for extensions and improvements; now if can just find the time... Ken Karakotsios karakots@apple.com In cyberspace, no one can hear you sneeze...