I'm not sure if you were asking for help, but I spent awhile hacking the program into a working state. I hope this write-up is useful as a way of getting familiar with Arc.
I started with the original file and debugged slowly. I'll try my best to go step-by-step, illustrating my thought-process. Seemed best to start from the REPL (read-eval-print-loop).
arc> (load "game-of-life.arc")
Error: "reference to undefined identifier: _tbl"
I'm not sure if you defined a different file (or modified ac.scm or such) so that tbl is a function, but I assume you meant table:
(= universe* (tbl)) ; changed this
(= universe* (table)) ; to this
arc> (load "game-of-life.arc")
Error: "Can't take cdr of x1"
I notice you have a particular with statement. Unlike let, which is for a single variable name, with is for several variables. As such, you need to wrap the variable declarations in an extra set of parentheses. I.e., instead of
Hm. Not the clearest message. I see the hash-tables have the same fields as the cell template. What the error means is that there's some code that looks like
(= (findfellas cell) cell)
After some searching, it turns out that
(def create-cell (x y)
(= c (inst 'cell 'x x 'y y 'state 0 'fellas () 'index (cindex x y))
(findfellas c)
c))
has some unbalanced parentheses. The (findfellas c) and c are both still inside of the =. The way = works is to pair up alternating variables/values, like:
arc> (= x 1 y 2)
2
arc> x
1
arc> y
2
So, in effect, this is trying to do
(= (findfellas c) c)
Rebalance the parens
(def create-cell (x y)
(= c (inst 'cell 'x x 'y y 'state 0 'fellas () 'index (cindex x y)))
(findfellas c)
c)
In the REPL again,
arc> (load "game-of-life.arc")
Error: "reference to undefined identifier: _x"
Well, where's that coming from? I search the source code for some unbound x. create-cell and cindex are okay, so the only other place is in findfellas, where we find
(with x1 (- c.x 1) x2 c.x x3 (+ c.x 1)
As rtnz noted,
c.x
expands into
(c x)
which tries to look up the variable x, which fails. What you want to access the fields of the template is
c!x
which expands into
(c 'x)
Notice the single-quote mark. This is a symbol. Symbols are covered in the Arc tutorial, so I'll spare you, but they have interesting uses I'll get back to later.
Similar instances of a.b instead of a!b produce the errors
Error: "reference to undefined identifier: _y"
Error: "reference to undefined identifier: _fellas"
i.e., of the form (sequence index). Here, you have (index sequence). Oops! Reverse the order, and we're good.
(let pos (cindex i j)
(= (u pos) (create-cell i j)))))
A couple of things to note: first, that Arc is 0-indexed. Some looks at your code reveal for-loops that start at 1. I don't know if they're doing anything "wrong" at this point, but in case you didn't know
(xs 0) ; == the *first* element of xs
(xs 1) ; == the second element of xs
; etc.
Also, it's desirable to generally (but not always) avoid naming variables the same thing as built-in functions & macros. Arc defines pos to find the position of an item in a sequence:
arc> (pos #\a "cbabc")
2
By rebinding pos, you clobber this definition (for more info, you can Google "Lisp-1 vs Lisp-2"). Here, it doesn't hurt though, except perhaps for readability.
In the REPL again,
arc> (load "game-of-life.arc")
Error: "random: expects type <pseudo-random-generator> as 2nd argument, given: 30; other arguments were: 1"
Well, this is a weird error! If you aren't sure whether there's a random function in Arc, you can check:
arc> (sig 'random)
nil
arc> random
Error: "reference to undefined identifier: _random"
So, Arc doesn't have a function named "random". Its random-number function is rand. The error says something about a "2nd argument", so let's try:
arc> (rand 1 50)
Error: "random: expects type <pseudo-random-generator> as 2nd argument, given: 50; other arguments were: 1"
Aha. rand doesn't like taking a 2nd argument. What's happening is that Arc's rand gets compiled down to Scheme's random. In your code, there's
(let cpos (rand 1 (len u))
Ouch. Maybe 0-indexing would help here. I make a comment of this potential issue, and sweep it under the rug by just:
(let cpos (rand (len u)) ; XXX should be 0-indexed?
In the REPL again,
arc> (load "game-of-life.arc")
Error: "reference to undefined identifier: _state"
Seeing that state is used as a field of the cell template, I suspect the same a.b vs a!b issue, and find the lines
meaning that it's happening when rejuvenate is called and c is nil. Lacking a debugger, I litter the program with print-statements to see what's happening.
; what's being passed to rejuvenate?
(def rejuvenate (c) (prn "c: " c) (= c!state 1))
(def init-universe (u)
(prn (sort < (accum a ; make accumulator called a, sort & print its result
(for i 1 x*
(for j 1 y*
(let pos (cindex i j)
(a pos) ; accumulate pos into the resulting list
(= (u pos) (create-cell i j))))))))
(prn "(len u) = " (len u)) ; what's the maximum random number to generate?
(repeat 10 ; XXX not guaranteed to produce 10 live cells due to duplicates!
(let cpos (rand (len u))
(prn "cpos: " cpos) ; what index are we using?
(prn "u.cpos: " u.cpos) ; what is the value at that index?
(rejuvenate u.cpos))))
Running the program, I get the following in the output:
So, nil is indeed being passed to rejuvenate, since (as we can see in the list of results of cindex) u.17 doesn't exist. The root problem here is then cindex -- as can be seen, it generates many duplicate numbers.
I inspect cindex and its use for awhile, coming to the conclusion that you're trying to represent the 2D Conway's Game of Life board in a 1D data structure. That is, instead of being able to reference a position by two points (like in a Cartesian plane), you're trying to condense it into a single point.
I thought it'd be clearer to represent the board as a 2D structure by just nesting a list within a list. This is alright; it remains sorted, but access times are generally slower than hash-tables and a lot of the code relies on iterating over integers. For better or worse, I decided to start rewriting code (trying my best to preserve your original code) to use a nested table. In so doing, there were other parts to refactor.
I look to see if you use the 'index field. Doesn't seem to be in use, so I get rid of it.
You've established 1 as a sentinel value for "alive" and 0 for "dead". Being in Lisp, this is a great place to use one of its interesting data literals: the symbol. It gives us the cheap ability to have data values that are simply a blob of text: these work great for sentinel values. Instead of 0/1, I rewrite it to use 'dead and 'alive. To see this in action, in the REPL:
arc> (= tbl (table))
#hash()
arc> (= (tbl 'x) 'alive) ; the symbol 'x is the key and the symbol 'alive is the value
alive
arc> tbl!x ; == (tbl 'x)
alive
arc> tbl.x ; == (tbl x) == tries to use the value in variable x as a key
Error: "reference to undefined identifier: _x"
arc> (= some-variable 'x)
x
arc> tbl.some-variable ;== (tbl some-variable) == (tbl 'x)
alive
arc> tbl!some-variable ;== (tbl 'some-variable) which is not a key in the table yet
nil
To see if this can be further simplified, I go to create-cell, the main place it's used.
Here, the 'x and 'y fields are set. I wonder how they're used, so look through the rest of the code. Turns out it's only in findfellas. But we needn't use = to set values all over the place that we access only once. We can redefine findfellas to work on just some coordinates x and y. More on that later. For the time being, I simplify with
Note the changes in alive? and dead? from isa to is. isa is defined in Arc as:
(def isa (x y) (is (type x) y))
But we don't want to check the type of the cell, just whether the state field is equal to something. For this, we use is.
Setting this aside for a moment, I try to remove the need for cindex from init-universe. I notice its reliance on using = to update the u that's passed. But assignment is kind of shaky business. Sometimes variables won't update the way you might expect them to (cf. passing by copy versus reference):
arc> (= x 1)
1
arc> (def f (something) (= something 1000))
#<procedure: f>
arc> (f x)
1000 ; sets "something" to 1000 and returns it
arc> x
1 ; but x is unmodified
arc> (= hash-table (table))
#hash()
arc> (def f (some-hash) (= some-hash!key 1000))
*** redefining f
#<procedure: f>
arc> (f hash-table)
1000 ; sets the key in "some-hash" to 1000
arc> hash-table
#hash((key . 1000)) ; and destructively updates the hash-table we passed in!
So, my solution is to use init-universe to generate a whole new object, then just return that object. Here's where the 0-indexing and nested hash-tables come into play.
(def init-universe ()
(let universe (table)
(for i 0 (- x* 1)
(= universe.i (table))
(for j 0 (- y* 1)
(= universe.i.j (create-cell i j))))
(repeat 10 ; not guaranteed to produce 10 live cells due to duplicates!
(with (i (rand x*)
j (rand y*))
(rejuvenate universe.i.j)))
universe))
But here, I use rejuvenate, which is itself setting a variable's value. It seems okay, though, because it's just setting a key in a hash-table, which (as seen above) should work:
Since I've been avoiding it, I turn back to findfellas. Instead of setting a cell's values, it should now just take in the things it needs to generate said values. Altering slightly yields
All of these if statements are introducing duplicated logic (plus, there's an unbalanced parenthesis in the last one). And now that cindex isn't used, we just need the two coordinates. Abstracting a bit, I got
(def findfellas (x y)
(with (x1 (- x 1) x2 x x3 (+ x 1)
y1 (- y 1) y2 y y3 (+ y 1))
(rem not-in-universe
(list (list x1 y1) (list x1 y2) (list x1 y3)
(list x2 y1) (list x2 y3)
(list x3 y1) (list x3 y2) (list x3 y3)))))
This let me sit back and figure out that it means to not be a valid coordinate. The best I could come up with was
; note: 0-indexing
(def not-in-universe ((x y))
(or (< x 0)
(< y 0)
(>= x x*)
(>= y y*)))
This definition makes use of a "destructuring" parameter, as it's called. To see the difference, here's a REPL interaction:
arc> (def f (x y) (prn "x: " x " y: " y) nil)
#<procedure: f>
arc> (f 1 2) ; called on two separate values
x: 1 y: 2
nil
arc> (def g ((x y)) (prn "x: " x " y: " y) nil)
#<procedure:zz>
arc> (g (list 1 2)) ; called on ONE parameter, a list, which is matched
; (or "destructured") against (x y). So (x y) == (1 2)
; implies that x == 1 & y == 2
x: 1 y: 2
nil
Okay. Not so bad. Now with a different representation of the universe, dumpu should be changed. This part is fairly straightforward:
(def dumpu (u)
(for i 0 (- x* 1)
(for j 0 (- y* 1)
(let c u.i.j ; u.i.j == ((u i) j)
(pr (if (alive? c) 1 (dead? c) 0)
"\t")))
(prn))) ; after every row, print out a newline
Phew! That seems to be the bulk of it. So, I try out the code.
arc> (load "game-of-life.arc")
nil
Oops. I forgot to check the main game loop. It's currently
I've rewritten init-universe to be non-destructive, so that needs to be changed. I also remember your comment about infinite numbers, but notice that your loop is until. In Arc, this is a loop that iterates "until" the expression is true (true values in Arc being anything other than the empty list). e.g.,
arc> (= x 5)
5
arc> (until (is x 0) (-- x) (prn x))
4
3
2
1
0
nil
You either want to use a different loop or use a boolean to signal dooms-day. But using a boolean that's not updated won't help -- either it's an infinite loop, or it just won't run at all. So, I reckon the looping construct should change, and the dooms-day counter should be a number. It makes sense to use repeat. So far, that's
I see the extra set of parens around the truth-clause of the if statement. I assume (and it makes sense) that you want to do both actions if (doomed? u) is true. For this, Arc has either the do block
arc> (do (prn "hi") (prn "how") (prn "are") (prn "you?"))
hi
how
are
you?
"you?"
and the when statement, which is like (if test (do ...))
arc> (when (> 10 5) (prn "I get executed") (prn "So do I.") (+ 1 2))
I get executed
So do I.
3
But then, calling (gof) again if we're doomed simply repeats the game until you stop it by force. I don't want to have to do that while testing, so I use one of Arc's more "advanced" constructs, point. If you don't know about continuations, basically what point does is give you a return statement (like in other languages), except you can name it whatever you want.
arc> (point return
(while t
(prn "in an infinite loop!")
(return 5)))
in an infinite loop!
5
arc> (point rabbit
(while t
(prn "wait, is this an infinite loop?")
(rabbit)))
wait, is this an infinite loop?
nil
So, in all, I've rewritten gof as
(def gof ()
(let u (init-universe)
(point return
(repeat doomsday*
(dumpu u)
(repeat 80 (pr "-")) ; print a line to help read between each gen
(prn)
(when (doomed? u)
(prn "we will start over")
(return))
(nextgen u)))))
Now all that's left is to rewrite doomed? and nextgen. The former is easy enough using the techniques applied thus far:
(def doomed? (u)
(point return
(for i 0 (- x* 1)
(for j 0 (- y* 1)
(if (alive? u.i.j)
(return nil)))) ; someone's alive, we're not doomed
t)) ; if we didn't find anyone who's alive, we're doomed!
nextgen is trickier. Even cleaning up the minor errors in your main conditional, it has overlapping logic:
(let goodfellas (len (alive-neighbours c u))
(if (alive? c)
; any live cell with fewer than two live neighbours dies
; any live cell with more than three live neighbours dies
; otherwise, live cell lives
(if (or (< goodfellas 2) (> goodfellas 3))
(takelife c))
; any dead cell with exactly three live neighbours becomes live
(if (is goodfellas 3)
(rejuvenate c))))
And once more I need to iterate with a nested for-loop across the universe. This is where I get sick and write a macro:
(Lightly tested, etc.) I'll leave it to you to figure out how it works. ;)
So
(def nextgen (u)
(each-cell c u
(let goodfellas (len (alive-neighbours c u))
(if (alive? c)
(if (or (< goodfellas 2) (> goodfellas 3))
(takelife c))
(if (is goodfellas 3)
(rejuvenate c))))))
This is a little bit freaky because of the assignment to a variable I've passed into the function. But, it (should be) setting to an index of a hash-table, so once more it looks fine.
I also clean up some other code using each-cell. But I can't use it for all cases, so there's probably a better macro to be written. Instead, I live with it; whatever.
In rewriting nextgen, I notice I need to rewrite alive-neighbours. (I've already taken the liberty of adding a hyphen to make the name easier to read.) This is pretty straightforward, again using the techniques described thus far:
I think that's it. I cleaned up the code as much as I'm going to (getting rid of the global universe, etc.), then tried it out on a 4x4 board for 3 generations:
I'm not sure if it's entirely correct, but it looks pretty good.
Sorry if any part of this seems condescending; I have literally no idea what your experience level is with programming or Arc. I just thought a write-up like this could help if someone wanted to see the (well, my) thought process behind tinkering with Arc code. Also, I've spent way too long writing this, so there are bound to be many typos. I'm not checking too intently because it's so long and I'm not going to make it perfect.
Note that this isn't the "best" or "right" way to write this code; merely the crack I took at it. Programming is an art.
Be that as it may, for reference I've posted the final version of my efforts at http://paste2.org/p/366945.
Thank you for writing such a long text. I sure could have avoided most of the syntax errors if had run it at least for once, but it serves me right by not doing so. This is my first arc program, but I think if I get such valuable comments, soon I will be writing good, idiomatic Arc code.
Have you actually run this code? It seems to have a lot of bugs. Also, this is just a style issue, but you seem to be indenting 8 spaces. Lisp convention is to put indents at 2 spaces, because lisp code tends to nest much more than code in C-like languages.
This is unnecessarily complex in two ways, and inefficient in a third. First, [alive? _] is just alive? itself. Second, the length of a list is zero if and only if that list is nil, and nil is itself a false value, so testing (is (len x) 0) when x is a list can be replaced with just (no x). Hence a simpler version would be:
(def doomed (u) (no (keep alive? u)))
; with ssyntax we can simplify this even further:
(def doomed (u) (~keep alive? u))
However, as mentioned by pg, this is still not the most efficient version of the function. If there are several alive cells in u, then (keep alive? u) will find all of them before terminating, when really we want it to exit with failure upon the first live cell it finds in u. Hence any one of (~mem alive? u), (~some alive? u) or (~find alive? u) will be more efficient (it doesn't really matter which you choose in this case).
As far as I can tell, your 'cindex function seems to be meant to take two integers and return a unique index. However, (cindex a b) == b + b*(a-1) == b + ba - b = ab. This obviously collides, for example, with (cindex b a).
You seem to use infix dot for accessing the fields of a cell a lot. This won't work; or example "c.fellas" will expand to "(c fellas)", which will depend on the value that fellas happens to be bound to (if any). What you probably want is "c!fellas", which expands to (c 'fellas).
(def aliveneighbours c (map [isalive _] c.neighbours))
; did you mean this?
(def aliveneighbours (c) (keep alive? c!neighbours))
> (= doomsday* 1) ; how to represent infinity? 1 will do,
> till Arc gets support.
Arc supports infinity as well as anything that uses ieee floating point. Mzscheme can directly read it with something like:
(= doomsday* +inf.0)
Alternatively, you can divide by 0, if you're sure that the division will happen in float-mode -- division-by-zero is well-defined in ieee floating arithmetic.
