Saturday, September 13, 2014

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.