Advanced Sequencer Design Discussion

[timcanham]

This call for comments discussed the implementation of a new "advanced" sequencer that would be another sequencing option alongside the simple legacy sequencer.

Description

The primary goal of an advanced sequencer is to supply new features to the sequencing set that fall outside of the legacy sequencer's capabilities. The sequencer is a component designed to execute a command Sequence.

Sequences are composed by a set of Statements where each statement is executed in order. Statements are either Commands used to dispatch a component command or Directives used to influence the sequencer itself.

The sequencer also has access to variables used to execute a sequence.

Variables

This advanced sequencer will have concept of three types of variable. These variables will be implemented as the type Fw.PolyType that stores both the type and value.

Local Variables (LVARs)

There will be a fixed number of local variables. These variables are owned by a given command sequencer and may only be set by the owner. All operations (compare, arithmetic, etc) are performed on these local variables. Other variables must be pulled into a local variable before being operated on.

Local variables act like a register file.

The first N local variables are reserved for special value storage.

Index	Use	Description
0	Previous statement status	Stores Success, Failure, or Error for the previously executed statement

Global Variables (GVARs)

Global variables are stored in an external global variable store. These variables are designed for use between a set of command sequencers. Global variables must be loaded into a local variable before use.

System Variables (SVARs)

System variables are stored in an external variable store. These variables are designed to be set by a system's components. System variables use a designated project-configurable enumeration to represent them. System variables must be loaded into local variables before use.

Requirements

These requirements are broken into several sections:

1. Feature Parity: features required to be able to operate at the same level as the legacy sequencer.
2. Basic Extensions: features that add in local variables, system variables, branches, and basic arithmetic.
3. Global Extensions: features for using global variables, and pre-setting locals.
4. Operations Extensions: features extending operations on local variables

Requirement	Description	Rationale
Feature Parity
SVC-ADVSEQ-001	The sequencer shall read a binary encoded sequence file
SVC-ADVSEQ-002	The sequencer shall be supported by ground side tools	Tooling is required to generate the binary file format
SVC-ADVSEQ-003	The sequencer shall dispatch commands	Allows
SVC-ADVSEQ-004	The sequencer shall support sequence directive WAIT	Allows waiting relative times
SVC-ADVSEQ-005	The sequencer shall support sequence directive WAIT_UNTIL	Allows waiting to absolute times
SVC-ADVSEQ-006	The sequencer shall support sequence directive ABORT_ON_FAILURE <true|false>	Allows exiting on statement failure
Basic Extensions
SVC-ADVSEQ-007	The sequencer shall support sequence directive ABORT <status>	Allows exiting
SVC-ADVSEQ-008	The sequencer shall support sequence directive LABEL <label>	Anchors a goto
SVC-ADVSEQ-009	The sequencer shall support sequence directive GOTO <label>	Jumps to label
SVC-ADVSEQ-010	The sequencer shall support sequence directive LVAR_SET_<I8,I16...,U8,U16...,F32,F64,BOOL>, <local index>, <literal value>
SVC-ADVSEQ-011	The sequencer shall support sequence directive EQUAL, <local output index>, <local index>, <local index>
SVC-ADVSEQ-012	The sequencer shall support sequence sequence directive GREATER, <local output index>, <local index>, <local index>
SVC-ADVSEQ-012	The sequencer shall support sequence directive LESS, <local output index>, <local index>, <local index>
SVC-ADVSEQ-013	The sequencer shall support sequence directive CAST, <local output index>, <local index>, <new type>
SVC-ADVSEQ-014	The sequencer shall support sequence directive ADD, <local output index>, <local index>, <local index>
SVC-ADVSEQ-015	The sequencer shall support sequence directive MUL, <local output index>, <local index>, <local index>
SVC-ADVSEQ-016	The sequencer shall support sequence directive AND, <local output index>, <local index>, <local index>
SVC-ADVSEQ-017	The sequencer shall support sequence directive OR, <local output index>, <local index>, <local index>
SVC-ADVSEQ-018	The sequencer shall support a special local varibal of "last status"
SVC-ADVSEQ-019	The sequencer shall support difrctive IF <local index>
SVC-ADVSEQ-020	The sequencer shall support difrctive ELSE IF <local index>
SVC-ADVSEQ-021	The sequencer shall support difrctive ELSE
SVC-ADVSEQ-022	The sequencer shall support difrctive END_IF
SVC-ADVSEQ-023	The sequencer shall support sequence directive SVAR_LOAD, <local index>, <svar enum>
Global Extensions
SVC-ADVSEQ-024	The sequencer shall support sequence directive GVAR_SET_<I8,I16...,U8,U16...,F32,F64,BOOL>, <local index>, <literal value>
SVC-ADVSEQ-025	The sequencer shall support sequence directive GVAR_SAVE, <local index>, <global index>
SVC-ADVSEQ-026	The sequencer shall support sequence directive GVAR_LOAD, <local index>, <global index>
SVC-ADVSEQ-027	The sequencer shall support parameterized sequences by loading local variable before executing
Operations Extensions
SVC-ADVSEQ-028	The sequencer shall support sequence directive SUB, <local output index>, <local index>, <local index>
SVC-ADVSEQ-029	The sequencer shall support sequence directive GREATER_EQUAL, <local output index>, <local index>, <local index>
SVC-ADVSEQ-030	The sequencer shall support sequence directive LESS_EQUAL, <local output index>, <local index>, <local index>
SVC-ADVSEQ-031	The sequencer shall support sequence directive EQUAL_FP <local output index>, <local index>, <local index>, <epsilon>
SVC-ADVSEQ-032	The sequencer shall support sequence directive DIV, <local output index>, <local index>, <local index>
SVC-ADVSEQ-033	The sequencer shall support sequence directive NOR, <local output index>, <local index>, <local index>
SVC-ADVSEQ-034	The sequencer shall support sequence directive XOR, <local output index>, <local index>, <local index>

Consider named arguments (alias) to local variable.

[zimri-leisher]

Notes from meeting:
Should sequences be able to access TM? Conclusion: we won't make this decision for you. Just assume some VariableStore backend exists

• The component would publish TM as a variable
• Internal type would be a polytype
• Potentially allow for user to change what values polytype can store
• Okay--decouple discussion: build a "SystemVariableStore" which can have any backend. Could be based on TM, could be separate, we don't make that decision at the moment

Two types of cmds in a sequence

• Traditional cmds
• Sequencer directives
• Directives are meta commands
• Both are a subtype of a sequencer statement

Other notes

• Abort returns a value---maybe ABORT should be called RETURN? We want to plan ahead for having procedures.
• variables stored as strings? not at the start--this is syntax sugar
• how to handle errors:
• have to have a special variable that's the last return status
• may want to reserve a few local variables at start of local var array
• Next meeting--I will make a second pass on requirements, then we will go into design

Overall thoughts:
We are building two languages here. One is a "sequence bytecode" which is low-level, easy to implement, hard to write. The other is a "sequence script" which is high-level, hard to implement, easy to write. The trick is that we have to write the sequence bytecode in such a way that it can still reasonably be written by hand, because it must be able to exist in isolation. This means we must simultaneously prioritize A) making the sequence bytecode suitable for implementing a high level language on top of it and B) making the sequence bytecode human readable and writable. The implication is that there will have to be some syntactic sugar, even in the sequence bytecode, that isn't strictly speaking necessary for the sequence scripts.

[zimri-leisher]

Taking inspiration from here:
https://en.wikipedia.org/wiki/List_of_Java_bytecode_instructions
and here:
https://max.rocketlabusa.com/docs#MAX/Sequencing/FlightJAS.md

[zimri-leisher]

Big question: do we want to have a stack?

[SterlingPeet]

I am not quite sure how to engage with this, because it feels like there is a lot of contextual information that is missing from the discussion post. That is ok, as the option is here, I will list some comments and if they are already covered in a reformulation of some sort, great!

1. The link to FlightJAS is great, you are ahead of me because I would have brought it up otherwise.
2. The most basic concern is reasonable branching; highly automated systems need to be able to select execution paths, even in a safe-mode scenario.
3. Composability: It seems desirable to be able to dynamically run different sequences, potentially within a sequence. It would be reasonable to limit the frame depth in a configurable way, perhaps to 4 or 8 by default.
4. Very small systems should be able to run bytecode-only, debug symbols in this scenario could be compressed to look like assert file hashes as already implemented. With good tooling, built in strings might be unnecessary anyway.
5. Breakpoint or stack-trace analogous support would be very useful for debugging and forensics.
6. Supporting triggers that start an independent sequence could also be very interesting, and would support concepts that resemble potentially complex automations.

[LeStarch]

@zimri-leisher @SterlingPeet I added context and basic tiers for this effort.

[zimri-leisher]

I think SVC-ADVSEQ-024 should say global index instead of local index

[zimri-leisher]

We have explicit support for a rudimentary form of arguments for sequences (parametrized sequences). I think we should also have explicit support for a rudimentary form of return values, so people can approximate function calling. Any thoughts?

[Joshua-Anderson]

From what I saw from my operational experience, there were a lot of strong justifications for parameterized sequences, since they allows operators to uplink re-usable sequences (I.E. call the take an image sequence instead of uplinking 50 commands to take an image). On the occasions where that the sequence needed to share state, they would set a global value that other sequences could check. A return value would have been more elegant, but they were needed rarely enough that they didn't seem to be missed.

The philosophical question in my mind is that there's good embedded interpreted/bytecode compiled programming languages out there (i.e. LUA variants, micropython, linux BPF, forth), and at what point does it potentially make sense for F' to use an existing language for sequencing instead of developing something from scratch. I think if the main goal is basic conditional logic it's probably a smoother patch to start to scratch, but if the the desired goal starts to grow beyond that to something more powerful, it may be worth looking to see if there's existing languages that could be leveraged instead, at the cost of maybe slightly less efficient sequence bytecode formats.

I think as part of this effort to design the new sequencing language I would encourage defining philosophies for what belongs in this sequencing language vs the flight software vs encouraging folks to sequence in some interpreted language like LUA

[zimri-leisher]

Yeah, it makes sense that return values would be pretty rarely used.

To your second point: we should probably do a trade on the different options here. I am not against using an already existing language, but there will be some downsides--memory usage like you mention, but also a general decoupling from the FPrime model/system that might mean we would have to change them significantly anyways (for instance, to support syntax checking for commands). The upsides would include: faster time to development, probably more features.

Of all the variants, I would be most interested in micropython, so I will look into it.

I made a post on the philosophy of what goes in a sequence vs FSW a while ago. My current thought is that sequences really should be for the highest-level of the FSW--usually decision making, fault response, things that you might want a human involved in.

[timcanham]

The "return value" we've used in the past is the pass/fail of the sequence, so you can at least signal to a calling sequence that waits that it worked or didn't.

[Joshua-Anderson]

Another interesting reference:

• Commanding the James Webb Space Telescope using event-driven operations software
  
• Event-driven James Webb Space Telescope operations using on-board JavaScripts
  (2006)

The James Webb team uses an isolated and embedded javascript runtime to command the vehicle by building and sending CCSDS space packets to the flight software

[zimri-leisher]

Very interesting... if it's good enough for JWST it seems like it should be good enough for FPrime. I will read the papers and see if they have any feedback on that system. I should note--I dislike Javascript a lot and would prefer Python were we to do this.

[zimri-leisher]

Summary of the second paper

Here are some of their requirements:

"Out of about a dozen initial candidates, four were selected for prototyping: TCL (open source), JavaScript (ScriptEase 5.00e by Nombas), Python 1.5.2 (open source), and a custom-made “G-Script” language"

"TCL was dropped from the study when it could not be
successfully ported to VxWorks. G-script received the lowest score due to its limited functionality, its awkward syntax, and the increased cost that would be needed for development and maintenance of a custom scripting language."

"JavaScript was fully compatible with VxWorks with extremely little modification and JavaScript could be embedded within the payload flight software using a much simpler interface than Python required. The Python port also exhibited memory leaks, and already was quite old."

Here are all the extra features added to JavaScript:

Section 4.2 is worth reading in its entirety

"Function return values are used to communicate status between script levels. "

[zimri-leisher]

Notes from meeting 9/17/24:

Pre existing versus rolling our own:

• Starch is leaning towards using a pre-existing language
• Zimri likes that but is worried about not being able to make guarantees about resources--memory allocation in micropython/lua?? runtime/scheduling?? exception handling??
• Starch says that sequences probably don't have as strict timeliness requirements so that's not as big of a problem
• Starch sees on the horizon: building schedulers and sequences in already existing languages is going to be more valuable. "people in JPL sequencing areas are saying they want to use Python"
• Also note: Research community is doing autonomy, advanced autonomy, etc and it's ALL in Python
• Looking for @timcanham and @Joshua-Anderson thoughts on Python scripting for FPrime.
• Are you aware of any alternatives to Micropython?
• Zimri will try to start working on testing Micropython with FPrime
• Starch is trying to get funding for autogen Python bindings for C++ component code--very likely to be relevant
• Big issue: Vxworks support for Micropython?? If Micropython doesn't have Vxworks support, then we might not be able to use it
• https://forum.micropython.org/viewtopic.php?t=2660 <-- Embedding Micropython in Vxworks
• https://github.com/LeStarch/fprime-python <-- relevant attempt by Starch to bind Python to FPP C++
• https://github.com/kuhlenough/cpython-for-VxWorks <-- other attempt to get python working in Vxworks

Working groups

• Zimri suggests making an open source working group where everyone can join weekly calls about this
• Starch says not sure what the rules are. Action to follow up on this @LeStarch

[timcanham]

Python in any form would be an extremely hard sell for the class B projects, because of
dynamic memory etc.
It doesn't matter that it is background, no dynamic memory is still a rule.
I think we would lose a lot of credibility suggesting it.

My opinion is that the simple syntax we had come up with is sufficient. The JavaScript option sounds interesting since JWST selected it as a class B project, but I think we should do the simpler one for our first class B implementation.

[SterlingPeet]

My understanding of the JWST Javascript was that it did not pan out to be as easy to integrate as they hoped. I have not noticed a lot of publications about it beyond 2010, which seems telling in and of itself. I wonder if the people who worked on it would claim it would be worth doing again, should they be starting with a clean slate.

I am in favor of whatever gets us to Turing complete, without going crazy with onboard features. Too simple, and it is what we already have, too complicated and it is hard to get there or a hard sell outside this community.

[SterlingPeet]

To be clear: I am not against Python integration, I think that has its own value. I just don't think that is the general solution that will be acceptable to all interested parties.

[zimri-leisher]

@timcanham what if we could "reserve" a certain amount of memory for Micropython? I think that might be possible. It would still technically make calls to dynamic allocation but it would be bounded.

[timcanham]

It's an interesting idea, but I wouldn't want to put it forward as our first proposal to flagship missions. It would be a cool addition to fprime-community.

[ReggieMarr]

Would this have any cross over with the mbse discussion from a while back ?
It seems to me that the effort to enable state machine modelling with qm and plantuml and specifying flight/mission sequences using a high level language like what is discussed here operate within seperate but related spaces.

This might be putting the cart before the horse but I'm curious if there's been cohesive thought behind how these two components might compliment each other and if there's any coordination between the two efforts.

[vietjtnguyen]

I think it's interesting to look at this from the other direction: what are the constraints and limitations we want to impose? If sheer functionality is what you want consider this thought experiment. What is "sequences" were just compiled runtime loadable libraries that are built against flight software. You make things you want to access globally accessible so they're accessible by the "sequence library". You can do this by removing the anonymous namespace on the global component instances and make those symbols available via a header with extern declarations. Then you compile your "sequence" as a dynamically loadable library (with some well defined entry point) that literally accesses variables on the component instances and can call functions (like command handlers) on the components (with some API sugar to make it nicer from the "sequence software" perspective). Then you send these "sequences" and have a subsystem to "execute" them by dynamically linking them (dlopen) and calling the entry point.

To me this represents the unbounded solution: maximum functionality with high software fidelity and interop with FSW. If that doesn't sound right then there's some unspoken constraint or limitation we want to impose. Capturing those will help identify a solution.

That said I think this kind of capability is great to have anyhow. Maybe you could do the same but use something like Cython to write it in a Python-like language (actually this is kind of non-starter because if you use Python objects you'll end up needing the Python C API).

[timcanham]

I could see how in a Linux environment that could be a power-user feature, but dlopen isn't available on many non-*nix platforms. Also, F Prime is designed to internally hide the command interfaces for encapsulation, so the commanding interfaces at least are not available as public interfaces. The command ports are, but you would have to manually assemble commands to invoke them.

The limits we want to impose are those that are defined by the flight/ground interface. That's our contract with the ground. There are workarounds like the shell command for Svc/FileManager, but the nominal case is that we interact via commands and telemetry.

[zimri-leisher]

I like this response a lot. It helps to clarify what the whole point of sequences are. They should be executable, they should be separate from the FSW binary, and they should interact with the FSW only via commands and telemetry. They also do not need to have as precise performance requirements as FSW code.

[zimri-leisher]

If we don't want to use a real Python interpreter due to memory allocation concerns, what if instead we just used the abstract syntax tree of Python and compiled that into our own bytecode format? Python exposes the syntax tree quite nicely.

This would give us the benefit of familiar and easy Python syntax, as well as avoiding having to write our own lexer and AST generator.

[timcanham]

Give an example of a simple sequence using Python syntax.

[zimri-leisher]

python_test_sequence.fpy

def run_thermal_response():
  powerManager.TURN_OFF_BATTERY_HEATER()

if componentName.temp_sensor > 32:
  thermalComponent.SET_HEATER(0)
  run_thermal_response()

for i in range(0, 100):
  cmdSeq.CS_RUN("/test/sequence/path.bin", 1)

It would support extremely basic Python features, each of which would have to be "translated" into our own bytecode. You would not be able to write arbitrary Python.

[zimri-leisher]

We could even leverage the already existing fprime integration testing library for some of this, like the dictionary parsing and serialization of commands.

[Joshua-Anderson]

Using a subset of python for the user friendly sequencing language could be useful - that can speed up development by utilizing existing parser / python tooling / test frameworks / IDE support and could avoid some of the investment required to create a new language.

This suggestion reminds me a bit of Starlark, a custom python-subset language that google built as their DSL for the bazel build system. Very different application, but some similar constraints. They needed a capable DSL to provide the capabilities they desired in a build system, but wanted to provide a familiar language to users... not sure how much of the tooling of the python ecosystem they take advantage of.

[zimri-leisher]

Meeting notes 9/23/24

On Micropython:

• Tim says the big projects won't like the word Python--they will be suspicious of running any sort of Python interpreter. "we'd start out at a skeptical disadvantage"

On using Python syntax:

• Michael says: If we use Python syntax, if in the future we want to use Micropython, there's some synergy. But settling a class-B project on flying Python is just not going to work. The trick is that one set of customers (research, etc etc) is moving one way, and big class-B is moving the other way
• Tim says that if we get the syntax similar enough, then we could swap in a Micropython backend. Perhaps could run it just in an instrument payload. Once people get used to using Python syntax, they might want to switch over.
• Zim says, okay great, let's go more into this Python syntax. Remember: 99.9% of the python stdlib will be unusable
• Tim says--don't start with functions. Just start with a "main" script with no procedures
• Michael says: start with "if statements", "for loops", "lists" and "local variables", "ability to interact with other system"
• Tim says--"globals", "locals".
• Zim is arguing for natively supporting telemetry in the script.
• Talking about how to get telemetry from the tlmpacketizer
• Michael says "natively reading from telemetry fits into standard computer practice: don't write the same code twice"

Draft release plans:

• Tim says should have a little mini release plan, what features do we want in each release?
• 0.1 would be basic syntax down where we're able to execute commands. Reproduce existing sequences
• 0.2 conditionals on command failure and goto
• 0.3 telemetry access
• Tim says @zimri-leisher should come up with a proposal schedule on this
• @timcanham notes: if you have any objections or see any fatal flaws with the Python syntax tree plan, please comment on this!
• @LeStarch says implication of this plan is that the requirements above will change, because we're starting with the higher level language. What we should start with is the "level 4 requirements--what behavior do we want?"
  • Reqs: want Python like syntax
  • Want to be able to send commands
  • Telemetry reading
  • Basic programming constructs (local vars, for loops, if statements)

Diving in deeper on callign cmds:

• Michael: how are you going to call cmds in this syntax?
• Tim and Zimri say we should just do "componentName.cmdName"
• Tim says that we could just use the template classes to come up with the notation
• We should generate an autocoded Python header file which allows for syntax completion

[zimri-leisher]

• @timcanham says that he will ask around for a JPL sequencer bytecode format that we might be able to copy
• Michael notes that Python also has a bytecode, could look at that: https://docs.python.org/3/library/dis.html#bytecodes

[zeroping]

Lua is often used for embedding into larger projects, and I know it was previously mentioned here. Would large projects be any more accepting of Lua over Python? (Smaller codebase, simpler language, maybe just less existing bias?)

[zimri-leisher]

The key issue is dynamic memory allocation. I haven't looked but I would think it's unlikely that a version of Lua without dynamic allocation exists.

[zimri-leisher]

Release plan table:

Release number	Description	Time Estimate
0.1	Same functionality as existing command sequences. A specification of the high level file. A compiler to the bytecode. A new sequencer.	2025-01-01
0.0.1	A specification of the high level file.	2024-10
0.0.2	A specification of the bytecode (binary upload file).	2024-11
0.0.3	Initial sequencer.	2024-12
0.2	Conditionals. Only conditional on command failure or success. Goto and if statement in bytecode. Equals operator.	2025-04-01
1.0	Telemetry access and loops. Local variables. All arithmetic and boolean operators. Flight ready release. Code quality/checklists/unit tests.	2025-07-01
1.1	Function definitions.	2025-10-01

[vietjtnguyen]

Another possibility is to not introduce a first-class advanced sequencing language and instead introduce the abstractions that make integrating one very easy. By avoiding a new first-class sequencing language, we can reduce the complexity in F' and allow integrators to select the best-fit language, minimizing overhead for projects with specific needs. If there was some abstraction for a function/command map and state/variable map that gets us most of the way there. The function/command map would be a mapping from symbol, like component name and mnemonic, to function pointer (and maybe signature?). The state/variable map would be the variables the script can perform logic on. Other hooks like program-wide init and deinit, script loading, script run, script cleanup, etc. can be handled through a component written to integrate a scripting language.

Ideally the abstractions would be concrete code objects that can be iterated, but some scripting engines might require integration that isn't easily done on a concrete code object. Instead you can provide an autocode step that makes these constructs (commands, function addresses, state/variable types and addresses, etc.) available to a template engine that the integrator could inject to provide the integration needed. A default template could be provided that produces concrete code objects so languages that can be integrated that way could just use that.

Regarding the state/variable map, it seems the current concept is to use telemetry channels as the state/variables that the script/sequence can perform logic on. I think it's worth considering introducing a state/variables concept as a first-class concept in F Prime and using that concept as a building block for telemetry and parameters. Having this advanced sequencing capability (via custom design or third-party scripting engine) will require centralization of at least references to the states/variables anyhow. Making it a first-class concept creates a natural integration point and can streamline telemetry/parameters. You can also provide notification hooks for change detection. Such hooks could be used to implement a telemetry system on top of the state store. Similarly parameters could be reconceptualized as states that are populated on start up and loaded to components. Having this state centralized like this would also make integrating a scripting language or advanced sequencer easier. If you also introduce an abstraction for the state store you can add additional implementations beyond the "contiguous region of memory" one like one that stores it in three memory regions and does voting, one backed by external ECC memory, one enhanced with transaction history, etc.

Ultimately, F' wouldn’t need to develop an advanced custom scripting language. Instead, it could offer a flexible integration layer, letting the integrator select the appropriate scripting language (custom or third-party) for their platform and deployment context.

Regarding third-party options, an interesting one is using WASM. There are WASM run-times that target embedded applications (like wasm3). Sandboxing is also part of WASM's overall design allowing you to limit the memory and capabilities available to a WASM program. The WASM programs can be compiled from any toolchain that can compile to WASM (like C/C++ using Emscripten).

[zimri-leisher]

Nice to talk to you again Steven :) (Steven was my group supervisor for my JPL internship)

LLVM was the second option I was considering. Maybe @Kronos3 could give an overview of how it worked?

[Kronos3]

@zimri-leisher Sure, what I built was in three main parts:

1. Frontend: converts user input into AST form
2. Compiler frontend: Converts AST into LLVM IR
   2.5 LLVM (I obviously didn't write this part): Optimizes (optionally) IR and converts IR to machine code (instruction set of your choosing)
3. Runtime: The runtime handles the interaction between the compiled code from above and the rest of the flight software. This exists as an autocoded runtime library.

TLDR We are compiling an actual executable from a stripped down language and using a library linked to that executable to communicate with FSW in some way

1. Frontend (language layer)

Here I was trying to demonstrate a safe control flow modelling environment that directly mimics Unreal Engine Blueprints. The idea here was that you could easily model things like event handlers/loops where in a conventional programming language this is a bit more difficult.

Here's a bite size example of what the frontend looked like

Alternatives

It is very straightforward to use a normal language provided we agree on the syntax into this compiler. The current status of the AST is very much in development so its subject to change.

In theory we could do a Python-like syntax and expand the AST definition accordingly

2. Compiler Frontend

The bulk of the work exists here. This takes the AST (JSON file) from the frontend and builds an LLVM module similar to how Clang or Rust might generate an LLVM module to pass to the latter stages of the compiler framework.

The control flow and calling convention are encoded in LLVM IR here.

3. Runtime

There are a couple of considerations I had here. The runtime is machine/fsw specific in that different FSWs will have a different convention for passing data and hooking command dispatch to their sequencing environment. To allow handling any such case, I left it up to a mandatory runtime library to be linked along with the LLVM generated .o file. This way LLVM just needs to worry about symbols exposed by the runtime library.

The runtime library essentially provides a compatibility layer between where or how you might want to run your sequence.

Memory Safety

Looking through this thread I see some discussion about memory safety and reserving memory for a language etc. What I did instead for this implementation is built it in such a way that you can only do stack based dynamic memory allocation. All heap objects are passed in to the language externally and the language does not directly modify or manage memory in any way.

To that end it is up to the runtime to allocate a block of memory to be used as a process stack so if you are virtualizing the execution of the sequence in some way you'd need to consider something like Fibers for context switching.

What can this run on

With MMU
If your system has an MMU, I'd say its probably easiest just to start another process and execute the code directly. Things like stack management can be handled directly by the OS.

Without MMU
Running without an MMU means that you can't really have a virtual memory address space and it would probably not be safe to run the code directly on the hardware. In this case, I have looked into what it might take to extract the CPU model of QEMU as a mini-VM to execute the binary on. Turns out the majority of the QEMU code is software models of other hardware like the disk or GPU etc. The CPU implementation itself is quite small meaning we could embed it into a FSW module to execute the sequence virtually.

[vietjtnguyen]

Very cool. What was the context/goal and constraints for this work? Was it expressly for enabling a visual logic block language for sequencing of any FSW?

[Kronos3]

Actually my initial goal was to do a conventional script-like compiled language instead of visual for FSW sequencing similar to M20 SPAM scripts for SRL (not actually funded for SRL just as a potential customer).

I decided to do a visual-based approach since I was working with Unreal Engine at the time and I found that it was very easy to model small behavior snippets like UI events or object behavior/event handling in this system. I wanted to see what it would take to re-create Unreal's system in a fully native-compiled environment.

[zimri-leisher]

@vietjtnguyen I referenced this comment in this issue: #3013

Would love to discuss further there

[zimri-leisher]

Meeting 9/30:
Accidentally refreshed the page and lost my notes draft, but it was short.
Main conclusions were:

• Canham and Starch are both of the opinion that A) the Python AST option will work and B) we should start writing code for this now.

• It would be nice to support the option of other languages being dropped in, and the implementation of the Python AST language will likely leave this as an option, but this is not the most important outcome.

• We really need an "out of the box" language that just works. Big projects will have the ability to write their own, but for small teams, they will want some "default" language.

• Starch thinks that LLVM will have the same problems as Python for big projects: running the LLVM may be heavy in terms of resource usage

  • On investigating it later, Zimri thinks this is not the case, LLVM would probably be performant and dynamic alloc on heap can be avoided according to Andrei. However, still have worries about the sequences themselves being executables running outside of the FSW binary. This toes the line between sequences and just writing CPP

• Zimri: In response to @vietjtnguyen 's comment:

• I love the idea of there being some first-class support for "variables/states" but this sounds like a massive effort and not strictly speaking necessary for advanced sequencing. It would be quite elegant and would unlock a lot of nice customizability as @vietjtnguyen mentioned. However unless somebody is volunteering to spend a significant amount of time to do this, it probably won't happen.

[vietjtnguyen]

I love the idea of there being some first-class support for "variables/states" but this sounds like a massive effort and not strictly speaking necessary for advanced sequencing.

I think whatever method chosen to make telemetry available to the sequencer for logic is probably 70-80% of the way there to creating the machinery for this abstraction anyhow.

There is a caveat here though: in my experience, the main issue with most of the "out of the box" interpreted languages (including wasm and Lua) is that they rely on JIT compilation for performance. That could break realtime and correctness guarantees, and can be too heavy for some low-power CPUs, but programs in these languages also become really slow without JIT-ing.

I see this concern often but I'm curious of the details. Do we even want folks to be able to use the sequencer in a tight, time-constrained loop? Can the current sequencer be used in that fashion?

Also regarding JIT, that's where projects like wasm3 come in which don't perform JIT compilation and instead interpret. From the project README:

In many situations, speed is not the main concern. Runtime executable size, memory usage, startup latency can be improved with the interpreter approach. Portability and security are much easier to achieve and maintain. Additionally, development impedance is much lower. A simple library like Wasm3 is easy to compile and integrate into an existing project. (Wasm3 builds in a just few seconds). Finally, on some platforms (i.e. iOS and WebAssembly itself) you can't generate executable code pages in runtime, so JIT is unavailable.

They have an interesting table of microcontroller support: https://github.com/wasm3/wasm3/blob/main/docs/Hardware.md. I'm not gonna stand on a soap box and say this is the solution for all cases, but I think it's probably more widely applicable than it seems.

[zimri-leisher]

I think whatever method chosen to make telemetry available to the sequencer for logic is probably 70-80% of the way there to creating the machinery for this abstraction anyhow.

Agreed, and future PRs could complete this effort.

I see this concern often but I'm curious of the details. Do we even want folks to be able to use the sequencer in a tight, time-constrained loop? Can the current sequencer be used in that fashion?

My personal belief is that sequences should be for things with 10-100 ms or greater order of magnitude timing precision. If it needs to be faster, use C++. The current sequencer has a worst case time precision guarantee of the time delta between rate group calls. For most people's fprime deployments I bet this will be 10-1000 ms.

wasm3 seems interesting. I don't want to fall victim to "not-invented-here" syndrome and ignore a promising option, but I'm just listening to Canham and Starch and they think the Python AST option will work. I am certain that the bytecode that we come up with will be less memory and time efficient than using a popular existing bytecode, but is losing exact control over the format, and forcing a dependency on a large external library worth it? I would feel much more confident in an existing bytecode interpreter if I saw that it had been used on a real-time system before.

[h313]

I previously ran some experiments on how fast WebAssembly interpreters were on a compute-heavy workload (Sieve of Eratosthenes, up to 10M) for a proposal. Assuming that's what we want to enable sequences to do, non-JIT runtime was >4x slower (see wasm3 vs wasmtime in the graph below).

If we do take the wasm3 route, another potential issue that may come up is that we would still have to build a support library to interface with F'. This may be much more involved than rolling a bespoke bytecode language, as we would need to define these interfaces and provide language-specific bindings to them to be compiled to.

[zimri-leisher]

@h313 Is there an option to only implement part of the support library?

[h313]

Ah, by support library I simply mean that we'll have to implement a way for the wasm3 program to dispatch F' commands, since it's not there by default. We'll also want to disable WASI, which exposes system APIs to the wasm3 program, which is perhaps too much freedom for a flight software sequence.

[zimri-leisher]

Meeting notes 10/7:

• Zimri has a first draft of the AST parser
• Will provide a working compiler for the existing sequence format by next week. It will take in .py files and output sequence .bin files in the previous format. This will constitute version 0.0.1

On wasm:

• Michael says we're still outstanding on the compiled binary format (still waiting to reach out to JPL folks who have done this bytecode stuff before). ETA next week for a report on this meeting.
  • Zimri says this will inform our decision on whether or not to use wasm3 or a similar bytecode.
  • Likely no matter what, we want it to be interpreted
  • Michael says the existing bytecodes will likely be more feature complete than we need, and it will bog us down. Let's keep anticipating using our own version of this stuff.
  • Given the current state of things, a class B mission/other major mission would probably not fly something that was not developed specifically with aerospace constraints in mind in such a core area.

[zimri-leisher]

Unclear on exactly what you mean, did the first sentence get cut off? Not sure how the LLVM IR relates to wasm3. In what way does using LLVM IR affect the need for a runtime library?
I am genuinely very interested in using LLVM IR because I've heard great things about it, and I can see how it would make our lives easier. Just want to understand the work involved.

[Kronos3]

LLVM IR is a platform agnostic bytecode format that LLVM uses to apply optimizations. After optimizations are applied, an LLVM backend is selected based on the target platform you are trying to compile to.

WASM (like any other instruction set like x86, MIPS etc.) has a corresponding LLVM Backend that converts this IR into a WASM object file (or text assembly).

Generally compilers for new languages just need to worry about converting their AST into LLVM IR and then they automatically gain the optimizations (-O1, -O2 etc.) and CPU targets provided out of the box by LLVM. The comment above is really just saying that to generate the IR you can not depend on the LLVM Runtime library that provides a C++ API for creating IR (which it sounds like is an undesirable compile-time dependency) and rather just generate a text file with the IR and call out to LLVM via CLI.

This way you can write your AST -> IR in whatever language you want and not directly depend on LLVM libs.

[h313]

I do agree that WASM might be overkill, especially given that the stack-based nature of the program could lead to memory overflows.

The eBPF ISA could be a good fit, as it's a RISC ISA that can support all the required commands, with a limited the number of registers to ensure that the program won't start dynamically allocating memory. The ISA also comes with support for helper functions, which we can repurpose to call other FSW sequences. There's also an LLVM backend for it!

Before loading an eBPF program, a verification step that ensures that illegal memory accesses can't happen. It'll be optional for us to use this verifier, but it can help us guarantee safety properties about the sequence, such as termination and memory safety.

If we do take this route, we can either spin our own interpreter, which should be comparatively simple given the small size of this ISA, or repurpose an existing one such as uBPF. There's also prior work on a realtime microcontroller-specific eBPF runtime.

[zimri-leisher]

Just to clarify my understanding, what is the reason we wouldn't want to turn LLVM IR into the native instruction set of the target CPU and avoid WASM/eBPF entirely? Is there no way to provide memory/runtime guarantees at the IR level?

[h313]

At that point, we'd just be compiling whatever code that we have to native assembly, and then running it on bare-metal, which seems a bit too close to just writing C code for F' to use.

As far as LLVM IR itself, it's not a memory safe language, as it can allow stuff like accessing array indices over the size of the array. Type safety is also an issue, since LLVM does allow C-style casting and garbage collection isn't required.

[zimri-leisher]

Notes 10/14:

• Michael has notes on the bytecode meeting with JPL but not sure if he can export the data
• He says it's going to look very much like the previous bytecode in fprime: A bit of header, a series of N command specs (time designator, cmd, arguments)
• The Mars missions wanted a "wait until", but the existing format has time designator prepended to the cmd itself
• However, tim isn't here and we want to reschedule the meeting
• New requirements regarding validation which we will cover in rescheduled meeting
• Requirements related to loops and breaks
  On LLVM IR:
• Starch feels big projects will consider this still as a research feature but wants Tim's opinion
• Still not wrong to keep an eye on it

[zimri-leisher]

Extra meeting on bytecode format (draft):

1. General format:
   Schema Version 0: Format that is backwards compatible with other JPL sequencers
   Schema Version 1+: Extended F´ format

Files look like:
HEADER
COMMAND SPEC
COMMAND SPEC
COMMAND SPEC
....

2. Data: Use F´ Default (Big Endian)

3. Header (draft)

4. Project Version. (3 bytes) - 1 bytes major, 1 byte minor, 1 byte patch

5. Sequence sequence "schema" (1 byte)

6. Number of input arguments (preset "locals"). 1 byte. (Configurable, must fit in one byte)

7. Array (Configurable) local IDs to map inputs into (Configurable)

8. (Schema version > 0) Extended features bitmap

9. COMMAND SPEC:

10. (Schema version 0) Command time spec (absolute time, relative to last dispatch, relative to some epoch, relative to last command completion). 1 byte.

11. (Schema version 0) Time value. (4 bytes).

12. Command length. (2 bytes). (Configurable: FwsizeType)

13. Command opcode. (2 bytes). (Configurable: FwOpcodeType)

14. Command args. (Variable).

Schema version 1 will not have time spec or value because delays will be separate commands.

Other requirements:

1. (ADD POST v1.1) Public command validation interface.
   1. On load and reactivate
2. (ADD) Read unassigned variable results in error
   1. Set locals as unassigned on sequence end
   2. Set assigned when written
   3. Track assigned state
3. (ADD) Cannot run sequence directives from ground
4. (ADD POST v1.1) Pause directive, reactivate command
5. (ADD POST v1.1) Cross-string directive
6. (ADD) Reserve configurable range of opcodes (universal) for seq directives
7. (ADD) Quit on run after absolute time
8. (ADD POST v1.1)
9. Allow commands "relative to epoch"
10. Set epoch at load/activation
11. (ADD) Global "deactivate all"
12. May not be a sequencer requirement
13. May be a sequenceDispatcher requirement

[timcanham]

To help flight systems with constrained uplink rates, we should have the ability to compress the contents of the sequence. Not the header, which can contain "is compressed" bits, but the commands.

[zimri-leisher]

You'd prefer that solution over just having the uplink conops use some compression algorithm?

[LeStarch]

Yes, I don't follow why operations wouldn't just compress the whole file on uplink as they would any other uplinked file that needed to be compressed.

[ReggieMarr]

Hopefully this doesn't detract from the conversation here but I'm curious if anyone here as opinions about elua as an option for this kind of dsl?

I've been working on a project of a similar nature to this, investigating different languages to specify operational behavior. After some evaluation I've found that lua appears to be the top contender for our purposes.

It seems like the folks on this thread might have some valuable insight/opinions and also if it's not too far down the line it may be worth considering.

[zimri-leisher]

The guidance I've been consistently getting from Canham and Starch is that we want to follow the tried and true path of a custom bytecode and high-level format, as boring and uninnovative as it may seem. All of the spacecraft that they have experience working on have developed their own high level language and custom bytecode, so if we develop our own that lets us pull in JPL heritage and help the big projects feel better.
So that's kind of a cop-out answer, and personally I would love to use these cool new langs or tools like LLVM, but I see the wisdom in picking one's battles.

[ReggieMarr]

Fair enough, thanks for the insight !

[zimri-leisher]

Hey, as part of the sequence compiler I would like access to the Python representation of the FPP model. What is the best entry point for getting, for instance, a list of the fprime_ac.models.Component.Component classes that make up the model? Do I need to hook into cmake?

Or alternatively, do you think the advanced sequence compiler should only depend on the dictionary json? The problem is, the dictionary json doesn't include some key information that must exist in the Autocoder that I would have to manually reconstruct if I can't just use the Autocoder source itself. Maybe we could just include this info in future versions of the dictionary json ("module" declarations, some other small things but the list will grow).

[bocchino]

What is the best entry point for getting, for instance, a list of the fprime_ac.models.Component.Component classes that make up the model?

You can use fpp-to-json for this. See https://nasa.github.io/fpp/fpp-users-guide.html#Analyzing-and-Translating-Models_Generating-JSON-Models. Run fpp-depend [build-cache]/locs.fpp [topology fpp files] to get the dependencies first. Then use the dependencies as input to fpp-to-json.

You should not use the Python model for anything. That model is deprecated and will be deleted when we fully switch away from using XML.

[zimri-leisher]

Okay, maybe I don't understand what the Python model is. I just wanted to be able to hook into the internal FPP parsing tools and pull out their representation of the FPP model. I thought this was separate from the Python model.

[zimri-leisher]

Want to ping on this again. Currently, given just the JSON dictionary, if I see an entry for a struct called Ref.name.StructName, there's no way for me to tell if name is a component or a module. Unless someone can think of a clever way.

[bocchino]

I just wanted to be able to hook into the internal FPP parsing tools and pull out their representation of the FPP model.

In general you can do this in Scala (the implementation language of FPP) or in another language, like Python. If you do it in another language, the recommended way is to use fpp-to-json to get a complete dump of the model in JSON. I provided a link above to the section of the User's Guide that explains how to use fpp-to-json.

Note that fpp-to-json is different from the tool that generates the JSON dictionary (fpp-to-dict). Is this a source of confusion? fpp-to-dict generates the ground dictionary. fpp-to-json dumps the model. Both are in JSON. fpp-to-json has a lot more info in it, but fpp-to-dict is in a format that's easier to use for applications like the GDS that need the dictionary.

I thought this was separate from the Python model.

We are moving away from using the Python model as we transition away from using XML. Going forward, the sources of truth for the model are (1) the Scala model; (2) the JSON model (via fpp-to-json); and (3) the JSON dictionary (via fpp-to-dict).

[zimri-leisher]

Okay. I think I would like to avoid using the fpp-to-json output and continue to rely on the dictionary for as long as possible. It may be the case that down the line I am forced to switch to the more complete json model, but for now the dictionary suffices.

[zimri-leisher]

For next meeting:

• Want to decide on name of the high level language
• Want to discuss whether any tasks could be delegated, especially ones related to the autocoder. Maybe the reworking of the tlm system so we can pull telemetry values without deserializing?

[zimri-leisher]

Basic demo of the Python syntax is working in my branch, https://github.com/zimri-leisher/fprime-gds/tree/2919-adv-seq-compiler

Example sequence file (using the Ref deployment):

Ref.fileManager.RemoveFile("fileName", ignoreErrors=False)
seq.sleep_until(Time(2, 0, 12333223, 5000))
Ref.typeDemo.CHOICE_PAIR(Ref.ChoicePair(Ref.Choice.RED, Ref.Choice.TWO))

Example of the new command to compile it:

fprime-seq test_seq.py -d test/fprime_gds/common/sequence/RefTopologyDictionary.json

Currently it doesn't actually produce the binary output. I estimate making the binary will take me another day or two of work. However, it includes

• full type checking for all arguments and commands in the Python syntax

Ref.typeDemo.CHOICE_PAIR("invalid type") # -> error on line 1: Expecting a value of type Ref.ChoicePair, found 'str'

• keyword arg support

Ref.fileManager.RemoveFile(fileName="test_file.txt", ignoreErrors=False)

• sequence directives for relative and absolute sleeps

seq.sleep_until(Time(2, 0, 12333223, 5000)) # -> absolute sleep
seq.sleep(Time(2, 0, 0, 50000)) # -> relative sleep

This is pretty exciting, we could easily start using this as a replacement for the .seq file format soon.
Also going to add one more thing, which is autocoded Python "header" files to allow for IDE autocompletion and highlighting.

[zimri-leisher]

Notes 11/5

• seq. syntax for sequence directives

• Could call them dir. says Starch--however, this is already a Python function

• Zimri advocates for removing the seq. and renaming to sleep_abs and sleep_rel--need to confirm with @timcanham that this is okay

• Starch brings up that someone could have a component named seq--don't want namespace conflicts

• Zimri points out that unqualified names would solve this problem

• On the syntax for the Time object constructor--Starch says this is okay, wants further opinion

• On using fpy as a name: Starch is confirms this is okay, need to confirm with @timcanham

• On delegating work for tlm system for accessing values: Starch says to make a ticket for this. There is the desire to help but would have to plan in advance for the manpower. @zimri-leisher to take action

[zimri-leisher]

Version 0.1 is working! Tested by compiling some basic FPy sequences and running them on the Ref deployment. It also has a reasonably large chunk of internal test cases.

PR is out. I will start working on writing a new CmdSequencer and bytecode format now. The first step will be just replicating the behavior of the current sequencer (just running commands at a certain time).

nasa/fprime-gds#181

[zimri-leisher]

For next meeting:

• Python stub generator workflow--how do you imagine this working? Language server support?
  • FYI for readers: Python stub generation will be an optional step for this language that involves generating Python stub files for FPrime components to allow IDE autocompletion to work. For example, if you type: component.ExampleComma in an FPy file, you want the IDE to complete it to component.ExampleCommand() and give you argument name/type hints. In the future I'd like not to have to rely on generating stub files, but that will require a custom language server.
• How to disambiguate type within component vs type within module
• Ping on github issues and PR review