[Arjen Markus] They are very powerful programming devices, but most languages are unsuitable to actually define them: (finite) state machines. Everyday examples: parsers in Yacc/Lex, regular expressions, protocol handlers and so on. Below is a small script, inspired by a paper on Forth, that shows that Tcl can retain the table-like appearance that one so dearly loves, when specifying a state machine. (Okay, it does little or no error checking, it defines only deterministic finite state machines, and the example is overly simple, but still, have a look). ---- # statemachine.tcl -- # # Script to implement a finite state machine # # Version information: # version 0.1: initial implementation, april 2002 namespace eval ::FiniteState { variable statemachine namespace export defineMachine evalMachine resetMachine } # defineMachine -- # Define a finite state machine and its transitions # # Arguments: # machine Name of the machine (a variable) # states List of states # # Result: # None # # Side effects: # The variable "machine" is filled with the definition # # Notes: # The list of states can only contain the commands initialState # and state. No others are allowed (no check though) # # For instance: # defineMachine aMachine { # initialState 1 # state 1 { # "A" 2 {puts "To state 2"} # "B" 3 {puts "To state 3"} # } # state 2 { # "C" 1 {puts "To state 1"} # "D" 3 {puts "To state 3"} # } # state 3 { # "E" 3 {exit} # } # } # # proc ::FiniteState::defineMachine { machine states } { upvar $machine machinedef set machinedef {} set first_name {} set maxarg [llength $states] for { set idx 0 } { $idx < $maxarg } { incr idx } { set arg [lindex $states $idx] switch -- $arg { "state" { set statename [lindex $states [incr idx]] set transitions [lindex $states [incr idx]] lappend machinedef $statename $transitions } "initialState" { set first_state [lindex $states [incr idx]] } default { } } } # # First three items are reserved: the initial state and the current # state. By storing them in the same list we can pass the # information around in any way needed. # set machinedef [concat $first_state $first_state $machinedef] } # evalMachine -- # Evaluate the input and go to the next state # # Arguments: # machine Name of the machine (a variable) # input The input to which to react # # Result: # None # # Side effects: # The machine's state is changed and the action belonging to the # transition is executed. # proc ::FiniteState::evalMachine { machine input } { upvar $machine machinedef set current_state [lindex $machinedef 1] # # Look up the state's transitions # set states [lrange $machinedef 2 end] set idx [lsearch $states $current_state] set transitions [lindex $states [incr idx]] set found 0 foreach {pattern newstate action} $transitions { if { $pattern == $input } { uplevel $action set found 1 break } } if { $found } { set machinedef [lreplace $machinedef 1 1 $newstate] } else { #error "Input ($input) not found for state $current_state" # Or rather: ignore } } # resetMachine -- # Reset the machine's state # # Arguments: # machine Name of the machine (a variable) # # Result: # None # # Side effects: # The machine's state is changed to the initial state. # proc ::FiniteState::resetMachine { machine } { upvar $machine machinedef set initial_state [lindex $machinedef 0] set machinedef [lreplace $machinedef 1 1 $current_state] } # # Define a simple machine to test the code: # A furnace that needs to keep the same temperature, so the heating # may be on or off # namespace import ::FiniteState::* defineMachine heater { initialState off state off { "too_cold" on { set heating $heat_capacity} } state on { "too_hot" off { set heating 0 } } } set time 0.0 set dt 0.1 set temp_amb 20.0 set temp $temp_amb set temp_ideal 200.0 set exch 0.3 set heating 0.0 set heat_capacity 500.0 while { $time < 10.0 } { evalMachine heater \ [expr {$temp<=$temp_ideal? "too_cold" : "too_hot" }] set time [expr {$time+$dt}] set temp [expr {$temp+$dt*($exch*($temp_amb-$temp)+$heating)}] puts "$time $temp $heating [lindex $heater 1]" } ---- ''[Theo Verelst]'' (who put ´anonymous´ here? I sure didn´t.) The formal definition of a finite state machine is that it has a countable number of (thus discrete) states, where it holds that the new state and output are computed from the old state with the inputs, which imo is relatively easy to program in any language: set state on proc newstate {input} { global state switch $state \ off {return "off"} \ on {if [string match $input "on"] {set state on} {set state off} } } newstate on puts $state newstate off puts $state Though of course not at all always easy to analyse. [Lars H]: The problem is seldom to encode the transition function, which is really all you did, but to use the finite state machine as a control structure. A '''goto''' command is in some sense the optimal (although not necessarily the most convenient) way to encode this, but in some languages that isn't easy to do. Also, your definition of a finite state machine is incorrect; ''countable'' allows the smallest infinite sets (such as that of the integers, or that of all finite words on a finite alphabet), but in a finite state machine the set of states must be (surprise?) '''finite'''. [Theo Verelst] Which goes to show you´re not a computer designer, in hardware, there is no such thing as the goto or whatever it is which executes the what you call state transition, there is a mapping between the current and the next state, and how you achieve the implemantation of that mapping could even be a ROM. Or of course and Arithmetic Logical Unit. Integers in tcl and computers are always bounded by word size, though I´d easily agree that it is interesting mathematically to make them a list and let imagination take over. A control structure. Hmm. The whole pentium or whatever CPU one uses, even when not a von Neuman, and possibly even when outside the broad turing machine boundaries, is full of logical circuits which can be interpreted as ´control structures´, which form the basis of the functioning of the processor, the software control structure, living at a higher level of agregation but a very much lower level of actual control choices being made per second, can be made or seen as one wants on the basis of what conditionals or pointer like structures one may want to apply from the instruction set. In that respect it is no doubt of interest to include direct referencing (say like in traps) or some mathematical construct to arrive at some piece of code or a single instuction, in an easy, cheap and overseeable way. Or a lookup table. Or list referencing, which I consider pleasing. The problem or limitation is that the FSM model is probably not the most natural to program in, and in its kind, which is suitable for message processing, it is limited, for isntance when faced with non determinate network problems, which it cannot formally resolve unambiguously or even define generally (like a petri net for instance). It is a design model which allows you to seperate state and functions, and the idea is that the state is known, and usually limited, and therefore overseeable. And that every transition is between two well defined states at well defined time instances. I guess it will be some time before our computers will have states which can cruise surfing Riemann surfaces somehow infinitely accurate. I think countable means just that, I wouldn´t say and integer number approaching infinity is countable, but I guess that is a matter of definition. Possibly even an interesting one. [AM] The mathematical definition of countable encompasses both finite and infinite sets. Discrete sets encompass both countable and incountable sets, as an example of the latter: consider the set obtained by removing all rational numbers from a finite-length interval of the real line. What you left with is a discrete, uncountable set. (I shamefully erased a remark about the Cantor set). [TV] 'Finite length interval' those words at least have a nice ring to it in the context.. - [AM] Quite intentional :) [TV] ''(18 Nov '03)'' Coming across this page because I do know where I'm going with fsm, process algebra and that in realm of software (and did so a decade ago at least, and about 3 decades ago about hardware, where the concept is commongood for the advanced), I can't agree to not making the remark that the above is like discussing the existence of distinquishable particles when pondering on the the existence of a Fock or Hilbert space. Appearently no expert speaking. [DKF]: Two points 1. '''goto''' is merely an artefact of the process of flattening a state graph onto linear memory. 1. It should be possible to map between a [Turing Machine] and any other state machine representation that admits an infinite state space of sufficient complexity. I think the "sufficient complexity" bit refers to the requirement to be able to represent more than a single non-negative number of arbitrary magnitude. ---- See also [A tiny state machine] which implements '''goto''' ---- [Trying FORTH in Tcl] - [Arts and Crafts of Tcl-Tk programming]