Links to thesis document and thesis defense slides.

• Implemented the digital watch assignment from MoSIS as an example.
• Created a library for integrating the runtime with an existing event loop implementation, making it run in "real time".
  The solution is truly generic, supporting multiple "wall clock time" functions and multiple event loop implementations. The motivations were:
  1. In my branch, of the core SCCD runtime uses integers for event loop timestamps. These integers can represent any unit (Planck time to current-age-of-the-universe's). The time unit used can be set in the model, or can be derived as the greatest common divisor of all duration values in the model (this is what happens when running the tests).
     (An interesting "feature" (or rather, absence of feature) is that the runtime itself will never measure wall clock time. Time only exists as a simulated value and is only advanced when told to do so. Any "real time" simulation (such as event loop integration) is therefore a layer around the core runtime.)
  2. In Python < 3.7, the recommended way to accurately measure wall clock time is the function "time.perf_counter()", which returns a float value with unit "seconds".
     Python 3.7 introduces a better function "time.perf_counter_ns()" which returns an integer of unit nanoseconds. We want to use this function if it is available.
  3. Event loop implementations (e.g. TkInter, or NodeJS/browser if we port the runtime to JavaScript) typically have a function to schedule future callbacks with a timeout value. The unit of this timeout depends on the implementation. TkInter uses milliseconds.
  It is clear that we want to do the following 2 conversions very often:
  1) Wall clock time unit -> SCCD's time unit, to always advance the simulation to the current wall clock time.
  2) SCCD's time unit -> event loop time unit, to schedule the next wakeup, when we are done advancing the simulation.
  The solution is to declare time functions, event loop implementation and their respective units in a common format, so the conversion factors can be calculated in advance.
  This allows us to automatically select the best Python time function for the platform, and new time functions or event loop implementations can be added if needed. A TkInter binding is included.
• Performance improvements to the transition execution code:
  • Generating the exited states-set is done by intersecting the current states-set and the transition arena descendants-set. Both are statically computed as bitmaps, so the intersection is a simple binary AND-operation.
  • The entered states-set is computed entirely statically in most cases. Only when one or more history states are part of the entered states-set, should the "history values" (= a set of states) for those states be looked up at runtime. It is statically known what history values have to be looked up for any transition, and the history values themselves are stored as bitmaps, so they can be joined with the statically known part of the entered set with a binary OR-operation.
  • Generating the history value when exiting a state with a history child is done by intersecting the set of exited states with the "history mask". The history mask is a statically computed bitmap of states that can be part a history state value. For a shallow history state, it consists of the direct children of the state. For a deep history state, it consists of all the descendants of the state.
  • When not setting the environment variable SCCDDEBUG, Python integers are used for bitmaps instead of our own Bitmap type (which is basically 'int' with an override for printing in binary format). This almost doubles transition execution speed. The reason is the overhead of function calls for our overrided binary operations.

New features:

• Action language:
  • User-defined functions (a function declaration is just a type of expression)
  • If-statements
  • After creating the AST, one "static analysis" visit of all nodes doing things like:
    • Determining the type of every expression
    • Determining the "return behavior" (always/never/some branches + return type) of every statement
    • Adding identifiers to the right scope if they serve as an LValue
    • Looking up identifiers in all scopes if they serve as an expression
  • New memory model, supporting recursion and function closures.
  • Added an interactive prompt app (just 30 lines of code!)
• Statecharts:
  • GC & RHS Memory Protocol semantic options from Day & Atlee
  • Multi-event triggers and negated event triggers
  • Event parameters
  • In/outport declarations with their events, closer to Yakindu's approach (will replace "port" attribute)
  • Statechart instances no longer execute big steps to "stabilize" (=execute eventless transitions if there are any) when there is no input.
  • Test suite: Added more examples from Day & Atlee

Technology:

• Another major revision of the XML parser for statecharts and tests, this time a more declarative, schema-like approach with order and multiplicity rules of XML elements.
• The action language modules no longer have any dependency on anything statechart-related. It could become a project on its own.
• Action language memory model: Stack frames are allocated on Python's heap (therefore garbage collected) and form 2 singly linked lists:
  • The list of "parents": the parent of a frame is the frame that will become the current frame when the current frame is popped. This is to support recursion.
  • The list of "contexts": if the current frame was pushed by a function call, the context of that frame is the frame in which the function was declared. In all other cases, the context frame is equal to the parent frame. This is to support closures. All variables that are nonlocal to a function's scope are looked up in the list of contexts.
  For statecharts, there are only 2 stack frames that exist before and after the execution of a transition:
  • The "builtin" stack frame, containing implementations for functions declared in the "builtin" scope.
  • The "instance" stack frame, containing variable values declared in the "instance" scope (the <datamodel> XML node of a <statechart>).
  During the execution of a transition, new stack frames can be pushed and popped. A transition, for instance, pushes a stack frame with the values of event parameters, similar to how a function call pushes values of function parameters.
  To support Memory Protocol semantic options, snapshots must be made such that reading a variable results in the value of that variable at the beginning of some round (small/combo/big step). Both the "builtin" and "instance" stack frames survive transition exuction, but we only have to make a snapshot of the "instance" stack frame since all names in the "builtin" scope are read-only.
  There is another interesting feature to the snapshotting: Although transitions may not immediately "see" each other's effects on the "instance" variables, it would be confusing if a transition would not see its own effects. Therefore, if a transition writes to an instance variable, all subsequent reads from that variable during the same transition execution will return the value that was written. To get this behavior, we keep a bitmap of offsets within the snapshotted frame that were written by the current transition. At the end of each transition, this bitmap is flushed to another bitmap, which represents the offsets that were written by transitions since the last "snapshot". Subsequent transitions within the same snapshot should never have overlapping write-bitmaps. If this is detected, a "race condition" exception is raised.
• In both the "action_lang" module and "statechart" module, there is perfect separation between a model and its execution. Each module has the following submodules:
  • module "static": Classes representing a loaded model. Their objects "freeze" (never change state) once loading the model is complete.
  • module "dynamic": Classes representing the current state of execution of a model. Objects from "static" serve as their input.
  • module "parser": Functions for parsing and loading a model. Depends on "static".
  Although currently a model is always generated by the "parse" module, it should be possible to construct models programmatically with the "static" module,, e.g. through a statechart designer GUI.
  Because a loaded model never changes state during execution, a single model can have multiple simultaneous (even parallel) executions.

Future work:

• Write thesis text!
• Add more examples from Day & Atlee
• Study YAKINDU's semantics and compare with ours
• Action language: It would be useful to detect statically if an expression evaluation or statement (or block of statements) execution can have side-effects, i.e. writes to the instance's memory. Use case: A guard condition evaluation should never have side effects.
• Action language: It should be possible to disable recursion and closures (to put an upper bound on memory usage and guarantee halting), and to statically detect whether a model has recursion or closures.
• Action language: Use Python's Language Services to "just-in-time compile" statements and expressions to "native Python" for a probably decent speedup. Combining this approach with running with PyPy (already supported by SCCD) would yield another speedup on top.

Screenshots of action language's interactive prompt:

static types

functions

scope hierarchy

recursion

closures

return type inference

See my branch: https://msdl.uantwerpen.be/git/simon/SCCD/src/joeri

New features:

• Compiler abandoned: no more generated Python code. From XML, an AST is constructed and executed directly.
• Action language. Parsed to AST. Interpreted at runtime
• Static type checking in action language with type inference
• Transition's "after" can be any expression evaluating to DurationLiteral. A DurationLiteral is an integer followed by a time unit (e.g. "ms")
• Added script that renders statecharts as SVG images (uses smcat)
• Testing framework: allow wildcards for semantic options. Will then generate tests for all possible combinations of values for the wildcards.
• Testing framework: new XML format. Statechart can be a separate file from the test.
• Testing framework: tests that must fail have filename starting with 'fail_'
• Loading errors display fragment of XML source code with error highlighted.

Internals:

• Using Lark parser to parse action code and transition target state references
• Implemented hierarchy of 'rounds' to deal with big/combo/small steps and their maximality semantics
• No explicit grouping of "conflicting" transitions for Priority semantics, instead assume order of generated candidates to be depth-first, giving correct behavior with less complexity, better performance
• New event-driven XML parser (basically an "event" is whenever an opening or closing XML tag is encountered). Can enable both more strict XML parsing and allow for more variation in document structure, if desired.
• Event names compiled to IDs within "model namespace"
• Bitmaps for sets of enabled events allow caching of transition candidates with quick lookup based on such bitmaps.
• 2 candidate generation algorithms (both with caching) to choose from
• Model delta (=smallest possible duration of simulated time in (integer) timestamp format) calculated based on all durations specified in the model, and by default a maximum of 100 microseconds

See my branch: https://msdl.uantwerpen.be/git/simon/SCCD/src/joeri

Next, will do:

• Disable spontaneous "stabilizing" of instances (=letting models with enabled eventless transitions execute big steps even if there is no input) in the controller event loop: Discussed this with Simon. Simon noted that this can cause starvation, and that YAKINDU also does not schedule big steps when there is no model input. The tests have a lot of eventless transitions, expecting "stabilizing" behavior, so they should be adapted too.
• Action language: Implement memory protocol semantic options from Day & Atlee paper.
• Action language: Implement different scopes for identifiers: local, global, builtin.

Doing some coding, mostly simplifying the SCCD runtime as a preparation for implementing the new semantic features. Progress can be tracked in my branch: https://msdl.uantwerpen.be/git/simon/SCCD/src/joeri

Here you can get my slides for the master students' mini-conference