Mutable Objects

Looking at the mess Rust has created with its handling of mutability, and also the confusion l-values and r-values cause in C/C++ I think a simpler model is needed for mutability. I also think that mutability needs to be part of the type signature not a separate annotation.

I think the problem comes from a failure to distinguish between a value and a location in the type system. A value is something like a number 1, 2, 3, or a particular string like "Hello World". It cannot change, values are by definition immutable. References to values do not make sense, as we should simply pass the value (as it is immutable, there is no concept of identity with values a '1' is a '1' there is no concept of 'this one' or 'that one'). Variables stand for unknown values, therefore are also immutable, like for example in "2x = 6". Once we know 'x' has the value '3' it always stands for '3' in that scope. All values and variables are by nature r-values (and not l-values) so this simplifies things considerably. We write the type of an integer value or variable as "Int" for example.

So what about mutability? Well values and variables are not mutable, how do you change something? You need a container (or a location in computer terms). You can only write to something that has a location (is an l-value in 'C/C++' terms. A container is something like an array, that has slots the contain values, and the values in the slots can be changed. As a parametric type we might write "Array[Int]", Of course an array has length, so we want a simple single value container for the common case of something like an integer we can increment. We could write this as a type: "Mut[Int]". This represents a singleton container that can have an 'Int' value put in it. Containers are 'l-values' they have an address. The important point is that the container itself is a value that can be assigned to a variable, it is just the contents that can change.

In this way the semantics are kept clean, and we don't need concepts like l-values and r-values, and nor do we have the problems Rust has with closures, where it does not know whether to reference or copy an object. So if value assignment is 'let' we can assign a value to a variable that cannot change, or another type of object like a single mutable location.

let y = 3 // value assignment, y is immutable, 3 has type Int, 'y' has type Int
let x = Mut(3) // value assignment x is a mutable container that initially has the value 3 in it. x has type Mut[Int]
x = 2 // the contents of the container called 'x' are changed to '2'. This is syntactic sugar for x.assign(2), which would have a type like: (=) : Mut[X] -> X -> Mut[X].

This removes the need to have any kind of special annotation for mutability or references, removes the need to understand l-values and r-values.

Finally we need references to containers so that the same mutable value can be shared with different program fragments. References can be Read Only, Write Only, or ReadWrite. we can have:

let x = RORef(Mut(3)) // x is a readonly reference to a container that has an int of 3 in it.
let y = WORef(Mut(3)) // y is a writeonly reference to a container that initially contains 3.
let z = RWRef(Mut(3)) // a reference that can be used for both reading and writing.

However the variables themselves are still immutable. A for loop could look like this:

for (let x = Mut(10); x > 0; x--) { ... }

where 'x' would have the type "Mut[Int]".

With GC, I don’t see any need to explicitly type references. We simply remember those primitive types which are always copied when assigned.

Agreed on annotating types with read-only, write-only, and read-write. Per my proposal for concurrency, we’ll also need an annotation for exclusive borrowing and another for stored (transitive) borrows.

I am preferring to keep these annotations concise employing symbols:

() for exclusive borrow (enclose any read/write symbols, or ⊕, ⊖, ⚪)
+ for write-only
- for read-only
nothing for read-write
! for stored (transitive) borrow

Note const (non-reassignment) doesn’t apply to the type but rather to the reference instance construction site. I am contemplating that const will be the default (for both function arguments and other instances). For function arguments these will be written normally but for other instances they will be created with := (optionally ≔) instead of = for reassignment. Reassignable instances will be prepended with var. Obviously for primitive types which are always copied then an instance with writable type must be var. So your example could be written less verbosely:

for (var x = 10; x > 0; x--) { ... }

Rust used symbols for different kinds of references and borrows and they have changed to words like 'Ref' etc because it is more readable.

Rust used symbols for different kinds of references and borrows and they have changed to words like 'Ref' etc because it is more readable.

I argued above we do not need Ref because (at least for my plans), contrary to Rust I am not attempting to create an improved C or C++ with programmer control over all those low-level details. Also Rust requires symbols such as & at the call/instantiation site and I proposed no symbols at the call/instantiation site other than := (optionally ≔). Please enumerate all the symbols Rust used/uses and what they’ve been changed to. Specifics are important. Note I am not yet claiming I disagree, because I need to compare the specifics and think about it.

Afaics, Rust is a blunder thus far, so I am not quite sure if we can cite them as a desirable leader on any design decisions. Remember I had complained to them about the need for the noisy & at the call sites.

Edit: also that last link exemplifies some of the complexity that is involved with having these concepts of references types, value types, and boxed types. I’d rather have the compiler/language deal with those things implicitly. For example, the compiler knows when it needs to use a boxed type because more than one type can be stored there. Unboxed slots in data structures are an optimization. Rust required that complexity because it is tracking borrows in a total order, which IMO is an egregious design blunder.

Ah I see a mention that ~T is the old syntax for what is now Box<T>. I agree that Box<T> is more readable than ~T because ~ has no relationship to Box in my mind. However, I think the symbols I proposed may be more mnemonic:

() cordoned border around access
+ putting more into to something
- taking out something
! for not released, although I realized that Rust named these moves.

I have been arguing that it is precisely because type systems do not differentiate between values and containers, that language semantics get very opaque and complex, for example C/C++ have l-values and r-values, and rust does not know whether to copy or reference variables in a closure.

JavaScript does it differently and treats numbers as values and everything else as references. This causes problems because 'enums' should be values but are treated like objects.

If you want a mutable number in JavaScript you end up using a singleton object like {n:3} or an array like [3]. So even in JavaScript there is some kind of notion of a "reference".

I think whatever we do, it needs to cleanly distinguish between l-values (containers) and r-values (values). It probably also needs to distinguish between boxed and unboxed things.

By distinguishing between objects and references you gain control over ownership, and so you can keep track of whether the caller or callee is responsible for deallocating the memory. As you say, this is probably not necessary with GC, but then I think that a hybrid GC would give the best performance, where you deallocate when things leave scope like C/C++, and only garbage collect those objects that escape their scope.

I think Rust's lifetime annotations are taking things a bit far, but I find the RAII style leads to clean code in C++. There is a clear advantage to having destructors over finalisers.

In any case, it is probably safe to infer things at the value level, as long as all these different kinds of things (that have different semantics) are clearly distinguished at the type level.

A prior quote might be apropos regarding “complexity budget”.

I’m attempting to reread most of the discussion on these Issues threads so I can make my final decisions and get on with creating a language or not.

^{_{P.S. note I have completed 16 weeks of my 24 week TB medication.}}

@keean

@keean wrote:

I think whatever we do, it needs to cleanly distinguish between l-values (containers) and r-values (values).

I repeat for my needs which is to not be mucking around in low-level details in a high-level language, I think JavaScript got this right in that certain primitive types (e.g. Number, also String correct?) are treated as values and the rest as references to a container of the value. So the programmer never needs to declare whether a type is a reference to a value or a value.

rust does not know whether to copy or reference variables in a closure.

Ditto the default behavior I wrote above is what I think I probably want.

JavaScript does it differently and treats numbers as values and everything else as references. This causes problems because 'enums' should be values but are treated like objects.

What is an enum in JavaScript? Afaik, JavaScript has no enum datatype.

If you want a mutable number in JavaScript you end up using a singleton object like {n:3} or an array like [3]. So even in JavaScript there is some kind of notion of a "reference".

What problem do you see with this?

It probably also needs to distinguish between boxed and unboxed things.

The compiler knows which types are (tagged) sum types and thus must be boxed. Why declare it?

In any case, it is probably safe to infer things at the value level, as long as all these different kinds of things (that have different semantics) are clearly distinguished at the type level.

Does that mean you are agreeing with me?

As you say, this is probably not necessary with GC, but then I think that a hybrid GC would give the best performance

We are sometimes (some aspects) designing different languages. Maximum performance is not the highest priority goal of a high-level language. Performance can be tuned with a profiler (i.e. typically less than 20% of the code needs tuning and perhaps only 5% needs extreme low-level tuning) and can drop down to low-level languages for maximum performance via FFI if necessary.

Marrying low-level details with a high-level language creates design priorities contention. I do not think such a perfect marriage exists. Programmers want a lower complexity budget and only a smaller portion of the code needs that high complexity focus. Python, JavaScript, and Java comprise the most popular programming language set on earth. C/C++ are still as popular as they are because sometimes we must have low-level control and because those other three (well at least Java and especially JavaScript) screwed up the integer types, which is one of things I want to rectify.

Jeff Walker wrote:

As I really learned C++ and began programming in it, I discovered that C++ is a very large and complex language. Why? Well, there are a number of reasons. One is that it follows the zero overhead principle, basically “What you don’t use, you don’t pay for.” That means every language feature has odd limitations and pitfalls to make sure it can be implemented in a very efficient way. Another is that, due to the focus on low level efficiency, there are no safety checks built into the language. So when you make a subtle mistake, which is easy given all the weird edge cases, the program compiles and silently does the wrong thing in a way that maybe succeeds 99% of the time but crashes horribly the remaining 1%. Finally, the language is designed for maximum power and flexibility; so it lets you do anything, even the things you shouldn’t do. This produces a programming minefield where at any moment one might be blown up by some obscure behaviour of the language. Because of that and because other developers and the standard library make use of every language feature, one must learn the whole language. However, C++ is so big and convoluted, learning it is really hard.

Also I agree with Jeff Walker’s analysis of the fundamental reason TypeScript can not radically paradigm-shift to improve upon on the JavaScript minefield (although I disagree with his opinion that adding static typing is regressive):

The real problem with TypeScript is contained in the statement that it is a “superset of JavaScript.”. That means that all legal JavaScript programs are also legal TypeScript programs. TypeScript doesn’t fix anything in JavaScript beyond some things that were fixed in ECMA Script 5.

I find the RAII style leads to clean code in C++. There is a clear advantage to having destructors over finalisers.

You are correct to imply that we must track borrows for safe use of RAII, because if a reference to the local block instance has been stored somewhere, because otherwise RAII can enable use after destruction.

Agreed it is a loss of brevity, convenience, and safety that GC languages such as JavaScript and Java don’t usually support destructors at block-level (or function level) scopes for instances local to that block.

But by minimally tracking borrowing as a compile-time (not runtime!) reference counting scheme as I have proposed, we could support implicit deterministic destructors for block-level instances (and even bypass the GC for these and use compile-time implicit allocation and deallocation, i.e. no runtime reference counting overhead). Good idea! That would be significant feature advantage over other GC languages!

@shelby3

@shelby3 wrote:

I am preferring to keep these annotations concise employing symbols:

() wrapping for exclusive borrow, else enclose any read/write symbols with shorthand ⊕ or ⊖
+ for write-only
- for read-only
nothing for read-write
! for stored (transitive) borrow

Add ? as an abbreviation for | undefined meaning not set (aka Option or Maybe) as opposed to unavailable (i.e. semantically an exception or error) with | null, which can be transpiled in TypeScript to ?: as type separator only for function argument parameters. This a suffix on the type and the others are prefixed except for ! (and in the order listed for consistency). The ! may be combined with the ? as ⁉️.

Edit: may need to add an annotation for unboxed data structures, or may prefer wrapping with Unboxed< … > than a single symbol annotation, because this is not so verbose, these should be used rarely for explicitly needed binary space compression.

Personally I don't like the hieroglyphics, it certainly makes it hard for occasional users to understand (like all the symbols in PL1, APL or perl). Most people can transfer knowledge about things like references from one language to another if the notation is readable.

We probably disagree. I do not like verbose text (compounded on top of already verbose textual types, we need some contrast). That is one reason I do not like Ceylon. I like symbols for very commonly used syntax, e.g. the -> for inline function definition. I am surprised that as a mathematician you do not like symbols. What I do not like are symbols for every commonly used function, e.g. Scalaz’s symbol soup. Symbols need to be used in moderation, and we are talking about type annotations (which are already too long and textual), not operators in the executable code.

I do not see any other popular languages with read-only, write-only, read-write, and exclusive borrows annotations, so there is nothing to transfer from. Even Ceylon (and others) adopted ? for nullable types.

Also these annotations on type annotations are mostly to be ignored by the eye, because they are a (type attribute) detail and normally the programmers wants to first focused on the named type annotation which varies between type annotations. Since these little (type attribute) details will be repeating (within a small bounded set of choices) on every type that otherwise are varying (within a unbounded set of choices), they are repetitive almost like noise that should be minimized in terms of visual conspicuity so it does not drown out the more prominent relevant information of the type annotation, e.g. ExclusiveBorrow[ReadOnly[Stored[Nullable[Atype]]]] (even if abbreviated Excl[RO[Stor[Null[Atype]]]]) versus ⊖Atype⁉️ or without Unicode (-)Atype!?.

There's a bit of a straw man there, as the type doesn't make sense (you wouldn't have a read-only exclusive borrow, as read only is a reference, and a borrow indicates transfer of ownership, and anything that is referenced must be stored).

The closest type to this would be something like:

Mut[Maybe[TYPE]]

or

type MyType[T]]= Mut[Maybe[T]]
RORef[MyType[TYPE]]

The point is the types are expressing the semantic invariants.

However I see no reason not to allow user defined type operators. So '?' can be an alias for maybe etc.

So we should alow symbols in the type definitions, and it can be left up to the programmer whether to use them or not.

@keean

@keean wrote:

There's a bit of a straw man there, as the type doesn't make sense (you wouldn't have a read-only exclusive borrow, as read only is a reference, and a borrow indicates transfer of ownership, and anything that is referenced must be stored).

Incorrect in my intended context. You’re presuming Rust’s borrowing/ownership model. Please read again my proposal and understand how it differs from Rust.

However I see no reason not to allow user defined type operators. So ? can be an alias for Maybe etc.

So we should allow symbols in the type definitions, and it can be left up to the programmer whether to use them or not.

Disagree. Remember you had also mentioned in the past that for readability consistency, one of the basic tenets of good programming language design is not to unnecessarily have more than one way to write the same thing.

This: ⊖Atype⁉️ makes it hard to understand the nesting, for example is it a reference to a nullable "type", or a nullable reference to a type? You would not only need to memorise what the symbols mean, but there precedence, to know which ones apply first.

@shelby3

This: ⊖Atype:interrobang: makes it hard to understand the nesting, for example is it a reference to a nullable "type", or a nullable reference to a type?

Lol, the use of the kenkoy ⁉️ emoji.

I am thinking there are no unadulterated (i.e. native, low-level manipulable) null references in the language I think I probably want:

@shelby3 wrote:

With GC, I don’t see any need to explicitly type references. We simply remember those primitive types which are always copied when assigned.

@shelby3 wrote:

I argued above we do not need Ref because (at least for my plans), contrary to Rust I am not attempting to create an improved C or C++ with programmer control over all those low-level details.

@shelby reiterated:

I repeat for my needs which is to not be mucking around in low-level details in a high-level language, I think JavaScript got this right in that certain primitive types (e.g. Number, also String correct?) are treated as values and the rest as references to a container of the value. So the programmer never needs to declare whether a type is a reference to a value or a value.

As you presumably know, in JavaScript a “null reference” is distinguished as the value undefined from null value which has the value null.

I suppose Undefinable is another type for which we may want a type annotation.

Excluding memory allocation which is inapplicable in GC, afaics the only utility of null pointers is to: a) differentiate the state of unset (undefined) from unavailable (null); and/or, b) to differentiate an instance shared (between data structures) from no instance. Sometimes we would for efficiency prefer to use for example the negative values a signed integer (i.e. the MSB aka most-significant-bit flag) to differentiate the null unavailable state from available positive integers state without requiring boxing (and perhaps a similar bit flag hack for unboxed nullables for other data types), thus perhaps we want to be able to differentiate the #a and #b cases. In no case though would a Nullable[Undefinable[…]] make sense in GC, so we do not need two transposed orderings of those annotations.

Since we probably need #b even for types that are not nullable, then the double question mark is an incongruent symbol choice.

I am contemplating how we might type the bit flag hacked unboxed nullables? And generally for any data type? It consumes some of the complexity budget though.

Don't forget with GC you often need Weak and Strong references, where a strong reference prevents the referenced object from being garbage collected, whereas with a weak reference the referenced object can be garbage collected, so you must check if it is still there when dereferencing. You can also have levels of weakness determining the memory pressure required to evict the object, to reflect circumstances like "I want to cache this in memory for speed, providing we have spare memory left, but evict as soon as we are running low on memory" vs "I want to hold this in memory for as long as possible, and only evict if we have no other free memory left".

The use of weak references for caches does not work well. Weak references are not needed for breaking cycles if GC is present. The only potentially (but dubious whether) legitimate use for weak reference is for avoiding having to manually undo “put” operations, e.g. removing objects added to a map, list, event/listener list, etc.. I am leaning towards agreeing with David Bruant’s stance that my aforementioned last use case would be encouraging bugs. Also JavaScript has no weak references, so could not support them on a language that compiles to JavaScript unless we implemented our own GC and heap employing ArrayBuffer.

@shelby3

@shelby3

Your proposal is that only mutable things have an address so you can distinguish between objects and values.

No, it is not. Do not restate the hypothesis and then attack your incorrect restatement. I repeat:

I propose the hypothesis that something must have an address to be mutable.

Then:

In any case, my proposal doesn’t need a literal way to indicate an object

I think this is a mistake, constructing objects by hand is painful boilerplate in C/C++

that implies that the generic object literal will have a generic default type such as Object in JavaScript.

Not at all, there are solutions to typed object literals:

html := html{ head{ title{ text{"my document"}}} body{p{ text{"some text"}}}}

Using a Kotlin like constructors, or Go like struct literals.

Vs

html := new html()
head := new head()
html.attachChild(head)
title := new title()
head.attachChild(title)
t1 := new textNode("my document")
title.attachChild(t1)
body := new body()
html.attachChild(body)
p := new p()
body.attachChild(p)
t2 := new textNode("some text")
p.attachChild(t2)

@keean

Your proposal is that only mutable things have an address so you can distinguish between objects and values.

No, it is not. Do not restate the hypothesis and then attack your incorrect restatement. I repeat:

@keean your proposals have changed so many times I can’t keep track of what you are actually proposing at any given whim that you change your mind. Originally you said that immutables should never be pointed to. Please make some coherent posts and stop just blasting noise.

In any case, my proposal doesn’t need a literal way to indicate an object

I think this is a mistake, constructing objects by hand is painful boilerplate in C/C++

What is the problem with constructing an object by calling the constructor?

Html(Body(Div())

Which can be syntax sugared as:

Html
   Body
      Div

So you prefer what?

{ type : Html, children : { type : Body, children : { type : Div } } }

Vs

html := new html()
head := new head()
html.attachChild(head)
title := new title()
head.attachChild(title)
t1 := new textNode("my document")
title.attachChild(t1)
body := new body()
html.attachChild(body)
p := new p()
body.attachChild(p)
t2 := new textNode("some text")
p.attachChild(t2)

There’s no new when using a named constructor. I already told you that. Did you fail to pay attention to that detail I wrote?

The example you wrote above doesn’t factor in that the constructor can attach its children without needing to create the temporary identifier names.

@shelby3

@shelby3

There’s no new when using a named constructor. I already told you that. Did you fail to pay attention to that detail I wrote?

What were you proposing 'new' for then?

@keean your proposals have changed so many times I can’t keep track of what you are actually proposing at any given whim that you change your mind. Originally you said that immutables should never be pointed to. Please make some coherent posts and stop just blasting noise.

Indeed. Let's keep things simple, forget what has gone before.

Hypothesis: All mutable objects must have an address.

Do you agree or disagree?

Refresh

There’s no new when using a named constructor. I already told you that. Did you fail to pay attention to that detail I wrote?

What were you proposing new for then?

I wrote up-thread:

I need the new because I am informing the compiler to make a new l-value from an r-value. Your proposal doesn’t have l-value and r-value. You can’t mix your proposal and my proposal.

I like new because it says make a new l-value. Literals are r-values not l-values.

Note the new is not needed when an l-value is not need from an r-value. So the new will rarely appear in code I think.

P.S. I am going to sleep.

@keean

Pony’s Design Compared

I’m trying to wrap my mind around what @keean and I have discussed in this thread.

I proposed to be explicit about pointers versus values in terms of what is copied on assignment or passing as arguments, so we don’t have the copy-by-sharing situation of Javascript and Java where some primitive types copy the value and other types copy the reference (i.e. the pointer). This also requires being explicit about taking the address of (&) when passing from a l-value to a pointer to that l-value. And requires being explicit with new when needing to form an l-value from an r-value. My proposal has an implicit distinction between l-value and r-value based on context wherein l-values always have an implicit container that is addressable. My proposal enables pointers to (the implicit container for) immutable l-values.

As far as I can surmise, @keean ostensibly proposed to be explicit about the distinction between l-value and r-value; wherein, all r-values are immutable and can’t be addressable. Additionally it seems that @keean doesn’t want to allow immutable l-values? Or he doesn’t want to allow pointers to immutable l-values (but that would be a bifurcation because by definition l-values are addressable)? Apparently @keean seems to think we will gain something from such a design such as some ability to do some compiler optimizations that can’t be done with my proposal, but frankly I can’t see clearly what is the advantage of his proposal. I ask @keean to please clarify or to admit that his proposal is half-baked and not yet fully coherent.

@keean suggested to me in private messaging that to facilitate compiling to Zer0 to Scala or Typescript, that I could adopt their copy-by-sharing design instead. But that doesn’t allow us to control when we want to store a reference or a value.

Pony makes everything a reference and references have types. Apparently a primitive type such as the literal 3 would have a default reference type of val for immutable. So the Pony compiler can presumably optimize whether it copies (and stores) a reference or the value when the reference type is val, iso, or trn (because there’s no conflicting writes by other references which the advantage of trn compared to the non-exclusive write-only I had contemplated in this thread). Pony’s exclusive writable capabilities iso and trn enable data race safety which supplant the guesswork of C’s restrict keyword. I remember that article about why C is a difficult language to optimize pointed out:

^{For example, in C, processing a large amount of data means writing a loop that processes each element sequentially. To run this optimally on a modern CPU, the compiler must first determine that the loop iterations are independent. The C restrict keyword can help here. It guarantees that writes through one pointer do not interfere with reads via another (or if they do, that the programmer is happy for the program to give unexpected results).}

Note Pony averts the complexity of Rust’s lifetimes (which also provides data race safety) by only allowing to recover exclusive writability from within recover lexical blocks. So it’s strictly less flexible than Rust (which already can’t express (c.f. also) all lifetime invariants) in terms of being able maximize opportunities for exclusive writability (because orthogonal recover blocks can’t overlap but orthogonal Rust lifetimes can overlap in complex ways), but Pony is more flexible for algorithms because it doesn’t force a total order on exclusive writability (i.e. it is possible to have ref capability which can be share writability between more than one reference). Pony can achieve this because ref sharing is only allowed within a single Actor, which are always single-threaded. Whereas, Rust presumes reentrancy everywhere, although its guarantees aren’t precisely “thread safety” (reentrancy is a tricky beast!). Rust can thus guarantee against iteration “single-thread reentrancy” invalidation which is really a semantic error (and we’ll never catch all semantic errors with the compiler). Rust’s prevention of “use after free” (at least w.r.t. to memory resources) is only necessary because Rust wants a zero-cost memory resource allocation (stack or heap) instead of tracing GC. Note that exclusive mutability for protecting against iterator invalidation can also be achieved in Pony (by moving the iso or trn reference to the iterator with consume then moving it back after done using the iterator), but I don’t see how Pony could protect against use after free. IOW, Rust is too aggressive on requiring exclusivity of writability, but it is more flexible on expressing that exclusivity. Yet maybe lifetimes are not really useful (at least for memory resources) when they’re automatically managed.

Apparently Pony is @keean’s preferred design once it is fully baked. There’s no concept of l-values and r-values. The compiler figures everything out based on the capabilities of the reference type. Pony thus needs a separate concept of capability of rebinding of identifiers (whereas in my proposal this is accomplished with the mutability of the pointer type for an identifier).

So Pony removes being explicit about when we’re using pointers or values, which certainly seems less noisy and less details for the programmer to juggle. I’m contemplating whether this removes any important low-level coding that the programmer could express?

The main issue seems to be the control over time versus space. In Pony, I can’t tell it that I want exclusive write-only (or immutability), but I want or don’t want it to copy around all the values. For example, I might prefer to reduce space by having an array of pointers to immutable values (wherein I have many references to the elements of the array), even though that would be probably slower when doing operations over most or all of the elements of the array due to the extra indirection and loss of cache locality (elements of the array not being sequential in a cache line or memory page).

So maybe the design we want is Pony’s but with optional extra annotation for reference types to signal to the compiler a preferred (but not guaranteed) choice between time versus space? What do you think @keean? I think I prefer the Pony design (with added optional preference annotations) because I think we can see from that article about the problems with C for parallelism that we should let the compiler have more leeway (and because we probably can’t predict exactly the future optimal hardware for parallelism):

^{Optimizers at this point must fight the C memory layout guarantees. C guarantees that structures with the same prefix can be used interchangeably, and it exposes the offset of structure fields into the language. This means that a compiler is not free to reorder fields or insert padding to improve vectorization (for example, transforming a structure of arrays into an array of structures or vice versa). That's not necessarily a problem for a low-level language, where fine-grained control over data structure layout is a feature, but it does make it harder to make C fast.}

But the tradeoff is that Pony can’t always maximally express exclusivity of writability? Will there will be algorithms that we can’t express optimally in Pony, i.e. where we want force storing a value but we can’t express exclusive writability of that value in Pony (although we can convince our human mind that the code is safe to make that assumption)? These (rare cases?) are where we really need that low-level capability of C. Perhaps we can in some cases recover that capability in Pony simply by manually copying when we want to force the capability to store a value but can’t express the safety of the exclusive writability in Pony. But yet there will be other cases where we want all these writable references to a shared value which we want stored sequentially in memory for the elements of an array, yet we can’t express in Pony that we don’t ever write to those references in a way that is not data race safe. But that also requires the semantic that we always assign to the array element first after creating an instance for the element before sharing the reference to that instance (realize this will also be single-threaded not shared between Actors). So seems what we really need is an annotation that says a reference is only allowed to receive assignments from newly created instances that have not yet been otherwise shared.

So this I do believe we can adapt (with some additional annotations) the Pony model to maximally performant low-level code! Wow! Impressive!

I think we have a C-killer here.

@keean

Optimization of Result Value Temporaries

We’re referring to for example optimization of the result values of the + infix operator function:

a[0] = 8 + 3 + 2 + 4
a[0] = "8" + "32" + "4"

Goals for result values temporaries:

Eliminate unnecessary copying of values.
Eliminate unnecessary execution of any destructors.
Eliminate unnecessary costly allocations and de-allocations on the heap.
Eliminate unnecessary increase in size of the stack.

The issue addressed by goal #‍‍4 is probably not that significant. The issues addressed by goals #‍‍2, are more pronounced for example in C++ because it has destructors, and for #‍‍3 because perhaps (without escape analysis) there’s no highly efficient young generation objects bump-pointer, compacting heap (C++ doesn’t have tracing style GC nor my ALP concept).

All programming languages need to deal with the issue addressed by goal #‍1, because unnecessary copying of the temporary result values significantly reduces performance.

Programming languages that employ pass-by-reference (aka call-by-reference or return-by-reference) as the default, eliminate the unnecessary copying (return-by-copy) to the caller of the result value when the value is stored on the heap. (But that’s not the only potential copying involved that a move constructor might ameliorate for complex data type such as strings per example below…) Such languages also typically have an efficient young generation objects bump-pointer heap with a tracing GC. Whereas, programming languages such as C++ or Rust which attempt to keep result values on the stack when possible for even greater efficiency (aka “zero cost resource allocation abstraction”) have the caller provide the stack space to the called function for storing the result value because the stack space of the called function is deallocated when it returns. I cited this “copy elision” (aka “return value optimization”) up-thread. Yet as we see for the example a[0] = "8" + "32" + "4" at this top of this post, strings can’t be allocated on the stack because they’re dynamically sized. So C++ and Rust are also employing heap allocation for strings.

But as the C++ optimization blog post I had cited up-thread explains, return-by-reference doesn’t eliminate all of the copying in the case of for example strings, because without move semantics then all of these temporary result values have to be copied to the next result value in the chain of the expression (e.g. of + operations). Move semantics can enable “normal geometric reallocation” of (memory for) the part of the string being appended to, instead of copying. IOW in many cases there will be no copying. Also programmable move semantics means the data structure can be designed to optimize operations over moves instead over copies. So for example a string data structure could be built that employs a linked list if that turned out to be more efficient in a particular use case as compared to geometric array resizing.

Thus we have shown that simplistic return-by-reference doesn’t eliminate all copying. Move semantics enables the elimination of more instances of copying. Additionally move semantics addresses the other 3 goals. With move semantics (and some cases requiring exclusive writable aliasing provided by Pony’s reference types or alternatively unboxed values), even the a[0] = 8 + 3 + 2 + 4 example can be optimized as a[0] = ((8 += 3) += 2) += 4 for goal #‍4 (and possibly #‍2 and #‍3 if what is being added have destructors and are allocated on the heap).

So even though with my posited ALP “actor epiphany” near zero-cost resource allocation bump-pointer heap (i.e. ^{_{no tracing, just reset the bump pointer to origin on completion of the Actor function}}) of non-ARC references¹ ameliorates #‍3 and #‍4, the performance could still benefit from move semantics to avoid needless calling destructors (probably a rare case of performance problem though) and combined with Pony’s reference types for knowledge of aliasing invariants to optimize memory consumption although in some cases that memory consumption can be optimized in another way. Note c.f. also Reentrant Actor-like Partitions.

Pony doesn’t have destructors and it has (efficient?) GC heap collection, so presumably they ostensibly didn’t consider the necessity of move semantics for increasing performance. @keean and I pointed out other fundamental design flaws in Pony in the WD-40 issues thread #35 (which @keean accidentally deleted so now is #50).

Therefore I propose that a PL should offer the option for the programmer to write move semantics variants of all functions including constructors.

¹ _{Note I have previously doubted whether we would want to allow use of destructors with non-ARC references in the proposed ALP design, not just because the Actor function could be stalled for considerable and non-deterministic time intervals due to concurrency. This would require recording each destructor for every non-ARC allocation. ARC references also can have non-deterministic lifetimes due to the fact that non-determinism is present in the program in many facets. Seems to me that use of destructors for freeing things such as file handles has to be used with caution by the programmer who is paying attention to for example the blocking functions (i.e. opportunities for non-deterministic preemption) called in his code.}

Note the post I made the Parallelism issues thread #41:

Extending Pony’s Reference Types

I propose to rename and extend Pony’s reference capabilities for Zer0 as follows.

Pony Zer0 Access Shared Aliasing Non-Shared Aliasing

iso
Isolated [r/w] Exclusive (read/write)
(writable) None None

val
Value val Immutable
(non-writable) Read-only Read-only

ref
Reference r/w Read/write
(writable) None Read-write

[r]/w (Exclusive read)/write
(writable) None Write-only

r/[w] Read/(exclusive write)
(writable) None Read-only

[read] Exclusive read-only
(non-writable) None Write-only

box
Box read Read-only
(non-writable) None
Read-only Read/write¹
Read-only

trn
Transition [write] Exclusive write-only
(writable) None Read-only

write Write-only
(writable) None Read/write

tag
Tag id Address-only
Opaque pointer Address-only Address-only

Note exclusive (read and/or write) capability is useful for being consumed (in addition to being consumable for other reasons such as sending between concurrent threads) for supersumption. For example supersuming the union element type (i.e. to add constituent union members, e.g. from Int to Int | String) of a collection. It’s safe to write to the resultant supertype (e.g. Int | String) because no reference can read the consumed source subtype (e.g. Int) that would otherwise be violated by writes (e.g. of String) to the supertype.

The dual subsumption case (i.e. removing constituent union member(s), e.g. from Int | String to Int) is handled (without consumption) by assigning a type with (even non-exclusive) write capability to the subtype with the write capability intact but discarding for the subtype reference any read capability (which would otherwise enable reading from the source supertype the violating the subsumed invariant). There’s no need to consume the source of the assignment because no new types were added to the subtype (to be written to) which would otherwise violate reading from the source type.

Pony doesn’t allow sharing as box (i.e. read-only between actors) a mutable that can only be written by one ”actor”. Although it wouldn’t be data race unsafe, it would vacate the optimization of employing CPU registers for values of read-only capabilities because the single-threaded execution assumption would be vacated. Also it would be a debugging nightmare substitute for event handlers.

¹ _{When a box alias was obtained from a trn, then the trn can be consumed as a val for sharing (c.f. also).}

Pony’s Monolithic Lifetime Borrowing Capabilities

Rust has complex (overlapping) lifetime tracking of exclusive writability borrowing. Whereas, Pony tracks more variants of aliasing capability (aka reference capabilities/types). Pony can entirely side-step the tsuris of Rust’s data race invariants, by employing the ref capability inside single-threaded code, although this has interplay with covariance for union and record polymorphism subtypes.

Pony’s borrowing¹ concept (i.e. when not permanently losing sendable property with the ref aliasing capability) is limited to a monolithic (i.e. non-overlapping) recover block lifetime. The only external references accessible inside a recover block are those which are sendable (i.e. data race safe to pass to another actor/thread), i.e. iso, val, and tag. The one reference recovered by the block can be recovered as any type if it’s writable² or any non-writable/opaque type if it’s non-writable², because all its internal aliases created inside the recover block go out of scope when the recover block does. This is data race safe because by definition of being sendable, the said external references can only alias the recovered (or any) reference in a data race safe manner— i.e. they can’t write to it nor read it if it’s writable.

Sendable capabilities

The val is safe to share because no actor/thread can write to it. The tag is safe to share because it can’t be used to read the data. The iso is safe to consume and pass, because although it can write, no other actor/thread can read. Whereas, a box doesn’t guarantee the current actor/thread doesn’t have aliases that write to it; and a trn doesn’t guarantee the current actor/thread doesn’t have aliases that write to it. So they (along with ref) can’t be shared nor passed after consuming them. None of Zer0’s proposed extended capabilities are sendable (which is probably why they weren’t included in Pony because Pony’s creators probably didn’t consider their utility as I did).

Function as a recover block

Pony’s Automatic receiver recovery is really just treating a function as a recover block wherein all the input (including external references in any automatic closures) arguments (except one?, e.g. the “receiver”³) are sendable and the result is also sendable (or discarded). That enables data race safety when the one chosen argument is treated as the recovered reference so that it can be passed in instead of aliased.

¹ _{Moves with consume seem to be as flexible as in Rust. And aliasing is more nuanced in Pony than in Rust.}

² _{C.f. chart in prior post but excluding the exclusive readability types added for Zer0, which must be recovered as exclusive readable.}

³ _{The (this) object on which the function is being called.}

Modeling Pony’s Reference Capabilities Type System in Scala

Check this out! I think we can complete a PoC for Zer0 without needing to implement a type checking engine, by transforming the Pony model into Scala’s type system!! With typeclasses also!!

I’m contemplating that it may be possible (at least initially for a rough PoC) to model Pony’s reference capabilities type system in Scala without needing to do any additional type checking in the Zer0 compiler (for a Scala output target). IOW, I posit that all the type checking can be done by the Scala compiler with the following model.

The model is complicated by Pony’s requirements:

Viewpoint adaptation which require that the reference capability type of each field of a data type are modulated by “origin” reference capability type they’re referenced with.
Arrow Types aka Viewpoints which require that argument and/or result reference capability type(s) can be modulated by any¹ of the other argument reference capability type(s).
Capability Subtyping which requires that only certain reference capability types are substitutable for another reference capability type.
Alias types and Ephemeral types which triple the variants of reference capability types.
Generics and Reference Capabilities which require a way to apply the reference capability of the generic type orthogonal to the generic type.

¹ _{Pony being that it has methods instead of free functions for OOP class inheritance anti-pattern](#43) (c.f. also, also, also “Edit#2”) seems to only support the viewpoint adaption for the “receiver” (i.e. this->) at function use sites. But for Zer0 I would like to support it more generally as stated.}

Wrapped data

The first trick is to wrap every data type in a zero-overhead value class wrapper type which implements the following interface, where DATA is the wrapped data type and TYPE is the reference capability:

trait Capability[DATA, +TYPE] {
   val data : DATA
}

Note the +TYPE means covariant. So all the reference capability types (including the Alias and Ephemeral type variants) will be defined in a Capability Subtying lattice insuring that substitution is soundly checked by the Scala compiler.

Wrapping the data this way will presumably not add much performance overhead (in most cases) because we can employ @inline (which in Scala 3 will become a guaranteed frontend operation) and some JVM automatically JIT optimize these also. This will disable Scala’s @specialized optimization but that isn’t apparently used that often in the Scala collections but can really hinder performance generally. Also any FFI will need to wrap and unwrap.

That also enables Generics and Reference Capabilities with only a syntactical transformation of Zer0 code into Scala code.

Implicit resolution of every typeclass function use-site

To model Viewpoint adaption and Arrow Types aka Viewpoints in Scala’s type system, employ type-level programming with (Scala’s unique?) implicit. Require the limitation that only functions of typeclasses (and their instance implementations) are allowed to perform Viewpoint adaption. This makes sense because they should be the only functions allowed to access members of data directly.

The implicit argument for the typeclass instance will already be adapted to the TYPE parameter(s) of the data type(s) that select the instance as exemplified in the Scala typeclass pattern monad example² (except imagine that example modified to provide adapted variants of each implementation for each TYPE variant).

That satisfies the viewpoint adaption for data types that select the typeclass instance. Any Arrow Types aka Viewpoints adaption are encoded with dependent parametrisation which is also applicable to non-typeclass functions.

Always alias expressions except ephemeralize result/return

If we always (implicitly consume so as to) cast result/return expressions as Ephemeral types, then all other expressions can be cast to Alias types because result/return expressions aren’t supposed to be aliased and they are only every assigned (to identifiers or as arguments) or discarded (the potential loss of a compiler optimization as mentioned in at the linked post is irrelevant in this context of a Scala model).

² _{There’s alternative patterns as well.}

You may be interested to know that Pony is moving toward a slightly more complex, but more permissive model for viewpoint adaptation that treats "extractive" viewpoint adaptation separately: https://github.com/ponylang/rfcs/blob/feature/formal-viewpoint-adaptation/text/0000-formal-viewpoint-adaptation.md

It's based on a paper by George Steed

@jemc

@jemc thank you very much for the heads up.

EDIT: I might have found an error or just a typo in George Steed’s paper.

@keean

To Share With Lifetimes, or Not Share At All?

An idea occurred to me while re-reading the Sharing doesn’t scale section of the Message-based concurrency (and parallelism) document I wrote on November 28, 2018.

I’ll quote the salient bit:

Pony’s ORCA garbage collection algorithm for inter-partition shared objects is inefficient because of the conceptual generative essence of Amdahl’s law in this case that “multiple garbage collectors running in parallel with each other and with the running program, can add significant … synchronization overhead … reducing the advantages of parallelism”.

I’ll quote the relevant bit from the “is inefficient” link cited above:

Indeed GC is runtime synchronization.

Runtime synchronization is the enemy of scaling.

[…]

Remember what ever paradigm you try to throw at the problem to avoid a compile-time borrowing model (i.e. which forces you to design to remove runtime synchronization) will always have synchronization at some level of abstraction. This is unavoidable.

tl;dr compile-time borrowing is the only solution

Pony is inefficient and can’t scale with shared data to massively concurrent Actor-like Partitions (ALPs) for the generative essence reason quoted above — the synchronization overhead between the distinct GCs for each ALP.¹ Their advice (c.f. also) for performance enhancement distills to don’t share, lol. 😖

¹ _{I’m coining the term Actor-like Partition (ALP) to describe the communicating sequential processes of Hoare’s Communicating Sequential Processes but without Hewitt’s Actor model’s complete lack of causal ordering which Pony misnomers “actors”, c.f. also.}

Likewise, languages with a single GC for all threads such as Java or Go are inefficient even if there’s no sharing and can’t scale to massively concurrent ALPs because a single GC for all ALPs either has global stop-the-world (of threads) contention or incurs synchronization overhead for contention mitigation with a concurrent and/or incremental algorithm, c.f. also, also, also, also, also and also.

The essence of the scaling problem is that as the number processors increases the exponentially exploding (opportunities for) contention and/or synchronization overhead due to the n log n Odlyzko-Tilly network connections (between processors) scaling² overwhelms the linear performance increases due parallelism. Amdahl’s law doesn’t model where p increases (even possibly non-linearly) with number of processors:

² _{Odlyzko-Tilly’s n log n is not sublinear and worse by implication of the distinguishing criteria from Metcalf’s law, networks with identical interconnections and nodes aka processors in this context, scale closer to n x n = n². And in this context network connections is an abstract notion for various inter-process synchronization issues such as: cache coherence, GC contention, etc..}

Imagine for the above image n is the chunking size interval between inter-process synchronization requests, i.e. inversely related to synchronization overhead. Here’s a more explicit visualization:

Putting multicore processing in context: Part One

However, there’s some compelling reasons (also including the cache coherency problem) why sharing won’t scale even when eliminating GC synchronization with the lifetime borrowing ideal herein (although sharing within a local cache coherent group of processors is performant, yet that’s not scaling):

Massively multicore + shared memory doesn’t scale

By employing distinct GCs for each ALP, Pony reduces the contention of GC compared to a single GC for all ALPs a la Go or Java, but only when those distinct GCs are independent from each other due to no or insignificant sharing. But then why have the reference capabilities model if sharing is to be discouraged? Well there’s the benefit that (even a writable) can be sent to another ALP without sharing if consumed instead. But even sending objects (instead of primitives) incurs some inter-process synchronization overhead either for cache coherence or inter-process bus such as AMD’s Infinity Fabric.

Pony’s reference capabilities model creates many more cases of non-composability between capabilities and is much more complex than not having it, although AFAICS Pony’s capabilities model is orthogonal to and could coexist with my idea herein. Essentially Pony’s capabilities enabling proving whether a reference is sendable avoiding the necessity of creating a copy. But reference capabilities do not track lifetimes to enable super efficient stack-frame allocation and stack-based compile-time memory management a la Rust — when you can keep Rust’s tsuris cat stuffed in the don’t-punt-to ARC-bag. Pony’s capabilities don’t create Rust’s reentrancy-safe code nor prevent single-threaded data races via borrowing as Rust can. Thus Pony’s capabilities seem to add a lot of complexity for a very small gain if the performance advice is don’t share and copy instead. 😖

The creators of Pony are experimenting with a new concept Verona, c.f. my Verona synopsis and also.

Compile-time borrowing for lifetimes is orthogonal to Pony’s capabilities, so my idea is to add compile-time borrowing for sharing objects to eliminate the synchronization overhead between the distinct GCs for each ALP. Conceptually this reduction in contention would even apply (to the mutex contention for altering the refcounts) for ARC with tracing for cycles if employing ARC for each CSP’s GC instead of tracing GC.

Additionally I incorporate my long-standing idea to employ — instead of Pony’s mark-and-don’t-sweep GC — a super efficient, trace-free, bumper pointer memory management scheme for non-stack-frame allocated objects which don’t persist beyond the lifetime of processing of a single message from the ALP’s message queue.

AFAICS, this can be accomplished at compile-time:

Sharing of data should be via a function call (analogous to @keean’s idea from 2018) which can either block an ALP when it “calls” another ALP — or blocks the shared objects from being GC — until said function returns. Calling can be implemented by the compiler by placing a message on the incoming queue of the “called” ALP and waiting for the called ALP to return to its message queue loop before unblocking the “calling” ALP (and returning any return value in the case of blocking the entire calling ALP).
- A tangential benefit is that function calls are generally more composable than message queues, including enabling closures if we want.
An ephemeral type tag³:
- Sharing by inter-ALP borrowing an ephemeral (allowed because it can’t persist to be accessed by simultaneous threads) becomes the preferred way to share objects between ALPs. Otherwise consume (exclusive read-only or) copies of objects to share them without incurring the synchronization overhead of sharing⁴ (writeable objects can’t even be shared, and can only be sent by consuming when exclusive access is present). Sharing without employing ephemeral invokes the inter-ALP synchronization overhead of Pony’s current GC model which this idea attempts to eliminate or significantly reduce.
- Assigning an ephemeral to a type without this tag or sharing an ephemeral with the sharing function call not blocked, inserts a run-time write-barrier which checks whether the referenced object is in the ALP-local bump-pointer heap and if so moves it to the (tracing GC’ed) ALP-local non-ephemeral heap. If the referenced object is in neither of the ALP-local heaps, it’s a shared object so assigning it to non-ephemeral invokes the inter-ALP synchronization overhead of Pony’s current GC model, although it’s not clear how the owning ALP will be track but that’s just implementation details. In the case of sharing an ephemeral which is not already referencing a shared object (which can be detected by the write-barrier if it’s referenced object is in either of the ALP-local heaps which will move it if necessary to the ALP-local non-ephemeral heap) and if not already set as follows, it is set by the write-barrier to remain reachable until the sharing function call returns — so as to track the inter-ALP borrow lifetime.
- An ephemeral can only be assigned or initialized/constructed from another ephemeral, a new constructed object, a shared object or a consumed non-ephemeral, because we only want to track inter-ALP (and not intra-ALP) borrow lifetimes. In the latter case a run-time write-barrier moves the object from the (tracing GC’ed) ALP-local non-ephemeral heap to the ALP-local bump-pointer heap.

³ _{Tag means analogous to a phantom type or Pony’s capabilities, i.e. its orthogonal to other attributes of the type.}

⁴ _{Note the underlying implementation could optionally automatically do the sharing as a consumed copy if that’s more efficient (c.f. also) such as for crossing the local cache coherent group barrier in a massively multicore architecture with intra-group but not inter-group cache coherence.}

Thus to the extent there’s only ephemeral tracked lifetime borrowing sharing, the distinct tracing GC for each ALP only needs to trace the references tree of (or ARC) the persistent non-ephemeral types of that ALP. There’s no GC contention nor synchronization overhead w.r.t. to shared ephemeral and there’s no need to apply the tracing GC (nor ARC) to any of the locally constructed ephemeral objects.

A key point is that a multitude of ALPs should be lightweight and employ green threads. The blocked ALPs incur no significant overhead in for example Go.

AFAICS, my idea herein would be compatible with Go, although the posited performance increases wouldn’t be achieved unless Go’s GC was modified to use my idea.

Note this idea herein wouldn’t break composability between non-ephemeral and ephemeral for some functions that have assignment, because the write-barriers enable these assignments. Yet there are performance impacts for this composability, especially depending how it’s used. Pony’s reference capabilities are worse for composability, although they’re orthogonal to this idea herein and may or may not still be needed.

@keean are you aware of any prior art for my idea?

@keean

However, there’s some compelling reasons (also including the cache coherency problem) why sharing won’t scale even when eliminating GC synchronization with the lifetime borrowing ideal herein (although sharing within a local cache coherent group of processors is performant, yet that’s not scaling):

Massively multicore + shared memory doesn’t scale

By employing distinct GCs for each ALP, Pony reduces the contention of GC compared to a single GC for all ALPs a la Go or Java, but only when those distinct GCs are independent from each other due to no or insignificant sharing. But then why have the reference capabilities model if sharing is to be discouraged? Well there’s the benefit that (even a writable) can be sent to another ALP without sharing if consumed instead. But even sending objects (instead of primitives) incurs some inter-process synchronization overhead either for cache coherence or inter-process bus such as AMD’s Infinity Fabric.

Pony’s reference capabilities model creates many more cases of non-composability between capabilities and is much more complex than not having it, although AFAICS Pony’s capabilities model is orthogonal to and could coexist with my idea herein. Essentially Pony’s capabilities enabling proving whether a reference is sendable avoiding the necessity of creating a copy. But reference capabilities do not track lifetimes to enable super efficient stack-frame allocation and stack-based compile-time memory management a la Rust — when you can keep Rust’s tsuris cat stuffed in the don’t-punt-to ARC-bag. Pony’s capabilities don’t create Rust’s reentrancy-safe code nor prevent single-threaded data races via borrowing as Rust can. Thus Pony’s capabilities seem to add a lot of complexity for a very small gain if the performance advice is don’t share and copy instead. 😖

Perhaps the correct answer is literally “do not share” — send messages instead. Sharing presumes cache coherence, whereas a future of massively multi-cored with Infinity Fabric interconnects (or some of the more esoteric massively multi-core processors, c.f. also) essentially the data has to be copied anyway to the destination message queue. I seem to remember @keean proposing this specific approach or at least proposing referential transparency via immutability in past discussions. Here’s some of my ideas:

Consume or Copy: Eliminate the unnecessary complexity, tsuris of Pony’s reference capabilities otherwise needed for (non-tag) sharing between concurrent threads.

Retain the reference capabilities for shareable, sendable non-exclusive tag and non-shareable, sendable exclusive [read] and iso (aka [r/w]). The latter being inter-ALP sendable by consuming (as distinguished from sharing or copying) into a message sent to another ALP.

Neither complex borrowing lifetimes nor linear types tracking are necessary (for tracking consumables) because [read] and [r/w] are always exclusive — simply only allow these to be consumed for intra-ALP code (e.g. as a function argument and returned consumed to caller) and never allow these to be assigned. So simple.

Note for non-consumables (thus not sendable) there's no requirement to enforce exclusivity.
Subdivide: @keean and I discussed in 2018 that given “actors” (aka ALPs) with very low space overhead, sharing isn’t required for optimal large data structures — if the data structures can be subdivided into ALP-size portions which are accessed via “messages.” We discussed that the “messages” could be abstracted as function calls.
Sharing: However inter-ALP sharing between a plurality of ALPs may still be required for large immutable data structures not amenable to subdividing and for which multiple copies would be too inefficient — although Reentrant Actor-like Partions could offer intra-ALP sharing of the large data structure. Yet I envision no compelling need to revive Pony’s complex reference capabilities for this case. Employ Clojure-like or Scala-like immutable data structures for these.

Presumably these could at least be subdivided to limit the sharing (and thus the requirement for cache coherence) to only between processors sharing the same local cache and/or local bus (i.e. not sharing across some, power-hungry, higher-latency Infinity Fabric-like interconnect).
Garbage Collection: Pony’s mark-and-don’t-sweep GC although efficient in the sense that it doesn’t visit and sweep unallocated objects until reclaiming them on demand on allocation, is inefficient in that due to lack of compacting, defragmentation sweep it can't employ an efficient bump-pointer (over a contiguous free space) for allocation.

My idea for a super efficient bump-pointer GC (i.e. deallocate entire heap with no tracing upon completion of the processing of each message) requires in every general case, some anti-compositional “What Color is Your Function”, bifurcation boondoggle, so that the data which doesn’t persist internally to the processing of the next incoming message¹ doesn’t become referenced by the data which does. Or requires inefficient runtime write-barriers for all assignments to check for those cases and move them from bump-pointer heap to the tracing GC or ARC heap.

Elimination of tracing and ARC removes the extra overhead tradeoffs required for “interior” pointers into the body of a data structure. But doesn’t remove the overhead issue for those persist which require tracing or ARC.
Reentrant Actor-like Partitions: However, there’s an interesting specific case where this super efficient bump-pointer deallocation idea can be employed while retaining composability without need for said inefficient write-barrier. We need a persist type tag — allowed only in combination with² the tag imm for immutability — which also tells the runtime to not allocate the data in the bump-pointer heap. If at compile-time all roots of the persistent data (including any inter-ALP shared data³) are references to persist imm, then the actor-like partition is trivially proven reentrant⁴ and additionally all non-persistent data can be safely deallocated (upon completion of the handling of each message) with a single instruction that resets the bump-pointer. Otherwise must employ less efficient tracing GC or the runtime write-barrier for all data in the ALP. So composability in this idealized, requisite case is not impacted much because the persistent and non-persistent data can be freely intermixed within generic functions without the possibility of the assignment of the reference for any non-persistent object to a mutable reference in persistent data (because all the persistent data is non-writable in the requisite case).

Additionally in this idealized case ARC instead of the less efficient tracing GC can be employed for the persistent data if employing imm instead of exclusive read (i.e. [read] or [r/w]) for all persistent data, because (as @keean pointed out in the past) imm (i.e. immutable since construction, thus not converted from the consume of a [r/w] or [read]) can never contain a cyclical reference. Shared immu would require mutex synchronization for mutating the refcounts, but this is likely more efficient than the inter-ALP messaging overhead (c.f. also) required for Pony’s GC model. Presumably the initiation of each instance of this sharing (i.e. sending an inter-ALP message to share an object) would occur infrequently.

¹ For example returning a consumed object wouldn’t persist internally to the next incoming message.

² Because otherwise — given the programmer would not be able to correctly label those which persist without creating a “What Color is Your Function” bifurcation — thus requiring generic functions to be specialized for mutable data according to whether the persist tag is present.

³ The option is either to enforce at compile-time that all inter-ALP sharing (i.e. via sent messages) contain data which is persist imm or place a write barrier on consumes for inter-ALP sending so as to move these at runtime from the bump-pointer heap to the ARC heap. The inefficient write-barrier would be only said consumes so more performant than an inefficient write-barrier on all assignments.

⁴ Thus can process more than one message in parallel in intra-ALP sharing of its persistent data between multiple threads, as an alternative or adjunct to inter-ALP sharing of its immutable data.

@keean

What’s the salient, coherent, succinct generative essence of this thread?

There’s the example of Marilyn vos Savant stating most pertinently, “The winning odds of 1/3 on the first choice can’t go up to 1/2 just because the host opens a losing door,”

Let’s contemplate a design without first-class ‘pointers’, i.e. without pointer equality comparisons nor pointer arithmetic such as is the case for Go(lang).

Immutable

If the program compiles (i.e. to avoid the ‘recursive types’ issue mentioned below) then semantically it makes no difference whether immutable containers^[1] are assigned by copying or by reference. Although the choice will effect whether assignment after initialization aka reassignment is by copying or rebinding by reference, this and other distinctions only apply to space and (sometimes versus) performance. Reassignability could be controlled separately from the aforementioned choice, such as with let, val, const or perhaps =:= or :=: versus :=.

Most glaring of the non-inferable space and performance considerations is that the compiler probably can’t decide for the programmer whether to assign the value to the field of a data record (aka structure) by reference to the value’s immutable container (for space optimization or performance) or copying the value (for avoiding recursive types or for performance). Even though theoretically in some or perhaps most other cases the compiler may be able to automatically optimize the choice of assignment (by reference or copying) for immutable containers, there could still be some cases where performance (versus space) could be fine-tuned if a manual choice can be expressed in the code.

^[1]@keean defined ‘container’ in this context to be the memory that stores a value. He adopted the mathematical definition of a ‘value’ which is always immutable, i.e. a 1 is always a 1 and never a 2 but a mutable container could have its memory changed from 1 to 2 which is the not the same as rebinding a reference to a different container. A reference to a container is not the same as a container, although a reference can be stored in memory that’s not a container in this context unless references are first-class entities accessible in code aka aforementioned first-class ‘pointers’. In PLs which have them, mutable (aka not let, val nor const) references can be rebound to a different container.

Read-only

Read-only access to a container which is not written during said access’ lifetime is in the same situation as aforementioned for an immutable.

The challenge is statically proving the aforementioned invariant. Perhaps primitive value types can always be assigned most efficiently by copying and thus would trivially satisfy the invariant. The challenge remains for non-primitive value types. Exclusivity of access such as Rust’s exclusive write borrowing, or Pony’s consume of exclusive write trn or iso, is an onerous total ordering.

A clever insight and delicious alternative to exclusive write total orders (why did I not think of this before!) is that two identifiers that apply to containers of different types of values can’t be aliases to the same container. Ah an advantage for typing that Clojure’s Rich Hickey didn’t enumerate. Given support for interior “pointers” then this rule has to be applied to all the referenced field types (i.e. thus typically not primitive types in call-by-sharing) within a data record (aka structure) type. Perhaps primitive value types can always be assigned most efficiently by copying and thus would be excluded from this rule (as is typical in call-by-sharing).

A synchronous^[2] “function” (or more precisely a procedure because not referring to a pure function) thus satisfies the aforementioned invariant for any read-only access arguments if all its writable access input arguments are of different types than the said read-only access arguments and also excluding any mutual field types of those as aforementioned.

The aforementioned invariant also satisfies the requirements of C’s restrict so a compiler can optimize what can be kept in the CPU’s registers instead of memory. The aforementioned clever insight can also be employed to automatically infer C’s restrict for writable types as well. There could also be a dynamic aliasing test for equality for references to the containers of the same value type, which is not generally possible for untyped pointers which point to anything which might contain the other.

Presumably code within a function can be analyzed to detect aliasing but in cases of ambiguity or just because said analysis is extremely complex (←c.f. §Optimizing C) then the same clever insight could be applied for identifiers instanced within the body of a synchronous function.

Explicit intent must be expressed in the code for read-only access arguments and any said identifiers which fall the invariant or for asynchronous functions.

^[2]An asynchronous function employing call-by-reference could be subject to writes to its read-only access arguments’ referenced containers by code external to the function.

Writable

If there’s not a default choice such as JavaScript’s call-by-sharing then there needs to be some way to indicate which choice to employ for assignment because the semantics are not equivalent between the two options.

I repeat for my needs which is to not be mucking around in low-level details in a high-level language, I think JavaScript got this right in that certain primitive types (e.g. Number, also String correct?) are treated as values and the rest as references to a container of the value. So the programmer never needs to declare whether a type is a reference to a value or a value.

JavaScript, Java, and Python employ call-by-sharing which is distinguished from call-by-reference because only certain objects are passed-by-reference.

Another clever insight is that a function is semantically agnostic as to whether its writable arguments are passed by reference or by copying. The choice will affect the optimization and compiled encoding of the function. Although the choice may affect the semantics of the function w.r.t. caller’s results, the function may be agnostic as long as the caller expresses and receives its intended semantics.

I thus posit that caller’s would express their intent such as by prepending call-by-value parameters (perhaps other than primitive value types) with *, with a call-by-sharing default for all functions. Or by prepending call-by-reference parameters with &, with a call-by-value default for all functions.

If instead make everything immutable but then you’d have Haskell and its drawbacks.

Why?

Paradigms that reduce the number of factors the programmer has to keep track of, aid productivity and possibly even reduce What Color Is Your Function noncomposability. Additionally C Is Not a Low-level Language (←c.f. §Optimizing C, c.f. also) points out that letting the compiler decide (and providing it the information to decide about optimization) enables optimizations that the programmer did not or could not anticipate because the ideal optimizations change as the hardware and other factors of the system change.

Letting the compiler can decide without the programmer’s intervention, fixes or ameliorates the issue @keean raised about Rust’s closures not being able to decide automatically and the concomitant complexity that introduces.

Additionally, inverting the control thus providing more degrees-of-freedom is achieved by enabling the caller of the function to decide, in the cases where the programmer must make the decision because the compiler doesn’t have enough information to do so automatically.

Navigation Menu

Repository navigation

Mutable Objects #32

86 remaining items

Pony’s Design Compared

Optimization of Result Value Temporaries

Extending Pony’s Reference Types

Pony’s Monolithic Lifetime Borrowing Capabilities

Sendable capabilities

Function as a recover block

Modeling Pony’s Reference Capabilities Type System in Scala

Wrapped data

Implicit resolution of every typeclass function use-site

Always alias expressions except ephemeralize result/return

To Share With Lifetimes, or Not Share At All?

Immutable

Read-only

Writable

Why?

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Pony	Zer0	Access	Shared Aliasing	Non-Shared Aliasing
`iso` Isolated	`[r/w]`	Exclusive (read/write) (writable)	None	None
`val` Value	`val`	Immutable (non-writable)	Read-only	Read-only
`ref` Reference	`r/w`	Read/write (writable)	None	Read-write
	`[r]/w`	(Exclusive read)/write (writable)	None	Write-only
	`r/[w]`	Read/(exclusive write) (writable)	None	Read-only
	`[read]`	Exclusive read-only (non-writable)	None	Write-only
`box` Box	`read`	Read-only (non-writable)	None Read-only	Read/write¹ Read-only
`trn` Transition	`[write]`	Exclusive write-only (writable)	None	Read-only
	`write`	Write-only (writable)	None	Read/write
`tag` Tag	`id`	Address-only Opaque pointer	Address-only	Address-only

Mutable Objects #32

Description

Activity

shelby3 commented on May 11, 2017

keean commented on May 11, 2017

shelby3 commented on May 12, 2017

keean commented on May 12, 2017

shelby3 commented on May 12, 2017

shelby3 commented on May 12, 2017

shelby3 commented on May 12, 2017

keean commented on May 12, 2017

shelby3 commented on May 12, 2017

keean commented on May 12, 2017

shelby3 commented on May 12, 2017

keean commented on May 15, 2017

shelby3 commented on May 17, 2017

keean commented on May 17, 2017

shelby3 commented on May 18, 2017

86 remaining items

keean commented on Aug 31, 2018

shelby3 commented on Aug 31, 2018

keean commented on Aug 31, 2018

keean commented on Aug 31, 2018

shelby3 commented on Aug 31, 2018

shelby3 commented on Sep 7, 2018

Pony’s Design Compared

shelby3 commented on Sep 8, 2018

Optimization of Result Value Temporaries

shelby3 commented on Sep 8, 2018

Extending Pony’s Reference Types

shelby3 commented on Sep 9, 2018

Pony’s Monolithic Lifetime Borrowing Capabilities

Sendable capabilities

Function as a recover block

shelby3 commented on Sep 10, 2018

Modeling Pony’s Reference Capabilities Type System in Scala

Wrapped data

Implicit resolution of every typeclass function use-site

Always alias expressions except ephemeralize result/return

jemc commented on Oct 5, 2018

shelby3 commented on Oct 21, 2018

shelby3 commented on May 18, 2020

To Share With Lifetimes, or Not Share At All?

shelby3 commented on May 22, 2020

shelby3 commented on Sep 20, 2020

Immutable

Read-only

Writable

Why?

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions