Lambda the Ultimate

(I'll write up a piece replying to the original post later, about const tactics.)

For instance, BitC had a "deep const" notion, which means that const is applied transitively to every value read through the deep const reference.

Which reminds me of a COW (copy-on-write) thing I did in a btree library in 1996 at Apple for structured storage. (There was an earlier patent-oriented discussion I ignored because I didn't want to even bother saying I would not read the patent.) The main idea here is, "Once you pass through a const reference, everything is const." But this is library level, not programming language level. It's trivial if one thinks spatially in terms of graphs.

The idea was block-oriented i/o, in fixed buffer space, using hand-rolled demand paging, with everything in trees (dict indexes and blobs both). Old content was immutable. But COW was used to incrementally patch old trees, starting from a new root that shared old tree nodes via const references. (One bit in the block offset reference meant "const".)

One makes a new mutable version of an old immutable tree by copying the root to a new mutable instance, then marking each node reference const in the new mutable copy. So you can navigate to any old node in the immutable tree, but you can't write any immutable node reached by passing through a nonzero number of const references. (This amounts to "boundary logic" in a Venn diagram separating mutable from immutable space with a const boundary.) Any attempt to write an immutable node copy-on-writes that node, as well every immutable parent above on the path discovered while navigating down from the mutable root.

It has the neat property that immutable blocks are never written, and blocks themselves don't need to know they are immutable, because the immutable bit in references is done in mutable blocks that hold the references to immutable nodes. (It was also an append-only store, but this isn't related to constness much.)

About ten years ago I started hearing from folks at storage solution companies, who seemed unhappy to hear I had done that, because it pre-dated their storage patents based primarily on ideas that "COW is so clever it's patentable."

Which reminds me of a COW (copy-on-write) thing I did in a btree library in 1996 at Apple for structured storage. (There was an earlier patent-oriented discussion I ignored because I didn't want to even bother saying I would not read the patent.) The main idea here is, "Once you pass through a const reference, everything is const." [...] About ten years ago I started hearing from folks at storage solution companies, who seemed unhappy to hear I had done that, because it pre-dated their storage patents based primarily on ideas that "COW is so clever it's patentable."

The KeyKOS operating system already did this in the 70s with "sensory keys". Node trees defined a process' address space, where the page tables are an in-memory cache of the node tree. If a process had a sensory key in its node tree, the subtree it designated was read-only and COW. Everything old is new again.

The KeyKOS operating system already did this

Yes, I didn't mean to suggest it was a new idea then. Architects at Apple always said "yes, of course" the instant I summarized the CoW plan and the effect of const annotations on node references. My point was that transitive const is an idea obvious in the first several seconds after thinking about CoW integrity maintenance.

Sensory keys were carried forward into EROS and Coyotos as well, where they were called "weak" capabilities.

Referring to my distinction below between read-only and immutable, weak capabilities are transitively read-only rather than transitively immutable. In order to show that the target graph is [deeply] immutable, you need to show that at some point in time there is a "perimeter" to the graph such that any capability outside the perimeter that denotes an object inside the perimeter is a weak capability. At that point, all of the outstanding capabilities are transitively read-only, and the data structure is therefore known to be transitively immutable.

This perimeter test is the essence of the confinement test performed by the KeyKOS "factory" and the EROS/Coyotos "constructor". It turns out to be a practically useful tool for building systems that exhibit defense in depth. For example, a new subsystem (process) constructed solely from weak constituent capabilities can observe mutations to data structures but cannot perform mutations on those data structures. This imposes a form of partial separation, and it's fairly easy to get from there to complete separation. To re-frame that in PL terms: the invoker of that subsystem knows that the only potential sources of information "escape" are object references (capabilities) that the caller provides.

If you can further show that the subsystem is "memoryless" (retains no state across calls), then you know something about how it can safely be serially reused.

It was also the impetus for looking at the whole notion of deep immutability in BitC.

While I appreciate the benefits of pure functional algorithms for certain kinds of processing, in some cases they transform fairly straightforward iterative solutions into clever brain-twisters that are primarily of interest to enthusiasts and academics. If a data structure is more efficiently implemented using mutation, then I would at some point want to examine the justification for hiding the fact of mutation from the user of that data structure. If the answer is "it makes reasoning about the behavior of the program simpler" then all well and good; But if the programmer has to go through complex contortions to accomplish something that is actually very simple under the hood, then I'm fully prepared to dump the immutability constraint to avoid that.

If a data structure is more efficiently implemented using mutation, then I would at some point want to examine the justification for hiding the fact of mutation from the user of that data structure.

Because efficiency isn't the only value of interest.

But if the programmer has to go through complex contortions to accomplish something that is actually very simple under the hood, then I'm fully prepared to dump the immutability constraint to avoid that.

The user of an immutable data structure doesn't have to do anything complicated. Anyway, my main point was addressing your claim that "it's extra work to have to implement two versions (mutable and immutable)". This extra work might not be needed in the future.

Having played around with functional languages, there are just too many cases where I couldn't figure out how to express the algorithm I wanted in a functional way. Not saying it couldn't be done, but that I personally couldn't figure out how to do it.

An example is the server state for an MMORPG, which contains a complex heterogenous graph with lots of complex cross-connections between objects (characters, items, terrain, spells, enchantments, chat channels, raid memberships, etc), and which needs to be updated piecemeal (i.e. you can't process the entire graph through a function - you only want to process the bits that users are interacting with at any given moment).

Doing this using a mutable data structure is trivial - doing it with immutable data structures becomes a computer science project.

The goal of my language isn't to remake the world of programming, but to offer many hundreds of small, incremental improvements over existing popular languages - supporting multiple programming paradigms that are blended together in a harmonious way.

Thus, the kinds of data structures that I am interested are the ones that are familiar to most programmers. As stated in "The Practice of Programming", 90% of data structures in programs are just lists and maps.

The entity system described in by the Bitsquid team seems amenable to building with persistent data structures, since it breaks up the graph with explicit ids:

http://bitsquid.blogspot.com/2014/08/building-data-oriented-entity-system.html

http://bitsquid.blogspot.com/2014/09/building-data-oriented-entity-system.html

http://bitsquid.blogspot.com/2014/10/building-data-oriented-entity-system.html

I wasn't saying that you should just use a functional language. Most existing functional languages don't have good support for mutation, references. I was suggesting that it's worthwhile to do that modeling. In your example of an MMORPG, it's useful for the language to understand the idea of world state as a value, rather than for it to only exist as an emergent property of an object graph being continuously manipulated by an updateWorld procedure.

I'm a fan of functional languages, but Matt's statement "it's just a better modeling of the situation" is overstated. Sometimes it is and sometimes it isn't. Has a lot to do with what kinds of things you are working on, and also what kinds of concurrency you are obliged to manage. For example, functional languages are about the worst tool imaginable for those problems where shared memory concurrency is the high-performance solution. Safe languages (and therefore all functional languages I know about) are simply horrendous at string manipulation.

I've been working on a unicode RegExp library recently in C++. When the time comes to reimplement it in BitC, this code will clearly serve as a torture test. Efficient Unicode support, incidentally, is inherently a torture test for just about any language.

So: functional languages are wonderful things, but let's not eat so much of our own dog food that we end up regurgitating it on the living room rug, eh?

Again, I wasn't trying to argue that any functional language is going to be a better choice than your favorite language. I acknowledged in my follow-up post that most functional languages won't be suitable for the problem domain he was interested in. But I stand by my claim that being able to treat program state consisting of a large graph of objects as a value at any given moment in time is useful. If your language doesn't let you do that, then it's a limitation of your language. I disagree with your assessment that "sometimes it's good and sometimes it's not". It's always good. When balancing the set of things that your functional programming language makes easy vs. the set of things your C-like language make easy, you may find that the latter is a better fit. But then a better language would make the union of those things easy. In the limit, better languages will include the ability to model large clusters of mutating objects as a series of values.

The above is a simplistic presentation of my actual point of view, but I believe it's much closer to the situation than what the "right tool for the job" people seem to think.

Also, to respond to a comment you made in a sister thread: If there were justice in the world, wouldn't 'const' mean 'constant' (does not change) and 'immutable' mean 'cannot be mutated' (readonly)? Thanks, C++ (feel free to point out that C++ borrowed this poor terminology from an earlier language).

Modelling a cell as a stream of values is ridiculous: it loses information (that the cell is a cell) and limits how the implementation can manage it. A lot of effort is expended in Haskell in order to claw back mutable references for efficiency reasons.

There are more ways to tame mutability than going functional. For example, one might not allow them to change at any given moment in time without translating everything into immutable graphs.

I don't necessarily disagree (though I wouldn't call it ridiculous). That certainly doesn't contradict what I'm saying. I'm not advocating functional programming (everything is a function), so much as value-oriented programming. And mutable values aren't values at all.

And if your programming paradigm turns out to be a hit, I have no doubt it can be made even better through incorporation into a value-oriented style. ;)

Actually, Glitch heavily relies on a distinction between values and objects for efficiency reasons. Values like numbers, points, and matrices are anonymous and immutable, and they change by getting replaced with other values. You don't update the X coordinate of a point, you replace the point with a new point.

Objects have identity and state (the mutable kind). A person's age can change over time, but the person is still the same person!

The distinction is huge when building traces: a field changing from one object to another triggers expensive graph recomputations while a point changing to another point can be handled much more cheaply (we don't even have to re-verify the type in a dynamically typed language!). It also turns out that cells that refer to values (e.g. a body's position) change much more often than cells that refer to objects (e.g. what body another body is touching), so having a separate fast path to deal with value changes makes a lot of sense.

But my point is that objects (that are named, can be aliased, and have state) and values (that are anonymous and propagate via copying) are quite different and we usually need both (at least in a reactive language). And indeed, in language design, representing everything as values (say using GUIDs to encode object-like values) is bound to obscure this very golden distinction. Likewise, everything-is-an-object design philosophies break for the same reason (and we haven't even gotten into boxing yet).

Objects have identity and state (the mutable kind). A person's age can change over time, but the person is still the same person!

Agreed! However, the person isn't inside the computer, are they? You've never actually got the person, but rather a model of the person.

An immutable person value represents a snapshot of some perception of a person. A mutable object ties that snapshot up with some policy about the succession of values over time. Recovering a snapshot from an identity in motion can be difficult unless snapshotting is a fundamental feature of the identity's encoding. Further, you often want to snapshot multiple objects at once, so you also need an identity for the context or a custom timeline as well.

It seems to me that the snapshots and succession strategies are the two primitive components that make up an ideal mutable object.

Again, that is what I'm railing against: we have all these ad hoc ways of clawing back real mutation (via snapshots and perceptions or whatever) when we already had mutation in the first place! Re-apportioning identity when its lost is quite difficult, almost impossible, and you have to crazy things like tree diffs to know what fields have changed...when for an object you know exactly what changes because you can see a new value replacing an old one in a field. I know very directly that the person's age changed if I just setup some observers (which happens transparently in Glitch).

Glitch uses versioned memory underneath its cells, you could think of these as snapshots; and they do enable time travel and changing the past... We recreate reproducible paths to re-access those existing objects when they are allocated during replay. All of those techniques are very common in functional approximations of objects, but for Glitch they are just implementation details hidden away from programmers. The abstraction is intact, and it is easy to derive whatever functional machinery we need for it. Contrast to the approach of having clean pure abstractions, and needing to instead claw back impure machinery!

I'm not usually in favor of clawing back, either. You don't have to claw back mutation or references. I believe Haskell uses both approaches: sometimes mutation is encoded functionally and then the compiler heroically attempts to recover mutation. Sometimes this is an improvement over just writing things imperatively to begin with because extra cases are converted to mutation automatically. Other times, though, mutation is encoded in a monad directly and the implementation can just output the imperative code. I'm generally not a fan of heroic optimizations and so I tend to favor this latter approach (though not necessarily Haskell's exact approach).

Modeling mutation explicitly has many advantages for reasoning. State is a common source of bugs and hidden dependencies. What you describe as "clawing back real mutation", I might describe instead as "taming mutation".

It is true that explicit mutation involves models of location, space, time, and identity that are redundant with the machine's model. But the ability to reason about these as part of the model, independent of the machine, is convenient. And we can more explicitly design such models with properties we want, such as portability, persistence, security, scalability. And the performance efficiency, though rarely optimal due to the extra layer of computation, is frequently acceptable and in many applications is not the bottleneck or hot spot.

But my point is that objects (that are named, can be aliased, and have state) and values (that are anonymous and propagate via copying) are quite different and we usually need both (at least in a reactive language)

Objects can be modeled quite well as identities (opaque references which are values) and associated properties (also values, some of which vary with time). This has been a fruitful approach for me in my language and fits in nicely with reactive semantics.

Also, as Brandon just said, the "object" in the program is not an "object" living in the world. So I don't see a good philosophical reason to consider objects as non-values.

I also don't buy that there's any reason for this approach to fail for efficiency reasons. You can always introduce distinctions between different kinds of values and support fast paths for certain operations acting on them. You'll still encounter cases where you want to be able to specify some natural thing that might be somewhat slow for the compiler to implement but that saves lots of hassle for the programmer. Like saving and restoring all associated state as a value, comparing two such states, etc. We shouldn't deny such expressions just because they're slow (though awkward to express can be fine).

But objects are naturally represented by the computer in memory...it is values that require special handling (copy copy copy). Any value can masquerade as an object with a name, sure, but this is like using a name tag to stand in for a person. Ya, you can do that, but its a poor stand in, and prevents efficient implementations as those identities stand outside of the compiler and run-time.

The big payoff between object and value distinctions are there different semantics. Objects tend to favor nominal constructs (classes, traits), while values tend to favor structural ones (type classes, structural type). If you deny values with names, you probably deny types with names also.

I didn't follow this, exactly. The claim that anything I'm suggesting prevents efficient implementation isn't correct. In the case where objects are used in the same way, the same implementation can be used.

In my world view, values don't "have" names. Names refer to values. Same for types, which are particular kinds of value. Identities are not the same as names. They are abstract references and can be considered values.

In my world view, names and identities are basically the same. A name identifies things statically, while an identity identifies things dynamically. Then OOP is a programming paradigm based on manipulating names statically and dynamically (and why OOP must basically be imperative) vs. FP which a paradigm oriented around manipulating nameless values.

Let's put this way: an object is not an object if it lacks an identity; it would no longer be a thing we could reason about. While you could conceivably eliminate the static names that refer to it and classify it, you couldn't really get rid of the object's dynamic name, its identity so to speak.

I'm not sure why I emphasized 'names are not identities'. My viewpoint is very similar to yours expressed in the first paragraph above. Names will generally be chosen by the user (not to be wasted on the compiler), while identities are introduced by the run-time, but they're similar ideas.

I'm not trying to eliminate object identities. I'm giving them a central role. One reason I insist that everything be values is that it allows formal reasoning. You presumably reason about objects as values at meta-level when you're considering the correctness of your programs, but it's difficult to reason about change when the context of your expressions is changing. Better to consider expressions of values that never change. Change can be introduced by explicit dependence on time.

Perhaps we agree more than we disagree, and just differ in what problems we are trying to solve. I admit that values allow formal reasoning, but I believe they do this by rejecting names. Instead, a value is distinguished solely by its structure. That is the power of math: we can know things for sure.

Names on the other hand are ascribed arbitrary meanings. They allow us to think and talk about ("communicate") things that we aren't entirely certain about, or we have no formal understanding about. This sounds scary and often results in incorrect results, but it is also incredibly useful; after all we evolved our capability for language long before we developed our capability for math. Basically, we are forced to live in a world that we barely understand, and names are how we deal with that.

My belief is that names are worthy in looking at in their own right, without the enforced-truth of values. Basically, those who study OOP study names, while those who study FP study values.

As far as language design goes, it is definitely reasonable to consider names without considering how they can be encoded as values. Change is something that just happens: this field went from 0 to 1, now notify everyone who read that field of that change. We are not really reasoning about or understanding the change, we are just dealing with it. Now, I also admit that we could reason about change as values (as they do in FRP with an explicit time dependency); this is probably useful if you are trying to understand change more formally, but I don't think it helps very much in "getting things done." Or to put it another way: I believe pure FP has value, just not the value that I'm concerned with.

See the differing goals of linguistics and mathematics. I once took a linguistic pragmatics course that attempted to bridge the two, it didn't go well.

Most results in graph theory can be understood as involving names. Let V be a set of vertices. What is a vertex? In graph theory, it's just a name -- an abstract element in some set with no other properties. A graph coloring is an assignment of a color to each vertex. When you have such a coloring, it is sensible to regard the associated color as a field of each vertex. Note that I'm not talking about encoding names as value, but just regarding them as values.

Now, I also admit that we could reason about change as values (as they do in FRP with an explicit time dependency); this is probably useful if you are trying to understand change more formally, but I don't think it helps very much in "getting things done."

Modeling change explicitly is really orthogonal to how names and objects are modeled, but I don't agree with this either. There are succinct means of expression enabled by a language aware of how to interpret large composites as evolving values.

Good point about graph theory. It is also the math that seems to come up the most when studying OO languages :) I'm not sure I would see the coloring as a field...it is an immutable property of a vertex (or what we might call a type). The connections between vertices might be field like, but these are more properties of the graph rather than properties of the vertex.

"Detecting" change is easy with mutability: you can observe when a field goes from one value to another. In a functional world, known that something has changed is actually hard: you have to compare two values (e.g. v1 and v2) to know what sub-values are different. Tree diffing in React annoys me to no end on this point. And ya, I am getting into efficiency at this point, but I care about practical implementations. What you want to accomplish, modelling change, is quite different, I think.

Please forgive this slightly off topic rant in support of React's model:

As a user of React, you genuinely don't care about diffs. It's not part of the programming model at all. If the React engine blew away the entire DOM every frame and rebuilt it from scratch, it wouldn't behave any differently than it does now (other than perf). You're not reifying the diff because you don't care about the diff, you care about the current view.

The identities/names of React components are paths through the tree. If you have the root element's second child's first child, you have something like ".1.0" as a component ID, to which you can add an arbitrary key, so that you can match up components where the relative element order isn't sufficient: ".1.$user1234" for example.

Assigning names to components by position in parent is a convenience because giving every component an explicit name is annoying and verbose in code. However, if you had a proper UI design tool, there's no reason you couldn't gensym a name for each component at the time it's created in the designer and insist that all dynamically created components get unique names as well.

The only place that something "diff" -like occurs in the mental model behavior of React is that component local state has a lifetime related to presence in the DOM. When a new ID is introduced to the DOM in a given frame, getInitialState is called. When that ID leaves the the DOM in a later frame, the current state is discarded. This is a pretty reasonable default. If you want component-local state to live beyond your component's presence in the DOM, you need to make it global state and then manually manage it's lifetime. That's what you do anyway when you write OOP style GUI code. Component libraries with addChild and removeChild methods are akin to manual memory management!

Diff works, I get it. It's just weird and indirect way of going about it.

YinYang uses paths names to basically re-access mutable state, using some of the same techniques as React. However, since we control the IDE, we simply use memoized lexical token identities to achieve this (and just prepend them into a path on method call, loop iterations also have a unique reproducible key), so it is completely transparent from the user.

Diff works, I get it. It's just weird and indirect way of going about it.

I agree with you. Both that it works, and that it's weird to diff pure data structures to compute updates to imperative ones.

My suspicion is that if we understood how paths (both absolute and relative) worked a bit better, then we get rid of the diffing business. Right now, I'm looking at Philippa Gardner, Gian Ntzik and Adam Wright's Local Reasoning for the POSIX File System, which formalizes paths in separation logic, to see if there's a subset that might be encodable in a type system.

You can compute the diffs directly. Like with React you define your UI as an impure(!) function of your domain model. It's impure since a lot of widgets have encapsulated state, so identity matters. You need a diffed version of all of your primitives. For a map function on lists you also have a version that works on list differences so that given a difference in the input list you can compute a difference in the output list. If your diffs are minimal then you automatically preserve the internal state of widgets that are not affected by the update. This works by plain old object identity; no paths or type systems needed.

My biggest issue with this whole line of discussion is that the average programmer wouldn't be able to understand any of it.

My self-imposed rule for the project I'm working on is that "if I can't figure out how to make it both fast and easy to understand, then the feature doesn't go in."

Well, you can't push the envelope without pushing the envelope.

Not trying to push the envelope. Just trying to make read-only and immutable values easier to use.

I think you're underestimating the average programmer - this discussion (for once) isn't that difficult, at least not hear at the leaf.

However, that is also irrelevant to the average programmer. What's relevant to him or her is how easy a feature is to understand and use, not how simple or difficult the design rationale for the feature is.

More important is to reject features that the experts don't understand.

is to reject features that experts (and even maybe gadflies like me) understand, but know to be wrong/evil/bad/backwards/hateful.

I think that the values vs names discussion is only alien to the average programmer because the most popular languages of today muddle the distinction so badly. However, understanding the distinction seems to be a sort of intelligence boosting understanding multiplier.

Being part of the Clojure community, I've watched lots of folks suddenly "get" lots of hard ideas once they are reframed in terms of values and identities. Further, I don't think it's really that hard to explain values and identities in the first place. Most programmers already understand the concept of a database auto-number ID and the costs/benefits that come with one, so you can draw parallels quite easily. There many other successful analogies to make depending on the target audience too.

So, the trick is to find the way to lure people into learning those things. Thank the gods for Clojure for that alone, if nothing else!

Dynamic enforcement has runtime costs, to store whether something is readonly and pervasively check this status before writing, with the bigger penalty being extra cache lines touched if status is located discontiguously somewhere else.

It is all a question of granularity, grasshopper. ☺

Yes, if you have to check every reference at run time things can get pretty expensive. Ironically, the transitive read-only case is cheaper than the fine-grain read-only case. For the transitive case, you can simply map the heap twice: once in mutable form and again in immutable form. If you can get the two mappings to appear at suitable relative positions, then the enforcement implementation can be as simple as OR-ing bits into each pointer as you load it. The check will then be handled by the hardware TLB, which is very good at caching such things. The cost of the OR will generally be hidden on a dynamic-issue machine, and it's "free" in some implementations because you can fuse it into the read and write barrier code that you have to execute in any case.

It is all a question of granularity, grasshopper.

(When Kung Fu first aired on network television, I was exactly the same age as the kid actor playing young Caine addressed thus in the monastery. :-) I wonder whether everyone gets such references. The scene where they discuss const correctness is one of my favorites.)

Using an MMU for clever mapping to get such effects did not occur to me. Several reasons prevent this option in typical contexts I target when coding, such as needing to work in 32-bit deployments mapping all of the address space to physical RAM. More general, though, is inability to control the way my host environment works: I usually write code embedded in something else. So the 64-bit version of my code runs in a hostile world governed by madness instead of organized reason. (The phrase infinite clown fight comes to mind.) Style favoring post-apocalyptic survivalism works better under chaos. But the tactic you describe sounds really neat.

Yes, if you have to check every reference at run time things can get pretty expensive.

I'd avoid checking every reference, favoring a sample-oriented approach at boundaries, especially when there's responsibilty transfer across an interface. A method to implement a write operation checks an argument, then notices a lvalue to be written is readonly and fails hard. Dynamic checks get amortized across a lot of uses without checks. When a value gets passed along farther than a dev's attention span can follow, it's time for another check. If source code goes through a rewrite pass adding or tuning debug and correctness checks, frequency of checks can vary depending on dev desperation when debugging.

The "readonly" notion means I can't modify it. The "immutable" notion means nobody can modify it.

I find a temperature metaphor less confusing, and harder to get wrong or backwards. Cold means quiescent (readonly), while hot means active (mutable). Frozen means no one can modify. Temp-related verbs, nouns, and adjectives can emphasize nuance in detail without being hard to parse. Ice is awkwardly both noun and verb, but I like to ice as meaning to freeze; thus to ice and to thaw are opposites with respect to change in status. You can hold a cold ref, denying local write, without the target being frozen (no one can modify). It's hard to get the distinction backwards.

wonder whether everyone gets [Kung Fu] references.

Probably not. Sigh. While a professor I had to give up using movie references entirely.

Your comment about 32-bit is well taken. I confess that I don't think much about 32-bit these days. Because it (finally) provides low-level concurrency coordination features that we can compile for, ARMv8 is being taken up rapidly. It incidentally provides 64-bit, so the migration is finally underway in the embedded world. Yes, I'm aware that 32-bit won't die soon or quietly.

For statically typed languages, I think immutability can simply be typed and no magic is needed. I haven't thought the issue through for dynamically typed languages.

Cold means quiescent (readonly), while hot means active (mutable). Frozen means no one can modify... You can hold a cold ref, denying local write, without the target being frozen (no one can modify).

I also like that metaphor, particularly because it admits "thaw" (as you mention), and there are concurrency idioms where you need to be able to go back and forth. The one caution I'd note in your example is that there is a difference between "cold ref" and "ref to cold 'a". Which seems to be confusing no matter what the syntax is.

This "cold ref" vs "ref to cold" issue is surprisingly messy if your language has an explicit unboxing operation and also has reference types. The problem is that the definition of a reference type has no syntactic place to say "ref to hot/cold stuff", so when you unbox it you are left with a missing mutability component in the type of the unboxed result. In BitC, I may end up deciding that unions and structures are all value types for this reason, though I can't say that I like the resulting "feel".

I'm familiar with the distinction between 'readonly' and 'immutable' - one of the best examples of this is the JodaTime library for Java, in which for every type (Interval, Date, etc) there is both a mutable and immutable type, and both derive from a 'readable' base type which has strictly weaker guarantees (you can't change it, but someone else might.) D and Rust also deal with this in similar ways.

I haven't tackled immutability just yet since it requires much stronger guarantees from the compiler, whereas readonly is relatively straightforward by comparison.

An open question about transitive immutability is whether it extends 'all the way down' or whether it is possible for mutation to be used as an internal implementation detail at some level. A frequent pattern in C++ is a a type that appears to be immutable to the outside world - no method call can ever disprove this - yet uses mutation internally for things like caching and reference counting.

However, if you were to place such an object in read-only memory, where the immutability contract is now enforced by the hardware, the object would no longer be able to function.

In some ways I conceive of transitive immutability as being sort of like HTML shadow DOM, where you have some walled-off section of the graph that is inaccessible, but nodes lower down can come out of the shadow and be treated like normal nodes.

I'd also like to say that the issues you bring up are the right issues to be thinking about (for my purposes anyway).

Immutability is surprisingly easy. At any initializer let imm = producer() in ..., where producer() is escape-free, there is an instant where the reference being returned is the sole extant reference in the universe. At that moment you don't need to worry about who else might hold it, so you can "downgrade" it to immutable. Once you have an immutable reference or object, the remaining requirement is that ".", and "[]" (the de-compositing operators) produce an immutable result when operating on an immutable thing on the left. If you apply the same rule to "^" (reference chasing) you get deep immutability.

Your question about "all the way down" is very much on target. Simple deep immutability is occasionally helpful, but mainly in contexts where you are going to do copy-on-write or you have some large reference dataset that is accessed concurrently and you'd like to eliminate concurrency and consistency overheads.

I gave an example earlier of an immutable list of mutable objects. If you will, the CONS cells are immutable but the objects referenced by the CAR field are not. This is a simple example of a partially mutable structure. The reason it's potentially interesting is that you can induct on list length of an immutable list, and so (e.g.) you can reason about termination in some cases.

One could readily imagine more complex data structures - say, an RB-tree - in which you'd like this kind of "mixed-mode mutability" as well. So an immutable RB-tree of mutable elements. Assuming you have some way to annotate which parts are which, you can apply the same intuition I gave just above, so you can to a bunch of construction and downgrade to mixed-mode immutable when the non-escaping producer() returns.

So now we're left with labeling which parts become immutable, which brings us back to my comment earlier that mutability probably wants to be parametric. In the RB-tree case, you annotate all of the node references (and the overall container) with one mutability type variable - the same one for all of them - and you either annotate the content references as mutable, or use a distinct type variable.

At which point you may decide that polymorphism over mutability helps reduce the library duplication burden, but I haven't gotten that far in BitC yet.

IMO this is another example where it's better to worry about semantics first. You should be able to just write:

var x = BigGraph
while ...
    params = computeInParallel(x)
    x.merge(params)

The function computeInParallel should take a BigGraph as a value. Now, this code snippet clearly specifies the desired value. It's also clear that x can be updated in-place except for any subvalues of x that are closed over by the result returned from computeInParallel (this could be monadic or figured out with linear types like you suggested). The point is that the remaining issue of ensuring that computeInParallel doesn't do too much copying is an implementation detail. Sure, it could have critical impact on performance, but this is still a big improvement over a situation where errors in immutability annotations can lead to computing the wrong value.

Building on your example, the goal would be to know that no concurrency guards are required on BigGraph because it is deeply immutable. How do we know that?

In the original problem, computeInParallel does not alter BigGraph at all, but copying is not merely an implementation detail when operating at scale.

I'm willing to be educated, but in I think that the "mutate minimization" story doesn't work for the kinds of problems I'm thinking about.

The mutability annotations I'm contemplating aren't just labeled. They're enforced. They therefore aren't a source of computational error.

Building on your example, the goal would be to know that no concurrency guards are required on BigGraph because it is deeply immutable. How do we know that?

We know that, because BigGraph is treated as a value passed to computeInParallel. Note: A value in the lingo I'm using here is a deeply immutable value in the lingo you're using.

I understood that in the original problem computeInParallel does not modify BigGraph. It cannot in my example simply because BigGraph is a value. The complicating issue is what should happen if computeInParallel attempts to close over some sub-value of the BigGraph. In my proposed scheme, any such attempt would be implemented by copying out the sub-value from BigGraph into params so that there can be a single full BigGraph in memory somewhere being updated. (Again, values don't change, so the returned value of computeInParallel isn't allowed to embed references to a piece of memory that is changing).

My previous understanding of your proposed scheme is that you were going to attempt to forbid such references by some kind of annotations, but I think you intended that you can try to detect that there do not exist references back from the immutable object when it is thawed. So I agree, there probably aren't correctness issues with either approach.

I still think my approach is preferable because the semantics are very simple. If you're thinking about escape analysis or locks, you're in the weeds.

I agree with the value semantics approach, arguments passed by read-only reference. The assumption is that we wait for all parallel workers to finish before mutating. But as the workers are separate threads/processes from the thread/process which still has access to the mutable reference, how do we enforce this does not mutate whilst the workers are still running?

The code snippet above is a single thread of computation. Each step completes before going to the next. The fact that computeInParallel is computed in parallel is an implementation detail (does not affect the semantics). I would avoid defining the semantics of things like this in terms of threads whenever possible.

Surely it does affect the semantics? We can only ensure the parallel tasks have completed by waiting inside compute in parallel. The interface definition of compute in parallel does not enforce this, we rely on the implementation to be well behaved.

I think you're basically having the same discussion with Jules and with me. When I say it doesn't affect the semantics, I mean it doesn't affect the value semantics. Obviously it affects operational semantics. The code above doesn't spell out very much, but I'm imagining that computeInParallel calls a library function or built-in that launches a safe parallel traversal of the graph. Maybe it's map-reduce. The point is that the value semantics are specified deterministically.

IMO if you want a concurrent thread / shared memory model, you should have to specify it explicitly (and opt-in which memory is shared with those places). It's really a terrible default.

Yes it seems like the same conversation. I guess I am wondering if something can be done to enforce the operational semantics. What I like about the capability model is that the linear types seem to express the constraints in the type system, and hence would include the appropriate guarantees in the type signature of the function (and hence in the interface definition).

Yes, I think some low level mechanisms for reasoning about concurrent threads operating on shared memory are a good idea. As an abstraction for specifying high level semantics, they're typically terrible, but the ability to roll your own high performance parallelism idioms with some degree of guarantee seems like a good idea.

I think the heart of the problem is going back and forth between immutable and mutable several times in sequence. None of the various (good) points that various people have made here appear to address this.

I think you're over-complicating things. The kind of straightforward code I wrote in the snippet above could produce the code that you want out-of-the-box. Procedural code is already linear. You don't need to introduce fancy machinery for this problem.

The only thing slightly subtle about this is that you may want computeInParallel to be annotated to indicate that it cannot leak any references back to the graph in its return value. That way the code generator in the main snippet can look at the call to computeInParallel and decide that it doesn't need to copy the graph. I would expect this annotation to be automatically inferred by the compiler, but maybe you'd want to allow it to be specified manually for purposes of separate compilation.

That is less expressive than I described below though. It's actually fine if references escape, the important point is that only the mutator can read them when you're in the mutate phase. This is more general than what you described, which may come in handy sometimes. Suppose each vertex in the graph is represented as an array of pointers to its successors, and suppose computeInParallel returns a list of pairs of references to vertices (vertex1,vertex2) which represent edges to be added to the graph. vertex1 and vertex2 point into the graph, and they escape computeInParallel. Finally the merge operation adds those vertices to the graph by doing vertex1.successors.append(vertex2). This is all perfectly safe since we either have 1 mutator or multiple readers, but not both at the same time.

Additionally, an unbounded amount of copying or not based on some inference system doesn't sound too good in practice. If a program grinds to a halt because it's copying several gigabytes of graph every iteration that's effectively a correctness issue too. If performance matters (which it does if you are using parallelism in the first place), then it's usually best to have predictable performance, so you want to be explicit about copying IMO.

You picked references to vertices as the value being captured. What if you had picked a mutable property of a vertex and closed over a reference to it? Then you'd have a bug (computeInParallel should be able to assume it's dealing with an immutable value and close over subvalues whenever desired).

The reason that your example works is that references to vertex objects are persistent over the lifetime of the mutating BigGraph object. This is a problem that comes up everywhere and is IMO one of the big things that functional languages don't solve properly. But once you model this correctly this the example goes back to working simply without big changes.

Also, I agree with you that there are hard constraints on operational semantics. I just prefer to keep those constraints orthogonal to value semantics because I think it's a simplifying factorization.

I don't understand what the problem is that you are describing. Can you elaborate on that?

Do you mean a reference to the interior of another object? Do you mean that vertex consists of the array of successors and for example an int weight, and you hold a reference to that int? Interior references do raise problems wrt memory management, but this seems like an orthogonal issue?

I agree that it's good to factor performance and value correctness. You can do this without implicit copying by making BigGraph not implicitly copyable.

I just mean modeling references. You want the ability to treat a graph structure as a value, but also stability of references. If you model references as pointers to memory, you lose the ability to treat graph structures as values. If you model references as natural number indices, you lose stability as indices shift around.

You can do this without implicit copying by making BigGraph not implicitly copyable.

Agree.

I see. My solution does allow you to treat the graph as a value though, at least for the duration of a read phase. You could make it so that you can treat it as a value forever, but you lose other properties then: either you lose expressiveness (the ability to have references into the graph) or you lose performance (you perform a real copy for computeInParallel). For the example I gave neither of those would be acceptable. You want references into the graph in order to mutate the successors of the vertices returned by computeInParallel, and making a copy of the graph wouldn't work either because then those references would be pointing into the copy and the point is to mutate the original graph. I think it's best to only restrict expressiveness by the minimum amount required to prevent read/write and write/write conflicts. If you want to further restrict the behavior you can always do so by other means. E.g. in my system if you want to make a value permanently immutable, you could add an additional capability ImmutablePhase[R] with a function to transform MutablePhase[R] -> ImmutablePhase[R] but not the other way around. ImmutablePhase[R] would allow you to read but not write region R. So once you converted your mutation capability into an immutable capability there is no way back, so you can treat it as a true value from then on.

I think the references should be modeled separately from the properties associated to them. The references are pure (immutable) values and you can hold them, but the various mutable properties associated to the reference depend on which version of the graph you're talking about. The computeInParallel function can return references to vertices, as those are logically values. The simplifying aspect of this problem is that we never make a copy of the graph (it's a requirement that we don't!) so we can implement references as pointers to objects and know that any property access can be implemented by pointer dereference (as there's only one graph around). It's a little more complicated to get this right in general.

Can you give an example of what you mean in general? Do you mean notions of reference that aren't pointers? Like iterators, or if you represent an array of structs as a struct of arrays and you have a reference to one particular logical struct? What would that change wrt concurrency?

Semantically, a reference is just a name. There are properties associated to that reference, but they depend on the context. When you have more than one set of such properties associated to a reference (in different contexts), the naive pointer-to-struct-of-properties implementation doesn't work. You have to have another level of indirection or identify specific places where you fix-up pointers as copies are made.

For an example of the kind of thing I'd like to support: keep a copy of the graph before you mutate it and then report a diff at the end telling which vertices were added and removed and of the remaining vertices, which properties changed.

Of course you don't want to pay for these features if you don't use them. The "one version of this object" needs to be a fast path.

The only thing slightly subtle about this is that you may want computeInParallel to be annotated to indicate that it cannot leak any references back to the graph in its return value.

That's actually not enough. You also need to ensure that no references to the graph leak anywhere else.

The inference suggestion is interesting. I hadn't considered the possibility of inferring escape freedom automatically. If you did, I think what you would want to infer was uniqueness of the return value rather than immutability. One doesn't necessarily imply the other.

You also need to ensure that no references to the graph leak anywhere else.

You may need to check for that. My functions only do what their type signatures say they do. :)

I think I agree with you on uniqueness, if I follow what you mean. The way I look at it is that computeInParallel semantically takes an honest value, so we have to consider what restrictions on the implementation allow the same in-place value to be passed in. The only obstruction I see is that it can't return (or leak through other channels) any subvalue of the graph without making a fresh copy of it. (And implicit obstructions, like that computeInParallel has no way to mutate the graph itself).

If you force the immutable to mutable conversion to require a copy operation, then if you discard the immutable version afterwards, you can optimise the copy to a move. If you still access the immutable version afterwards the copy would really happen, and its still safe.

Having thought about this a bit more, I can see that it requires some kind of write lock. So each worker that needs the base graph to be immutable must lock the base graph so no merges happen whilst its working. Does it need to wait for all running workers to finish before doing a merge?

There is a problem though - this may not be worth it. For example in a UCT (upper-confidence-bound tree) the information added during the merge is so influential, that any work-in-progress using the previous version of the tree is effectively useless. In other words, working in parallel has no advantage. I hesitate to state this is a general property, but I wonder that if the write would change the output of the running parallel workers so much that the graph must be static, is the worker's output still useful after the merge?

If it is then perhaps only consistency is required, IE locking can be per node, and graph updates can be done link at a time in a way that preserves consistency, avoiding the need to make the whole thing immutable? For example marking each link with a version number (and a versioned delete mark) and the algorithm ignores all links with a version higher than the value then the worker is started.

Is there a graph algorithm that requires static input and post merge-back where parallel workers have been proved to improve performance (where performance is not just running more computations,but getting to the answer in less time than a sequential algorithm)?

Having thought about this a bit more, I can see that it requires some kind of write lock. So each worker that needs the base graph to be immutable must lock the base graph so no merges happen whilst its working. Does it need to wait for all running workers to finish before doing a merge?

That's getting at the problem. Typically, the merge process is single threaded. The problem here is that if even one thread needs to be able to take a write lock, then all other threads need to take read locks, and the desired efficiency is defeated. This wants some form of argument about phase separation via some variant on linearity.

What about the graph versioning approach?

The original problem statement was that we don't have the space to copy the graph.

The graph versioning idea is interesting, and I want to give it some thought, but note that I'm NOT assuming an acyclic graph. Versioning approaches are certainly doable in cyclic graphs, but they are a good bit harder and entail more space overhead.

The idea was no copying. One graph with atomic operations to deprecate or add a link. Each link has a valid from version, and a valid to version. A worker might start with version 1, so it would see all links with valid from <= 1 and valid to > 1. The worker would create new links with valid-from = version + 1, and valid to = infinity. It would delete links by setting valid-to = version + 1.

This captures the generational aspect, and only requires atomic writes not locking (assuming updating valid-to, and inserting a new link in a node is an atomic operation). I don't see acyclic or cyclic making a difference. If the problem is not enough space for successive generations, then there is a problem, but this seems different from the space problem per worker (because the merge happens incrementally you would not add two copies of the same link for generation + 1).

Put each mutable location in a region. For this example all the mutable locations of the graph are in the same region R. Now we need to make sure that either one thread can mutate locations in the region, or multiple threads can read from the region. So you have a linear capability MutatePhase[R] and a capability ReadPhase[R], and you have the functions mutateToRead : MutatePhase[R] -> ReadPhase[R] and readToMutate : ReadPhase[R] -> MutatePhase[R]. Now we can control whether we are in the read phase or mutate phase, but it still doesn't allow us to read from multiple threads (remember ReadPhase[R] is linear). So we introduce two additional functinos splitRead : (n:Int) -> ReadPhase[R] -> Vec[n, Reader[n,R]], and combineReaders : (n:Int) -> Vec[n, Reader[n,R]] -> ReadPhase[R]. Here Reader[n,R] is linear too. This allows us to split into n readers, but in order to return to the mutate phase we have to give back all n readers. I think you don't even need dependent types if you split the readers recursively.

Define two types Zero and Succ[T]. split : Reader[N,R] -> (Reader[Succ[N],R], Reader[Succ[N],R]) and combine : (Reader[Succ[N],R], Reader[Succ[N],R]) -> Reader[N,R]. Now you don't even need dependent types.

Couldn't you simply do this: you define some construct to open a region for reading, similar to the existing constructs that these kind of languages have. Then this is perfectly safe as far as I can tell:

computeInParallel(workload) = 
   left, right = par computeInParallel(firsthalf(workload)), computeInParallel(secondhalf(workload))
   return combineWork(left,right)

graph = some graph in region R
while condition:
   open region R for reading {
     x = computeInParallel(graph)
   }
   graph.mutateWith(x)

where par e1 e2 computes e1,e2 in parallel (using work stealing for example).

Under the hood this could elaborate to what I described above.

The capabilities above seem safe to me, but the region based approach does not seem to guarantee that graph.mutateWith waits until all workers in computeInParallel have finished. For example we could join all the threads inside computeInParallel, but what if we forget?

Can't forget: par only returns after both computations finished.

How do you ensure par is the only way to launch threads? I guess the assumption was implicit? It's not obvious what restrictions should apply from your code example.

It's fine if there are other ways to launch threads. If you launch a thread by some other method where the thread can outlive the open region R for reading { ... } that just won't let you access region R then. It's the same thing if you try to allocate a closure with a pointer into R and let that escape the block. Languages like Rust already handle that, it's no big deal.

I prefer the guarantees given in the type system by the capability model. This makes the guarantees / requirements explicit in the type signatures, which avoids the need to look at the implementation.

It's just sugar on top of capabilities, where the splitting/combining of capabilities is done implicitly by par.

The key issue here is the linearity. Though it's tricky, because on the one hand you want linearity and on the other hand you're going to clone the pointer to the frozen graph across multiple threads, which clearly violates linearity.

There's an interesting composition here between linearity and escape-free sub-computations that needs to be exploited. I think we're on a good track, but we aren't quite there yet.

This doesn't really have anything to do with capabilities.

I thought these kind of things were called static capabilities. Anyway, what they are called is not so important :)

Though it's tricky, because on the one hand you want linearity and on the other hand you're going to clone the pointer to the frozen graph across multiple threads, which clearly violates linearity.

What's linear here is not the pointer(s), but the "capability"/"proof" to mutate pointers in region R. To be more precise, the operation setPtr : MutatePhase[R] -> Ptr[R,T] -> T -> MutatePhase[R]. To use setPtr we require a capability/proof value MutatePhase[R]. That capability/proof can only be used linearly. They don't need to have a run-time representation; the type MutatePhase[R] is only for type checking purposes. Does that make sense?

So I think we're on the right track here, and maybe we're saying the same thing, but I think it's slightly more subtle than you say.

The linearity part is across phases: we're using it to show that at the phase transition boundaries there are no outstanding references into the graph. Actually, that's too strong. Pointers that get left lying around in deeply read-only form aren't a problem, because they aren't a source of future mutation. We're concerned only with the mutate-enabling references that might wander.

Within each phase, we're not concerned about linearity. We're only concerned about escape freedom. We're saying, in effect, that multiple instances of a linear reference actually don't present a problem, so long as (a) they occur solely within a non-escaping membrane, and (b) no linear "transfer" of the reference occurs before the membrane collapses (while it's "inflated"). That's a more generally useful pattern, BTW.

Note I say "deeply read only" above rather than "deeply immutable". The distinction is important, because "immutable" means "by anybody" where "read only" means "by me". If references wander in such a way that they continue to exist during the mutate phase, it would be a type error for those references to claim to be [deeply] immutable.

We're actually exploiting the linearity here to impose a form of temporal scope, and in doing so we're playing an interesting and subtle game with the notion of "immutable". What the linearity lets us do is establish that no other reference exists through which a mutation might occur while the [deeply] immutable reference exists. That's a subtly different statement than saying that "immutable" means "no mutation can ever occur on the referenced object [graph]."

The linearity part is across phases: we're using it to show that at the phase transition boundaries there are no outstanding references into the graph. Actually, that's too strong. Pointers that get left lying around in deeply read-only form aren't a problem, because they aren't a source of future mutation. We're concerned only with the mutate-enabling references that might wander.

Actually it's the other way around: what you're saying is stronger than what I'm saying. It's not a problem to have pointers lying around that can be mutated *eventually*, they just can't be mutated while in the read phase. For example the computeInParallel may return pointers that the merge step mutates. Since we're back in the mutate stage at the merge step, that's fine.

Within each phase, we're not concerned about linearity. We're only concerned about escape freedom. We're saying, in effect, that multiple instances of a linear reference actually don't present a problem, so long as (a) they occur solely within a non-escaping membrane, and (b) no linear "transfer" of the reference occurs before the membrane collapses (while it's "inflated").

No, that's not what I'm saying. Whether pointers escape or not doesn't matter. What matters is that they can only be mutated in the mutate phase, and only one thread at a time is allowed to hold the mutate capability/proof/token.

In summary: I don't restrict the flow of pointers at all. They can go anywhere they want. What I restrict is the ability to use those pointers. Pointers in a region R can only be mutated by somebody holding the MutatePhase[R] capability.

In fact pointers are a red herring. It doesn't matter that there are pointers. In a language without pointers at all, the problem would be exactly the same. The issue is with mutation, not pointers. We could as well be dealing with a single mutable integer, instead of a graph data structures with pointers inside it. To prevent concurrency problems you need to ensure that either:

1. We're in the read phase, and there may be multiple readers but no writers.
2. We're in the mutate phase, and there can only be a single reader/writer.