Previous: A long time ago, in a village far, far away

Moses flew along, showing the way to The Magnificent Smullyan Bird’s nest. As they walked along, Maude saw the most curious sight: A small winged elephant perched on a nest.1

“What is that!?”

Moses clicked his beak. “That is Horton Jr., or just plain Horton. I don’t know why everyone is so fascinated with his appearance. He can barely fly, his beak is all rubbery, and he lacks any plumage of note. Mind you, he is something of an expert on certain subjects and I do consult him from time to time.”

Maude asked about his expertise.

“Well, he does a lot of work playing with pebbles on vast grids that he lays out.”2

“Speaking of egocentricity, Horton actually claims that by following certain rules, his pebbles can answer any question that songbirds like the Starling and Kestrel can answer. I think it’s interesting, but outside of fanciful flying creations like gliders and heavyweight spaceships, I don’t see the point.”

Maude was interested. Pebbles? “Well,” Moses said, “I alluded to this earlier. A certain lesser class of bird likes to build a bower out of various found objects.”

For example, I could show you the Stuart’s Tombird. It builds an elaborate bower out of just one material, chips of red crystal. It is intelligent, and claims its chips of Ruby can do various tasks like count to one hundred or even write nonsensical words like “fizz” or “buzz.”3

“In any event,” continued Moses, “We may as well say hello to Horton since we’re here.”

horton

Moses introduced Maude to Horton. After exchanging pleasantries, Maude asked Horton what kind of song he sang.

“I am not particularly interested in songs,” said Horton, “I am working at the moment on bird sociology, particularly flocking birds. As you may know, some birds, like Schönfinkel’s Bright Bird and myself, are fairly solitary. Others like to live in large flocks.”

“In most such flocks, there is a strict pecking order. What interests me is how such flocks behave when each bird is autonomous and there is no centralized control over the order of rank for the birds.”

“I will show you,” started Horton, scribbling some marks in the dirt with a stick he held in his trunk. Moses hastily intervened.

“Alas, Horton, we are on our way to see The Magnificent Smullyan Bird so that Maude can learn about hopeless egocentricity and do not have time—” Horton would hear nothing of it. “Nonsense! Egocentricity can wait, that is fascinating for gaudy plumage fanciers but serious birds pay attention to sociology.”

“Sit. Pay attention. Listen.”

Moses squawked but in the end, he and Maude settled down as Horton began to speak.

surreal birds

“I have discovered that each bird in a flock knows some set of birds in its flock. Flocks are large, and in some cases no one bird personally knows every other bird in the flock. Each bird divides the birds it knows into two sets: Those that outrank it in the flock, and those it outranks in the flock. I call them greater known birds and lesser known birds respectively.”

“Of course, a bird may not know any birds it outranks in the flock. That doesn’t mean it doesn’t outrank any birds, it just doesn’t personally know any birds it outranks. The same goes for birds that outrank it: A bird may not personally know any birds it outranks, but that does not mean there aren’t any in the flock.”

Maude was making notes:

{any} = require('underscore')

class FlockingBird
  constructor: ({@knownOutrankedBy, @knownToOutrank} = {}) ->
    @knownOutrankedBy or= []
    @knownToOutrank   or= []

“Now these birds often compete with each other: For good nesting sites, for mates, for a piece of food, for a good perch on a branch. Each will instinctively show its threat display and try to get the other to back down. As they do so, they screech at each other. When one stands fast and the other not stand its ground, the one that stands fast always outranks the other.

“I wondered how they sorted it out, so I observed and made extensive notes. I have discovered that they obey both of two simple rules. To simplify the explanation, imagine a bird is displaying on its courtship stage when a rival appears. We have the courting bird and the rival who square off in a challenge.

The first rule is that in order to stand its ground, the courting bird cannot know any bird ranked greater than the courting bird such that the rival would stand its ground against the greater ranked bird.

The second rules is that in order to stand its ground, the rival cannot know any bird lesser than the rival that stands fast against the courting bird.

Maude gave this some thought, and then wrote:

  standsAgainst: (rival) ->
    courtingBird = this
    case1 = any @knownOutrankedBy, (gb) -> rival.standsAgainst(gb)
    case2 = any rival.knownToOutrank, (lb) -> lb.standsAgainst(courtingBird)
    (not case1) and (not case2)

“The first important rule about flocking birds is that they like to have a well-defined place in the flock’s pecking order. Specifically, they become confused if either of the following cases are true:

“First, a bird is confused if it knows a confused bird. Second, a bird is confused if any of the birds it knows it outranks would stand fast against a bird it knows outrank it.”

Maude quickly wrote:

  confused: ->
    case1a = any @knownToOutrank, (lb) -> lb.confused()
    case1b = any @knownOutrankedBy, (gb) -> gb.confused()
    case2  = any @knownToOutrank, (lb) =>
      any @knownOutrankedBy, (gb) ->
        lb.standsAgainst(gb)
    !!(case1a or case1b or case2)

Moses was preening itself, acting as disinterested as possible, but he fixed his eye on Horton and appeared to be thinking hard when Horton posed a question:

“Now that you know the basic rules of sociology, I present to you Mayzie, a flocking bird that is so self-centered it doesn’t know any other birds. Is Mayzie confused?”

Maude thought for a moment and then wrote:

describe "Lazy Mayzie", ->

  Mayzie = new FlockingBird()
  
  it "should not be confused", ->
    expect( Mayzie.confused() ).toEqual false

notation

Here Horton stopped and stared at Maude’s writing. “And what do you call this system of notation you have?”

“CoffeeScript,” said Maude, “because when it gets complicated, I need to drink a lot of coffee to work it out by hand.”4

“Actually,” she said, “My uncle Brendan5 devised a notation for solving certain problems to deal with the appearance and behaviour of web spiders. He called it JavaScript, no doubt because of our family’s coffee plantation business. My cousin Jeremy6 liked Brendan’s ideas, but found them awkward for certain classes of problems and streamlined it somewhat. Jeremy called his variation CoffeeScript, and he taught it to me.”

After explaining the details of her notation to Horton, he agreed with her assessment. “Yes, Mayzie isn’t very sociable, but she isn’t confused.”

Horton continued with his explanation. “Some flocks have confused birds, some do not. I call a flock that has no confused birds a proper flock. Every proper flock has a simple pecking order. That is, you can arrange all of the birds in a line (as if perched on a branch), and there is always an arrangement such that every bird stands fast against any bird to its left.”7

birds on a branch

Horton was gathering enthusiasm, and he fairly trumpeted the next explanation. “This idea of a branch where birds can perch in order is interesting. Let’s start with an empty branch. Now, let’s place Mayzie on the branch by herself in the middle:”

“Mayzie obviously forms a proper flock as she is not confused. As we have established, Mayzie doesn’t know any birds. But what if a bird alights to her right, a bird that knows her, perhaps from reading a book.8 This bird knows and outranks Mayzie.”

Maude considered, then wrote:

Mayzie = new FlockingBird()
OneRight = new FlockingBird
  knownToOutrank: [Mayzie]

Maude asked, “Do these two birds form a proper flock?”

Horton curled his trunk and smiled. “You tell me! Do these two birds form a proper flock? And if so, do they obey the rules for ordering on a branch?”

Maude worked things out in her mind for a few moments, writing:

describe "a flock with two birds", ->

  it "should not contain confused birds", ->
    expect( Mayzie.confused() ).toEqual false
    expect( OneRight.confused() ).toEqual false
      
  it "should have a linear pecking order", ->
    expect( OneRight.standsAgainst(Mayzie) ).toEqual true
    expect( Mayzie.standsAgainst(OneRight) ).toEqual false

“Yes,” agreed Horton, “They form a proper flock. And now let us consider a bird that alights to the right of our bird to the right of Mayzie. It knows the bird to the right of Mayzie and knows that it outranks that bird. Do we have a proper flock?”

TwoRight = new FlockingBird
  knownToOutrank: [OneRight]

describe "a flock with three birds", ->

  it "should not contain confused birds", ->
    expect( Mayzie.confused() ).toEqual false
    expect( OneRight.confused() ).toEqual false
    expect( TwoRight.confused() ).toEqual false

  it "should have a linear pecking order", ->
    expect( Mayzie.standsAgainst(OneRight) ).toEqual false
    expect( Mayzie.standsAgainst(TwoRight) ).toEqual false
    expect( OneRight.standsAgainst(Mayzie) ).toEqual true
    expect( OneRight.standsAgainst(TwoRight) ).toEqual false
    expect( TwoRight.standsAgainst(Mayzie) ).toEqual true
    expect( TwoRight.standsAgainst(TwoRight) ).toEqual true

“Interesting things happen when we consider this flock that is created by birds successively alighting to the right of the previous bird where each bird knows the bird immediately to its left (except for Mayzie).”

liberté, égalité, et fraternité

“First,” said Horton, “What happens if we are given two birds where the first stands fast against the second and the second bird stands fast against the first? Do they form a proper flock?”

Maude looked confused.

“No,” said Horton, “Do not become confused yourself. We said earlier that a proper flock can be arranged along a branch such that every bird stands fast against the bird to its left. This implies that the bird to its right stands fast against it. But we said nothing about whether a bird stands fast against a bird to its right.”

“If two birds stand fast against each other, they have equal rank and form a proper flock.”

FlockingBird::isOfEqualRankTo = (otherBird) ->
  case1 = @standsAgainst(otherBird)
  case2 = otherBird.standsAgainst(this)
  case3 = not @confused() and not otherBird.confused()
  case1 and case2 and case3

describe "equality", ->

  it "should be true for Mayzie vs Mayzie", ->
    expect( Mayzie.isOfEqualRankTo(Mayzie) ).toEqual true
    
  it "should be true for OneRight vs OneRight", ->
    expect( OneRight.isOfEqualRankTo(OneRight) ).toEqual true
    
  it "should be false for Mayzie vs OneRight", ->
    expect( Mayzie.isOfEqualRankTo(OneRight) ).toEqual false
    expect( OneRight.isOfEqualRankTo(Mayzie) ).toEqual false

“Now,” continued Horton, “We can define the relationship you were thinking of when we consider a strict ordering of birds in a flock. A bird outranks another bird if it stands fast against that bird and it is not of equal rank to that bird.”

Maude hastily updated her notes:

FlockingBird::outranks = (otherBird) ->
  case1 = @standsAgainst(otherBird)
  case2 = not @isOfEqualRankTo(otherBird)
  case1 and case2
  
describe "outranking", ->

  it "should work for Mayzie vs. Mayzie", ->
    expect( Mayzie.outranks(Mayzie) ).toEqual false
    
  it "should work for Mayzie vs. OneRight", ->
    expect( Mayzie.outranks(OneRight) ).toEqual false
    expect( OneRight.outranks(Mayzie) ).toEqual true
    
  it "should work for Mayzie vs. TwoRight", ->
    expect( Mayzie.outranks(TwoRight) ).toEqual false
    expect( TwoRight.outranks(Mayzie) ).toEqual true  

“One interesting property of birds belonging to proper flocks is that they will sometimes pair up and work together to defend a nest or bit of food. Sometimes two unattached birds will pair up to chase away a higher-ranked bird from attracting a mate and so on.

“We have defined the ranking for birds against each other. It turns out that the birds have an equally rigorous way of ranking pairs of birds. Given any two birds x and y, their pairing has rank equal to some third bird we shall call P(x, y). How do we find this rank? Let’s take two birds B1 and B2. From my observations, four rules apply. The first two identify birds that the pair must outrank:”

1. If B1 outranks some bird L1, then P(B1, B2) must outrank P(L1, B2).
2. If B2 outranks some bird L2, then P(B1, B2) must outrank P(L2, B1).

“The next two rules identify birds that must outrank the pair:”

1. If some bird G1 outranks B1, then P(G1, B2) must outrank P(B1, B2).
2. If some bird G2 outranks B2, then P(G2, B1) must outrank P(B1, B2).

Maude pursed her lips. “That’s all very well, but how do we find such a bird? How do we know what birds a bird B1 or B2 might outrank?” Horton’s replied with deep simplicity: “Ask them!”

Maude considered, then decided to try things out and see if they worked:

{map} = require('underscore')

P = (B1, B2) ->
  PL1B2s = map B1.knownToOutrank,  (L1) -> P(L1, B2)
  PL2B1s = map B2.knownToOutrank,  (L2) -> P(L2, B1)
  PG1B2s = map B1.knownOutrankedBy, (G1) -> P(G1, B2)
  PG2B1s = map B2.knownOutrankedBy, (G2) -> P(G2, B1)
  new FlockingBird
    knownToOutrank:   PL1B2s.concat(PL2B1s)
    knownOutrankedBy: PG1B2s.concat(PG2B1s)

Horton was busy eating some ground nuts, so she showed her progress to Moses. “How,” she wondered, “Do I check my work?” Moses provided some hints:

describe "pairing Mayzie with a bird", ->

  it "should be the same rank as that bird", ->
    expect( P(Mayzie, Mayzie).isOfEqualRankTo(Mayzie) ).toEqual true
    expect( P(Mayzie, OneRight).isOfEqualRankTo(OneRight) ).toEqual true
    expect( P(OneRight, Mayzie).isOfEqualRankTo(OneRight) ).toEqual true
    expect( P(Mayzie, TwoRight).isOfEqualRankTo(TwoRight) ).toEqual true
    expect( P(TwoRight, Mayzie).isOfEqualRankTo(TwoRight) ).toEqual true

describe "pairing OneRight with itself", ->
    
  it "should be the same rank as TwoRight", ->
    expect( P(OneRight, OneRight).isOfEqualRankTo(TwoRight) ).toEqual true

She showed her work to Horton. “Wait,” she said suddenly, “I should use a more descriptive name. I’ll just change P to Pair.” Horton demurred. “Actually,” he said, “The correct word isn’t ‘pair,’ it’s plus.”

It took a few moments for the revelation to sink in, then Maude laughed in delight. They explored the relationship between proper flocks and numbers further, then Maude spoke up.

what does it mean?

“Well,” Maude said, “This is all very interesting. But what does it mean? Is this a kind of ornithological circus trick? Or does it have some deep significance?”

Horton looked at her blankly. His trunk quivered, and tears began to well up in his eyes. Moses hurriedly consoled him. “There, there, she didn’t mean it, she knows nothing of your family history. She’s just interested in your work, that’s all.”

Horton calmed down, but not before his trunk tooted plaintively a few times. Then he sighed and turned away. “I must get back to my work,” he said quietly.

onwards

“Yes, of course, and most important work it is.” Said Moses. “And we really MUST be on our way. Thank you so much, good-bye, good-bye!” Maude said her good-byes as well and they walked away.

“I’m so sorry!” sad Maude, “I have no idea what I did to offend him…”

Moses fluttered awkwardly. “Well, it’s a very short story, but we are in a hurry to catch The Magnificent Smullyan Bird, so perhaps I will tell you about it another time. In the mean time, if you’ll just follow me…”

And together, Moses the Schönfinkel’s Bright Bird and Maude the Curious Person travelled further into the Enchanted Forest.

After walking on a bit, Moses stopped and asked Maude, “What is troubling you?”

Maude said that nothing was troubling her, but Moses cawed and squawked at her until she admitted that she was still troubled by what she had learned from Horton.

“I hate it when I learn something like this and leave it at that. It feels like there is more to the story, something very important to understand about the relationship between proper flocks and numbers.”

“It can’t just be a silly game, can it?”

Moses said nothing for a moment, then he seemed to shrink in defeat.

“I really want you to meet Smullyan, but I can’t allow you to carry this problem unresolved in your head. Come, we are going to talk to Zee Hackenbush Bird. Like Stuart’s Tombird, he is a bowerbird, he lacks the refinement of proper plumage.”

“But I have heard him talk of Horton’s work and I know he can explain its significance to you.”

Coming Soon: Zee Hackenbush Bird

notes: