Should functions not be allowed to return aliases by default?

[athas]

I am plugging some holes in alias tracking, and I discovered something uncomfortable. We currently have a rule that functions may not return aliases of global variables. This rule was instituted such that we can assume that the value returned by e.g. transpose A can at most alias A, which allows us to make in-place updates to transposed arrays, as long as we can consume the original array.

Now consider the following program:

module type monoid = {
  type t
  val zero : t
  val plus : t -> t -> t
}

module pm (M: monoid) = {
  def f (x: M.t) : M.t =
    M.plus M.zero x
}

While this is currently allowed by the type checker due to a bug, it should actually be a type error. The reason is that the result of the f function aliases M.zero (a global variable), which we do not want to allow. This is because the plus function does not declare its return type to be unique/alias-free, meaning it is allowed to alias either of its arguments. We may know that it is unlikely that a monoidal plus operation will do that, but the type checker does not. Worse, all of our builtin mathematical module types define their operations like this, and allow the result to alias the operands. Fixing this bug will require fixing a significant number of programs. Now, that's doable. The fix is to add an asterisk to the return types, indicating that the result is alias-free:

module type monoid = {
  type t
  val zero : t
  val plus : t -> t -> *t
}

...but to be honest, I think this adds a lot of visual clutter everywhere. I am considering whether we should change the default behaviour. Maybe t -> t should denote a function that does not alias any of its parameters (i.e make our current treatment of * in return types the default). We could then use another symbol, say @, to indicate that the result may alias the parameters (but still not global variables). For example, transpose would then be defined as

def transpose 'a [n] [m] (A: [n][m]a) : @[m][n]a = ...

This is based on the assumption (which I have not yet checked) that the common case is that functions return fresh results, and that aliasing is somewhat rare.

This is a pretty major bug that we should fix quickly, but the fix could have significant impact on the language. @melsman? @coancea? Anyone else? I'd like input.

[FluxusMagna]

I think your proposed solution seems quite reasonable. Having return values aliasing arguments require special syntax honestly makes more sense to me than the opposite (although I am rather used to the current system, which has worked well too). At any rate I agree avoiding clutter for the most common case is important, and not breaking code should not be prioritized over good long term design solutions.

edit: I would assume that rather few top level functions, that would be most likely to have an explicit type annotation, return values that alias their arguments, so I think impact on existing code is somewhat limited, and pretty easy to fix too.

[athas]

edit: I would assume that rather few top level functions, that would be most likely to have an explicit type annotation, return values that alias their arguments, so I think impact on existing code is somewhat limited, and pretty easy to fix too.

Unfortunately, closures also have aliases (their lexical environment). This means that programs that depend heavily on function-based representations, say a library for expressing neural networks, might be significantly affected. I don't yet have a full grasp of what the impact might be.

[FluxusMagna]

Unfortunately, closures also have aliases (their lexical environment). This means that programs that depend heavily on function-based representations, say a library for expressing neural networks, might be significantly affected. I don't yet have a full grasp of what the impact might be.

Didn't think of that. Well, as long as it's fixable by just changing type annotations, it's not too big of a deal for me (and by extension hopefully not for most people). If you are really worried about the impact on higher order functions and the like, you can make a test branch. I can be a subject.

[athas]

This is becoming more urgent. The tracking of aliases at the IR level is now good enough that it notices the things we let slip through the cracks in the frontend.