VPL is not declarative #124
Comments
|
So, as long as you have don't-care positions, you can trigger two rules with the same conditions: Whatever the choice of semantics, the important thing is feedback to the programmer. My memory is rusty but I think checking for ambiguous rules is the same as constructing an Aho-Corasick automaton. |
|
The sensors are random number generators. Another reasonable semantics would be to give the priority to the sensor that has changed the most since the last clock tick |
|
That is interesting indeed. There are many possible semantics indeed, depending on whether we only consider the close/far thresholds (and hence the conditions), which works only when these thresholds cannot be changed, or whether we consider general conditions. Actually, when I think about it, I think that in VPL2, all true transition within the reactive mode are taken. @marvelous, is it correct? |
|
No, the implementation is single-threaded, only one row is triggered simultaneously. We could have one thread per row to support multiple concurrent row triggers, but the problem would resurface anyway when we add a mutable state variable: last write wins would be an obvious implementation choice. |
|
I think that, without multi-threading, one could improve the current situation, even assuming we do not want to detect and forbid conflicts. Indeed, even with a single state and no action conflict, the current behaviour is unexpected. Let us consider the following program, with only one state, with the robot lying on a white surface: I agree that it will not solve cases with action conflicts, but at least it will behave as naturally expected in a reactive setting with no action conflict. So there are two questions:
|
|
That sounds like an ugly hack. I much prefer to do an exhaustive check and raise a compilation error if not too runtime-intensive. An other option that seems simple to me is to do a runtime check, raise an aesl event and stop the robot when multiple transitions are possible, prompting the programmer to remove the ambiguity. |
|
BTW, do you have a realistic VPL1 program for this issue? |
|
For simplicity, let's invent a text syntax: Example 1This is an attempt at a black line follower. The student's idea is to turn away from white, and to shine red if the robot gets lost on white. Question: if the robot gets lost, does it turn? Deterministically or stochastically? Example 2This is an attempt at a wall avoider, where the student requires a consensus between proximity sensors to make a decision. If the threat of hitting the wall is high the robot swerves in place, otherwise it turns while advancing. If nothing is directly in front, then go forward at speed. Independently, shine red or yellow if a wall is detected. Questions: what color is shown when rule 2 is triggered? What speed is used when Possible answers: (red, yellow, or orange); (150||50, 200||200, or 175||125); (300||0, 0||300, 300||300, or 0||0) CommentsThese programs are syntactically correct and have a clear intention. They don't have to be the programs we would have written, or even correct; they are plausible programs that a student might try, and hope to learn from the observed behavior of the robot. We can't forbid these programs because of an arcane rule, that can't be explained to a 10-year-old. I can think of four semantics for these programs: deterministic using rule order, stochastic transition system, constraint solving over finite domains, analog (average between requested values). But really the question is, which semantics is best for helping students learn to program autonomous robots in a noisy world? |
|
Great examples! Let's ping @motib and @FrancescoMondada for input. |
|
David's examples use "don't care"s which are very much like variables in Prolog. I am in favor of choosing the Prolog semantics: execute the first clause that unifies, here, the first event-action pair whose event evaluates to true. It is easy to explain and deterministic, hence, repeatable, so you can debug the program. Any non-deterministic semantics would just confuse kids. There is lots of "noise" in the sensors and the environment, so I don't see the need for noise in the program semantics! |
|
It is hard that in the case of / _ 1 1 1 _ \ all sensors become true at the same time. Therefore I expect several lines to activate during the steps between / _ 000 _ \ and / _ 1 1 1 _ . This should better fit to what the programmer expects. If all three become 1 at the same moment, I agree with Moti that it should be deterministic: even the last or the first line satisfying the conditions should be executed. But the transition bit should be per line, and not per sensor. |
|
In example 2, the intent of the user seems to run 2 things concurrently: motor control and light control (the 5th line should even be split in two!). If the sensors go from / 1 0 0 0 0 \ to / 1 1 0 0 0 , should 150||50 or top(15,15,0) be executed? @davidjsherman says that both should be executed, @motib and @FrancescoMondada say that only 150||50 should be executed. Do I get this right? |
|
I agree with @FrancescoMondada that the noisiness of the environment means that many rules get their chance. But what is unfortunate is that a non-declarative semantics leads to a bias, which is what I tried to show in the examples. There isn't any way for the young programmer to define a fair strategy. In example 1, the lost robot always spins clockwise. In example 2, there is a bias towards turning right. And I fear that the programmer will have a hard time understanding why the lost robot never turns red. Actually, as a teacher I fear the trouble I will have explaining why to the programmer! |
|
@marvelous well spotted. I suppose we could say that each set of actuators (motors, LEDs, sound, IR comm) run in separate threads? |
|
@davidjsherman why the robot will never turn red? Because we have transition bits per sensor and not per line, and this a problem. |
|
@FrancescoMondada so you are arguing for having the conflict resolution between actions, not between lines? Both lines should run, but if they have conflicting actions only one of these actions is executed? Sorry if I misunderstood first. |
|
@marvelous yes, only conflict resolution between conflicting actions (and executing all of them will result in having the last only applied), it does not make sense to have conflicts between actions of different type |
|
The implementation will be simpler if we do the conflict resolution at the aesl variable level. The motor action block always sets both Using this last writer wins conflict resolution [insert distributed systems paper reference here], we can execute the action blocks in program order (last action block wins) or in reverse program order (first action block wins). |
|
Hello everyone, you keep talking about "program order" as if that is a thing, but the issue is named "VPL is not declarative". An implicit priority between rules is a cognitive bias that comes from sequential programming! Has a decision been made that you want to teach that to young programmers? |
|
@FrancescoMondada, I guess I don't understand which problem you mean in your comment? I understand that you want to trigger rules on the rising edge of sensor changes. Is the problem this strategy, or my example? Sorry to be so slow. Thanks for explaining. |
|
You are right, @davidjsherman! Going back to The issue is that [ 0 0 ] would effect both 150||50 and 50||150. But it's not an issue that it would also effect top(31,0,0). Should the program detect this situation (before or during execution) and explain it to the user? So he would arrive to this solution: (we won't tell him that the lights never turn back off) |
|
I am now confused as to the semantics of VPL. My intuition is that - while all event-action pairs are notionally parallel - in practice there is an endless loop that checks the events sequentially in textual order, jumping back to the first pair at the end of the program. Or are separate threads initiated for each pair? With interrupts to schedule them? Do multicore computers execute the threads in true parallelism?! If my intuition is correct, you teach that the pairs are executed in parallel, but if that leads to weird behavior, then the sequential model needs to be explained. Even in languages like Prolog that are designed to be declarative, the implementation is sequential. There were parallel logic programming languages, but they never made it outside the research labs. |
|
Let me add a clarification: I am using the (for me very important) concept of a "notional machine" proposed by Ben du Boulay in 1986. (For a modern survey see: Juha Sorva. Notional machines and introductory programming education. ACM Transactions on Computing Education (TOCE) 13(2), 2013.) This is the architecture that defines the semantics, even if it doesn't precisely reflect the implementation. Beginning students, in particular, should be presented with a very simple notional machine. That is why I am comfortable with a VPL notional machine that is fully parallel, even if the underlying implementation is different, and even if the notional machine has to modified in some situations. |
|
@motib and purely declarative logic languages that didn't even get that far! |
|
@motib I agreed that the semantics of the notional machine is paramount, we shouldn't define the meaning of the language in terms of what it easy to implement. When you say "fully parallel" do you mean that the sensor surveillance threads are running in parallel, or that every rule is notionally running in parallel (and thus will fire independently whenever its conditions are met)? |
|
@marvelous Yes, it would be nice to give advice for completing rules as you suggested. But I worry that it will lead to a combinatorial explosion. In Example 2, I made a cascade of all the front sensors. Wouldn't a complete solution require you to add 25 rules for all of the combinations? |
|
Yes, an unambiguous solution for example 2 seems impractical to say the least. So where do we go from here? Last/first action block wins doesn't seem bad to me, but you seem to want an other behaviour. Averaging or metastable? I remember @stephanemagnenat saying that a big part of this issue from his point of view is that the real-time execution makes it very hard for the user to understand and address the issue. Maybe some kind of replay functionality that highlights where conflicting action blocks were executed at the "same" time? |
|
I just knew this thread was going to be good. |
|
@davidjsherman sorry, for me discussing in such a chat is complex a not very productive. Perhaps I am wrong in my assumptions. Let start from beginning: why do you say that the lost robot never turns red . Is this in example 1 or 2? |
|
To go forward let's explain some actual thing and why there is misunderstanding. There is a difference between VPL1 and VPL2 generated code. When the robot go on white the generated code make that all the three event are fired and finally the robot turns right and it is red. It is what Francesco is used to and here the order matters. If we invert line 2 and line 3 the behavior is changed, robot turns left and is red. As all event are fired all action are executed and finally last win when two actions are on the same element. In VPL2, as it is single thread, the Thymio only turns left and never become red. It execute the first one and then it is finished. So it is why David was saying it never go red and it will be hard to explain to student. For me in this simple example 1, it is logic for me that it's behave like in VPL1. I think it is the position of Francesco. Orders matter but finally it can be explain to student specially if we show the generated code. I will now test example 2. Lets see the difference with actual implementation and if we can agree if implementation of VPL1 it is ok or if we have to improve to be declarative (logique?). |
Sunday Aug 06, 2017 at 08:19 GMT
Originally opened as aseba-community/thymio-vpl2#116
As pointed out by @davidjsherman, VPL is close to being declarative, but is not because when events conflicts (for instance with multiple configurations of distance sensors), the order of lines of appearance matters.
This problem has also been reported by teachers, and is actually one cause of the difficulty of using VPL to write non-trivial problems: the notional machine becomes difficult to create when the order matters.
It is interesting to think how this could be improved: currently, VPL forbids similar events or event configurations on two different lines. This could maybe be extended to forbid non-disjoint event conditions.
The text was updated successfully, but these errors were encountered: