VPL is not declarative

[MobsyaBot]

Issue by stephanemagnenat Sunday Aug 06, 2017 at 08:19 GMT Originally opened as https://github.com/aseba-community/thymio-vpl2/issues/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.

[MobsyaBot]

Comment by davidjsherman Sunday Aug 06, 2017 at 09:48 GMT

---

So, as long as you have don't-care positions, you can trigger two rules with the same conditions: r1(0,x), r2(x,0) both match (0,0). If I understand the goal, teaching autonomous robotics is a noisy world, a realistic semantics would be a random choice between the two. It might be fun to think of an exercise for the children that demonstrates this. For example, a line follower with the above rules, would tend to go straight only if there is no bias.

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.

[MobsyaBot]

Comment by davidjsherman Sunday Aug 06, 2017 at 10:29 GMT

---

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

[MobsyaBot]

Comment by stephanemagnenat Monday Aug 07, 2017 at 07:03 GMT

---

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?

[MobsyaBot]

Comment by marvelous Monday Aug 07, 2017 at 08:07 GMT

---

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.

[MobsyaBot]

Comment by stephanemagnenat Monday Aug 07, 2017 at 16:22 GMT

---

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:

Currently, the second line is never executed, because it has been evaluated to true at the first evaluation step, even though it was never actually executed (because the first line was instead). We could change this behaviour such that the transition bit of a line is only set when it is actually executed.

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:

• Do we want to detect and forbid conflicts? If so, what do we mean by conflict? Do we consider any possible event conflict, with or without action conflict?
• Do we want to improve the current behaviour with event conflict in case of a single state and no action conflict?

[MobsyaBot]

Comment by marvelous Monday Aug 07, 2017 at 18:12 GMT

---

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.

[MobsyaBot]

Comment by marvelous Monday Aug 07, 2017 at 18:13 GMT

---

BTW, do you have a realistic VPL1 program for this issue?

[MobsyaBot]

Comment by davidjsherman Tuesday Aug 22, 2017 at 07:24 GMT

---

For simplicity, let's invent a text syntax: ...||... for motor speed, [...] for bottom sensors, /...\ for front sensors, top(...) for top LEDs.

Example 1

[ 1 1 ]  ->  100||100
[ _ 0 ]  ->  150||50
[ 0 _ ]  ->   50||150
[ 0 0 ]  ->  top(31,0,0)

This 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 2

/ 1 1 _ _ _ \  ->  150||50
/ _ 1 1 _ _ \  ->  300||0
/ _ _ 1 1 _ \  ->    0||300
/ _ _ _ 1 1 \  ->   50||150
/ _ _ 0 _ _ \  ->  200||200 ; top(0,31,0)
/ _ _ 1 _ _ \  ->  top(31,0,0)
/ _ 1 _ _ _ \  ->  top(15,15,0)
/ _ _ _ 1 _ \  ->  top(15,15,0)

This 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 / 1 1 0 _ _ \ is true? When / _ 1 1 1 _ \ is true?

Possible answers: (red, yellow, or orange); (150||50, 200||200, or 175||125); (300||0, 0||300, 300||300, or 0||0)

Comments

These 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?

[MobsyaBot]

Comment by marvelous Tuesday Aug 22, 2017 at 10:41 GMT

---

Great examples! Let's ping @motib and @FrancescoMondada for input.

[MobsyaBot]

Comment by motib Tuesday Aug 22, 2017 at 11:05 GMT

---

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!

[MobsyaBot]

Comment by FrancescoMondada Tuesday Aug 22, 2017 at 11:27 GMT

---

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.

[MobsyaBot]

Comment by marvelous Tuesday Aug 22, 2017 at 12:07 GMT

---

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?

[MobsyaBot]

Comment by davidjsherman Tuesday Aug 22, 2017 at 12:10 GMT

---

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!

[MobsyaBot]

Comment by davidjsherman Tuesday Aug 22, 2017 at 12:15 GMT

---

@marvelous well spotted. I suppose we could say that each set of actuators (motors, LEDs, sound, IR comm) run in separate threads?

[MobsyaBot]

Comment by FrancescoMondada Tuesday Aug 22, 2017 at 12:18 GMT

---

@davidjsherman why the robot will never turn red? Because we have transition bits per sensor and not per line, and this a problem. @marvelous If the sensors go from / 1 0 0 0 0 \ to / 1 1 0 0 0 , both 150||50 and top(15,15,0) should be executed, both detect the transition of this sensor. But if the sensors go from / 0 0 0 0 0 \ to / 1 1 1 0 0 \ only the last motor command (or the first) will be executed.

[MobsyaBot]

Comment by marvelous Tuesday Aug 22, 2017 at 12:41 GMT

---

@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.

[MobsyaBot]

Comment by FrancescoMondada Tuesday Aug 22, 2017 at 12:52 GMT

---

@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

[MobsyaBot]

Comment by marvelous Tuesday Aug 22, 2017 at 13:10 GMT

---

The implementation will be simpler if we do the conflict resolution at the aesl variable level. The motor action block always sets both motor.left.target and motor.right.target, so if two motor action blocks are executed sequentially by the runtime, the effect will be only the last action.

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).

[MobsyaBot]

Comment by davidjsherman Tuesday Aug 22, 2017 at 13:29 GMT

---

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?

[MobsyaBot]

Comment by davidjsherman Tuesday Aug 22, 2017 at 13:33 GMT

---

@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.

[MobsyaBot]

Comment by marvelous Tuesday Aug 22, 2017 at 14:01 GMT

---

You are right, @davidjsherman! Going back to

[ 1 1 ]  ->  100||100
[ _ 0 ]  ->  150||50
[ 0 _ ]  ->   50||150
[ 0 0 ]  ->  top(31,0,0)

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:

[ 1 1 ]  ->  100||100
[ 1 0 ]  ->  150||50
[ 0 1 ]  ->   50||150
[ 0 0 ]  ->   xx||xx ; top(31,0,0)

(we won't tell him that the lights never turn back off)

[MobsyaBot]

Comment by motib Tuesday Aug 22, 2017 at 14:14 GMT

---

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.

[MobsyaBot]

Comment by motib Tuesday Aug 22, 2017 at 14:40 GMT

---

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.

[MobsyaBot]

Comment by davidjsherman Tuesday Aug 22, 2017 at 14:41 GMT

---

@motib and purely declarative logic languages that didn't even get that far!

[MobsyaBot]

Comment by davidjsherman Tuesday Aug 22, 2017 at 14:44 GMT

---

@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)?

[MobsyaBot]

Comment by davidjsherman Tuesday Aug 22, 2017 at 15:03 GMT

---

@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 2⁵ rules for all of the combinations?

[MobsyaBot]

Comment by marvelous Tuesday Aug 22, 2017 at 15:18 GMT

---

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?

[MobsyaBot]

Comment by ddoak Tuesday Aug 22, 2017 at 15:22 GMT

---

I just knew this thread was going to be good. /gets popcorn :-)

[MobsyaBot]

Comment by FrancescoMondada Tuesday Aug 22, 2017 at 15:27 GMT

---

@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?

[MobsyaBot]

Comment by mbonani Friday Aug 25, 2017 at 13:13 GMT

---

To go forward let's explain some actual thing and why there is misunderstanding. There is a difference between VPL1 and VPL2 generated code. First taking simple example 1, I will then make test of example 2. As I am less familiar with terms like "declarative" , single tread etc, I make the example 1 on the 2 platform and tested it on real Thymio.
With VPL1:

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?).