Dan Q

Tag: programming languages

Smug Interview Moment

I’ve been in a lot of interviews over the last two or three weeks. But there’s a moment that stands out and that I’ll remember forever as the most-smug I’ve ever felt during an interview.

Close-up of part of a letter, the visible part of which reads: Dear Dan, We are pleased to offer you a position as Senior Softwa... / and reporting to the Company's Manager, Software E... / (the "Commencement Date"). You will receive an... / By accepting this offer you warrant and agree...
There’ll soon be news to share about what I’m going to be doing with the second half of this year…

This particular interview included a mixture of technical and non-technical questions, but a particular technical question stood out for reasons that will rapidly become apparent. It went kind-of like this:

Interviewer: How would you go about designing a backend cache that retains in memory some number of most-recently-accessed items?

Dan: It sounds like you’re talking about an LRU cache. Coincidentally, I implemented exactly that just the other week, for fun, in two of this role’s preferred programming languages (and four other languages). I wrote a blog post about my design choices: specifically, why I opted for a hashmap for quick reads and a doubly-linked-list for constant-time writes. I’m sending you the links to it now: may I talk you through the diagrams?

Interviewer:

'Excuse me' GIF reaction. A white man blinks and looks surprised.

That’s probably the most-overconfident thing I’ve said at an interview since before I started at the Bodleian, 13 years ago. In the interview for that position I spent some time explaining that for the role they were recruiting for they were asking the wrong questions! I provided some better questions that I felt they should ask to maximise their chance of getting the best candidate… and then answered them, effectively helping to write my own interview.

Anyway: even ignoring my cockiness, my interview the other week was informative and enjoyable throughout, and I’m pleased that I’ll soon be working alongside some of the people that I met: they seem smart, and driven, and focussed, and it looks like the kind of environment in which I could do well.

But more on that later.

× ×

Article posted at UTC on .

1 comment

Werewolves and Wanderer

This post is also available as a video. If you'd prefer to watch/listen to me talk about this topic, give it a look.

This blog post is also available as a video. Would you prefer to watch/listen to me tell you about the video game that had the biggest impact on my life?

Of all of the videogames I’ve ever played, perhaps the one that’s had the biggest impact on my life1 was: Werewolves and (the) Wanderer.2

This simple text-based adventure was originally written by Tim Hartnell for use in his 1983 book Creating Adventure Games on your Computer. At the time, it was common for computing books and magazines to come with printed copies of program source code which you’d need to re-type on your own computer, printing being significantly many orders of magnitude cheaper than computer media.3

Front cover of The Amazing Amstrad Omnibus, by Martin Fairbanks, with its bright yellow text on a red background.
Werewolves and Wanderer was adapted for the Amstrad CPC4 by Martin Fairbanks and published in The Amazing Amstrad Omnibus (1985), which is where I first discovered it.
When I first came across the source code to Werewolves, I’d already begun my journey into computer programming. This started alongside my mother and later – when her quantity of free time was not able to keep up with my level of enthusiasm – by myself.

I’d been working my way through the operating manual for our microcomputer, trying to understand it all.5

Scan of a ring-bound page from a technical manual. The page describes the use of the "INPUT" command, saying "This command is used to let the computer know that it is expecting something to be typed in, for example, the answer to a question". The page goes on to provide a code example of a program which requests the user's age and then says "you look younger than [age] years old.", substituting in their age. The page then explains how it was the use of a variable that allowed this transaction to occur.
The ring-bound 445-page A4 doorstep of a book quickly became adorned with my pencilled-in notes, the way a microcomputer manual ought to be. It’s strange to recall that there was a time that beginner programmers still needed to be reminded to press [ENTER] at the end of each line.
And even though I’d typed-in dozens of programs before, both larger and smaller, it was Werewolves that finally helped so many key concepts “click” for me.

In particular, I found myself comparing Werewolves to my first attempt at a text-based adventure. Using what little I’d grokked of programming so far, I’d put together a series of passages (blocks of PRINT statements6) with choices (INPUT statements) that sent the player elsewhere in the story (using, of course, the long-considered-harmful GOTO statement), Choose-Your-Own-Adventure style.

Werewolves was… better.

Photograph of Dan in his mid-teens, with shoulder-length bleached-blonde hair and wearing a t-shirt with a picture of a snarling wolf, sits in front of a running PC (with its beige case open) on which an external modem is precariously balanced.
By the time I was the model of a teenage hacker, I’d been writing software for years. Most of it terrible.

Werewolves and Wanderer was my first lesson in how to structure a program.

Let’s take a look at a couple of segments of code that help illustrate what I mean (here’s the full code, if you’re interested): 

10 REM WEREWOLVES AND WANDERER

20 GOSUB 2600:REM INTIALISE
30 GOSUB 160
40 IF RO<>11 THEN 30

50 PEN 1:SOUND 5,100:PRINT:PRINT "YOU'VE DONE IT!!!":GOSUB 3520:SOUND 5,80:PRINT "THAT WAS THE EXIT FROM THE CASTLE!":SOUND 5,200
60 GOSUB 3520
70 PRINT:PRINT "YOU HAVE SUCCEEDED, ";N$;"!":SOUND 5,100
80 PRINT:PRINT "YOU MANAGED TO GET OUT OF THE CASTLE"
90 GOSUB 3520
100 PRINT:PRINT "WELL DONE!"
110 GOSUB 3520:SOUND 5,80
120 PRINT:PRINT "YOUR SCORE IS";
130 PRINT 3*TALLY+5*STRENGTH+2*WEALTH+FOOD+30*MK:FOR J=1 TO 10:SOUND 5,RND*100+10:NEXT J
140 PRINT:PRINT:PRINT:END

...

2600 REM INTIALISE
2610 MODE 1:BORDER 1:INK 0,1:INK 1,24:INK 2,26:INK 3,18:PAPER 0:PEN 2 
2620 RANDOMIZE TIME
2630 WEALTH=75:FOOD=0
2640 STRENGTH=100
2650 TALLY=0
2660 MK=0:REM NO. OF MONSTERS KILLED

...

3510 REM DELAY LOOP
3520 FOR T=1 TO 900:NEXT T
3530 RETURN
Locomotive BASIC had mandatory line numbering. The spacing and gaps (...) have been added for readability/your convenience.

What’s interesting about the code above? Well…

  • The code for “what to do when you win the game” is very near the top. “Winning” is the default state. The rest of the adventure exists to obstruct that. In a language with enforced line numbering and no screen editor7, it makes sense to put fixed-length code at the top… saving space for the adventure to grow below.
  • Two subroutines are called (the GOSUB statements):
    • The first sets up the game state: initialising the screen (2610), the RNG (2620), and player characteristics (2630 – 2660). This also makes it easy to call it again (e.g. if the player is given the option to “start over”). This subroutine goes on to set up the adventure map (more on that later).
    • The second starts on line 160: this is the “main game” logic. After it runs, each time, line 40 checks IF RO<>11 THEN 30. This tests whether the player’s location (RO) is room 11: if so, they’ve exited the castle and won the adventure. Otherwise, flow returns to line 30 and the “main game” subroutine happens again. This broken-out loop improving the readability and maintainability of the code.8
  • A common subroutine is the “delay loop” (line 3520). It just counts to 900! On a known (slow) processor of fixed speed, this is a simpler way to put a delay in than relying on a real-time clock.

The game setup gets more interesting still when it comes to setting up the adventure map. Here’s how it looks: 

2680 REM SET UP CASTLE
2690 DIM A(19,7):CHECKSUM=0
2700 FOR B=1 TO 19
2710   FOR C=1 TO 7
2720     READ A(B,C):CHECKSUM=CHECKSUM+A(B,C)
2730   NEXT C:NEXT B
2740 IF CHECKSUM<>355 THEN PRINT "ERROR IN ROOM DATA":END

...

2840 REM ALLOT TREASURE
2850 FOR J=1 TO 7
2860   M=INT(RND*19)+1
2870   IF M=6 OR M=11 OR A(M,7)<>0 THEN 2860
2880   A(M,7)=INT(RND*100)+100
2890 NEXT J

2910 REM ALLOT MONSTERS
2920 FOR J=1 TO 6
2930   M=INT(RND*18)+1
2940   IF M=6 OR M=11 OR A(M,7)<>0 THEN 2930
2950   A(M,7)=-J
2960 NEXT J
2970 A(4,7)=100+INT(RND*100)
2980 A(16,7)=100+INT(RND*100)

...

3310 DATA   0,  2,  0,  0,  0,  0,  0
3320 DATA   1,  3,  3,  0,  0,  0,  0
3330 DATA   2,  0,  5,  2,  0,  0,  0
3340 DATA   0,  5,  0,  0,  0,  0,  0
3350 DATA   4,  0,  0,  3, 15, 13,  0
3360 DATA   0,  0,  1,  0,  0,  0,  0
3370 DATA   0,  8,  0,  0,  0,  0,  0
3380 DATA   7, 10,  0,  0,  0,  0,  0
3390 DATA   0, 19,  0,  8,  0,  8,  0
3400 DATA   8,  0, 11,  0,  0,  0,  0
3410 DATA   0,  0, 10,  0,  0,  0,  0
3420 DATA   0,  0,  0, 13,  0,  0,  0
3430 DATA   0,  0, 12,  0,  5,  0,  0
3440 DATA   0, 15, 17,  0,  0,  0,  0
3450 DATA  14,  0,  0,  0,  0,  5,  0
3460 DATA  17,  0, 19,  0,  0,  0,  0
3470 DATA  18, 16,  0, 14,  0,  0,  0
3480 DATA   0, 17,  0,  0,  0,  0,  0
3490 DATA   9,  0, 16,  0,  0,  0,  0
Again, I’ve tweaked this code to improve readability, including adding indention on the loops, “modern-style”, and spacing to make the DATA statements form a “table”.

What’s this code doing?

  • Line 2690 defines an array (DIM) with two dimensions9 (19 by 7). This will store room data, an approach that allows code to be shared between all rooms: much cleaner than my first attempt at an adventure with each room having its own INPUT handler.
  • The two-level loop on lines 2700 through 2730 populates the room data from the DATA blocks. Nowadays you’d probably put that data in a separate file (probably JSON!). Each “row” represents a room, 1 to 19. Each “column” represents the room you end up at if you travel in a given direction: North, South, East, West, Up, or Down. The seventh column – always zero – represents whether a monster (negative number) or treasure (positive number) is found in that room. This column perhaps needn’t have been included: I imagine it’s a holdover from some previous version in which the locations of some or all of the treasures or monsters were hard-coded.
  • The loop beginning on line 2850 selects seven rooms and adds a random amount of treasure to each. The loop beginning on line 2920 places each of six monsters (numbered -1 through -6) in randomly-selected rooms. In both cases, the start and finish rooms, and any room with a treasure or monster, is ineligible. When my 8-year-old self finally deciphered what was going on I was awestruck at this simple approach to making the game dynamic.
  • Rooms 4 and 16 always receive treasure (lines 2970 – 2980), replacing any treasure or monster already there: the Private Meeting Room (always worth a diversion!) and the Treasury, respectively.
  • Curiously, room 9 (the lift) defines three exits, even though it’s impossible to take an action in this location: the player teleports to room 10 on arrival! Again, I assume this is vestigal code from an earlier implementation.
  • The “checksum” that’s tested on line 2740 is cute, and a younger me appreciated deciphering it. I’m not convinced it’s necessary (it sums all of the values in the DATA statements and expects 355 to limit tampering) though, or even useful: it certainly makes it harder to modify the rooms, which may undermine the code’s value as a teaching aid!
Map showing the layout of the castle in video game "Werewolves and the Wanderer". Entering from outside the castle, to the West, the player must progress through the ground floor, up the stairwell in the Inner Hallway, into the Lift, and then East to the exit, but there are several opportunities to diverge from this path and e.g. explore the dungeons or various dead ends on the ground or first floors.
By the time I was 10, I knew this map so well that I could draw it perfectly from memory. I almost managed the same today, aged 42. That memory’s buried deep!

Something you might notice is missing is the room descriptions. Arrays in this language are strictly typed: this array can only contain integers and not strings. But there are other reasons: line length limitations would have required trimming some of the longer descriptions. Also, many rooms have dynamic content, usually based on random numbers, which would be challenging to implement in this way.

As a child, I did once try to refactor the code so that an eighth column of data specified the line number to which control should pass to display the room description. That’s a bit of a no-no from a “mixing data and logic” perspective, but a cool example of metaprogramming before I even knew it! This didn’t work, though: it turns out you can’t pass a variable to a Locomotive BASIC GOTO or GOSUB. Boo!10

An experimental program being run that attempts to GOSUB a variable, failing with a syntax error on the relevant line.
In hindsight, I could have tested the functionality before I refactored with a very simple program, but I was only around 10 or 11 and still had lots to learn!

Werewolves and Wanderer has many faults11. But I’m clearly not the only developer whose early skills were honed and improved by this game, or who hold a special place in their heart for it. Just while writing this post, I discovered:

A decade or so later, I’d be taking my first steps as a professional software engineer. A couple more decades later, I’m still doing it.

And perhaps that adventure -the one that’s occupied my entire adult life – was facilitated by this text-based one from the 1980s.

Footnotes

1 The game that had the biggest impact on my life, it might surprise you to hear, is not among the “top ten videogames that stole my life” that I wrote about almost exactly 16 years ago nor the follow-up list I published in its incomplete form three years later. Turns out that time and impact are not interchangable. Who knew?

2 The game is variously known as Werewolves and Wanderer, Werewolves and Wanderers, or Werewolves and the Wanderer. Or, on any system I’ve been on, WERE.BAS, WEREWOLF.BAS, or WEREWOLV.BAS, thanks to the CPC’s eight-point-three filename limit.

3 Additionally, it was thought that having to undertake the (painstakingly tiresome) process of manually re-entering the source code for a program might help teach you a little about the code and how it worked, although this depended very much on how readable the code and its comments were. Tragically, the more comprehensible some code is, the more long-winded the re-entry process.

4 The CPC’s got a fascinating history in its own right, but you can read that any time.

5 One of my favourite features of home microcomputers was that seconds after you turned them on, you could start programming. Your prompt was an interface to a programming language. That magic had begun to fade by the time DOS came to dominate (sure, you can program using batch files, but they’re neither as elegant nor sophisticated as any BASIC dialect) and was completely lost by the era of booting directly into graphical operating systems. One of my favourite features about the Web is that it gives you some of that magic back again: thanks to the debugger in a modern browser, you can “tinker” with other people’s code once more, right from the same tool you load up every time. (Unfortunately, mobile devices – which have fast become the dominant way for people to use the Internet – have reversed this trend again. Try to View Source on your mobile – if you don’t already know how, it’s not an easy job!)

6 In particular, one frustration I remember from my first text-based adventure was that I’d been unable to work around Locomotive BASIC’s lack of string escape sequences – not that I yet knew what such a thing would be called – in order to put quote marks inside a quoted string!

7 “Screen editors” is what we initially called what you’d nowadays call a “text editor”: an application that lets you see a page of text at the same time, move your cursor about the place, and insert text wherever you feel like. It may also provide features like copy/paste and optional overtyping. Screen editors require more resources (and aren’t suitable for use on a teleprinter) compared to line editors, which preceeded them. Line editors only let you view and edit a single line at a time, which is how most of my first 6 years of programming was done.

8 In a modern programming language, you might use while true or similar for a main game loop, but this requires pushing the “outside” position to the stack… and early BASIC dialects often had strict (and small, by modern standards) limits on stack height that would have made this a risk compared to simply calling a subroutine from one line and then jumping back to that line on the next.

9 A neat feature of Locomotive BASIC over many contemporary and older BASIC dialects was its support for multidimensional arrays. A common feature in modern programming languages, this language feature used to be pretty rare, and programmers had to do bits of division and modulus arithmetic to work around the limitation… which, I can promise you, becomes painful the first time you have to deal with an array of three or more dimensions!

10 In reality, this was rather unnecessary, because the ON x GOSUB command can – and does, in this program – accept multiple jump points and selects the one referenced by the variable x.

11 Aside from those mentioned already, other clear faults include: impenetrable controls unless you’ve been given instuctions (although that was the way at the time); the shopkeeper will penalise you for trying to spend money you don’t have, except on food, presumably as a result of programmer laziness; you can lose your flaming torch, but you can’t buy spares in advance (you can pay for more, and you lose the money, but you don’t get a spare); some of the line spacing is sometimes a little wonky; combat’s a bit of a drag; lack of feedback to acknowledge the command you enterted and that it was successful; WHAT’S WITH ALL THE CAPITALS; some rooms don’t adequately describe their exits; the map is a bit linear; etc.

× × × × ×

Article posted at UTC on .

2 comments

The Ruby Story

This is a repost promoting content originally published elsewhere. See more things Dan's reposted.

…

By 2005, Ruby had become more popular, but it was still not a mainstream programming language. That changed with the release of Ruby on Rails. Ruby on Rails was the “killer app” for Ruby, and it did more than any other project to popularize Ruby. After the release of Ruby on Rails, interest in Ruby shot up across the board, as measured by the TIOBE language index:

It’s sometimes joked that the only programs anybody writes in Ruby are Ruby-on-Rails web applications. That makes it sound as if Ruby on Rails completely took over the Ruby community, which is only partly true. While Ruby has certainly come to be known as that language people write Rails apps in, Rails owes as much to Ruby as Ruby owes to Rails.

…

As an early adopter of Ruby (and Rails, when it later came along) I’ve always found that it brings me a level of joy I’ve experienced in very few other languages (and never as much). Every time I write Ruby, it takes me back to being six years old and hacking BASIC on my family’s microcomputer. Ruby, more than any other language I’ve come across, achieves the combination of instant satisfaction, minimal surprises, and solid-but-flexible object orientation. There’s so much to love about Ruby from a technical perspective, but for me: my love of it is emotional.

×

Repost posted at UTC on .

1 mention

Learning BASIC Like It’s 1983

This is a repost promoting content originally published elsewhere. See more things Dan's reposted.

…

C64 showing coloured barsNow, it’s Saturday morning and you’re eager to try out what you’ve learned. One of the first things the manual teaches you how to do is change the colors on the display. You follow the instructions, pressing CTRL-9 to enter reverse type mode and then holding down the space bar to create long lines. You swap between colors using CTRL-1 through CTRL-8, reveling in your sudden new power over the TV screen.

As cool as this is, you realize it doesn’t count as programming. In order to program the computer, you learned last night, you have to speak to it in a language called BASIC. To you, BASIC seems like something out of Star Wars, but BASIC is, by 1983, almost two decades old. It was invented by two Dartmouth professors, John Kemeny and Tom Kurtz, who wanted to make computing accessible to undergraduates in the social sciences and humanities. It was widely available on minicomputers and popular in college math classes. It then became standard on microcomputers after Bill Gates and Paul Allen wrote the MicroSoft BASIC interpreter for the Altair. But the manual doesn’t explain any of this and you won’t learn it for many years.

One of the first BASIC commands the manual suggests you try is the PRINT command. You type in PRINT "COMMODORE 64", slowly, since it takes you a while to find the quotation mark symbol above the 2 key. You hit RETURN and this time, instead of complaining, the computer does exactly what you told it to do and displays “COMMODORE 64” on the next line.

Now you try using the PRINT command on all sorts of different things: two numbers added together, two numbers multiplied together, even several decimal numbers. You stop typing out PRINT and instead use ?, since the manual has advised you that ? is an abbreviation for PRINT often used by expert programmers. You feel like an expert already, but then you remember that you haven’t even made it to chapter three, “Beginning BASIC Programming.”

…

I had an Amstrad CPC, myself, but I had friends with C64s and ZX Spectrums and – being slightly older than the author – I got the opportunity to experiment with BASIC programming on all of them (and went on to write all manner of tools on the CPC 464, 664, and 6128 models). I’m fortunate to have been able to get started in programming in an era when your first experience of writing code didn’t have to start with an examination of the different language choices nor downloading and installing some kind of interpreter or compiler: microcomputers used to just drop you at a prompt which was your interpreter! I think it’s a really valuable experience for a child to have.

×

Repost posted at UTC on .

1 mention

Ruby is still great! · Hendrik Mans

This is a repost promoting content originally published elsewhere. See more things Dan's reposted.

I realized something today:

Ruby is still great.

I’ve spent the last couple of weeks digging into some of the newer/fancier/shinier technologies that have been in the limelight of the development world lately – specifically Elixir, Phoenix and Elm – and while I’ve thoroughly enjoyed them all (and instantly had a bunch of fun ideas for things to build with them), I also realized once more how much I like Ruby, and what kind of project it’s still a great choice for…

Repost posted at UTC on .

1 mention

Writing A Calendar App In Rails Vs. PHP

Some time ago, I wrote a web-based calendar application in PHP, one of my favourite programming languages. This tool would produce a HTML tabular calendar for a four week period, Monday to Sunday, in which the current date (or a user-specified date) fell in the second week (so you’re looking at this week, last week, and two weeks in the future). The user-specified date, for various reasons, would be provided as the number of seconds since the epoch (1970). In addition, the user must be able to flick forwards and backwards through the calendar, “shifting” by one or four weeks each time.

Part of this algorithm, of course, was responsible for finding the timestamp (seconds since the epoch) of the beginning of “a week last Monday”, GMT. It went something like this (pseudocode):

1. Get a handle on the beginning of "today" with [specified time] modulus [number of seconds in day]
2. Go back in time a week by deducting [number of seconds in day] multiplied by [number of days in week] (you can see I'm a real programmer, because I set "number of days in week" as a constant, in case it ever gets changed)
3. Find the previous Monday by determining what day of the week this date is on (clever functions in PHP do this for me), then take [number of seconds in day] multiplied by [number of days after Monday we are] from this to get "a week last Monday"
4. Jump forwards or backwards a number of weeks specified by the user, if necessary. Easy.
5. Of course, this isn't perfect, because this "shift backwards a week and a few days" might have put us in to "last month", in which case the calendar needs to know to deduct one month and add [number of days in last month]
6. And if we just went "back in time" beyond January, we also need to deduct a year and add 11 months. Joy.

So; not the nicest bit of code in the world.

I’ve recently been learning to program in Ruby On Rails. Ruby is a comparatively young language which has become quite popular in Japan but has only had reasonable amounts of Westernised documentation for the last four years or so. I started looking into it early this year after reading an article that compared it to Python. Rails is a web application development framework that sits on top of Ruby and promises to be “quick and structured”, becoming the “best of both worlds” between web engineering in PHP (quick and sloppy) and in Java (slow and structured). Ruby is a properly object-oriented language – even your literals are objects – and Rails takes full advantage of this.

For example, here’s my interpretation in Rails of the same bit of code as above:

@week_last_monday = 7.days.ago.gmtime.monday + params[:weeks].to_i.weeks

An explanation:

  • @week_last_monday is just a variable in which I’m keeping the result of my operation.
  • 7.days might fool you. Yes, what I’m doing there is instantiating an Integer (7, actually a Fixint, but who cares), then calling the “days” function on it, which returns me an instance of Time which represents 7 days of time.
  • Calling the ago method on my Time object, which returns me another Time object, this time one which is equal to Time.now (the time right now) minus the amount of Time I already had (7 days). Basically, I now have a handle on “7 days ago”.
  • The only thing PHP had up on me here is that it’s gmdate() function had ensured I already had my date/time in GMT; here, I have to explicitly call gmtime to do the same thing.
  • And then I simply call monday on my resulting Time object to get a handle on the beginning of the previous Monday. That simple. 24 characters of fun.
  • + params[:weeks].to_i.weeks simply increments (or decrements) the Time I have by a number of weeks specified by the user (params[:weeks] gets the number of weeks specified, to_i converts it to an integer, and weeks, like days, creates a Time object from this. In Ruby, object definitions can even override operators like +, -, <, >, etc., as if they were methods (because they are), and so the author of the Time class made it simple to perform arithmetic upon times and dates.

This was the very point at which I feel in love with Ruby on Rails.

Article posted at UTC on .

5 comments