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

[Hernán Wilkinson]

Hi Vanessa!
 Yeah thank you for the explanation, pretty clear.
 I understood the algorithm after reading the article and looking at it
with a co-worker
 He did some refactorings that will share for sure

Hernan

On Sun, 22 Jan 2023 at 19:56 Vanessa Freudenberg <vanessa at codefrau.net>
wrote:

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

*Hernán WilkinsonAgile Software Development, Teaching & Coaching*
*Phone: +54-011*-4893-2057
*Twitter: @HernanWilkinson*
*site: http://www.10Pines.com <http://www.10pines.com/>*
Address: Alem 896, Floor 6, Buenos Aires, Argentina
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20230123/70df7a03/attachment.html>