Identity, Ontology, and Pass-by-Value

Surprisingly, parameter passing is a contentious issue. One wouldn’t expect that such an apparently simple thing could invoke disagreements but it does. Perhaps the most prominent disagreement involves pass-by-value in C, C++ and Java. According to the language designers, these languages always pass by value; but according to many programmers, arrays are passed by var and in Java all objects are passed by var.

The roots of this controversy can be traced back to the ancient Greeks who argued over how many kinds of enduring Substance there were. No really. The argument over parameter passing really comes down to ontology --what categories of things there are.

The two sides of the debate might be called the cyber-materialists and the cyber-dualists. According to the cyber-materialists, there is just one ultimate category of Substance and all programming language objects are essentially --or should be viewed as-- concrete material things. The cyber-dualists agree that concrete material things exist but maintain that there are also abstract things which are radically different.

To a cyber-materialist the pass-by-value issue is simple: when a parameter is passed by value, the called function cannot modify it. When a parameter is passed by var, the called function can modify it. In C, C++ and Java arrays are passed in such a way that the called function can modify the value, therefore arrays are passed by var. QED.

To a cyber-dualist, the situation is quite a bit more complex. But before we get into the weeds of cyber-dualism, let’s talk about Bob. Bob is a typical grad student of the 1980s (we have to pick a time before all documents are stored on-line and passed by email or it confuses the issues). Bob drives a sweet 1972 Firebird Trans Am and he has just finished a paper on the semantics of pattern matching in SNOBOL4. Today, he has two errands to run: he must send his paper to the publisher and he must take his car in to be detailed because he has a first date tonight with a hot grad student from the business college.

As Bob is sitting in his Firebird holding his paper in his hand, he has two choices about how to send the paper. First, he can shove it into a manilla envelope and send it to the publisher, second, he can make a copy of it and send the copy to the publisher. Either choice works.

For the car, Bob has no such option; he has to take in the very car that he is sitting in. Even if he could make an exact copy of the car, dirt and all, the car that gets detailed must be the car that he takes tonight. His date is not going to be impressed if he shows up in a filthy car but assures her that there is an identical clean copy at the detailer's.

The difference here is that the car is a concrete physical object. It is not the same object as any car that is not exactly in the same place at the same time. Even if you could make a car that was identical in all respects except for it’s physical location, there would be two different cars that will go on to become more different over time. By contrast, the SNOBOL4 paper is an abstract object that is represented physically with ink on paper but is not itself physical. Once the paper is published there will be many physical copies, but there will always be just one paper on the semantics of SNOBOL4 pattern matching written by Bob (Bob is getting out of semantics because compilers are more fun).

So in the real world there are these two dramatically different categories of things and cyber-dualists see the same two categories in computer programs. In Java, an int is an abstract value represented by bits on the computer. The int itself is not the bits. The int is not in the computer at all; it is an abstraction that has no physical existence. If you want to pass an int to another function --or to another machine for that matter-- you send a copy of the bits that represent the int but since the bits only represent the int, you are only sending a reference to the int, not the int itself.

If the called function changes the bits, it does not thereby change the int that the calling function is referencing because the calling function has a different copy of the reference. This is what call-by-value means: the caller sends a copy of its reference so the callee cannot change the caller's reference. In call by reference, the caller sends a reference to its reference. In this case, the caller can access the callee's reference and modify the bits in it, thereby making the callee's reference refer to a different int.

By contrast, a Java object is a concrete object that exists in a particular time and place, an object that changes over time. Changing the bits of an object is the same as changing the object itself. So when a caller sends a reference to an object, it is sending a reference to something that can change. If the called function changes this thing, then naturally the caller will see the effects of the change.

But here is the important part: just like for the case with int, the caller has only passed a its of your reference to the object. The called function cannot change the caller's reference so when the function returns, you know that whatever the object looks like, the object that the caller is referencing is still the very same object that it was referencing before the call. The called function cannot change what object the caller is holding on to. So let me stress this: it is call by value because the called function cannot change which object the calling function is referencing. In call by reference the calling function passes a reference to its reference. This lets the called function change the reference of the caller and does let it change which object the caller is referencing.

Bob sent both his paper and his car by value. The journal editor could write obscene comments on the paper, but that would not change the paper that Bob wrote, it only changes the editor's physical instance of the paper. If the detailer writes obscene comments on the Firebird, it very definitely is changing Bob's car and Bob probably won't be happy about it. But it is still the same car; it is still Bob's Firebird. The detailer can't change that. Even if the dealer steals the car and sells it off to a chop shop, it is still the same car as long as it is a car at all (the analogy breaks down here because the detailer can, in fact, destroy the car).

So this is the real difference between pass by value and pass by reference as it was intended by the language designers: it isn't whether the called function can modify the object --that is a function of what category of object it is. The difference is that in call by value, the called function has an independent reference to the object and cannot modify the caller's reference. In call by reference the called function does have access to the caller's reference and can change what value or object the caller is referencing.

The cyber-materialist model is that all values are concrete. A cyber-materialist would argue that this distinction between abstract and concrete values is an illusion. You can change an int; just assign a value to it. The int is a concrete object that lives at a certain place in memory and changes over time just like any concrete object. The sequence of bits in an int variable is just the current state of the int, as the current contents of an array is the current state of the object.

To deal with this objection, the cyber-dualist model becomes even more complex. To a cyber-dualist, an int is an abstract object but an int variable is itself a concrete object used to hold an abstract value. It is the variable that can change, not the int itself. When you assign a new value to an int variable, you are changing the variable, not the abstract value in the variable.

But the cyber-materialist can object that Java lets you change the inside of an int variable:

int i = 0xFFFF;

i &= ~1; // unset bit 1

((char*)&i)[0] = 0; // set byte 0 to 0

How is this any different from changing a value in an object? You can view the above operations as changing the whole int, but you can just as easily view an array operation

a[0] = 0;

as changing the whole array.

In other words, instead of being a dualist and treating ints differentlly from objects, why not go whole hog and treat all objects as abstract objects? Why not become a cyber-abstractionist? Because cyber-abstractionism like cyber-materialism admits only one kind of object, it also would imply that C, C++ and Java have two different parameter-passing methods.

The cyber-dualist responds that you can’t consistently view the array operation in a cyber-abstractionist way. Assignment follows the same rules as parameter passing and the equality operator follows compatible rules. So you have this situation:

int i = 5; // now i == 5

int j = i; // now j == 5

int a[] = {1,2,3,4}; // now a[0] == 1

int* b = a; // now b[0] == 1

i = 10; // now i == 10 and j == 5

a[0] = 10; // now a[0] == 10 and b[0] == 10

A crucial distinction between abstract objects and concrete objects is what it means for one object to be identical to another. This shows that the value in an int variable behaves like an abstract object: when you assign it you are only passing a representation. Changing the original representation to something else does not change the representation that was assigned. By contrast when you assign an array to a pointer, you are creating a co-reference to the same location.

It would be poor engineering practice to fight the model of the programming language you are working in, so if C, C++, and Java consistently maintain this distinction between abstract and concrete objects and if they fully support both categories of objects then that would seem to settle the matter in favor of cyber-dualism. Unfortunately these language do not support abstract objects either consistently or fully. In Java if you declare two strings like this

String s1 = "abc"

String s2 = "abc"

then test s1==s2 you will find it to be false. Strings are abstract objects so two identical strings ought to compare equal. What is going on here is that Java represents strings with Java objects and all Java objects are concrete values. So while Java Strings may be immutable, they are not abstract values. Java is being consistent in that "==" tells you if two concrete objects are the very same object. The problem is that you want a string to be an abstract object.

This oddity is a consequence of the fact that Java does not support user-defined data abstractions of abstract values. Java’s only data abstraction feature is through Java objects which are concrete values. Java does have a standard equals() method for comparing objects, but this method can’t even be used on Java’s actual abstract object --numbers and booleans, so it cannot really be viewed as Java’s equality operator.

C does have a feature for user-defined data abstractions of abstract objects, but the feature is limited. In C, you use structs for data abstractions. If you want to define a concrete object, then you represent the object by a pointer. When an object is represented by a pointer in this way, then assignment, parameter passing, and equality checks naturally work out correctly for a concrete object. If you want to define an abstract value, then you represent the value with an in-place struct. Assignment and parameter passing make a copy of the struct and equality comparison does a bit-by-bit comparison. This is the right thing to do for an abstract value since the bits represent only a reference to the value.

It would be nice if you had full power to use this feature to create any abstract values you want, but you can’t because in-place objects are copied everywhere so there are practical limits to how large of an object you can represent this way. Consequently, if the abstract object is large or variable-sized then you need to use a pointer representation which ends up giving you a concrete value that you have to pretend is abstract, much like Java strings.

Furthermore, the way that C handles structs is confusing for someone trying to following the cyber-dualist model. Structs are treated consistently as abstract objects. When you compare two structs, it compares the representations. When you assign one struct to another, the bits are copied. When you pass a struct to a function, the bits are copied. This is exactly the way that C handles numbers and it is the way that you would expect an abstract object to be handled. But structs have fields that can be assigned to, and assigning to the field of a struct is alway described as a modification to the struct just like assigning to an array reference modifies the array.

If array are concrete objects you expect to be able to modify them, but structs are abstract objects so it should not be possible to modify structs. Because of assignments to fields, it is natural for programmers to view structs as being concrete objects like arrays, and therefore they expect the structs to work like arrays in parameter passing.

C is formally consistent here if you realize that a struct is treated as a large variable holding an abstract struct value. Assigning to a field of a struct is like the examples above of changing an int variable; it should not be viewed as changing the struct but as changing the value in the variable so that now this large variable represents a different abstract struct. Although this works formally it is a rather strained and unintuitive way of looking at it, and you can’t blame programmers for viewing it in the obvious way.

C++ has operator overloading which lets you define “==” to do whatever you want. Because of this, C++ technically lets you define data types that represent either abstract or concrete values. But C++ also lets you define objects that don’t seem like either category of value. C++ lets you define abstract values in much the same sense that a fully-stocked auto parts store can sell you a car --in the sense that you can buy all the parts and build the car.

Declarative languages (of which pure functional languages are a subset) do a better job of handling abstract values, both in the built-in types and in the facilities for user-defined values but pure declarative languages do not let you define concrete values. Declarative languages can be considered the languages of pure cyber-abstractionists, much like pure object-oriented languages are the languages of cyber-materialists.

The large majority of languages used by real programmers to get work done are in between. They have some values that can be viewed as abstract, some values that can be viewed as concrete, and no very clear and precise distinction. Many languages have variations on immutable or const objects, but in many cases (such as the Java String class) they are just concrete objects that don’t change.

So the disagreement seems destined to continue until we come up with a language that makes a clear and precise distinction between these categories of value. Until then, try to be understanding of the ontological differences of your fellow programmers.

back to semicolons for a moment

Someone asked me in a comment to Why Programming Languages Should Die what is the difference between semicolons used as statement separators and semicolons used as statement terminators. The difference is basically the difference between the period and the comma in English. You use a period to terminate a sentence and you use a comma to separate phrases.

When semicolons are used as statement terminators, there are certain statements that require a semicolon at then end, such as expression statements in C:

a = b+c;
function_call(a,b);

There are other statements that do not require a semicolon at the end, specifically compound statements:

if (a) {do_something();}
a = b+c;

You never need a semicolon after a compound statement like that, even if there is another statement following it. In Pascal, statements are used as separators. An assignment doesn't need a semicolon after it if it comes at the end of a block. In Pascal, blocks are surrounded with begin and end rather than braces, so this is legal:

begin
  a := b
end

But semicolons are needed between statements so you need a semicolon after an assignment if it has another statement following it, and you also need one after end if another statement follows it:

begin
  a := b;
  begin
    a := c
  end;
  a := d
end

So although the semicolon-as-separator makes a lot of intuitive sense, it is odd in practice and programmers tend to forget them or put them in the wrong places more often than they do with languages where the semicolon is just used to end certain statement types.

Infinite Digits to the Left

Some numbers do not have finite representation in normal decimal notation. For example1/3 has a representation like 0.33333... where the list of threes never ends. Irrational numbers like pi also continue on forever, but without the repetition.

I think most imaginative students when they are introduced to this fact, immediately wonder: what about the other direction? These are numbers where the representation to the right is infinite, but what about if the representation to the left were infinite? I’m going to start by explaining why the question isn’t really mathematically interesting, then I’ll explore the mathematics of such numbers.

Why the Question Doesn’t Matter

The question seems to be based on the idea that there is something mathematically significant about the way that numbers are represented in decimal notation, but that’s not really the case. Numbers that repeat endlessly to the right were not discovered by mathematicians playing around with the decimal representation, but rather by mathematicians discovering limitations in decimal notation.

There are other ways to represent numbers than by decimal notation. You can represent numbers with tick marks so that the first ten whole numbers (integers greater than 0) would be represented like this:

1

11

111

1111

11111

111111

1111111

11111111

111111111

1111111111

That’s pretty unwieldy and it’s hard to read larger numbers so similar number systems put a slash through each group of five. The Romans used to use a more complex method that was even easier to read. They represented the first ten whole numbers like this: I, II, III, IV, V, VI, VII, VIII, IX, X.

Decimal notation is just another way to represent numbers. It is a notation where you can represent a number x by a procedure that calculates S(x) --a sequence of digits that represents x. In the following, DIV(x,y,i,j) takes two numbers x and y. It sets i to the number of times that y goes into x and sets j to the amount left over. In other words, i is the integer result of x/y and j is the remainder. Here is how you calculate S(x) for a whole number. It writes the number from left to right:

Calculate S(x)

1. Find d, the smallest power of 10 that is greater than x.
2. Set d = d/10
3. DIV(x,d,i,j).
4. i is guaranteed to be between 0 and 9 so write the digit i
5. Set x = j
6. If d > 1 go to 2

When d = 1 in step 6 we are done. At that point we are guaranteed that x = 0 because for a whole number x, x/1 = x with no remainder. This means that we have represented the entire number with complete accuracy and did it in a finite number of steps.

If we want to represent other numbers besides the whole numbers, then we need to add some steps:

7. If x > 0 write a dot
8. if x = 0 then we are done
9. x = x*10
10. DIV(x,1,i,j)
11. i is guaranteed to be between 0 and 9 so write the digit i
12. Set x = j
13. Go to 8

We switched techniques here. For the whole part of the number, we divide by ever smaller powers of 10. When we get to the fraction, we start multiplying the fraction by 10 each time through the loop and dividing by 1. It is possible to do the whole procedure with a single technique but I’ll leave that as an exercise for the reader.

With this modified procedure, we keep going as long as x is not 0. But now there is no guaranteed stopping condition. The procedure will only stop if the remainder of the division goes to 0. The remainder may never to go 0 and that is why the representation is said to be “infinite” to the right, because the procedure for generating the representation never stops.

So the numbers that have a representation that are infinite to the right aren’t “defined” by decimal notation that is infinite to the right --that is just an accident of the notation, a failure of the notation, actually because it shows that there are numbers that can’t be represented using decimal notation. But there is nothing especially interesting about a number that can’t be represented by a finite S(x).

The algorithm above uses 10 as the base, but that is essentially an arbitrary choice because any other base could be used. And for each rational number, there are bases where the number could be represented in a finite string of digits for a rational number x, an infinite S(x) is just a consequence of the mathematical relationship between x and the base. It doesn’t tell you anything interesting about x on its own.

For irrational numbers, they are interesting because they can’t be written as any ratio of two whole numbers. The fact that they can’t be represented in decimal notation with a finite sequence is just a minor consequence of this far more important fact.

So the fact that a number is infinite to the right in decimal notation is not interesting. All it does is point out the limitations of decimal notation.

A Theory of Numbers that are Infinite on the Left

The fundamental misunderstanding that leads to the question about numbers that are infinite to the left is the idea that decimal notation is an interesting way to create or define numbers rather than merely a convenient representation. Here I’ll investigate that intuition. It’s simpler to stick with whole numbers so I’ll do that in the following. The extension to numbers that can be infinite in both directions is left as an exercise for the reader.

Given a sequence of digits s, we can calculate D(s), the number that the digits represent by reversing the procedure for S(x):

Calculating D(s)

1. Set x=0
2. Set d=1
3. Set i=the rightmost digit in s
4. Set x = x + d * i
5. Set d = d*10
6. If there are no more digits to the left then we are done.
7. Set i = the next digit to the left
8. Go to 4.

So let’s say that we have an infinite sequence of digits that extends infinitely to the left rather than the right. A sequence of digits is not a number but we can try to make it represent a number by applying the procedure above for D(s). The problem is that the procedure for generating D(s) will never terminate if s is infinite.

That doesn’t necessarily stop us because there are techniques for dealing with infinite sequences. In the algorithm for D(s) there is a variable x that takes on a successive sequence of values that eventually become the answer in the case of a finite sequence. So we can say that if x ever stops changing, then that is the answer. If we get to a point in the sequence where every single digit to the left is a 0, then x will never change again and we can make that the answer. We have to do this so that, for example, if s is sequence ...00000001 with an infinite sequence of 0s to the left then D(s)=1. Since these finite sequences produce finite numbers, we will call them finitoid.

Other infinite sequences are infinitoid. An infinitiod sequence is one such that no matter where you are in the sequence, there is a digit to the left that is not 0. For an infinitoid sequence, the x in the D(s) procedure has no upper limit so we say that D(s) is infinitoid.

In other mathematical contexts, we might say that the limit of x is infinity or that D(s) is infinite but that does not lead to an interesting theory of infinitoid numbers. The reason is that in normal mathematics, two infinite numbers are always the same (well, there are different orders of infinity, but that doesn’t apply here because all infinitoid numbers are the same order).

So let’s not say that all infinitoid numbers are just the same value, “infinity”, let’s say that they are all different.

You  can skip this section if mathematical logic frightens you

There is precedence for this in formal logic. I would give you the Wikipedia entry for Herbrand Universes or various consistency results but it would just confuse things if you don’t know mathematical logic, so let’s just say that when you want to define a set of mathematical objects that may or may not exist, you can get by with the assumption that they exist, as long as you have something to map them to.

In other words, we don’t have any reason to think that infinitoid numbers exist, but we know that infinitoid sequences exist so we can set up a correspondence between the sequences and the numbers. As long as everything we have to say about infinitoid numbers can be mapped to a statement about infinitoid sequences we know that we are saying something consistent. I’m not going to actually worry about this, but just note that the possibility of doing this in principle justifies talking about infinitoid numbers even if we can’t actually say what they are.

The point of the above digression is that it is safe to assume that we could in principle come up with a consistent theory of infinitoid numbers. Just not, as I’ll show, a consistent theory that looks anything like numbers.

On that ominous note, let us see if we can extend the addition operation to work on infinitoid numbers. We start by defining a function on sequences of digits: if s1 and s2 are two sequences of digits, then plus(s1,s2) is the sequence of digits that you get by applying the normal addition algorithm that we all learned in school. Keep in mind that this function operates on sequences of digits, not on numbers. But we can use this function to define addition on infinitary numbers: if x and y are numbers and at least one of them is an infinitary number, then x+y is defined as D(plus(S(x),S(y))). In other words, we convert both numbers to sequences of digits and then apply our schoolroom addition algorithm.

We can define multiplication and subtraction in a similar way but not division or comparison. The division algorithm starts at the left, and in an infinitoid sequence there is no left-most digit. Similarly, to compare two numbers as digit sequences, you have to compare the leftmost digit of the shorter sequence. So we can compare a finitoid number to an infinitoid number; the infinitiod number is always larger. But we can’t compare two infinitiod numbers because we need to get to the leftmost non-zero digit which does not exist.

This is a serious problem. One of the essential properties of numbers is that for any two numbers x and y, either x=y or x<y or x>y. This property doesn’t seem to hold for infinitoid numbers and I can’t think of any consistent way to define comparison to make it hold (except to take the usual mathematical approach and say that all infinitoid numbers are equal to each other).

There is another very important theorem that infinitoid numbers violate: the theorem that if x>0 then x+y>y. That is, if you add a number greater than 0, then the result is increased. That does not hold for infinitoid numbers. Let s9 be the infinitoid sequence that consists of an infinite sequence of 9s. Then

D(s9)+1 = plus(“...9999”,”...00001”) = D(“...00000”) = 0.

Since D(s9)>0, the answer should be greater than 1, but 0<1. And since 1>0, the answer should be greater than D(s9) but 0<D(s9).

This is a very serious problem. I can’t think of any way around it except by restricting all sequences to prevent an infinite sequence of 9s to the left at any point in the sequence. This may seem at first sight to be analogous to the fact that in normal decimal notation infinite sequences of 9s are equivalent to another number. For example 1.9999... with an infinite sequence of 9s is equal to 2.

As I say, the situations may seem analogous at first sight but I don’t think they are. In the case with infinite 9s to the right, the issue is that there is no finite difference between 1.9999... and 2 so they are the same. The situation with infinite 9s to the left is that it allows us to get around an infinite process by induction --that is, we can finesse the never-terminating algorithm and find out what it would return after an infinite number of steps-- and doing so reveals an inherent inconsistency in the process which was there anyway.

Conclusion? Sequences of numbers that are infinite to the left make no sense mathematically and the question itself is based on a misunderstanding.

A Compositional SELECT Statement --Part 2

Here is the next part in my series on compositional SQL. In this one show how to handle AS and DESC and give a more rigorous semantics.

Why Programming Languages Should Die

Back in the day, the semicolon issue was a big deal. Compiling was a lot slower so putting a semicolon in the wrong place was a painful experience shared by everyone except Lisp programmers. Cliques and parties formed around concepts of proper semicolon use. Some enterprising rabblerouser did a study that showed that the Pascal syntax that treated semicolons as statement separators led to more syntax errors than the C syntax which treated semicolons as statement terminators. This inflamed the great controversy.

In those days, it was common for someone to introduce a new programming language with a brief description of the major features and those brief descriptions commonly included the language’s position on the semicolon issue. Python became famous as the language that “solved” the semicolon issue by making indentation significant. It was an interesting language with lots of interesting features, but was mostly known for the indentation. The Icon programming language had some marvelous innovations. Descriptions of it often went something like this:

Icon is a procedural programming language where any expression can potentially generate a stream of results rather than just one. Boolean operations and control structures are defined to make use of multiple results in ways that make them more powerful than in single-result languages. There are powerful built in data structures and a string scanning construct that uses generators to create a new way of matching and parsing strings. Oh, and semicolons are statement separators except that they are optional at the end of a line when they are not needed for disambiguation.

One of these things is not like the others. Would Icon have been a significantly different language if there had been a different semicolon rule?

It gets worse. It isn’t enough that language designers get pedantic about semicolons, companies and programming groups get pedantic about how long your lines get, where the left brace goes, and how many spaces you indent.

Why don’t mathematicians get hung up on syntax like this? Where are the competing mathematics languages with schools of thought about whether the factorial symbol ought to be a suffix operator or a prefix operator? Mathematicians make up notation as they go and there are usually not too many complaints (there are some notable exceptions like Principia Mathematica).

Notation doesn’t matter so much to mathematicians because mathematics is only intended to be read by people. Programming languages must be readable by machines as well as by people and so there is a need to compromise between the strict rules that are needed by computers vs. the flexibility that is valued by people.

But that compromise is only needed because the computer needs to read the same text file that the people read. What if it didn’t? What if the computer could read a file of abstract syntax trees and people could still read programming language text?

An abstract syntax tree or AST is how the compiler sees your program after parsing and before generating code. It is basically the logical structure of your program. More specifically, the compiler sees your program as a symbol table that matches symbols like function names to abstract syntax trees that implement the function. And this is how the computer should always represent the logical structure of a program --not just in the compiler. The programming language text should only be an form of presentation to the user and never input to the computer.

Imagine an editor that guides you in writing a program. You don’t have to know the exact computer-precise syntax for a function declaration. You just press a button that says “create function” and the computer prompts you for the function name. Then it prompts you for the return type, then for the parameters and their types. When you have entered the information the computer shows you the function declaration and puts your editing point in the body of the function. When you type “if” in the function body, the computer lays out an if statement with condition, then branch, and else branch empty for you to fill in.

There are programming editors that superficially work like this, but what they do is generate programming language text for the compiler to read. What I am proposing is that the computer builds the abstract syntax tree as the user types and generates code directly from that AST. The computer never stores programming language text on disk, only presents it to the user in an editing window as a view of the AST. And when the editor presents the text, it automatically formats it according to some specification so the user never has to worry about how many spaces to indent or how long the lines are.

Modern integrated development environments have a cataloging function or a separate program that reads through the source files parsing them just enough to get declarations so that they can construct a database of named entities (classes, functions, variables, etc.) and then the code browser uses that database to look up declarations in the source code. The database can get out of date, and it can slow down your computer when the cataloging function is running. This is not needed if the computer stores the program as an AST. The internal representation of the program already is a database of declarations that the code browser can access directly.

Other utilities like the debugger, the diff program, and the revision control system also have to work with ASTs rather than text so they can work with logical structure rather than lines and they don’t need a parser to do so.

How the computer presents the progam to the user is no longer bound to a particular language, only to the logical structure of the program. The user can ask for a C-like representation:

int f(int n) {

 if (n < 2) {

   return 1;

 } else {

   return n*f(n-1);

}

or Pascal:

function f(n: integer):integer is

begin

 if n < 2 then

   factorial := 1

 else

   factorial := n*f(n-1)

end

or Lisp:

(function (f n)

 (cond (< n 2) 1 (* n (f (- n 1)))))

or pick a more mathematical representation like

f(n) = 1, n < 2

f(n) = n * f(n-1) otherwise

(the above is a real equation in Docs, but as usual it didn't transfer over to Blogger).

The possibilities are endless. There is no need to stick with ASCII or even text. Any form of presentation is possible, perhaps a graphical representation based on flow charts or E/R diagrams.

Now let’s go back to C notation and ask the editor to change the function name to “factorial”:

int factorial(int n) {

 if (n < 2) {

   return 1;

 } else {

   return n*factorial(n-1);

}

There is no need for the programmer to go through the program finding every instance of “f”, figuring out if it is a call to the function and changing it; the computer represents each call to f() as a pointer to symbol-table entry, not as a name. So when you change the name of f() in the symbol table the representation on the screen changes everywhere.

Up to now the computer has been hiding certain grungy parts of the code so that we can study the main logic undisturbed by the details of error handling. But when we want to see the grungy details, the computer shows us:

int f(int n) {

 assert(n>=0);

 if (n < 2) {

   return 1;

 } else {

   try {return n*f(n-1);}

   catch (NumericOverflowError e) {...}

   catch (StackOverflowError e) {...}

}

Notice that we aren’t changing the code, here, just revealing or hiding parts.

Even more complex view changes are possible. For example suppose you have a collection of object that all have a print method in common. Sometimes you want to see the print method as part of the object so that you can compare what it does with the members of the object:

class Foo::InterfaceX {

 int x;

 ...

 void print(ostream::out) {out << x;}

 ...

Other times you want to see all of the print methods together so you can compare what the different print methods in different classes are doing, perhaps with a syntax like this:

void InterfaceX::print(ostream::out) {

 typecase(this) {

 case Foo: {out << x;}

 case Bar: {out << y << "." << z;}

 case Zed:

 ...

Again, we aren’t changing the code, just viewing it in a different way.

When the program is represented as text the editor has to be able to do a complete parse of the program in order to come up with these sorts of sophisticated global view changes. But when the program is in the form of a name table of ASTs, then it is just a matter of some tree manipulation.

With this model of programming, a whole class of errors become impossible. You can’t put a semicolon or brace in the wrong place because you don’t type them at all (except possibly as a keyboard shortcut to indicate the end of a statement or something). Parentheses, braces, semicolons, function headers, class headers, type declarations --these are all just computer generated representations of your program structure. With programs-as-text, you have to tell this structure to the computer. With programs-as-ASTs, the computer tells you the structure. Of course you have to define the structure in some way. Perhaps with a dialog or perhaps with actual text --but in this case, the computer will not let you enter wrong text  --or at least, will not accept dumb typing errors.

For example, misspelling variable or function names is a thing of the past because the computer can’t parse the name until you spell it right. And since the computer knows all names that are in scope at any point, it can give you an abbreviated list of choices to complete the name. When you want to use a function from another module, you type the name; the computer gives you a list of modules that define the name, and you pick one. From then on, that name means what you told the computer it means and you don’t have to worry about changing what it means by careless use of declarations, imports or includes. The computer writes the declarations, imports and includes for you and always does it properly.

Of course there are complexities to deal with. If you look carefully at the different language examples then you will see cases where there are slightly different abstract syntax trees represented in the different languages. To handle these language differences the presenter of the AST has to be sophisticated enough to do certain local transformation based on the requested source language.

It would be impossible (or at least, very difficult) to implement full language-to-language translations. It would be better to invent extensions to various languages to support certain features. For example, basic Pascal does not have classes so if the language being presented has classes and you want to present it in Pascal form then you have to use a form of Pascal that has a class extension.

This is the way things ought to be in the Twenty-First Century. Computers should not use text as the internal representation for complex structures such as programs. Data should be represented as object and there should be generic tools to deal with such objects. Having a logical internal representation to deal with makes so many things so much easier to do, that it could lead to an explosion of new development methods if we had this sort of representation for programs.