Phillip Trelford's Array

POKE 36879,255

Small Basic on Mac & Linux

Microsoft’s Small Basic is a simple programming language and environment aimed at beginners.

It ships with an IDE for Windows, a commands line compiler and a small .Net library. Small Basic programs can also be run in the browser on Windows & Mac via SIlverlight.

The shipped .Net library for Small Basic targets WPF for graphics which is unfortunately not supported on Mono, which means Small Basic apps will not run directly on Mac or Linux.

To get Small Basic apps running from the command prompt on Mac and Linux all that is needed is a new library is required without the WPF dependency.

Recently I knocked up such a library providing support for command line input and output, providing graphics is a work-in-progress.

But this does mean I can now write and run FizzBuzz, or even work through the majority of the Small Basic Tutorial, on Linux or Mac via Mono:

Small Basic on Mac

Combine this with my open source Small Basic compiler project (written in F#) and there’s now have a cross platform version of Small Basic :)

If you fancy having a play with an early version of the source download it here: http://trelford.com/SmallBasicLibrary2012.zip

Future work

I’m currently evaluating GtkSharp, OpenTK and WinForms as options for a cross platform version of the graphics library.

As well as the compiler, I’ve also written an interpreter for Small Basic which means it should be possible to edit and run programs on iOS and Android, but that’s another story…

Debugging Small Basic Apps in Visual Studio

Microsoft Small Basic ships with a custom IDE with syntax colouring and code completion but no debugger:

SmallBasic

There’s a good article by Nonki Takahashi on Microsoft Technet on How to debug Small Basic programs manually which boils down to:

  • trace with TextWindow.WriteLine
  • add conditional debug code with If debug Then …
  • promote your app to full VB.Net

Small Basic in Visual Studio

Last year, for fun, I wrote a custom Small Basic compiler with some extensions like functions with parameters and tuples and pattern matching.

I added debugger support recently so you can compile and debug Small Basic apps directly in Visual Studio:

SmallBasic Debug in VS2013

Setup Steps:

  • download and compile the custom Small Basic compiler
  • create a project to host your Small Basic file (.sb)
  • compile the app with the custom Small Basic Compiler
  • in the project properties Debug tab configure Start External Program

Implementation details

The Reflection.Emit library allows you to mark points in the emitted IL code with corresponding points in the source file using the MarkSequencePoint method. There’s a good guide from back in 2005 on Michael Stall’s blog: Debugging Dynamically Generated Code (Reflection.Emit)

Only a few changes to the compiler were required to provide Debugger support. First I augmented the parser, which uses FParsec, to produce line and column information for each statement. For this FParsec provides a handy getPosition function that returns the current position in the input stream. Then in the IL emit step I simply used MarkSequencePoint to annotate each statement.

Future work

It would also be nice to add syntax colouring for Small Basic within Visual Studio too. If anyone is interested in working with me on this, please get in touch Smile

I’m also now able to run Small Basic programs on Mac and Linux via Mono but that’s another post…

Finite State Machine Compiler

Yesterday I noticed a tweet recommending an “Uncle” Bob Martin video that is intended to “demystify compilers”. I haven’t seen the video (Episode 29, SMC Parser) as it’s behind a pay wall, but I did find a link on the page to a github repository with a hand rolled parser written in vanilla Java, plus a transformation step that compiles it out to either Java or C code.

cats and dogs

The parser implementation is quite involved with a number of files covering both lexing and parsing:

I found the Java code clean but a little hard to follow so tried to reverse engineer the state machine syntax off of a BNF (found in comments) and some examples (found in unit tests):

Actions: Turnstile
FSM: OneCoinTurnstile
Initial: Locked
{
Locked Coin Unlocked {alarmOff unlock}
Locked Pass Locked  alarmOn
Unlocked Coin Unlocked thankyou
Unlocked Pass Locked lock
}

It reminded me a little of the state machine sample in Martin Fowler’s Domain-Specific Language book, which I recreated in F# a few years back as both internal and external DSLs.

On the train home I thought it would be fun to knock up a parser for the state machine in F# using FParsec, a parser combinator library. Parser combinators mix the lexing and parsing stages, and make light work of parsing. One of the many things I like about FParsec is that you get pretty good error messages for free from the library.

Finite State Machine Parser

I used F#’s discriminated unions to describe the AST which quite closely resembles the core of Uncle Bob’s BNF:

type Name = string
type Event = Name
type State = Name
type Action = Name
type Transition = { OldState:State; Event:Event; NewState:State; Actions:Action list }
type Header = Header of Name * Name

The parser, using FParsec, turned out to be pretty short (less than 40 loc):

open FParsec

let pname = many1SatisfyL isLetter "name"

let pheader = pname .>> pstring ":" .>> spaces1 .>>. pname .>> spaces |>> Header

let pstate = pname .>> spaces1
let pevent = pname .>> spaces1
let paction = pname

let pactions = 
   paction |>> fun action -> [action]
   <|> between (pstring "{") (pstring "}") (many (paction .>> spaces))

let psubtransition =
   pipe3 pevent pstate pactions (fun ev ns act -> ev,ns,act)

let ptransition1 =
   pstate .>>. psubtransition
   |>> fun (os,(ev,ns,act)) -> [{OldState=os;Event=ev;NewState=ns;Actions=act}]

let ptransitionGroup =
   let psub = spaces >>. psubtransition .>> spaces
   pstate .>>. (between (pstring "{") (pstring "}") (many1 psub))
   |>> fun (os,subs) -> 
      [for (ev,ns,act) in subs -> {OldState=os;Event=ev;NewState=ns;Actions=act}]

let ptransitions =
   let ptrans = attempt ptransition1 <|> ptransitionGroup
   between (pstring "{") (pstring "}") (many (spaces >>. ptrans .>> spaces))
   |>> fun trans -> List.collect id trans

let pfsm =
   spaces >>. many pheader .>>. ptransitions .>> spaces

let parse code =
   match run pfsm code with
   | Success(result,_,_) -> result
   | Failure(msg,_,_) -> failwith msg

You can try the parser snippet out directly in F#’s interactive window.

Finite State Machine Compiler

I also found code for compiling out to Java and C, and ported the former:

let compile (headers,transitions) =
   let header name = 
      headers |> List.pick (function Header(key,value) when key = name -> Some value | _ -> None)
   let states = 
      transitions |> List.collect (fun trans -> [trans.OldState;trans.NewState]) |> Seq.distinct      
   let events =
      transitions |> List.map (fun trans -> trans.Event) |> Seq.distinct

   "package thePackage;\n" +
   (sprintf "public abstract class %s implements %s {\n" (header "FSM") (header "Actions")) +
   "\tpublic abstract void unhandledTransition(String state, String event);\n" +
   (sprintf "\tprivate enum State {%s}\n" (String.concat "," states)) +
   (sprintf "\tprivate enum Event {%s}\n" (String.concat "," events)) +
   (sprintf "\tprivate State state = State.%s;\n" (header "Initial")) +
   "\tprivate void setState(State s) {state = s;}\n" +
   "\tprivate void handleEvent(Event event) {\n" +
   "\t\tswitch(state) {\n" +
   (String.concat ""
      [for (oldState,ts) in transitions |> Seq.groupBy (fun t -> t.OldState) ->
         (sprintf "\t\t\tcase %s:\n" oldState) +
         "\t\t\t\tswitch(event) {\n" +
         (String.concat ""
            [for t in ts ->
               (sprintf "\t\t\t\t\tcase %s:\n" t.Event) +
               (sprintf "\t\t\t\t\t\tsetState(State.%s);\n" t.NewState)+
               (String.concat ""
                  [for a in t.Actions -> sprintf "\t\t\t\t\t\t%s();\n" a]
               ) +
               "\t\t\t\t\t\tbreak;\n"
            ]         
         ) +
         "\t\t\t\t\tdefault: unhandledTransition(state.name(), event.name()); break;\n" +
         "\t\t\t\t}\n" +
         "\t\t\t\tbreak;\n"
      ] 
   )+   
   "\t\t}\n" +
   "\t}\n" +   
   "}\n"

Again, and probably not surprisingly, this is shorter than Uncle Bob’s Java implementation.

And again, you can try the compiler snippet out in the F# interactive window.

Conclusion

Writing a parser using a parser combinator library (and F#) appears to be significantly easier and more succinct than writing a hand rolled parser (in Java).