# Type system brainstorming

Types we need:
- Primitives: number (int, float), bool, string
- `$null`
- `any` - simultaneously the subtype and supertype of all types (for breaking the type system)
- Lists
- Records
- Tables
- Ranges
- Streams
- Closures (monomorphic)
- Union types
- Plus a nullable/optional type

Types that would be good to have:
- String literals
- Separate "sealed" and "unsealed" records
- Sealed record `{a: int}` does not allow `{a: 1, b: 2}`
- Unsealed record `{a: int, ...}` allows `{a: 1, b: 2}`
- Tuple type - two options:
- TypeScript-like tuple types (sealed lists)
- `[...C]` equivalent to `list<C>`
- `[A, B, C]` for a tuple `(a, b, c)`
- `[A, B, ...C]` for an `A` and a `B` prepended to a `list<C>`
- Tuple type entirely separate from lists (separate syntax)
- User-defined ADTs - no inheritance
- If ADTs have type parameters, we'll need the ability to mark type parameters as being covariant or contravariant
- User-defined classes

## Possible features

### Type aliases

- Type aliases without type parameters shouldn't be too hard, and are probably a must-have.
- Type aliases with type parameters are harder but probably still worth it.

Options for dealing with recursive type aliases:
- We detect them and produce an error
- During typechecking, we carefully expand type aliases only one layer at a time as necessary.

### Generics (type parameters) for custom commands

I'm not sure there's any reasons against this. Subtype bounds on type parameters would be useful, perhaps supertype bounds too.

### Command overloading

Pros:
- Sometimes you just gotta use the same name for two slightly different things
- One way to deal with commands having multiple output types

Cons:
- Possible to accidentally call the wrong overload of your command
- Makes type inference harder

### Type-level operations

There's a lot of different operations we could have on types that could go into this category. One big one would be accessing fields of record types. Useful for typing `get`:

# Ignore the syntax, it just means K needs to be a string literal
def typed-get<R, K extends literal>[ k: K ] : R -> Get<R, K> {
  $in | get $k
}

{ a: 1 } | typed-get a # type of expression is int

## Less practical possible features

Just spitballing here. This is mostly spit, very little balling.

These features are too fantastical to put directly into Nushell, but perhaps we could add something like them. These are mostly to deal with commands having multiple output types.

### Flow typing

Pros:
- Helps deal with the fact that commands can have multiple output types depending on the pipeline input type

Cons:
- Probably very hard to implement
- Overkill most of the time. TypeScript does make heavy use of it, but that's partially because of JavaScript

### Match types

Pros:
- Can be used for commands with multiple output types

Cons:
- Overkill
- Makes type inference harder
- Makes signatures more complicated for users

Without match types:

def foo [] : [int -> string, float -> float] {...}
# bar needs to repeat the same signature
def bar<A> [] : [int -> string, float -> float] {
  ...
  foo
}

With match types:

type MultiType<A> = match A {
  int => string,
  float => float,
}
def foo<A> [] : A -> MultiType<A> {...}
# bar doesn't need to repeat the signature, it can just use the match type
def bar<A> [] : A -> MultiType<A> {
  ...
  foo
}

### Higher-kinded types

Pros:
- Helps get rid of multiple output types for some commands

Cons:
- Overkill
- Makes type inference harder