*

A metaphor connecting
programming and phrase structure syntax

—

If you ever took a linguistics class, you very likely drew some syntax trees, more or less like this one:

Now we will show how these very same trees can help explain computer programming.

Specifically, we will concern ourselves with what the latter field calls control flow. In many commonly-used programming languages, it is expressed using if, if-else, while, and related constructions.

Hacking at trees

—

Recall that syntax trees can be easily broken down to branches. Listed below are some of the branches of the preceding tree:

…

We can also notate them as follows:

S → NP + VP
NP → N
AdvP → Adv
PP → P + NP
⋮
N → treats

Now they have the semblance of rules. Later, we will speak interchangeably of branches and of rules. For our purposes, they are the same thing.

Branches generate sentences

Having broken down a tree to its branches, we can reassemble it once again! What is important here that we need not get the same tree we had in the beginning. This is especially true if we allow ourselves to pick several copies of identical branches.

Recall that we had this kind of branch/rule:

…but we did not have this one:

What we then have is a limited repertory of branches/rules. For this reason, the variety of trees that we can construct using them is limited in the same way, and so is the variety of sentences that we can construct them for.

Whenever we can construct a tree for a sentence, we will say that our set of branches/rules generates that sentence.

We can imagine different sorts of branch/rule repertories: at one point, we might possess one set of branches/rules, but on a different occasion we might also have another set at our disposal. In such cases, what will also vary is the set of sentences that can be generated.

Naturally, this can come in very handy in natural language syntax. One of its goals is, after all, separating “good” branches/rules from the “bad” ones. By “good” mean those that generate only those sentences that are possible in a particular language variety. Impossible sentences (such as *Wugs in indulged) would never come out.

A grammar of conversation

—

As we see now, adopting some branches/rules and discarding the rest creates an opposition of sentence versus word salad.

We might suspect that such a classifying device for word sequences might be useful in other places than syntax, too. Let us look at the following example, where conversations are generated:

conversation → greeting + exchange
greeting → “Good morning!”
greeting → “Hi!”
exchange → question + follow-up
question → “How are you?”
follow-up → “Fine, thanks.” + reciprocation
follow-up → “Fine, thanks.” + excuse
follow-up → “Not so good, to be honest.” + commiseration
commiseration → “Oh my, what happened? [...]”
reciprocation → “And you?” + follow-up
excuse → “Sorry, I am running late!”

The following is a possible tree. A valid conversation, if somewhat soulless:

On the other hand, the following verbal exchange is truly chaotic. Through our careful choice of branches/rules, we have prevented it from being generated:

Not so good, to be honest.   Hi!   And you?   Good morning!

Obviously, conversational dynamics is a complicated matter. It is not something where we could just carry over a model from syntax and expect to be done. Our rules can generate the following sequence, but as a conversation, it is not very coherent (assuming that only two people are conversing):

If we say that our intent was to predict what kind of conversation is realistic, and what other kind is not, we will have to concede that our predictive model has made a mistake. We have obtained a false positive: we generated something that we would have liked to avoid generating.

Of course, a model of polite conversation does not have much to do with programming, but all of this shows that phrase structure rules are capable of capturing something dynamic, something that evolves in time.

By the way, these rules that correspond to the branches of a syntax tree are termed phrase structure rules.

Commands, concrete and abstract

—

Instead of engaging in this analysis of these courteous rituals, let us try and model an execution trace of a simple program. It is popular to assume that a program is a sequence of instructions. Let us clarify:

• an execution trace is a sequence of instructions,
• a program is something that generates some execution traces, but not others.

What follows below could be a list of commands in the order that a program executes them in, if its goal is to spell WHIRLWIND. In other words, this is its execution trace.

The same effect would be achieved by a slightly longer trace, in which one makes a typo and fixes it right away:

It is not unlikely that you are thinking to yourself, “But where do all of these commands come from? Write, backspace, … Are they made up? Is it not knowing the actual repertory of them that makes a good programmer?”

We can reassure you that it is not! While we agree that it is part of the mastery of programming, it not a major part. And practice fills in most gaps in it.

Importantly, any command (e.g., backspace) that might have not even existed yesterday, can exist today! We have this kind of dynamic situation thanks to the internet.

To delve somewhat deeper into this, consider an example. Assume that yesterday we had been writing some code for a robot. Yesterday, its programming language had the commands forward and turn, and also a question command obstacle?, which is automatically followed by yes or no.

On one occasion, our robot behaved as follows, as given by this execution trace:

Such a trace would likely come from a program that makes it bump off of obstacles, while moving in the space that surrounds it, in straight lines.

So that is the program that we created yesterday; let us also assume that we uploaded it to the web. But this was yesterday – today’s programmers can use our program as if it were a fully atomic command, just like forward! Perhaps it is named bump off of obstacles. Even programming languages often help us to this end: we need not copy and paste our yesterday’s program; we can import it instead.

Computer scientists have adopted the term abstraction for this phenomenon. Indeed, our fellow programmers, for whom our program will be a mere command, will be able to program as succinctly as we did, yet obtain something larger in scale. Our contribution will be abstracted away from.

A grammar of behavior

—

To program, therefore, is to combine smaller behaviors into larger ones, “smaller” being the key word here, as opposed to just “small”.

Let us not stray too far from phrase structure, though.

A program is a set of rules that singles out some execution traces as possible products of its execution, leaving aside the ones that are impossible.

Now this does not seem all too different from contrasting grammatical sentences with ungrammatical strings, and also from separating coherent courteous rituals from nonsensical ones!

Only rarely can a single string of instructions make a meaningful program, because a program must react to an unpredictable environment. One does not need robots for that: in a simple desktop application, too, the user can click on one button, but they can also click on another.

Because of this, a program often has more than one corresponding string of instructions (execution traces). The program’s code embodies all of them. In a sense, it generates these strings of instructions.

—

Demonstration

—

We now find ourselves in a simple text editor (imagine Microsoft Word ®, just a lot more simplistic), that can be controlled programmatically:

Try this program out: in the Text window, type any response, and after that, press Enter. Afterwards, we suggest looking for specific parts in its code that are responsible for the phrases that it outputs. This program will be discussed later as well.

—

Commands for a good start

—

In our demonstration, we can use the following commands to construct a program like the one above. Note that in our program, we had also defined two commands ourselves! These were ask how the user feels and continue conversation.

• write something,
• space,
• read
  (pauses the program and lets the user enter some text; execution is resumed as soon as Enter is pressed;
  once the input has been received, it becomes selected: see below),
• forward, back
  (moves the cursor by one character),
• select, unselect
  (turns selection mode on and off respectively;
  in this mode cursor movement doubles as including characters in a selection),

There are some question commands too; for now, we have made use of the following one:

• selection equals something?

An important point on how we treat execution traces in this article:

Once a question command is run, the word yes or no follows it immediately in the trace.

Yes and no are part of the trace, but in general, the program does not cause either of them to occur in any predictable manner. To put it metaphorically, a question command is a question posed by the program to the environment, and yes or no is the response.

How does this program run?

—

Here is the same program, again:

Its code, which appears on the left, is just a set of phrase structure rules that generate all of the program’s traces.

Even if traditional programming languages do not look that way, the difference is arguably superficial. It is possible to program in phrase structure rules; it is a different question whether it is equally easy in all situations. We will come back to that.

The shortest trace that our program could generate is this one:

A longer trace could be generated as well, if the word “interested” were entered only at the second attempt:

To save space, we abbreviated the three write commands as (H), (D) and (O) by the first letter of the text they output:

• (H) = write How are you feeling?
• (D) = write Did you perhaps mean “interested”?
• (O) = write Oh, perfect! We hope it only gets better!

Meet recursion. We define ask how the user feels to include continue conversation, but also provide an option for continue conversation to include ask how the user feels. As a result, the commands that ask how the user feels expands to will potentially include ask how the user feels itself! This way, we obtain a cyclical process.

We can make the trace as lengthy as we wish:

Programming languages

—

What we applied here was an illustrative programming language, but a rather peculiar one, too. Let us now see how programs look in languages that are more common!

We will use Python for comparison (on the right). The comparison is schematic; the letters A–F represent arbitrary commands:

A()
B()
C()

A()
D()

def A():
  B()
  C()

A()
D()

def A():
  B()
  C()

def D():
  E()
  F()

A()
D()

Let us direct our attention to some details in these short Python snippets.

• The def keyword. It signals that whatever follows is a definition of a command (or function in Python parlance). You can verify for yourself that almost* every def keyword on the right has a corresponding rule on the left.
• Spaces. The content of a definition resides in a block. We separate it from the outside by pushing it rightwards using spaces or tabs. A different number of spaces can place a line inside different blocks!
• Colons. They are obligatory before starting a block. It is interesting that there is nothing obligatory for ending blocks! The blank lines that we have inserted in the examples are, in fact, optional.

* The definition of the program itself has no def keyword. Neither is it placed inside a block. It is, however, important to place it at the very end: up to that place, all other functions must be already defined, or they will be inaccessible.

Also, for the ones who are interested:

• Parentheses. In Python, commands (i.e., functions) can have arguments. This is similar to the concept of argument that we use in linguistics, when discussing verbs. In fact, commands/functions are often named using verbs!
  Recall the command write something. The encircled part (something) is the argument – both in a linguistic and in a programming sense. In the language that we employed in this article, we would have said write Hello world, and in Python, we will say print("Hello world").
  Therefore, the parentheses are here to contain the arguments of a function. To slightly simplify the actual state of affairs, even in the absence of arguments, the parentheses are still required for consistency.

The “if” construction

—

Wherever we had two possible paths of execution with yes and no, we will now use the if keyword in Python, possibly accompanied by else. Both of these keywords also take blocks:

def A():
  if Q():
    B()

A()

def A():
  if Q():
    B()
  else:
    C()

A()

def A():
  if Q():
    B()
    A()
  else:
    C()

A()

There is also logical negation: the not keyword. To understand how it works, compare the top row with the bottom one:

if Q():
  A()
else:
  B()

if not Q():
  A()
else:
  B()

Tail recursion and the “while” construction

—

Let us have a closer look at one program that we saw before. Below, the definition of A contains the command A itself; therefore, here too we are dealing with recursion. There exists a special while block for this type of recursion. In fact, the two variants of the program listed below are identically behaved:

def A():
  if Q():
    B()
    A()
  else:
    C()

A()

def A():
  while Q():
    B()
  C()

A()

The type of recursion that can be notated using while, is called tail recursion. It is the kind of recursion where a command enters its own definition as the very last constituent, as in A → Q? + yes + B + A. (Notice in which places A recurs!)

Summary

—

Let us recap now:

• we introduced execution traces,
• on them, we applied a familiar instrument of syntactic analysis,
• we composed phrase structure rules that generate various execution traces,
• then, we identified these sets of rules with programs,
• and lastly, we saw that Python programs have a piecewise correspondence with these sets of rules.

Thank you for your interest!

Addendum

—

If you are interested in how phrase structure rules turn into Python programs, please type some rules and click the Translate to Python button:

Here is an exhaustive list of the commands that our text editor recognizes:

• write something,
• space,
• read,
• forward,
  back,
• to next line,
  to previous line,
• to beginning of line,
  to end of line,
• to beginning,
  to end,
• select,
  select all,
  unselect,
• cut,
  copy,
  paste,
• delete.

Question commands:

• at beginning of line?,
  at end of line?,
• at beginning?,
  at end?,
• selection equals something?,
• selection consists of N characters?,
• selection contains something?,
• selection begins with something?,
• selection ends with something?,
• selection equals clipboard?

*

© Ignas Rudaitis 2019, 2021