RE: Conway's Game of Life (cellular automata)

["Anton van Straaten" <anton@appsolutions.com>]

> you left open the question of how
> HTDP would propose to design the Life program.

I think my comments about abstraction relate to something HtDP says about
the importance of creating abstractions, which should have well-defined
contracts.  The section "Abstracting Designs" covers this.  Also, related to
my points about generalized functions, HtDP says "In many cases, an abstract
function is useful in a much broader array of contexts than we first
anticipate and makes functions easier to read, understand, and maintain"
(from "Abstracting from Examples").  I'll relate to this below.

But I can't speak for the authors of HtDP.

> Sure did!  That's what I think the TLS/TSS functional programming
> style is: consume lists.

Perhaps I'm wrong, but I would generalize that to say that what they're
really teaching is to think and solve problems recursively.  In Scheme,
lists make sense for this purpose.  Nevertheless, once again, the approach I
described could be adapted to lists.  I think it's more important to try to
separate the design from the low-level implementation details.  Perhaps this
isn't covered in TLS/TSS; I've never worked through them from beginning to
end.

> But I ran into all kinds of
> mutability problems, so the list of list functional version was easier
> to code up!

If you want to build a vector recursively, without mutation, you're pretty
much going to have to use a list (or something a lot like it) while
building, then convert it to a vector when you're done.  That shouldn't be
difficult (list->vector), and you'll still benefit from the addressability
of the "matrix" once you're done.  In fact, this ought to give the best of
both the list & vector worlds.

It should be recognized that the requirement to use lists here is really an
artifact of lower-level implementation issues; it's easy to imagine a vector
that can be built recursively, but it so happens that Scheme's vectors don't
allow it.

> Your `count-surrounding-black-cells' is maybe too cute, why not
> redefine `matrix-sum' to not add up the "origin" of your range, then
> `count-surrounding-black-cells'  doesn't need `cell-value' as an
> argument.

There are reasons for that.  First, I like to write code that's going to be
useful to me in other contexts (see HtDP quote above); a matrix-sum that
doesn't add the origin might or might not be, but I guessed it wouldn't be.

The cell-value argument is actually there as part of a convention.  When
you're writing routines which map over things like vectors and matrices, it
tends to be useful to pass through both the value of the current location
and its coordinates.  You're correct that this isn't essential in the
'count-surrounding-black-cells' case; the subtraction could actually be
moved up a level, to new-cell-state, or as you say, it could be handled in
(a possibly less generic) matrix-sum.

> BTW I think cellular automata all use the nearest neighbors, so we
> wouldn't be summing over a larger range.

Again, I was thinking more generally than that.  In fact, I do have a
matrix-map function in a financial analysis system that I work on, and
that's part of what led me in that direction.  I like inventing wheels as
few times as possible, and the sorts of solutions one chooses make a big
difference to how often one has to do that.

> But much different functions
> are used on the nearest neighbors.  Just keeping it to 0s and 1s, I'm
> thinking of 2^{2^9} such `new-cell-state' functions, there are 2^9 0/1
> configurations for the cell & its nearest neighbors, and each
> configuration get sent by `new-cell-state' to either 0 or 1.
>
> This shows an inelegancy of the x/y approach: your function
> `new-cell-state' does "the same thing" no matter what x & y are.  Of
> course, the cell & its nearest neighbors change as x & y vary, but the
> function in 2^{2^9} is the same everywhere on the board.  It's not
> like we calculate one way in Germany and a different way in the US.

I'm not sure I follow you.  x & y is simply a concise way to specify a set o
f nine cells, in this case, and potentially, a larger set, although you're
saying that for this specific application a larger set isn't needed.

What's a better alternative?  Presumably passing the nine individual cell
values through isn't any better.

If you're saying that you want to parameterize the behavior of the
new-cell-state function, I can go along with that, but that doesn't have
much to do with x & y being passed to new-cell-state.  Simply decide on the
parameters needed by the functions you want to be able to support - in the
case of Life, it's just 'count' - and make sure that the appropriate
function is provided at some level, perhaps as a parameter to
'next-generation' or at an even higher level, such as in the overall
iteration function.  Then new-cell-state can become something like:

  (define (new-cell-state cell-value x y)
    (decide-cell-state cell-value (count-surrounding-black-cells cell-value
x y)))

Then for Life, we have:

  (define (decide-cell-state-for-Life cell-value count)
    (if (or (= count 3) (and (isblack? cell-value) (= count 2)))
        black-cell-value
        white-cell-value)))

At some level, 'decide-cell-state' would be set to
'decide-cell-state-for-Life', presumably by passing the latter through as a
parameter.

Were you saying that what I've turned into decide-cell-state didn't need x &
y?  I don't see that as an "inelegancy", although by my own reuse criterion,
the separated version is better.

Anton