Protocols

Motivation

Clay currently allows protocols (or concepts or type classes, if you prefer) to be defined in an ad-hoc way, using CallDefined?:

   ForwardCoordinate?(T) = CallDefined?(dereference, T) and CallDefined?(inc, T);

While this works, it leaves the compiler with very little semantic information for error reporting or debugging—it can only report that the pattern match failed, not why. The CallDefined? syntax is also abstracted from actual expression syntax. First-class language support for protocols and function definition syntax for protocol-following types would allow for improvements in compiler error reporting and code readability, and would reduce boilerplate in common function definition cases.

Proposed implementation

There's plenty of prior art in designing the semantics of type constraints (ConceptC++, type classes in Haskell + the various GHC extensions, .NET generics, among others). The primary question in bringing them to Clay is syntax. We need a pattern matching form for constraining a pattern variable (such as "'X of Protocol") and forms for defining protocols (perhaps in both automatically-derived and formal forms), refinements of protocols, and formal instances of protocols.

Protocol definitions

A good spot-test is the sequence/iterator/coordinate family of protocols. Here's a theoretical definition of those protocols, using forall <pattern> of <ProtocolName>[<..ProtocolArgs>] { } as the syntactic form for protocol definitions, and <pattern> of <Protocol> as the pattern syntax for constrained pattern variables.

  forall 'I of IteratorType['E] {
      // required operations
      next(i:'I) : 'E;
      hasNext?(i:'I) : Bool;

      // derived definitions
      #IteratorTargetType('I) = 'E;
  }
  
  forall 'S of SequenceType['I of IteratorType] {
      // required operations
      iterator(x:'S) : 'I;
      
      // derived definitions
      #SequenceIteratorType('S) = 'I;
      #SequenceElementType('S) = IteratorTargetType('I);
  }

  forall 'C of CoordinateType['E] {
      dereference(c:'C) : 'E;
      inc(ref c:'C) : ;
      dec(ref c:'C) : ;
  
      #CoordinateTargetType('C) = 'E;
  }

  forall ('C of CoordinateType['E]) of RandomAccessCoordinateType['E] {
      add(c:'C, i:'I of IntegerType) : 'C;
      subtract(c:'C, i:'I of IntegerType) : 'C;
      subtract(c:'C, c:'C) : Int;
  }
  
  forall 'S of CoordinateSequenceType['C of CoordinateType['E]] {
      begin(s:'S) : 'C;
      end(s:'S) : 'C;

      #SequenceCoordinateType('S) = 'C;
  }

One weakness of this proposed syntax is that the use of both "of " in the protocol definition form and as a pattern expression leads to the somewhat awkward "forall ('X of Root) of Refined" construct for defining a refined protocol (the inner "of" constraining the input pattern, and the outer "of" making up the syntax of the outer definition).

Formal instances

Formal instance definitions should look similar to protocol definitions:

    instance ('S of CoordinateSequenceType['C]) of SequenceType[CoordinateRange['C]] {
        // define members of protocol
        // The :'S type qualification on x is implicit from the protocol definition
        iterator(x) = CoordinateRange(begin(x), end(x));
    }

Implicit vs. formal protocol membership

If functions are defined within a protocol definition form, then those functions should only be definable as part of an instance definition. Types thus could only become instances of protocols with a formal instance definition. The "overload" keyword can be used within a protocol definition to indicate that an already-defined function with ad-hoc overloading is part of a protocol, allowing for implicit protocol membership:

    symbol foo?;
    forall 'T of FooType {
        overload foo?(x:'T, y:Int) : Bool;
    }
    overload foo?(x:Foo, y:Int) = x[y] == 0; // Foo is now implicitly an instance of FooType

Discussion

Please add comments here.