[Vm-dev] Tangential: A Lisp Interpreter Implemented in Conway's Game of Life

[Vanessa Freudenberg]

On Sat, Jan 21, 2023 at 00:48 Stéphane Rollandin <lecteur at zogotounga.net>
wrote:

>
> > I can not map
> > that implementation to the rules of the game... Can someone explain to
> > me or point me to a paper/description of why that implementation works?
>
> There is the Byte paper, around
>
> https://archive.org/details/byte-magazine-1981-08/page/n205/mode/2up?view=theater
>
> The figure there shows how ancilliary forms are used to count, in
> parallel, the number of neighbors for each point in the pattern.
>
> For each direction in the Moore neighborood, the pattern is shifted and
> these eight shifted grids are combined together.
>
> This is an addition in base two, and we need to count up to eight, so
> the algorithm uses three forms (nbr1, nbr2 and nbr4) to store the
> corresponding bits, and two other forms (carry2 and carry4) to store the
> bits carried from one bit to the next (so here from nbr1 to nbr2, and
> from nbr2 to nbr4), just as you need to do when performing an addition
> by hand.
>
> The last step (the last four lines in #nextLifeGeneration from the Byte
> paper) generates the next pattern from nbr1, nbr2 and nbr4. The rules of
> the Game of Life are encoded here in the successive combination rules,
> in a nifty and quite obfuscated way that I did not even tried to
> comprehend.
>
> Stef



Right. You basically need to understand how binary counting works at a
logic-gate level, to be able to comprehend the neighbor counting code.

Typically that logic is invisible. I love this mechanical version:

https://youtu.be/zELAfmp3fXY

You can see the bits (the big 0s and 1s). The carry is the little latch
sticking out to the left, and it gets set whenever a bit flips from 1 to 0,
which means the next bit has to flip.

The “bit + carry” logic is called a “half adder”, you can google that, but
basically it generates the next bit and carry from the previous bit and
carry using two logic operations, an XOR for the bit and an AND for the
carry.

With that understanding, Dan’s explanation in the Byte article might make
more sense – it does the XOR and AND for all pixels at the same time.

The 3 bit result count is then used to determine if a cell should be born,
survive, or die. Again, logic ops do that for all pixels at once.

The Life rule is that cells with 2 or 3 neighbors survive, any with fewer
or more neighbors die, and any empty cell with 3 neighbors is born.

To implement that rule with minimal logic, we restructure it a bit

A live cell will be there in the next generation if
(1) the cell is alive AND has 2 neighbors
(2) OR has 3 neighbors (independent of itself being alive or not)
(3) BUT it must not have 4 or more neighbors

(1) is implemented as “self AND 2s” because the 2s bit is only set for 2, 6
and 7 neighbors (010, 110 and 111 in binary), and we deal with the >= 4
neighbors case in (3)
(2) is implemented as “self OR (1s AND 2s)” because those bits are only set
together for 3 and 7 neighbors (011 and 111 in binary), and we deal with
the 7 neighbors case in (3)
(3) is implemented as “self AND NOT 4s” which kills any remaining 6 and 7
neighbor cells (4, 5, and 8 neighbor cells wouldn’t have made it to this
step anyways because their lower bits look like 0 and 1 neighbors: 100,
101, and 000)

This also explains why we don’t need to count to 8. With 3 bits we can only
count to 7, if we add one more to 7 we get 0. But in Life this is fine
because both cells with 8 and 0 neighbors have the same result.

Hope that helps,
Vanessa

>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20230122/478cccc8/attachment.html>