Phillip Trelford's Array

POKE 36879,255

Fun Basic Preview

Fun Basic is an extended clone of Microsoft’s Small Basic programming language that runs as an app in the Windows Store. The app provides a range of sample programs from simple turtle graphics through to video games and physics simulations. The samples have been selected from programs in the public domain created by the Small Basic community. Each sample is presented with it’s corresponding source code allowing you to edit the code and run the program.

FunBasic Entry Screenshot

The concept is that you can learn elements of programming by reading the provided programs and editing and enhancing them. The inspiration comes from the type-in programs circulated in computer magazines throughout the 80s, and through which I had some of my earliest forays into programming.

The editor on the other hand affords more modern conveniences including syntax colouring, code completion and tooltips over API calls.

FunBasic 1942 Screenshot

Why not head over to the Windows Store and try the preview (new features will be appearing weekly).

It’s free and there’s games to play! http://tinyurl.com/funbasic

Language resources

Fun Basic provides all the language features of Small Basic and it extends the language with parameters on subroutines. You can learn more about language features in the Small Basic Tutorial.

The app is currently a preview, in future releases extended support for function return values, tuples and pattern matching (using Select Case) will be enabled.

Technical bit

Fun Basic is an offshoot from an extended Small Basic Compiler project I wrote for fun in early 2014 while learning FParsec, a parser combinator libraryfor F#. You can learn more about that effort in my presentation at NDC London “Write Your Own Compiler in 24 Hours” and an interview on .Net Rocks on “Writing Compilers”.

My kids (8 & 12) have been enjoying programming and downloading apps from the Windows Store so last month I set out to cover both of these interests with a Store app version.

Interpreter

The Windows Store sandbox doesn’t support compilation within apps so the compiler was out. Fortunately I’d also knocked together an interpreter for Small Basic during early prototyping so I used this as a basis for the runtime. The interpreter simply pattern matches over the Abstract Syntax Tree (AST) generated by the parser, executing instructions and evaluating expressions.

Library

The next challenge was supporting Small Basic’s runtime library which provides simple graphics and text based operations. This had to be written from scratch as it needed to work against the Windows Store API and run in process with the app. All API calls are made asynchronously and I’ve employed separate canvases for the drawing, shapes and text layers. There’s also support for the Flickr API which unfortunately at the time of writing is broken in Small Basic.

image

Editor

The editor employs the ActiPro SyntaxEditor control to provide syntax colouring, code completion and tool tips. ActiPro’s Language Designer wizard meant I had syntax colouring set up in minutes, and it was relatively easy to set up the code completion and tooltips using my existing parser and AST. I’m planning to enable more of the SyntaxEditor’s features in future versions.

App

To build the app I used the Windows Store Grid App project template that’s built-in to Visual Studio. All that was needed was to customize the grid items with pictures and descriptions for the master view and add the editor and program panels to the detail view.

Logo

Special thanks to Sergey Tihon,, author of the excellent F# Weekly, for putting together a nice logo for the app!

Source Code

The source is open and available on BitBucket, see http://bitbucket.org/ptrelford/funbasic

If you delve in you’ll find a mixture of F#, C# and VB.Net. F# is used for the parser and interpreter, C# for interfaces and small imperative functions and VB.Net for gluing the app together.

Releases

I’m currently releasing new features weekly, let me know if there’s a feature you “must have” via Twitter @ptrelford :)

Find the last Sunday of each Month

Rosetta Code has a number of programming tasks with example solutions in multiple languages. One of those tasks is find the last Sunday of each month. Here’s a sample in C#:

DateTime date;
for (int i = 1; i <= 12; i++)
{
   date = new DateTime(year, i, DateTime.DaysInMonth(year, i), System.Globalization.CultureInfo.CurrentCulture.Calendar);
   while (date.DayOfWeek != DayOfWeek.Sunday)
   {
      date = date.AddDays(-1);
   }
   Console.WriteLine(date.ToString("yyyy-MM-dd"));
}

I thought it might be fun to write an F# version, code golf style, that fits in a tweet:


The general gist of that solution was to create a list of all days in each month in reverse order and find the first Sunday (which will be the last):

[for month in 1..12->
   [for day in System.DateTime.DaysInMonth(2014,month).. -1.. 1->
      System.DateTime(2014,month,day).DayOfWeek,(month,day)]
   |> Seq.find (fun (dayOfWeek,_) -> dayOfWeek = System.DayOfWeek.Sunday)
]

 

Enter Petricek

Then Tomas Petricek came up with a neat solution that had enough space left over to execute against @fsibot:


Tomas’s solution evaluates each day of the year, yielding the last Sundays as dates:

[for days in 0.0 .. 365.0 do 
   let day = System.DateTime(2014,1,1).AddDays(days) in 
   if int day.DayOfWeek = 0 && day.AddDays(7.).Month <> day.Month 
   then yield day
]

 

Wellum Reprise

Meanwhile Richard Wellum suggested an alternate solution in C#, which I was able to translate to standalone F# with space left over for a pretty print:


Richard's solution is to calculate the last day of the month, find the day of week and subtract that value to reach the Sunday. Here's a version with variable names:

[for month in 1..12->
   let lastDay = System.DateTime(2014,month,1).AddMonths(1).AddDays(-1.) in 
   lastDay.AddDays(-(lastDay.DayOfWeek|>int|>float)).ToString("m")
]

Conclusion

Finding the last Sunday of each month in a tweet now appears to be a solved problem :)

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.