Phillip Trelford's Array

Microsoft’s Small Basic is a minimal implementation of the BASIC programming language using only 14 keywords. It’s aimed at beginners with a very simple development environment and library. My kids have enjoyed playing with it particularly the Turtle API which are reminiscent of Logo. Small Basic programs can be run locally, online via Silverlight or migrated to full fat Visual Basic .Net.

I’m quite interested in building Domain Specific Languages (DSLs), including embedded DSLs, parsers and compilers. For a short exercise/experiment I wanted to recreate a simple imperative language and Small Basic looked like a fun option.

Abstract Syntax Tree

I started by sketching out an abstract syntax tree (AST) for the language which describes the values, expressions and instructions.

F# discriminated union’s make light work of this:

/// Small Basic instruction
type instruction =
    | Assign of assign
    | SetAt of location * expr
    | PropertySet of string * string * expr
    | Action of invoke
    | For of assign * expr * expr
    | EndFor
    | If of expr
    | ElseIf of expr
    | Else
    | EndIf
    | While of expr
    | EndWhile
    | Sub of identifier
    | EndSub
    | GoSub of identifier
    | Label of label
    | Goto of label

A parser or embedded DSL can be used to generate an AST for a program. The AST can then be evaluated by an interpreter, or transformed by a compiler to processor instructions, byte code or even another language.

Embedded DSL

To test the AST I built a small embedded DSL using custom operators and functions:

let I x = Literal(Int(x))
let (!) (name:string) = Var(name)
let FOR(var:identifier, from:expr, ``to``:expr) = 

    For(Set(var, from), ``to``, I(1))
let PRINT x = 
    let writeLine = typeof<Console>.GetMethod("WriteLine",[|typeof<obj>|])
    Action(Call(writeLine, [|x|]))

This can be used to specify a Small Basic program.

let program =
    [|
        FOR("A", I(1), I(100))
        PRINT(!"A")
        ENDFOR        
    |]

The program AST can then be evaluated in F# interactive:

val program : instruction [] =
  [|For (Set ("A",Literal (Int 1)),Literal (Int 100),Literal (Int 1));
    Action (Call (Void WriteLine(System.Object),[|Var "A"|])); 

    EndFor|]

Defining the embedded DSL in F# only took minutes using the interactive REPL environment and looks quite close to the target language.

Interpreter

Programs can now be run by evaluating the AST using an interpreter. The interpreter merely steps through each instruction using pattern matching:

let run (program:instruction[]) =
    /// ... 

    /// Instruction step
    let step () =
        let instruction = program.[!pi]
        match instruction with
        | Action(call) -> invoke state call |> ignore
        | For((Set(identifier,expr) as from), target, step) ->
            assign from
            let index = findIndex (!pi+1) (isFor,isEndFor) EndFor
            forLoops.[index] <- (!pi, identifier, target, step)
            if toInt(variables.[identifier]) > toInt(eval target) 
            then pi := index
        | EndFor ->
            let start, identifier, target, step = forLoops.[!pi]
            let x = variables.[identifier]
            variables.[identifier] <- arithmetic x Add (eval step)
            if toInt(variables.[identifier]) <= toInt(eval target) 
            then pi := start
    while !pi < program.Length do step (); incr pi

Scriptable Small Basic

The AST, embedded DSL and interpreter are available as an F# snippet that you can run in F# interactive or build as an executable. The script includes a Small Basic FizzBuzz sample.