Entries tagged - "programming-languages"
Ownership
This post is meant as an explainer about how substructural type theory can be applied in programming language design. Terms like “substructural type theory” tend to scare and confuse programmers who don’t write Haskell on the weekends, so one thing programming language designers should do when thinking about how they will present their language is invent metaphors, even slightly misleading ones, to help more ordinary programmers understand how their language works. One such term is “ownership.”
Not infrequently, objects in a program come to represent something outside of themselves; they are not “pure data” but some kind of resource with identity. A classic example of this might be a sort of handle granting exclusive access to a resource. For this to really work well you want to know that to get that object you had to execute certain code (a “constructor”), that when the object is no longer used some other code will be executed (a “destructor”), and that while the object is in scope, no concurrently executing code also has an object representing the same exclusive resource (that it is not “aliased”). This is what ownership (as presented in Rust, at least) is all about.
I want to demystify ownership and substructural types in the hopes that this will become more common knowledge. Nothing in this post is really groundbreaking - if you’re already “in the know,” it will contain no new information - but it does contain some notes on aspects of Rust’s implementation that I think are incorrect (one of which would even be easy to change).
…References are like jumps
In a high-level language, the programmer is deprived of the dangerous power to update his own program while it is running. Even more valuable, he has the power to split his machine into a number of separate variables, arrays, files, etc.; when he wishes to update any of these he must quote its name explicitly on the left of the assignment, so that the identity of the part of the machine subject to change is immediately apparent; and, finally, a high-level language can guarantee that all variables are disjoint, and that updating any one of them cannot possibly have any effect on any other.
Unfortunately, many of these advantages are not maintained in the design of procedures and parameters in ALGOL 60 and other languages. But instead of mending these minor faults, many language designers have preferred to extend them throughout the whole language by introducing the concept of reference, pointer, or indirect address into the language as an assignable item of data. This immediately gives rise in a high-level language to one of the most notorious confusions of machine code, namely that between an address and its contents. Some languages attempt to solve this by even more confusing automatic coercion rules. Worst still, an indirect assignment through a pointer, just as in machine code, can update any store location whatsoever, and the damage is no longer confined to the variable explicitly named as the target of assignment…
Unlike all other values (integers, strings, arrays, files, etc.) references have no meaning independent of a particular run of a program. They cannot be input as data, and they cannot be output as results. If either data or references to data have to be stored on files or backing stores, the problems are immense. And on many machines they have a surprising overhead on performance, for example they will clog up instruction pipelines, data lookahead, slave stores, and even paging systems. References are like jumps, leading wildly from one part of a data structure to another. Their introduction into high-level languages has been a step backward from which we may never recover.
— C.A.R. Hoare, Hints on programming-language design 1974
How embarrassing it is for the practice of software development that, when it comes to the subject of references, we have spent half a century creating an enormous object proof that Sir Tony was correct. Null pointers may have been his billion dollar mistake, but the decision to ignore his remarks about the problem of pointers in general was a trillion dollar mistake that everyone else made.
What Tony Hoare was writing about when he said that references are like jumps was the problem of mutable, aliased state. If you have in a language the ability to alias two variables so that they refer to the same location in memory, and also the ability to assign values to variables as execution progresses, your ability to locally reason about the behavior of a component of your system becomes badly inhibited. Depriving the user of the ability to mutate aliased state by accident is critical to enabling the user to easily create correctly functioning systems.
…Coroutines and effects
For the past few months I’ve been mulling over some things that Russell Johnston made me realize about the relationship between effect systems and coroutines. You can read more of his thoughts on this subject here, but he made me realize that effect systems (like that found in Koka) and coroutines (like Rust’s async functions or generators) are in some ways isomorphic to one another. I’ve been pondering the differences between them, trying to figuring out the advantages and disadvantages of each.
A few weeks ago, Will Crichton posted something on Twitter that helped bring the contrast into sharper focus for me:
The entire field of PL right now: what if it was dynamically scoped…. but statically typed…………..? (effects, capabilities, contexts, metavariables…)
I’m just a humble language designer (and not a theorist of anything, especially not PL), so my focus is the difference in user experience and affordance. But this seems like a cutting insight and this property of effect handlers - static typing but dynamic scoping - seems to me to be a good jumping off point for understanding the difference between effect handlers and coroutines from a user perspective.
…