There are striking similarities between my current project Core Society and Grove Script which was the first domain specific programming language I’ve ever written. It was a really fun project on two levels: It’s fun to come up with a domain specific language of your own and then write a parser for it and an interpreter, where, for a change, optimization for speed is actually justified. But once you have established that new interface to talk to your computer the *real* fun can begin: To figure out how to use that new language and see what you can do with it. When you already know a systems inner workings and can change it on a whim if something doesn’t please you the learning experience isn’t even painful. Core Society is like this. It’s about programming cellular automata.
Cellular Automata are a well known concept in computer science. Typically you have a regular grid of cells, each in one of a finite number of states. Based on a set of rules you can look at a cell and it’s neighbours and decide on the cell’s next state. Now you just apply these rules repeatedly to all cells in the grid. It’s amazing to think about the complexity that can emerge from even simple setups. Take Conway’s Game of Life for example where each cell has only two possible states (on/off) and where only four simple rules define a cells next state based on itself and the local neighbours. And despite that it’s not only capable of generating complex evolving patterns, you can even build a Universal Turing Machine with it!
Conway’s Game of Life is a simple rule based system, quite in contrast to God’s Game of Life
But why simple rules and simple cell states? When I hear the word ‘Cell’ I think of the building blocks of all known living organisms, capable of self-replication and functionally quite complex. I wanted to step away from simple, rule based systems and towards the complexity of living cells. Why not build a cellular automaton where each cell is a fully programmable little computer? No external rules would decide how a cell’s state would change – only the initial programming of the cores would determine the course of the simulation.
I’ve never written an emulator before but that was exactly what I needed to do next – just that I wasn’t emulating an already existing computer system but a system I had yet to define. A system specifically designed to serve as a programmable cell in a CA.
The architecture I’ve settled with acts like a von Neumann machine where instruction and data share the 256 16bit words of memory. That means the whole memory is mapped to an 8bit address space. Because I can’t use less than a word (16 bit) to encode an instruction I figured there are enough bits left to encode additional information along with the instruction – including the target address the operation is meant to operate on. All other computer systems I know don’t have instructions that operate directly on memory. Not only because they have a far larger amount of addressable memory but also because they are designed to run efficient on physical hardware and memory access is a bottleneck. Thus most CPU’s have a couple of registers to store binary data in. When you program for those CPU’s in assembler you typically spend a lot of instructions copying data between registers and memory and I was pretty excited about a chance to get away without it. Apart from that a lot of the basic instructions in CoreSociety’s assembly language will look familiar if you know other assembly languages. Here’s the full list.
After planning the instruction set from a semantic point of view I needed to figure out how to map the instruction and all relevant parameters to one or, if the instruction is more complex, two words of memory.
To be memory-efficient not all bits encode the same kind of information in every instruction. For example not all instructions have a second parameter. The INC instruction just increases the value at the given address, while the SET instruction replaces the value at a given address with a new value that also needs to be supplied. If an instruction expects a second parameter the next word following the instruction is assumed to encode this parameter.
Here’s how it works in detail: The highest four bit of an instruction word always encode the instruction group. If a group consists of complex operations that require two operands only 2 bits are available to identify the group member. The 3rd bit (Param Flag) will encode whether the following parameter word, that encodes the second operand, is interpreted as a numeric value or as a pointer to an address. So there are 16 distinct groups possible that can either consist of 4 complex or 8 simple instructions. More then enough for our needs.
The next bit is the Target Flag and it tells the processor how the lower 8bits of the instruction word, that always encode the first operand of the operation, are to be interpreted. When it’s set the operation’s target is not an address but a numeral value or an address reached by indirection. Indirection means the passed address is not used directly as the target but read to get another address which is then used as a target.
When a second parameter is required the word after the instruction can either be interpreted as a 16 bit numeric value or an address that can be either supplied direct or by (recursive) indirection.
To verify the architecture I’ve build a prototype IDE to write and run core programs in. Basically you write a listing of a custom assembly language which is immediately compiled into a core’s memory. The core’s memory is visualized as colored blocks and also written out in HEX numbers. You can step through the code and watch the operations change the memory. The assembly language is pretty simple. There’s a 3-letter mnemonic assigned to each instruction followed by one or two operands. You can use labels to assign names to specific memory addresses and use those names instead of the actual address. Comments are also supported.
This is the IDE where the cell-programms are written and tested. Click for an unscaled version!
It’s surprising what you can do with just 512 bytes. A program to calculate prime numbers that I wrote as an early test-case was only 17 words long, leaving more then enough room to store the primes. Another positive side-effect of such tiny memory is that you can visualize all the data with a couple hundred pixels. I found it pretty fascinating to watch the little cores work!
A core viewed in the IDE spending 255 energy on calculating primes. The last primes it finds is 19, then he runs out of energy.
The next step after implementing the virtual system that would represent a cell in the Cellular Automata was to put a bunch of them together in a grid so that they could start interacting.
This is the GRID the simulation takes place. Each tick the core with the highest unbound energy get’s to execute an instruction. Energy is distributed cyclical until the energy budget is spend!
With the basic set of instructions in place I needed to figure out the rules by which cores (e.g. the cells) would be able to interact with their neighbours and how the system would decide which core would get to execute an instruction next. The straight-forward solution would be to just let them execute one instruction one after another and to add some instructions to read and write the memory of neighbouring cores.
But I’ve settled with something more complex. I had this grand vision that Core Society might evolve into a platform for competitive programming games. Like an arena where you’d try to write the perfect program to beat a challenge or compete with other programs for grid space. So I added an energy mechanic that governs the execution and interaction of programs. Energy is a precious resource that each core accumulates over time. It is spend when a core executes instructions. A core can spend energy to shield itself, preventing adjacent cores from writing into it’s memory. It can also reserve an amount of energy that when released allows the core to execute a number of instructions uninterrupted. There is an instructions that allows you to transfer energy into a neighbouring core. And one to drain energy from it, respectively.
So with a few bytes a core can be programmed to copy it’s program to neighbouring cores. Once the program has spread over multiple cores those can work together to establish dominance of the grid against competing programs or fulfil whatever goals they were programmed to.
Last but not least – to facilitate the creation of scenarios – I added an instruction to raise and one to lower a global score. It serves as a metric to gauge efficiency of a solution to a scenario. Obviously the more excess energy you can spend on raising the score the better the final score will be. The initial board state could involve some cores that lower the score constantly so a high scoring solution would need to be very efficient in gaining control of these cores as fast as possible.
The green core is calculating primes, supported by the grey cores who provide it with energy! The blue cores try to prevent the red core from taking over the board by spending their energy to keep a shield up and supporting neighbours.
Give it a try!
If you’d like to see more than animated gifs I’d suggest you check out Core Society’s Github repository or download it’s content as a ZIP. It includes a precompiled executable, full source-code, documentation and a couple of scenarios including reference solutions.
- You might need to install the .Net Framework 4.5 redistributables if you don’t have them installed.
- Then just start the prebuild executable (CoreSociety.exe) or build it yourself with Visual Studio 2013. (Should run on Mono, too)
- Click on the top left icon to open a scenario. A click on the ‘Play’ Icon starts the simulation.
- You can click on a listing in the ‘Deck’ to open the IDE window that allows you to modify the listing. The changes will automatically apply to the initial state of all cores that show the listing’s color.
- To learn more about the instruction set and how to program a core have a look at the Documenation.
- If you’ve got questions and can’t find answers in the docs just comment below!