https://github.com/woodrush/lisp-in-life Skip to content Sign up * Why GitHub? + Features + Mobile + Actions + Codespaces + Packages + Security + Code review + Issues + Integrations + GitHub Sponsors + Customer stories * Team * Enterprise * Explore + Explore GitHub + Learn and contribute + Topics + Collections + Trending + Learning Lab + Open source guides + Connect with others + The ReadME Project + Events + Community forum + GitHub Education + GitHub Stars program * Marketplace * Pricing + Plans + Compare plans + Contact Sales + Education [ ] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this user All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up {{ message }} woodrush / lisp-in-life Public * Notifications * Fork 2 * Star 166 * A Lisp interpreter implemented in Conway's Game of Life woodrush.github.io/lisp-in-life/ View license 166 stars 2 forks Star Notifications * Code * Issues 0 * Pull requests 0 * Actions * Projects 0 * Wiki * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Wiki * Security * Insights main Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags 1 branch 0 tags Code Latest commit @woodrush woodrush Revise the documentation ... 512de61 Dec 23, 2021 Revise the documentation 512de61 Git stats * 295 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time QFT-devkit @ 8a2789c Update the QFT-devkit submodule Dec 20, 2021 elvm @ 70d2e00 Update the ELVM submodule Dec 17, 2021 img Remove former build flow image Dec 23, 2021 lisp Add lambda.lisp Dec 22, 2021 misc Update hello.c's standard input Dec 18, 2021 patterns Add lambda.lisp Dec 22, 2021 qftasm Clean up ./src Dec 17, 2021 src Add build system for the 512-word-RAM architecture Dec 21, 2021 tools Add lambda.lisp Dec 22, 2021 .gitignore Clean up the repository and change some filenames Dec 16, 2021 .gitmodules Add instructions for building from source, fix shellscripts, and add ... Dec 15, 2021 LICENSE Revise the readme and the build system Dec 12, 2021 Makefile Add build system for the 512-word-RAM architecture Dec 21, 2021 README.md Revise the documentation Dec 23, 2021 build.md Remove former build flow image Dec 23, 2021 details.md Revise the documentation Dec 23, 2021 View code [ ] Lisp in Conway's Game of Life Running Lisp and C on the Game of Life Screenshots How is it Done? Conversion from VarLife to Conway's Game of Life Pattern Files Descriptions of the Lisp Programs Details of the Lisp Interpreter Special Forms and Builtin Functions Lexical Closures Macros Running Times and Statistics Tests Building from Source Implementation Details README.md Lisp in Conway's Game of Life Lisp in Life is a Lisp interpreter implemented in Conway's Game of Life. The entire pattern is viewable on the browser here. Running Lisp and C on the Game of Life This repository contains a Conway's Game of Life pattern that runs a Lisp interpreter. The Lisp program is provided by editing certain cells within the pattern to represent the ASCII-encoding of the Lisp program. The interpreter writes its standard output to the bottom end of the RAM module, which can be directly examined in a Game of Life viewer. The Lisp implementation supports lexical closures and macros, allowing one to write Lisp programs in a Lisp-like taste, as far as the memory limit allows you to. The Lisp interpreter is written in C. Using the build system for this project, you can also compile your own C11-compatible C code and run in on Conway's Game of Life. Screenshots An overview of the entire architecture. An overview of the entire architecture. An overview of the CPU and its surrounding units. An overview of the CPU and its surrounding modules. On the top are the ROM modules, with the lookup module on the right, and the value modules on the left. On the bottom left is the CPU. On the bottom right is the RAM module. This pattern is the VarLife version of the architecture. VarLife is an 8-state cellular automaton defined in the Quest For Tetris (QFT) Project, which is used as an intermediate layer to create the final Conway's Game of Life pattern. The colors of the cells indicate the 8 distinct states of the VarLife rule. The Conway's Game of Life version of the architecture, converted from the VarLife pattern. The Conway's Game of Life version of the architecture, converted from the VarLife pattern. What appears to be a single cell in this image is actually an OTCA metapixel zoomed away to be shown 2048 times smaller. A close-up view of a part of the ROM module in the Conway's Game of Life version. A close-up view of a part of the ROM module in the Conway's Game of Life version. Each pixel in the previous image is actually this square-shaped structure shown in this image. These structures are OTCA metapixels, which can be seen to be in the On and Off meta-states in this image. The OTCA metapixel is a special Conway's Game of Life pattern that can emulate cellular automatons with customized rules. The original VarLife pattern is simulated this way so that it can run in Conway's Game of Life. A video of the RAM module of the computer in the VarLife rule in action. A video of the RAM module of the computer in the VarLife rule in action. The QFT computer showing the results of the computation of (print (* 3 14)). The computer showing the results of the following Lisp program: (define mult (lambda (m n) (* m n))) (print (mult 3 14)) The result is 42, shown in binary ascii format (0b110100, 0b110010), read in bottom-to-up order. As shown in this image, the standard output of the Lisp program gets written at the bottom end of the RAM module, and can be directly viewed in a Game of Life viewer. This repository also contains scripts that run on Golly to decode and view the contents of the output as strings. How is it Done? The build flow of Lisp in Life. The Lisp interpreter, written in C, is compiled to an assembly language for a CPU architecture implemented in the Game of Life, which is a modification of the computer used in the Quest For Tetris (QFT) project. The architecture is based on Tetris8.mc in the original QFT repository. The compilation is done using an extended version of ELVM (the Esoteric Language Virtual Machine). The Game of Life backend for ELVM was implemented by myself. Generating a short enough Lisp interpreter assembly code, a Game of Life architecture, and a working pattern that runs in a reasonable amount of time required a lot of effort. This required optimizations and improvements in every layer of the project, including the C compiler layer, the CPU architecture layer, including: * The C Compiler layer - adding the computed goto feature to the C compiler, preserving variable symbols to be used after compilation, etc. * The C layer (the Lisp interpreter) - using a string hashtable and binary search for Lisp symbol lookup, minimization of stack region usage with union memory structures, careful memory region map design, etc. * The QFTASM layer - writing a compiler optimizer to optimize the length of the assembly code * The VarLife layer (the CPU architecture) - creating a lookup table architecture for faster ROM access, expanding the size and length of the RAM module, adding new opcodes, etc. * The Game of Life layer - Hashlife-specific optimization A more detailed description of the optimizations done in this project is available in the Implementation Details section. Conversion from VarLife to Conway's Game of Life VarLife is an 8-state cellular automaton defined in the Quest For Tetris (QFT) Project. It is used as an intermediate layer to generate the final Conway's Game of Life pattern; the computer is first created in VarLife, and then converted to a Game of Life pattern. When converting VarLife to Conway's Game of Life, each VarLife cell is mapped to an OTCA Metapixel (OTCAMP). The conversion from VarLife to the Game of Life is done in a way so that the behavior of the states of the VarLife pattern matches exactly with the meta-states of the OTCA Metapixels in the converted Game of Life pattern. Therefore, it is enough to verify the behavior of the VarLife pattern to verify the behavior of the Game of Life pattern. Due to the use of OTCA Metapixels, each VarLife cell becomes extended to a 2048x2048 Game of Life cell, and 1 VarLife generation requires 35328 Game of Life generations. Therefore, the VarLife patterns run significantly faster than the Game of Life (GoL) version. Additional details on VarLife are available in the Miscellaneous section in details.md. Pattern Files Program VarLife Pattern Conway's Game of Life Pattern print.lisp QFT_print.mc QFT_print_metafied.mc lambda.lisp QFT_lambda.mc QFT_lambda_metafied.mc printquote.lisp QFT_printquote.mc QFT_printquote_metafied.mc factorial.lisp QFT_factorial.mc QFT_factorial_metafied.mc z-combinator.lisp QFT_z-combinator.mc QFT_z-combinator_metafied.mc backquote-splice.lisp QFT_backquote-splice.mc QFT_backquote-splice_metafied.mc backquote.lisp QFT_backquote.mc QFT_backquote_metafied.mc object-oriented-like.lisp QFT_object-oriented-like.mc QFT_object-oriented-like_metafied.mc primes-print.lisp QFT_primes-print.mc QFT_primes-print_metafied.mc primes.lisp QFT_primes.mc QFT_primes_metafied.mc Pattern files preloaded with various Lisp programs are available here. Detailed statistics such as the running time and the memory consumption are available in the Running Times and Statistics section. The patterns can be simulated on the Game of Life simulator Golly. The VarLife patterns can be simulated on Golly as well. To run the VarLife patterns, open Golly and see File -> Preferences -> Control, and Check the "Your Rules" directory. Open the directory, and copy ./ QFT-devkit/Varlife.rule to the directory. Descriptions of the Lisp Programs * object-oriented-like.lisp: This example creates a structure similar to classes in Object-Oriented Programming, using closures. + The class has methods and field variables, where each instance carries distinct and persistent memory locations of their own. The example instantiates two counters and concurrently modifies the value held by each instance. + New syntaxes for instantiation and method access, (new classname) and (. instance methodname), are introduced using macros and functions. The Lisp interpreter's variable scope and the macro feature is powerful enough to manage complex memory management, and even providing a new syntax to support the target paradigm. * printquote.lisp: A simple demonstration of macros. * factorial.lisp: A simple demonstration of recursion with the factorial function. * z-combinator.lisp: Demonstration of the Z Combinator to implement a factorial function using anonymous recursion. * backquote-splice.lisp: Implements the backquote macro used commonly in Lisp to construct macros. It also supports the unquote and unquote-splice operations, each written as ~ and ~@. * primes.lisp: Prints a list of prime numbers up to 20. This example highlights the use of the while syntax. The contents of print.lisp is quite straightforward - it calculates and prints the result of 3 * 14. backquote.lisp and primes-print.lisp are similar to backquote-splice.lisp and primes.lisp, mainly included for performance comparisons. backquote.lisp doesn't implement the unquote-splice operation, and demonstrates some more examples. primes-print.lisp reduces the number of list operations to save memory usage. Details of the Lisp Interpreter Special Forms and Builtin Functions * define * if * quote * car, cdr * cons * list * atom * print * progn * while * lambda, macro * eval * eq * +, -, *, /, mod, <, > Lexical Closures This Lisp interpreter supports lexical closures. The implementation of lexical closures is powerful enough to write an object-oriented-like code as shown in object-oriented-like.lisp, where classes are represented as lexical closures over the field variables and the class methods. Macros This Lisp interpreter supports macros. Lisp macros can be thought as a function that receives code and returns code. Following this design, macros are treated exacly the same as lambdas, except that it takes the arguments as raw S-expressions, and evaluates the result twice (the first time to build the expression, and the second time to actually evaluate the builded expression). Running Times and Statistics VarLife Patterns Lisp Program and Pattern #Halting Running Time Memory Usage (VarLife) Generations (VarLife) (VarLife) (VarLife) print.lisp [pattern] 105,413,068 1.159 mins 5.0 GiB (exact) lambda.lisp [pattern] 700,000,000 2.966 mins 12.5 GiB printquote.lisp [pattern] 800,000,000 3.424 mins 12.5 GiB factorial.lisp [pattern] 1,000,000,000 5.200 mins 17.9 GiB z-combinator.lisp [ 1,700,000,000 9.823 mins 23.4 GiB pattern] backquote-splice.lisp [ 4,100,000,000 20.467 mins 27.5 GiB pattern] (max.) backquote.lisp [pattern] 4,100,000,000 21.663 mins 27.5 GiB (max.) object-oriented-like.lisp 4,673,000,000 22.363 mins 27.5 GiB [pattern] (max.) primes-print.lisp [ 8,880,000,000 27.543 mins 27.5 GiB pattern] (max.) primes.lisp [pattern] 9,607,100,000 38.334 mins 27.5 GiB (max.) Conway's Game of Life (GoL) Patterns Lisp Program and Pattern #Halting Running Memory (GoL) Generations (GoL) Time (GoL) Usage (GoL) print.lisp [pattern] 3,724,032,866,304 382.415 27.5 GiB mins (max.) lambda.lisp [pattern] 24,729,600,000,000 1372.985 27.5 GiB mins (max.) printquote.lisp [pattern] 28,262,400,000,000 - - factorial.lisp [pattern] 35,328,000,000,000 - - z-combinator.lisp [ 60,057,600,000,000 - - pattern] backquote-splice.lisp [ 144,844,800,000,000 - - pattern] backquote.lisp [pattern] 144,844,800,000,000 - - object-oriented-like.lisp 165,087,744,000,000 - - [pattern] primes-print.lisp [ 313,712,640,000,000 - - pattern] primes.lisp [pattern] 339,399,628,800,000 - - Common Statistics Lisp Program #QFT CPU Cycles QFT RAM Usage (Words) print.lisp 4,425 92 lambda.lisp 13,814 227 printquote.lisp 18,730 271 factorial.lisp 28,623 371 z-combinator.lisp 58,883 544 backquote-splice.lisp 142,353 869 backquote.lisp 142,742 876 object-oriented-like.lisp 161,843 838 primes-print.lisp 281,883 527 primes.lisp 304,964 943 The running times for each program are shown above. The Hashlife algorithm used for the simulation requires a lot of memory in exchange of speedups. The simulations were run on a 32GB-RAM computer, with Golly's memory usage limit set to 28000 MB, and the default base step to 2 (configurable from the preferences). The memory usage was measured by Ubuntu's activity monitor. "(max.)" shows where the maximum permitted memory was used. The number of CPU cycles and the QFT memory usage was obtained by running the QFTASM interpreter on the host PC. The QFT memory usage shows the number of RAM addresses that were written at least once. The memory usage is measured in words, which is 16 bits in this architecture. All of the VarLife patterns can actually be run on a computer. The shortest running time is about 1 minute for print.lisp. A sophisticated program such as object-oriented-like.lisp can even run in about 22 minutes. On the other hand, the Game of Life patterns take significantly more time than the VarLife patterns, but for short programs it can be run in a moderately reasonable amount of time. For example, print.lisp finishes running in about 6 hours in the Game of Life pattern. As mentioned in the "Conversion from VarLife to Conway's Game of Life" section, since the Game of Life pattern emulates the behavior of the VarLife pattern using OTCA Metapixels, the behavior of the Game of Life patterns can be verified by running the VarLife patterns. Tests There are tests to check the behavior of the Lisp interpreter. There is a test for checking the QFTASM-compiled Lisp interpreter using the QFTASM interpreter, and a test for checking the GCC-compiled Lisp interpreter on the host pc. To run these tests, use the following commands: git submodule update --init --recursive # Required for building the source make test # Run the tests for the QFTASM-compiled Lisp interpreter, using the QFTASM interpreter make test_executable # Run the tests for the executable compiled by GCC Running make test requires Hy, a Clojure-like Lisp implemented in Python available via pip install hy. Some of the tests compare the output results of Hy and the output of the QFTASM Lisp interpreter. The tests were run on Ubuntu and Mac. Building from Source This section explains how to load the Lisp interpreter (written in C) to the Game of Life pattern, and also how to load a custom Lisp program into the pattern to run it on Game of Life. Please see build.md. Implementation Details This section describes the implementation details for the various optimizations for the QFT assembly and the resulting Game of Life pattern. Please see details.md. About A Lisp interpreter implemented in Conway's Game of Life woodrush.github.io/lisp-in-life/ Topics lisp game-of-life Resources Readme License View license Stars 166 stars Watchers 3 watching Forks 2 forks Releases No releases published Packages 0 No packages published Languages * C 37.0% * Python 34.4% * Shell 22.9% * NewLisp 3.7% * Makefile 1.8% * Common Lisp 0.2% * (c) 2021 GitHub, Inc. * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time. You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.