guile-smc

guile-smc copied to clipboard

• Guile-SMC [[https://github.com/artyom-poptsov/guile-smc/actions/workflows/guile2.2.yml/badge.svg]] [[https://github.com/artyom-poptsov/guile-smc/actions/workflows/guile3.0.yml/badge.svg]] [[https://github.com/artyom-poptsov/guile-smc/actions/workflows/guix.yml/badge.svg]]

[[https://www.gnu.org/software/guile/][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

• [[https://www.gnu.org/software/guile/][GNU Guile]], version 2.2 or later
• [[https://www.nongnu.org/guile-lib/][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
• [[https://www.gnu.org/software/help2man/][help2man]]

** Installation *** GNU Guix #+BEGIN_EXAMPLE shell $ guix install guile-smc #+END_EXAMPLE

Development version from =guix.scm=: #+BEGIN_EXAMPLE shell $ guix build -f guix.scm $ guix package -f guix.scm #+END_EXAMPLE

*** Manual #+BEGIN_EXAMPLE shell $ git clone https://github.com/artyom-poptsov/guile-smc.git $ cd guile-smc $ autoreconf -vif $ ./configure $ make $ sudo make install #+END_EXAMPLE

** 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:

#+BEGIN_EXAMPLE shell $ smc Usage: smc [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. #+END_EXAMPLE

*** The Context Generator =smc context= command performs two main tasks:

• Generate intermediate contexts for providing Guile-SMC API for custom code.
• Generate a context stub for a state machine based on a PlantUML file.

Here's the =smc context --help= output: #+BEGIN_EXAMPLE shell $ smc context --help Usage: smc context [options] [input-file]

Analyze or generate a context stub based on a given PlantUML file. If INPUT-FILE is not provided, than the command will read the standard input.

Options: --help, -h Print this message and exit. --resolve, -r Show resolved and unresolved procedures. --standalone, -s Generate a standalone compiler context. --type, -T Set the context type for the output context. Expected format: "[/]". Supported values: - oop - oop/generic - oop/port - oop/char - oop/u8 - functional - functional/generic - functional/char - functional/u8 --generate, -g Generate a context stub from a given PlantUML file. --guile-smc-path Set the path where Guile-SMC modules are stored.

                Default value:
                  /gnu/store/6j376x184g070383sxdzi775my9x081s-guile-smc-git/share/guile/site/3.0/

--module, -m Place the output code into a specified module --load-path, -L Add an extra load path. --log-driver Set the log driver. Supported values: - "syslog" -- use syslog as the logging driver. - "file" -- log to a specified file. Output files are rotated as needed. Options: "file" -- the full path to the log file. - "null" -- disable logging (discard all the messages.)

                Default value is "syslog"

--log-opt Set the logging options. The set of options depends on the logging driver. Format: "key1=value1,key2=value2" Example: "file=/tmp/smc.log"

                There's an option "stderr" that is handled independently
                from the log driver that allows to configure stderr logging.
                Example values:
                  "stderr=true"
                  "stderr=false"

--debug Enable the debug mode.

#+END_EXAMPLE

*** The Compiler The state machine compiler allows to compile state machines from a formal description (currently only PlantUML format is supported.)

#+BEGIN_EXAMPLE shell $ smc compile --help Usage: smc compile [options] [input-file]

The program reads a PlantUML transition diagram from an INPUT-FILE or the standard input if no file specified, and creates a finite-state machine (FSM) from the formal description.

Then the FSM can be validated and/or compiled.

If no INPUT-FILE is specified, then the input PlantUML transition diagram is read 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. --log-driver Set the log driver. Supported values: - "syslog" -- use syslog as the logging driver. - "file" -- log to a specified file. Output files are rotated as needed. Options: "file" -- the full path to the log file. - "null" -- disable logging (discard all the messages.)

                Default value is "syslog"

--log-opt Set the logging options. The set of options depends on the logging driver. Format: "key1=value1,key2=value2" Example: "file=/tmp/smc.log"

                There is an option "stderr" that is handled independently
                from the log driver that allows to configure stderr logging.
                Example values:
                  "stderr=true"
                  "stderr=false"

--load-path, -L Add a paths separated by a colon to load paths. --guile-smc-path The path to Guile-SMC modules.

                Default value:
                  /gnu/store/6j376x184g070383sxdzi775my9x081s-guile-smc-git/share/guile/site/3.0/

--modules, -U 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 Set the name for the output FSM. --fsm-module, -m Set the module for the output FSM. Example value: "(smc puml-fsm)" --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. --target, -t Compilation target. Allowed values: "guile", "guile-standalone" Default value is "guile". --debug Enable the debug mode.

#+END_EXAMPLE

Usage example: #+BEGIN_EXAMPLE shell $ cat fsm.puml | smc compile -L . -U "((context))" -m "(custom-fsm)" > custom-fsm.scm #+END_EXAMPLE

**** 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): #+BEGIN_EXAMPLE scheme (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)) #+END_EXAMPLE

*** The State Machine Runner The state machine runner allows to run a state in /ad hoc/ fashion with the minimum amount of supporting code:

#+BEGIN_EXAMPLE shell $ smc run --help Usage: smc run [options]

Run a state machine.

Options: --help, -h Print this message and exit. --eval, -e Eval a procedure with the resulting context as a parameter. Example value: "(lambda (context) (display context))" --load-path, -L Add an extra load path. --context-thunk, -C A thunk that produces the initial value for an FSM context. Example value: "(lambda () 0)" --modules, -U 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-driver Set the log driver. Supported values: - "syslog" -- use syslog as the logging driver. - "file" -- log to a specified file. Output files are rotated as needed. Options: "file" -- the full path to the log file. - "null" -- disable logging (discard all the messages.)

                Default value is "syslog"

--log-opt Set the logging options. The set of options depends on the logging driver. Format: "key1=value1,key2=value2" Example: "file=/tmp/smc.log"

                There is an option "stderr" that is handled independently
                from the log driver that allows to configure stderr logging.
                Example values:
                  "stderr=true"
                  "stderr=false"

--debug Enable the debug mode. #+END_EXAMPLE

Usage example: #+BEGIN_EXAMPLE shell $ smc run -L . -U "((context))" -C "(lambda () 0)" fsm.puml #+END_EXAMPLE

*** 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: #+BEGIN_EXAMPLE shell $ 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 %) #+END_EXAMPLE

*** Programming interface **** Compilation PlantUML (http://www.plantuml.com/) state machine compiler can be used from a Scheme code as follows: #+BEGIN_EXAMPLE scheme (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))) #+END_EXAMPLE

**** Validation #+BEGIN_EXAMPLE scheme (let ((fsm (puml->fsm (current-input-port))) (format #t "validation report:~%") (pretty-print (fsm-validate fsm))) #+END_EXAMPLE

** 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.

[[./doc/architecture.png]]

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 == 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

#+BEGIN_EXAMPLE scheme (list (list guard:some-guard action:some-action state1) (list guard:#t action:some-action state2)) #+END_EXAMPLE

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

• [[https://github.com/artyom-poptsov/guile-dsv][Guile-DSV]]
• [[https://github.com/artyom-poptsov/guile-ini][Guile-INI]]
• [[https://github.com/artyom-poptsov/guile-ics][Guile-ICS]]
• [[https://github.com/artyom-poptsov/guile-png][Guile-PNG]]

** Ideas to implement

• Write a PlantUML generator that take a == instance and produces a PlantUML state diagram.
• Produce a timing diagram based on FSM log output in [[https://plantuml.com/timing-diagram][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.