life.txt

26 Mar 1998

Copyright 1994-98. S. Weyer.  All Rights Reserved Worldwide.



See life.htm for introduction.



Additional implementation notes for life.nwt



Contents:

- life.txt   -- this file

- life15.pkg -- a ready-to-install package (created by Newt)

- life.nwt   -- Newt source

- life.htm   -- help file (HTML) to create help book

- life.bit   -- LifeIcon



----------

Development and "Newt"



If you would like to construct and modify Life directly on your Newton,

obtain the latest version of



- "Newt" (newt-devenv-34)  -- an environment for developing applications

  saving as packages directly on your Newton



- "Sloup" (sloup-21) a text/data transfer utility (both shareware)



from your favorite Newton server/archive (internet (AMUG, TVNUG, info-mac,...), AOL,

Compuserve). See "Develop" and "Author" help pages. Contact me if you

have trouble finding Newt, using it initially, or have questions about

registering it.



Registered Newt users receive a 80+ pp. introductory manual, and access to

200+ examples. This includes NewtPFB (an interactive tutorial, similar to

NewtATut), and LifeCnst.pkg plug-in for building versions of Life with

native code.



For more development details, see "Building and Transferring Life" (later).



----------

Revision History:

Life 1.5 (26 Mar 98)

- updated URLs and help

- uses info button

- compressed package



Life 1.4 (1 Jan 96)

- NOS 2.x compatible

- integrates 6 display/speed options (selectable via "method" picker)

  2 different representations: array or bitmap

  3 different styles: object-oriented, inline, native(RISC) code

- adds "gen" picker for disabling gen# update or doing timing

- line gesture to fill area, scrub gesture to erase area

- created with Newt Development Environment

- includes Newt source



Life 1.3N & life13.nwt (11 Aug 95) [non-public releases]

- [very similar to Life 1.2B & life12b1.nwt -- available earlier to Newt users]

- faster generation from native code for several methods

- for increased speed, suppress Gen: refresh by tapping on it



Life 1.2B (12 Nov 94)

- limits width of universe to 30 (width of NewtonScript integer)

- caches/operates on rows as longint (or NIL) rather than bitmap directly

- inlines inner-loop getCell accesses for greater speed (vs. clarity)

- does not display the empty border columns/rows

- numbers x (bit) positions from right to left

- handles scrub gesture for Clear (see LifeDraw:viewGestureScript)

- selectable grid sizes (see gridSize)

- generates faster (1.5 - 3.5x Life 1.2) and allows larger grids

  by using a bitmap data structure for storage and drawing



Life 1.2 (12 Nov 94)

- modifies symbol names/program structure to be more consistent with 1.2B

- fixes button highlighting glitch (sibling order)



Life 1.1 (15 Oct 94)

- uses 0/1 for cell values rather than nil/true

- allows patterns to be selected/added

- adds a grid (when stopped)



Life 1.0 (18 Sep 94)

- adds a "Clear" and "Next" button

- adds a generation counter.

- adds a "Repeat" button -- which invokes "Next" in the background until

  you tap "Stop" (or all cells are empty)

- adds an "Info" button and help book

- avoids allocating/examining empty rows/columns where possible to

  improve speed drawing and generating



Life "0.1" (Mar 94)

- see "Life with NewtonScript" by David Betz in Byte, March 1994, pp. 191-194.

This article provided inspiration, an initial framework and a few main methods.



The early versions are quite usable for small patterns, but not blindingly

fast for more sparse or spreadout patterns -- the emphasis is on the complete

application and learning programming.  There is also another source version

life12b.nwt (available to registered Newt users) which is uses the same basic

bitmap representation as life13.nwt, but is slower and perhaps more

understandable since it is less heavily optimized).



If you would like to encourage me to develop and distribute this and other

examples, I encourage you to register Newt (kind words also appreciated).



----------

Transferring and Building Life



Use your favorite transfer mechanism to move the text from your desktop system

to the Newton Notepad. This file is formatted to be used most easily with

Sloup.  ----- delimits separate notes.



To build the Life application, install Newt (3.4 is the latest version at

time of this release). If you would like to save the application as the

package to run it standalone later, also install the NewtPack plug-in, which

comes with Newt. If you would like to use native (faster) methods for Life

in Newt, install the LifeCnst.pkg plugin (available to registered Newt users)

-- this way you could customize the application while also gaining extra

performance by borrowing those methods from the Life "library".



If you are not going to transfer the Life icon (life.bit file) with Sloup,

comment out the icon line inside _package in the life.nwt source.



Start Newt, select the folder at top where you stored the source.



If you are low on heap (esp. on 1.x MessagePads), you may want to "comment out"

the two long in-line methods: Life._arrI.nextGeneration and Life.bitI.nextGeneration

by changing the names, e.g.,

  xLife._arrI.nextGeneration

  xLife._bitI.nextGeneration

This will remove them from the build process, and Life will just

use the generic nextGeneration method;

when you're done, browse to #newObject to free up a little more heap.



To include a help book, either uncomment out xLife.helpBook+pageX and the lines after helpBook:;

or if from HTML document, see after build.



Tap Expr, select :doObj('build,'Life), tap Eval



If creating help book from HTML and Newt's Cape,

tap Expr, select :createHelpBook(), tap Eval.



After help book successfully created, copy its reference into PFB app:

tap Expr, select PFB:setHelpBook(), tap Eval.





Some simple modifications you might try:

- add other patterns in patternPicker.patterns array (and names in labelCommands)

- change MakeOval to MakeRect in drawDots

- change the rules (nextGeneration)



Note: constants such as vfFillWhite can be used, but this requires additional

plug-ins, e.g., misccnst.pkg to define these at development time.



If you would like to run your version of the Life application later without

having to recompile the sources in Newt, and you have NewtPack installed,

tap the Save button (in Eval Controls) when Life is open; or Eval  :saveApp(Life)



If you have further optimizations that you would like to contribute, feel free

to send them to me, and if I incorporate them, you'll be recognized.



----------

Implementation:



This version of Life show several different implementations.

There are two basic representations of dots: "arr" and "bit".



"arr": internal representation of rows as arrays of cells;

the drawing is done cell-by-cell. [similar to an earlier version -- Life 1.2,

and to Betz' Byte article]



"bit": internal representation of rows as words in a bitmap;

the drawing is done directly with the bitmap. [similar to Life 1.2B]





There are three optimization variations for each: "", "I", "N"



- none.  default. more object-oriented -- uses same :nextGeneration method



- "I" (Inline). :nextGeneration inlines (i.e., substitutes definitions for)

  :getCell,:getRow, :setCell,:setRow methods



- "N" (Native). :nextGeneration is native (RISC) compiled code.

  For development, this requires you install the LifeConst.pkg plug-in so that you

  can use/copy the constants while still modifying the main application on your Newton



So, the source supports 6 versions:

- "arr" uses arrays for representing rows; it is written in a very object-oriented style;

  uses the same :nextGeneration method as "bitO".



- "arrI" same as "arr" but in-lines :nextGeneration

  i.e., substitutes definitions for :getCell,:getRow, :setCell,:setRow methods.



- "arrN" uses native code for :nextGeneration



- "bit" uses a bitmap for representing and drawing cells.

  it uses the same generic :nextGeneration method as "arrO"



- "bitI" same as "bit" but inlines :nextGeneration



- "bitN" uses native code for :nextGeneration and :makeUniverse

   (the NewtonScript is identical to "bitI" but without declarations;

   I did not include the declarations here -- although they are ignored

   by the Newton compiler for NOS 2.x, the 1.x compiler generates errors).



The Life application and package was created entirely with the Newt

Development Environment. (LifeCnst.pkg plug-in was created with NTK).

The help book was created with Newt's Cape (it is also possible to create

simple help books directly with Newt).



----------

Objects:



Life -- the application (floating view)

  split into several sections to make editing on Newton more manageable

drawArea -- an embedded view to handle drawing

titleObj -- title at top of Life view

status -- status bar at bottom of Life view

clearButton, nextButton, repeatButton, zhelpButton -- embedded in status

gridPicker -- picker for selecting grid size

methPicker -- picker for switching between various "arr" and "bit" methods

patternPicker -- picker for selecting patterns

genPicker -- picker for update/timing, generation counter

helpBook -- help book data structure

helpView -- dynamic "Tiny Tim" help reader view

ButtonBounds -- development-time method for computing location of status buttons



"method frames"

there are 6 frames that contain 9 methods each that define the representation,

computation and display for the six versions included: "arr", "arrI", "arrN", "bit", "bitI", "bitN".

when the user makes a choice in "method picker", these are copied into the current

Life application (view). [original "arr" defs are still in the app template]



Generally, there are many ways to write "nextGeneration". I chose one that

hopefully isn't too hard to follow, works for both the array and bitmap

representations, and performs reasonably well. With some INT declarations

put in, the same version produces "bitN" which is quite fast.  I would be

interested in any faster algorithms or programming tricks also. (see "Timing"

below).



-----

Coordinates:



To maximize performance for the "bit" implementation, I constrained the x

coordinate to be between 0 and 29 (numbered from right to left), to

correspond to bit positions in a NewtonScript integer ("long"); the "array"

implementation follows these conventions also in order to share methods. I

have other implementations that can access multiple longs, but large grids

are difficult to display and impractical to compute anyway.  The y

coordinate is numbered from top to bottom. Cells are square.



-----



You can speed up computation somewhat by selecting "gen <0>".

This indicates that the generation counter should not be updated.



-----

Benchmarks



To do benchmarks, I would recommend saving the application first. This

maximizes the amount of heap that is available (and minimize the amount

of time that Life spends in gc (garbage collection)).



In order to see timing results printed, do one of the following:

- connect the NTK Inspector

- or, open Sloup (in Inspect? mode) with a terminal emulator

  [you can drag Sloup off right screen edge; also toward bottom

  so it's not totally on grid]

- or, open Newt (and turn on Print?)



Select "gen <time:40>" to do 40 iterations of a pattern.



Draw your pattern, tap Repeat.



time: <ticks = 60ths of a sec> will appear.



note: generation counter is set to 0

after Clear, new method picked, or timing complete





Two simple patterns that indicate roughly the performance profiles

of these different methods.



- glider. small dynamic pattern



- 4 blocks (one in each corner of grid). maximize number of rows examined





I used a 26x29 grid. I did two tests for each data point and took the

average. I tested on a MP100(1.3), MP110(1.3) and MP120(2.x).

If anyone would like to redo these, or provide data for other MPs,

send to me and I'll include.





											xx	...	xx

											xx		xx

				 x							...		

				x							xx		xx

				xxx							xx		xx

				glider						corners4								



		100		110		120			100		110		120

		----	----	----		----	----	----

arr		1100	1030	 472		3775	3700	1058

arrI	 785	 750	 385		2374	2330	 683

arrN 	 575	 520	 405		1336	1320	 708

bit      930	 940	 362		3760	3575	 962

bitI     695	 682	 284		2487	2345	 573

bitN     237	 215	 213		 243	 220	 216





Some initial observations:

(of course, it's dangerous to draw any very general conclusions

based on such few data points; your mileage may vary depending on

the patterns you try, amount of heap, etc.):



- large patterns generally take much longer time (though bitN is almost constant)

- the NOS 2.x NewtonScript interpreter can be much (2x-3x) faster than 1.x

- some native code (arrN) can be slower on 2.x! (an anomaly worth investigating)

  advantage of bitN much less on 2.x

- MP100 a little slower than MP110



I'd be interested in other results/observations on these and

other algorithmic variations.