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…

Seq vs Streams

Last week Gian Ntzik gave a great talk at the F#unctional Londoners meetup on the Nessos Streams library. It’s a lightweight F#/C# library for efficient functional-style pipelines on streams of data.

The main difference between LINQ/Seq and Streams is that LINQ is about composing external iterators (Enumerable/Enumerator) and Streams is based on the continuation-passing-style composition of internal iterators, which makes optimisations such as loop fusion easier.

The slides (using FsReveal) and samples are available on Gian’s github repository.

Simple Streams

Gian started the session by live coding a simple implementation of streams in about 20 minutes:

type Stream<'T> = ('T -> unit) -> unit

let inline ofArray (source: 'T[]) : Stream<'T> =
   fun k ->
      let mutable i = 0
      while i < source.Length do
            k source.[i]
            i <- i + 1          

let inline filter (predicate: 'T -> bool) (stream: Stream<'T>) : Stream<'T> =
   fun k -> stream (fun value -> if predicate value then k value)

let inline map (mapF: 'T -> 'U) (stream: Stream<'T>) : Stream<'U> =
   fun k -> stream (fun v -> k (mapF v))

let inline iter (iterF: 'T -> unit) (stream: Stream<'T>) : unit =
   stream (fun v -> iterF v)

let inline toArray (stream: Stream<'T>) : 'T [] =
   let acc = new List<'T>()
   stream |> iter (fun v -> acc.Add(v))
   acc.ToArray()

let inline fold (foldF:'State->'T->'State) (state:'State) (stream:Stream<'T>) =
   let acc = ref state
   stream (fun v -> acc := foldF !acc v)
   !acc

let inline reduce (reducer: ^T -> ^T -> ^T) (stream: Stream< ^T >) : ^T
      when ^T : (static member Zero : ^T) =
   fold (fun s v -> reducer s v) LanguagePrimitives.GenericZero stream

let inline sum (stream : Stream< ^T>) : ^T
      when ^T : (static member Zero : ^T)
      and ^T : (static member (+) : ^T * ^T -> ^T) =
   fold (+) LanguagePrimitives.GenericZero stream

and as you can see only about 40 lines of code.

Sequential Performance

Just with this simple implementation, Gian was able to demonstrate a significant performance improvement over F#’s built-in Seq module for a simple pipeline:

#time // Turns on timing in F# Interactive

let data = [|1L..1000000L|]

let seqValue = 
   data
   |> Seq.filter (fun x -> x%2L = 0L)
   |> Seq.map (fun x -> x * x)
   |> Seq.sum
// Real: 00:00:00.252, CPU: 00:00:00.234, GC gen0: 0, gen1: 0, gen2: 0

let streamValue =
   data
   |> Stream.ofArray
   |> Stream.filter (fun x -> x%2L = 0L)
   |> Stream.map (fun x -> x * x)
   |> Stream.sum
// Real: 00:00:00.119, CPU: 00:00:00.125, GC gen0: 0, gen1: 0, gen2: 0

Note for operations over arrays, the F# Array module would be more appropriate choice and is slightly faster:

let arrayValue =
   data
   |> Array.filter (fun x -> x%2L = 0L)
   |> Array.map (fun x -> x * x)
   |> Array.sum
// Real: 00:00:00.094, CPU: 00:00:00.093, GC gen0: 0, gen1: 0, gen2: 0

Also LINQ does quite well here as it has a specialized overloads including one for summing over int64 values:

open System.Linq

let linqValue =   
   data
      .Where(fun x -> x%2L = 0L)
      .Select(fun x -> x * x)
      .Sum()
// Real: 00:00:00.058, CPU: 00:00:00.062, GC gen0: 0, gen1: 0, gen2: 0

However with F# Interactive running in 64-bit mode Streams take back the advantage (thanks to Nick Palladinos for the tip):

let streamValue =
   data
   |> Stream.ofArray
   |> Stream.filter (fun x -> x%2L = 0L)
   |> Stream.map (fun x -> x * x)
   |> Stream.sum
// Real: 00:00:00.033, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0

Looks like the 64-bit JIT is doing some black magic there.

Parallel Performance

Switching to the full Nessos Streams library, there’s support for parallel streams via the ParStream module:

let parsStreamValue =
   data
   |> ParStream.ofArray
   |> ParStream.filter (fun x -> x%2L = 0L)
   |> ParStream.map (fun x -> x + 1L)
   |> ParStream.sum
// Real: 00:00:00.069, CPU: 00:00:00.187, GC gen0: 0, gen1: 0, gen2: 0

which demonstrates a good performance increase with little effort.

For larger computes Nessos Streams supports cloud based parallel operations against Azure.

Overall Nessos Streams looks like a good alternative to the Seq module for functional pipelines.

Nessos LinqOptimzer

For further optimization Gian recommended the Nessos LinqOptimizer:

An automatic query optimizer-compiler for Sequential and Parallel LINQ. LinqOptimizer compiles declarative LINQ queries into fast loop-based imperative code. The compiled code has fewer virtual calls and heap allocations, better data locality and speedups of up to 15x

The benchmarks are impressive:

cs-ssq

Reactive Extensions (Rx)

One of the questions in the talk and on twitter later was, given Rx is also a push model, how does the performance compare:


Clearly the Nessos Streams library and Rx have different goals (data processing vs event processing), but I thought it would be interesting to compare them all the same:

open System.Reactive.Linq

let rxValue =
   data
      .ToObservable()
      .Where(fun x -> x%2L = 0L)
      .Select(fun x -> x * x)
      .Sum()      
      .ToEnumerable()
      |> Seq.head
// Real: 00:00:02.895, CPU: 00:00:02.843, GC gen0: 120, gen1: 0, gen2: 0

let streamValue =
   data
   |> Stream.ofArray
   |> Stream.filter (fun x -> x%2L = 0L)
   |> Stream.map (fun x -> x * x)
   |> Stream.sum
// Real: 00:00:00.130, CPU: 00:00:00.109, GC gen0: 0, gen1: 0, gen2: 0

In this naive comparison you can see Nessos Streams is roughly 20 times faster than Rx.

Observable module

F# also has a built-in Observable module for operations over IObservable<T> (support for operations over events was added to F# back in 2006). Based on the claims on Rx performance made by Matt Podwysocki I was curious to see how it stacked up:

let obsValue =
   data
   |> Observable.ofSeq
   |> Observable.filter (fun x -> x%2L = 0L)
   |> Observable.map (fun x -> x * x)
   |> Observable.sum
   |> Observable.first
// Real: 00:00:00.479, CPU: 00:00:00.468, GC gen0: 18, gen1: 0, gen2: 0

As you can see Observable module comes off roughly 5 times faster.

Note: I had to add some simple combinators to make this work, you can see the full snippet here: http://fssnip.net/ow

Summary

Nessos Streams look like a promising direction for performance of functional pipelines, and for gaining raw imperative performance the Nessos LINQOptimizer is impressive.