DEV Community: Andrew Buntine

The historical obscurity of the SEGA SC-3000 Personal Computer

Andrew Buntine — Mon, 08 Jan 2018 08:55:49 +0000

This post is part of a series on the retro SEGA SC-3000 personal computer. In the next part I will give an introduction to writing BASIC on this machine. In the last part we will make a simple shoot-em-up video game and persist it to audio cassette.

It was an otherwise average hot summers evening in Melbourne, Australia when I heard a "knock, knock" at the door.

I saw my neighbour standing in front of me with a large plastic bag in his hand. Upon closer inspection, I could see the plastic bag seemed to contain a stack of old video games and assorted peripherals. My eyes lit up a bit but I tried to hold my excitement.

He went on to tell me that he was doing some demolition work in an abandoned house in the outer suburbs when he'd stumbled upon an "old computer or something". He knew I was into that type of thing so he asked if I wanted it.

Did I want it?! Hell yes, I did. I've always been a huge fan of retro computer gear. Finding something lke that in an abandoned house is like treasure to me!

"OK, compose yourself Andrew", I thought to myself.

I ran inside and grabbed a ~$300 bottle of Dom Pérignon that I'd been given when I started my last job. After some convincing, he took the bottle and we called it a fair trade.

Better than expected

When I got inside and emptied the contents of the plastic bag on my loungeroom floor, I saw it was a lot more than I'd initially realised. In the bag there was a retro minicomputer, some RF cables, an AC adapter, five software cartridges, a joystick and a game pad. All boxed and in near mint condition. It was like a time capsule from simpler times.

Wait, a SEGA computer?

One thing that really stood out to me was the logo on each of the games and the computer itself: SEGA.

Since when did SEGA make home computers?

When I was a little kid, the first video game console I'd owned was a SEGA Master System (or Mark III in Japan). It was a great little system with a good catalogue of games developed for it. What I did not know, however, was that before the Genesis, before the Saturn and even before the Master System - SEGA released a home computer called the SC-3000.

Amazing... But there was also something else that stood out. The machines full name was the "John Sands SEGA SC-3000H Personal Computer".

For those who are not aware, John Sands is an Australian supplier of greeting cards and gift wrap. Just take a look at their website - it doesn't look much like a computer distributor, does it? Well, sure enough, in the early 80's John Sands really did enter the fledgling home computer market when they helped SEGA distribute this machine and a video game equivalent called the SG-1000.

Mind blown...

OK, gimme' the nitty gritty details

The reason you've probably never heard of this machine is because the SEGA SC-3000 was released in just a few markets: Japan, Australia, New Zealand, France, Italy and Finland.

It did not fare particularly well in Europe but saw some minor success in Japan and Australia/NZ. Infact, the SC-3000 represents SEGAs first and last foray into the personal computer market. And although the SC-3000 was marketed as a tool primarily for home business and educational use, it was seemingly only ever used to play video games. What a surprise...

The machine was released in two models: The SC-3000 (with rubberized keys) and the SC-3000H which boasts a fully mechanical keyboard (and a pretty nice one, I must say!). Each market seems to have got it's own colour variant, also. All of the John Sands Australian models are black. Supposedly the white models are the rarest.

On the back there is a power switch, a DC-in, composite video port, printer port, audio cassette in/out ports (I'll discuss those a bit more later) and an RF connector port for plugging into your television.

On one side there is a large space to put software cartridges. On the other there is two standard joystick ports.

On the inside there is an 8-bit NEC D780C-1 CPU running at 4 MHz. I believe it's identical to the more well known Z80 CPU that saw massive use during the 80s in scientific calculators and many arcade machines.

Embedded in the machine is just a measly 2Kb of RAM. Along with 16Kb of VRAM provided for the video display processor (a Texas Instruments TMS9929A). Perhaps a surprise to some people, but the software cartridges actually provided their own RAM (anywhere from 1Kb up to 32Kb). While a game was running, it would read and write via the RAM on it's own cartridge. So, unfortunately that means saving your game progress and coming back later was simply out of the question!

And how about the software?

The SEGA SC-3000 has no operating system. In fact, if you turn it on without a cartridge stuffed in the side of it you will get just a blank screen of nothingness.

As I mentioned previously, the main way of distributing software was via cartridge. The SC-3000 cartridge slot was also compatible with games for the earlier SG-1000 and the SEGA "my card" format.

I found out the hard way that these cartridges tend to get dirty (even when left in their box) and so I spent quite some time cleaning them with cotton buds before I was able to get each to work. It was very nostalgic to sit in my living room blowing into cartridges and wiggling them around. It definitely brought back memories of my childhood!

I believe there was less than 100 officially released games for the SC-3000/SG-1000 systems, which I can only assume means they are probably pretty rare nowadays. Although, somewhat amazingly, there is a group of fans who have provided many of the tapes dumps as uncompressed audio files on over at the SC-3000 Survivors website. This means you can actually play many lost SEGA games on this retro machine via the Internet. Wow!

How do I hack on this thing?

Like many home computers of the time, the SC-3000 was intended to be programmed via the BASIC programming language. From my research, it seems to me that all models were sold with a BASIC cartridge. There were a few separate BASIC cartridges available, the difference lying in the amount of RAM available. The most "basic" release had just 1Kb (of which 512 bytes were taken by the BASIC runtime itself). The other releases has 16Kb and 32Kb, respectively. Many adverts of the SC-3000 at the time boasted of 48Kb of RAM - but this would only be the case if you also bought the most expensive BASIC cartridge!

The SC-3000 also allowed for one relatively interesting means of I/O in conjunction with the BASIC cartridge - via standard audio cassettes. The software was written to the tape bit-by-bit, each taking just under 1ms (833.3μs) to record. This resulted in roughly 6.8 seconds of audio per kilobyte of data. So reading a 16Kb game from cassette and onto the memory on the BASIC cartridge would take nearly 2 minutes...

Once your cassette player had been plugged into the SC-3000 via 3.5mm audio cable, it could be read into memory and executed very simply:

LOAD some-game
RUN

What's next?

Hacking, of course. But for that we will have to wait until the next post.

Laser Drift: Reverse engineering slot cars for fun and (maybe) profit!

Andrew Buntine — Mon, 28 Aug 2017 12:29:49 +0000

In this blog series I discuss the creation of Laser Drift, a system that allows you to remotely control any Carrera Digital slot cars by emulating the infrared wireless controllers for between one and four players in realtime.

Feel free to take a look at my promo video or the Github repo before you read.

Motivation

A couple of months ago I was in a brainstorming meeting with the Creative Director, the Head of Strategy and an assortment of other tech people. This is a volatile melting pot of skills that in the past has produced many amazing things (and the odd Frankenstein). Our client had tasked us with "doing something awesome with one of those BCI devices". For those unaware, Brain-Computer Interface devices measure electrical activity in the brain and provide an SDK for performing computations based on simple thoughts, emotions and physical gestures.

These open briefs are generally great, but it can be difficult to come up with a viable idea that satisfies everyones concept of what constitutes awesomeness and (God forbid) fits within the proposed budget.

We eventually settled upon the idea of brain powered slot car racing, in which a user would think certain thoughts like "push" in order to make the cars move. So, in a nutshell, two to four players would race against each other and the first player to n laps would win. We felt this would work well because (as those of us old enough to remember already know) turning is automatic in slot car systems. Users had only to move forward and the rest would be be taken care of.

This idea also satisfied a few other prerequisites - most importantly it would allow users to interact with the physical world. The client, perhaps correctly, felt that it would be more impressive if the BCI device was able to move physical objects opposed to digital ones.

To me, this idea actually involved two separate projects. First:

PC -> Slot Cars: We needed to create software to accurately control up to four players on a slot car set using simple, language-agnostic commands

And second:

BCI -> PC: We needed to create software to listen for mental commands like "push" and "pull" and then translate them into those simple commands I mentioned above

In this series I will discuss the former as it is by far the most interesting and challenging of the two - even though "mind control" may sound cooler in a press release.

The project manifested itself in three phases. In this post I will discuss the first two:

Research and Experimentation
Reverse Engineering

In a separate post I will discuss the creation of the solution itself: Laser Drift.

Research and Experimentation

The only experience my colleagues and I had with slot cars were distant childhood memories of analogue cars zipping around single-lane tracks. And so the first task at hand was to find out what a state of the art slot car set looked like in 2017.

Wow! They've really come a long way.

In the old days, each car needed to occupy it's own lane. And if any two cars got in the same lane, they would always travel at exactly the same speed. They were fun, but relatively monotonous toys.

But that was the past! For in about 2004, the major manufacturers started introducing digital systems in which each car could be uniquely identified (even if they occupied the same lane). So now players can freely change lanes, simulate oil spills, have pit stops, configure braking performance and even represent real-world concepts like fuel levels and tyre blowouts. All of this was going to allow for a whole new dimension of badassery in the end result.

The next point of call was to decide was which slot car manufacturer we would go with. As it turns out, there are two main players in the slot car world: Scalextric and Carrera. The general sentiment among enthusiasts is that Scalextric is for the older, hobbyist demographic whilst Carrera is for the younger crowd who just want to have some fun. But both options are of a very high quality.

After some looking around, I found that Carrera offered a bluetooth interface called the AppConnect that would allow one to program car speeds, set fuel levels and perform various other tasks. One Thomas Kemmer had also released Python bindings into the underlying protocol, whch meant I could easily whip up a python program to control the cars. I was starting to think this whole thing may be much easier than I initially thought...

Oh, ignorance is bliss.

My elation was quickly extinguished when I realised that by "programming car speeds", Carrera had meant that the bluetooth interface can be used to pre-program cars with individual top speeds before a race. It's of no use during a race! Alas, we still ordered a new (and pretty damned expensive!) Carrera Digital 132 GT Championship Wireless+ set and the bluebooth adapter regardless. This particular set came with wireless controllers, which communicated with the control unit on the track via infrared (atleast, that is what I had read on the official forums).

At this point I realised that there was no official way of using a PC to control each car in realtime. And so we hit the drawing board.

The first idea was to physically press the accelerator on the controllers using something like a linear actuator. The controllers themselves would be housed in a chassis of some kind and we'd use a hobbyist microcontroller like an Arduino to press down on each controller when desired. If you watch the first 20 seconds of this video it should be obvious how this may work.

This would have the benefit of not requiring us to open the hood of the Carrera set but simply to emulate the pressing of a thumb. Although it did require a whole bunch of additional hardware for each controller and some specialised skills that no one on the project professed to have. It also didn't give us the accuracy we were really after as the actuators we found tended to actuate very slowly.

The next idea was to reverse engineer the controllers infrared signals. We could emulate the entire array of controllers as long as we could send the right data packets at the right time. I mean, the controllers are basically like really simple TV remotes, right? This would require some hardware aswell, but atleast there would be no soldering involved.

I did some additional research online and I was able to find some brialliant work by Stephan HeÃŸ in which he showed the basic contents of the infrared packets sent by the controllers. This meant that we already had some of the reverse engineering completed for us. And I already knew that cheap USB-based IR transceivers like this one from Irdroid were readily available.

So it was decided: We would use an infrared transceiver to emulate the data sent by the controllers to the control unit. One simple device would act as all of the controllers.

One additional curve ball was thrown my way when I took a closer look at the controllers we had. They were not the 38khz IR controllers I had read about but actually 2.4ghz RF! This was going to make communication a whole lot more difficult. As it turns out, the IR controllers were decommissioned in 2013 and replaced with the superior RF models. Luckily, it seemed that the new control units still supported the older controllers. So I got en ebay and bought the older gear that I wanted.

Reverse Engineering

The IR transceiver I purchased was the Irdroid. Interestingly, it's handmade in Bulgaria in repurposed SD card readers. The reason I chose this device was because it's supported out of the box by the predominant infrared tool suite for Linux environments, Lirc. LIRC is a package that allows you to decode and send infrared signals of many (but not all) commonly used remote controls. A full introduction to it is beyond the scope of this article, but it's sufficient to just know that lirc gives you the ability to send and receive IR blasts in a Linux environment.

An important part of reverse engineering is to take small steps. Try to get a general idea of how the device works before trying to reach the end goal. For me, the first port of call was to see what the information coming from the controllers looked like. To do this, I used a low-level tool that lirc provides called mode2. Mode2 simply listens for raw IR data and prints it to STDOUT.

Let me explain what IR data looks like.

Infrared devices typically encode their message to the receiver via a method called Pulse Code Modulation (PCM) in which an IR-emitting LED is switched on and off rapidly. When the transmitter is "off", we call it a space. And when the transmitter is "on", we call it a pulse. There are a few common methods for encoding binary into pulses and spaces, but all involve transitioning between said pulses and spaces.

In my case, I expected to see a random looking series of pulses and spaces being printed to STDOUT. But I got nothing. No matter what I did, I could not get any output from the controller. I spent the next hour troubleshooting why the Carrera control unit could pick up on the IR data but I couldn't. It wasn't until I pointed my IR transceiver at the control unit itself that I realised there was more to the story.

The control unit (well, technically the IR device on the unit) was actually sending out the following signals every ~70 milliseconds:

pulse 800
space 700
pulse 550

The numbers are microseconds. What we are seeing here is a pulse of 800Î¼s, a space of 700Î¼s and then a pulse of 550Î¼s. This was repeated ad infinitum.

As it turns out, the controllers only respond when they are instructed to by the control unit. Pressing the button does not actually cause an IR transmission. It just updates some state on the microcontroller in the controller itself. This, I assume, is important for synchronising the controllers so that their transmissions do not get tangled on the receiving end.

Cool. So the next thing I did was transmit the syncing blast from my transceiver to the controller and see what it returned. This is what I got back:

pulse 300
space 1000
pulse 250
space 250
pulse 250
space 250
pulse 500
space 250
pulse 250
space 500
pulse 250
space 250
pulse 250
space 250
pulse 250

At the suggestion of a friend, I wrote a little script to visualise this with a step graph where a pulse is high and a space is low.

I performed this test a bunch of times. I could see that the transmission repeated every ~60 ms. And it always started with a pulse of 300 followed by a space of either 750 or 1000. This was definitely the start bit, which told the control unit that the blast was coming from a controller and that the rest of the transmission was the payload.

Following the start bit was a series of pulses and spaces that were always either 250Î¼s or 500Î¼s.

After some additional experimentation and research I presumed Carrera were using Manchester Coding to encode their data packets. In Manchester Coding, a bit is represented as a transition from either low-to-high or high-to-low. Specifically, 1 is encoded as a pulse of NÎ¼s followed by a space of NÎ¼s. And 0 is encoded as a space of NÎ¼s followed by a pulse of NÎ¼s.

As we can see, in our case N = 250. So each bit required exactly 500Î¼s. Summing the numbers together (minus the start bit) we get 4000. And 4000 / 500 = 8. So the data packet consisted of a start bit followed by eight bits (one byte) of data.

Consulting the work of Stephan HeÃŸ, which by this point had saved me many hours, I was able to confirm the structure of the data packet sent by each controller. Each controller sent the start bit, followed by two bits representing the player, four bits for the speed and one bit to indicate whether the lane-change button was pressed. Wait - that's only seven bits!?

As it turns out, there was also a trailing bit that seemed to be used to represent additional players. I assume it was added to the end for backwards compatibility with older models. This also explained why there was no end bit on the data word - it allowed for future expansion of the payload whilst maintaining backwards compatibility.

I've drawn the payload contents below.

As an example, let's suppose we were player #3 travelling at speed 7 with the lane change button pressed. Our 8 bits would look something like this:

10011110

To encode these bits into pulses and spaces using Manchested Coding we can first add the start bit:

pulse 300
space 750

And then we start adding in each bit one by one. Remember that bits in Manchested Coding are represented as a transition. So let's add the 1 (a pulse followed by space):

pulse 300
space 750
pulse 250
space 250

So far so good. Let's add the next bit, a 0 (a space followed by a pulse):

pulse 300
space 750
pulse 250
space 250
space 250
pulse 250

Uh-oh! Now we have two spaces in a row. We can fix this by simply merging them into one, longer space:

pulse 300
space 750
pulse 250
space 500
pulse 250

Cool. Every time we see a 0->1 or a 1->0, we are going to merge one end with the other to produce a pulse or a space of 500Î¼s. Now let's add in the rest of the bits:

pulse 300
space 750
pulse 250 # 1
space 500 # 0
pulse 250
space 250 # 0
pulse 500 # 1
space 250
pulse 250 # 1
space 250
pulse 250 # 1
space 250
pulse 250 # 1
space 500 # 0
pulse 250

And we're done!

Here is another representation:

And when we visualise it as a step graph, the data packet is very similar to the one I showed above. You should be able to see the difference between the 250Î¼s and 500Î¼s bursts.

And with this, the reverse engineering project was complete. From here I was able to use lirc to listen for the syncing blast from the Carrera control unit and respond with some hardcoded data packet.

After I solved some minor timing issues I was elated when I saw the car move! It was proof enough for me, at the very least, that the idea was not totally bonkers.

Below is a video of the first time I got the car to move without a physical controller. In this video I am ignoring all syncing efforts from the IR tower on the Carrera set. I am just blasting the same message over and over and hoping the timing is correct. This explains why the car only moves in little bursts.

Laser Drift

Wow, this post got long...

I am going to leave the details of the end-result to another blog post. For now, you can check out Laser Drift on Github or watch the promo video I embedded at the top of this article.

Hulkamania! Or; How I made our office play personalized entrance theme music

Andrew Buntine — Sun, 02 Apr 2017 12:47:38 +0000

This blog post details how I hacked the office WiFi to play entrance theme music for my colleagues when they entered the building each morning. If you only want to see the finished product and are not interested in the details, here is a little video demonstration (including some seriously underreceived overacting):

I was a pretty normal 90's kid. My brother and I spent more than our fair share of time watching and emulating our favourite WWF (ahem, WWE) superstars.

We didn't get wrestling on television in Australia and so we were limited to watching the VHS releases on Coliseum Video. And watch them we did! Every Friday night we would take advantage of the "5-for-5" deal at our local video shop, which allowed us to hire five weekly videos for just $5. Typically, at least three of these would have been classics like Wrestlemania X, SummerSlam '95 and Royal Rumble '94.

One of the most satisfying parts of the wrestling events was the theme music that each wrestler would get when they were first entering the ring (or squared circle, as I should say). For those uninitiated into the world of very-much-not-fake-I'm-sure-of-it wrestling, the average entrance looked something like this:

I'm sure you noticed the uncanny similarities between myself and "Stone Cold" Steve Austin.

Growing up, I thought it was only fair that I got my own theme music. And I figured that if I got theme music, then my colleagues also deserved their own (even if they disagreed).

Luckily, we already had a bunch of Internet connected Sonos speakers in the office that I could communicate with over the LAN. So I knew the actual playing of music would be easy enough. And so the main problems were now:

Detect when someone entered the office
Determine who it was
Determine if this is their first visit today
Perform 1, 2 and 3 without any input from the user (aka magically)

My first thought was to use a proximity sensor on the main door ¹ . This was short-lived as I determined that users would need to buy-in to the idea by installing an app on their phone and agreeing to some terms and conditions. Not to mention the fact that I'm way too tight to actually buy those sensors.

After what was probably an embarrassing amount of time pondering the problems, I eventually realized that the WiFi was a perfectly suitable way of determining when people entered and left the office area. And because our office WiFi signal is strong enough to reach the footpath out the front, it would have the added benefit of playing a users theme song slightly before they entered the building (you know, for added realism).

I started digging around in the office router control panel hoping I'd find some way of easily detecting WiFi events like connect and disconnect. After some time I came to the conclusion that it wasn't going to be that easy! Whilst I didn't find a way of detecting events ², I did see that this particular router had pretty comprehensive logs. I thought that perhaps a quick and dirty approach would be to continuously poll the logs looking for useful events. It wasn't great, but it was something.

After some further investigation I found that I was able to forward the router logs over TCP to a remote syslog server. This was important because it meant that the router could push the events to me instead of me having to continuously tail a log file. I started to see how this thing was going to come together. So I found an old computer in a closet, installed a flavour of Linux on it, connected it to the LAN and had syslog listen on TCP port 514 (the syslog standard port).

It worked! I tailed /var/log/syslog and started seeing logs like this almost instantly:

DATA 127.0.0.1: <14>Dec 12 15:15:20 10.our.host.com.au (\"YO,v3.7.21.5389 libubnt[1441]: w event.cust(): EVENT_STA_JOIN ath0: 00:34:da:58:8d:a6 / 3

Every time a device connect and disconnected from the network, a log including the devices unique mac address was appended ³. Awesome! But there was a lot of noise. There were logs for connections, disconnections, roamings, handshakes, failed connections, rate limiting, etc. I eventually decided that there were only two events that I was actually interested in: EVENT_STA_JOIN and EVENT_STA_LEAVE. So I added some syslog configuration that would

Find logs that matched my desired events
Forward them onto local TCP port 10514 (Where I'd have a simple TCP server running to handle the next step)
Ignore everything else

The syslog configuration ended up looking like this:

if $msg contains "EVENT_STA_JOIN" or $msg contains "EVENT_STA_LEAVE" then
   action(type="omfwd" Target="localhost" Port="10514" Protocol="tcp")
& ~

So now the problem was much simpler. Every time someone connected or disconnected from the WiFi, my little computer in the corner of the room was sent the devices mac address and an indication of the event type (JOIN or LEAVE). All I needed to do now was to read those incoming messages, map the mac address to a Human and then play the appropriate song.

I wrote a TCP server in the Rust programming language, which you can check out on Github ⁴. It simply reads the byte stream into a string, parses out the useful information and then takes the appropriate action on the Sonos.

In terms of knowing who was triggering the WiFi event, I kept it simple and just created a JSON file that mapped mac addresses to names, songs, greetings, etc. It looks something like this:

{
  "3d:5b:22:b7:dc:a9": {
    "name": "Andrew",        // In case I want it later (and for logging)
    "state": "UNSEEN",       // IN | OUT | UNSEEN
    "song": "owenhart.mp3",
    "join": "Welcome to the office, Bunts",
    "leave": "See you later, Bunts",
    "lastEvent": 1490436790  // Unix Epoch timestamp
  },
  "4d:aa:58:b6:9a:61": {
    "name": "Mel",
    "state": "IN",
    "song": "stonecold.mp3",
    "join": "Welcome back, Mel",
    "leave": "I hope to see you soon, Mel",
    "lastEvent": 1490436790
  },
  // ...
}

Each night at midnight I have a little cron job that resets each users state to UNSEEN. I use this to ensure that a particular theme song is only played the first time the given user connects to the WiFi. Any subsequent events trigger a greeting or exit message to be vocalized over the Sonos. This was achieved using the great Google Text-to-Speech service.

The only thing left to do was to add in some minor smarts to prevent the office from being spammed with "hellos" and "goodbyes". I noticed that certain devices would often lose, and then quickly reestablish, their connection, which would cause their greetings to be fired in succession even though the user didn't actually leave and re-enter the office. I tackled this by ensuring that certain events had to match criteria in order to be considered valid. For example, in order for a JOIN event to be considered valid, the user in question must:

Be in the OUT or UNSEEN states
Not have fired any events in the past 15 seconds

I also allowed for the join and leave keys to have an optional array of strings, in which a random greeting would be chosen and vocalised. This gave the whole thing a bit of variation and prevented people from tiring of the same greetings every day.

The final product was now ready to rock and roll! After adding in some logging, I ended up with something like this:

As for next steps, creating a simple GUI to wrap the JSON file (or perhaps I should do the right thing and move it to a database) would be pretty simple. This would provide users with a simple way to actually write their own greetings and upload their own favourite theme music. And, at least theoretically, this system could be used for more practical tasks such as a slack bot that could tell an employee if a certain colleague was in the office.

I believe this type of passion project is a great way to get out my creative energy whilst also giving the office a refreshing spin. Thanks for reading!

Footnotes:

In case you were wondering - no, unfortunately we don't have any type of swipes or user identification processes in place when people enter the office.
I later found out that the router actually shipped with a minimal HTTP API that may have been sufficient - but finding documentation and examples proved difficult.
Yes, I know that some mobile operating systems spoof mac addresses. But this is not a problem in the short term as once a device connects to a WiFi network, it's reported mac address tends to stay the same. Spoofed mac addresses are more of a concern for WiFi networks that are trying to track unconnected devices across nodes.
I've since moved some of the higher-level details to a Node-based web service for reasons totally uninteresting to the reader. I've decided not to mention that explicitly in the article as it derails the technical details unnecessarily.

DOM elements with ID's are global variables

Andrew Buntine — Thu, 12 Jan 2017 13:07:23 +0000

So, here is something weird.

Yesterday I was refactoring some code and came across something akin to this:

const logo = document.getElementById("brand")

brand.style.top = 0

At no point in the codebase was a variable named brand defined. And so any sane observer would expect that the preceding snippet would result in a runtime error -- assuming there was not something like a linter available that would have picked up on it (and the fact that logo was being defined but never used) first.

I started having one of those moments that we all dread: I was looking at some code that could not possibly have ever worked. Yet, there it was. Working. I sank into my chair, not sure to make of what I was seeing.

In fact, the only other place I could see the word "brand" in the entire application was in the HTML document upon which this Javascript was being executed (yes, some websites still send HTML over the wire).

So I changed it:

<div id="brand_foo"> ... </div>

And then, lo and behold, the code instantly started causing a runtime error. Wait. No way... The browser is surely not pre-defining a global variable for each DOM element with an ID attribute. Right?

Wrong! It does. I've looked at this code in most major browsers and mobile devices and not one of them complained.

Don't believe me? You can try it yourself right now. Press F12 (or otherwise Right Click -> Inspect), find an element with an ID, and then evaluate that ID at the console REPL.

What about IDs such as "brand-name" that don't conform to Javascript's grammar? Surely they are ignored? Nope:

window["brand-name"]  // --> <div id="brand-name">

I have no idea how well known this is. I certainly did not know about it but, admittedly, I haven't spent a lot of time in the browser in many years. I've reached out to all of the frontend developers I know and none of them knew about this either.

As it turns out, the HTML specification actually documents this functionality. Although it seems major browsers are not implementing it uniformly at all. If you define more than one element with the same ID (you evil person), then Chrome will actually return an array of Element objects whilst Firefox returns the first element it saw. And neither browsers define global variables based on the name attribute on elements like img and a.

Should I make use of this?

No. Please, no. Imagine how confusing this could get if you were dealing with many DOM elements in a non-trivial codebase and none of them were being defined anywhere visible to the programmer. Or imagine if you go all-in and then one day a major browser decides this is insanity and disables it!

The only place I can see this being of use would be in the REPL whilst debugging. But, still, it's kind of cool in a never-do-this kind of way.

Header image originally from http://www.classichorrorcampaign.com

Pâ€³ - The original Brainf*ck and mother of the Turing tarpits

Andrew Buntine — Mon, 05 Dec 2016 06:37:33 +0000

When we think of esoteric programming languages, most of us quickly gravitate towards one in particular: the infamous Brainf*ck - a super minimal programming language that achieves Turing Completeness in just six simple instructions (not including the two for I/O).

The incessantly lovely Brainf*ck was created in 1993 by Urban MÃ¼ller in an attempt to construct a usable - albeit barely - programming language with a compiler under 1024 bytes. Why 1024 bytes? Well, he had been inspired by Wouter van Oortmerssen's FALSE, a stack-based language with a compiler of exactly 1024 bytes. So I guess you could say it was a competition of sorts.

In this article, purely for the joy of it, we will see that Brainf*ck is actually an informal dialect of a programming language invented in Italy more than 50 years ago: Corrado BÃ¶hm's Pâ€³ (pronounced "P Prime Prime" or "P Double-Prime).

I do expect that the reader has basic familiarity with Brainf*ck - although, if you've never heard of it, I definitely recommend you take a look. Oh, and don't worry; despite the scary name, it's really very easy to learn (note, I didn't say "easy to use"!).

Let's talk a bit about Corrado BÃ¶hm's place in the history of Computer Science before we get into the nuts and bolts of his decidedly strange creation.

Corrado BÃ¶hm and the Structured Program Theorem

You can skip this section if you're only interested in the details and not the motivation.

When we talk about "programming" today, we are almost universally referring to what is known as "structured programming". That is, writing programs that employ the use of block structures, functions and loops. Pretty simple, huh? In fact, this all seems so obvious nowadays that we don't feel the need to qualify so specifically what we mean - so we use more general terms like "imperative" and "declarative" to describe our favorite paradigms of programming. The whole "structured" part is kind of a given.

But it wasn't always this way...

Many of the earliest programming languages, including heavy-hitters like BASIC, FORTRAN and COBOL¹, were unstructured: Statements were sequentially ordered, generally one per-line. And those lines were given labels or numbered in such a way that a program could perform an unconditional jump from one part of the program to the other.

And when I say "jump", I really mean jump! Execution was not returned back to the calling context as is the case with a function call (unless, of course, it was physically asked to with another jump). One could, at least theoretically, jump straight into the middle of a SUBROUTINE or an IF². Following the execution of a program meant tracing all of the jumps. Such a messy form of execution eventually gave rise to a phrase we still hear a lot of today (but never about our own code, of course): "Spaghetti code"³!

In case you haven't worked it out already; yes, I am talking about the notorious GO TO.

The early '60s were dominated by the debate over structured vs. non-structured programming. This was further ignited when, in 1966, a landmark paper titled "Flow diagrams, Turing Machines and Languages with only Two Formation Rules" was published by Corrado BÃ¶hm and Giuseppe Jacopini. This paper⁴ provided the theoretical foundation for structured programming (and therefore the abolishment of GO TO) by proving that one can compute any computable function with only three simple control structures:

Execute one subprogram, and then another subprogram (sequence)
Execute one of two subprograms according to the value of a boolean expression (selection/branching)
Execute a subprogram until a boolean expression is true (iteration)

To demonstrate this in relation to Turing machines, they, of course, used a programming language: Pâ€³

Pâ€³, the mother of the Turing tarpits

Pâ€³ is a very simple. In fact, it's so simple that the whole thing can get a bit confusing. Kinda' like those movies that are so bad they loop back around to being good again. The language consists of only four characters: R, Î», ( and ) that act upon a Turing machine with infinite tape (main memory) and a finite alphabet (the set of things that can be written in a memory cell - such as the digits 0..9).

BÃ¶hm defined the syntax rules⁵ as follows:

Î», R âˆˆ Pâ€³
qâ‚, qâ‚‚ âˆˆ Pâ€³ implies qâ‚qâ‚‚ âˆˆ Pâ€³
q âˆˆ Pâ€³ implies (q) âˆˆ Pâ€³
Only the expressions that can be derived from rules 1, 2 and 3 belong to Pâ€³.

Right. Let's try that without the set notation:

The characters Î» and R are syntactically valid programs in Pâ€³.
Programs can be composed. So, if qâ‚ and qâ‚‚ are programs in Pâ€³, then so is their composition: qâ‚qâ‚‚.
Any valid program can be iterated over. So, if q is a program in Pâ€³, then so is (q). This will make sense when we get to the semantics.
That's it!

BÃ¶hm then goes on to explain the language semantics, which I've summarized and simplified here:

The machine has a finite alphabet of length N, where N > 1. 0 is considered a special, blank symbol. So each memory cell can contain any value from 0 to N. Because we are dabbling in the theoretical world of Turing machines, we can say that the exact value of N is precisely what it needs to be for the computation at hand.
Execution starts at the leftmost symbol and proceeds to the right until there is nothing left to compute.
R is the operation of shifting the tapehead (a.k.a data pointer) forward to the right one cell (if there is one).
Î» is the operation of replacing the symbol, c, at the tapehead with (c+1) mod (N+1) and then shifting the tapehead to the left one cell. Note the modulus operation - so if N = 5 then trying to increment 5 will result in 0 (the blank symbol) because 6 mod 6 = 0.
(q), where q is any valid program, is interpreted as a while loop that iterates while the current cell does not contain the blank symbol (0). Endless loops are possible, of course.

So, we can think of Pâ€³ as being a near-literal implementation of a Turing machine in a similar sense that we can see the original Lisp as being deeply related to Church' Lambda Calculus. The former is just far less useful to the practicing programmer.

In a paper published in 1964 for the International Computation Center in Rome⁶, BÃ¶hm proved that Pâ€³ was Turing-complete, which makes it the first structured programming language that did not contain a GO TO instruction but instead relied upon iteration. Djikstra would go on to cite BÃ¶hm and Jacopini and in his now-famous paper, Go To Statement Considered Harmful, which would help to solidify their place in computer science folklore.

Here is a simple program to add two numbers together for a Turing machine where N = 3 and main memory looks something like this [2, 1]:

(
 Î»RÎ»RÎ»R    # Decrement current cell (remember that N+1 wraps back around to 0, so decrementing is equivalent to N increments).
 R         # Move tapehead right.
 Î»R        # Increment current cell.
 Î»RÎ»RÎ»RÎ»   # Move tapehead left by decrementing the current cell and then executing one final Î».
)          # Iterate if the current cell is not 0. This means we iterate twice in this example.

At the end of execution main memory will look like this: [0, 3].

Ok, cool, I guess. Maybe you can see some minor similarities to Brainf*ck, but we are definitely missing some things. And even in esoteric programming language terms, it's all very clunky!

But, luckily for us, BÃ¶hm provided several small abstractions that allow us to write much simpler programs. And in doing so we will see that Brainf*ck and Pâ€³ are equivalent.

Let's take a look.

When two become one

There are a few instructions that Brainf*ck gives us that we don't get out-of-the-box with Pâ€³. Specifically, we still need to fill in the following gaps:

Increment the current cell (without moving the tapehead!).
Decrement the current cell.
Move the tapehead leftward.

Let's define those as follows:

Increment
- I = Î»R
- Increment the current cell and move left, then move right.
Decrement
- D = I^N
- This is defined as N I's in a row. So for a Turing machine where N = 5 it's literally IIIII. The best way to think of D is as a macro that expands to N I's rather than a runtime construct like a function.
Move left
- L = DÎ»
- Decrement the current cell and then increment it (to restore the original value) and move left.

To recap, we have now now defined the following instructions:

Move right: R
Move left: L
Increment: I
Decrement: D
Open loop: (
Close loop: )

Now it's starting to look familiar! And so, finally, let's write the previous program again with our new abstractions:

(D R I L)

And how does the same program look in Brainf*ck?

[- > + <]

Interesting! Although we've decided upon slightly different syntax, these two programs are now semantically identical.

I might just take a moment here to mention that there is something very fulfilling about defining a programming language in which DRILL is a valid program (although, I must admit, BÃ¶hm used different names). I think I'll call my dialect "Braindriller".

Let's try another program⁷ that moves a value from cell 0 two places to the right (cell 2):

R R ( D ) L L ( D R R I L L )

And Brainf*ck:

> > [ - ] < < [ - > > + < < ]

Well, I don't know about you, but I'm sold. I implore you to keep trying other Brainf*ck programs but, considering the two models of computation are now the same, it's my hypothesis that they will all be instruction-for-instruction identical.

One final note - you'll notice that we've skipped on the I/O instructions , and . that exist in most dialects of Brainf*ck. This is because the theoretical nature of Pâ€³ means that practical things like input and output would serve no purpose - we are only interested in the effect of the instructions upon the machine state (memory cells). But if you were to build a Pâ€³ interpreter - and I encourage you to do so - then you could implement I/O exactly as Brainf*ck does.

Thanks

If you've made it this far - well done! And I'm sure the mental energy you've just exerted will all pay off in the long run. Think about it: Next time you're talking to someone who brings up Brainf*ck, you can tell them all about the wonders of Pâ€³ and the genius of Corrado BÃ¶hm.

As always, corrections and feedback are always more than welcome. :)

BASIC, FORTRAN and COBOL all added support for structured programming in later versions.
I guess this would make coroutines somewhat simple to implement.
It's not known exactly who coined this term, but according to Wikipedia, an early usage comes from the Guy L. Steele's 1977 paper: Macaroni is better than spaghetti
This paper is known to be cited more than it's read. OK, I admit, I tried to get through it all. I really did. But before you judge me - give it a shot yourself.
Had Backus-Naur Form been popular in '64, it would have looked something like this: <program> ::= R|Î»|<program><program>|(<program>).
I have searched high-and-low for a copy of this paper. The ICC was decommissioned in the late-60s and most of their publications are very difficult to find now. I've tracked a physical copy down to the British Library, but am yet to get my hands on it.
Courtesy of esolangs.
Cover image, originally from corradobohm.it, shows the attendees of the first Lambda Calculus Conference (1979). Corrado has the white hair in the second row.

The Balanced Ternary Machines of Soviet Russia

Andrew Buntine — Mon, 21 Nov 2016 00:00:00 +0000

"Perhaps the prettiest number system of all is the balanced ternary notation" - Donald E. Knuth, The Art of Computer Programming, Vol. 2.

It's pretty common knowledge that computers store and operate on data using the binary number system. One of the main reasons for this can be found in the circuitry of modern computers, which are made up of billions of easily mass-producible transistors and capacitors that can together represent two states: high voltage (1) and low voltage (0).

Such a design is so ubiquitous nowadays that it's hard to imagine that computers could operate in any other way. But, in Soviet Russia during the 1950s, they did. Enter Setun, a balanced ternary computer developed in 1958 by a small team led by Nikolay Brusentsov at the Moscow State University.

OK, so before we continue talking any more about Brusentsov and Setun, let me explain a little bit about balanced ternary.

Balanced Ternary

Ternary, or base-3, is a number system in which there are three possible values: 0, 1 and 2. In balanced ternary, these three possibilities are -1, 0 and +1; often simplified to -, 0 and +, respectively.

So, in its balanced form, we can think of the ternary values as being "balanced" around the mid-point of 0. The same rules apply to ternary as to any other numeral system: The right-most symbol, R, has it's own value and each successive symbol has it's value multiplied by the base, B, raised to the power of it's distance, D from R.

Uhh, right, maybe I'll just give you an example. Let's encode 114:

+++-0 = (1 * 3^4) + (1 * 3^3) + (1 * 3^2) + (-1 * 3^1) + 0
      = 81 + 27 + 9 + -3
      = 114

And in binary (base-2):

1110010 = (1 * 2^6) + (1 * 2^5) + (1 * 2^4) + 0 + 0 + (1 * 2^1) + 0
        = 64 + 32 + 16 + 2
        = 114

And, just to be sure, here are the same rules applied in decimal (base-10):

114 = (1 * 10^2) + (1 * 10^1) + (4 * 10^0)
    = 100 + 10 + 4
    = 114

Cool?

Now, what if we wanted to represent -114? Well, in binary and decimal, we need to introduce a new symbol: the sign. In the main memory of a binary computer, this would either translate to storing a leading bit to specify the sign or significantly reduce the amount of numbers we can represent ¹. This is the reason we speak about signed and unsigned integers in programming languages.

But in balanced ternary, as we're about to discover, to represent the inverse of a number we simply have to swap all +'s with -'s and vice versa. We don't need any extra information to represent the sign!

Check it out:

---+0 = (-1 * 3^4) + (-1 * 3^3) + (-1 * 3^2) + (1 * 3^1) + 0
      = -81 + -27 + -9 + 3
      = -114

In a moment we will see that this property (and a couple others) of balanced ternary give us some very interesting computational efficiencies. But, for now, let's go back to talking about the Setun computer.

The Birth of Setun

The late 50's were an exciting time in computers: Nathaniel Rochester and his team at IBM had recently developed the first mass-produced, stored-program (a.k.a "modern") computer - the IBM 701. John Backus and his team had invented FORTRAN, the first high-level programming language that was seeing widespread use. And, perhaps most important of all, the first fully-transistorized computers, such as the TX-0 and the Philco Transac S-2000, were starting to be developed. The path was set for the development of the binary computing machines that have dominated the market ever since.

But that was North America.

At the same time in Russia, a group of mathematicians and engineers under the guidance of Nikolay Brusentsov and his colleague Sergei Sobolev were devising different ways in which computers could operate ². Brusentsov and co. surveyed the array of computers and technological advancements emerging from the West and comprehended their use of transistors to represent binary data. But, let's remember, this was Russia - transistors were not readily available behind the Iron Curtain. And vacuum tubes sucked as much in Russia as they did in the West!

So Brusentsov devised an element from miniature ferrite cores and semiconductor diodes that was able to act as a controlled current transformer, which proved to be an effective base for implementing ternary logic ³. It was found that these elements, compared with their binary counterparts, provided more speed and reliability and required less power to operate.

The team of ten literally built Setun from scratch, working in a small room filled with laboratory tables (which they also built!). Every morning, the team members began their day by assembling five basic machine elements. They started with a ferrite core and, using an ordinary sewing needle, wound 52 coils of wire onto it. The cores were then handed off to technicians who completed the assembly process and mounted them onto blocks.

Ternary logic was implemented by combining two of these ferrite elements and wiring them in such a way that they could represent three stable states. This approach was successful but did nothing to reduce the number of elements required as, in reality, those two ferrite cores could potentially represent two binary bits, which represents more information (2^2) than one ternary "trit" (3^1). Alas, at least their power consumption was reduced!

Setun operated on numbers of up to 18 trits, meaning one could represent anything between -387,420,489 and 387,420,489. A binary computer, on the other hand, would need at least 29 bits to reach this capacity.

Overall, development of Setun lasted two years - although it was operational after just ten days of testing, which was unheard of at the time. In total, only about 50 machines were produced. And even though Setun machines proved capable of operating successfully for years-on-end in Russia's extreme climate, the entire project was racked with controversy.

This was primarily due to the fact the manufacturing plant was unable to justify the mass-production of what they deemed as a cheap intellectual endeavor and the "fruit of university fantasy". I think it's safe to assume that Russia was simply not ready to comprehend the eventual importance of computing machines. Ultimately, the Setun machines were replaced with binary counterparts that were able to calculate with similar efficiency but at more than twice the cost of operation!

But why Ternary?

As I demonstrated briefly above, in Ternary, there is no need to store a leading bit, ahem trit, to indicate sign. Therefore, there is no concept of signed or unsigned integers - everything is just an integer. So subtraction is achieved by simply inverting the operand and applying addition (which is implemented similarly to binary machines). This plus-minus consistency is also able to cut down on the number of carries required in multiplication operations.

Another useful trait of balanced ternary (or any balanced numeral system for that matter!) is the fact that one can implement rounding on floating-point numbers by blatant truncation, which allows for a simplified implementation of division. This is because of the way balanced ternary represents the fractional portion of real numbers.

Let me give you a simple example. Encoding 0.2 looks like this:

0.+--+ = 0 + (1 * (3^-1)) + (-1 * (3^-2)) + (-1 * (3^-3)) + (1 * (3^-4))
       = 0.33 + -0.11 + -0.03 + 0.01
       = 0.2

And to encode 0.8 we must start with a + in the most significant digit and then simply inverse the fractional portion (e.g 1 + -0.2):

+.-++- = 1 + (-1 * (3^-1)) + (1 * (3^-2)) + (1 * (3^-3)) + (-1 * (3^-4))
       = 1 + -0.33 + 0.11 + 0.03 + -0.01
       = 0.8

Above we can see that truncating the trits to the right of the radix point is equivalent to rounding: 0.2 becomes 0 whereas 0.8 becomes 1. Cool!

Programming with trits and trytes!

OK, back to Setun one last time. In the late 60's, Brusentsov developed a more modern machine called "Setun-70" that embodied it's ternarity more directly. The "Tryte" was introduced, which accounted for 6 trits (roughly 9.5 bits). The Setun-70 computer was a stack machine, and so rather than having machine instructions that specifically named registers for input and output, all operations worked on two stacks - one for operands (input) and one for return values (output). In order to accommodate this design, machine instructions were written in reverse Polish notation (a.k.a postfix).

In the late 70's, Brusentsov and some of his students developed a programming language for the Setun-70 computer called the Dialog System for Structured Programming (DSSP). In my research ⁴, I have been able to discover that it is a stack-based language (no surprise there) similar to Forth that uses reverse Polish notation. This allows one to write programs in a relatively high-level language yet still feel "close to the metal". So close, in fact, that the authors had the following to say:

DSSP was not invented. It was found. That is why DSSP has not versions, but only extensions.

Take the following DSSP program that sums a bunch of numbers:

1 2 3 4  DEEP 1- DO +

Let's try to break it down. In the first column we have the instruction, in the second we have the machine state after execution (the operand stack), and in the third I've provided an explanation:

1    [1]            Push 1 to the stack.
2    [2 1]          Push 2 to the stack.
3    [3 2 1]        Push 3 to the stack.
4    [4 3 2 1]      Push 4 to the stack.
DEEP [4 4 3 2 1]    Push "the depth of the stack" (4) to the stack.
1-   [-1 4 4 3 2 1] Push -1 to the stack.
DO   [4 3 2 1]      Initiate LOOP, pop top two items from stack. To control 
                    the loop, the first item is applied to the second item until
                    it reaches 0.
+    []             Apply the "+" operation repeatedly until the LOOP terminates,
                    each time popping the top item from the operand stack stack,
                    applying + and then pushing the output to the return stack.

At the end of execution, the operand stack will be empty and the return stack will contain [10].

You can read a bit more about DSSP over at the website of Ivan Tikhonov (original authors Sidorov S.A. and Shumakov M.N.).

The future

The development of balanced ternary machines has all but faded into a small footnote in the annals of computer history. And whilst research into memory cells able to efficiently represent three distinct states has been relatively minimal, there have been some efforts in this area.

Particularly, researchers in Japan in the late 90's described the possibility of using a Josephson Junction to implement ternary logic. This could be achieved by circulating superconducting currents, either clockwise, counterclockwise, or off. They found that this gave the memory cells a "capability of high speed computation, low power consumption and very simple construction with less number of elements due to the ternary operation".

But, for the moment at least, I don't think that you'll be hearing much more about balanced ternary computers in the near future. Nor do I think DSSP is going to be the next big thing in programming language fanboyism. But I do believe that much wisdom can be sought by looking into the past ⁵.

Thanks for making it this far. Corrections and feedback is very welcome. You can also read more here, here and here. :)

This depends on how the machine in question represents numbers. Two's complement is a common notation that would allow one to represent -((2^n) / 2) to ((2^n) / 2) - 1 in n bits.
Although Setun was the first electronic device to operate on balanced ternary, it's worth mentioning that the idea of using balanced ternary in computing devices was first popularized over 100 years before. In 1840, Thomas Fowler built a calculating machine entirely from wood that operated on data in the balanced ternary notation.
A far more accurate description can be found on the Russian Computer Museum website.
Reference material for DSSP in English is not widely available so I'd like to provide a warning here that my knowledge is very limited and just may contain some guesswork.
My own contribution can be seen at computerpionee.rs.
Cover image, originally from the Moscow University Supercomputing Center, depicts one of the Setun machines in operation.

ComputerPionee.rs or: How six hours turned into six months

Andrew Buntine — Thu, 18 Aug 2016 00:00:00 +0000

Several months ago I made an off-the-cuff comment to my girlfriend along the lines of:

I want to be able to see a "cloud" of computer pioneers sized relative to their impact in a given sub-field of computer science

At the time it felt like a simple enough project. I'd just grab some pre-packaged data and whip up a little circle-packing algorithm. Or maybe I'd just utilise some existing framework for data visualisation like D3. It'll probably take a few hours... Right?

The first hurdle was the data. I could find many sources of data for achievements in the field, but nothing that was both consumable and sufficiently complete. Of the sources I found, all simply exclaimed that an achievement was exactly that: an achievement. None attempted to purvey the relative impact of each achievement - probably because of the inherent risk in doing so. And by risk I am referring to the fact that achievements can be difficult (or impossible) to truly compare to one another. Was Grace Hopper's FLOW-MATIC compiler more impactful than Robin Milner's ML? Would one have even happened without the other? Oh no, it's all getting too hard! In either case, I decided that I'd need to collect my own data in my own format and hope that the end result was both sufficiently fair and sufficiently accurate.

Three hours in and I was up to pioneer #4. Great, I though, this is going to take a while... Although, I must admit, part of me was silently kind of excited as I knew doing it manually would force me into actually learning a tonne of interesting things about the past achievements of the giants in my field. And as an amateur history buff, such a challenge is not entirely uninteresting to me!

But moving onto the actual circle-packing. And, in case you are unsure, when I say "circle packing" I mean (to quote wikipedia):

The arrangement of circles (of equal or varying sizes) on a given surface such that no overlapping occurs and so that all circles touch one another

Think something like this (spoiler alert!) or this. It turned out to be far more interesting (and challenging) than I had first imagined. I quickly decided against using an off-the-shelf data viz library as I wanted deep control over the eventual effect, didn't want to burden the user with unnecessary dependencies and, heck, I wanted to learn something interesting!

As it turns out, certain forms of circle packing are considered NP-hard. But considering we are dealing with a visualisation we are not trying to find the "best" pack possible, but simply a pack that is visually "good enough" to the Human observer. Lucky us! The eventual algorithm I came up with was one that performs successive refinements by applying an attractive force to each circle pulling them to the center point of the canvas, which is then slightly over-powered by a detractive force when two circles collide. The exact amount of refinement passes we perform is a function of the number of circles we are packing. And to add padding of N pixels between each circle we simply pretend each circles radius is N/2 larger than it is in reality. An upside to this approach is that it makes animating the whole thing trivial; it's just a matter of repositioning every circle on each iteration of the algorithm.

As for tools I decided to keep everything simple. The website is implemented in TypeScript and Python. In place of a potentially gratuitous frontend framework I have a simple dispatch pattern (who I am sure the Gang Of Four has a nice name for which I've forgotten). State is handled by a simple dictionary of three items: tab, tags and operation . I did make use of the (very handy) Snap SVG library in order to wrap the physical generation of SVG elements at runtime. I'll leave my analysis of TypeScript as a viable language to another post.

During this project I realised just how much effort goes into the collection and curation of data. I must have spent at least 50 hours scouring the web for birth dates, suitable pictures and details of achievements. And then, of course, I was struggling with trying to "rank" achievements that I quite simply couldn't truly appreciate. For example, in 1971, Stephen Cook published a landmark paper that now-famously proposed the P vs. NP problem. This is still an unsolved problem in computer science. I know what this problem states as far as the practicing programmer needs to and I also know it is incredibly important. But without recent education in theoretical computer science it's somewhat difficult for me to feel confident in exclaiming just how important it is to the field. Hopefully over time others will help me correct some of my mistakes in this area.

Because of the amount of time it took me to collate the data, I felt it was important that it was presented back to the community in a parsable format. And so I've packaged up the current data set in CSV format and hosted it on the official repository.

Anyway... Without further ado, I present: The Pioneers of Computer Science

Simple technique for car engine sounds in video games

Andrew Buntine — Sat, 28 May 2016 00:00:00 +0000

When I was working on Swervin' Mervin, there was one thing that constantly sat on my TODO list. It seemed simple enough, but getting rid of it proved a lot harder than I'd initially thought.

All I wanted to do was:

Generate engine sounds based on speed

I didn't know exactly how I was going to do it, but I knew a couple of things. For example, I knew that the effect didn't need to be perfect. It just needed to get the general idea into the players head and their imagination would do the rest. I also knew that I didn't want to fall too far into the rabbit hole of audio signal processing because I knew that once I climbed in, I'd either never come out or I'd come crawling out a defeated mess of a Human.

My first thought was to generate a sawtooth wave and set the frequency based on the players speed. I knew it could theoretically work because the sound programmer(s) on the classic arcade game Pole Position used a similar (but more advanced) technique. I setup a little prototype and it worked fine, but unfortunately, sounded almost nothing like a car engine. I've recreated the effect using the WebAudio API. I started dabbling with more advanced waveforms, but quickly realised I was slipping into the aforementioned rabbit hole of doom.

If I was releasing Swervin' Mervin in 1979, my half-baked attempt at waveform generation may have been sufficient. Alas...

My next idea was to find a soundbite of a running engine that I could seamlessly loop and simply shift the pitch and/or playback rate in response to the increase of the players speed. This idea fell to pieces when I realised that the sound libraries in Pygame simply didn't support seamless looping. There was a few milliseconds gap between each loop, which totally ruined the effect. But then I noticed in the documentation that I could queue sounds. Awesome! But, to my dismay, it simply didn't work. I tried everything I could, until I eventually found out that it kinda' just doesn't work. Damn...

I have recreated the car engine soundbite effect again using the (quite obviously) far more powerful WebAudio API. As for a simple engine effect, this one actually works pretty well for me...

I had one final idea that involved playing a soundbite of a car engine from idle to full acceleration and keeping track of the position we were at in the stream. If the player stopped accelerating, another soundbite that was a reverse of the first would start playing from the same position. Pretty simple, huh? Well, it turns out that Pygame doesn't provide us with an easy way of tracking the current position in a sound file! The WebAudio API does, of course...

These little experiments taught me an important lesson:

Be extra careful in the dependencies you choose!

I always knew that car engine sounds was something I wanted to add into Swervin' Mervin, but I was so confident in Pygame that I never really bothered to look into exactly how "powerful" it was. As it turns out, Pygame is all but dead and the last stable release was from over 6 years ago! Like all things in life - don't make decisions lightly... Happy coding.

The WebAudio API examples I mentioned here can also be found in my repository on Github.

Aha! Understanding lifetimes in Rust

Andrew Buntine — Sat, 02 Jan 2016 00:00:00 +0000

When I'm learning something complex, I often find myself waiting around for the Eureka effect (also known as the "Aha! moment"). Wikipedia defines the Eureka Effect as the "common human experience of suddenly understanding a previously incomprehensible problem or concept". This effect has been understood for thousands of years and was most-famously popularised by the great Greek mathematician Archimedes, who discovered how to measure the volume of an object whilst sitting in his bath.

In this post I'd like to share my own "Aha!" moments whilst grappling with lifetimes in Rust. I hope this helps some of you in your journey to the summit of Rust mountain.

I will assume that the readers already know some basic Rust and have read the documentation on ownership, lifetimes and borrowing.

A simple scenario

First, I want to propose a simple, suitably contrived snippet that requires us to stipulate a lifetime

// Our Person struct consists of a name and an optional reference to another Person.
#[derive(Debug, Eq, PartialEq)]
struct Person<'a> {
    name: &'static str,
    parent: Option<&'a Person<'a>>,
}

impl<'a> Person<'a> {
    fn new(name: &'static str, parent: Option<&'a Person<'a>>) -> Person<'a> {
        Person{name: name, parent: parent}
    }

    // Rust lets us elide the lifetime of &self here.
    fn parents_name(&self) -> Option<&'static str> {
        self.parent.and_then(|p| Some(p.name))    
    }
}

And some code that implements it:

let jane = Person::new("Jane", None);
let tom = Person::new("Tom", Some(&jane));

assert_eq!(tom.parent.unwrap().name, "Jane");
assert_eq!(tom.parents_name(), Some("Jane"));
assert_eq!(jane.parent, None);
assert_eq!(jane.parents_name(), None);

It's just a contract!

If we omit the lifetime specifiers in the previous example, we run into problems:

$ cargo test
  Compiling lifetimes v0.1.0 (file:///home/andrew/dev/rust/lifetimes)
  src/lib.rs:4:20: 4:27 error: missing lifetime specifier [E0106]
  src/lib.rs:4     parent: Option<&Person>,

Why is this? Well, it's because Rust needs a way to ensure that any borrowed Person does not outlive any other Person that is borrowing it. And therein lay my first "Aha!". When we specify a lifetime explicitly, we are simply entering a contract with the compiler guaranteeing that the given resource will be available for a certain scope. We are, in a sense, making a promise to the compiler. But we all know that promises can be broken and so Rust still makes all of the necessary checks for us.

We are not "creating" lifetimes. Nor are we telling Rust to allow a reference to exist somewhere that it shouldn't. We are just telling the compiler to complain if the calling code breaks the lifetime rules we've dictated.

What's in a name?

So exactly which scope is 'a? Is it referring to something in our Person type? No, 'a is defined by the calling code. Our type just dictates how long the value we are borrowing must live. Think of it like â€œfor any lifetime â€˜aâ€ rather than â€œthe particular lifetime called â€˜aâ€. The constructor demonstrates this pretty well. Look at the function signature:

fn new(name: &'static str, parent: Option<&'a Person<'a>>) -> Person<'a>

Here we are saying "new is a function that accepts a reference to a Person that must live for a lifetime we are going to call 'a' and it returns a new Person that contains a reference that must live for the same lifetime".

See that? We've stated at the syntactic level that the borrowed value (parent) will have the same lifetime as the thing that's borrowing it (the return value). In reality, the borrowed value may outlive its container. Our lifetime annotations just refer to the smallest lifetime for which the value must exist.

But why?

Why canâ€™t Rust just deal with this for us under the hood? And why canâ€™t Rust just ensure that an object lasts for exactly long as itâ€™s required by the program? Like, for example, an object that escapes its scope in Go will be heap-allocated and dealt with by the garbage collector at a later time. Well, thatâ€™s just it: such conveniences require a garbage collector, which would give our programs a performance hit.

Edit: As told by Reddit user andytoshi in this comment, Rust's ownership and borrowing systems do a lot more than simply "avoid garbage collection for performance reasons". They also, potentially more importantly, guarantee that any borrowed value you have access to will not change out from underneath you, even if you have a mutable reference to something. This gives our code a higher degree of reasonability and reduces overall complexity.

Rustâ€™s ownership and lifetime systems allow the compiler to validate the memory safety of our programs at compile-time. We donâ€™t have to delegate this task to a garbage collector at runtime such as in Ruby, Python, Go, etc nor do we have to manually allocate/deallocate memory ourselves such as in C. Infact, it's probably worth mentioning at this point that all this mumbo-jumbo about lifetimes is only of concern at compile-time. We are only referring to the lexical scopes that our borrows must exist in.

Rusts memory model is one of a few things that Rust refers to as a â€œzero-cost abstractionâ€, which brings me to my next Aha!

Zero-cost to our programs, not to us!

When I first started reading about some of these zero-cost abstractions, I wondered how it really applied here as the learning curve involved certainly didnâ€™t seem like a â€œzero-costâ€. But then I realised that when Rustaceans talk about zero-cost, they are talking solely about runtime performance of programs. Aha! Infact, in the case of lifetimes, Rust is actually removing the necessity of a garbage collector entirely by pushing additional rules onto the programmer. If your program compiles - itâ€™s almost certainly memory safe. These rules force us to think about the memory safety of the way we are programming upfront rather than in bug fixes months down the track. Yes, it's potentially more work, but it will undoubtedly save us headaches in the future!

One last point

Often when Iâ€™m dealing with simple structs I find myself wondering why Rust canâ€™t elide here like it does in certain function declarations. For example, when we say:

struct Person {
    name: &str,
    parent: Option<&Person>,
}

Canâ€™t Rust just translate it to this under the hood:

struct Person<'a> {
    name: &'a str,
    parent: Option<&'a Person<'a>>,
}

This point has caused some discussion in the Rust community. Some core contributors even believe that modern Rust should elide in this scenario.

Itâ€™s important to remember here that Rust often favours explicitness over succinctness. I think the example Yehuda Katz gives in his reply in the thread above is a good one. If we were able to omit the lifetime annotations then implementing code may end up looking something like this:

let people: Vec<Person> = â€¦;

We have suddenly lost the fact that Person contains a borrowed value. In complex, real-life software, this could lead to confusing bugs. But with that said, I imagine that there will be some movement in this area in the coming versions of Rust.

The End

That's all I have for the moment. I hope that something in here helped you on your journey. And if you've noticed that I've said something that's incorrect, please feel free to correct me. Thanks in advance!

Building a DIY arcade machine, part 1: Baby Steps

Andrew Buntine — Fri, 09 Oct 2015 00:00:00 +0000

In the previous post, I spoke about the motivation to build my own arcade machine. This time I'm going to start showing you how I actually did it.

My years of computer programming have taught me that the best way to start a large and daunting project is to take the overall problem and sub-divide it into lots of little problems. The idea is that you can abstract away the scariness of the overall goal and just focus on small tasks, whose sum will (well, may) reveal something awesome.

So I sat down and started jotting down all of the things I could think of. I ended up with a list that contained things like:

Find old monitor
Get old computer or Arduino
Work out how to get component speakers working
Buy thing to cut wood good (It's called a Jigsaw)
Buy lots of wood
Learn how to use jigsaw

And so on...

One of the tasks that seemed the scariest to me was "Work out how to wire Joysticks and buttons into computer". I had no idea how to do this, or even if I'd phrased the task correctly. And so I did what every good developer does: I started Googling. Pretty quickly I came across a company called Ultimarc who produce a product called the I-PAC (no relation to any Apple product).

The I-PAC is a PC interface to industry-standard arcade controls: A keyboard encoder. In other words, it translates button presses and joystick movements into key strokes on a normal PS/2 keyboard. And it's re-programmable so you can assign new keystroke outputs to each pin.

I excitedly bought the i-PAC along with 8 arcade pushbuttons and a joystick called the Mag-Stik Plus. While I waited for my package to arrive, I went to my local electronics shop and picked up some hook-up wire, crimp connectors, a small vice and a beginners electronics kit that had some wire cutters, a soldering iron, some solder and a bunch of heat shrinks in different sizes and colours. I was all set!

After some searching I'd found an old monitor (in my wardrobe), found an old computer (the old office file server, a Dell setup from the early naughties) and purchased a shitload of wood (or as I now knew to call it: MDF). I reformatted the old Dell computer and chucked Linux on there so I'd feel more comfortable. I also noticed that the machine had an OK old graphics card in there! I thought that I may be able to use it to get some more advanced arcade games working. So I decided to inspect it a bit more closely and swiftly snapped off a few diodes... Oh well, there goes that idea.

My apartment is small.

When my package from Ultimarc finally arrived, the first task I set myself was to wire up the joystick so that when I jiggled it my computer would receive the appropriate arrow key strokes. This, luckily, turned out to be pretty simple. The joystick had four microswitches on it; one for each direction. I needed to run a wire from each microswitch into the appropriate pin on the I-PAC. All four microswitches also needed to be grounded, which I accomplished by daisy-chaining them using a bunch of wires all connected together in the right way. The hardest part was getting the length of the wires correct. I must have gone through 20 meters of the stuff...

When I felt like I'd got everything hooked up correctly I plugged the I-PAC into my computer via USB and started gently moving the joystick head down. I expected that it would either do nothing or just simply blow up. But, no. It worked! It fucking worked!. I was so excited that I made my girlfriend watch me move around a text document using a Joystick that was flimsily attached via some probably-too-short hookup wire.

The joystick connected to the I-PAC. Dangerously close to the sink.

I'd hit my first milestone. In software, it's often essential to create what's known as a "proof-of-concept" before taking on a larger project. It's essentially a super scaled down version of the final product that demonstrates the essence of a potential solution. This probably-poorly wired joystick was my proof-of-concept. And so at this point I knew that I was going to succeed to some degree. I still had no real idea what success would look like, but I knew that, for better of worse, I'd produce something!

My next goal was to fully wire the player controls and mount them into their final resting place. But I'll talk about this more in the next part. Stay tuned.

Building a DIY arcade machine, part 0: Motivation

Andrew Buntine — Sat, 15 Aug 2015 00:00:00 +0000

I've always been a fan of retro video games. It takes me back to my childhood years when my brother, my sister and I would huddle on the floor in front of our tube television and play games on our Sega Master System console. It was one of the special edition versions that had Alex Kidd in Miracle World built-in. I remember that game in particular because it was both very difficult and also didn't ship with any notion of a "save game". So, naturally, we would just pause the game and leave the console running for weeks at a time.

Artists impression of my childhood.

Some time in the early nineties we got an upgrade when our Dad surprised us with a brand new Super Nintendo. I have fond memories of beating games like Donkey Kong Country II and Mega Man X. Each weekend, my brother and I would hire a mix of SNES games, Schwarzenegger films and WWF wrestling videos from the local video store. These were the pre-WWW days when the only indication of whether or not a game was any good was by looking for the "Highly Recommended!" sticker on the cover.

Sporadically, my siblings and I were also known to lose a dollar or two (hundred) at our local arcade that, funnily enough, had been fashioned out of an old Horse Stables building. We were particularly good on the 4-player X-Men game (a classic of the Beat 'em up genre) and a relatively unknown Japanese platformer named Toki. One of my good friends actually pissed his pants while playing Toki because he was up to a huge score and didn't trust me to take over for 30 seconds. Mum drove us home in shame that day...

The local arcade where Adam pissed his pants.

Fast-forward 20 years. I'm sitting at the dinner table with my girlfriend talking about an idea for a video game I want to make. It will be a racing game like the one I used to play in the arcade: Out Run. I knew that for full effect, the game would need to run in an actual arcade machine. My initial thoughts were that perhaps I could buy an existing arcade machine and replace some of the internal hardware. It turns out that this is a possibility because most arcade machines manufactured after the mid-eighties were standardised by JAMMA, which means that you can swap out an old circuit board for a modern motherboard and connect the two with a JAMMA-2-USB connector.

But, alas, finding an original arcade machine in good condition is relatively difficult. This may have something to do with the fact that the poor machines typically spent their first twenty years being beaten to shit by everyone that played them and then laid rotting due to exposure to the elements in some old guys shed. On top of this, an active collectors market has also pushed prices up steadily...

I was left with only one option: Build the damn thing myself!

In this blog series I will detail the trials and tribulations faced by me, Andrew Buntine, a man with no experience in cabinetry or electronics, in building my very own arcade machine. And, just to prove that I really did build it and it really does exist, I'd like to give you a sneak preview of the finished product:

Rounded corners are hard.

Stay tuned for the next part. In the mean time, maybe you could try to beat the hardest video game ever made, Battletoads, on a NES emulator? Good luck!!

ClojureScript saved me 100 hours

Andrew Buntine — Tue, 28 Jul 2015 00:00:00 +0000

Five years ago, I started tinkering with Clojure, a Lisp that runs atop the JVM. The language was still somewhat esoteric at the time. It was a Lisp, afterall!

Picking up Clojure wasn't too difficult because I'd already spent a few years playing around with Scheme. Generating fractals, Fibonacci sequences (of course) and working my way through the SICP and Simply Scheme textbooks. Infact, I think I may still be helping some first-year Comp Sci students at Berkeley University through my answers repository to the latter. Hey Berkeley, how about an honorary degree? Oh c'mon...

It was obvious from the get-go that Clojure was going to be a big deal. Although the language designer, Rich Hickey, decided to stick with S-Expressions, Clojure came with a much richer set of data structures than the humble linked list. And they were immutable and persistent, which gave them both the thread safety of immutability and the performance characteristics of mutability. The whole Java interop thing was also very important... It meant that Clojure programmers had access to the plethora of existing Java libraries.

The first non-trivial software I wrote in Clojure was a text-based game called Medieval Alien Massacre. It was inspired by an old game called Dunnet that, funnily enough, still ships as a default package with the Emacs editor today. The game was great fun to write, although I made the mistake of choosing a title and publishing the game before I'd written the story. The finished product did not involve any massacres and did not occur in the middle ages. It did, however, contain aliens so I wasn't completely wrong!

But, more importantly, sharing the game with my non-techy friends was kind of difficult as it required them to have Java installed and run it in a shell. I decided that I would (one day) rewrite the game in Javascript so that I could utilise the browser. As far as ease-of-distribution goes, it's difficult to beat Javascript.

And so sat my game. Incomplete and unknown. Alas, such is the blight of the the computer programmer... Until, that is, a friend mentioned to me that a project called ClojureScript was gaining some popularity. ClojureScript is a Clojure to Javascript compiler, which meant, atleast theoretically, I could directly compile Medieval Alien Massacre to Javascript and save myself the hassle of doing it manually!

I knew it wouldn't "just work". I was using Java's threading library to suspend execution, doing user IO from the terminal, etc. And so I started through the code, line by line, flagging everything that I thought might not compile. The process turned out to be relatively simple. ClojureScript swaps out Java interop for Javascript interop and so, for example:

(. Thread sleep 10)

was simply replaced with:

(.setTimeout js/window f 10)

I replaced all IO with a simple HTML input wrapped in a form with a submit event attached to it. I'd say about 85% of the core codebase stayed exactly the same. The language parsing didn't change at all!

In total, the process took me three quiet evenings after work. I also took the chance to give the game a more appropriate name: Moon Dweller. At a guess, I reckon I would have spent atleast 100 hours writing my own version in Javascript.

Oh, and guess what?! You can play it right now directly in your browser!

PLAY MOON DWELLER NOW

Happy hacking, people.