Reactive Scratch technical proposal

Scratch: the positive

Scratch is an amazing IDE and runtime for children to program small video games and interactive animations. Scratch has lots of great features:

These features have made Scratch extremely successful.

Scratch: the negative

However, Scratch as a programming language is awful, and it is particularly inadequate for reactive programming. In reactive programming, the main action of the program is to react to outside events that it does not control, as opposed to the more traditional transformational programming, where some input is given at the start, and the program produces some output based on it.

A Scratch program is composed of a set of event handlers attached to each sprite, and these event handlers communicate with shared mutable state - an area of programming known to be difficult even for specialists. In fact, Paul McKenney, the concurrency specialist of the Linux operating system, starts his book Is Parallel Programming Hard, And, If So, What Can You Do About It? by saying

The purpose of this book is to help you program shared memory parallel machines without risking your sanity

which answers the question of the title of his book by a resounding "Yes". Given that it is challenging even for adults, this is really not what we should be teaching children.

More concretely, reactive programs often involve patterns like "repeat an action A until an event E occurs". If the action A is simple, and the event E is built-in, this is not too difficult to express in a language like Scratch:

repeat
  A
until E

However, things are generally not so simple. The action A often takes a long time to execute, but we often still want to immediately stop executing A immediately when E occurs. Let us consider the case where A is composed of three sub-actions A1, A2, and A3. As a computer scientist, it is pretty clear that this can be encoded: 

repeat
  A1
  if not E
    A2
  if not E
    A3
until E

To a computer scientist, this is starting to look a lot like an automaton. In fact, reactive systems are implemented using automata. But that does not mean that it is how they should be programmed. Indeed, even in this very simple case, it already looks quite cumbersome. Now, consider that, in addition, usually, a reactive program involves multiple such levels of preemption, as well as concurrency. Moreover, if we have written A, and then want to add the possibility to preempt it, we have to edit all of A, and this is a very error-prone process.

Moreover, "until E" cannot be expressed directly in Scratch: there is no way to test within an event handler whether another event is triggered. Some other frameworks do offer this kind of test.

As the size of the program grows, reactive programs written in the programming style of Scratch turn into the "spaghetti" encoding of an automaton: all operations are split into "atomic" components A1, A2, ..., An that take one step of execution, and guarded by conditions C1, C2, ..., Cn on the amalgamated state S, which evolves according to an amalgamated "next" function: 

S := S0
repeat
  if C1
    A1
    S := next(S)
  else if C2
    A2
    S := next(S)
  else if Cn
    An
    S := next(S)

Our proposal: Reactive Scratch

Reactive Scratch is an extension of Scratch with the primitives of Esterel, a synchronous programming language that allows the simple composition of concurrency and preemption.

Time

An Esterel program describes how to react at each reaction instant, based on signals. A reaction instant happens instataneously at some point in real time, as in the following figure, where the arrowed line represents real time, and the ticks represent the reaction instants:

reaction instants

These instants do not have to be regularly spaced in time (although they are in Reactive Scratch)

Concurrency

The first ingredient of Esterel is the concurrent composition: given two Esterel blocks p and q, they can be executed concurrently with (using our Reactive Scratch syntax)

concurrently
  p
with
  q
end

which in plain Esterel is written

p || q

Signals

The second ingredient is signals, which make it easy for two Esterel blocks to interact. Scratch itself has messages, but these are rather limited in expressivity. A signal S can be made available to p with

signal S in
  p
end

which allows p to contain signal emission

emit S

and testing whether signals are present (in our syntax):

if signal S is present then
  p
else
  q
end

which in plain Esterel is written

present S then
  p
else
  q
end

or even (in Esterel 7)

if S then
  p
else
  q
end

In Scratch, messages are somewhat similar, except that (1) they are global, which makes it difficult to separate internal messages used to implement a functionality within a block of code, from external signals meant to interact with the rest of the program (2) they cannot be valued, which means that to provide information in addition to the presence of a signal, one has to encode message passing with state.

Preemption

The third ingredient of Esterel is preemption: a block p can be put inside a trap T

trap T in
  p
end

where p can contain

exit T

which causes the execution of the whole trap block to terminate immediately.

Rather than terminate the execution of a block, we might want to suspend it:

suspend p when S

Background

Esterel is a language to write structured automata by expressing the control structure, rather than encoding it using mutable state.

This idea of using Esterel (or similar things) is in fact not original at all:

and many more that reinvented some ideas of Esterel.

The best textbook on Esterel remains "Compiling Esterel".

Reactive Scratch is developed by Jean Pichon-Pharabod.

Last modified: 2022/06/08