State Machines – Basics of Computer Science

(If you like this, you should check out my cartoons on YouTube and my mailing list.)

Computer science is what enables programming, but it is possible to do a lot of programming without understanding the computer science concepts underlying the process of computation. This isn’t always a bad thing. When we program we work at a much higher level of abstraction. When we drive a car, we only concern ourselves with two or three pedals, a gearshift, and a steering wheel. You can safely operate a car without having any clear idea of how it works. However, if you want to operate a car at the very limits of its capabilities, you need to know a lot more about automobiles than just the three pedals, gearshift and steering wheel.

The same is true of programming. Much mundane everyday work that can be accomplished with little or no understanding of computer science. You don’t need to understand computational theory to build a “contact us” form in PHP. However, if you plan to write code that requires serious computation, you are going to need to understand a bit more about how computation works under the hood.

The purpose of this article is to provide some fundamental background for computation. If there is interest I may follow up with some more advanced topics, but right now I want to look at the logic behind one of the simplest abstract computational devices–a finite state machine.

Finite State Machine

A finite state machine is a mathematical abstraction used to design algorithms. In simple terms, a state machine will read a series of inputs. When it reads an input it will switch to a different state. Each state specifies which state to switch for a given input. This sounds complicated but it is really quite simple.

Imagine a device that reads a long piece of paper. For every inch of paper there is a single letter printed on it–either the letter a or the letter b.

As the state machine reads each letter it changes state. Here is a very simple state machine.

The circles are “states” that the machine can be in. The arrows are the transitions. So if you are in state s and read an a you’ll transition to state q. If you read a b, you’ll stay in state s.

So if we start on s and read the paper tape above from left to right, we will read the a and move to state q. Then we’ll read a b and move back. Another b will keep us on s followed by an a which moves us back to the q state. Simple enough, but whats the point?

Well it turns out that you can run a tape through the state machine and once it is done tell something about the sequence of letters by examining the state you end up on. In our simple state machine above, if we end on s, the tape ends with the letter b, if we end on q, the tape ends with the letter a.

This may sound pointless, but there are an awful lot of problems that can be solved with this type of approach. A very simple example would be to determine if a page of HTML contains these tags in this order:

<html>
	<head>
	</head>
	<body>
	</body>
</html>

The state machine can move to state that shows it has read the html tag, loop until it gets to the head tag, loop until it gets to the head close tag, etc. If it successfully makes it to the final state, then you have those particular tags in the right order.

Finite state machines can also be used to represent the mechanics of a parking meter, pop machine, automated gas pump and all kinds of other things.

Deterministic Finite State Machine

The state machines we’ve looked at so far are all deterministic state machines. From any state there is only one transition for any allowed input. In other words there aren’t two paths leading out of a state when you read the letter a. At first this sounds silly to even make this distinction.

What good is a set of decisions if the same input can result in moving to more than one state? You can’t tell a computer, if x==true then execute doSomethingBig or execute doSomethingSmall, can you?

Well you kind of can with a state machine. The output of a state machine is its final state. It goes through all its processing and then the final state is read and then an action is taken. A state machine doesn’t do anything as it moves from state to state. It processes and then when it gets to the end, the state is read and something external triggers the desired action (dispenses a soda can, etc.). This is an important concept when it comes to non-deterministic finite state machines.

Non-deterministic Finite State Machine

Non-deterministic finite state machines are finite state machines where a given input from a particular state can lead to more than one different state. For example, lets say we want to build a finite state machine that can recognize strings of letters that start with a and are then followed by zero or more occurrences of the letter b or zero or more occurrences of the letter c terminated by the next letter of the alphabet. Valid strings would be:

  • abbbbbbbbbc
  • abbbc
  • acccd
  • acccccd
  • ac (zero occurrences of b)
  • ad (zero occurrences of c)

So it will recognize the letter a followed by zero or more of the same letter of b or c followed by the next letter of the alphabet. A very simple way to represent this is with a state machine that looks like the one below, where a final state of t means that the string was accepted and matches the pattern.

Do you see the problem? From starting point s, we don’t know which path to take. If we read the letter a, we don’t know whether to go to the state q or r. There are a few ways to solve this problem. One is by back tracking. You simply take all the possible paths and ignore or back out of the ones where you get stuck.

This is basically how most of the chess playing computers work. They look at all the possibilities and all the possibilities of those possibilities and choose the path that gives them the greatest number of advantages over their opponent.

The other option is to convert the non-deterministic machine into a deterministic machine. One of the interesting attributes of a non-deterministic machine is that there exists an algorithm to turn any non-deterministic machine into a deterministic one. However, it is often much more complicated. Fortunately for us, the example above is only slightly more complicated. In fact this one is simple enough we can transform it into a deterministic machine in our head without the aid of a formal algorithm.

The machine below is a deterministic version of the non-deterministic machine above. In the machine below, a final state of t or v is reached by any string that is accepted by the machine.

The non-deterministic model has four states and six transitions. The deterministic model has 6 states, 10 transitions and two possible final states. That isn’t that much more, but the complexity usually grows exponentially and a moderately sized non-deterministic machine can produce an absolutely huge deterministic machine.

Regular Expression

If you have done any type of programming, you’ve probably encountered regular expressions. Regular expressions and finite state machines are functionally equivalent. Anything you can accept or match with a regular expression can be accepted or matched with a state machine. For example the pattern above could be matched with:

a(b*c|c*d)

Regular expressions and finite state machines also have the same limitations. In particular they both can only match or accept patterns that can be handled with finite memory. So what type of patterns can’t they match? Lets say you want to only match strings of a and b, where there are a number of a’s followed by an equal number of b’s. Or n a’s followed by n b’s where n is some number. Examples would be:

  • ab
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

At first this looks like an easy job for a finite state machine. The problem is that you’ll quickly run out of states or you’ll have to assume an infinite number of states–at which point it is no longer a finite state machine. Lets say you create a finite state machine that can accept up to 20 a’s followed by 20 b’s. That works fine until you get a string of 21 a’s followed by 21 b’s at which point you will need to rewrite your machine to handle a longer string. For any string you can recognize, there is one just a little bit longer that your machine can’t recognize because it runs out of memory.

This is known as the Pumping Lemma which basically says, if your pattern has a section that can be repeated like the one above then the pattern is not regular. In other words neither a regular expression nor a finite state machine can be constructed that will recognize all the strings that do match the pattern.

If you look carefully, you’ll notice that this type of pattern where every a has a matching b, looks very similar to HTML where within any pair of tags you may have any number of other matching pairs of tags. So while you may be able to use a regular expression or finite state machine to recognize if a page of HTML has the html, head and body elements in the correct order, you can’t use a regular expression to tell if an entire HTML page is valid or not because HTML is not a regular pattern.

Turing Machines

So how do you recognize non-regular patterns? There is a theoretical device that is similar to a state machine called a Turing Machine. It is similar to a finite state machine that it has a paper strip that it reads, but a Turing Machine can erase and write on the paper tape. Explaining a Turing Machine will take more space that we have here, but there are a few important points relevant to our discussion of finite state machines and regular expressions.

Turing Machines are computationally complete and anything that can be computed can be computed on a Turing Machine. Since a Turing Machine can write as well as read from the paper tape, it is not limited to a finite number of states. The paper tape can be assumed to be infinite in length. Obviously, actual computers don’t have an infinite amount of memory, but they contain enough memory that you don’t hit the limit for the type of problems they process.

Turing Machines give us an imaginary mechanical device that lets us visualize and understand how the computational process works. It is particularly useful in understanding the limits of computation. If there is interest I’ll do another article on Turing Machines in the future.

Why does this matter?

So whats the point? How is this going to help you create that next PHP form? Regardless of their limitations state machines are a very central concept to computing. In particular, the recognition that for any non-deterministic state machine you can design, there exists a deterministic state machine that does the same thing. This is a very key point because it means you can design your algorithm in whichever way is the easiest to think about. Once you have a proper algorithm, you can convert it into whatever form is most efficient.

The understanding that finite state machines and regular expressions are functionally equivalent opens up some incredibly interesting uses for regular expression engines–particularly when it comes to creating business rules that can be changed without recompiling a system.

A foundation in computer science allows you to take a problem X that you don’t know how to solve and reason, “I don’t know how to solve X, but I do know how to solve Y and I know how to convert a solution for Y into a solution for X. Therefore I now know how to solve X.”

(If you like this article, you might enjoy my YouTube channel where I create an occasional video or cartoon about some aspect of creating software. I also have a mailing list for people who would like an occasional email when I produce something new.)

Prioritizing Features

In building software, the actual coding is rarely the hardest part. Often deciding what features to build is very difficult. There is a huge wasteland full of code that never got to the point where it was actually usable before people gave up on creating it. Getting your code to the point where it is being used by real users clears a significant hurdle and gives you a much greater chance of success.

Arranging the order of your features so you can quickly get to a usable state with the smallest set of useful capabilities without building anything unnecessary may sound simple. It isn’t.

Continue reading “Prioritizing Features”

Connecting Visual VM to Tomcat 7

Connecting Visual VM to a remote instance of Tomcat 7 is surprisingly easy. All you have to do is add some options to JAVA_OPTS turning on JMX, specifying how you want to handle security and setting the hostname. While it is easy to get it up and running, there are quite a few steps to go through if you want to make it work with authentication and behind a firewall.

My goal with this post is to walk through the basics of getting it running and then modifying the installation to support common configuration needs.

Here are instructions for how to set it up using Ubuntu 11.10:

First lets install Tomcat 7 if you don’t have it.

sudo apt-get update
sudo apt-get upgrade
sudo apt-get install tomcat7

Now we need to set the JAVA_OPTS. We will do that by creating a setenv.sh file in /usr/share/tomcat7/bin/ and putting the options in there. setenv.sh gets called before Tomcat starts to set any environmental variables you may want.

export JAVA_OPTS="-Dcom.sun.management.jmxremote=true \
                  -Dcom.sun.management.jmxremote.port=9090 \
                  -Dcom.sun.management.jmxremote.ssl=false \
                  -Dcom.sun.management.jmxremote.authenticate=false \
                  -Djava.rmi.server.hostname=50.112.22.47"

Line 1 enables jmxremote. Line 2 specifies the port. Line 3 says that we don’t need to use ssl. Line 4 says to leave it wide open and not use any type of authentication. Line 5 specifies the ip address of the server where you are running Tomcat. (Don’t use my ip address of 50.112.22.47, substitute your own.) This is left out of many instructions on the web, so it might work in some circumstances without it, but I wasn’t able to connect with VisualVM unless this configuration points to itself.

I believe this has to do with the fact that JMX is going to open another connection on a random port (discussed below). If you don’t tell it what its hostname (or ip) is, JMX doesn’t know how to tell the client how to connect back to that other port.

Now open VisualVM. On OS X you just run:

jvisualvm

Add the connection by clicking on File > Add JMX Connection… and fill out the dialog box as shown (but using the ip address of your server).

Once you add it, you should see the server in the list on the left hand side. Double click on the JMX connection to the server. (The JMX connection has a JMX icon and should show port 9090.)

You should then be able to view the following screens of information showing what is going on inside of Tomcat.

Firewall

One problem people run into in getting this to work is that they open port 9090 (or whatever they have specified) and VisualVM is unable to connect. This is because JMX appears to accept connections port 9090, but then opens at least one other random port and instructs the client to connect to this port as well.

If we run

sudo netstat -ntlp

We should see something like this:

ubuntu@ip-10-252-22-93:~$ sudo netstat -ntlp
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State       PID/Program name
tcp        0      0 0.0.0.0:22              0.0.0.0:*               LISTEN      494/sshd        
tcp6       0      0 :::8080                 :::*                    LISTEN      2650/java       
tcp6       0      0 :::36851                :::*                    LISTEN      2650/java       
tcp6       0      0 :::22                   :::*                    LISTEN      494/sshd        
tcp6       0      0 :::35543                :::*                    LISTEN      2650/java       
tcp6       0      0 :::9090                 :::*                    LISTEN      2650/java 

Line 4 shows ssh running on port 22. 5 is where Tomcat is serving HTTP. 9 shows the JMX connection. However 6 & 8 appear to be part of the JMX process. If you have firewall that is blocking access to these ports, VisualVM won’t be able to connect. You can’t just add those specific ports because they are random and can change every time Tomcat is restarted. So you have to leave your machine wide open to connect or use the Listener that will be explained a few sections below.

Authentication

Now lets look at how to secure the connection a bit and require a username and password. We can change the settings we put into setenv.sh to tell it to require authentication by changing false to true.

export JAVA_OPTS="-Dcom.sun.management.jmxremote=true \
                  -Dcom.sun.management.jmxremote.port=9090 \
                  -Dcom.sun.management.jmxremote.ssl=false \
                  -Dcom.sun.management.jmxremote.authenticate=true \
                  -Djava.rmi.server.hostname=50.112.22.47"

By default this should look for two files. One is called jmxremote.access and the other is jmxremote.password. It will probably look for the files in /usr/lib/jvm/java-6-openjdk/jre/lib/management/ but this may be different depending on which JDK you have installed and in some cases it will look for the files in the CATALINA_HOME directory.

We need to specify where the files should be found with the following options. Here we specify the files will be in the tomcat7/conf directories. So now our /usr/share/tomcat7/setenv.sh file should look like:

export JAVA_OPTS="-Dcom.sun.management.jmxremote=true \
 -Dcom.sun.management.jmxremote.port=9090 \
 -Dcom.sun.management.jmxremote.ssl=false \
 -Dcom.sun.management.jmxremote.authenticate=true \
 -Djava.rmi.server.hostname=50.112.22.47 \
 -Dcom.sun.management.jmxremote.password.file=/var/lib/tomcat7/conf/jmxremote.password \
 -Dcom.sun.management.jmxremote.access.file=/var/lib/tomcat7/conf/jmxremote.access"

jmxremote.password should look something like:

jmxadmin mysecretpassword

and jmxremote.access should have something like:

jmxadmin readwrite

Our user is jmxadmin, but could be any username. jmxremote.password tells what password is assigned to each user and jmxremote.access tells what access rights each user has. For a user to have access, they need to have an entry in both files.

Now if you try to run this setup, you will probably see something like this error in your catalina.out file:

Error: Password file read access must be restricted: /var/lib/tomcat7/conf/jmxremote.password

To fix this we need to make sure that both files are owned by the tomcat7 user:

sudo chown tomcat7:tomcat7 /var/lib/tomcat7/conf/jmxremote.*

Then we need to make sure that the tomcat7 user is the only user who has read access.

sudo chmod 0600 /var/lib/tomcat7/conf/jmxremote.*

Now you should be able to create a new connection to the server as before, but this time specifying the username and password you wish to use to connect. VisualVM wouldn’t let me just modify an existing JMX connection, so I had to create a new one rather than just adding the username and password to the existing connection.

Controlling the Ports

The only remaining inconvenience is the fact that JMX is going to choose a random port. If you aren’t dealing with a firewall this might not be a big deal, but if you are dealing with a remote server in a data center or in the cloud, it becomes more problematic. We need some way to tell Tomcat to bind the other JMX ports to a specific port number rather than choosing something at random.

We can do this by adding a listener to the /var/lib/tomcat7/conf/server.xml file like this:

<Listener className="org.apache.catalina.mbeans.JmxRemoteLifecycleListener"
  rmiRegistryPortPlatform="9090" rmiServerPortPlatform="9091" />

Just put it below the other Listeners in server.xml. Notice the rmiRegistryPortPlatform is the 9090 that we previously specified in setenv.sh. The rmiServerPortPlatform allows us to bind the process to 9091 instead of a random port number.

Note: You can now remove the line that specifies port 9090 in setenv.sh.

In addition to adding the Listener we need to put the jar in /usr/share/tomcat7/lib/. The jar we are looking for is called catalina-jmx-remote.jar.

To locate this jar, first determine what version of Tomcat you are using by running the version script which will give us the output as shown.

ubuntu@ip-10-252-22-93:$ /usr/share/tomcat7/bin/version.sh 
Using CATALINA_BASE:   /usr/share/tomcat7
Using CATALINA_HOME:   /usr/share/tomcat7
Using CATALINA_TMPDIR: /usr/share/tomcat7/temp
Using JRE_HOME:        /usr
Using CLASSPATH:       /usr/share/tomcat7/bin/bootstrap.jar:/usr/share/tomcat7/bin/tomcat-juli.jar
Server version: Apache Tomcat/7.0.21
Server built:   Sep 8 2011 01:23:08
Server number:  ...0
OS Name:        Linux
OS Version:     3.0.0-14-virtual
Architecture:   amd64
JVM Version:    1.6.0_23-b23
JVM Vendor:     Sun Microsystems Inc.

In our case we are using Tomcat/7.0.21, so we want to go to http://archive.apache.org/dist/tomcat/tomcat-7/v7.0.21/bin/extras/. You can substitute your own version number in the URL to find the file.

Once the file is in /usr/share/tomcat7/lib/, restart your tomcat server and create a new JMX connection as specified above using VisualVM. You should now have a server that requires authenticated access for JMX and where you don’t have to leave all of the ports open.

There is also a way to tunnel VisualVM over an SSH connection for people who want even stronger security, but we aren’t going to address that in this post.

Other Notes

I have seen cases where VisualVM stops showing the Monitor and Threads tabs. If you delete the connection and add it again, they come back. I’m not sure why, but it is worth trying if you aren’t seeing all the data you expect.

Visual VM allows you to add plugins. They can be found under the Tools > Plugin menu option. They are supposed to download when you select them, but I kept getting a failure when trying to install the Visual GC garbage connection plugin.

I was able to get it to install by switching to JDK 1.6 (from Apple) instead of OpenJDK 1.7 on the client. However, when I tried to use Visual GC it said “Not supported for this JVM”. I wasn’t clear if that meant that the client or the server wasn’t supported, but I think it was complaining because the server is using OpenJDK 1.6 instead of the Oracle JDK.

Simple Made Easy – Rich Hickey

Notes from Rich Hickey’s talk on simplicity at Strangeloop 2011.

The video is now available here.

Word origins:

  • Simple  = sim – plex = one braid
  • Easy = adjacent = lie near
Simple:
  • Simple means having one of something, one braid, one fold, one role, one concept, one task, one dimension.
  • Simple can involve many things, but not having interleaving.
  • Simple is an objective notion.
Easy:
  • Near, at hand.
  • Near to our understanding–being familiar.
  • Near to our capabilities. We don’t like to talk about this because it tramples on our egos.
  • We are far to interested in things being easy. This is to our detriment.
  • Easy is relative (unlike “simple”). Music and German are hard from some and easy for others.
Construct vs Artifact
  • We become to infatuated with things being easy  instead of being simple.
  • Long term use is a better indication of simplicity and helps keep use from focusing on things being easy.

We can only hope to make reliable those things we can understand. There is a limit to how much we can keep in our mind at the same time. Intertwined things have to be considered together and this taxes our brains. Fewer “braids” means less complexity and less complexity means we can hold it in our minds better.

To change software requires analysis and decisions. You must be able to reason about your program to be able to reliably change it.

We say, “I can make a change because I have tests.” Who does that? Who drives their car around banging into the guard rails!?

Easy things make us feel like we are fast.

What type of runner can run full speed from the very start of the race? Thats right. Someone who runs very short distances. But as programmers, we are smarter than that. We just fire the starter pistol again every 100 yards.  I don’t know why runners haven’t figured that out.

Ignoring complexity will slow you down if you aren’t just doing a very small project.
There are many constructs that are easy to use, but are very complex.

Benefits of Simplicity:

  • Ease of understanding
  • Ease of change
  • Easier debugging
  • Flexibility
  • More independence for change.

Making Things Easy:

  • Making it “at hand” by bringing it into our environment–installing it.
  • Become familiar with it by learning it.
  • There is a mental barrier. We can’t really get much smaller.

We are all very limited compared to the complexity we create. The difference between a really smart programmer and an average programmer is minimal–no one can really understand all of the complexity we can create.  A juggler can juggle 3 balls. A really good juggler can juggle 9. No juggler can juggle 90 or 900.

Everyone has seen parenthesis, but they haven’t seen it on THAT SIDE of the method. Thats crazy!

Parenthesis are overloaded in lisp. They do several different things so they are complex. By removing this complexity the ease problem is back in the domain of what we can change.

Everyone is happy to grab benefits of new tools, but no one takes the time to see if there are any trade offs.

  • Complect = braid together.
  • Compose = place together.

We can write modules that are completely complected. What are your modules allowed to “think” about. Just partitioning doesn’t give you simplicity.

Having state is never simple because it complects value and time. It is easy, familiar, at hand, etc. The only way to get rid of state is to put it in a box that gives you a functional interface where you always get the same output with the same input.

Simplicity is a choice. It is your fault if you don’t have a simple system.