Add Type Aliases

[macrologist]

Is there any desire for type aliases? Are they feasible? If they are, are there reasons to not support them?

E.g.

(define-alias Thing (Optional (Tuple String Integer)))

(define-alias (NormalResult :t) (Result String :t))

[eliaslfox]

There has been desire for type aliases. Implementing type aliases that expand early shouldn't be very difficult. Part of the reason I held off from implementing them, is I wanted to see if having GHC's type alias semantics was possible.

Compare the following two rather contrived programs:

enum T {
    T,
}

type T2 = T;

fn main() {
    let x: T2 = T::T;
    let y: T2 = T::T;

    x == y;
}

module Main where

data T = T

type T2 = T

main = do
  let x = (T :: T2)
  let y = (T :: T2)
  let _ = x == y
  pure ()

In both cases the program fails to compile because T doesn't implement Eq. In Rust's case the error looks like this:

error[E0369]: binary operation `==` cannot be applied to type `T`
  --> src/main.rs:11:7
   |
11 |     x == y;
   |     - ^^ - T
   |     |
   |     T
   |

In GHC the error looks like this:

main.hs:10:13: error:
    • No instance for (Eq T2) arising from a use of ‘==’
    • In the expression: x == y
      In a pattern binding: _ = x == y
      In the expression:
        do let x = (T :: T2)
           let y = (T :: T2)
           let _ = x == y
           pure ()
   |
10 |   let _ = x == y
   |             ^^

Note that Haskell tracks that the variables x and y were annotated as the type alias T2 and displays that as their type in the error message.

OTOH we could definitely implement eagerly expanding type aliases and then try to figure out the error messages later.

[macrologist]

The convenience of type aliases definitely feels secondary to preserving the helpfulness of error messages.

[Izaakwltn]

Type Aliasing Proposal

This provides a grammar, proposed promises, examples, error examples, and thoughts for implementing type aliases in Coalton.

Proposed syntax:

Grammar:

toplevel-define-alias := "(" "define-alias" identifier ty docstring? ")"

A few examples:

(define-alias Index UFix 
  "An Index is a UFix") ;; optional docstring

(define-alias Basket (Vector Item)
  "A shopping basket filled with Item(s).")'

(define-alias int-transformation (Integer -> Integer)) ;; also works for arrow types

Invalid uses

;; no free variables
(define-alias Bucket (Vector :Fish)
  "A misguided attempt to fill a bucket with any one type of fish.")

;;no class constraints
(define-alias Number (Num :a => :a))

Proposed behavior:

• An alias points to an existing type or struct.

• Aliases occupy the same namespace as structs and types, and thus signal naming collisions within the namespace. (This may be revelant to ongoing murmurs about redefinition in Coalton.)

• You can alias an alias. (Note: this will make a new alias pointing to the same base-type and may not retain the original alias).

• Self-recursion is invalid.

• Mutual recursion between aliases is invalid.

• Class instances should only be definable on base-types, not aliases.

• Performing type-of on a variable that is an instance of an alias should return the name of the alias (maybe also base-type).

• Aliases should be exportable like other package symbols.

Proposed error behavior:

Example 1: Unresolved Constraint

(coalton-toplevel
  (define-alias Number-Word String
    "A string representing a number.")

  (declare word-sin (Number-Word -> Number-Word))
  (define (word-sin word)
    (sin word)))

Potential compilation output with minimal changes:

   |
 1 |  (COALTON (word-sin "seven"))
   |           ^^^^^^^^^^^^^^^^^^ expression has type ∀. (TRIGONOMETRIC NUMBER-WORD) => NUMBER-WORD with unresolved constraint (TRIGONOMETRIC STRING)
   |           ------------- Add a type assertion with THE to resolve ambiguity
   |  Note: Number-Word aliases String

Example 2: Type Mismatch

(coalton-toplevel
  (define-alias Index UFix)

  (declare add-3 (Index -> Index))
  (define (add-3 i)
    (+ 3 i))

  (coalton (add-3 "two")))

Should return:

  read-error: 
    COMMON-LISP:READ error during COMMON-LISP:COMPILE-FILE:

      error: Type mismatch
      --> unification.lisp:1:16
       |
     1 |  (coalton (add-3 "two"))
       |                  ^^^^^ Expected type 'INDEX' but got 'STRING'
       | Note: Index aliases UFix

      (in form starting at line: 1, column: 0, position: 0)

Compilation failed.

Example 3: Unknown Instance

(coalton-toplevel

  (define-type (Basket :a)
    (Contents (List :a)))

  (define-alias Fish-Bucket (Basket Fish))

  (declare bucket-map ((:a -> :b) -> Fish-Bucket -> Fish-Bucket))
  (define (bucket-map f x)
    (map f x))

  read-error: 
    COMMON-LISP:READ error during COMMON-LISP:COMPILE-FILE:

      error: Unknown instance
      --> unification.lisp:8:5
       |
     8 |      (map f x)))
       |       ^^^ Unknown instance FUNCTOR BASKET
       |  Note: Fish-Bucket aliases (Basket Fish)

      (in form starting at line: 1, column: 0, position: 0)

General implementation plan:

Add an alias-environment, which will be queried along with the other environments (type and struct) to prevent duplication and other issues.