search

frame-lang / frame_transpiler

Frame is a markdown language for creating state machines (automata) in Python as well as generating UML documentation.
MIT License
65 stars 9 forks source link

Grammar: allow terminators inside of branches? #17

Open walkie opened 3 years ago

walkie commented 3 years ago

Currently, terminators are not allowed inside of branch statements. Since branches are statement-level, it seems like this should be permitted.

For example, this Frame spec currently returns a (confusing) Frame parse error:

#TerminatorsInBranch
    -interface-
    Foo

    -machine-
    $S1
        |Foo|
            true ?
                -> $S2 ^
            :
                -> $S3 ^
            ::

    $S2
    $S3

    -actions-
    -domain-
##

Instead one must move the terminators out of the branch to write this:

#TerminatorOutOfBranch
    -interface-
    Foo

    -machine-
    $S1
        |Foo|
            true ?
                -> $S2
            :
                -> $S3
            ::
            ^
    $S2
    $S3

    -actions-
    -domain-
##

Enabling within-branch terminators would give handlers finer grained control over whether to propagate a message on to a parent handler in a hierarchical state machine. For example, one could write the following handler, which is currently a parse error:

    |Foo| [b:bool]
            b ?
                log("continue") :>
            :
                log("return") ^
            ::
frame-lang commented 3 years ago

Agreed the parser doesn't trace through the execution graph to determine if all paths are terminated and cheats by insisting on a ^ or :> as an event handler terminator. However, to be clear, one can add the terminators for each branch, but the grammar does insist on a redundant event handler terminator, which isn't elegant:

#TerminatorOutOfBranch
    -interface-
    Foo

    -machine-
    $S1
        |Foo|
            true ?
                -> $S2 ^
            :
                -> $S3 ^
            ::
            ^
    $S2
    $S3

    -actions-
    -domain-
##

I am very open to improving this as I know a lot of (or all?) compilers will complain. Any pointers to how this kind of tracking is done would be welcome as well as an open invitation to implement. I'll create an RFC doc and we can add technical proposals, background there and get an agreed upon solution defined.

walkie commented 3 years ago

Ah, good to know it's supported and I was just doing it wrong!

I think this should be a relatively easy constraint to remove. You don't need a sophisticated control-flow analysis, just a terminated property attached to each node n in the AST (you can also define this externally as a function, either approach is equivalent). The value of n.terminated is defined recursively as follows:

Then the rule changes to: the statement block that is the body of a handler must be terminated.

Additionally, you can perform dead code analysis with this property by checking the following rule: if n is a statement block, it is an error if any statement other than the final statement is terminated.

I think this covers all of the cases, but it's possible I'm missing something!

walkie commented 3 years ago

I included a test for terminators inside of branches in my latest PR, and it seems to work!

frame-lang commented 3 years ago

Cool - for awareness I'm actively working on the parser to make this work correctly, by which I mean not requiring a terminating return if the last branching statement has all paths terminated.

walkie commented 3 years ago

Sounds good! I assume the continue terminator will also be allowed at the end of each branch?

Relatedly, it would be good to come up with a way to test in the test suite that a given Frame file doesn't compile. I'll look into a way to do that.

frame-lang commented 3 years ago

Commit 9ebe8f4..3ca27d0 supports:

No event handler terminator if all branches for a boolean conditional terminate:

    $S1
        |Foo|
            t ?
                -> $S2 ^
            :
                y() ^
            ::

        |x| ^

Termination of a branch ending in a transition/change_state statement:

    $S1
        |Foo|
            t ?
                -> $S2 
            :
                y() ^
            :: ^

        |x| ^
walkie commented 3 years ago

Looks good! In the second case, do you need the final terminator at the end of Foo, or does the transition imply a return in the then-branch?

frame-lang commented 3 years ago

as long as all branches are terminated by the next statement then the parser considers it valid. however you raise a really interesting question as to whether a transition/statechange should be self terminating.

For logical consistency I presume that self terminating transitions would also support this syntax:

    $S1
        |Foo| -> $S2

        |x| ^

    $S2
frame-lang commented 3 years ago

@walkie I think this is easy enough to do, however I do think these options need to be supported in the code generators:

    $S1
        |A| -> $S2
        |B| -> $S2 ^
        |C| -> $S2 ^(ret)

    $S2

Thoughts? I'm assuming that the code generators need to detect a self termination with no explicit return and generate a return but not generate if an explicit return exists.

frame-lang commented 3 years ago

So I'm thinking how to implement things with self terminating statements (transitions the only example so far).

Here is a few cases I've been mulling over:

#Terminators2

    -machine-

      $TransitionTermination

          |A| -> $S2 :> --- this should be invalid
          |B| -> $S3 ^
          |C| -> $S4 ^(0)
          |D|
            t ? -> $S2 :>
            u ? -> $S3 :>
            v ? -> $S4 ^(1) :>
            w ? a() :>
            x ? b() ^ :>
              : f()
            :: ^(42)
          |E|
            t ? -> $S2
            : ^ ::
          |F|
            t ? -> $S2 ^
            : -> $S3 ::            
##

It seems to me the cases to deal with are:

  1. |A| -> $S2 --- transition should be self terminating and generate a "return" automatically.
  2. |B| -> $S2 ^ --- transition return "auto-generation" should be suppressed and ^ token generates return (same code output as 1. though).
  3. |C| t ? -> $S2 :: ^(42) --- should return 42, so auto-gen is suppressed.

There is more nuance but those are key I think.

walkie commented 3 years ago

Your list of cases looks reasonable to me.

I would vote for still allowing a return at the end of an if-then-else, even if it's not needed. This will keep all the existing code compiling and is consistent with your second example, where the return is not required, but may be optionally provided.

It sounds like you plan to still include a return node in the AST after a transition (i.e. generating the return node even if a return statement is not included). In that case, I don't think this should require any additional work on the backends. However, I think the Rust backend should already work whether or not the return node is included.

frame-lang commented 3 years ago

still allowing a return at the end of an if-then-else, even if it's not needed. Agreed.

It sounds like you plan to still include a return node in the AST after a transition I hadn't considered that but that is probably the simplest way to do it. Good idea.

frame-lang commented 3 years ago

So I've been playing with the "implicit return" aspect of transitions and am thinking now that it is a complication that doesn't really give a lot of value other than being slightly more elegant. It is at the cost of significant complexity in the parser as well as being complex to the programmer to understand what is going on in deeply nested conditionals.

Any objections, strong or otherwise, to simply requiring the very next token be a return?

So

t ? -> $S2 ^ ::

would be good while

t ? -> $S2 :: ^

would be an error.

walkie commented 3 years ago

That would be fine, although I actually think I would prefer just completely rolling back the changes made because of this ticket and marking it as "won't fix".

Requiring a single terminator at the end of every handler (as Frame currently does) is less syntactic overhead than requiring a terminator after every transition. And the semantics of returning after a transition is relatively easy to implement in the backend, as I've done for the Rust backend already.

In my initial issue report, I thought that return was not allowed inside of branches at all, which would have been a major limitation. Once you corrected me that they are supported, but you still need the final terminator, I was able to fix the semantics and write lots of tests checking various interactions of transition/change-state/continue/return. Things seems to work well, and I think this is a pretty good solution.

What do you think about just rolling the changes back, going back to always requiring a final terminator, and delegating the fact that transitions/change-states imply a return to the backends?

walkie commented 3 years ago

Also, if you're on-board with this idea, I can go ahead and roll back the changes on the v0.6.0 branch and merge in my other fixes. Just let me know!

frame-lang commented 3 years ago

Ok sounds good. Roller back!

walkie commented 3 years ago

The commit history ended up being a little too messy to automatically revert the changes, but I was successfully able to manually revert them (i.e. diffing with an old version and deleting/restoring code). This ended up being slightly better anyway since I was able to retain some of your other code/comment improvements you made along the way.

I'm gonna let you merge the PR since it's obviously well outside of the scope of the Rust backend!

I'll rebase and merge my other changes onto v0.6.0 once you do.

frame-lang commented 3 years ago

Tis in!

On Fri, Sep 10, 2021 at 10:38 PM Eric Walkingshaw @.***> wrote:

The commit history ended up being a little too messy to automatically revert the changes, but I was successfully able to manually revert them (e.g. diffing with an old version and deleting/restoring code). This ended up being slightly better anyway since I was able to retain some of your other code/comment improvements you made along the way.

I'm gonna let you merge the PR since it's obviously well outside of the scope of the Rust backend!

I'll rebase and merge my other changes onto v0.6.0 once you do.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/frame-lang/frame_transpiler/issues/17#issuecomment-917345644, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABOQ2RUWTHTT2EM37MOVNE3UBLTMNANCNFSM5C32O2BA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

--

Mark Truluck - Inventor

e | @.*** w | frame-lang.org

https://www.patreon.com/framelang [image: Frame Language] https://www.patreon.com/framelang