Thank you for the detailed answer. I'm looking forward to that blog post. One more question for now (a variant of something I asked before): How do you know a use is a last use? For example:

    foo = (list1 list2) -> {
        mutate_last list1
    }

The use of list1 in the mutate_last call is the only, and hence the last, use of list1. So mutate_last can mutate it in place. Right?

Except if I call this function like:

    big_list = [ ... ]
    foo big_list big_list
    print big_list

Then mutating in place will be incorrect. So how do you tell inside foo whether the call is the last use of the object referenced by list1? Heroic interprocedural pointer analysis? A uniqueness type system? Something else?

Thanks for discussing this with me and helping me work through it. To answer your question:

Let's annotate the variable lifetimes. `'` indicates last use, `_n` indicates that a variable holds the same value. I'll only be annotating the values in question:

    foo = (list1_0 list2_0') -> {
        mutate_last list1_0'
    }

    big_list_0 = [ ... ]
    foo big_list_0 big_list_0
    print big_list_0'

Let's focus on this line. Because these both aren't the last reference to `big_list`, they're passed as a CoW reference. I'll use `&` to denote this:

    foo &big_list_0 &big_list_0

In `foo`, `list1_0 = &big_list_0` and `list2_0' = &big_list_0`. `list2_0` is never used, so this reference is immediately dropped (not the value itself, rather the reference to that value). Let's now look at the body of foo:

    mutate_last list1_0'

Because list1_0 is a final reference, it's passed the value of the CoW reference, which is, well, the CoW reference. mutate list mutates this, and because the reference is copy-on-write, a copy of `&big_list_0` is returned. We'll call this `big_list_1`.

So the CoW reference of a value is a CoW<Value>. a CoW reference of a CoW<Value> stays the same, it's still a CoW<Value>.

> So how do you tell inside foo whether the call is the last use of the object referenced by list1? Heroic interprocedural pointer analysis? A uniqueness type system? Something else?

Something else. Vaporization is not all compile-time magic, it depends on the runtime as well. You can basically sum it up with two operations:

    reference: Value or CoW<Value>            -> CoW<Value>
    mutate:    Value or CoW<Value> + mutation -> Value

So when `mutate_list` mutates the list, depending on whether `list1` is a value or a CoW reference, either a copy will be made or it'll be mutated in place. I'm not claiming that Vaporization is the best approach to compile-time memory management, rather, it's more of a set of compiletime+runtime strategies that allow the interpretation of programs without garbage collection (in the traditional sense)

So, the question becomes: how do we indicate whether something is a value or a CoW reference? Something along the lines of a tagged pointer will do. Passerine already uses NaN-tagging, so this fits right in.

What about compiling to low-level targets, like LLVM IR, which don't really have a 'runtime' and rather specify the manual layout of structs and references?

I'm not quite sure, but here's one possibility. All values that can escape a local scope exist in some region of memory allocated for local variables. When a function is called, we can pass a bitfield indicating which of the locals variables on the stack are CoW references, and which are not. When the runtime goes to mutate a reference, it quickly checks the bitfield (which can be stored in a register or in the call frame) whether it needs to make a copy before mutating. In practice, the check is just a quick bit-shift and `&`.

Note that we can go a bit further: the bit-fields of all calls are known at compile time, so instead of copying and passing the bitfield itself, we can pass the index of the bitfield (which is a constant) to the function to use. In fact, I imagine you could somewhat 'monomorphize' this, so to speak, and generate different functions for different bitfields... but I'd have to think some more about this.

Anyway, that's about it. I hope I've helped clear some things up. If you notice anything else slightly off, or if you'd like to discuss this further, please let me know :)

Sorry, one more question about mutation and CoW. It would be good to know how mutation is written, since without that I can't write out the example I have in mind!

Imagine I want to write a function

    append xs y

that appends element y to the linked list xs using "mutation". It recurses down the linked list and at the very end it mutates the last cons cell to have [y] rather than [] as its tail.

Imagine this is called with a CoW reference for xs. I guess as you recurse down the list, each tail pointer must also be treated as CoW, since there will be copying mutation going on. So you get to the end, "mutate" the last element by copying it... but now all the other CoW references you encountered along the way must be copied as well. Do I understand this correctly? How is this handled? Do the CoW references have backlinks, or do you unwind some sort of stack (defeating any possibility for "real" tail recursion)?

Right, so there would have to be built in functions that mutate and return an object. So, for instance, one might be:

    List::replace list index value -> list

List would just write to the `list` it is given. If `list` is a CoW reference, it would make a copy first before mutation (hence copy-on-write), if it was not, it would just mutate it in place.

To mutate `xs` with append as you suggested, you'd have to reassign `xs` with the result of append. Because this would make the `xs` in `append xs y` the last occurence of the value, `xs` would be mutated in place:

    xs = append xs y

If the function were of the form `append y xs`, you could use dot-notation like so:

    xs = xs.append y

and if you really hate writing out `xs =`, you could always make a macro:

    syntax 'mut value function {
        value = function value
    }

    mut xs (append y)

I've got to go, but I'll get back to you on tail recursion.

Under the hood I'm going to use Rust `Vec<T>`s to represent lists, so it'd be trivial to provide a FFI operation to append something to the end in constant time. However, we can treat the list like a linked list, and, using recursion, here's a tail-call-optimized implementation of append in linear time:

    append = list value -> {
        loop = acc rem -> match rem {
            [] -> acc,
            [head & tail] -> loop [head & acc] tail
        }
        loop value (List::reverse list)
    }

I'm thinking of using something other than the `[a & b]` syntax, but that's besides the point. Note that `loop` does not close over any values other than itself, so it doesn't need to be inside `append`:

    loop = acc rem -> ...
    append = list value -> ...

The function really starts when we reach this line:

    loop value' (List::reverse list')

I added `'` to indicate that this is the last occurrence of both `list` and `value` in this scope, which means that they're passed to `loop` without making a CoW reference. Let's look at `loop`:

    loop = acc rem -> match rem {
        [] -> acc,
        [head & tail] -> loop [head & acc] tail
    }

This is where things get complicated, depending on the definition of match. If it were defined as macro, it'd be laborious to write out how it all works by hand. But if we treat `loop` as a function with multiple heads, it's a bit easier.

Here, we have two arms. If the remaining list is empty, we return `acc`. note that each arm is independent, so this usage of `acc` is the last in the scope.

If the list is not empty, we match `rem` against `[head & tail]`. This is equivalent to, roughly:

    [head & tail] = rem'

Note how this is the last usage of rem in this scope, meaning it's passed by actual value. This list is then split in-place, with head taking on the value of the first element of the list and tail taking on the value of the rest. Once passed to loop, note that all the values used are the last occurrence of the value in the scope:

    loop [head' & acc'] tail'

This means that the actual value is passed down to the next level. Looking at this as a whole, we can see that nothing is ever passed by CoW reference, which means that this operation is performed in-place. And because it's done in a tail-recursive manner, `append` only uses constant space.

So to answer your question specifically: what if append is called with `xs` being a CoW reference?

    append &xs y

When we reach the line:

    [head & tail] = &rem'

`rem` is mutated, i.e. split in two, so a copy of it is made. This copy is it's own value, so head no tail are no longer CoW. we then call:

    loop [head & acc] tail

Note that head and tail are now passed by value and not CoW - same goes for acc. Because nothing is CoW anymore, this tail-recursive implementation operates on the new list, mutating it in place.

In short: the first iteration in `append` makes a copy to the list, but in subsequent iterations the copy is used, and the list is mutated in place.

That was a big one, I'm practically writing the blog post out here, haha! Does this help clear things up?

Thank you again for explaining things.

> When we reach the line: [head & tail] = &rem' `rem` is mutated, i.e. split in two, so a copy of it is made.

Huh. That surprises me, that you consider destructuring a form of mutation. But if you do, then I see how this works out because it forces a copy.

However, this raises more doubts. If I write something like

    first_two xs -> match xs {
        [] -> [],
        [head & tail] -> [head & first tail]
    }

    first xs -> match xs {
        [] -> [],
        [head & _] -> [head]
    }

and call first_two with a CoW reference to a very long list, will it copy the entire list on the first destructuring, even though we really only want to copy two elements? For that matter, will a list search function, that is only supposed to read the list, called with a CoW reference actually copy the list?

If the answer is "well, lists are special", I guess you could consider the same questions on trees. In a functional language, insertion into a binary tree only copies nodes along one path in the tree. Would your language copy the entire tree instead, at potentially exponentially higher cost?

(I'm also slightly confused by your definition of append -- the accumulator seems to be a list, but then the initial call of loop would need to use [value] instead of value, no?)

Regarding "tying references to the stack" I had another question here: https://news.ycombinator.com/item?id=26228961

Thanks for your excellent questions. They're really helping me fuzz through my approach - I wish I had people I could do this with more often, haha. :P

Anyway, something I realized after I posted that question is that assignment doesn't have to force a copy; for instance, this could just take a CoW slice reference to the original list:

    [head & tail] = &rem'

The only requirement is that the value returned from a function is an owned value, not CoW. To avoid talking myself into circles, I'll show that `append` still works under this rule. It just moves the copy to the point where we construct the new list, rather that at the point where we de-structure it:

    loop [head' & acc'] tail'

So in `[head' & acc']`.

For the code sample you provided, a reference would be passed down, rather than a copy of the entire list, so just the first two elements would be copied. Do you have any further questions regarding this? I'd like to be able to prove the soundness of this system, but I'm not sure going back and forth on example after example is the best strategy in the long run.

> In a functional language, insertion into a binary tree only copies nodes along one path in the tree. Would your language copy the entire tree instead, at potentially exponentially higher cost?

Most functional languages use persistent data-types, because all data in those languages are immutable. I haven't thought about how they'd work into Passerine, but if you mutate data that will be used later, a copy of that data will be made. So yes, mutating a tree makes a copy of it if the original tree is used later.

This is less of a problem then you'd think. It's common to write programs as series of transformations on data, so note that if you do something like this on a big million-element list children .map { child -> (child.name, child.age, child.hobby) } .filter { (_, age, _) -> age > 10 } .map { (name, _, hobby) -> (first_name name, hobby) } .filter { (_, hobby) -> is_fun hobby } .fold "" { (string, (name, hobby)) -> string + name + " enjoys " + hobby + "\n" } .print

No copies will be made, because each step is the last usage of the data-structure produced in the previous step.

> (I'm also slightly confused by your definition of append -- the accumulator seems to be a list, but then the initial call of loop would need to use [value] instead of value, no?)

Once again, correct.

> Regarding "tying references to the stack" I had another question here: https://news.ycombinator.com/item?id=26228961

I wrote a long response, to this, but it ended up being a couple thousand words, so I'm trying to trim it down. (I went off the deep end, with stack diagrams, explaining how cycles get created, etc, etc.) TL;DR for now is that you can't have a list of references, each object is only mutably 'owned' by one other. Once I trim down the response, I'll post it - should be sometime later today.

Thank you again for your answers. I must admit that at this point I'm thoroughly confused by references, CoW, Passerine being pass-by-value, ownership (new information today!), and fairly advanced rules for when something needs to be copied. It probably makes sense to leave you to write that blog post where you can give a consistent view of the whole rather than iterating on small examples. I'm intrigued, and I'm looking forward to reading more, though I'm also getting a nagging feeling that there's a lot of ceremony here just to avoid garbage collection...

Thank you for your patience in explaining all this. Runtime tagging seems to make a lot of sense for this approach! Is this based on any previous work? It's been about ten years since I was last up to date with compile-time garbage collection techniques.

> What about compiling to low-level targets, like LLVM IR, which don't really have a 'runtime' and rather specify the manual layout of structs and references?

If you want to support dynamic memory allocation/deallocation, you will have to provide a runtime anyway. Even if it's "just" LLVM IR or C code or whatever for a simple allocator.

I think I'll have at least one more question about how the "tying of references to the stack" works, but I need to think things through a bit more.

It's loosely based on Proust ASAP, but without the explicit quadratic-time construction of paths (in a sense, this is done 'dynamically' at runtime with the CoW strategy we've discussed). When you think about it, Vaporization is really just an extension to escape analysis. It's not a perfect system though, namely, It required immutable closures. But if you're coming from a functional programming language, that's a small sacrifice to make, given that mutability is generally frowned upon.

> I think I'll have at least one more question about how the "tying of references to the stack" works, but I need to think things through a bit more.

I tried to answer your sibling comment on appending a CoW xs. I hope that clears some things up so you can ask any questions you have!

> Vaporization basically ties everything to the stack, and prevents values stored on the heap from becoming dissociated with it.

So if some code somewhere hands me a list that contains references to some heap data, how do you track this? For example, say at some point in the program I have a reference called "refs" that happens to be bound to a list of references to some objects a, b, and c. Then I do:

    refs = drop_first refs

so that refs is now [b, c]. We lost/dropped/gave up a. How do we know how a was tied to the stack? How many other references might point at the object previously referenced by a? Can we collect that object now? Is this the case where reference counting kicks in? In which case, the category of "closure references" is probably more general than I thought.

Because Passerine is pass-by-value, it only allows each reference to be owned by one object.

> So if some code somewhere hands me a list that contains references to some heap data, how do you track this?

Passerine is a high-level language, so it does not give the programmer control over whether something is a list of references to data on the heap or a list of values. Assuming `a`, `b`, and `c` have been defined, If I write this:

    list = [a, b, c]

`a`, `b`, and `c` will be moved into the list upon construction. If I do something like:

    list = [a, b, c]
    print (foo a c)

`b` will be moved into the list, and copies of `a` and `c` will be moved into the list.

So, to now answer your question:

    list = [a, b, c]
    list = drop_first list

> We lost/dropped/gave up a. How do we know how a was tied to the stack?

`a` was tied to the stack because it's in `[a, b, c]`, which is tied to the stack via `list`.

> How many other references might point at the object previously referenced by a? Can we collect that object now?

By definition, none - `a` is a unique value. Now that we dropped `a`, there are guaranteed to be no other references of `a`, so we can collect that object now.

> Is this the case where reference counting kicks in?

No, the reference counting is a small optimization for sharing immutable values in closures. If a closure captures a value, say a large list, we don't want to go around copying this willy-nilly:

    big_list = [...]
    c = () -> {
        -- big list is copied when the closure is made
        -- this happens because the reference in the closure can outlive local stack frame
        a -> first big_list
    }

    -- these calls to c do not copy big_list again
    a_outer = c ()
    a_another = c ()

Closures need to copy values immutably to prevent the construction of cycles. I wrote a long explanation on why this is the case, but I've decided to move it to the blog post when I publish it. I thought of a way to efficiently count references acyclically, but I need to work it out before I made any more claims.

Hope this helps!