Back in the post HTML is not a programming language! I brought up the three properties required by a programming language. A discussion recently got me thinking about it again. This post is just some notes on those thoughts…

There is a very casual definition that a “programming language” is any language used to make a computer do something. Under the umbrella of such a broad definition, many things (HTML, for example, or a list of email addresses used as a filter) would be “programming” languages rather than just computer languages.

A much less casual definition is that a programming language accomplishes calculation, which includes the ability to do math as well as logic.

The more formal definition takes that further and equates “programming language” with “Turing-Complete language” or a Turing Machine (which is the basis of our definition of what it means to calculate).

Generally this implies three requirements:

1. Storage
2. Selection
3. Recursion

The last one, recursion, takes some explaining, but the first two are fairly easy to understand.

Storage, the ability to save program state, is most often expressed in variables. There is also an internal need to save state. Almost all non-trivial calculations have intermediate results that must be stored until the program needs them. As a simple example:

x := (a + b) * (c + d)

The multiplication requires doing the two additions first. Both those operations produce intermediate values that must be stored for the multiplication.

And, obviously, that example includes five variables, the external expression of saving state.

Selection, the ability to select among different code paths, is most usually expressed as the common if-then-else statement. (In some languages, it’s just an if-then statement — programmers create “else” clauses in other ways.)

Selection, or conditional branching, also includes switch or case statements as well as other less common ways of controlling code flow. For example, some languages can branch on an index variable.

The key features of selection involve testing a value and selecting a code path based on the results of the test.

Recursion is the complicated one because it can be replaced by iteration and isn’t even strictly necessary depending on the nature of selection in the language in question. (It’s the complications and features of recursion that prompted these notes.)

Recursion is really the ability to call sub-routines or functions. We use the term recursion to indicate an important required property: The functions must be reentrant. Reentrancy is necessary for a function to be recursive, and recursion is absolutely necessary when we use functions.

§

Let’s start with an extremely simple language, one that meets the minimum T-C requirements listed above. We’ll give it an if-then construct, variables, and functions (oh, my). For simplicity, we’ll use Python’s syntax.

The main point here is the lack of any loop construct (do-while or for-next) — as well as the lack of the dreaded GOTO. Recursion allows us to implement them with the tools we’ve already got:

def loop (n, m, data, cb):
    if m < n:
        return n
    if not cb(n, data):
        return n
    return loop(n+1, m, data, cb)

The function above implements a for-next style loop as recursion.

The first two parameters, n and m, specific the begin and end index; n must be less than m. The data parameter is any data used by the callback function, cb, passed as the last parameter.

To create a loop, the user first defines a looping function — the statements that would be inside the loop:

def cb_foobar (n, data):
    loop statements
    loop statements
    return True

Then to use the loop:

data = <data>
rv = loop(0, 10, data, cb_foobar)

Multiple calls to loop with cb_foobar and different data allow executing the same kind of loop over different data.

It’s also easy to define a do-while loop function:

def while_loop (condition, data, cb):
    if not condition():
        return True
    if not cb(data):
        return False
    return while_loop(condition, data, cb)

The difference is this function requires a condition (function!) parameter. The data and cb parameters are as before. We can also define the loop with the test at the end:

def loop_while (condition, data, cb):
    if not cb(data):
        return False
    if not condition():
        return True
    return loop_while(condition, data, cb)

And, of course, do-until loops are also possible. So are more creative ones!

The point is that iteration (looping) doesn’t have to be part of the language, so long as you have the main T-C tools, most importantly recursion.

It works the other way. A language with iteration can implement a recursive process. For now I’ll leave that as an exercise for the reader!