As I mentioned in recent posts, SoCalCodeCamp was last weekend. I presented two sessions:
- Stop Guessing About MEF Composition, Start Testing
- CoffeeScript Crash Course
I did not record video for the MEF session, but you can find a recording of my MEF session from SoCalCodeCamp @ CSU Fullerton linked from this previous post. The video for the CoffeeScript session is embedded above. Below, find links to the presentation materials.
I explain a bit about how this works in the video and I was able to work through it during the session. But there were two bugs that prevented the machine from providing the correct results. Oh well, people were mostly there to see CoffeeScript, getting the machine to work was secondary. After getting home, I figured out the bugs and posted the code. I also wanted to create this supplemental post to show a cleaner version of the working code. In this article, I’ll also show how to implement the machine using CoffeeScript classes, which I wasn’t able to do in the demo.
The code is available as a gist, and if you are really interested in its evolution, you can step back and forth between the different commits and study the changes.
Let’s get started.
Instant Feedback With Node.js
First install node.js and the coffee-script NPM module. You can find instructions 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 Sublime Text 2, side by side.
Shrinking the Implementation
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 what we want. Like I told my session attendees, just try what you think will work and it probably will. But if we try, we can take advantage of some additional CoffeeScript language features to make this implementation 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 accessing data.
I test, and everything works.
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 post fixed condition. Since nothing outside the object manipulated the object’s fields, I don’t need to provide any getters for
FinalStates. Although I can just take advantage of closure to capture my data members, I still need to use the
@ symbol when referring 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.
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 input. 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 with 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, , 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, , 2
createMyMachine we can test with 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 that’s more useful that the starting implementation, but just happens to use the same number of lines.
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.
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
createMyMachine = () -> rules = [ createRule 0, '0', 1 createRule 0, '1', 1 createRule 1, '0', 0 createRule 1, '1', 0 ] new Machine 0, rules, , 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, , 2
In our scenario, there really isn’t a big advantage to using classes, because we have no need to extend
Machine. But, I wanted to show what this looks like because I’m sure it will be interesting to someone getting started with CoffeeScript.
Someday I’ll do one of these machines without iterating over a set of rules The approach in this example has big O complexity of at least n*n. If we had long strings and large rule sets, we would spend a lot of time looping in the “Read” method.
Since there was so much interest in this session, maybe I’ll do it again at the next CodeCamp, but there are still plenty of other languages I’d like to play with including .NET languages like Nemerle and F#. Whatever crash course I do in the future, it will be for beginners and it will be for fun.