Impl of Command Sequence Logic

[zimri-leisher]

Hey all,
A couple weeks ago I posted asking about whether logic could be implemented in command sequences (#2537). Well, I went ahead and implemented it. Now command sequences can be Turing-complete 😆

Here are the first 10 Fibonacci numbers, calculated in a command sequence:

Here's the command sequence:

R00:00:00 logic.SET_BOOL "loop_done", false
R00:00:00 logic.SET_INT "a", 0                      ; (n-1)th fib number
R00:00:00 logic.SET_INT "b", 1                      ; nth fib number
R00:00:00 logic.SET_INT "c", 0                      ; temporary storage
R00:00:00 logic.SET_INT "iter", 0                   ; current iteration of loop
R00:00:00 logic.SET_INT "max_iters", 10             ; number of iterations of loop we want to run

R00:00:00 logic.TRACK_VAR "b"                       ; output b in telemetry as "loggedVarInt"

R00:00:00 logic.GEQ "iter", "max_iters", "loop_done"; loop_done = (iter >= max_iters)
R00:00:00 logic.IF "loop_done", 10                  ; if the loop is done, proceed, else go to cmd idx 10 where we continue the loop
R00:00:00 cmdSeq.CS_GOTO 15                         ; go to the end

R00:00:00 logic.ADD "a", "b", "c"                   ; c = a + b
R00:00:00 logic.ASSIGN "a", "b"                     ; a = b
R00:00:00 logic.ASSIGN "b", "c"                     ; b = c
R00:00:00 logic.INCREMENT "iter"
R00:00:01 cmdSeq.CS_GOTO 7                          ; go back to greater than or equal to after 1 second

R00:00:00 logic.STOP_TRACKING_VAR                   ; stop tracking b in telemetry

Here is how this is implemented:

1. CmdSequencer has a CS_GOTO command, and a goto port, which goes to a command index in the currently running sequence. I implemented this in a pretty simple way, it just resets the deserializer for the sequence binary file and deserializes from the start until it reaches the desired command index. With large values for cmdIndex I'm worried this could be inefficient, but this was the best way I could think of.

    void CmdSequencerComponentImpl::performCmd_Goto(const U32 cmdIndex) {

        // reset the command sequence to start from the beginning
        this->m_sequence->reset();

        // we want to skip i number of commands
        // e.g. if cmdIdx is 1, then we want to skip cmd at idx 0
        int i = cmdIndex;

        while(i > 0) {
            if (!this->m_sequence->hasMoreRecords()) {
                this->log_WARNING_HI_CS_InvalidCommandIndex(cmdIndex);
                return;
            }
            this->m_sequence->nextRecord(m_record);
            i--;
        }

        if (!this->m_sequence->hasMoreRecords()) {
            this->log_WARNING_HI_CS_InvalidCommandIndex(cmdIndex);
            return;
        }

        this->log_ACTIVITY_LO_CS_GotoSuccess(cmdIndex, this->m_sequence->getLogFileName());
    }

2. A new component called CommandLogicManager was made, which has three things: a variable database, logic and arithmetic functions which operate on that database, and an if command which allows for non-trivial control flow.

Variable database: I chose to use a new variable database rather than the ParamDb or telemetry stream because both of those are really meant for separate purposes. ParamDb is not supposed to be updated super frequently, and telemetry is just an output of the system. The new database is dead simple, it's just three std::maps of std::string to U8 (for bools), I32 (for ints), and F64 (for floats). You can set values in it with commands, so command sequences can have their own workspace, and also with ports, so that arbitrary code can set values for command sequences to use.

Logic and arithmetic functions: Standard stuff like &&, ||, +, -, pow, sqrt, log are all commands which take in names of variables and store their result in another variable. This means you can't do stuff like x = y + 1, you have to do z = 1; x = y + z. Not sure how best to solve this, it seems like I'd need a new command for each situation of argument type.

If command: If a boolean variable is true, it doesn't do anything and the command sequencer goes to the next command. If the boolean variable is false, it uses the CmdSequencer goto port to go to a specific command index (the 'else' case).

Use cases

Our original intent with this is to allow for fault detection and response to be implemented in command sequences, so that they can be modified from the ground. However, this could also be useful if there is a situation in which a decision will have to be made autonomously, and this situation was not foreseen when developing the FSW.

I would love to hear your thoughts on this. I know that @timcanham is going to post something soon about this, so I'm looking forward to reading it. Next, I'm looking at adding support for running multiple sequences at once.

[LeStarch]

@timcanham, @Joshua-Anderson did you see this?

[timcanham]

PolyDb doesn't have the logic functions, but it would be a good resource for your CommandLogicManager as a glue component.

[zimri-leisher]

Ok, look for a PR from me in the next week or two for this.

[zimri-leisher]

Are you imagining this as two separate PRs, one for CmdSequencer and one for CommandLogicManager? Also I think I'm gonna rename it to CmdLogicManager just to be consistent.

[timcanham]

I'll defer to @LeStarch, but that seems like a good idea.

[zimri-leisher]

The devops for this are going to be tricky. We want this change to be compatible with our own internal FPrime fork, but it is a few versions out of date. I'd like to prioritize getting it to work on our own version, and once it's done, I'll go through the normal FPrime contribution process. I think I should be able to copy the code and git history over from our internal fork to an public fork on Github and then make changes to support the more recent FPrime version there.

[ljreder]

Oh God! Not a GOTO command please. Just a thought. Leonard J. Reder

…

On Thu, Mar 7, 2024, 8:39 AM Zimri Leisher ***@***.***> wrote: Hey all, A couple weeks ago I posted asking about whether logic could be implemented in command sequences (#2537 <#2537>). Well, I went ahead and implemented it. Now command sequences can be Turing-complete 😆 Here's the first 10 Fibonacci numbers, calculated in a command sequence: image.png (view on web) <https://github.com/nasa/fprime/assets/25469876/c749ce23-d0ee-4d66-a6e6-6f2d521bc4c2> Here's the command sequence: R00:00:00 logic.SET_BOOL "loop_done", false R00:00:00 logic.SET_INT "a", 0 ; (n-1)th fib number R00:00:00 logic.SET_INT "b", 1 ; nth fib number R00:00:00 logic.SET_INT "c", 0 ; temporary storage R00:00:00 logic.SET_INT "iter", 0 ; current iteration of loop R00:00:00 logic.SET_INT "max_iters", 10 ; number of iterations of loop we want to run R00:00:00 logic.TRACK_VAR "b" ; output b in telemetry as "loggedVarInt" R00:00:00 logic.GEQ "iter", "max_iters", "loop_done"; loop_done = (iter >= max_iters) R00:00:00 logic.IF "loop_done", 10 ; if the loop is done, proceed, else go to cmd idx 10 where we continue the loop R00:00:00 cmdSeq.CS_GOTO 15 ; go to the end R00:00:00 logic.ADD "a", "b", "c" ; c = a + b R00:00:00 logic.ASSIGN "a", "b" ; a = b R00:00:00 logic.ASSIGN "b", "c" ; b = c R00:00:00 logic.INCREMENT "iter" R00:00:01 cmdSeq.CS_GOTO 7 ; go back to greater than or equal to after 1 second R00:00:00 logic.STOP_TRACKING_VAR ; stop tracking b in telemetry Here is how this is implemented: 1. CmdSequencer has a CS_GOTO command, and a goto port, which goes to a command index in the currently running sequence. I implemented this in a pretty simple way, it just resets the deserializer for the sequence binary file and deserializes from the start until it reaches the desired command index. With large values for cmdIndex I'm worried this could be inefficient, but this was the best way I could think of. void CmdSequencerComponentImpl::performCmd_Goto(const U32 cmdIndex) { // reset the command sequence to start from the beginning this->m_sequence->reset(); // we want to skip i number of commands // e.g. if cmdIdx is 1, then we want to skip cmd at idx 0 int i = cmdIndex; while(i > 0) { if (!this->m_sequence->hasMoreRecords()) { this->log_WARNING_HI_CS_InvalidCommandIndex(cmdIndex); return; } this->m_sequence->nextRecord(m_record); i--; } if (!this->m_sequence->hasMoreRecords()) { this->log_WARNING_HI_CS_InvalidCommandIndex(cmdIndex); return; } this->log_ACTIVITY_LO_CS_GotoSuccess(cmdIndex, this->m_sequence->getLogFileName()); } 1. A new component called CommandLogicManager was made, which has three things: a variable database, logic and arithmetic functions which operate on that database, and an if command which allows for non-trivial control flow. *Variable database*: I chose to use a new variable database rather than the ParamDb or telemetry stream because both of those are really meant for separate purposes. ParamDb is not supposed to be updated super frequently, and telemetry is just an output of the system. The new database is dead simple, it's just three std::maps of std::string to U8 (for bools), I32 (for ints), and F64 (for floats). You can set values in it with commands, so command sequences can have their own workspace, and also with ports, so that arbitrary code can set values for command sequences to use. *Logic and arithmetic functions*: Standard stuff like &&, ||, +, -, pow, sqrt, log are all commands which take in names of variables and store their result in another variable. This means you can't do stuff like x = y + 1, you have to do z = 1; x = y + z. Not sure how best to solve this, it seems like I'd need a new command for each situation of argument type. *If command*: If a boolean variable is true, it doesn't do anything and the command sequencer goes to the next command. If the boolean variable is false, it uses the CmdSequencer goto port to go to a specific command index (the 'else' case). Use cases Our original intent with this is to allow for fault detection and response to be implemented in command sequences, so that they can be modified from the ground. However, this could also be useful if there is a situation in which a decision will have to be made autonomously, and this situation was not foreseen when developing the FSW. I would love to hear your thoughts on this. I know that @timcanham <https://github.com/timcanham> is going to post something soon about this, so I'm looking forward to reading it. Next, I'm looking at adding support for running multiple sequences at once. — Reply to this email directly, view it on GitHub <#2575>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AASN3AH2QN3ISOKKYID6DLDYXCJ3VAVCNFSM6AAAAABELKY37CVHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZWGMZTONRZHA> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[zimri-leisher]

Yeah it's not very pretty. It has the virtue of being sufficient to write arbitrarily complex control flow, and also being simple to implement. We will use this system to tide us over until a better alternative can be developed officially in F`.

[Joshua-Anderson]

@ljreder I look at this as similar to assembly level code - which is also primarily driven by conditional jumps. But just as software developers almost never directly write assembly, I expect that we'd probably add a higher level fprime sequencing language with if/else/loop statements that would be compiled down into conditional jump statements.

[ljreder]

@Joshua-Anderson to be honest my reaction to the GOTO was as I was reading this one day on my cell phone. I would certainly think that something like seqen would be enhanced to take a Sequencer file format with higher level constructs and encode into some sort of binary format of lower level. Of course now that I read this it seems more and more looking like an interpreter sort of thing is going one. @zimri-leisher I totally get the first prototype nature of this. In fact this is really very cool thing you have done.

[zimri-leisher]

If we were going to continue developing this into a more usable system, we would want it to look like ASI's FlightJAS: https://max.rocketlabusa.com/docs#MAX/Sequencing/FlightJAS.md

[Joshua-Anderson]

This is fantastic @zimri-leisher - I can't believe y'all have gotten conditional sequencing all up and running! I haven't looked at flightJAS before, will definitely be reviewing as well.

This was definitely along the lines of what I was thinking.

Here are some of the trade space discussions I've been thinking about as we move forward with conditional logic in fprime:

1. Reusable sequences and sequence directives: From our operations experience with fprime, we've learned we need better support for reusable sequences
   • Many missions have multiple command sequencers, and operators generally should be agnostic to what command sequencer a sequence is running on
   • If sequence logic is implemented as command sequencer commands, you must target your sequence to run on a specific sequencer (since the opcode for cmdSeq.CS_GOTO will be different than cmdSeq2.CS_GOTO.
   • We could instead create a concept of F' sequence directives, commands that can only be called from a sequence and always target the sequence engine executing the sequence. Could be implemented by adding a 1-bit field to serialized commands that indicates if they're a command or a sequence directive.
2. Assembly style conditional jumps vs serializing IF/ELSE/ENDIF commands directly to sequence directives.
   • Looks like your design is going for conditional jump statements, where you can jump to a command offset based on a variable comparison.
     • I think this is generally a good approach and allows you to implement arbitrarily complex checks, which adds a lot of sequencing flexibility.
     • The downside in my mind is this approach is that it probably requires developing a high level sequencing language for F', since hand writing conditional jumps can be error prone. As an spacecraft operator, I'd be pretty concerned about the challenges of validating complex sequences with hand-written conditional jumps.
     • JPL FSW generally has rules precluding infinite loops - conditional jumps are more challenging to validate and ensure they terminate. May not be a significant concern if the higher level sequencing language exists and has a for loop concept.
   • The other approach is that IF, ELSE, ENDIF just become sequence directives. Then, if the sequence engine encounters a seq if, it'll just walk through the sequence linearly, skipping commands based as needed based on the condition
     • This is generally simpler to implement, but makes supporting arbitrarily complex conditional statements and loop statements more challenging.
   • This trade definitely opens the pandora's box of philosophical arguments about how much logic should live in the flight software vs at the sequencing level. 😄 I generally lean towards your proposal of conditional jump statements, but could be swayed either way.
3. Treat variables as register indexes instead of named strings

• We may want to consider treating command sequence variables a bit like registers in assembly languages. You could allocate a fixed number of registers on startup (no dyanamic memory allocation) and refer to variables by index instead of name
• If we had a higher level sequencing programming language, we could map human friendly variables names to register indexes, just like most compiled programming languages.

4. Passing variables to as arguments to commands

   • It's super useful be able to pass variables/arguments to command sequences. Can significantly help with sequence reusability.
   • Definitely not needed in any first revision of a more complex sequence engine, but worth making sure architectural choices don't preclude this later on.

5. Global variables

   • The ability to non-volitilely load and store variables can be really useful for some missions

These are just some of the things I'm thinking about, and I fully expect that we'll all have different opinions on them - let me know what your thoughts are as well. Just want to make sure we consider that larger architectural decisions as we start to come up with an architecture.

[zimri-leisher]

Thanks for this writeup! Yes, the goal of this implementation was the most direct and simple path to command sequence logic so that we can go ahead and start using this functionality.

I like your points about multiple command sequencers, non-volatile variables, arguments and the pandora's box of what should live in FSW vs sequences.

On the pandora's box of what should be in FSW vs sequences:

Commands are the human interface to the spacecraft. As such, logic in command sequences should be thought of as analogous to human decision making. If you could magically have a (very attentive and patient) human ride along with the spacecraft, whatever tasks you'd give to them, I would put in command sequences. For example, I would not use them to control RCS thrusters to point the spacecraft, but I would use them to set a pointing target for the spacecraft. I would not trust them to push the engine-on button at a precise time, but I would trust them to decide when that button should be pressed and hand it off to FSW.

On non-volatile variables:
This can be accomplished by having interaction between the sequencing logic and the ParamDb. I was already planning on doing this actually.

On arguments and multiple command sequencers:

Everything points to a new or upgraded binary file format, which means changes to the CommandSequencer backend and changes to fprime-seqgen.
I think very likely the proper solution is a new, higher-level human readable sequence file format, combined with a new binary sequence file format. I'm wondering which existing technologies we can use to make this as simple to implement as possible. I don't want to write another syntax parser, one new language in a project is enough 😅 I'm thinking that there's probably some way Python can be leveraged to do this. Probably by using this: https://docs.python.org/3/library/ast.html and mapping Python language features to command sequence language features.

On variable registers:
I think this is an implementation detail that shouldn't be visible to the end writer of sequences. One way or another, there must be some association of strings with values, and if that's a fixed-size array indexable by integers, that would certainly work.

I highly recommend that everyone who is interested in this read through the FlightJAS documentation as a starting point.

[ljreder]

WOW it is so funny @zimri-leisher mentioned Python because as I was reading through all of this that is what I was thinking about. Many years ago I have seen Python embedded for various applications and essentially used as a top level sequencing language to control various specific hardware using Python-to-C bindings. For example see this bit of work presented here: Design and Implementation of an Embedded Python Run-Time System.

Perhaps it might be possible to build a scaled down Python interpreter that could be encapsulated into an F prime component for sequencing. You could create bindings into the interpreter for commands and telemetry. One would need to address various FSW requirements of course but I have seen this done in the past in various ground based and aircraft instrumentation applications so it might be interesting to look at.

One would use the Python compiler to generate a byte code file and that would end up being the sequence file used in the new component.

Just some off the wall late night thinking. If any of you guys end up doing something like this I would be interested in hearing about it.

[zimri-leisher]

That's interesting, I was thinking of a different use of Python. I was imagining that no Python would actually run on a machine. Instead, we would take a Python program, parse the syntax tree, and generate our own binary format from the Python program.

[ljreder]

Yes I realized what your approach was and it is probably more practical here but you will have to do language implementation kind of stuff with the AST to get what you want. But you have allot of the low level logic already so that is good. I was just recalling the past I have seen this done. For myself I have taken the Python interpreter and built back end real-time C code that runs by commanding it via python functions that are interfaces to C functions. When I did this first some 25 years ago I had to program all manually but now there are technologies like SWIG or hopefully even better ways to generate all this. The problem is that you want to restrict to single threads and disable any run-time dynamic allocation going on - these two things are probably big show stoppers.