In October 2020 I took Dave Beazley’s Advanced Programming with Python course. Since I wrote a series about his SICP course and the Raft course, I figured I’d write about this one too :).
In the last post of this series, we talked about inheritance in Python. This time, we’re talking about programs that need to do multiple things at once.
Our example: the humble elevator.
An elevator needs to move up and down based on the buttons that people have pressed. It needs to open its doors at different floors, not based on which floor was requested first, but rather based on whether or not there has been a request at all for each floor it passes.
As an elevator is operating, it also needs to process new requests. There’s some threshold on how much advance notice it needs—we’ve all been on an elevator where someone only pressed their button as the elevator was reaching their floor, and it raced right past.
How might Python-based elevator control software work?
Let’s start with a test case.
Suppose I decide that I want to do the following:
control = ElevatorControl()
elevator = Elevator(control)
panel = ElevatorButtonPanel(elevator)
panel.request_button_pressed(5)
panel.request_button_pressed(4)
panel.request_button_pressed(3)
panel.request_button_pressed(2)
panel.request_button_pressed(1)
panel.request_button_pressed(5)
time.sleep(15)
panel.request_button_pressed(4)
time.sleep(6)
panel.request_button_pressed(4)
panel.request_button_pressed(1)
Here’s what’s happening:
- When we turn the elevator on, some combination of requests come in for floors 5, 4, 3, 2, and 1. Maybe people on each of these floors request an elevator, or maybe somebody inside the elevator requests a floor. It doesn’t matter.
- 15 seconds after the elevator starts running, after the elevator has picked everyone up and is headed back down to floor 1 with them, a request for floor 4 comes in.
- As the elevator is headed up to floor 4, another request for floor 4 comes in, and a request for floor 1.
What should happen? Ideally, we’d like the elevator to go up from floor 1, floor by floor, opening at each floor, until it gets to 5. Then we would like it to come down, not stopping at all, to floor 1. It should open on floor 1. Then, when the requests for floor 4 come in, it should go up to floor 4 (only once). Then, it should come back, again not stopping, to floor 1, and open there:
How do we get such a thing to work as advertised?
Changing the state alone doesn’t do it.
I tried that in the vain hope that the simplest conceivable implementation would get the job done. I had request_button_pressed update a requested_floors collection in the Elevator class and had the class react to changes to that variable. What happened: I’d run the test, and then the computer and I would have a staring contest for 22 seconds while all of the commands (including the sleeps) in the test finished. Then, the Elevator would react to the accumulated state all at once. Dingdangit. On to the next idea.
Pub-sub alone also doesn’t do it.
There’s an idea in programming called the publish and subscribe (pub-sub) model. Make some objects publishers that send information to other objects (subscribers). Subscribers then act on the information. What if we had an Elevator class whose instances are subscribers, and made an ElevatorButton class whose instances are publishers, and then posted the information to the Elevator class whenever a button was pressed?
I tried this. It didn’t work. I struggled to get my elevator class to execute requests out of order. When I initialized it with some buttons already pressed, it would serve only those requests (ignoring new ones) and then only get to the new ones after it finished the existing requests. It could not execute and listen at the same time.
Reason: I was using one instance of raw Python to do this, and the tasks only started after other tasks finished due to the Global Interpreter Lock (GIL) implemented in the standard CPython interpreter. To get the program to do one thing while watching another, I needed something else.
So I started using threads.
First, I had a button panel that controlled the Elevator:
class ElevatorButtonPanel:
def __init__(self, elevator):
self.elevator = elevator
# Logic of the elevator
def request_button_pressed(self, floor):
self.elevator.go_to_floor(floor)Let’s talk about the Elevator class. I have provided the full, 80-line implementation here, but this is the important part for our discussion:
import time
import threading
class Elevator:
def __init__(self, control, timer=Timer(), eventlog=EventLog()):
self.control = control
self.timer = timer
self.eventlog = eventlog
#Python thinks it's a dict if you
#initialize an empty set
self.floors_to_visit = {1}
self.floors_to_visit.remove(1)
self.min_floor = 1
self.max_floor = 1
self.current_floor = 1
self.action_log = []
self.on= True
threading.Timer(self.timer.interval, self.keep_it_moving).start()
...
def keep_it_moving(self):
if self.floors_to_visit:
if len(self.floors_to_visit) == 1 and self.current_floor in self.floors_to_visit:
self.floors_to_visit.remove(self.current_floor)
self.open_doors()
time.sleep(self.timer.interval)
elif self.max_floor > self.current_floor:
self.up_1_floor()
else:
self.down_1_floor()
if self.on:
threading.Timer(self.timer.interval, self.keep_it_moving).start()You can see the keep_it_moving method, which determines, based on the current state of self.floors_to_visit, whether it should be going up or down (or opening its doors right where it is). I don’t run this directly from the initializer: instead, in the initializer, I spawn and start a thread that runs it. In the method itself, after checking the state and sending the elevator an instruction about what to do with the state, I spawn and start another thread that runs the method again.
It works. The tests, at first, were super slow, but I fixed that by injecting a timer with an interval and setting the step interval to a shorter amount of time if I wanted the step to run faster and a longer amount of time if I wanted to watch the logs occur to figure out what was happening:
class Timer():
def __init__(self, interval=1.0):
self.seconds_elapsed = 0
self.interval = interval
def wait(self):
self.seconds_elapsed += 1
===================
#And then in the test, using the timer like so:
timer = Timer(interval=0.05)
control = ElevatorControl()
elevator = Elevator(control, timer)While the pub-sub model attempts to produce the right behavior in the right order in continuous time, this implementation simplifies things by treating time as discrete. That is, it runs in steps: initialize a step, check the state, and run a command. Initialize another step, check the state, run a command. Particularly when we’re talking about something like a user interface, steps are usually good enough. The human eyeball can only process visual signals at a rate of about 60 frames per second, so most programming languages can step fast enough that the program’s reaction to user input will feel continuous to the person doing the inputting.
We spent all of Wednesday’s class on this elevator problem, and I felt satisfied for having come out with a working solution. Spawning a bunch of threads feels inelegant, though. This left me wondering whether there wasn’t something else we could do.
On Thursday, we returned to the question and explored an option that doesn’t require thread manipulation or concurrency at all. However, this implementation makes that implementation more clear because it primes us on the concept of steps, which we’re going to see again. We’ll take a look at that in Elevators: Part 2 :).
If you liked this piece, you might also like:
The Philosophy of Software Design series
How to Jump-Start a New Programming Language, or maybe, even, gain a more concrete mental model of the one you already use!
Lessons from Space: Edge-Free Programming, which also explores an Android app’s design and the engineering choices behind it (plus, cool pictures of rockets!)
Loved it. Thanks for sharing.