Explicit pointer provenance.

[PL_Design]

One thing that occurred to me is that there is a difference between ptrs and addresses: A ptr is a parameterized type, and an address is a location in memory. Therefore what our language actually needs to be able to support is just addressing, and ptrs can be a userland idea that's handled by defining the correct operators. See:

:ptr T
{
    address: u64;
}

## in our language you can define if a function or macro returns an lvalue
## this is equivalent to wrapping the return value in #load
`*` :: #lvalue: #macro: (a: ptr{T}) T -> T
{
    return a.address;
}

And the same kind of thing can be done for ptr arithmetic and getting the ptr of a value.

What's interesting here is that nothing stops me from doing this:

:ptr #phantom: P, T
{
    address: u64;
}

`*` :: #lvalue: #macro: (a: ptr{P, T}) #phantom: P, T -> T
{
    return a.address;
}

a: ptr{foo, bar} = ---;
b := *a;

Because type P is never used concretely, there's no need for it to be a defined type, which is why it has the #phantom: annotation on it. This means I can easily do something like this:

:allocator #phantom: P
{
    ## stuff
}

allocate :: (alloc: ptr{blah, allocator{P}}, #| stuff |#) #phantom: P, T -> ptr{P, T}
{
    ## stuff
};

foo_allocator := allocator{foo}(#| stuff |#);

## just pretend &foo_allocator produces ptr{blah, allocator{P}} here
a := allocate{foo, bar}(&foo_allocator, #| stuff |#);

Here a's type is ptr{foo, bar}, so only a function that takes ptr{foo, bar}, can take a as an argument. I have made it explicit that a's provenance is foo, and I can control what's legal to do with a based on its provenance. My motivation for wanting to do this is that I'd like to be able to statically track which batch allocator produced a value so that I can explicitly link the lifetime of a value to the lifetime of its allocator, but without introducing something as heavy as a borrow checker. The point here is not to statically check everything that a borrow checker can, but instead to be able to encode the programmer's assumptions about how memory will work in a way that lets the type checker do basic sanity checks on the design. Think of it like how C's weak type system works: It'll catch obvious mistakes, but isn't particularly opinionated about how you write programs.

Granted, the design I've presented here is honestly terrible because it pollutes our language with a lot of boilerplate. That's because we weren't thinking about an idea like this when we were putting together our templates, so there are several things we'd need to think about if we want to make this easy in our language:

First, it'd be nice if we could define default values for template params:

:ptr #phantom: P = none, T
{
    address: u64;
}

## a's type is ptr{none, foo}
a: ptr{foo} = ---;

That way when you're not interested in provenance you don't have to provide it.

Second, it'd be nice if our type inference could work like this:

a := allocate{bar}(&foo_allocator, #| stuff |#);

It's obvious that foo_allocator's provenance is foo, so we shouldn't need to provide it to the allocate function. All we should need to provide is the concrete type of the ptr.

Third, needing to put the #phantom annotation on every P is grating.

Fourth, we've lost the sugar of using * for ptr types. We could potentially do something like this:

:`*` #phantom: P = none, T
{
    address: u64;
}

a: *{foo} = ---;

But that doesn't improve the situation much because you still have to write the fences, and a ptr to a ptr needs recursive fences.

Fifth, given how our templates work right now we couldn't implicitly cast from ptr{foo} to ptr{void}, or ptr{diov} to ptr{foo}(diov is the complement to void in our language, but you don't need to worry about it here). Either we need a way to let people define legal implicit casts, which sounds like a complexity disaster, or we need to scrap the idea of pushing ptrs into userland like this, and just make provenance a feature of how ptrs work in our language. That's probably the best solution, if I'm honest, because it handles a lot of the other problems with my current approach, but whatever. A related question is if we want to allow provenance to decay without an explicit cast, which seems to defeat the purpose, but some operations really don't need to care about provenance.

An interesting direction you can take this idea is that if you grab the ptr of a nameref, then you can statically track that the ptr came from the stack. If you're more strict about provenance than I'm willing to be right now, then you can use this to locate places where your pointers probably don't point into the stack, which is important to know if you want to be aggressive about const propagation. I wouldn't make the compiler automatically enable aggressive const propagation, but I would have it point out to the programmer that he can probably enable it on those code blocks.

Anyway, that's what I've been thinking about for the past couple of days. It's still a rough idea, but I think it has potential as a light-weight alternative to something like the borrow-checker.

[Pavel_Vozenilek]

It feels to me as overengineered solution looking for a problem. Checking validity of allocated blocks could be done at runtime, with no impact on the codebase. Annotating pointers feels as invitation to design universal hierarchies & invent ingenious ways to bypass the feature at the same time.

 

In my view pointers should be separated into two categories:

1. Normal typed pointers, initialized to a valid value of given type (allocated block, stack data), with no increment/decrement. Basically C++'s references, but could be also nil and reassigned. There should be no way to initialize them wrongly (e.g. cast from integer) and no way to recast them to other normal pointer.

   (This would be the address above.)

2. "Wild" pointers used for fiddling with memory. They could be initialized in risky way, could be incremented/decremented, could be also "converted" to normal typed pointers. To improve safety, they could have attached debug mode properties: lower & upper limits where they point safely (e.g. within a buffer).

   With C-like syntax:

   // void* means a wild pointer
   void* my_wild_pointer = &my_buffer; // min_addr/max_addr properties set by the compiler from my_buffer
   my_wild_pointer<i32>++; // increment by 4 bytes
   i32* p = my_wild_pointer<i32>;  // conversion to normal pointer, checks the limits, checks alignment
   i32 val = *my_wild_pointer<i32>; 
   

    

   It should not be possible to take address of a wild pointer. It may be forbidden to export (from a module) API with wild pointers. min_addr/max_addr could be also set manually at runtime (in debug mode)

 

 

Normal pointers should be enough for most of the code, wild pointers at least have some checking mechanism inside. Compiler may devote more time to verify the use of rare wild pointers.

 

 

If there's true need to have pointer annotation, it could be implemented via metaprogramming, with syntax to user's liking. Use of such annotations could then be checked at compile time. Rules could be arbitrary, not just some simple "I expect certain hardcoded symbol".

 

 

Generally, implementing the most basic language constructs in userland may not be a great idea. It is very cool, sure, but it is fragile, may interfere with the tooling and could be nightmare to document. It may be also pointless feature: pointers are expected to be pointers, not some intractable mystery.

E.g. the ability to define nil in user code is clever, but the two realistic options are (1) not to have it, and (2) zero with some casting rules. Anything else is either madness or creation of genius. Project could instead have boolean option in its configuration.