How to represent linear types in C#/.Net?

Question

Is there a reasonable way to express the concept of a linear type in .Net (Compact Framework/desktop 3.5 common subset), in such a way that (a) the required syntax doesn't become overly verbose, convoluted, or otherwise painful and (b) the invariant can be either enforced at run time or validated by code analysis at compile time (so a maintenance programmer in an all-fired hurry can't just blithely ignore the invariant)? The idea here is to avoid the need for defensive copying of command objects at subsystem boundaries.

Answer 1

There are two kinds of types in .Net: reference types and value types.

When you copy a reference type by assigning it to another variable, just the reference is copied.

When you copy a value type, the whole content of the type is copied, byte by byte.

In both cases, there is no way to prevent, modify or get notification about it (in contrast with C++'s copy constructors). What that means is that you can't implement linear types in .Net.

Your can instead use immutable (or freezable) type, as others suggested.

Answer 2

Linear types, based on the theory of linear logic, and closely related to uniqueness types, are types assigned to values having the property that they have one and only one reference to them at all times. These are valuable for describing large immutable values such as files, strings, and so on.

An immutable type is one whose internal state cannot change after it has been instantiated.

A ‘deeply immutable’ type is one whose dependency graph contains reference types that are also ‘deeply immutable’. If dependant reference types are not themselves ‘deeply immutable’, the type is termed ‘shallow immutable’.

In C# we work with reference types and value types. Instances of reference types can be shared between disparate concurrently executing code, whereas value types are stack bound (unless boxed), copied on sharing and therefore autonomous, although not immutable (and may contain dependencies on other reference types which are then ‘copy shared’).

Although the ability to share a reference type is undoubtedly a powerful feature of object orientated frameworks, in the world of Enterprise development it should also be considered one of its main weaknesses and used with extreme caution. Anything that cannot be executed atomically exposes fragility and an opportunity for interleaving bugs to intermittently wreak havoc.

In C# the best we can do is describe our intentions. Immutability can be partially implemented by marking a types entire internal state as private and readonly. Deep immutability cannot be enforced (nor for that matter can shallow) so it is up to the developer to stick to the intentions. Changes to the state is through static methods that return new instances of the type containing the requested state.

public sealed class PersonImmutable {

    private readonly int _age;
    private readonly string _name;

    public PersonImmutable(int age, string name) { 
        this._age = age;
        this._name = name;
    }

    public int Age {
        get { return this._age; }
    }

    public string Name {
        get { return this._name; }
    }

    public static PersonImmutable NotifyBirthday(PersonImmutable source) {
        return new PersonImmutable(1 + source.Age, source.Name);
    }
}

Answer 3

The provided link really defines LinearVariable, which could be defined similar to this:

Option Explicit On
Option Strict On
Option Infer On 

<System.Diagnostics.DebuggerDisplay("{_state}: {_value}")> _
Class LinearVariable(Of T)
  Private Enum State
   Unassigned
   Assigned
   Used
 End Enum
 Private _state As State = State.Unassigned
 Private _value As T
 Public Sub New()
  'Allow creation and later assignment
 End Sub
 Public Sub New(ByVal Value As T)
  _value = Value
  _state = State.Assigned
 End Sub
 Public Shared Widening Operator CType(Value As T) As LinearVariable(Of T)
  Return New LinearVariable(Of T)(Value)
 End Operator
 Public Shared Widening Operator CType(Value As LinearVariable(Of T)) As T
  Return Value.Value
 End Operator
 Public Property Value As T
  Get
   If _state = State.Assigned Then
    _state = State.Used
#If DEBUG Then
    Return _value
#Else ' Release - free the reference immedately after use
    value = _value
    _value = Nothing
#End If
   End If
   If _state = State.Unassigned Then _
    Throw New NullReferenceException("LinearVariable is unassigned")
   If _state = State.Used Then _
    Throw New AccessViolationException("LinearVariable has already been accessed")
   Throw New InvalidOperationException
  End Get
  Set(ByVal Value As T)
   ' May want to check _state, although the "definition" at http://c2.com/cgi/wiki?LinearTypes seems to allow multiple writes
   _value = Value
   _state = State.Assigned
  End Set
 End Property
End Class

_{(This has been compiled but untested.)}

This obviously only works at run time. I cannot think of any way of trying to enforce exactly one use of .Value at compile time.

Note that you could make LinearVariable IDisposable and then catch at run time when its value is set and not used.