Object oriented programming, the beginning

When you learn to program today, you encounter something called "object oriented programming." Everyone argues over what is or is not object oriented. Alan Kay invented the term, and people even argue with him.

There's a relevant line from Tom deMarco's The Deadline: A novel about project management: "When I come across anything unclear in a specification I go nosing around for conflict. I always find it." If there is this much argument for this long, that means that there are really different practices all trying to share the name object oriented programming. None of them are wrong. They're all shaped by their particular needs and conditions, but to an outsider or someone who has only lived in one of the traditions the whole morass is bewildering.

Let's take a tour through these various traditions. I'll start with what all of them acknowledge as the beginning: the language Simula-67.¹

Simula took ALGOL 60, the lingua franca of imperative languages at the time, and adapted it for simulating discrete systems. As a very simple example, consider three checkout stations at the grocery store. People arrive at some rate to check out and go to the checkout station with the shortest line. The checkout stations take some random amount of time to handle each customer, at which point the customer disappears from the simulation. Our entities are the three checkout stations and the customers.

In ALGOL 60, we would write a program like (I'm using Python since it has all the features we'll need and is much more familiar and available than ALGOL 60 these days):

import random
import queue


def argmin(xs):
    """Return the index of the minimum value in the list xs.

    If the minimum value appears multiple times, return the index
    of its first appearance. If the list is empty, return None.
    """
    if len(xs) == 0:
        return None
    elif len(xs) == 1:
        return 0
    else:
        idx = 0
        val = xs[0]
        for i, v in enumerate(xs):
            if v < val:
                idx = i
                val = v
        return idx


def peek_priority(q):
    """Return the priority of the first element in the priority queue q.

    This does not change the contents of q, so q.get() will get the
    same element whether we run this function first or not.
    """
    return q.queue[0][0]


customer_arrival_rate = 1.0  # customer/minute
shortest_checkout_time = 1.0  # minutes
longest_checkout_time = 5.0  # minutes

# We will enqueue events with the time they
# are supposed to happen as their priority.
# We will enqueue (time, checkout line) for
# events of a customer finishing at the specified
# checkout line, and (time, -1) for a new customer
# arriving to join a line.
event_queue = queue.PriorityQueue()

CUSTOMER_ARRIVES = -1

n_checkout_lines = 3
checkout_line_lengths = [0] * n_checkout_lines
next_customer_arrives_at = random.expovariate(customer_arrival_rate)

# We run the simulation for 100 events. We have to
# stop it somewhere or it runs forever.
total_customers = 30
customers = 0
while True:
    if not event_queue.empty():
        # Customers might arrived in the time before
        # the next event in the queue. We peek that time and then
        # add customer arrival events to the queue until
        # we pass it.
        timestamp = peek_priority(event_queue)
        while timestamp > next_customer_arrives_at and customers < total_customers:
            event_queue.put((next_customer_arrives_at, CUSTOMER_ARRIVES))
            customers += 1
            next_customer_arrives_at += random.expovariate(customer_arrival_rate)

        timestamp, event = event_queue.get()
        if event == CUSTOMER_ARRIVES:
            shortest_line = argmin(checkout_line_lengths)
            checkout_line_lengths[shortest_line] += 1
            checkout_time = random.uniform(
                shortest_checkout_time, longest_checkout_time
            )
            event_queue.put((timestamp + checkout_time, shortest_line))
            print(
                f'{timestamp:6.2f} - ({" ".join(str(v) for v in checkout_line_lengths)}) '
                f"- Customer joined line {shortest_line} "
            )
        else:
            checkout_line_lengths[event] -= 1
            print(
                f'{timestamp:6.2f} - ({" ".join(str(v) for v in checkout_line_lengths)}) '
                f"- Line {event} finished with customer "
            )

    elif customers < total_customers:  # queue is empty, enqueue a customer
        event_queue.put((next_customer_arrives_at, CUSTOMER_ARRIVES))
        customers += 1
        next_customer_arrives_at += random.expovariate(customer_arrival_rate)
    else:
        break

Simula was designed so that we could write each entity's behavior separately instead of interleaving everything as we have here.

Its idea of simulation was to have distinct entities emitting and awaiting discrete events. You wanted to be able to send the same events to different entities in the simulation and have them handle them differently, so it introduced the idea of classes of entities and subclasses. Subclasses could have their own behavior for responding to given events.

The event handling itself was done by letting you define coroutines on the classes. We'll emulate this with Python's asyncio, which is awkward since it wasn't meant to be a simulation system, but lets us see each checkout station and the source of customers written as their own scripts and allowed to interact as we would have in Simula-67.

import random
import asyncio
import time
import collections
import math

# This simulation runs in real time as opposed to
# as fast as the event loop can spin. For the sake
# of not waiting forever, we speed up the rates by
# scaling all rates uniformly.
scale = 100.0

customer_arrival_rate = 1.0 * scale  # customer/minute
shortest_checkout_time = 1.0 / scale  # minutes
longest_checkout_time = 5.0 / scale  # minutes


def argmin(xs):
    """Return the index of the minimum value in the list xs.

    If the minimum value appears multiple times, return the index
    of its first appearance. If the list is empty, return None.
    """
    if len(xs) == 0:
        return None
    elif len(xs) == 1:
        return 0
    else:
        idx = 0
        val = xs[0]
        for i, v in enumerate(xs):
            if v < val:
                idx = i
                val = v
        return idx


# Our first entity is the checkout station. It maintains a list
# of how long each customer queued will take to check out.
class CheckoutStation:
    def __init__(self, i):
        self.line_length = 0
        self.i = i  # For reporting, we want to know which checkout station this is
        self.closed = False  # Bookkeeping so we can shut down gracefully

    def queue_length(self):
        return self.line_length

    def join_queue(self):
        self.line_length += 1
        return self.line_length

    def close_station(self):
        self.closed = True

    async def run(self):
        while True:
            if self.line_length > 0:
                checkout_time = random.uniform(
                    shortest_checkout_time, longest_checkout_time
                )
                await asyncio.sleep(checkout_time)
                self.line_length -= 1
                report(
                    f"Queue {self.i} finished with customer in {checkout_time*scale:.2f} seconds."
                )
            elif self.line_length == 0 and self.closed:
                report(f"Closed queue {self.i}.")
                return
            else:
                await asyncio.sleep(0)


# And here is the entity that generates customers and has them
# queue.
async def customer_source(stations):
    for i in range(30):
        time_until_customer = random.expovariate(customer_arrival_rate)
        await asyncio.sleep(time_until_customer)

        queue_lengths = [st.queue_length() for st in stations]
        shortest_queue = argmin(queue_lengths)
        n = stations[shortest_queue].join_queue()
        report(f"Customer joined queue {shortest_queue}, position {n} in line")
    report("All customers arrived.")
    for st in stations:
        st.close_station()


n_stations = 3
stations = [CheckoutStation(i) for i in range(n_stations)]

start_time = time.time()


def report(msg):
    queue_lengths = [st.queue_length() for st in stations]
    print(
        f'{(time.time() - start_time)*scale:6.2f} - {" ".join(str(v) for v in queue_lengths)} '
        f"- {msg}"
    )


loop = asyncio.get_event_loop()
futures = [st.run() for st in stations] + [customer_source(stations)]
loop.run_until_complete(asyncio.gather(*futures))

The key passages are (amended slightly to take out the edge cases from making the simulation terminate and the reporting code):

while True:
    time_until_customer = random.expovariate(customer_arrival_rate)
    await asyncio.sleep(time_until_customer)

    queue_lengths = [st.queue_length() for st in stations]
    shortest_queue = argmin(queue_lengths)
    n = stations[shortest_queue].join_queue()

and

while True:
    if self.line_length > 0:
        checkout_time = random.uniform(
            shortest_checkout_time, longest_checkout_time
        )
        await asyncio.sleep(checkout_time)
        self.line_length -= 1
    else:
        await asyncio.sleep(0)

The behavior of each entity is separate and clear. Compare that to the ALGOL 60-esque version. For this simple simulation, we were able to write it either way, but think about simulations involving thousands of entities interacting in many ways. With the Simula approach, it's a lot of work, but it's straightforward. With the ALGOL 60 approach, it would be a monumental struggle.

This idea of objects modelling entities and defining hierarchies of classes and subclasses of entities persists in some traditions of object oriented programming. In others it has been rejected in favor of very different approaches.

The notions of class and method familiar from modern languages like Java, Python, or Ruby are all in place in Simula-67. Many people stop here.

That 67 stands for the version of Simula released in 1967. Naming your language version with the year has been pretty typical for most of the history of computing, e.g., ALGOL 60, FORTRAN 77, C 99, and C++ 14. ↩

Blog

Object oriented programming, the beginning

Fred Ross

Join Our Newsletter. No Spam, Only the good stuff.

Related