Author Archives: Toni

Great Retro Computing Podcast

As is painfully apparent by my projects/blog posts/hobbies, I’m a huge retro computing fan. As such, I find it interesting to hear about others’ experiences with retro hardware – what they have in their collection, forgotten tidbits about these computers, things currently going on in the community, etc.

A fantastic podcast I’ve been listening to for a couple months now and really digging is The Retrobits Podcast.

There have been 116 shows or so, all covering a variety of different machines and topics. If you’re a classic computer fan like me, you should check it out – the host, Earl Evans, seems like a nice guy and does a good job with presenting the info in a clear and entertaining manner. Plus he’s a Commodore fan so bonus points there.

So load up your iPod or Smart Phone and give it a listen on your way into work, it definitely makes my morning commute more enjoyable.

Upcoming This Week (PSX64 and Gruepal)

Just a heads up, I’ve been off the radar the last week with Christmas stuff going on, but I’m gearing back up to get some work done and tutorials out.

By the end of the week I should have two things ready to go –

1. Gruepal is up and running on another (faster) server. It’s shared webspace but the processor is a hell of a lot faster. If you are interested in helping test out some interactive fiction, shoot me a comment/message and I’ll send you back a username and password for when the site is ready.

2. I’m going to be adding some Paypal cart functionality to purchase a PSX64 on the Synthetic Dreams site. After sales at the TPUG convention, I have about 15 in stock. Once those 15 go I’ll make another batch.

Plus some other random goodness. Hope everyone had a good holiday!

An Introduction to Recursion

I remember the first time I formally encountered recursion – it was sophomore year of high school and I was watching as my CS teacher, Mr. Kendall Chun, was explaining how instead of using loops, a function could repeatedly perform an action by calling itself. The concept at the time just completely blew me away. It seemed to me, like I think it does to a number of people when they first learn about it, almost magic. I used it on more of a faith basis until I became more comfortable with it – and now, like any programmer, it is a standard part of my arsenal.

What is Recursion?

While recursion is a powerful technique, there is definitely nothing mystic about it. Simply put, recursion is when a function uses itself in it’s own definition. It can be a little easier to demonstrate by showing an example.

Non-Recursive Function

First off, remember that a function is a dependence between two values – or in plain terms, it’s a “machine” where input goes into it, and output comes out. Usually that output is generated by doing something to the input.

Take f(x) = x+3. This is a simple function that says whatever I put in, I get that plus 3 out – so if I put 7 in, I get a 10 out. f(7) = 7+3 = 10. No biggie, the function is defined in terms of x – we put a 7 in for x, we got a 10 out – no recursion yet.

Recursive Function

The most classic example of a recursive function is the factorial function. For those unfamiliar, the factorial function multiplies all integers less than or equal to itself, and is represented by an exclamation mark. So 5!, or 5 factorial, is equal to 5 * 4 * 3 * 2 * 1, or 120.

Why is this recursive? Check it out:

  • 5! = 5 * 4 * 3 * 2 * 1
  • 4! = 4 * 3 * 2 * 1
  • 3! = 3 * 2 * 1
  • 2! = 2 * 1
  • 1! = 1

So I’ve listed the factorials of each of these numbers out, so what? Well, if 4! = 4 * 3 * 2 * 1, then we could say:

  • 5! = 5 * 4!
  • 4! = 4 * 3!
  • 3! = 3 * 2!
  • 2! = 2 * 1!

As can be seen, any factorial is the number going into it times the factorial of one less that number. This means that factorial uses itself as its definition –

f(x) = x * f(x-1)

Factorial is the number going into it (variable x) times the factorial of the number minus 1. So factorial of 5, or f(5), is 5 * f(4). What’s f(4)? 4 * f(3). f(3) = 3 * f(2), and f(2) = 2 * f(1).

The Base Case

The issue is that for recursion to be useful, it has to STOP somewhere. In the factorial example, nothing stops it. We would say f(1) = 1 * f(0), f(0) = 0 * f(-1), f(-1) = -1 * f(-2), ad infinitum. Endless loops are no fun (unless the basis of annoying pranks), so we need a way of saying STOP! This is where the “Base Case” comes in. It is simply a point during execution, or in the definition of the function, that says “no more calling yourself, stop the looping madness”.

In the case of factorial, it’s f(0). f(0) = 1. Period. It doesn’t involve itself any longer, it just returns 1 – it’s a static value, an axiom, a solid rock, where the buck stops. Every recursive function needs a base case.

Full Execution

So the full definition of our factorial function is

f(0) = 1
f(x) = x * f(x – 1)

That means, if we call f with 0, we get 1, otherwise we perform the second operation. Let’s try it out with 4. We should get 4 * 3 * 2 * 1 = 24.

  • f(4) = 4 * f(3)
  • f(3) = 3 * f(2)
  • f(2) = 2 * f(1)
  • f(1) = 1 * f(0)
  • f(0) = 1

Now we know what each function returns, we can fill in the unknown values

  • f(1) = 1 * f(0) = 1 * 1 = 1
  • f(2) = 2 * f(1) = 2 * 1 = 2
  • f(3) = 3 * f(2) = 3 * 2 = 6
  • f(4) = 4 * f(3) = 4 * 6 = 24

It worked! And is very easy to implement in whatever programming language you happen to be using. Once you become comfortable using recursion, you’ll find it’s useful all over the place, because the world around us uses recursion constantly – it is a large part of math and our Universe.

Other Fun Examples

Looking for some more examples of recursion?

  • The Fibonacci Numbers – 0, 1, 1, 2, 3, 5, 8, 13, 21, etc. Each number is defined by adding the two numbers before it – so f(x) = f(x-1) + f(x-2). Double recursion – it makes use of itself twice! Our base cases are f(0) = 0 and f(1) = 1.
  • Any Geometric Series – The powers of 2 for example – 1, 2, 4, 8, 16, 32, 64, 128, 256. Each number is the previous number times 2. We could define this using exponents, but let’s do it with recursion! f(x) = 2 * f(x-1). Base case f(0) = 1.

Recursion rocks, so try finding some situations where loops are used that you could use recursion instead – it’s a lot more fun!

Gruepal – Version 4 Progress

Pretty much all the code I had before is now version 4 compliant. All the opcodes that deal with objects and their properties are now fully v1-8 compliant. What I’m mostly doing now is dealing with the screen manipulation that is common to version 4 and higher z-machines. Earlier games were written to pretty much print to the screen in a continuous fashion, whereas 4 and above could split the screen into two windows, print in column/row format, adjust height, font style, etc.

Implementing Multiple Windows

I’ve beefed up the output buffer quite a lot – instead of just being a place to dump text that’s shown on the screen, its now sectioned into multiple areas, such as the status bar for v1-3 games, or windows 0-7 for v4+ games. Each buffer has a raw area the game writes to, and a render area that combines the raw text with CSS code derived from style data from the game to be shown on the browser.

Gruepal can now handle screen differentiation between v1-3 and 4, handle multiple windows on the screen (both splitting and joining), clearing certain windows, and space-based positioning (which a lot of games use). A Mind Forever Voyaging is looking better and better, the next two steps are keeping track of where the screen goes into reverse mode and rendering that via css, then taking care of positioning when position opcodes are used.

More Website Cleanup

I’m becoming more and more active on this blog – I get quite a bit of enjoyment from doing it. I hope you guys enjoy reading it too. Along with the more frequent posting, I want to ramp up putting some more tutorials on here, but I wanted to make things a little more user friendly first.

Visuals

I made the margins slightly larger and made the text a big larger as well – it’s not a huge difference, but it does make reading articles a little easier. Alongside getting rid of the large left-hand ad last week, I think this has helped a lot.

Recent Posts

I also redid the recent posts list a bit. It used to list 3 over in the side bar – now it lists 5 on the main page, with an easy link that gives an abbreviated view of all posts, paginated. This also allowed me to move categories up in the side bar and organize them a bit better.

Feel free to shoot me a note if there’s anything else you’d like to see on the site. Thanks!

Spotlight: Alan Turing

Hanging on the wall of my cubicle at work, I have quite a number of geek related items, from web comics involving SQL jokes to a detailed mechanical diagram of K-9 from Doctor Who. Always in my field of vision, though, are some small photos of my computer science heroes. It’s not surprising that many non-geeks haven’t heard of these people – but it is sad. Most people know media stars like Tom Cruise, Eminem, and Michael Jordan, who are rightfully talented in their fields – but mention John von Neumann, Max Planck, or Kurt Gödel, and most won’t have heard of them. This is a shame, because it is the mathematicians, scientists, and engineers of history who have made many things we now enjoy possible. Given that we live in a place that gives an average salary of 2.7 million dollars to baseball players, it’s nice to at least recognize the people that make an incalculable impact on life.

The Man, The Legend

One of these people, regarded as the father of Computer Science, is one of my biggest heroes, and goes by the name Alan Turing. Born in 1912, Turing started life off in a world that had never seen a finished computer. The field of mathematical logic was new and fresh, with the work of mathematicians like Boole, De Morgan, Peano, and Hilbert (among others) paving the way for computation theory and algorithms.

Alan Turing WWII Work

Turing made contribution after contribution not only in this new field of Computer Science, but also to the world as a whole. During World War II he was a cryptanalyst, designing a device and doing work that would decipher encoded German communications, giving the Allies a key advantage.

Artificial Intelligence

Turing also had a keen interest in the ideas of computation and intelligence, and how the two related, ideas that would later found the area known as Artificial Intelligence. He developed the Turing Test which addresses, at its roots, that there is no distinction between intelligence and something that acts truly intelligent. It was a concept that is still not even truly accepted today by all; an effort in logic to dispel the idea that intelligence is somehow ineffable.

The Turing Machine

From pattern work with the mathematics of biology, to theory of computation, Turing gave more and more to the community. One of his biggest contributions (and my favorite part of his work), an idea that continues to pervade every inch of a computer from hardware to operating system to software, from a word processor to a video game emulator, is that of the Turing Machine. Some (like myself) would go so far as to say it pervades every aspect of the Universe.

More on This Concept

To give some background, the idea of a Turing Machine is a simple machine that can perform algorithms to compute a value. The idea of a Universal Turing Machine is one that can compute any Turing Machine, and hence anything computable, including OTHER Universal Turing Machines. This is what a computer is – it is a device that can, given enough time, compute anything that can be computed. Not only that, but since computers are themselves computable (i.e. computers work algorithmically), any computer can emulate any OTHER computer. This is proven all the time, from video game emulators, to Java, .NET, and virtual machines (including my Gruepal project!). The Turing machine speaks to the heart of Functionalism, which is that it is not the “stuff” that matters, but the function the “stuff” performs. E.g. you can make a calculator out of silicon chips, steam through pipes and valves, or virtually on a computer (e.g. doesn’t physically exist at all), but it still adds 2+7 the same, as long as the functionality is intact.

I won’t jump too far off course from Turing, but I can’t stress how important this concept is, and one that I guarantee we will continue to discover more about in the decades to come. In a sense, the human brain is very much a Universal Turing Machine (though fallible), as you could, mentally or on paper, emulate any computer or machine algorithmically – as many programmers do constantly every day in their line of work. And with the Universe giving rise to everything, all Turing machines, and having a tendency to recurse, there is a good chance (some will say), that this whole great ball of wax is just one big Universal Turing Machine recursing over and over into other Universal Turing Machines. It is one of the reasons I tell people that Computer Science has more to do with the Universe itself than any pile of microchips.

The Final Years

Regardless of how deep or far the philosophy goes though, there can be no denying the role Alan Turing played in the mathematics behind computability and computers. His absolutely life changing work was rewarded by his government giving him the choice of imprisonment or estrogen injections when it was found out he was homosexual. Homosexuality was still illegal in the UK at this time, and though he had literally helped save the world only a few years before, this meant nothing in the light that he was attracted to men. After the effects of the hormones and ostracism from the life he knew, he committed suicide by eating an cyanide laced apple.

I remember the first time reading the details about Turing’s death, and how just pissed off and horrified I was about the whole thing. You’d think times had changed since Galileo, but they were still going strong in 1952. It is a relief, though, that since then he has become such an honored person, with a prestigious award and many memorials named after him.

Respect

So here’s a most humble, awe-filled, respectful shout out to my hero, Alan Mathison Turing. I would be proud to be 1/100th the Computer Scientist he was.

Gruepal – Version Support and Pre-Alpha Testing

Public Testing Soon!

Things are moving along, I haven’t found any further bugs when testing out version 3 games (I’m sure they’re there but things are looking fairly stable), so I’m calling Gruepal ready for people to pound away on for v1-3 games. Since my rented server is starting to get a little too big of a load, I found some cheap web hosting with fast processors and setup an account tonight. I will be installing Drupal on there and putting Gruepal builds on it for people to play around with within the next week.

With things looking good for versions 1-3, I wanted to start fleshing out v4-8 support before adding too many extra features – I want to ensure that the core of the engine is done, I may have to make a change that would affect extras and cause a lot of code rewrite.

Versions 4 and Up

I’ve starting working primarily on supporting version 4 stuff, but in the process it will fill in a lot of functionality required for versions 5-8 as well. I’m doing my version 4 work with “A Mind Forever Voyaging” – for two reasons. First, it’s a classic that I’ve heard great things about, and I haven’t had a chance to play it yet, so this will give me an opportunity. Also, it uses a lot of screen manipulation which I need to handle better anyway, so it’s a good game to work with.

Screen Manipulation

There are a lot of decisions I’ve had to make as far as screen manipulation since there isn’t really a screen in the classic sense – the game isn’t directly controlling what the user sees, its rendering to an output buffer which is printed in the user’s browser. Really, through the use of CSS it’s not too bad, I can recreate things – but I gave the user some functionality such as scrolling through the entire history of their game which isn’t part of the z-machine spec, so I need to balance that with things that don’t fit with that, e.g. a clear screen. Does it clear the whole history, or just put a lot of whitespace in so the screen being viewed is cleared, but the user can still scroll up? I’m thinking I’ll probably clear the whole buffer, as there may be times when the game simulates a control panel of some type and it wouldn’t make any sense to have previous renders of what the control panel had been showing in the output buffer.

Anyway, I’ve implemented enough version 4 code that A Mind Forever Voyaging doesn’t crash off the bat – it prints a lot of what it’s supposed to, but it definitely isn’t formatting the text right yet, and some of the text is wrong. My favorite is, instead of saying

“You have entered Communications Mode”

it says

“You have entered dinner.”

Definitely a lookup issue there. 😉

I will post the info here when the testing area is ready to go for the v1-3 code though.

Gruepal – Another bug squashed

Fixed the Moonmist bug that printed out a strange character when putting your favorite color in. This ended up actually being a biggie with the way I was performing the SREAD opcode, which is the standard opcode that reads in text and does all the parsing/lexical table construction.

There are two buffers you have to fill in that the game expects in a certain format – the text buffer and the parse buffer. The text buffer basically contains a copy of what the user typed, and the parse buffer contains an entry for each word and symbol parsed, entries consisting of what index in the dictionary the word is, how long the word was, and where in the text buffer the word appears.

I had actually made two errors in SREAD which kind of canceled each other out, only not canceling each other out in Moonmist during the favorite color question. One, I had read version 5+ of the SREAD specification by accident, and was off by 1 byte in where I was writing to in the buffer. Everything still worked, because I was also off by one byte in my position calculations within the parse buffer. I fixed both those issues, and everything worked, including the Moonmist issue.

I’ve run into a few more infinite loop bugs in Moonmist, but most of the bugs are ironed out now. After I kill the Moonmist bugs, I’m going to try a few more games, and if things go smoothly, I want to start filling out the code for versions 4-8 of the zmachines, then get Gruepal online for some alpha/beta testing.

Strong Bad’s Cool Game for Attractive People

I make no secret that I am a huge fan of Telltale Games, as can be seen in my first post on what a top notch gaming company they are. I urge you to check them out if you haven’t heard of them before or seen their creations.

I just got through playing the final installment in the Strong Bad’s Cool Game for Attractive People series – “8-bit is Enough” – and I’ve got to say, they’ve yet to let me down – the game was simply awesome. I won’t give anything away, but as you Homestar Runner fans know, the Brothers Chaps have an affinity for the 8 bit world, both poking fun and reliving the joy that was gaming in the 80s. All that is brought to new light in “8-bit is Enough”, with the 8-bit world bleeding and mixing into the game world of Strong Bad. For a retro geek like me, it was fun, hilarious, and just a great time to play. The puzzles were pretty good, not great, but on par with previous Strong Bad adventures – but the retro feel of the game was the real champion here – cavorting and battling against pixelated baddies was very true to the spirit of Homestar Runner and ripe with in-jokes of our arcade past.

SBCG4AP Poopsmith Retro

Featuring everyone’s favorite Trogdor, this one was definitely my favorite in the series, with the first episode being a close second. If you’re into adventure games, retrogaming goodness, the Homestar Runner gang, or just having fun, I definitely suggest playing the entire series, it’s a lot of fun at a very reasonable price.

Links to check out:

Telltale Games
Homestar Runner

Removed some ads

I took the large ad in the upper left hand corner of my posts out. It irritated me looking at it whenever I’d read any posts, so I imagine it probably did the same for other people too. Maybe it generated a few clicks, but it’s not worth it, my primary concern is that people are actually able to read the posts easily.