State machines are so much fun to write!

[jemfinch]

This is just a friendly message to say that state machines are a ton of fun to write in a strictly typed functional language like SML. Take a look at this one I wrote to parse IRC messages:


datatype state = INITIAL
| PREFIX
| AFTERPREFIX
| COMMAND
| AFTERCOMMAND
| ARG
| AFTERARG
| LASTARG

fun fromString "" = NONE
| fromString s = let
fun isEnd c = c = #"\r" orelse c = #"\n"
fun machine (INITIAL, last, current, prefix, command, args) = let
val c = String.sub (s, 0)
in
if isEnd c then
NONE
else if c = #":" then
machine (PREFIX, 1, 1, "", "", [])
else
machine (COMMAND, 0, 0, "", "", [])
end
| machine (PREFIX, last, current, prefix, command, args) = let
val c = String.sub (s, current)
in
if isEnd c then
NONE
else if c = #" " then
machine (AFTERPREFIX, current, current+1,
String.substring (s, last, current-last), "", [])
else
machine (PREFIX, last, current+1, "", "", [])
end
| machine (AFTERPREFIX, last, current, prefix, command, args) = let
val c = String.sub (s, current)
in
if isEnd c then
NONE
else if c = #" " then
machine (AFTERPREFIX, last, current+1, prefix, "", [])
else
machine (COMMAND, current, current, prefix, "", [])
end
| machine (COMMAND, last, current, prefix, command, args) = let
val c = String.sub (s, current)
in
if isEnd c then
SOME (prefix, String.substring (s, last, current-last), [])
else if c = #" " then
machine (AFTERCOMMAND, current, current+1, prefix,
String.substring (s, last, current-last), [])
else
machine (COMMAND, last, current+1, prefix, "", [])
end
| machine (AFTERCOMMAND, last, current, prefix, command, args) = let
val c = String.sub (s, current)
in
if isEnd c then
SOME (prefix, command, [])
else if c = #" " then
machine (AFTERCOMMAND, current, current+1, prefix, command, [])
else if c = #":" then
machine (LASTARG, current+1, current+1, prefix, command, [])
else
machine (ARG, current, current, prefix, command, [])
end
| machine (ARG, last, current, prefix, command, args) = let
val c = String.sub (s, current)
in
if isEnd c then
SOME (prefix, command,
rev (String.substring (s, last, current-last) :: args))
else if c = #" " then
machine (AFTERARG, last, current+1, prefix, command,
String.substring (s, last, current-last) :: args)
else
machine (ARG, last, current+1, prefix, command, args)
end
| machine (AFTERARG, last, current, prefix, command, args) = let
val c = String.sub (s, current)
in
if isEnd c then
SOME (prefix, command, List.rev args)
else if c = #" " then
machine (AFTERARG, last, current+1, prefix, command, args)
else if c = #":" then
machine (LASTARG, current+1, current+1, prefix, command, args)
else
machine (ARG, current, current, prefix, command, args)
end
| machine (LASTARG, last, current, prefix, command, args) = let
val c = String.sub (s, current)
in
if isEnd c then
SOME (prefix, command,
rev (String.substring (s, last, current-last) :: args))
else
machine (LASTARG, last, current+1, prefix, command, args)
end
in
(case machine (INITIAL, 0, 0, "", "", []) of
NONE => NONE
| SOME (prefix, command, args) =>
SOME (MSG {prefix=IrcUtils.stringToNetmask prefix,
command=command, args=args}))
handle Subscript => NONE
end


It's a bit wordy, but it was really very easy to write -- and (I'm not kidding here) once it typechecked and compiled, it worked. I did not have to make a single change to the code once it compiled, and have yet to discover a bug in it.

Yay for strictly typed languages with easy-to-use sum types and tail-recursion!

Jeremy

[inkedmn]

i have a (dumb) question...

what's a state machine?

[kmj]

http://www.nist.gov/dads/HTML/statemachine.html

They're a basic component of the theory of computer science.