Phillip Trelford's Array

POKE 36879,255

Parsing with SNOBOL

Just before Christmas I came across some Java source code by “Uncle” Bob Martin aimed at “demystifying compilers” which expends about 600 lines of code to parse the following simple finite state machine:

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

For fun I knocked up a broadly equivalent parser in F# using FParsec which was just under 40 lines of code, and posted the code on this blog.

The post generated some interest, and I even got a mention on Twitter from “Uncle” Bob himself:

I’d not seen SNOBOL before, but given Mr Martin’s recommendation I popped over to the SNOBOL page on WikiPedia and liked what I saw:

SNOBOL rivals APL for its distinctiveness in format and programming style, both being radically unlike more "standard" procedural languages such as BASIC, Fortran, or C.

SNOBOL first appeared in 1962 and appears to have been popular in US Universities as a text manipulation language in the 70s and 80s. The language supports pattern matching over text combined with assembler like control flow using labels and goto (like C#).

As a text manipulation language, SNOBOL code feels a little more readable than the new norm - regular expressions .

If you’d like to take it out for a spin there’s an open source SNOBOL IDE, with syntax colouring support, for Linux and Windows called TkS*LIDE.

SNOBOL Interpreter

Nowadays when I want to learn a new language I often start by implementing it, to this end over the course of about a week I built a SNOBOL interpreter with just enough functionality to run the samples on the Wikipedia page along with some more involved samples from other sources.

The SNOBOL interpreter is about 400 LOC and available as an F# Snippet.

Finite State Machine in SNOBOL

Armed with a basic knowledge of SNOBOL, I could now answer the question, is the implementation even smaller in SNOBOL.

The answer is a resounding yes, and here’s the 34 lines of SNOBOL code that proves it:

SNOBOL4 FSM

Disclaimer: unlike the FParsec version there’s no error handling/error messages and the FSM must be layed out in a specific format.

Conclusions

The SNOBOL finite state machine parser, like the FParsec based parser, fits on a page and is an order of magnitude shorter than the broadly equivalent clean Java implementation written by Uncle Bob Martin that aimed to demystify compiler writing.

Will I be switching from FParsec to SNOBOL for parsing? Probably not, FParsec is at least as expressive, provides pretty good error messages for free and runs on the CLR.

Special thanks to Uncle Bob Martin for the SNOBOL tip Smile

DDD East Anglia 2014

This Saturday saw the Developer Developer Developer! (DDD) East Anglia conference in Cambridge. DDD events are organized by the community for the community with the agenda for the day set through voting.

T-Shirts

The event marked a bit of a personal milestone for me, finally completing a set of DDD regional speaker T-Shirts, with a nice distinctive green for my local region. Way back in 2010 I chanced a first appearance at a DDD event with a short grok talk on BDD in the lunch break at DDD Reading. Since then I’ve had the pleasure of visiting and speaking in Glasgow, Belfast, Sunderland, Dundee and Bristol.

Talks

There were five F# related talks on the day, enough to fill an entire track:

Tomas kicked off the day, knocking up a simple e-mail validation library with tests using FsUnit and FsCheck. With the help of Project Scaffold, by the end of the presentation he’d generated a Nuget package, continuous build with Travis and Fake and HTML documentation using FSharp.Formatting.

Anthony’s SkyNet slides are already available on SlideShare:


ASP.Net was also a popular topic with a variety of talks including:

All your types are belong to us!

The title for this talk was borrowed from a slide in a talk given by Ross McKinlay which references the internet meme All your base are belong to us.

You can see a video of an earlier incarnation of the talk, which I presented at NorDevCon over on InfoQ, where they managed to capture me teapotting:

teapot

The talk demonstrates accessing a wide variety of data sources using F#’s powerful Type Provider mechanism.

The World at your fingertips

The FSharp.Data library, run by Tomas Petricek and Gustavo Guerra, provides a wide range of type providers giving typed data access to standards like CSV, JSON, XML, through to large data sources Freebase and the World Bank.

With a little help from FSharp.Charting and a simple custom operator based DSL it’s possible to view interesting statistics from the World Bank data with just a few key strokes:


The JSON and XML providers give easy typed access to most internet data, and there’s even a branch of FSharp.Data with an HTML type provider providing access to embedded tables.

Enterprise

The SQLProvider project provides type access with LINQ support to a wide variety of databases including MS SQL Server, PostgreSQL, Oracle, MySQL, ODBC and MS Access.

FSharp.Management gives typed access to the file system, registry, WMI and Powershell.

Orchestration

The R Type Provider lets you access and orchestrate R packages inside F#.

With FCell you can easily access F# functions from Excel and Excel ranges from F#, either from Visual Studio or embedded in Excel itself.

The Hadoop provider allows typed access to data available on Hive instances.

There’s also type providers for MATLAB, Java and TypeScript.

Fun

Type Providers can also be fun, I’ve particularly enjoyed Ross’s Choose Your Own Adventure provider and more recently 2048:

2048 

Write your own Type Provider

With Project Scaffold it’s easier than ever to write and publish your own FSharp type provider. I’d recommend starting with Michael Newton’s Type Provider’s from the Ground Up article and video of his session at Skills Matter.

You can learn more from Michael and others at the Progressive F# Tutorials in London this November:

DDD North

The next DDD event is in Leeds on Saturday October 18th, where I’ll be talking about how to Write your own Compiler, hope to see you there :)

Pacman Tiles

Back in January I built a sample Pacman maze script in F# to use at a Pacman Kata evening with the F#unctional Londoners group. Coincidentally there’s another Coding Kata this Thursday 26th July at Skills Matter. Anyway a couple of weeks ago I started playing with the sample again on the train to and from work, filling in some of the gameplay.

You can play the latest version with your cursor keys and 9 lives below:

(Right click to install game to desktop)

 
Windows 8

As the sample runs in Silverlight I thought I’d also try it out on it’s cousin WinRT. WinRT lets you build Metro apps on Windows 8. The transition code wise has been pretty straight forward and I now have a tile for the game appearing on my Windows 8 start page:

One click: From Metro tile to video game

 

WinRT is yet another XAML based framework, and is very similar to Silverlight and WPF. One of the few differences I have encountered has been the namespaces the classes are in. For example in Silverlight the Canvas class is in the System.Windows.Controls namespace and in WinRT it is in Windows.UI.Xaml.Controls namespace. It is possible to target both WinRT and Silverlight from the same source code using conditional directives:

#if NETFX_CORE
using Windows.UI.Xaml.Controls;
#else
using System.Windows.Controls;
#endif

 

Multi-targeting

Multi-targeting Silverlight and WinRT is the route I decided to go down which allowed me to develop the game on my laptop running Windows 7 with Visual Studio 2010. Then I periodically tested it out on a desktop box running the Windows 8 Preview Release using Visual Studio 2012. Visual Studio 2012 does run on Windows 7, however WinRT does not.

The WinRT version of the app is implemented in F# and C#. The game part is written in F# as a portable library and the plumbing in C#. There’s a great walkthrough on Creating a Portable F# Library over on MSDN which describes this direction in some detail.

Code Fragment

When the ghosts are eaten they need to return to the enclosure. I used a flood fill algorithm to mark the shortest route from anywhere in the maze back to the enclosure. The flood fill is started inside the enclosure, the fill number is incremented with each iteration of the fill, so that the shortest route is to follow the lowest number adjacent to the ghost’s current square:

module Algorithm =
    let flood canFill fill (x,y) =
        let rec f n = function
            | [] -> ()
            | ps ->
                let ps = ps |> List.filter canFill
                ps |> List.iter (fill n)
                ps |> List.collect (fun (x,y) -> 
                    [(x-1,y);(x+1,y);(x,y-1);(x,y+1)]
                )
                |> f (n+1)
        f 0 [(x,y)]
 
Full Source

The full source code to the game is publicly available on BitBucket:

A single file playable script version is also available on F# Snippets: