Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Lisp Interpreter Implemented in Conway's Game of Life

github.com

Post reply on HN
Print view View original

61–70 of 88 posts

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#61

Post by eggy »

nisa wrote: post #11

Not so exciting but still pretty cool: Conways Game of Life in a few lines of otus lisp* https://github.com/yuriy-chumak/ol/blob/master/samples/Conve... * otus lisp is a descendant of owl lisp ( https://www.youtube.com/watch?v=utOVF0U7Zd8 ) with a nice ffi - http://yuriy-chumak.github.io/ol/

Wow, thanks for those links. I am well acquainted with Lisp, but I never stumbled upon these. The video was great too.

I have played with Wasp Lisp which is very cool and the Wasp VM. And checkout how it can spawn drone nodes on different machines[1,2]. I think C and Lisp together are amazing. I have been using them for decades, but J and APL entered my life over 8 years ago, and I am hooked! Checkout a rework of the famous APL GoL demo. It's much easier to understand than the original[3]

[1] https://github.com/swdunlop/WaspVM

[2] https://bluishcoder.co.nz/2015/02/19/spawning-windows-comman...

[3] https://www.youtube.com/watch?v=pMslgySQ8nc

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#62

Post by nigwil_ »

davesque wrote: post #50

This makes me wonder. If cells were occasionally activated in random positions, what sorts of modifications to the architecture would be necessary to make the system robust and still able to carry out its computations with a reasonable probability of success? Would that even be possible? In other words, what kinds of modifications to this system would make it more like a natural biological system that has to cope wit…

Dave Ackley explores this aspect here: https://www.youtube.com/watch?v=oXiqMGhn9rk

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#63

Post by spicybright »

galaxyLogic wrote: post #38
Aperocky wrote: post #20

Shameless plug: Have some fun over possible setups of cellular-automata (which conway's game of life is a subset of): http://aperocky.com/cellular-automata/

What is special about Game Of Life? Why does it seem to be the most "interesting" cellular automaton?

I think it's just inertia.

It's the most popular and well researched one at this point.

There's definitely tons of other less researched rules that are as interesting.

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#64

Post by djtriptych »

smoldesu wrote: post #42
idiotsecant wrote: post #35

Earlier quoted context omitted.

This reminds me a lot of the aging rockstar who hates the billboard top 10 hit that he always gets asked to play.

If you're Thom Yorke, you use that hatred to drive you to build your magnum opus. Though admittedly, I don't know how one could iterate on Game of Life. It's simplicity is part of what makes it so great.

Well kinda. The Bends was next after Pablo Honey, which contained "Creep", the song Radiohead famously learned to hate.

The "magnum opus" is typically said to be OK Computer, their 3rd album, 2 after Pablo. While it was certainly a departure, the band generally said they wanted a total artistic change in direction.

Interesting though is the song "Iron Lung" on The Bends, which is a song about "Creep" where they refer to it as, among other things, a "total waste of time".

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#65

Post by ColinWright »

galaxyLogic wrote: post #38
Aperocky wrote: post #20

Shameless plug: Have some fun over possible setups of cellular-automata (which conway's game of life is a subset of): http://aperocky.com/cellular-automata/

What is special about Game Of Life? Why does it seem to be the most "interesting" cellular automaton?

It's simple, small, clean, and Turing Complete. Most others show "interesting behaviour" (for some definition thereof) but are not Turing Complete (though some are).

I've not found a CA that's Turing Complete and as small and easy to understand (which is not to say there isn't one).

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#66

Post by galaxyLogic »

eesmith wrote: post #47
galaxyLogic wrote: post #39

Is there any hardware designed to just run cellular automata? I wonder if it could actually be a very efficient form of calculation, because cells are almost bits, but seem to possess more power than bits. For instance this Lisp in GoL. Could it run faster than lisps on "bit processors" if it ran on special purpose hardware? So instead of 64-bit processors we might have "64-cell processors" ?

GoL implementations for big systems don't evaluate the cellular automata step-by-step. They implement HashLife - https://en.wikipedia.org/wiki/Hashlife . The first example on that page shows position 6.3+ octillion for a Turing machine, computed in under 30 seconds. If the special purpose hardware ran at 1 THz, it would take about 4 quadrillion seconds to get to the same point, which is a bit over 200 million years.

Special-purpose hardware for cellular automata would not evaluate it "step-by-step" either, but in parallel. Every cell could evaluate its next state independently of others.

We could think of some kind of version of RAM where each 'cell' would implement this behavior.

Perhaps similar optimizations like HashLife could be developed for such special purpose hardware as well.

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#67

Post by roflc0ptic »

WJW wrote: post #57
davesque wrote: post #49

Earlier quoted context omitted.

Fascinating. Thanks so much for this! Natural biology really is miraculous (to use a loaded term).

Biology uses only global variables. All processes can write to all others. We wouldn't do this in software because the human mind can't handle it (leading to bugs), but evolution has no such constraint.

As a metaphor that really doesn’t work. Biology is incredibly hype about modularization and separation of concerns. The human body rather goes out of its way to prevent arbitrary changes, both exogenous and endogenous

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#68

Post by rezmason »

galaxyLogic wrote: post #66
eesmith wrote: post #47

Earlier quoted context omitted.

GoL implementations for big systems don't evaluate the cellular automata step-by-step. They implement HashLife - https://en.wikipedia.org/wiki/Hashlife . The first example on that page shows position 6.3+ octillion for a Turing machine, computed in under 30 seconds. If the special purpose hardware ran at 1 THz, it would take about 4 quadrillion seconds to get to the same point, which is a bit over 200 million years.

Special-purpose hardware for cellular automata would not evaluate it "step-by-step" either, but in parallel. Every cell could evaluate its next state independently of others. We could think of some kind of version of RAM where each 'cell' would implement this behavior. Perhaps similar optimizations like HashLife could be developed for such special purpose hardware as well.

I implemented Hashlife for a different CA rule set earlier this year.

Hashlife's data structure is a quad tree embedded in a hash table. Most Hashlife instances only spend a few short moments simulating cellular automata at the "ground level"— the real work involves combining the future of the children of a quad tree node into the future of the node. That might be optimizable, but it feels extremely application-specific.

Edit: shameless, shameless plug: https://rezmason.github.io/wireworld-player/?engine=macrocel...

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#69

Post by kevin_thibedeau »

AprilArcus wrote: post #48
davesque wrote: post #37

One interesting thing about this is that it serves as a kind of simplified demonstration of the kind of computation that must be occurring or could occur with actual cellular biology. DNA really seems somewhat like a tape in a Turing machine (although technically a read-only one). But the entire system does compute a result which is an organism.

You might be interested to learn that DNA is not actually read-only. Besides viruses like HIV and transposable elements which permanently splice themselves in to the host's DNA, antibodies gain specificity through irreversible self-editing of the lymphocyte's genome via a similar (and perhaps, evolutionarily related) mechanism. https://en.wikipedia.org/wiki/V(D)J_recombination

There's also epigenetics controlling gene activation, some of which is inheritable based on a parent's environmental exposures.

Re: A Lisp Interpreter Implemented in Conway's Game of Life

#70

Post by OscarCunningham »

davesque wrote: post #50

This makes me wonder. If cells were occasionally activated in random positions, what sorts of modifications to the architecture would be necessary to make the system robust and still able to carry out its computations with a reasonable probability of success? Would that even be possible? In other words, what kinds of modifications to this system would make it more like a natural biological system that has to cope wit…

I wrote about the state of the art for this here: https://www.lesswrong.com/posts/mL8KdftNGBScmBcBg/optimizati...
Post reply on HN