A Finite State Machine to accept even length strings of 0s and 1s. Written at SoCalCodeCamp San Diego, 6/24/2012. Details, Video, Slides: http://wp.me/p1HYUa-80

.gitattributes

# Disable LF normalization for all files
* -text

README.md

CoffeeScript Crash Course

Instant Feedback With Node.js

First install node.js and the coffee-script NPM module. You can find isntructions on coffeescript.org.

Watch-compile your source file with this command:

coffee --watch --compile .\coffeescriptcrashcourse.coffee

A *.js file should appear with the same name as the CoffeeScript file. In our case, coffeescriptcrashcourse.js. Open both files in SublimeText 2, side by side.

When you make changes in the CoffeeScript file and save, the watch compiler will update the javascript as soon as the file hits the disk. To see the changes, just click in the Sublime window displaying the js, and Sublime should instantly refresh (as long as you haven't made any changes in that window.)

Shrinking the Implementation

###Creating rules My initial implementation of createRule (created live during my SoCalCodeCamp session) looked like this:

createRule = (currentState, inputCharacter, nextState) ->
 state: currentState
 char: inputCharacter
 next: nextState
 Match: (machineState, i) ->   
   @state is machineState and @char is i

This works fine, and its the most obvious way to setup a function that does waht we want. Like I told my session attendees, just try what you think will work and it probably well. But if we try, we can take advantage of some additional CoffeeScript language features to make this implentation shorter:

createRule = (CurrentState, InputChar, NextState) ->
  GetNextState: () -> NextState
  Match: (machineState, inputChar) -> 
    machineState is CurrentState and inputChar is InputChar

CoffeeScript doesn't require us to manually create fields to store the state passed into the function, the variables will be automatically visible to our object. But, they wont be available later on unless we close over them. Hence, while we removed three lines, we added one back in order to make NextState accessible. I also renamed some of the variables, and then updated the machine implementation to use the new GetNextState function instead of directly acessing data.

I test, and everything works.

###Creating machines

Likewise, I can tighten up the createMachine implementation with the same technique. Here is the original:

createMachine = (initialState, rules, finalStates) ->
  currentState: initialState
  ruleSet: rules
  acceptance: finalStates 
  ReadAll: (s) ->
    @Read x for x in s.split ''
    return undefined

  Read: (c) ->
    return if @currentState == 2 
    for rule in @ruleSet
      if rule.Match @currentState, c
        return @Update rule
    @currentState = 2
   
  Update: (r) ->
    @currentState = r.GetNextState()
  AcceptedInput: () ->
    @currentState in @acceptance

And the new:

createMachine = (CurrentState, Rules, FinalStates) ->
  ReadAll: (value) ->
    @Read x for x in value.split ''
    return undefined
  Read: (inputChar) ->
    return if CurrentState == 2 
    for rule in Rules
      return @Update rule if rule.Match CurrentState, inputChar        
    CurrentState = 2   
  Update: (rule) ->
    CurrentState = rule.GetNextState()
  AcceptedInput: () ->
    CurrentState in FinalStates

I also eliminated one level of nesting by turning the loop's inner conditional statement into a postfixed condition. Since nothing outside the object manipulated the object's fields, I don't need to provide any getters for CurrentState, Rules, or FinalStates. Although I can just take advantage of closure to capture my data members, I still need to use the @ symbol when refering to non-closure data (in this case the non-closure fields are all functions, but the same should be true if they were just data values).

I test this and everything still works.

Machine Factory

During the demo I created one machine instance by writing down the rules and then invoking createMachine. Once I had the machine, I used it to evaluate a string and query whether the machine accepted the inupt. Due to a couple bugs, the machine rejected input that it should have accepted. However, once I got home and debugged it, the machine worked as expected.

Creating a one off machine was fine for the demo, but not very useful when we want to test the machine with different values. This is because a new machine must be created for each input string, since there is no way to reset a machine after it has run. createMachine is (almost) a method for creating any finite state machine. I say "almost" because the "dead" state is hard coded as 2. To make createMachine useful, we must create a rule set and pass it to the machine along witht the start state, final state and (ideally) the dead state.

Lets fix the dead state issue first.

createMachine = (CurrentState, Rules, FinalStates, DeadState) ->
  ReadAll: (value) ->
    @Read x for x in value.split ''
    return undefined
  Read: (inputChar) ->
    return if CurrentState == DeadState 
    for rule in Rules
      return @Update rule if rule.Match CurrentState, inputChar        
    CurrentState = DeadState   
  Update: (rule) ->
    CurrentState = rule.GetNextState()
  AcceptedInput: () ->
    CurrentState in FinalStates

By promoting the dead state to a parameter, we should be able to use this code to create just about any (deterministic) Finite State Machine. Of Course, we need to pass 2 when we call createMachine for our current example to continue to work.

myMachine = createMachine 0, rules, [0], 2

Now, we can wrap up the code that creates the specific FSM from our demo.

createMyMachine = () ->
  rules = [
    createRule 0, '0', 1
    createRule 0, '1', 1
    createRule 1, '0', 0
    createRule 1, '1', 0
  ]
  createMachine 0, rules, [0], 2

With createMyMachine we can test wtih blocks like this:

myMachine = createMyMachine()
myMachine.ReadAll "00"
alert myMachine.AcceptedInput()

myMachine2 = createMyMachine()
myMachine2.ReadAll "1"
alert myMachine2.AcceptedInput()

But clearly, we have an opportunity to remove duplication, lets do that. While we're in there we can make the output a little more informative too.

testMyMachine = (input) ->
  myMachine = createMyMachine()
  myMachine.ReadAll input
  alert [input, myMachine.AcceptedInput()].join ','

Now we have a prettier implementation thats more useful that the starting implementation, but just happens to use the same number of lines.

Get Classy

During the demo I couldn't show the attendees CoffeeScript's class support. When I watched the video I realized why. I forgot to put the skinny arrow after my constructor! I should have kept a closer eye on the top right corner of coffeescript.org, there was a message up there which probably would have taken me to the right line.

Since I couldn't do it then, lets do it now, and convert our two objects into classes. Starting with the machine.

class Machine
  constructor: (@CurrentState, @Rules, @FinalStates, @DeadState) ->
  ReadAll: (value) =>
    @Read x for x in value.split ''
    return undefined
  Read: (inputChar) => 
    return if @CurrentState is @DeadState
    for rule in @Rules
      return @Update rule if rule.Match @CurrentState, inputChar
    @CurrentState = @DeadState
    return undefined
  Update: (rule) =>
    @CurrentState = rule.GetNextState()
    return undefined
  AcceptedInput: () => 
    @CurrentState in @FinalStates

Here is our Machine class. Its not that different than our createMachine implementation. However, we do go back to using @ everywhere and we are using the fat arrow. The fat arrow seems like the right thing to do, according to my reading of the CoffeeScript documentation:

When used in a class definition, methods declared with the fat arrow will be automatically bound to each instance of the class when the instance is constructed.

coffeescript.org

However, I tried it with the skinny arrow and in our use case, it still worked. So, I still can't claim to understand this binding. Oh well, we also need to update createMyMachine to use the new operator:

createMyMachine = () ->
  rules = [
    createRule 0, '0', 1
    createRule 0, '1', 1
    createRule 1, '0', 0
    createRule 1, '1', 0
  ]
  new Machine 0, rules, [0], 2

Now lets turn createRule into a class.

class Rule 
  constructor: (@CurrentState, @InputChar, @NextState) ->
  GetNextState: () => @NextState  
  Match: (machineState, inputChar) =>
    machineState is @CurrentState and inputChar is @InputChar

Nothing very exiting, just more of what we saw when we converted Machine. We just need to update createMyMachine to get this to work with our test.

createMyMachine = () ->
  rules = [
    new Rule 0, '0', 1
    new Rule 0, '1', 1
    new Rule 1, '0', 0
    new Rule 1, '1', 0
  ]
  new Machine 0, rules, [0], 2

In our scenario, there really isn't a big advantage to using classes, because we have no need to extend Rule or Machine. But, I wanted to show what this looks like because I'm sure it will be interesting to someone getting started with CoffeeScript.

coffeescriptcrashcourse.coffee

# node.js shim for alert
alert = (value) -> console.log value

class Rule 
  constructor: (@CurrentState, @InputChar, @NextState) ->
  GetNextState: () => @NextState  
  Match: (machineState, inputChar) =>
    machineState is @CurrentState and inputChar is @InputChar

class Machine
  constructor: (@CurrentState, @Rules, @FinalStates, @DeadState) ->
  ReadAll: (value) =>
    @Read x for x in value.split ''
    return undefined
  Read: (inputChar) => 
    return if @CurrentState is @DeadState
    for rule in @Rules
      return @Update rule if rule.Match @CurrentState, inputChar
    @CurrentState = @DeadState
    return undefined
  Update: (rule) =>
    @CurrentState = rule.GetNextState()
    return undefined
  AcceptedInput: () => 
    @CurrentState in @FinalStates

createMyMachine = () ->
  rules = [
    new Rule 0, '0', 1
    new Rule 0, '1', 1
    new Rule 1, '0', 0
    new Rule 1, '1', 0
  ]
  new Machine 0, rules, [0], 2

testMyMachine = (input) ->
  myMachine = createMyMachine()
  myMachine.ReadAll input
  alert [input, myMachine.AcceptedInput()].join ','

testMyMachine "00"
testMyMachine "1"

coffeescriptcrashcourse.js

// Generated by CoffeeScript 1.3.3
(function() {
  var Machine, Rule, alert, createMyMachine, testMyMachine,
    __bind = function(fn, me){ return function(){ return fn.apply(me, arguments); }; },
    __indexOf = [].indexOf || function(item) { for (var i = 0, l = this.length; i < l; i++) { if (i in this && this[i] === item) return i; } return -1; };

  alert = function(value) {
    return console.log(value);
  };

  Rule = (function() {

    function Rule(CurrentState, InputChar, NextState) {
      this.CurrentState = CurrentState;
      this.InputChar = InputChar;
      this.NextState = NextState;
      this.Match = __bind(this.Match, this);

      this.GetNextState = __bind(this.GetNextState, this);

    }

    Rule.prototype.GetNextState = function() {
      return this.NextState;
    };

    Rule.prototype.Match = function(machineState, inputChar) {
      return machineState === this.CurrentState && inputChar === this.InputChar;
    };

    return Rule;

  })();

  Machine = (function() {

    function Machine(CurrentState, Rules, FinalStates, DeadState) {
      this.CurrentState = CurrentState;
      this.Rules = Rules;
      this.FinalStates = FinalStates;
      this.DeadState = DeadState;
      this.AcceptedInput = __bind(this.AcceptedInput, this);

      this.Update = __bind(this.Update, this);

      this.Read = __bind(this.Read, this);

      this.ReadAll = __bind(this.ReadAll, this);

    }

    Machine.prototype.ReadAll = function(value) {
      var x, _i, _len, _ref;
      _ref = value.split('');
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        x = _ref[_i];
        this.Read(x);
      }
      return void 0;
    };

    Machine.prototype.Read = function(inputChar) {
      var rule, _i, _len, _ref;
      if (this.CurrentState === this.DeadState) {
        return;
      }
      _ref = this.Rules;
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        rule = _ref[_i];
        if (rule.Match(this.CurrentState, inputChar)) {
          return this.Update(rule);
        }
      }
      this.CurrentState = this.DeadState;
      return void 0;
    };

    Machine.prototype.Update = function(rule) {
      this.CurrentState = rule.GetNextState();
      return void 0;
    };

    Machine.prototype.AcceptedInput = function() {
      var _ref;
      return _ref = this.CurrentState, __indexOf.call(this.FinalStates, _ref) >= 0;
    };

    return Machine;

  })();

  createMyMachine = function() {
    var rules;
    rules = [new Rule(0, '0', 1), new Rule(0, '1', 1), new Rule(1, '0', 0), new Rule(1, '1', 0)];
    return new Machine(0, rules, [0], 2);
  };

  testMyMachine = function(input) {
    var myMachine;
    myMachine = createMyMachine();
    myMachine.ReadAll(input);
    return alert([input, myMachine.AcceptedInput()].join(','));
  };

  testMyMachine("00");

  testMyMachine("1");

}).call(this);

watch.cmd

coffee --watch --compile .\coffeescriptcrashcourse.coffee

Debugged, line 17 was assigning the value of @currentstate instead of checking it.
line 24 had the incorrect property name for the next state.