# Explaining Event-Driven Programming in the context of the Structured Programming Theorem

I'm a retired college teacher. I've been asked to "teach coding" to a dozen very bright seventh-graders using the Micro:Bit kits the school has on hand. I have a total of seven contact hours available. In three hours, we've learned about algorithms, variables, and operators.

On Tuesday we'll write a program for "red light / green light" and learn the difference between sequence and selection. The following week we'll do something with a loop and I'll add "iteration" to the vocabulary. While I probably won't say "Structured Programming Theorem," I was going to tell the kids that sequence, selection, and iteration are "all you need."

The trouble is, the MakeCode block language has "on-blocks" which fire when events occur, e.g. "on Button A pressed." You can't avoid these.

So, how do I explain events, or "on-blocks" in the context of sequence, selection, and iteration? (The best I've been able to come up with so far is that there's a hidden loop of if statements checking for events, which is probably how the on-blocks are actually implemented, but unlikely to be satisfying to twelve-year-olds.)

• Note that a Turing Machine has no notion of asynchronous action. A TM is deterministic. Event driven programming isn't. I'll try to come up with a satisfying answer, but you are, at best, simulating events using a polling loop. – Buffy Mar 1 '20 at 16:42
• Event-driven programming is non-deterministic in the sense that a specification for an event-driven language generally doesn't specify the order that event handlers will be executed in. That doesn't mean that an implementation of an event-driven language must be non-deterministic in the sense of not always producing the same output via the same sequence of internal states when executing the same program. Javascript for instance is event-driven but single-threaded, and most implementations are deterministic in the latter sense because to not be, they would have to intentionally not be. – kaya3 Mar 1 '20 at 17:56
• See the question on lying to students v being pedantic: cseducators.stackexchange.com/questions/4717/…. My answer suggests "lying honestly" or something. – Buffy Mar 2 '20 at 0:15
• Sequence, if & while are "all you need" for sequential programming, giving possible sequences of states or events per assignments & calls that they surround. But you have more to what you are doing than this--you have a sequential process & an event-generating process--so non-determinacy & concurrency. You need to give--just as when you only have a single sequential process--a "model of computation"--a system state structure & how it starts & changes per evolution of some process(es). (Similarly, teaching iteration should include how to reason re a loop constantly advancing to a goal state.) – philipxy Mar 4 '20 at 23:52
• I had considered adding, unfortunately these fundamental semantics are typically not given when presenting programming & then learners literally do not know what they are doing & the lucky ones sort of learn some stuff--though not to specify or justify programs. Now having read the kit documentation, alas, that is exactly the case with it. We are not told the semantics of "event handlers". Eg what if one event happens during processing of another?--Is the event lost? Is it enqued? Does a device wait, or detect further events? Etc etc. Sad. But typical. The blind blinding the blind. – philipxy Mar 5 '20 at 4:01

In the spirit of K.I.S.S., I believe that you can call this "selection" (it is), and no one will bat an eyelash. At this stage, selection within a program won't be fully differentiated from selection by a user in any case, so no one will be expecting anything different in any case.

If you feel the need to explain further, just say that, if you think about it, these really seem like if statements, too. They just don't use the word for it. But if we were to go somewhere into the code that makes the whole program go, we'd discover that our instincts are correct, because there really are if statements that drive this, and they look something like:

if button A gives a signal, find the "on Button A pressed" block and run from there.

• This is likely to be true, but one could imagine an event-driven implementation working differently. For example, there could be a data structure mapping event kinds to event-handler lists, and when an event is triggered it immediately looks up the right list and invokes each handler, instead of adding the event to a queue to be dispatched later. That is how triggering events works in e.g. JS/jQuery; so it's possible to do it with neither conditional statements nor unbounded iteration. The missing piece is that "sequence, selection and iteration" doesn't include dynamic dispatch of functions. – kaya3 Mar 2 '20 at 13:16
• @kaya3 Definitely, and that's an interesting point. Though I certainly wouldn't bring that up at this point with these kids. And I suppose if I were being pedantic, I would say that that would ultimately push the if down to another layer of abstraction, so it's still not innaccurate to say that that if is somewhere in the code that makes the whole program go. 😁 – Ben I. Mar 2 '20 at 13:39
• Yes, I wouldn't bring it up in a lesson. I think it's a matter of philosophy, but I argue that it is inaccurate to say if must be in there somewhere. At the lowest level, the program is doing conditional jumps, sure; but a conditional jump forwards is not always logically an if statement, and a conditional jump backwards is not always logically a loop. The main benefit of "structured programming" is to avoid the direct manipulation of the instruction pointer required in assembly, so I think it would be perverse to count assembly programs as "structured programs" in that sense. – kaya3 Mar 2 '20 at 13:52
• @kaya3 I'm intrigued by your assertion that a conditional jump is not always an if statement, since I think of them as one and the same. I am open to learning something new, however. I agree that a large goal of structured programming is to prevent the human from having to work at a low level, but that doesn't make the low level less valid. It just means that we can step further away from the weeds. – Ben I. Mar 2 '20 at 18:50
• For example, a while loop might be compiled to (start); conditional jump to end; loop body; jump to start; (end). So the conditional jump is forwards but there was no if statement, and the repetition is achieved by an unconditional jump backwards. A conditional jump could also break out from the middle of a loop, which isn't possible with just "sequence, selection and iteration" in the structured program theorem. – kaya3 Mar 2 '20 at 18:59

I don't see that there's anything to explain, because there's no apparent contradiction between a set of language constructs being "all you need", and a language having more constructs than are "needed". Languages are designed to have constructs that are useful for human programmers to easily and concisely express what a program should do, not just a minimal set of constructs for it to be possible to express programs.

It's not even necessary to explain that event-driven languages are implemented using hidden conditional statements and loops; and as Buffy notes in the comments, they may not actually be implemented that way anyway. If you want to tell your students that they could be, then I see no problem with that. But consider this:

• Untyped lambda calculus is Turing complete, so "all you need" is function definitions and function application. Does that imply that conditional statements and loops must be implemented with hidden function definitions and hidden function applications? Well, no, it doesn't imply that.
• The logical NAND operation is functionally complete, so "all you need" is NAND gates. Does that imply that computers are made only of NAND gates? Again, no, it doesn't.
• As shown in this paper and amusingly demonstrated in this compiler, the x86 mov instruction is "all you need", i.e. any C program can be compiled to a sequence of unconditional writes to memory (at addresses read from memory). But the rest of the x86 instruction set is, of course, not implemented that way.

What I will suggest is that if you do want to mention that sequence, conditional statements and loops are "all you need", then you should add that real programming languages have more control-flow constructs than just those, because the additional ones (e.g. subroutines/function calls and return, try/catch, event loops…) are convenient.

Disclaimer: I am aware that this does not directly answer the question, but I it still useful nonetheless to question the question itself.

IMHO, it seems you are overthinking this issue. You are introducing a whole new world of programming to 12 year olds in seven hours. There will be many huge gaps in their understanding and many things will remain partial knowledge. And that's OK. Make them passionate about the subject and they will search for more about the parts they are interested in.

Micro:bits allows for lots of interesting experiments using the inputs/outputs. Instead of worrying about "Selection, Iteration and Sequence" you could focus on, you know, building cool stuff. If it were me, I would rather have students finishing the course with something of their own making and that they know how to explain how it works to their parents than worrying about abstract CS concepts many college students struggle to understand.

• I disagree. The students should certainly have fun, and based on yesterday's game of Rock Paper Scissors Lizard Spock, with score keeping using the Micro:Bit buttons, they are. If I do this right, they'll also go away with at least some understanding of the science behind what they're doing. When they get to college, maybe they won't struggle with what you have called abstract concepts. – Bob Brown Mar 4 '20 at 13:24
• My reasoning was that college is years in the future. They may or may not choose CS as a major. They may or may not take a course in theoretical computing and, even if they do, they'll probably not remember a 16hour course taken almost 10 years ago. IMHO, you are doing a good job. Students are having fun and this is what would matter if I were in your shoes. – igordsm Mar 4 '20 at 18:10
• The semester has rocked along, moving to a virtual environment, and "my" kids can explain sequence-selection-iteration. At this point, the brightest ones can also say "Turing complete" and equate that to the "effectively computable" requirement for a procedure to be an algorithm. I told you these kids were smart! – Bob Brown Mar 26 '20 at 13:30

You might first begin by explaining how a program begins running. The program is not always running. It simply stored somewhere, but dormant. Some event external to the program causes it to run. Generally this is a click on an icon. Some running program is notified of this click and does the work necessary to get the selected program running.

When you write an on-block you are defining some code to to be run when a specific external event occurs. That is, you don't see the invocation of this code within in your own program. But you have told the outside world that if an event occurs, notify me by running this block of code. If you never define such a block, then your program will not be notified that it has happened. Since the on-block is inside your program it can alter the state of the program. As Scott Rowe pointed out, your program is "listening".

Ultimately, it all begins with the hardware and operating system. Actions like keyboard presses, or mouse movement cause an electrical signal. The interrupt handler looks at the signals and decides what to do with them. Eventually, it is passes them on to the program(s) that have expressed interest in the event. But just because program has expressed interest in a type of event, doesn't mean it will receive that event. A drawing program is interested in mouse movement so you can "draw" things by moving the mouse. But even if the program is running, it will only receive the event when the mouse is in the window, and the window has focus.

And when your program terminates, it will no longer receive any events until it is run again. If you turn off your computer, no signals are handled. You can type on the keyboard, but there is nothing listening.

Two ideas:

1. The recommendation for teaching is usually to explain things in a way that the students can understand. Usually this means giving an age-appropriate response to questions that young children ask. The key is to present your material, and only go outside it when someone asks a question.

2. It is fine to say that Sequence, Selection and Iteration are all that you need to write a program. But to have a computer you also need interrupts, otherwise the computer would not respond to us at all.

When the subject of interrupts came up, I would say that originally, there was an interrupt line that went straight in to the CPU and which caused it to set aside what it was doing and invoke a different (small) program to handle the interrupt. Then I would explain that this is how the keyboard is read, the mouse handled, the screen redrawn, and basically almost everything else that makes a computer actually interact with people, rather than just calculating something invisibly.

Interrupts are on a different level than programming. It changes a machine in to a tool that responds. Otherwise we would still be using punched cards. Programming is necessary to get the computer to 'talk' to us, but not sufficient for it to 'listen'.