Hi everyone, it's my first time posting here.
I created Lisp in Life, a Lisp interpreter that runs on Conway's Game of Life.
The pattern is available at my GitHub repo: https://github.com/woodrush/lisp-in-life
The Lisp program is provided by editing certain cells in the pattern to represent the ASCII encoding of the program.
Therefore, the pattern can be programmed so that it runs your own Lisp program.
The standard output is written at the very end of the RAM module in binary ASCII format, which can easily be located and be directly examined in Golly.
In the GitHub repo, there are scripts for loading custom Lisp programs, and for viewing the output text.
The overall architecture is based on the Quest For Tetris project (https://codegolf.stackexchange.com/ques ... 673#142673).
This project uses an 8-state Life-like rule called VarLife as an intermediate layer, and encodes patterns created in VarLife to Conway's Game of Life (b3/s23) using OTCA Metapixels to create the Game of Life patterns.
Since the ROM and RAM sizes are both about 10 times larger than the original project, to let patterns to run in a reasonable amount of time, Lisp in Life involves lots of modifications over the original architecture. Some examples are: introducing a new lookup table architecture for the ROM, removing and adding new opcodes, extending the ROM and RAM address space, changing the ROM word size, etc.
The VarLife patterns can also be run in Golly. Short programs such as `(print (* 3 14))` runs in about 1 minute, and even more sophisticated programs such as object-oriented-like.lisp (https://github.com/woodrush/lisp-in-lif ... -like.lisp) can be run in about 20 minutes.
On the other hand, for the Game of Life version, due to the heavy use of OTCA Metapixels, `(print (* 3 14))` takes about 6 hours to evaluate. I'm currently running another short example (https://github.com/woodrush/lisp-in-lif ... ambda.lisp) but it is currently taking over 14 hours.
To make everything closed in the Game of Life space, I also included a script that can directly write Lisp programs into the metafied Conway's Game of Life pattern. This script directly edits the meta-states of the OTCA Metapixels in the Game of Life pattern to load the Lisp programs.
The Lisp interpreter is written in C, and is compiled using a modified version of the QFTASM backend of ELVM (the Esoteric Language Virtual Machine) (https://github.com/shinh/elvm).
The QFTASM backend in the original ELVM project was implemented by myself as well.
A large room for improvement and limitations is the running time, due to the heavy use of OTCA Metapixels.
If we could use a more simple and compact Game of Life-based architecture, I believe the running time could be significantly improved.
However, I believe that the technique of using ELVM to create simple assembly code and allowing access to C is powerful for letting Game of Life computers doing sophisticated tasks.
Lisp in Life - Lisp Interpreter in Conway's Game of Life
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
I wanted to ask two questions, one about the Game of Life, and another about how I could improve my post quality.
The first one is, I was wondering if there are other instances where a high-level programming language was interpreted inside a Conway's Game of Life pattern, or if this was the first one.
I saw the Universal computer page in LifeWiki, but although the entry mentions architectures, it does not mention their applications.
The best I know about a specific high-level programming language being targeted for GoL is Cogol used by the Quest for Tetris project (https://codegolf.stackexchange.com/ques ... 676#142676), but this is a compiled language that is used for generating assembly code which runs on the pattern, and the language itself is not meant to run on the pattern itself, so it does not fit what I am searching for.
I also found the post for the beta reader for the Conway's Game of Life Textbook (https://www.conwaylife.com/forums/viewt ... 02#p136002), and saw the index for the computation section, but it also seemed to be focused on the architecture as well.
So I was wondering if this task was covered in Conway's Game of Life in the past. Specifically, I was looking for an instance where a high-level language is accepted in its original form as a string of text to the pattern, which the pattern parses, evaluates, and returns a result for. I wanted some help from everyone to know whether if this was done in the past. Does anyone happen to know? I was also interested in how other methods could be used to cover this topic.
The second one is, I wanted some feedback on my post for improving my future post qualities.
I was wondering if I was too focused on an application of a specific pattern and not the pattern itself, which I currently suspect was probably out the of scope of this forum.
I do acknowledge the fact that the architecture I used for this project is mostly based on the Quest for Tetris (QFT) project.
The architecture changes that I made to make this project possible are: A new lookup table architecture for the ROM for saving the pattern size, new opcode sets, and extended ROM and RAM address spaces.
Although I did lots of extensive optimization on the software side as well which made the ROM size significantly smaller, I was wondering if my project was too focused on the application of a Conway's Game of Life architecture and not the architecture itself. I'll be focusing on the architecture more if this is true. I also wanted to know if there were some other things that I overlooked on in this post.
I've always been fascinated by the vast world of Conway's Game of Life, and I wanted to be able to share better findings to the community.
The first one is, I was wondering if there are other instances where a high-level programming language was interpreted inside a Conway's Game of Life pattern, or if this was the first one.
I saw the Universal computer page in LifeWiki, but although the entry mentions architectures, it does not mention their applications.
The best I know about a specific high-level programming language being targeted for GoL is Cogol used by the Quest for Tetris project (https://codegolf.stackexchange.com/ques ... 676#142676), but this is a compiled language that is used for generating assembly code which runs on the pattern, and the language itself is not meant to run on the pattern itself, so it does not fit what I am searching for.
I also found the post for the beta reader for the Conway's Game of Life Textbook (https://www.conwaylife.com/forums/viewt ... 02#p136002), and saw the index for the computation section, but it also seemed to be focused on the architecture as well.
So I was wondering if this task was covered in Conway's Game of Life in the past. Specifically, I was looking for an instance where a high-level language is accepted in its original form as a string of text to the pattern, which the pattern parses, evaluates, and returns a result for. I wanted some help from everyone to know whether if this was done in the past. Does anyone happen to know? I was also interested in how other methods could be used to cover this topic.
The second one is, I wanted some feedback on my post for improving my future post qualities.
I was wondering if I was too focused on an application of a specific pattern and not the pattern itself, which I currently suspect was probably out the of scope of this forum.
I do acknowledge the fact that the architecture I used for this project is mostly based on the Quest for Tetris (QFT) project.
The architecture changes that I made to make this project possible are: A new lookup table architecture for the ROM for saving the pattern size, new opcode sets, and extended ROM and RAM address spaces.
Although I did lots of extensive optimization on the software side as well which made the ROM size significantly smaller, I was wondering if my project was too focused on the application of a Conway's Game of Life architecture and not the architecture itself. I'll be focusing on the architecture more if this is true. I also wanted to know if there were some other things that I overlooked on in this post.
I've always been fascinated by the vast world of Conway's Game of Life, and I wanted to be able to share better findings to the community.
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Welcome to the forum!
First let me say that this is a very impressive pattern! It's so cool to not just be able to run Lisp in Life, but even to type the code directly into the pattern rather than have it compiled.
The QFT project uses GoL logic circuits to build metacells, and then uses these metacells simulate a CA called VarLife in which logic circuitry is built. This adds a large amount of overhead to any pattern. A typical logic gate in VarLife has size around 5 by 5. The metapixels have size 2048 by 2048. So the typical gate in the QFT project has size around 10000 by 10000. Meanwhile if we use modern glider circuitry to build the gates directly in Life, each gate has size of about 100 by 50, or smaller. So we can fit roughly 20000 gates in the space that the QFT project needs to fit one.
Of course complaining in this way makes this community sound like sore losers, because the QFT project actually accomplished something we did not. You know what they say about premature optimization. But it's just so ridiculous that the final size of the pattern was 29 billion cells. It should be closer to one million.
I myself did think about the problem of writing a C to APGsembly compiler, so that high-level code could be run on Goucher's computer. But the problem I ran into was that the computer does not use RISC-V architecture (unlike QFT). So a lot of massaging would have to be done to get the memory and IO to work as expected.
There was also some work done on this forum to build a smaller metacell that could be used to make the QFT architecture more efficient. I believe chris_c ultimately accomplished this here. You might even be able to plug this cell directly into your code to make your pattern 4 times smaller and 8 times faster.
First let me say that this is a very impressive pattern! It's so cool to not just be able to run Lisp in Life, but even to type the code directly into the pattern rather than have it compiled.
It is the first one. The closest outside of the QFT project is the computer built by Adam Goucher, which runs an assembly language called APGsembly.I was wondering if there are other instances where a high-level programming language was interpreted inside a Conway's Game of Life pattern, or if this was the first one.
The slow reaction is not your fault. It's just that the QFT architecture is a bit unpopular in this community. Partially this is just not-invented-here syndrome. But also, the QFT project is just insanely inefficient.I wanted some feedback on my post for improving my future post qualities.
I was wondering if I was too focused on an application of a specific pattern and not the pattern itself, which I currently suspect was probably out the of scope of this forum.
I do acknowledge the fact that the architecture I used for this project is mostly based on the Quest for Tetris (QFT) project.
The QFT project uses GoL logic circuits to build metacells, and then uses these metacells simulate a CA called VarLife in which logic circuitry is built. This adds a large amount of overhead to any pattern. A typical logic gate in VarLife has size around 5 by 5. The metapixels have size 2048 by 2048. So the typical gate in the QFT project has size around 10000 by 10000. Meanwhile if we use modern glider circuitry to build the gates directly in Life, each gate has size of about 100 by 50, or smaller. So we can fit roughly 20000 gates in the space that the QFT project needs to fit one.
Of course complaining in this way makes this community sound like sore losers, because the QFT project actually accomplished something we did not. You know what they say about premature optimization. But it's just so ridiculous that the final size of the pattern was 29 billion cells. It should be closer to one million.
I myself did think about the problem of writing a C to APGsembly compiler, so that high-level code could be run on Goucher's computer. But the problem I ran into was that the computer does not use RISC-V architecture (unlike QFT). So a lot of massaging would have to be done to get the memory and IO to work as expected.
There was also some work done on this forum to build a smaller metacell that could be used to make the QFT architecture more efficient. I believe chris_c ultimately accomplished this here. You might even be able to plug this cell directly into your code to make your pattern 4 times smaller and 8 times faster.
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Maybe "unpopular" isn't quite the right word, speaking for myself at least. I meant to post something on this thread a lot sooner, but all I had to say immediately was just, "Wow!", more or less. So I hoped someone else would have something more interesting to say.Macbi wrote: January 8th, 2022, 7:01 pm The slow reaction is not your fault. It's just that the QFT architecture is a bit unpopular in this community.
It's certainly true that QFT architecture leaves a lot of people on the forums kind of scratching their heads, though. The reaction is something like, "look at all that impressive work -- but why on earth are they using those metacells?" It would be an awful lot simpler -- from a Conway's Life perspective, not a VarLife perspective -- to build an equivalent circuit that moves the necessary information from point A to point B.
For many of those VarLife-simulating metacells, I think the equivalent would just be something like a single period 2^N gun plus maybe a few Snarks and a beehive stopper or block keeper or two. The metacells are often looking for possible inputs in all kinds of places where no input could possibly come from, and so the whole structure ends up way more complicated than it needs to be.
There's only a small difficulty with that metacell design, which is that part of each metacell overlaps into a neighboring metacell, as described here. A little higher up the thread was as far as I had gotten building a pure-stable version of the reduced metacell.Macbi wrote: January 8th, 2022, 7:01 pmThere was also some work done on this forum to build a smaller metacell that could be used to make the QFT architecture more efficient. I believe chris_c ultimately accomplished this here. You might even be able to plug this cell directly into your code to make your pattern 4 times smaller and 8 times faster.
At this point I'd start over again from the base engine here, and probably double the diameter of the metacell to allow space for a reasonable-sized metapixel area -- big enough to see from a distance, so to speak, even if it doesn't take up the majority of the metacell's area.
The size of the OTCA metapixel isn't the issue, as far as HashLife not being able to run things very well -- it's just the fact that the period isn't a power of two. Just switching to any power-of-two metacell, even a 2048x2048 one, would probably let Golly run much more complex Lisp programs without grinding to a halt.
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Thanks Macbi and dvgrn for your feedback! I was curious about how the task of processing languages were discussed in GoL so I was happy to know about it.
I think the heavy use of OTCA Metapixels when metafying the QFT architecture is a large drawback too. It was the main problem that required me to do lots of optimizations to make the pattern size smaller for a feasible runtime at least for small programs. It currently takes about 6 hours to evaluate a simple multiplication + print program, and about 23 hours for a three-line program that defines and runs a function. Since these programs only take about 1 and 3 minutes each to run on VarLife, I believe if we are able to construct a 2-power metacell, it probably should speed up the generation significantly, perhaps comparable to that of VarLife's generation speed.
Another way for optimization is to use another architecture as well. When I was first choosing the architecture, I first looked at Coban's 8-bit programmable computer (https://www.conwaylife.com/forums/viewtopic.php?t=2561). The reason why I couldn't take that course was not an issue for the architecture, but it was because I couldn't figure out how to do that at that time, since I wasn't able to analyze the pattern enough.
The current Lisp interpreter uses 3300 instructions for the ROM and 1024x2 bytes for the RAM. Looking at my final result, I think 8 bits is enough for the RAM's byte size to host the Lisp interpreter or any other C program, so if we could extend the ROM and RAM address size, I think we can run Lisp on Coban's architecture. However, depending on how the jump instructions are processed, it may be a requirement to extend the RAM word size to 12 bytes to fit the ROM addresses as well.
According to the wiki for the 8-bit_programmable_computer,
I haven't been able to analyze Coban's architecture fully, but do you think it's possible to extend the address size this way?
I think the heavy use of OTCA Metapixels when metafying the QFT architecture is a large drawback too. It was the main problem that required me to do lots of optimizations to make the pattern size smaller for a feasible runtime at least for small programs. It currently takes about 6 hours to evaluate a simple multiplication + print program, and about 23 hours for a three-line program that defines and runs a function. Since these programs only take about 1 and 3 minutes each to run on VarLife, I believe if we are able to construct a 2-power metacell, it probably should speed up the generation significantly, perhaps comparable to that of VarLife's generation speed.
Another way for optimization is to use another architecture as well. When I was first choosing the architecture, I first looked at Coban's 8-bit programmable computer (https://www.conwaylife.com/forums/viewtopic.php?t=2561). The reason why I couldn't take that course was not an issue for the architecture, but it was because I couldn't figure out how to do that at that time, since I wasn't able to analyze the pattern enough.
The current Lisp interpreter uses 3300 instructions for the ROM and 1024x2 bytes for the RAM. Looking at my final result, I think 8 bits is enough for the RAM's byte size to host the Lisp interpreter or any other C program, so if we could extend the ROM and RAM address size, I think we can run Lisp on Coban's architecture. However, depending on how the jump instructions are processed, it may be a requirement to extend the RAM word size to 12 bytes to fit the ROM addresses as well.
According to the wiki for the 8-bit_programmable_computer,
These instructions should be enough to host a wide variety of programs as well. Since the architecture has a very sophisticated set of instructions, I think the program size wouldn't change that much.The computer supports eight variables and 13 instructions -- write, goto, move, jumpif, print, add, or, and, xor, not, flat, sign, and increment.
I haven't been able to analyze Coban's architecture fully, but do you think it's possible to extend the address size this way?
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Hi, there is an updated version of my computer that can handle up to 256 lines of ROM and 128x32 bit RAM :
https://github.com/nicolasloizeau/scalable-gol-computer
I advise using this one rather than the old 8 bit computer since it's also a bit smaller for the same size.
It can be programmed using this script : https://github.com/nicolasloizeau/scala ... ssembly.py so I guess it is feasible to write a lisp compiler to this instruction set.
https://github.com/nicolasloizeau/scalable-gol-computer
I advise using this one rather than the old 8 bit computer since it's also a bit smaller for the same size.
It can be programmed using this script : https://github.com/nicolasloizeau/scala ... ssembly.py so I guess it is feasible to write a lisp compiler to this instruction set.
Nicolas
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Thanks! I tried running the pattern in your repo. The pixel display looks awesome!
I looked at the instruction set in your computer and it seems to cover everything included in the current Lisp assembly, so it seems to be possible to fit the Lisp interpreter assembly to a size similar to the current one.
The current instruction size for the Lisp interpreter is around 3300, and the RAM usage is 1024x16 bits now. So if the architecture's ROM size could be expanded to 4096 and the RAM size to be that size, we could write a Lisp interpreter for the architecture.
I already have an idea of how to write a compiler for compiling the C code to the architecture's assembly code, so I consider that's already covered.
Also, do you think it's possible to integrate the text displayer in Adam P. Goucher's pi calculator into your architecture? The pixels to be written could probably be referenced from certain regions of the RAM.
I looked at the instruction set in your computer and it seems to cover everything included in the current Lisp assembly, so it seems to be possible to fit the Lisp interpreter assembly to a size similar to the current one.
The current instruction size for the Lisp interpreter is around 3300, and the RAM usage is 1024x16 bits now. So if the architecture's ROM size could be expanded to 4096 and the RAM size to be that size, we could write a Lisp interpreter for the architecture.
I already have an idea of how to write a compiler for compiling the C code to the architecture's assembly code, so I consider that's already covered.
Also, do you think it's possible to integrate the text displayer in Adam P. Goucher's pi calculator into your architecture? The pixels to be written could probably be referenced from certain regions of the RAM.
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Sorry I don't really get why developing a list interpreter ? Why not a compiler ?
That would already be super cool !woodrush wrote: January 27th, 2022, 12:09 pm I already have an idea of how to write a compiler for compiling the C code to the architecture's assembly code, so I consider that's already covered.
Nicolas
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Thanks!
The main purpose that I find interesting in running an interpreter on GoL instead of compiling the code beforehand, is that we can allow Conway's Game of Life patterns to be programmed using a high-level language like Lisp, using text as the interface. The current Lisp in Life pattern takes raw ASCII text (expressed in binary ASCII encoding) and runs it as a Lisp program.Coban wrote: January 27th, 2022, 8:43 pm Sorry I don't really get why developing a list interpreter ? Why not a compiler ?
I consider that this follows the purpose of constructing a universal computer in GoL. Before universal computers were constructed in GoL, we only had raw logic gates, which were Turing complete, but were hard to work with. I consider that universal computers in GoL such as yours take a step further so that GoL could be programmed with a more natural interface, using an assembly language. Running a Lisp interpreter takes this idea further where we allow interaction with Conway's Game of Life patterns with an even more natural interface for humans, using Lisp code expressed in ASCII. Therefore, I consider that running interpreters in GoL is a project where the objective is set from an engineering perspective.
Another purpose is to demonstrate that it's possible to run a large, complex program, written in C, in Conway's Game of Life.
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Wow -- it looks like the Lisp in Life project was actually completed, and very thoroughly documented, but (unless I'm just missing seeing the link somehow) the blog post was never advertised here. The blog post is definitely worth a look! Some of the same content is available in the Git repo README, but there are sections at the bottom that are different.woodrush wrote: January 28th, 2022, 2:52 amThe main purpose that I find interesting in running an interpreter on GoL instead of compiling the code beforehand, is that we can allow Conway's Game of Life patterns to be programmed using a high-level language like Lisp, using text as the interface. The current Lisp in Life pattern takes raw ASCII text (expressed in binary ASCII encoding) and runs it as a Lisp program.
Anybody interested in supplying HashLife-friendly drop-in replacements for the different VarLife cells?
I don't seem to be getting around to finishing a self-contained HashLife-friendly metacell, but as they say there's a first time for everything that there's a first time for. Maybe it will show up this year... especially if someone else builds it.
Chris Cain's HashLife-friendly metacell would need a redesign to become self-contained, and would probably need to be resized to add a metapixel region, for cell state readout purposes at far-out zoom levels.
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Sorry, I don't have time to follow all the discussions here and missed your post until now. I find your achievement extremely impressive!
Your Lisp dialect even has CL-style macros! I see where your macro system comes from. I am also a fan of Hy. Gonna code something now.
Making a much larger version (>=16k) with alphanumeric output and a script-driven REPL could be a next step!
Your Lisp dialect even has CL-style macros! I see where your macro system comes from. I am also a fan of Hy. Gonna code something now.
Making a much larger version (>=16k) with alphanumeric output and a script-driven REPL could be a next step!
Re: Lisp in Life - Lisp Interpreter in Conway's Game of Life
Thanks dvgrn and Yoel for your comments! Also thanks for nominating Lisp in Life as the Pattern of the Year 2022 patterns, and to the people who have voted for the pattern. I'm very happy to hear that many of you have found my work interesting!
One thing to watch out after building the metacell may be how to build the metafier. Since the pattern is very large, using a cell-by-cell run-length encoding for the metafication process is too costly. Instead I modified an existing script that directly constructs the Macrocell format, based on reuse of predefined patterns. I tweaked the existing code a bit for compatibility with large patterns. This script is also available in the repo.
It would be very cool if we could integrate GoL-native displays such as the one from the Pi calculator. Since we are using metacells, we would need a layer that converts from metacell signals to GoL signals. Building a serial communication circuit between these layers may work. We would probably need a new phase in the CPU cycle for drawing the screen as well.
The script-based REPL is also a very nice idea. Here's one way to do it: we could watch for a certain cell in the RAM to become active to await user input, probably with an infinite loop like `while(flag)` in the C layer, and the REPL UI (probably a Python or Lua plugin for Golly) will toggle the RAM cell so that `flag` becomes false, breaking the loop. This way we can work around the fact that the number of generations required per cycle is practically random (it depends on too many factors, such as the instruction/target memory's ROM/RAM address).
I appreciate your compliment! As for the metacells I'd be very interested if this is possible. The VarLife *.mc patterns are also available in my repo, so if anybody makes one you can use them for the metafication process.dvgrn wrote: January 7th, 2023, 9:59 am [...] The blog post is definitely worth a look! Some of the same content is available in the Git repo README, but there are sections at the bottom that are different.
Anybody interested in supplying HashLife-friendly drop-in replacements for the different VarLife cells?
[...]
One thing to watch out after building the metacell may be how to build the metafier. Since the pattern is very large, using a cell-by-cell run-length encoding for the metafication process is too costly. Instead I modified an existing script that directly constructs the Macrocell format, based on reuse of predefined patterns. I tweaked the existing code a bit for compatibility with large patterns. This script is also available in the repo.
Many thanks for your compliment! As for the macros, yes, that's kind of where I got the idea from - I'm a fan of Hy too, I've contributed to Hy a little bit in the past. The idea of macros as "functions that build code" was also inspired from the book Let over Lambda.Yoel wrote: February 9th, 2023, 3:00 pm Sorry, I don't have time to follow all the discussions here and missed your post until now. I find your achievement extremely impressive!
Your Lisp dialect even has CL-style macros! I see where your macro system comes from. I am also a fan of Hy. Gonna code something now.
Making a much larger version (>=16k) with alphanumeric output and a script-driven REPL could be a next step!
It would be very cool if we could integrate GoL-native displays such as the one from the Pi calculator. Since we are using metacells, we would need a layer that converts from metacell signals to GoL signals. Building a serial communication circuit between these layers may work. We would probably need a new phase in the CPU cycle for drawing the screen as well.
The script-based REPL is also a very nice idea. Here's one way to do it: we could watch for a certain cell in the RAM to become active to await user input, probably with an infinite loop like `while(flag)` in the C layer, and the REPL UI (probably a Python or Lua plugin for Golly) will toggle the RAM cell so that `flag` becomes false, breaking the loop. This way we can work around the fact that the number of generations required per cycle is practically random (it depends on too many factors, such as the instruction/target memory's ROM/RAM address).