1
$\begingroup$

I'm a big fan of Algol 68's treatment of variables. "Variables" are just constant references that point to memory allocated on the stack or on the heap. When you refer to a variable or a component of one, the result is of type "reference to T" instead of T directly; but values of type "reference to T" will be coerced into values of type T automatically. There is no need for an "address of" operator. In assignment and parameter passing, objects are copied (but a copy of a reference points to the same object as the original). Variable bindings always have dynamic extent (no closures); objects have indefinite or dynamic extent depending on whether they are heap- or stack-allocated. See the bottom of the post for more details about Algol 68.

I'm also a big fan of variables in Lisp and most dynamic languages. It's sometimes called "pass-by-sharing" or "pass-by-identity". Assignment and binding cause variables to hold the same object, instead of a copy. This essentially necessitates working with references to objects instead of objects directly. Bindings and objects have indefinite extent.

In my language, I have Lisp-style variables. Recently I've been contemplating adding references in order to increase its expressive power (e.g., the assignment operator can be described using the language itself*, since I have user-defined operators). However, I would want references to behave as in Algol 68 (or C++), with automatic dereferencing. But with Lisp-style variables, every binding has an implicit additional level of indirection, and the two ideas don't seem overly compatible.

Should I work the Lisp-variable-ness into the coercion process along with dereferencing? (Thereby adding one more level of indirection to Algol-style variables.) Is there prior art for that? Or an alternative to references that generalizes lvalues and expressions and allows the assignment operator to be defined.

I'm also not positive about how references interact with indefinite extent bindings and closures. Like, can a local variable escape its scope by assigning a reference to it to an outer variable? Should bindings have dynamic extent unless captured in a closure?


* A procedure to implement the operator would require support from the runtime/compiler, but its type can be expressed and lvalues can be consistently defined if the language has references.


Algol 68 is decently obscure these days, so here's some more information about how it deals with variables. Note that actual Algol 68 terminology is idiosyncratic and I'm "translating" it here to be more widely understood.

The simplest kind of declaration in Algol 68 is the "identity declaration", which corresponds roughly to a constant in other languages:

int i = 1;

This means that i is synonymous with the value of 1. More complicated example:

real circumference = 2 × 3.14 × r;

The right hand side of the = is evaluated and "ascribed" to the identifier on the left, so that they are equivalent in expressions. The computation of the value may involve side effects and need not be possible at compile time.

When an identifier has been introduced in an identity-declaration, it is conceptually replaced by its meaning every time it is applied. Re-declaring the same identifier creates a new binding.

To construct an object of a given type in Algol 68, you use a "generator", which looks like loc ⟨type⟩ or heap ⟨type⟩. Where the object is allocated is determined by whether you write "loc" (value is on the stack with dynamic extent) or "heap" (value is in heap with indefinite extent). The result of a generator is a value of type "reference-to-⟨type⟩", which is conceptually just a pointer to some part of the machine's memory. To express a reference type in Algol 68, write "ref ⟨type⟩".

Operations like array subscripting yields a reference, because it denotes a location in memory. Thus if you have an array A holding int, then A[2] would yield a value of type reference-to-int.

Algol 68's assignment operation is defined to operate on values of type "reference-to-t". For example,

(heap int) := 5

is like

*(malloc(sizeof(int))) = 5

in C; in both languages, it allocates space for an integer in the heap, stores 5 there, and promptly forgets about it.

Algol 68 assignment always copies the value.

As a consequence, you can get an int "variable" by writing

ref int i = loc int;
i := 5

This means "declare i as constantly holding the value resulting from evaluating loc int, which will be of type reference-to-int; then store the value 5 in the memory location just ascribed to i. The value (a pointer) ascribed to i will not change as long as it is in scope; but the value i points to may vary. The assignment construct evaluates the left-hand-side to obtain a reference; there is no special case for when the destination of an assignment is an identifier.

Such notation is common enough that there's syntactic sugar (the initializer := 5 is optional):

loc int i := 5;
heap int j := 5;

In fact, the loc or heap may be omitted, in order to make code look more like Algol 60.

All this is fine, but we still don't really have an "int variable". We have a constant reference-to-int. Theoretically, that means you'd have to dereference i anytime you don't want to assign to it (which is probably the more common case). Instead, Algol 68 defines a coercion from any type reference-to-⟨type⟩ to ⟨type⟩, which gets applied whenever necessary. In other words, dereferencing is automatic; in fact there is no way to dereference a value explicitly. Note that there is also no address-of operator, since anything we could meaningfully take the address of (variable names, array slices, fields of structures, etc.) already happens to yield a reference.

As a consequence of this system, classic problems are easily accounted for:

if p(x) then a else b fi := 10;

proc swap integers(ref int a, b) void:
  (loc int t := a; a := b; b := t);

loc int i := 1, j := 2;
swap integers(i, j)

The first line is like *(p(x) ? &a : &b) in C.

A "pointer to a variable", rather than to a memory location created by a generator, is of type reference-to-reference-to-⟨type⟩. Another way to think about this is as "non-constant references".

loc int v := 10, w := 11;
loc ref int p;
p := v;
print(p);
p := w;
print(p)

The assignments to p copy the references ascribed to v and w. Note that the declaration of p is equivalent to

ref ref int p = loc ref int;
$\endgroup$

1 Answer 1

3
$\begingroup$

Disentangling variable semantics from calling conventions

First off, I want to caution against confusing the semantics of variables and types with semantics of parameter passing. In Lisp (and Python, and for most types in Java, and for selected types in C#), variables have reference semantics, i.e. the rule that "variables hold references and assignment copies the reference". Reference semantics are particularly common in dynamically typed languages, simply because the assigned value might use a different amount of memory than the original value for its underlying representation; since indirection is generally required anyway, it may as well be used to avoid unnecessary copying.

So-called "pass-by-sharing" or "pass-by-identity" is really pass by value in a context where the passed value has reference semantics. In an earlier era, people thought the terminology "pass by value" was confusing for such languages; but as originally defined, it's a perfect fit. Another more modern term is "pass by assignment" - meaning that passing an argument to a parameter works the same way as assigning a value to a variable.

Evaluating reference types in C++

As for the main question: true pass by reference is quite rare in contemporary languages, and the C++ implementation is weird and arguably not quite the same thing. (I'm not familiar with Algol 68, but I'm inferring from your description that it works substantially the same way as in C++). Conceptually, "pass by reference" should be a parameter passing convention, but C++ models this by making "references" into a separate type category (and further confuses things by adding this to a language that already has "pointers", which in generic computer science discussion would be considered a form of "reference").

This approach accomplishes the goal of enabling "operator overloading" for assignment. Perhaps a more classic test - which can be applied in a more language-agnostic way - is that this scheme allows for writing a "swap" function that swaps the values of two of the caller's variables. This can't happen with pass-by-value, even when the values have reference semantics, because the function is given different references. But C++ causes assignments to the reference, to affect the referred-to original value, rather than changing the referent ("re-seating" the reference, in the terminology of the C++ FAQ Lite).

And that causes all manner of problems when one tries to develop a proper mental model. C++ references can to some extent be treated like const pointers, except that they can't legally be NULL or dangling, and attempting to use them inserts indirection into the code that isn't actually there, and you can write an assignment even though it's const because it actually assigns to the indirected target. But on the other hand, there might not actually be a value there at all after even the most basic compiler optimizations. Unless the reference is a member of a data structure somewhere, in which case it might have to exist just to take up space and have an address (which must be distinct from the addresses of other members).

It's really a quite complex idea. And that's without even touching on the issue of "bindings and closures", as you mention it - i.e., the lifetime of the referent vs. its references. This is especially complex without garbage collection, but I expect it would still be a massive headache in a garbage-collected language that implemented references this way. C++ ends up needing special rules like this one and that one. I'm afraid I can't tell you anything useful about how to implement that sort of thing.

Discussion and alternatives

Personally, I don't think that contemporary languages with reference-semantics variables benefit much, if at all, from support for pass by reference. Users can always just wrap the value in a container, which is passed by value and modified by the function; or the calling code can assign back whatever returned value. Being able to modify the passed-in object is generally sufficient for typical programming idioms; things that can't work this way often have separate support (for example, Python has a multiple assignment idiom that makes a theoretical swap function sound clunky and useless).

I suspect that a major reason why true pass-by-reference has become so rare is because it can make programs very difficult to reason about, by violating the apparent atomicity of functions. It's already considered poor practice to have "mutable shared state" without well-defined boundaries - for example, to have functions that communicate by modifying a global variable. Re-assigning a variable from an enclosing lexical scope (rather than, say, an attribute of an object, within the code for a method) is already a major source of bugs. True pass by reference is something like the dynamically scoped equivalent of that - modifying a variable from the caller, i.e., an enclosing dynamic scope. It effectively introduces a dynamic scoping concept into an otherwise lexically scoped language. Dynamic scoping is also an increasingly rare language feature, so this could easily be counted as another strike against pass by reference.

That said, if you really want the kind of flexibility and semantics that you describe, I would strongly encourage you to instead consider how C# implements pass-by-reference. C# allows for types that have value semantics as well as those with reference semantics - called "value types" and "reference types", respectively, in documentation. (I couldn't use these terms before, since "reference type" means something fundamentally different in C++.)

More importantly for the current discussion, it also allows for passing either by reference or by value, as well as supporting "out parameters" (functionally pass by reference, except that the passed-in value may not be used and thus is not required to be initialized). To avoid surprises (and perhaps ease compilation - I don't know any relevant implementation details), the calling convention must be marked on both the function and the caller.

And, crucially, pass by reference is treated as a true calling convention, and not a property of types. You can pass the same value by value or by reference to different functions, and you can do this with both value types and reference types. It's especially useful for value types, since it allows for modifying the passed-in value as well as replacing it. (Passing a reference type by value allows for modification, but not replacement. But keep in mind that such modifications can be "seen" by other potential referers, too, whereas replacement would not be.)

$\endgroup$
3
  • $\begingroup$ Algol 68 references are similar to C++'s but they're more consistent because the language was designed around them (think BLISS or MDL, except they require explicit dereferencing), whereas in C++, as you point out, references were just shoved into a language that already had pointers. In Algol 68, references are tightly integrated into the type system. $\endgroup$
    – texdr.aft
    Commented May 22 at 20:44
  • $\begingroup$ If they require explicit dereferencing, then aren't they basically just "safe" (restricted) pointers? In that case, if added to a system where variables have reference semantics, they would essentially just function as syntactic sugar around the "wrap in an object/length-1 container" tricks. I think languages like Python have resisted adding that kind of functionality for the reasons I vaguely pointed at - it doesn't come up often enough, and is powerful/dangerous enough that they don't want to make it easier. $\endgroup$ Commented May 22 at 21:19
  • $\begingroup$ Sorry, I was unclear. I meant that in BLISS and MDL dereferencing is required. I've added some more information about Algol 68 to my question for additional context. $\endgroup$
    – texdr.aft
    Commented May 22 at 21:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .