Phillip Trelford's Array

POKE 36879,255

Basic Tuples & Pattern Matching

Over the last couple of weeks I’ve been building my own parser, interpreter and compiler for Small Basic, a dialect of BASIC with only 14 keywords aimed at beginners. Despite, or perhaps because of, Small Basic’s simplicity some really fun programs have been developed, from games like Tetris and 3D Maze to a parser for the language itself.

Small Basic provides primitive types for numbers, strings and associative arrays. There is no syntax provided for structures, but these can be easily modelled with the associative arrays. For example a 3D point can be constructed with named items or ordinals:

Named items Ordinals
Point["X"] = 1.0
Point["Y"] = 2.0
Point["Z"] = 3.0
Point[0] = 1.0
Point[1] = 2.0
Point[2] = 3.0

In languages like Erlang and Python this could be more concisely expressed as a tuple:

Erlang Python
Point = {1.0, 2.0, 3.0}
point = (1.0, 2.0, 3.0)

In fact sophisticated Erlang programs are built entirely from tuples and lists, there is no explicit class or inheritance syntax in the language. Messages can be easily expressed with tuples and behaviour via pattern matching.

Alan Kay, inventor of the Smalltalk language has said:

The notion of object oriented programming is completely misunderstood. It's not about objects and classes, it's all about messages.

In Erlang a hierarchy of shapes can simply be modelled using tuples with atoms for names:

Circle = { circle, 5.0 }
Square = { square, 7.0 }
Rectangle = { rectangle, 10.0, 5.0 }

The area of a shape can be expressed using pattern matching:

area(Shape) ->
  case Shape of
    { circle, R } -> pi() * R * R;
    { square, W } -> W * W;
    { rect, W, H } -> W * H

Select Case

The Visual Basic family’s Select Case functionality is quite rich. More so than the switch/case statements of the mainstream C dialects: Java, C# and C++, which only match literals.

In Visual Basic it is already possible to match values with literals, conditions or ranges:

Select Case agerange
  Case Is < 16
  Case 16 To 21
    MsgBox("Still Young")
  Case 50 To 64
    MsgBox("Start Lying")
  Case Is > 65
    MsgBox("Be Yourself") 
  Case Else
End Select

Given that Select Case in VB is already quite expressive, it feels support for tuples and pattern matching over them would feel quite natural in the language.

Extended Small Basic

To this end I have extended my Small Basic parser and compiler implementation with tuple and pattern matching support.


Inspiration for construction and deconstruction was taken from F# and Python:

F# Python
let person = ("Phil", 27)
let (name, age) = person
person = ("Phil", 27)
name, age = person

So that tuples use explicit parentheses in the extended Small Basic implementation:

Person = ("Phil", 27)
(Name, Age) = Person

Internally tuples are represented using Small Basic’s built-in associative arrays.

Pattern Matching

First I implemented VB’s Select Case statements, which is not hugely dissimilar to parsing and compiling Small Basic’s If/ElseIf/Else statements.

Then I extended Select Case to support matching tuples with similar functionality to F#:

F# Extended Small Basic
let xor x y =
  match (x,y) with
  | (1,1) -> 0
  | (1,0) -> 1
  | (0,1) -> 1
  | (0,0) -> 0
Function Xor(a,b)
  Select Case (a,b)
    Case (1,1)
      Xor = 0
    Case (1,0)
      Xor = 1
    Case (0,1)
      Xor = 1
    Case (0,0)
      Xor = 0

Constructing, deconstructing and matching nested tuples is also supported.


Putting it altogether, FizzBuzz can now be expressed in my extended Small Basic implementation with functions, tuples and pattern matching:

Function Mod(Dividend,Divisor)
  Mod = Dividend
  While Mod >= Divisor
    Mod = Mod - Divisor

Sub Echo(s)

For A = 1 To 100 ' Iterate from 1 to 100
  Select Case (Mod(A,3),Mod(A,5))
    Case (0,0)
    Case (0,_)
    Case (_,0)
    Case Else


Extending Small Basic with first class support for tuples was relatively easy, and I feel quite natural in the language. It provides object orientated programming without the need for a verbose class syntax. I think this is something that would probably work pretty well in other BASIC dialects including Visual Basic.

Source code is available on BitBucket:

Try 10 Programming Languages in 10 minutes

There are a lot of interesting programming languages out there, but downloading and setting up the environment can be very time consuming when you just want to try one out. The good news is that you can try out many languages in your browser straight away, often with tutorials which guide you through the basics.

Following the pattern of 7 languages in 7 weeks book, here’s a somewhat abridged version.

Dynamic Languages

Fed up of long compile times, want a lightweight environment for scripting? Dynamic languages could be your new friend.

Try Lua

Lua is a lightweight dynamic language with excellent coroutine support and a simple C API making it hugely popular in video gaming for scripting. Have fun with game engines like LÖVE and Marmalade Quick.

Try Clojure

Clojure is the brainchild of the hugely charismatic speaker Rich Hickey, it is a descendant of one of the earliest programming languages LISP. There’s a really rich community around Clojure, one of my favourite projects is Sam Aaron’s Overtone live coding audio environment.

Try R (quick registration required)

R is a free environment for statistical computing and graphics, with a huge range of user-submitted packages. Ever wondered how to draw an egg?

Functional Languages

Aspects of functional programming have permeated most mainstream languages from C++ to VB. However to really appreciate the expressiveness of the functional approach a functional-first language is required.

Try Erlang

Erlang is a really interesting language for building fault tolerant concurrent systems. It also has great pattern matching capabilities. It has many industrial applications and tools including the RabbitMQ messaging system and the distribute database Riak.

Try Haskell

Haskell is heavily based on the Miranda programming language which was taught in British universities in the 80s and 90s. Haskell added Monads and Type Classes, and is still taught in a few universities, it is also still quite popular in academic research.

Try OCaml

OCaml like Miranda is based on the ML programming language adding object-oriented constructs. F# is based on OCaml, there is even a compatibility mode. OCaml still has industrial application, for example at Jane Street Capital and XenSource.

Web Languages

There’s a plethora of languages that compile to JavaScript languages out there. Also worth a look are the new features in JavaScript itself, see Brendan Eich’s talk at Strangeloop last year on the The State of JavaScript. Here’s 3 *Script languages I find particularly interesting:


LiveScript is an indirect descendant of CoffeeScript with features to assist functional programming like pattern matching and function composition. Check out 10 LiveScript one liners to impress your friends.

Try Elm

Elm is a functional reactive language for creating highly interactive programs, including games. Reactive programming is an interesting direction and I think languages designed specifically for this are worth investigating.


Unfortunately there’s currently no online editor for this one, but there is a command line REPL. PogoScript is DSL friendly allowing white space in function names.

Esoteric Languages

Esoteric languages tend to be write-only, a bit like Perl but just for fun.

Try Brainfuck

Brainfuck is the Rubik’s cube of programming languages. I built the site last year with the interpreter written in plain old JavaScript, check out the fib sample.

Browser IDEs

With so many programming language experimentation environments available online, the next logical step is to host the IDE there. Imagine not having to wait 4 hours for Visual Studio to install.

Cloud 9 is an online environment for creating Node.js apps, pulling together sets of relevant packages. Tools like Sploder let you build games online.

The Try F# site offers arguably the most extensive online learning features of any language. Cloud Tsunami IDE also offers a rich online development experience for F#. In the near future CloudSharper will offer an online IDE experience for developing web applications with F# using WebSharper,

Scaling up

Once you’ve completed some basic tasks in a new language you’ll want to move on to slightly larger tasks. I like to use exercises from the coding Kata Catalogue like FizzBuzz, the Game of Life and Minesweeper.

Some people enjoy going through the Project Euler problems, others have their own hello world applications. For Martin Trojer it’s a Scheme interpreter and Luke Hoban often writes a Ray Tracer.

I’d also recommend joining a local meetup group. The London Scala meetup have a coding dojo every month and the F#unctional Londoners meetup have hands on session in the middle the month, the next one is on Machine Learning.

Programming language books that include questions at the end of sections are a good way to practice what you’ve learned but are few and far between. The recent Functional Programming with F# book is an excellent example of what can be done with questions at the end of each chapter.

While the basics of a language can be picked up in a few hours, expect it to take a few weeks before you’re productive and at least a few months before you start to gain mastery.

Want to write your own language? Pete Sestoft’s Programming Language Concepts book offers a good introduction to the subject.

Functional Fizz Buzz

Fizz-Buzz or Bizz Buzz is a word game, popularized by Jeff Atwood in the article:

Why Can’t Programmers… Program?

The game has been turned into a simple programming test:

Write a program that prints the numbers from 1 to 100. But for multiples of 3 print "Fizz" instead of the number and for the multiples of 5 print "Buzz". For numbers which are multiples of both 3 and 5 print "FizzBuzz".

If you’re involved in hiring programmers then the article is probably worth a read.

This kind of problem can be expressed very concisely in functional programming languages to the point where the code fits in a tweet.


Last month Calvin Bottoms posted an article describing and implementation of Fizz-Buzz in Haskell expressed in a mere 78 characters:

[max(show x)(concat[n|(f,n)<-[(3,"Fizz"),(5,"Buzz")],mod x f==0])|x<-[1..100]]

Higher order functions and list comprehensions (a feature taken from Miranda) make this very terse, but also a little impenetrable.


Rather more verbose (122 characters) but perhaps a little more readable:

for n in 1..100 do printfn "%s" <| match n%3, n%5 with 
0,0 -> "FizzBuzz" | 0,_ -> "Fizz" | _,0 -> "Buzz" | _,_ -> string n

Pattern matching makes the various states relatively obvious.


Martin Trojer sent over this quite elegant Clojure implementation via Twitter:

(map #(cond (zero? (mod % 15)) "FizzBuzz" (zero? (mod % 3)) "Fizz" 
(zero? (mod % 5)) "Buzz" :else %) (range 1 101))

Testing for “FizzBuzz” using modulus 15 helps reduce the character count.


I’ve been playing with Erlang recently and Fizz-Buzz is my new “Hello World” app. This was my first effort:

f(X)->Y=case{X rem 3,X rem 5}of{0,0}->fizzbuzz;{0,_}->fizz;{_,0}->buzz;
{_,_}->X end,io:format("~w~n",[Y]),f(X+1). 

Erlang doesn’t have a for loop construct built-in so I resorted to recursion instead.

That said you can achieve the same thing using the lists module seq and foreach functions:

lists:foreach(fun(X)->io:format("~w~n",[case{X rem 3,X rem 5}of{0,0}->fizzbuzz;
{0,_}->fizz;{_,0}->buzz;{_,_}->X end])end,lists:seq(1,100)).


Is Fizz-Buzz the new “Hello World”?

I think it might be, despite Jeff’s protestations, take a peek at Fizz-Buzz on Rosetta Code.