Using the State Machine Compiler with Python

Today I learned about a state machine compiler and code generator. It provides a small DSL that you can use to describe a state machine and the transitions between the states, which will be compiled to create a number of classes, and then all you have to do is provide the code for the actions. Here, actions, states, and transitions are defined terms that are described in the documentation for the smc tool.

All you need to do is download the source code from SourceForge here. The jar file you’re looking for is located in smc/bin/Smc.jar. I’ll walk through the example in the SMC documentation. Copy the following snippet and save it as Turnstile.sm

%class Turnstile
%package turnstile
%start MainMap::Locked
%map MainMap
%%
Locked
{
 coin Unlocked { unlock(); }
 passs nil { alarm(); }
}
Unlocked
{
 passs Locked { lock(); }
 coin nil { thankyou(); }
}
%%

Great. Now compile that state machine script as:

java -jar Smc.jar -python Turnstile.sm

This should produce a Turnstile_sm.py in your working directory.

VERY IMPORTANT: Put smc/lib/Python/statemap.py in your PYTHONPATH or your working directory, you’ll need to import it in the next snippet.

import Turnstile_sm

class Turnstile:
    def __init__(self):
        self._fsm = Turnstile_sm.Turnstile_sm(self)
    def alarm(self):
        print("Alarming!")
    def thankyou(self):
        print("Thanks!")
    def lock(self):
        print("Locked!")
    def unlock(self):
        print("Unlocked!")

if __name__ == '__main__':
    ts = Turnstile()
    ts._fsm.coin()
    ts._fsm.passs()

Why does “pass” have an extra “s”? Because pass is reserved in Python, and I couldn’t think of a better variable name. So this doesn’t do much besides print stuff out when different actions are triggered by changes in state, but it’s still pretty cool. For more motivation for state machines, read this Robert Martin article.

The Recursive Maze Problem, Part I

Earlier this year, when I was looking for work, I got the same recursive maze problem three interviews in a row. Recursion is cute and clever, but you generally want to use iterative solutions in production.

Usually, you get a string representation of the maze, something like:

ms = '''
S####
....#
#.###
....G
##..#
...##
#..##
'''

So then you need to parse that into a list of lists, which isn’t difficult:

def maze_string_to_list_of_lists(maze: str) -> []:
    rows = maze.split()
    new_maze = []
    for row in rows:
        new_row = [i for i in row]
        new_maze.append(new_row)
    return new_maze

Next, I like to write a function to return cells orthogonal to some cell location. This originally considered cells north, south, east, and west of a location, but then I limited it to just south and east, because this is recursive and we have to worry about the stack size in Python. (Because recursion is as stupid as it is clever.)

def orthogonals(row: int, col: int, row_limit: int, col_limit: int) -> []:
    result = []
    # check input
    if row < 0 or row >= row_limit:
        return result
    if col < 0 or col >= col_limit:
        return result
    # compute output
    s = [row+1, col]
    e = [row, col+1]
    # check computed output
    if s[0] < row_limit:
        result.append(s)
    if e[1] < col_limit:
        result.append(e)
    return result

Finally, the meat and potatoes. Yeah, so SOLN is a global variable that’s laying around, which is bad. You know what else is bad? Recursive maze solvers.

SOLN = []

def find_path(row: int, col: int, maze: list) -> bool:
    if maze[row][col] == 'G':
        SOLN.append([row, col])
        return True
    if maze[row][col] == '#':
        return False
    SOLN.append([row, col])
    orthos = orthogonals(row, col, len(maze), len(maze[0]))
    for ortho in orthos:
        if ortho in SOLN:
            pass
        if find_path(ortho[0], ortho[1], maze):
            return True
    SOLN.pop()
    return False

References:

  • (Recursion: Solving a Maze)[https://www.cs.bu.edu/teaching/alg/maze/]
  • (Backtracking: Rat in a Maze)[http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/]

Getting CSRF to work with Rails and Angular

I had trouble posting to my Rails server from an Angular controller until I found this SO post. In /app/controllers/application_controller.rb I added the following code.

class ApplicationController < ActionController::Base
  protect_from_forgery with: :exception

  after_action :set_csrf_cookie_for_ng

  def set_csrf_cookie_for_ng
    cookies['XSRF-TOKEN'] = form_authenticity_token if protect_against_forgery?
  end

  protected

    # In Rails 4.2 and above
    def verified_request?
      super || valid_authenticity_token?(session, request.headers['X-XSRF-TOKEN'])
    end
end

Getting Started with Watercolor

In this post, I’ll discuss options for building a watercolor kit, and provide some introductory reading material.

My Background

I started working in watercolor in 2016. I heard the quote by Annie Dillard, “How we spend our days is, of course, how we spend our lives.” and thought that I should make an effort to carve out more time for art, before I don’t have any time left to carve. I decided to work more in watercolor because, for me, it strikes a balance between range of expression, time, and space. Also, although I’ve done art my whole life, I’ve tended to shy away from color because of it’s difficulty. Focusing on watercolor has allowed/forced me to learn more about color.

Continue reading

Functional Digression at Work

One of my coworkers asked how to filter a list, but return the “pass” and “fail” items in separate lists. For example, filter takes some data and a condition, and returns a list of the items that pass the condition, but what if we returned two lists? One of my other coworkers came up with a neat solution using reduce, and I wrote something using generics. Here’s the operation I’m calling “fork”, implemented in Swift3.

import Foundation

func fork<T>(_ data: [T], completion: (T)->Bool) -> ([T],[T]) {
    var pass = [T]()
    var fail = [T]()
    for item in data {
        completion(item) ? pass.append(item) : fail.append(item)
    }
    return (pass,fail)
}

var (pass, fail) = fork([0,1,2,3,4]) { $0 % 2 == 0 }

Deterministic Finite Automata in Swift

I’ve been reading Understanding Computation by Tom Suart, and it reminds me of my first CS class in grad school where I learned about and struggled to implement finite automata. I think one major lesson from that experience was to forget about the pictures of circles and loops on the blackboard, and figure out the bare minimum needed to represent the idea. In the case of finite automata, the bare minimum was that there was a state, and a set of rules that modified the state; each rule was composed of a current state, an input, and a next state. I decided to implement a simple finite automata in Swift using a list of Ints as states, and a single Int as input.

Continue reading

Very Very Verbose Cosine Similarity

This material was a teaching aid for a crash course I gave at work about cosine similarity. Cosine similarity is a blunt instrument used to compare two sets of text. If two the two texts have high numbers of common words, then the texts are assumed to be similar. The ultimate goal is to plug two texts into a function and get an easy to understand number out that describes how similar the texts are, and cosine similarity is one way to skin that cat.

Please note, there are plenty of other very fast implementations for cosine similarity, but this one was written for educational purposes.

Continue reading

C++14 Range Based For Loops

C++ has changed a lot since I was first learned about it in college, so I’m going to do a series of posts outlining some of those changes as they come up for me. First off: range-based for-loops using auto type-inference. Here’s the TL;DR:

  • Use auto i when you want to work with copies of the array items
  • Use auto &i when you want to work with the original items and maybe modify them place
  • Use auto const &i when you want to work with the original items and not modify them

Continue reading

How Many Trials Before the Nth Success

TLDR: the negative binomial counts the number of trials needed before the Nth success.

I had this problem where we were considering running some very expensive tests that had a known success rate, and we wanted to know, given the success rate and the cost, whether we should run them at all. To make things more interesting, we were only interested in a set number n of successes, and we could stop all testing after the first n successes. My initial thought was to use the binomial distribution, but the binomial doesn’t “cut off” after a set number of successes. It turns out that we needed to use a version of the negative binomial distribution.

Continue reading

Setting Up Sphinx Documentation

It took me a while to get Sphinx documentation set up correctly. Since it is highly configurable, it is highly easy to not configure correctly. In this guide I’ll assume that you’re using a Python virtual environment, and that you’ve placed the source code that you want to document in a directory called src/. I’ll walk through installing and configuring what you need to create documentation from inline comments using the Google or NumPy style, and create API documentation for a Flask server. I’ll be extra-explicit about what directory I’m in when I make calls that make assumptions about the working directory.

Continue reading