Guile-SMC
GNU Guile state machine compiler.
License
Guile-SMC is free software: you can redistribute it and/or modify it under the
terms of the GNU General Public License as published by the Free Software
Foundation, either version 3 of the License, or (at your option) any later
version. Please see COPYING
file for the terms of GNU General Public
License.
Requirements
- GNU Guile, version 2.2 or later
- Guile Library
Build-time dependencies
- GNU Guile development files (something with
dev
suffix, e.g.guile-3.0-dev
on Ubuntu GNU/Linux) - texinfo
- make
- automake
- autoconf
Installation
From package managers
Manual
$ git clone https://github.com/artyom-poptsov/guile-smc.git $ cd guile-smc $ autoreconf -vif $ ./configure $ make $ sudo make install
Quick start
NOTE: To read the full Guile-SMC documentation run info guile-smc
Although Guile-SMC API can be used from a Scheme code, it comes with smc
tool that allows to compile, run and profile state machines from the shell:
$ smc Usage: smc <command> [options] Commands: compile Compile a PlantUML state diagram to a Guile finite-state machine. context Analyze or generate a context stub based on a given PlantUML file. run Read a finite-state machine from a specified PlantUML file and run it right away. profile Run the state machine profiler. help Print this help message. For each command there's '--help' option (or '-h' for short) that prints a help message for the given command.
The Compiler
The state machine compiler allows to compile state machines from a formal description (currently only PlantUML format is supported.)
$ smc compile --help Usage: smc compile [options] The program reads a PlantUML transition diagram from the standard input. Options: --help, -h Print this message and exit. --print-transition-table, -p Print the FSM transition table to the standard output. --load-path, -L <paths> Add a paths separated by a colon to load paths. --modules, -U <extra-modules> Load additional modules. The value must be the same as for 'use-modules'. Example value: "((smc context char-context) (smc puml-context))" --fsm-name, -n <name> Set the name for the output FSM. --fsm-module, -m <module> Set the module for the output FSM. Example value: "(smc puml-fsm)" --target, -t <target> Compilation target. Allowed values: \"guile\", \"guile-standalone\", \"guile-standalone-copy\" --validate Validate the output FSM and print the validation result. The exit code is 0 if the validation is passed, and a non-zero value otherwise. --debug Enable the debug mode.
Usage example:
$ cat fsm.puml | smc compile -L . -U "((context))" -m "(custom-fsm)" > custom-fsm.scm
Targets
guile
The default compilation target. The code produced by the compiler for this target is dependent on the Guile-SMC.
guile-standalone
This compilation target produces GNU Guile FSM code in a single file that does not dependent on Guile-SMC.
All required Guile-SMC procedures will be copied to the output stream, and the extra procedures that are not used in the output code are removed by pruning.
Here’s an example of an output FSM (without the auxiliary code copied from Guile-SMC that normally goes before this procedure):
(define (run-fsm context) "" (define (DEFAULT context) "Count parenthesis." (let ((event (event-source context))) (cond ((guard:eof-object? context event) (let ((context (action:validate context event))) (log-debug "[~a] -> [*]" 'DEFAULT) context)) ((guard:semicolon? context event) (let ((context (action:no-op context event))) (log-debug "[~a] -> [~a]" 'DEFAULT 'COMMENT) (COMMENT context))) ((guard:double-quote? context event) (let ((context (action:no-op context event))) (log-debug "[~a] -> [~a]" 'DEFAULT 'STRING) (STRING context))) ((#{guard:#t}# context event) (let ((context (action:count context event))) (DEFAULT context)))))) (define (STRING context) "Skip a string." (let ((event (event-source context))) (cond ((guard:double-quote? context event) (let ((context (action:no-op context event))) (log-debug "[~a] -> [~a]" 'STRING 'DEFAULT) (DEFAULT context))) ((#{guard:#t}# context event) (let ((context (action:no-op context event))) (STRING context)))))) (define (COMMENT context) "Skip a comment." (let ((event (event-source context))) (cond ((guard:newline? context event) (let ((context (action:no-op context event))) (log-debug "[~a] -> [~a]" 'COMMENT 'DEFAULT) (DEFAULT context))) ((#{guard:#t}# context event) (let ((context (action:no-op context event))) (COMMENT context)))))) (DEFAULT context))
guile-standalone-copy
The compiler can be configured in such way that it will copy all the modules that are needed to run the output FSM so the FSM will not depend on Guile-SMC.
For example, let’s imagine that we have the following file set:
. ├── context.scm ├── fsm.puml ├── main.scm └── README.org 0 directories, 4 files
The context.scm
contains all actions, guards and event sources for FSM to run:
(define-module (context) #:use-module (opp goops) #:use-module (ice-9 textual-ports) #:use-module (smc context char-context) #:re-export (guard:#t guard:semicolon? guard:double-quote? guard:newline? guard:eof-object? action:no-op) #:export (event-source action:count action:validate)) (define-method (event-source (ctx <number>)) (get-char (current-input-port))) (define (action:count ctx char) (cond ((char=? char #\() (+ ctx 1)) ((char=? char #\)) (- ctx 1)) (else ctx))) (define (action:validate ctx char) (unless (zero? ctx) (error "Parenthesis mismatch" ctx)) ctx)
The fsm.puml
file contains the FSM description:
@startuml [*] --> DEFAULT DEFAULT: Count parenthesis. DEFAULT --> [*]: guard:eof-object? -> action:validate DEFAULT --> COMMENT: guard:semicolon? DEFAULT --> STRING: guard:double-quote? DEFAULT --> DEFAULT: guard:#t -> action:count COMMENT: Skip a comment. COMMENT --> DEFAULT: guard:newline? COMMENT --> COMMENT STRING: Skip a string. STRING --> DEFAULT: guard:double-quote? STRING -> STRING @enduml
Now let’s compile the FSM, using the “guile-standalone” target:
$ cat fsm.puml | /usr/bin/smc compile -L . -U "((context))" -m "(custom-fsm)" \ --target guile-standalone-copy > custom-fsm.scm
Now the project root directory looks like this:
$ tree . ├── context.scm ├── custom-fsm │ ├── context.scm │ └── smc │ ├── context │ │ ├── char-context.scm │ │ └── context.scm │ ├── core │ │ ├── common.scm │ │ ├── log.scm │ │ ├── stack.scm │ │ ├── state.scm │ │ └── transition.scm │ └── fsm.scm ├── custom-fsm.scm ├── fsm.puml ├── main.scm └── README.org 4 directories, 14 files
custom-fsm
directory contains all the required Guile-SMC modules that the
output FSM needs to run, plus the extra modules (like (context)
) specified
for the compiler.
The State Machine Runner
The state machine runner allows to run a state in ad hoc fashion with the minimum amount of supporting code:
$ smc run --help Usage: smc run [options] <puml-file> Run a state machine. Options: --help, -h Print this message and exit. --eval, -e <procedure> Eval a procedure with the resulting context as a parameter. Example value: "(lambda (context) (display context))" --load-path, -L <load-path> Add an extra load path. --context-thunk, -C <procedure> A thunk that produces the initial value for an FSM context. Example value: "(lambda () 0)" --modules, -U <modules> Load additional modules. The value must be the same as for 'use-modules'. Example value: "((smc context char-context) (smc puml-context))" --validate Validate the output FSM and print the validation result. The exit code is 0 if the validation is passed, and a non-zero value otherwise. --log-file <file> Log file to use. Pass "-" as the file to use the standard error stream (stderr.) 'smc run' logs to syslog by default. --debug Enable the debug mode.
Usage example:
$ smc run -L . -U "((context))" -C "(lambda () 0)" fsm.puml
The Profiler
The profiler allows to analyze state machines using its logs (traces) and thus provides facilities to detect bottlenecks in state machines in terms of running time:
Usage example:
$ smc profile fsm.log Total transitions: 99 Total time: 14925 us Stats: read: 3158 us (21.1591 %) read_state_transition_guard: 1663 us (11.1424 %) read_state_transition_to: 1483 us (9.9363 %) read_word: 1259 us (8.4355 %) read_state_description: 1014 us (6.7940 %) read_state_right_arrow: 839 us (5.6214 %) search_state_transition_to: 670 us (4.4891 %) search_state_transition: 638 us (4.2747 %) read_state_transition_action: 536 us (3.5913 %) read_start_tag: 535 us (3.5846 %) search_state_transition_guard: 428 us (2.8677 %) read_state: 178 us (1.1926 %) search_state_transition_action: 139 us (.9313 %) read_state_action_arrow: 139 us (.9313 %) search_state_action_arrow: 132 us (.8844 %) read_end_tag: 125 us (.8375 %)
Programming interface
Compilation
PlantUML (http://www.plantuml.com/) state machine compiler can be used from a Scheme code as follows:
(let ((fsm (puml->fsm (current-input-port)))) (format #t "output fsm: ~a~%" fsm) (format #t "transition table:~%") (pretty-print (hash-table->transition-list (fsm-transition-table fsm)) #:display? #t)))
Validation
(let ((fsm (puml->fsm (current-input-port))) (format #t "validation report:~%") (pretty-print (fsm-validate fsm)))
Architecture
We won’t discuss the system architecture in depth in this short manual (please
refer to info guile-smc
for details.) Nevertheless, it’s good to have
overall picture of the system main concepts.
Internally a state machine represented by a hash table and a directed graph. A hash table is used to keep track of all the states in a FSM that enables fast state searching by a state name.
A directed graph is produced by the fact that each state keeps references to all the states it can transition too.
There’s also a reference to the current state of a FSM inside an <fsm>
instance; this reference changes each time the FSM transitions to a new state.
Transition table
Each state holds a transition table in a form of
(list (list guard:some-guard action:some-action state1) (list guard:#t action:some-action state2))
When state-run
method is called on a state, the state loops over its
transition table and applies each transition guard to the incoming event and
current context. When a guard returns #t
, the state applies a related
transition action to the event and the context and returns two values: a
reference to the next state (or #f
when the final transition is performed)
and a new context returned by the action procedure.
Usage examples
Guile-SMC can generate a FSM from the PlantUML format that reads a FSM in the
PlantUML format – see examples/pumlpuml.scm
.
Also see other examples the examples
directory.
Projects that use Guile-SMC
- Guile-INI: https://github.com/artyom-poptsov/guile-ini
Ideas to implement
- Write a PlantUML generator that take a
<fsm>
instance and produces a PlantUML state diagram. - Produce a timing diagram based on FSM log output in PlantUML format. That
would help with analyzing and optimizing an FSM. It could be implemented in
the
smc
compiler as part of state machine benchmark suite. - It is possible to add compilation to other languages aside from Scheme, but it will be quite hard to implement indeed.
- Add standalone-mode for the FSM compiler that will produce state machines independent from Guile-SMC.