Subroutine calls from subroutines don't work

[ptpj]

Moving here from the initial report: https://github.com/aseba-community/aseba/issues/752

Adding a procedure call to a procedure block results in an empty AESL subroutine being generated.

The code that causes that is here: https://github.com/aseba-community/blockly/blob/866c66c66df78100816c77d5bd8879edacf06927/generators/aesl/procedures.js#L18

There seems to be no apparent reason. The comment in code says: "AESL does allow subroutines to call other subroutines, but they need to be defined in the correct order." But it doesn't seem to be the case, the following code works fine in AESL:

sub AA: callsub BB

sub BB: ...

AESL is happy as long as there are no cycles.

[ptpj]

There's a similar block here, not sure which place is relevant, possibly both. https://github.com/aseba-community/blockly/blob/866c66c66df78100816c77d5bd8879edacf06927/generators/aesl/thymio.js#L61

[davidjsherman]

So, first a general remark about what I've learned about Blockly. Programs are built by connecting blocks. The philosophy is that block connections that violate the grammar or the type constraints shouldn't be possible. This provides a strong guarantee that every program is valid, but doesn't allow the “I'll-figure-it-out-later” style that is possible in a text language. (The Aseba Studio editor is the latter, but does flag errors on the fly.) Blockly has two mechanisms for checking constraints, and one for constructing programs:

1. In the JSON block specification, one uses Checks for immediate type checking. This looks at the immediate block neighbors and only allows a connection if they are of the appropriate type. This mechanism is intended for block arguments, for example arithmetic can't be done on strings, and for simple grammatical constraints, for example that one can't connect a block after a STOP block.

2. In block Extensions, where arbitrary code can be hooked up to implementation the block. If I understand the documentation, this code can potentially walk over the syntax tree.

3. The principle is that drop-down menus in blocks are populated dynamically. For example, the list of subroutines that one can call, should depend on the subroutines that have been defined. So it is impossible to build a program that calls a subroutine that doesn't exist.

Which of these mechanisms is best for subroutines, depends on what the constraint is, exactly.

Ideally, all of the grammatical and type constraints that are checked in Studio, are expressed in Blockly.

[davidjsherman]

Second, I haven't been able to find documentation of the constraints on subroutines in the Aseba language, beyond that statement that they can't be recursive. @stephanemagnenat would know what the true constraints are.

Looking at the code for the Aseba compiler, subroutine names are resolved during the type checking step, so the comment blockly generators/aesl/procedures.js#L18 doesn't appear to be justified. If I understand the code, the reason that subroutine calls can't be recursive is that verifyStackCalls at aseba compiler/analysis.cpp#L32 conservatively tries to prove that the stack never overflows.

[stephanemagnenat]

@davidjsherman you are correct, initially a subroutine could only call a previously-known subroutine but this prevented the call of a subroutine from the initialization code so this was relaxed in aseba-community/aseba@2b6b25e (see aseba-community/aseba#158 for a discussion). Your analysis of stack verification is correct.

So it might be that the constraint in Blockly is too strong. One only needs to verify that a subroutine exists, that the call tree does not form loops and that the maximum stack depth is below the VM stack size (this last point is hard to check within Blockly, but two previous should be doable).

[davidjsherman]

It should be easy to walk the block graph to verify that there are no loops. It isn't necessary to check whether a subroutine exists: the subroutine palette only contains callsub blocks that have already been created (I checked, it is not a pulldown menu but a separate new block for every defined subroutine).

For checking the stack depth, it would be better to call the compiler. I'm not confident that this can be done fast enough to interactively disallow block connections. I do have an asm.js version of asebacompiler, but I haven't finished the WebIDL interface definitions and can't yet test it from a web page.