A Pushdown Automaton toolkit for Ruby. It's based on the State Manager from the Amethyst project.
A Pushdown Automaton is a combination of a Stack and a State Machine. Transitioning between states is accomplished via stack operations like push and pop, which allows you to encapsulate a state's behavior in a small single-responsibility class instead of making a class vary its behavior based on a variable.
To set up a Pushdown Automaton, you'll need to:
Declare a variable for the state stack
Declare state classes that provide the functionality for the automaton in that state.
This example will be using the “Language acceptor” from Chapter 4 of the MIT Open Courseware course: Introduction to Electrical Engineering and Computer Science I. You don't necessarily need to have taken that course or reviewed the chapter notes, but it's an excellent introduction to the state machine concept.
Examples that start with [1] pry(main)> are executed using the excellent Pry REPL.
The description from the chapter notes on this example are:
Here is a finite-state machine whose output is true if the input string adheres to a simple pattern, and false otherwise. In this case, the pattern has to be
a, b, c, a, b, c, a, b, c, ….It uses the states 0, 1, and 2 to stand for the situations in which it is expecting an a, b, and c, respectively; and it uses state 3 for the situation in which it has seen an input that was not the one that was expected. Once the machine goes to state 3 (sometimes called a rejecting state), it never exits that state.
To get started extend your stateful class with Pushdown::Automaton and declare a state stack:
require 'pushdown' clsss Acme::Language extend Pushdown::Automaton pushdown_state :acceptor end # class Acme::LanguageAcceptor
Now, when we create an instance of the class, it attempts to push an initial state on the stack, defaulting to a class in the same namespace called Initial. Since we haven't declared such a state class, creating the class fails:
[1] pry(main)> l = Acme::Language.new
Pushdown::DeclarationError: failed to look up a state class for
:initial: uninitialized constant Acme::Language::Initial
from lib/pushdown/automaton.rb:218:in `rescue in pushdown_inferred_state_class'
Caused by NameError: uninitialized constant Acme::Language::Initial
from lib/pushdown/automaton.rb:216:in `pushdown_inferred_state_class'
To rectify this, we need to start declaring the state classes that will provide stateful functionality to Acme::Language#acceptor:
The default convention is for state classes to be declared in the same namespace as the state stack. This is fine for examples and state machines with only a few simple states, but it can be unwieldy for more complex machines. We'll show you how to set up for those more complex cases a little later.
In the meantime, let's set up the Initial state inline with the Acme::Language class:
clsss Acme::Language
# [...]
# The initial state
class Initial < Pushdown::State
end
end # class Acme::LanguageAcceptor
Now we can create an instance of Language and see the acceptor_stack has an instance of the Initial state on it:
[1] pry(main)> l = Acme::Language.new => #<Acme::Language:0x00007f9397995070 @acceptor_stack=[ #<Acme::Language::Initial:0x00007f93979947d8 @data=nil>]>
Let's say that the entry point into “accepting” the input is a method on Language called #accept. Since it's Ruby, we'll assume the input is Enumerable (responds to each and yields a character at a time), which will make the input source extremely flexible. Enumerable already provides a way of asking a question of each value and returning either true or false if and only if every value answers the question with true in the #all? method:
class Acme::Language # [...] def accept( input ) return input.all? do |char| # ... end end end
Now that we have some basic functionality set up, let's start testing. First, the happy path test:
RSpec.describe( Acme::Language ) do RSpec::Matchers.define( :accept ) do |expected| match do |acceptor| acceptor.accept( expected ) end end it "accepts a,b,c" do instance = described_class.new expect( instance ).to accept( 'abc'.each_char ) end end
This fails, as expected:
Failures:
1) Acme::Language accepts a,b,c
Failure/Error: expect( instance ).to accept( 'abc'.each_char )
expected #<Acme::Language:0x00007fd567227600
@acceptor_stack=[#<Acme::Language::ExpectingA:0x00007fd567226b60
@data=nil>]> to accept "a", "b", and "c"
# ./spec/acme/language_spec.rb:21:in `block (2 levels) in <top (required)>'
It's not yet hooked up to the states so the failure isn't as meaningful as it could be, so let's confirm that the containing logic is at least correct. We'll temporarily make the inner block of #accept look like this to reflect the procedural method covered in the MIT example:
def accept( input ) n = ->( s, i ) { case when s == 0 && i == 'a' then 1 when s == 1 && i == 'b' then 2 when s == 2 && i == 'c' then 0 else 3 end } state = 0 return input.all? do |char| state = n[ state, char ] state != 3 end end
Yep, that makes it pass:
Finished in 0.00067 seconds (files took 0.13729 seconds to load) 1 example, 0 failures
Obviously if your state machine is this simple, you should consider just keeping the code simple to match. Let's ignore that for now, however, for the purposes of demonstrating how you might decouple things a bit for more complex state machines, especially if transitions happen asynchronously or based on several inputs, etc.
To this end, let's implement it with Pushdown states. First let's cover the API for interacting with the current state since that's what's required.
The first thing to grok is that instead of the state being a variable that drives the functionality via a block of conditions, states are objects which themselves are responsible for that state's functionality. In our example, instead of using an integer variable state, whatever is at the top of the acceptor stack is the current state. To change what a given state does we just change the state class's functionality.
So now we just need to interact with the right states depending on what the input is.
To do this we need to think about transitions. There are three states our state machine can be in which mean that the input it's seen up to that point is “acceptable”: 0, 1, 2, and 3. Since we can name our classes in a way which reveals the intention of their functionality, let's instead call them: ExpectingA, ExpectingB, and ExpectingC; and a fourth state which which means that some unacceptable input has been seen called Rejected. Our state machine currently starts in an Initial state, but now we can see that it should start out ExpectingA. Let's change the initial state from the default in the declaration and rename the Initial class accordingly:
diff --git a/lib/acme/language.rb b/lib/acme/language.rb
--- a/lib/acme/language.rb
+++ b/lib/acme/language.rb
@@ -10,7 +10,19 @@ class Acme::Language
# Declare state stack with conventional defaults for all options
- pushdown_state :acceptor
+ pushdown_state :acceptor, initial_state: :expecting_a
+ ### Return +true+ if the +input+ is acceptable, false otherwise.
+ def accept( input )
+ return input.all? do |char|
+ # ...
+ end
+ end
+
+
+ # Expect an 'a' as input
+ class ExpectingA < Pushdown::State
+ end
+
end # class Acme::Language
The state stack is changed via transitions that it declares for itself. Transitions in Pushdown are operations on the stack like push, pop, switch, etc. In ExpectingA, if an a is seen, we want to transition to ExpectingB, or to Rejected otherwise.
There are a few different options for the successful transition. If you wanted to keep track of how you got to where you are (e.g., for backtracking, sensible errors, etc.) you might consider pushing the next state, which pushes a new instance of the specified state onto the stack. Alternatively, you can just switch the state, which pops the current state and pushes a new instance of the specified state. For simplicity, let's use the latter. We'll name the transition saw_an_a to reveal the intention behind the declaration; it will transition to the ExpectingB state. We also can declare the Rejected case, using a push so we know what the previous state was:
class ExpectingA < Pushdown::State transition_switch :saw_an_a, :expecting_b transition_push :didnt_see_an_a, :rejected end # ExpectingA
There are two primary methods for interacting with the current state on the stack: an event-oriented one and a time-oriented one. The difference is up to you, but this is useful for things like waiting on network input and timing out after a while, etc.
The event-oriented method is #on_event. It has one required argument, the “event”, and a splat to allow any additional arguments you may require. The “event” can be anything meaningful to your system; for our case we'll just use the input character.
class ExpectingA < Pushdown::State transition_switch :saw_an_a, :expecting_b transition_push :didnt_see_an_a, :rejected ### Determine what should happen given the specified input +char+. def on_event( char, * ) if char == 'a' return :saw_an_a else return :rejected end end end
Ruby
$ gem install pushdown
You can check out the current source with Git via Gitlab:
$ hg clone http://hg.sr.ht/~ged/Pushdown $ cd Pushdown
After checking out the source, run:
$ gem install -Ng $ rake setup
This task will install dependencies, and do any other necessary setup for development.
Michael Granger ged@faeriemud.org
While Pushdown does not contain any Amethyst Game Engine source code, it does borrow heavily from its ideas and nomenclature. Many thanks to the Amethyst team for the inspiration.
Thanks also to Alyssa Verkade for the initial idea.
This gem includes code from the rspec-expectations gem, used under the terms of the MIT License:
Copyright (c) 2012 David Chelimsky, Myron Marston Copyright (c) 2006 David Chelimsky, The RSpec Development Team Copyright (c) 2005 Steven Baker Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
The documentation and code examples use material from:
Leslie Kaelbling, Jacob White, Harold Abelson, Dennis Freeman, Tomás Lozano-Pérez, and Isaac Chuang. 6.01SC Introduction to Electrical Engineering and Computer Science I. Spring 2011. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
Pushdown itself is:
Copyright © 2019-2021, Michael Granger All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
Neither the name of the author/s, nor the names of the project's contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.