Phillip Trelford's Array

POKE 36879,255

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).

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 :)

Snowflakes

Welcome to day 2 of the F# Advent Calendar in English, and don’t miss Scott Wlaschin’s introduction to property-based testing from yesterday.

In A Christmas Carol Charles Dickens wrote of cold winters with snow as a matter of course. White Christmases were common during the Little Ice Age that lasted from the 1550s to the 1850s. Nowadays the chances of a snowfall on Christmas day are much lower, but the imagery of a white Christmas persists.

In this post we’ll generate our snowflakes instead.

Koch Snowflake

The Koch snowflake is a mathematical curve constructed from an equilateral triangle where each line segment is recursively altered:

Koch

The picture above was generated in the F# REPL, using WinForms to display a bitmap:

let snowflake (graphics:Graphics) length =
   use pen = new Pen(Color.White)
   let angle = ref 0.0
   let x = ref ((float width/2.0) - length/2.0)
   let y = ref ((float height/2.0) - length/3.0)
   let rec segment n depth =
      if depth = 0 then
         line n
      else
         segment (n/3.0) (depth-1)
         rotate -60.0
         segment (n/3.0) (depth-1)
         rotate 120.0
         segment (n/3.0) (depth-1)
         rotate -60.0
         segment (n/3.0) (depth-1)
   and line n =
      let r = !angle * Math.PI / 180.0
      let x2 = !x + cos(r) * n
      let y2 = !y + sin(r) * n
      graphics.DrawLine(pen, float32 !x,float32 !y, float32 x2, float32 y2)
      x := x2
      y := y2
   and rotate a =
      angle := !angle + a
   let depth = 5
   segment length depth
   rotate 120.0  
   segment length depth  
   rotate 120.0
   segment length depth

The full snippet is available on F# Snippets: http://fssnip.net/oA

Paper and Scissors

Snowflakes can be created by folding paper and cutting holes with scissors. We can get a similar effect using transparent polygons and rotational symmetry:

Paper

Here the polygons are selected randomly and like snowflakes each one is different:

let paperSnowflake () =   
   let image = new Bitmap(int width, int height)
   use graphics = Graphics.FromImage(image)  
   use brush = new SolidBrush(Color.Black)
   graphics.FillRectangle(brush, 0, 0, int width, int height)
   graphics.TranslateTransform(float32 (width/2.0),float32 (height/2.0))
   let color = Color.FromArgb(128,0,128,255)
   use brush = new SolidBrush(color)
   let rand = Random()
   let polys =
      [for i in 1..12 ->
         let w = rand.Next(20)+1 // width
         let h = rand.Next(20)+1 // height
         let m = rand.Next(h)    // midpoint
         let s = rand.Next(30)   // start
         [|0,s; -w,s+m; 0,s+h; w,s+m|]
      ]
   for i in 0.0..60.0..300.0 do
      graphics.RotateTransform(float32 60.0)
      let poly points =
         let points = [|for (x,y) in points -> Point(x*5,y*5)|]
         graphics.FillPolygon(brush,points)
      polys |> List.iter poly 
   image

 

The full snippet is on F# Snippets: http://fssnip.net/oB

Another interesting method of generating snowflakes is cellular automata, but I’ll leave that as an exercise for the reader.

Happy holidays!