Below are some rough notes from a tutorial session called Soft alife with SPLAT and Ulam by David Ackley. These notes are very hastily taken and I am editing them between sessions mostly for my own benefit, so expect to see typos and maybe even mis-wordings.
Soft alife with SPLAT and Ulam
By David H Ackley. Emeritus associate professor of Computer Science at the University of New Mexico. Does research, development, and advocacy of robust-first and best-effort computing on indefinitely scalable computer architectures. https://www.cs.unm.edu/~ackley/
What are we doing here?
- the talk is intended for the restless programmer of traditional machines
- the host is a recovering restless programmer of deterministic machines
- the talk is a conceptual reboot for why we need to change our approach to computing going forward. We are currently in the stone age of computing.
We are talking about cellular automata, but not as we know it. The type of cellular automata Ackley is presenting is viciously asynchronous. It is not deterministic, and is prone to failure at all levels. But we need to write code that can do something useful with it. We are not talking about Conway’s Game Of Life here - it is anything but perfect and deterministic.
It is cellular automata that is aligned chaotic good.
The goal is to develop and deploy useful devices based on indefinitely scalable, best-effort computing.
This can be used for scientific, mathematical, formal purposes. And that is great, but that is not what the speaker is focusing on in this talk. Ackley is focusing on robustness and deployable systems rather than elegance.
If we agree to give up on deterministic execution, how do we write code? We need to get a big benefit in return to even consider something like this. What we will get is indefinite scalability. We can take this computing platform and grow it as long as we want until the cows come home. Until we run out of space, power, cooling, money to buy hardware [perosnal note: but is that not already the case? Is it mostly that we currently need to restart our programs to scale up in many cases?]
Where does alife come in?
But where is the artificial life in this concept? In order to survive on an indefinitely scalable computing group, software will need to be a form of artificial life. It needs to be able to reproduce itself either to take advantage of additional resources that open up, or for robustness, or both. Indefinite scalability implies artificial life.
Best Effort Computing: Movable Feast Machine and Ulam
If we give up on hardware determinism, this is what we will replace it with. Hardware will try to execute steps we give it in order, but if it fails to get the correct answer we do not get to blame the hardware. The hardware’s agreement with software is that it will only make its best effort. It reserves the right to fail and sometimes fail catastrophically. It is the software’s job to try to work with that - software has to become best effort as well.
The Movable Feast Machine (MFM) is idefinitely scalable. It has no internal limit. It is a series of tiles. It has no CPU. You have to only do things that are local, no long distance links or constant time. All local, all best effort.
Ulam is an object oriented procedural programming language for the MFM:
- Very limited persistent state
- Stack and best effort determinism during one event
- No pointers or general purpose RAM.
The CPU and RAM has the limit of flexibility. A pointer can point anywhere in RAM and switch to point anywhere else, so in effect there is no spatial structure in RAM. This makes it easy, but also makes it so that you can’t guarantee anything if something goes wrong. We see this in computer security - all you need to do is take a CPU and RAM model and knock it off its expectation once. Divert the flow of control once, and you can take over the machine. Why? CPU and RAM is too flexible, too general purpose. This makes it easy for programmers, but Ackley believes we now have enough knowledge to do better. We can build systems that are less flexible at the lower level while still providing the capabilities we need to build useful software.
T2 Tile Project
The T2 Tile Project attempts to create an indefinitely scalable computational stack. We will make a tiny tile of computing that will plug together with more and more of its own kind. No serial number, no absolute address. The tiles are identical grains of sand that we can pack together in a sheet. To show a proof of concept demo, pick some linux board, make some tile PCB for it, stick it on a cheap display.
The speaker shows several demos, comparing Java syntax to Ulam syntax.
- Each element in Ulam has an atomic symbol - by default the first two letters of the element name. Element Foo’s atomic symbol would be Fo unless overridden. Atoms (analog to objects) are instances of elements (classes)
- An atom has 71 bits of state. All atoms are the same size. We can swap with neighbors, but we are not swapping pointers - we are swappng the actual bits from one place to the other.
- State transition code is per element, not per atom.
void behave()is the entry point for a state transition.
behave()ing atom is stored in the event window at
- An Ulam program has no main - no real place to begin, and no exit - no default place to end. Living systems don’t want to end unless they want to sacrifice themselves for some greater good.
- The initial configuration is generally determined externally - don’t try to find or call a main method, it is impossible.
- Ulam code is about writing transition functions like any other cellular automata, except on steroids.
- Arithmetic in ulam does not overflow, it saturates. Eg let’s say we have an int of 3 bits. In Ulam, int(3) 2+2 != -4; 2+2=3. Overflow is like a programming error: you’re not supposed to do it in traditional programming, so the answer we get can be nonsensical as it is not intended to be used. With best effort model, if we don’t want to be right we want to be close - it matters. Saturation is almost always less wrong than overflowing. In this cases, one solution is to go from int(3) to int(4).
- In MFM, you can read and write the entire event window - you can write your entire neighborhood. The neighborhood/event window can be seen at http://robust.cs.unm.eu
- Synchronize only what you need
Q: Isn’t this inefficient? The program keeps restarting.
A: that is a principal source of its robustness
Q: How can you write anything serious with 71 bits of state?
A: View an atom less as a program and more as an ALU or mobile FPGA. Many atoms will coordinate to perform complex and stateful tasks.
Q: How can atoms coordinate without a synchronous architecture?
A: As demonstrated by the swapline element, atoms can synchronze as needed.
Q: It’s too hard. Where is my IDE? Where is my autocomplete?
A: Living on the frontier is not for everybody.
Ulam Programming Motifs
behave() method typically employes a four step process. Within a single call of
behave() you usually see four steps:
- rationalize: Power On Self Test; internal and external invariants. Wake up from being in a coma and see where you are. If you find a problem, fix it - either change something or fail. Failing is fine, but you will get erased
- sense: input analysis, categorization
- compute: reason, imagine, predict, move selection
- act: output. change the world, place bets
Then wait for another
behave() invocation, in another event.
Instead of shooting all over the place with arbitrary pointer jumps, we have a sequence of phases (above).
We want to take what had been arbitrary computation with any sequence and turn it into a repeated nesting pattern of phased steps.
The Ulam compiler generates C++ code from Ulam code. Small Ulam code geneates a huge amount of C++ code. But many of the things we needed to do in Ulam, like representing these spatial structures like the SwapLine, are inelegant. Couldn’t we make space be first class? CPU and RAM discarded space immediately, and we bring it back in (cellular automata is inherently spatialized), so shouldn’t the programming language be spacialized as well?
In SPLAT, you have two dimentional programs. A SPLAT program uses indentation and ASCII character positioning as a first class citizen.
Anatomy/phases of a SPLAT rule:
You can optionally escale to Ulam in any of these.
Q: how do you measure complexity of algorithms that run in a computation model with infinite scalability and non constant communication time?
A: In best effort computing, software will have data sheets. There could be different types of implementations - use less total area/total sites to get a job done, but maybe be less robust. Or one that spreads out where possible, but will agree to be small if there is no space available.
Q: What problems would you love to see solved in Ulam/SPLAT?
A: Kick ass demos. Traditional computing has had 80 years to bulk up its abilities. What we need now is incredibly expensive, tons of hardware, tons of software, tons of grad student time spent building the simplest robot. Like a Braitenberg vehicle, except implemented in a tile sheet with a robot. It is not that it knows how to turn left and right to find the light - the point is you can taser it, shoot it, punch a hole in it, and it can still find the light.
Q: What is the application domain? Do you see this architecture as supporting classic applications or is it more aimed at massively distributed apps?
A: It is intended for real time system control. This is where using classical computation is a disaster waiting to happen. Will you eventually use best effort architecute to run a spreadsheet? Sure, but it will be way at the end, not at the beginning. This is specifically aimed at real time system control.
Q: How many people are involved? what timeline do you see for this?
A: It is a small rebel alliance. Ackley himself retired from acamdemia a couple of years ago to focus on this full time. There are no funded grad students, just people on the internet doing stuff. It is the earliest days, there are maybe a dozen active folks.
Q: Do you foresee deploying the architecture (programming language as well as the hardware) on quantum computers? If so, what can be some of the reprecussions in terms of deployment?
A: Ackley is waiting to be proven wrong, but for the moment he is a quantum skeptic. He suspects once error decoherence has been properly accounted for, in essence what quantum computing will give us is a huge constant factor over traditional computing. We will use it because we like huge constant factors, but it wont be “suddenly all the secrest are gone” that people talk about. For the MFM, all we require from hardware level is that it can do these flexibly specified transition functions. We need to come up with byte code, a VM language to compile to the VM. Then anybody that can figure out how to implement the VM can become a substrate to do these things. He does not see quantum folks being anywhere near this being applicable in his lifetime.