Damian Walker

Personal Web Pages

The Tiny BASIC Interpreter and Compiler Project

In August 2019 I put aside my work on the BOOPL compiler to pick up something simpler, as BOOPL is a bit complicated for a first compiler project. Tiny BASIC is a much easier introduction to compiler and interpreter implementation. Designed in 1975 for the minimal hardware that hobbyists had at the time, it has only eight statements, integer arithmetic, no arrays, no string handling beyond PRINTing hard-coded messages, and 26 variables (A-Z).

On this page I'll post about my progress in buliding the interpreter and compiler. Once it's finished, there will be download links, documentation and possibly even a library of programs and routines.

Euclidean Distance Subroutine

15 Oct: I found another interesting text-based game from the 1960s or 1970s called Snark. This is one of a trio of games that run on a 10x10 grid, the others being Hurkle and Mugwump. Information for Snark is more elusive than for the other two games, but I found a listing in the Treasure Trove of Games that I posted about previously. In Snark, your guess consists of a set of coordinates and a radius. The radius defines a ... (read more...)

Can the Wumpus Program be Simplified?

a-map-of-hunt-the-wumpus

13 Oct: Hunt the Wumpus was the first example program I developed for Tiny BASIC, and is still probably the most entertaining of all the samples. It suits the language very well, and is a great example of how the computed GOTO or GOSUB can make up for a lack of array functionality. But the computed GOTO in Wumpus is the very thing I've been thinking can be replaced with something more elegant. The caves in Wumpus are laid out ... (read more...)

Compilation, Bug Squashing & a Treasure Trove of Games

12 Oct: Development of the Tiny BASIC compiler has been that much of a whirlwind affair that I forgot about blogging over the past couple of weeks. The code generation proved to be easy enough, once I decided to use C as a target language. Many of the BASIC statements map 1-to-1 onto C equivalents. The only complications were dealing with computed GOTOs and GOSUBs, and providing a numeric input routine more robust than C's own scanf(). Once working, I ... (read more...)

BASIC Compilation Approaches!

21 Sep: I put together a to-do list for Tiny BASIC, and for the past few weeks I've been ticking off various refactoring tasks that I wanted to get out of the way before I start on code generation. The main two are now done: proper handling of end-of-line characters, and individual tokens for keywords. Until now, the tokeniser would recognise words and symbols, package them up as WORD or  SYMBOL and pass them to the parser. The parser would ... (read more...)

Tiny BASIC Road Block Cleared

14 Sep: It's been a while since I posted about the Tiny BASIC Interpreter and Compiler project. After I finished writing Intergalactic Space Rescue, I returned to the compiler itself and started on some tidying up. What was meant to be a simple task resulted in a bug that stalled me for two weeks. When I started on Tiny BASIC, I adopted and adapted the tokeniser I'd written for BOOPL. In BOOPL, end-of-line (EOL) characters aren't hugely significant. An EOL ... (read more...)

Tiny BASIC: Interpreter Largely Completed

27 Aug: A long holiday weekend, made longer for me because of health issues, means I've made a lot of progress on the Tiny BASIC Interpreter and Compiler project. After parsing and interpretation of LET and PRINT statements was complete, getting the rest of the commands implemented didn't take very long. And turning my attention to getting some of the games running has helped flush out some bugs - mainly in the games, rather than the interpreter. The games also highlighted ... (read more...)

Back to BASIC Games with Hammurabi

24 Aug: Having spent quite a bit of time on the Tiny BASIC implementation and its manual, I'm starting to miss writing the little games that it will eventually compile. I've already written some of the classic numerical games like hurkle, mugwump, wumpus and lunar lander. So it's time to tackle Hammurabi . Originally written in 1969 as "The Sumer Game", Hammurabi (often spelt Hamurabi ) is a game where you manage an ancient city state. Resources are people, land ... (read more...)

More Progress on Expressions

23 Aug: With the Great Refactoring out of the way, and with setting up a github repository for the project, I've been able to make some more concrete progress. Before all of this, Tiny BASIC was at a stage where it could parse line numbers, and simple LET statements of the form "LET variable = number ." Now I've expanded on that a bit. Expressions are still limited to a single term, and each term is still a single factor. ... (read more...)

Giving in to git

22 Aug: I gave up on using Dropbox for synchronising my Tiny BASIC project. It works really well for keeping files synced between my Intel-based Linux machines, so I can sit down at my laptop or desktop and have the latest edits available. But it's not very smooth on my Android device. Files need syncing one-by-one for offline editing, and I've found that even then it sometimes doesn't let me edit "offline" files when there's no network available. And it doesn't ... (read more...)

Writing the Tiny BASIC Manual

21 Aug: Lots of people have documented Tiny BASIC already, and in various forms. But if I eventually want to publish my own version, I want it to have its own documentation rather than referring from others. Two good reasons for reinventing this wheel stand out among others. Firstly, my own implementation has its own additional features. Comments, not present in the original Tiny BASIC specification, don't need much documenting. But the features surrounding omitted line numbers probably warrant some ... (read more...)

Tiny BASIC: The Great Refactoring

18 Aug: With further work on Tiny BASIC I managed to get the parser to recognise simple LET statements in the form: LET X=5 It doesn't properly understand expressions yet, so as far as the parser is concerned, an expression for now is just a number. Despite this, I did implement the logic that an expression is split into terms, which are split into factors, as fits the original specification. And at this point, I noticed that the parser ... (read more...)

An Improved Random Number Generator

17 Aug: I don't know where I went wrong, but my attempt to adapt the random number generator I found ended up as complete nonsense. Once my expression was simplified, I ended up dividing and multiplying by the same number, so that only rounding or overflow errors would produce a number different from the last. So I scrapped the subroutine I'd written and went for a simple approach that I can understand. The idea of most pseudorandom number generators is ... (read more...)

I Love Finite State Machines!

16 Aug: I learned about Finite State Machines over twenty years ago and was captivated by them. I've used them in all kinds of projects, from game logic to more serious things.  I used them to control the enemies in  Ossuary , my simple ZX Spectrum roguelike, and for simple tokenisation in projects like BOOPL and Tiny BASIC. The idea, if you've not used them before, is that at any time you're in a particular state. Depending on what your ... (read more...)

Debugging the Tiny BASIC Games

15 Aug: I finally got around to downloading an existing Tiny BASIC interpreter. Tom Pittman rewrote his Tiny BASIC interpreter in C for 21st century enthusiasts. This single C source file should compile on just about any operating system, and is a nice little no-frills no-nonsense implementation. Though Pittman's Tiny BASIC has some extensions (REM lines, and some rudimentary PRINT output formatting), it should run programs for the original Tiny BASIC specification without change. It needs line numbers, but the ... (read more...)

Adventures in AWK: a Tiny BASIC Conversion Script

14 Aug: I've finally found the time to settle down and re-learn AWK . After getting fed up of manually numbering the lines of my Tiny BASIC programs, I decided it was time to automate the process. So I've written a quick-and-dirty AWK script to read through a file, strip out the comment lines, and add line numbers to the remaining lines that lack them. The program will start at line 1, and increment the line numbers by 1. If ... (read more...)

And Another Tiny BASIC Game: Mugwump

13 Aug: As I said when I implemented  Hunt the Hurkle , it would be trivial to convert it to play the game of Mugwump too. The only difference between the games is what gets reported when you guess the position of the creature wrongly. In  Hurkle you get the direction it lies in relative to your guess; in  Mugwump you get the distance. It took about fifteen minutes to change the  Hurkle code to  Mugwump , and that includes ... (read more...)

Syntax Highlighting for Tiny BASIC

syntax-highlighting-in-tiny-basic

12 Aug: I spent quite a bit of time preparing a GTKSourceView language definition file for Tiny BASIC. It's not perfect, but it recognises all the core commands, comments, output strings and numbers. It allows me to see syntax highlighting in GEdit and Mousepad, two editors I use regularly. Other editors probably support GTKSourceView, but I don't know what they are. Just download the GTKSourceView Language Definition for Tiny BASIC and stick it in your GTKSourceView directory, wherever that is ... (read more...)

Hunt the Hurkle: Another Tiny BASIC game

11 Aug: It looks like I jumped in at the deep end with Hunt the Wumpus . Simple as it is, when I chose it as a sub-project I hadn't realised that it's very much more complex than Hunt the Hurkle . It's taken me barely half an hour to develop a  Hunt the Hurkle game, producing versions for both a modern compiler and the original interpreter. The entire program, stripped of comments, weighs in at 34 lines instead of the ... (read more...)

Progress on Wumpus!

hunt-the-wumpus-program-listing

10 Aug: Over the past few days I've managed to complete my Hunt the Wumpus implementation in Tiny BASIC. Programming in Tiny BASIC for me feels like running a marathon or completing a gruelling assault course - painful, but satisfying and in a strange way enjoyable. I started out by assuming optional line numbers, and those not limited to a maximum of 255. I'd also included comments and blank lines for readability. After that I manually "renumbered" the program so ... (read more...)

My Tiny BASIC Implementation

9 Aug: I've fleshed out some of the details of my Tiny BASIC implementation plan. Although I want to stick to the original specification, with no arrays, string handling, functions or other fripperies, there are some additional features I want to include to make programming in Tiny BASIC less painful. 1. The original interpreter had no REM (comment) or blank line support. I'd like to add these as an option that can be switched off for full compatibility checking. I ... (read more...)

Hunt the Wumpus in Tiny BASIC

hunt-the-wumpus

8 Aug: Since I started researching Tiny BASIC, I have found that program examples aren't as plentiful as I'd hoped. Most of the examples I have found use one of the expansions to the language, and require such things as a random number function (RND) or array handling. So it looks like I'll have to generate some project myself. Naturally, it will be some kind of game - it's not as if you can do anything much more useful in Tiny ... (read more...)

How Many Years? An Update

1 Aug: The last time I wrote a blog entry on my compiler project must have been a few years ago. I've worked on it on and off over that time. I decided on a name (BOOPL - Basic Object Orented Programming Language), prepared some documentation and with the help of the  Modern Compiler Design book, I wrote the tokeniser. Since then I also bought a very old but very cheap copy of the "Dragon Book",  Compilers: Principles, Techniques, and ... (read more...)