A secondary "type system" for references?

Question

I'm designing a language and was wondering how to incorporate C++-like references with regards to their place in the type system. I think they're useful for operations like indexing and dereferencing (v[i] returns a reference that can be assigned to, *pointer_type<a> returns a reference to an a that behaves like an a).

Nominally in C++, a reference type like int& and its original type int are two distinct types. However, I believe that this is inconsistent with the rest of the type system: an int& can be substituted for int and they sometimes behave as they were the same type, and sometimes they don't, without explicit conversions (which is one of the reasons why references are used in the first place).

My solution would be for bindings and function arguments to essentially have a "secondary type", or rather another qualification with special rules, determining whether they are references or not. There would be two types in this secondary type system: ref and non-ref (default), and these labels would be written in places where other similar labels like const (or mut) would be -- mainly when introducing new bindings or in function types.

Thus, along with classical type mismatch errors, the compiler would report something like mismatched binding mechanism as well. For example this would happen if the programmer attempted to place a function which accepts a single integer by-reference into a list of functions which accept it by-copy (ref a -> b vs. a -> b). Although the functions would have the same type: a -> b, the binding mechanisms are incompatible (because if passed lvalues that are later assigned to, unexpected incompatible behaviour could occur).

Does this solution make sense or is it better to just wrap it in the type system and suffer inconsistencies? Are there some negative side-effects that I'm not anticipating?

---

To clarify: the touching points between these two type systems would have special rules. For example, there would be implicit conversions from ref to non-ref while keeping the type invariant.

Answer 1

C++ treats int, const int, int&, and const int& as separate types with ways to convert to/from each type (except to const int or to const int&). If you know what types you have and what types are expected, then given a list of converters, you know if you can make each passed parameter pass as an argument parameter.

Since there may also be custom converters (overloading operator =), you can simply add this to the list of converters and apply the same rules. The biggest advantage of this approach is simplicity.

If you decide that int, const int, int&, and const int& are all the same, then const and & then become modifiers of that type. It might be a very smart idea to come up with a way of creating custom type modifiers which declares how that type can convert to the normal type, and then using this method to create predefined type modifiers like & and const.

The compiler would then attempt to convert from one modifier to "normal" type and from normal type to the modifier present in the method argument. If it is missing the proper conversion, then it is not the method being called (and if no such methods found, then compiler would throw an error).

For instance to call a method void doSomething(int& val) by passing to it a const int valToPass, your compiler would attempt to first convert const int valToPass to int valToPass, but no conversion would exist, and so you wouldn't call that method. However calling doSomething(const int val) with int& valToPass would be called because there would exist a converter from int& valToPass to int valToPass, and from int valToPass to const int valToPass.

A const int& type would simply be connected to the existing int & which behaves in a similar fashion, except that from the normal type int, it must first be convertible to int & before it can convert to const int&.

In all these examples I'm using int, but these declarations would hold for all types. The point is that the programmer using your language could create custom extensions using their keywords (so long as it doesn't conflict with existing type modifiers or keywords).

I would stay away from a secondary type, because that implies that there will necessarily be exactly two, and there is already const and & to consider, but I think that you're moving in the right direction.

I hope that helps!

Answer 2

I think here it is fruitful to consider how mutable references work in the ML/Haskell family of languages. In these languages, there are explicit, generic types whose values are mutable references. I'll use Haskell because that's what I know better, but ML has similar ideas.

Take for example the STRef type in Haskell:

• https://hackage.haskell.org/package/base-4.8.1.0/docs/Data-IORef.html

We can use this (and a few other tools) to, for example, sum the elements of a list in the same manner you'd do in an imperative language:

import Data.Foldable (Foldable, for_)
import Data.IORef

imperativeSum :: (Foldable t, Num a) => t a -> IO a
imperativeSum numbers = do
    ref <- newIORef 0        -- Allocate mutable cell, initialize with `0`
    for_ numbers $ \i -> do  -- Loop over the numbers, with `i` as loop var
      modifyIORef' ref (+i)  -- Mutate the cell by adding `i` to its content
    readIORef ref            -- Read final value of the cell and return it

Here, the type of the ref variable is Num a => IORef a—a mutable reference to a value of type a (which must be a Number). Haskell is completely strict about the fact that the IORef and its content are different values with different types—an IORef Int is not the same type as an Int. So the type system automatically prevents you from using one in a context where the other is expected.

Note the operations available for an IORef are:

1. Creating a new IORef, with an initial value (obligatory)
2. Reading the current content of an IORef
3. Mutating the content of an IORef
4. Comparing two IORefs for equality ("are these two references to the same memory location").

Also note that IORef is just a generic type with some operations, and the language doesn't privilege it at all. There are other similar types that provide for different types of references:

• STRef: special reference type for use in computations that use mutation internally but don't have externally observable side effects.
• TVar: reference type used in software transactional memory computations. See Simon Peyton Jones' paper on Haskell STM for a demonstration.

Answer 3

There are certain things that cannot be considered separately. In other words, there are certain things that are not orthogonal at all.

Firstly, think about how your type system will allow the implementation of pure functions.

A pure function shouldn't care about whether the inputs are values, ref's, or other pure functions that promise to provide the same type of values.

A pure function won't be able to call any non-pure functions. Don't allow any way around this.

Secondly, think about how your type system will provide useful information to your compiler to enable it to deduce the lifetime of objects - to check that it is valid throughout a function call, to borrow it, to extend it outside the current scope, to garbage-collect or reference-count it, or something else. In the case of multithreading, you may also need to track whether there might be concurrent (overlapping) modifications to it.

The C++ type system is the result of taking most of the above into consideration (excluding threading). It is the result of observing what would make sense and what would not. Still, many people can find out and complain about ways in which the safety of C++ type system can be defeated.

Once you have made some decisions about these two aspects, you can think about the type system for the handling of arguments for non-pure functions.

Answer 4

they sometimes behave as they were the same type, and sometimes they don't, without explicit conversions (which is one of the reasons why references are used in the first place).

No they don't. An int & (basically an int lvalue) can be implicitly converted to an int (an rvalue), but not the other way around.