A SPARQL UPDATE query emulating a PDP-1 running Spacewar!

by Michael Brunnbauer, 2013-10-14

The background

SPARQL (SPARQL Protocol and RDF Query Language) is a language to retrieve and manipulate data stored in Resource Description Framework format.

The PDP-1 (Programmed Data Processor-1) was the first computer in Digital Equipment Corporation's PDP series and was first produced in 1959. It is famous for being the computer most important in the creation of hacker culture at MIT, BBN and elsewhere. The PDP-1 was also the original hardware for playing history's first game on a minicomputer, Steve Russell's Spacewar! (quoted from Wikipedia).

One pattern to (ab)use SPARQL UPDATE as a programming language is this:

DELETE { old state } 
INSERT { new state }
WHERE {
OPTIONAL { SELECT (new state1) WHERE { old state1 } }
OPTIONAL { SELECT (new state2) WHERE { old state2 } }
}

The OPTIONAL clauses describe the possible state transitions and the "program" is executed by repeating the query until the desired state is reached.

The first time I used this pattern was for a query that searches for SPARQL endpoints. I created a query for a Turing machine shortly after. Then I thought about the C++ PDP-1 emulator I wrote a long time ago using this PDP-1 Java emulator as pattern.

I removed all loops and recursions from my C++ emulator - introducing intermediary states for instruction fetching and indirect adressing. Then I proceeded to convert the code into SPARQL - sometimes looking into this PDP-1 manual.

Writing the SPARQL query was quite tedious because:

• SPARQL has no bitwise operators
• Intermediary results are only possible with subqueries
• SPARQL has no integer division (call floor() every time you divide and be careful to cast to integer with xsd:integer() if necessary)

The results

• The query doing the emulation
• The query to initialize the machine with Spacewar! in memory.
• A Python script to initialize the machine and repeat the emulation query. The number of iterations is passed as command line parameter. After the specified number of iterations, a consistency check is done and the registers and a hash of the machine state (including memory) is printed on stdout.
• The "Ontology"

This image was created using this Python script after 30000 iterations of the query, showing the first frame.

Q&A

How fast is it?

Ca. 2s per query with Jena Fuseki. My C++ version runs ca. 50 million times faster :-)

How do I control the spaceships?

By changing the control word (property pdp1:control):

Bit 2 Spaceship 1 turn left
Bit 3 Spaceship 1 turn right
Bit 1 Spaceship 1 thrust
Bit 0 Spaceship 1 fire
Bit 16 Spaceship 2 turn left
Bit 17 Spaceship 2 turn right
Bit 15 Spaceship 2 thrust
Bit 14 Spaceship 2 fire

Hyperspace is activated with turn left+right pressed simultaneously.

The Sense switches (property pdp1:sense) can be used to control features of the game:

Bit 0 Activate angular momentum
Bit 1 ?
Bit 2 ?
Bit 3 Disable starfield
Bit 4 Enable collisions with central star
Bit 5 Disable central star (and gravity)

Why?

Well... it was pointless and tedious - but it was also fun. Maybe it can be of use for SPARQL validation/benchmarking suites.