Introducing Scdlang (Statecharts Description Language), a universal description language for defining State Machine

Repository

https://github.com/drsensor/scdlang

PR#3

About

Scdlang is a description language for describing Statecharts that later can be used to generate code or just transpile it into another format. Although the syntax itself inspired from text-based drawing (e.g mermaid or graphviz), this project is more focus on how to describe Statecharts universally that can be used in another language/platform rather than drawing a Statecharts diagram.

Motivation

Statecharts (or State Machine in general) has a lot of benefit ranging from modeling User Experience (UX) to NPC behavior. While it has a lot of benefits, each implementation is different and the only single-source-of-truth is the diagram itself. A visual diagram is great but it's time consuming when you want to refactor it (one of many reasons why visual programming not popular). As far as I know, there is 3 way to implement Statecharts model in the programming language:

Approach	Pro	Con
via key-value pair	fast (almost O(1))	cost more memory
via pattern-matching/switch-case/if-else statement	less memory	has runtime overhead
typestate	type-safe, fast, no memory overhead	only applicable on static type language that has generic type

Each implementation has its pros and cons which suitable depend on the context. For example:

• XState approach it via key-value pair,
• most of string matching implementation use FSM via switch-case + if-else statement,
• smlang-rs (Rust package) and GenStateMachine (Elixir package) approach it via pattern-matching
• Embedded programming in Rust mentioning about typestate for static guarantee
• Boost.SML under the hood use partial specialization of template (I'm still not sure if it's categorized as typestate programming or pattern-matching 🤔)

Hopefully (in the future), Scdlang can be used as a single source of truth to model a state machine regardless of the interpreter, platform, or programming language you use.

Features

This project is still in really early stage and it's a one-man show for several reasons. For now, this language can only be transpiled into XState format and only support Finite State Machine representation. Regardless of that, here is the current features:

Core features

Decent error messages

This description-language can produce beautiful error messages similar to Rust out of the box (thanks to Pest). Although Pest give me beautiful error messages for free, some adjustment needs to be done to make the error messages less confusing (see packages/core//error/format.rs). This adjustment is a never-ending process which I need to document on how to fine-tune that in the Contribution Guidelines.

_{Fig 1. error message on basic usage (Left & Center) | (Right) error message when code is piped from stdin}

As for the syntax highlighting, it handled using prettyprint and I only use it in the CLI layer. (I also contribute a bit on that package to make it fit into this project 😋)

Semantics analysis

Because Scdlang is a description-language (not programming-lang), it doesn't mean there is no need to add semantics analysis. This language needs to have semantics analysis because StateMachine and Statecharts have some caveats which most of them are related to a state transition. Currently, my only source about prohibited transition is in the OMG UML specification (it has more details than W3C SCXML spec).

For more info about the semantics error (still in draft), see files in the folder tests/fixtures/semantic_errors

_{Fig 2. Error message produced when it found semantical error}

Syntax overview

TL;DR see examples/simple.scl

• Support both //line and /*block*/ comments
• If not quoted, state and event name must be in PascalCase
• Supported quotes: single-quote ', double-quote ", backtick `
• Only names quoted with backtick will support newline
• Any pre-defined symbol support both direction, either left or right.
• Some symbol can be used for break-line. For example:

/*
bunch of expressions
*/
Z ---------------------------> A @ Reset

• Finally, it's easy to rename as a human language text:

It's not exactly a feature. I use this technique when choosing a symbol and designing fluent API

Short overview of the current syntax

Transient transition 👇

"get🆙" -> Walk

Eventful/Triggered transition 👇

On -> Off @ Shutdown

Reverse arrow 👇

On -> Off @ Toggle
On <- Off @ Toggle

CLI

For a new language, only having core functionality without having a tool to play around is a bit unexciting. So here I create the CLI to help me evaluate it in interactive manners. The CLI itself implemented using clap (without additional args-parsers-helper like Structopt or others). The CLI is called scrap which is stand for Statecharts Rhapsody (in respect to Rational Rhapsody). Currently, scrap has 2 main subcommands:

• scrap code|generate for code generation
• scrap eval|repl to enter REPL mode

This CLI is also pipe friendly which mean the output between interactive and non-interactive shell is different. This is useful when you want to log the error into a file or preprocess the results via stdout|>stdin.

_{Fig 3. Disable colored output when piped}

Transpile or Generate to others format

The essential feature of many compiler/transpiler is to output the result. In scrap code command, the output is base on --format flag as long as there is no syntax or semantic error. By default, it parses the whole file and outputs it as an XState format (in JSON). To parse it line-by-line, you need to provide --stream flag which also gives you the partial results.

_{Fig 4. Transpile scdlang code into XState config}

REPL

Ideally, when someone wants to showcase a new language, they will create a playground site (e.g playrust or smcat). Because I'm focusing this first implementation on CLI, I create a REPL feature instead of the playground site. The caveat is when someone wants to try this, they need to install the CLI first 😋.

_{Fig 5. How to use the REPL}

This REPL subcommand is also pipe friendly just like scrap code. The only differences are it always outputs line numbers when running on the interactive shell. It also can receive input from stdin when piped (see Fig 3.).

Technology Stack

• Project structure: polyglot monorepo
• Languages:
  • Rust (mainly)
  • Python (just for scripting to manage the project)

Current toolchains:

Description	Tools
Task runner	Justfile
Linter / Code checker	clippy, flake8 + mypy
Code formatter	rustfmt, black
Dependency manager	cargo, pipenv

Key Dependencies:

Dependency	Use on
Pest	core
clap	cli
serde	transpiler/*

CI infrastructure and benchmark strategies

The CI will play a big part in detecting bugs and performance degradation early on (hopefully). Currently, I'm using 2 CI service:

• Github Action for macro benchmark and running automated test
• Azure Pipeline for managing the release process

The CI configuration is still far from complete. A lot of things need to be done like publishing to package repository (e.g PPA, AUR, crates.io, etc) and others. At least this will help to do regression tests and quickly download the release binary without compiling it first.

As for what performance metrics I measure, I just measure the CPU Load and Peek Memory when parsing 1000 lines of Scdlang code without empty lines or comments (see Perf CLI release action). I also measure the build time in non-release mode because I need to be aware of which dependencies are bloated. Unlike Javascript, detecting bloated dependencies is not as simple as getting the bundle size. By measuring the compile time, I can guess when I add a bloated dependency by comparing the compile time of before and after I add it. It also gives me a clue about duplicated instantiation.

_{Fig 6. CI diagram for doing macro-benchmark on pull_request}

Ideally, continuous benchmarks should be run in the dedicated machine to achieve consistency.
Well, I just need it to be cheap 💸

Project layout and test strategies

This project currently separated into 3 modules:

Module	Description	Test strategy
cli	module that compiled into binary CLI	integration test
core	module that implements the core features	unit test
transpiler/*	bunch of modules to transpile Scdlang code into another format	unit test

Next step

• [compatibility] Transpile into the JSON format of State Machine Cat
• [syntax] Introduce symbol that can be expanded into multiple expression. (e.g On <-> Off @ Toggle)
• [cli] Pipe REPL output to another process.
  For example, pipe REPL output to state-machine-cat CLI to generate SVG image

scrap eval --format smcat --pipe-to 'smcat --input-type json [stdin] | open-in-browser'

Possible future development

• [😎] IDE support
• [🤔] Compile to another binary format (WebAssembly, LLVM, or GraalVM bytecode)
• [🤔] Support another state machine (or alike) interchangeable format that can be derived from statecharts. E.g Amazon Step Function, CI configuration, and maybe more.
• [🤔] Support another state machine variant by constraining which statecharts feature is enabled. E.g Behaviour Tree, Mealy Machine, Protocol State Machine, and maybe more. Statecharts is not the only one on how to approach Model Driven Development.

TODO

• Move some of the github actions into separate repository then publish it to Github marketplace for public consumption
• Add comprehensive documentation written in Asciidoc
• Publish to Github package manager (waiting to be accepted as a beta tester 😅)

How to contribute❔

I'm still figuring out how to document the project architecture and also on how to fine-tune and make some changes (especially for the error message). However, feel free to open a github issue if you have some ideas or feature requests.

Closing

In the beginning, I create this project just to evaluate Pest parser before I use it in another project (I need decent context-free grammar for data cleansing). In the experiment (see branch prototype), I make text-based drawing language as a problem that I want to solve. I also took a chance to play around with Github Actions and test the idea of storing custom metadata on each commit using git-notes (in this case I store the macro-benchmark results). Now I realize that seems I've gone too far drilling the problems 😂. I want to push this project forward and see what it will become 🥺.

The development of this project is kinda slow and less productive. Hopefully, Rust compiler and the type-checker will get faster while the language server consumes less memory over time 😢

Resources

• Statecharts in the Making: A Personal Account by David Harel (👈 recommended)
• State Machine Design pattern — When, Why & How
• Welcome to the world of Statecharts
• Fundamentals: why state machines?

GitHub Account

https://github.com/drsensor