Skip to content

Latest commit

 

History

History
1575 lines (1116 loc) · 17.2 KB

infer-expr.md

File metadata and controls

1575 lines (1116 loc) · 17.2 KB

Type inference for expressions

What's the type of an ast::Expr?


Literals.

infer("int")

1

Blocks get the type of the last expression.

infer("fn () -> ()")

{ fn foo() {} }

Block ends with function

infer("fn () -> int")

{ fn foo() -> int { 1 } }

Block ends with function 2

infer("fn (int) -> int")

{ fn foo(bar: int) -> int { bar } }

Block ends with function 3

infer("fn (int, bool) -> int")

{ fn foo(bar: int, baz: bool) -> int { bar } }

Block ends with function 4

infer("fn (A, bool) -> A")

{ fn foo<T>(bar: T, baz: bool) -> T { bar } }

Sanity check: types must exist

errorContains("Type not found: T")

{ fn foo(x: T) -> T { x } }

Block ends with list

infer("fn () -> [int]")

{ fn foo() -> [int] { [1] } }

Block ends with generic list

infer("fn (A) -> [A]")

{ fn foo<Y>(bar: Y) -> [Y] { [bar, bar] } }

Generic arguments 1

errorContains("Wrong arity")

{ fn foo(bar: Result<string, int, bool>) {} }

Generic arguments 2

infer("fn () -> [[int]]")

{ fn foo() -> [[int]] { [[1]]} }

Generic arguments 3

errorContains("Wrong arity")

{ fn foo(bar: int<bool>) {} }

HKTs are not supported.

errorContains("Wrong arity")

{ fn foo<T>(bar: T<bool>) {} }

Populate scope with let bindings.

infer("int")

{
  let x = 5
  x
}

Function call with no arguments.

infer("string")

{ hello() }

Function call with arguments

infer("int")

{ sum(1, 4) }

Wrong arity #1

errorContains("arity")

{ hello(1) }

Wrong arity #2

errorContains("arity")

{ sum(1) }

Wrong param type

errorContains("mismatch")

{ sum("asdf", 1) }

Slice literals

infer("[int]")

{ [1,2,3] }

Slices are polymorphic

infer("[string]")

{
  let x = [1,2,3]
  list_push(x, 4)
  ["hello"]
}

It's possible to sanity-check the type of a value.

infer("[int]")

{
  let x = [1,2,3]
  @ensure x, [int]
  x
}

And the check should work!

errorContains("mismatch")

{
  let x = [1,2,3]
  @ensure x, bool
  1
}

Functions should get inferred correctly.

infer("fn <A, B>([A], fn (A) -> B) -> [B]")

list_map

Functions can take functions.

infer("[int]")

{
  let x = [1,2,3]
  list_map(x, inc)
}

Generics are applied correctly.

errorContains("mismatch")

{
  let x = ["hello"]
  list_map(x, inc)
}

Functions can be inlined.

infer("[int]")

{
  let x = [1,2,3]
  list_map(x, |n| sum(n, 5))
}

Closures can be inferred.

infer("fn (int) -> int")

|n| sum(n, 1)

Functions are in scope after declaration.

infer("int")

{
  fn foo(a: int) -> int { sum(a, 4) }
  foo(1)
}

Generic functions get instantiated at each use site.

infer("int")

{
  fn constant<T, Y>(a: T, b: Y) -> T { a }

  let x = constant("hello", 5)
  @ensure x, string
  let y = sum(constant(1, false), 5)
  @ensure y, int
  y
}

If expressions.

infer("int")

if true {
  1
} else {
  2
}

Condition must be a bool.

errorContains("mismatch")

if 12 {
  1
}

Both branches should have the same type.

errorContains("mismatch")

if true {
  1
} else {
  "hello"
}

Match expressions.

infer("string")

match 1 {
  1 => "foo",
}

Patterns in a match arm should unify with subject.

errorContains("mismatch")

match 1 {
  1 => "foo",
  false => "foo",
}

Wildcard matches.

infer("string")

match 1 {
  1 => "foo",
  _ => "foo",
}

All arms should have the same type.

errorContains("mismatch")

match 1 {
  1 => "foo",
  2 => false,
}

Aliasing in a match arm.

infer("string")

match 1 {
  1 => "foo",
  foo => int_to_string(foo),
}

Match and If are still expressions.

infer("int")

{
  let x = "foo"

  let a = match x {
    "foo" => 1,
    _ => 99,
  }

  let cond = false

  let b = if cond {
    0
  } else {
    1
  }

  sum(a, b)
}

Unit type.

infer("()")

()

Tuples.

infer("(int, int)")

(1, 2)

Tuples with wrong type annotation.

errorContains("mismatch")

@ensure ("foo", 2), (bool, int)

Tuples with wrong arity.

errorContains("mismatch")

@ensure (1, 2, 3), (int, int)

Tuples as function arguments.

infer("fn ((int, bool)) -> int")

{
  fn foo(t: (int, bool)) -> int {
    fst(t)
  }
}

Tuples as return type.

infer("fn () -> (string, bool)")

{
  fn foo() -> (string, bool) {
    ("foo", true)
  }
}

Typing callbacks.

infer("string")

{
  fn foo( f: fn (i: int) -> string, x: int ) -> string {
    f(x)
  }

  foo(|x| int_to_string(x), 1)
}

Callbacks with generics

infer("[int]")

{
  fn another_map<A, B>( f: fn (x: A) -> B, xs: [A] ) -> [B] {
    // mimics implementation
    let first = list_head(xs)
    [f(first)]
  }

  let a = another_map(|x| int_to_string(x), [1,2,3])
  @ensure a, [string]

  another_map(|x| sum(x, 1), [1,2,3])
}

Enums should introduce a new type in the environment.

infer("Color")

{
  enum Color { Red }
  Color.Red
}

Enums with generics should get instantiated.

infer("Maybe")

{
  enum Maybe<T> { Just(T), None }
  Maybe.Just(1)
}

Enum variants get instantiated correctly.

infer("Maybe")

{
  enum Maybe<T> { Just(T), None }

  @ensure Maybe.Just(1), Maybe<int>
  @ensure Maybe.Just("foo"), Maybe<string>
  @ensure Maybe.None, Maybe<bool>
  @ensure Maybe.Just(Maybe.Just(1)), Maybe<Maybe<int>>

  Maybe.None
}

Pattern matching works on enums.

infer("string")

{
  enum Color { Red, Blue(string) }

  let x = Color.Blue("foo")
  match x {
    Color.Red => "bar",
    Color.Blue(c) => str_concat(c, "!"),
  }
}

Pattern matching constructor arity.

errorContains("arity")

{
  enum Color { Red, Blue(string) }

  match Color.Blue("foo") {
    Color.Red => "bar",
    Color.Blue(c, nope) => c,
  }
}

Generic enums can be pattern matched.

infer("int")

{
  enum Maybe<T> { Just(T), None }

  let x = Maybe.Just(1)
  match x {
    Maybe.Just(v) => v,
    Maybe.None => 2,
  }
}

Nested pattern matching is supported.

infer("Color")

{
  enum Maybe<T> { Just(T), None }
  enum Color { Red, Blue(string, bool) }

  let c = Color.Blue("foo", false)
  let x = Maybe.Just(c)

  let n = match x {
    Maybe.Just(Color.Blue(s, b)) => {
      @ensure s, string
      @ensure b, bool
      1
    },
    Maybe.None => 2,
  }

  @ensure n, int

  match x {
    Maybe.Just(x) => x,
    Maybe.None => Color.Red,
  }
}

Enums can be returned from functions.

infer("fn (A) -> Maybe")

{
  enum Maybe<T> { Just(T), None }

  fn ok<T>(v: T) -> Maybe<T> {
    Maybe.Just(v)
  }

  @ensure ok(1), Maybe<int>
  @ensure ok("foo"), Maybe<string>

  ok
}

Enums from functions II.

infer("int")

{
  enum Maybe<T> { Just(T), None }

  fn foo(b: int) -> Maybe<int> {
    Maybe.None
  }

  @ensure foo(1), Maybe<int>

  fn bar(b: int) -> Maybe<int> {
    Maybe.Just(b)
  }

  match @ensure foo(2), Maybe<int> {
    Maybe.Just(x) => x,
    Maybe.None => 3,
  }
}

Enums from functions (error).

errorContains("mismatch")

{
  enum Maybe<T> { Just(T), None }

  fn foo(b: int) -> Maybe<string> {
    Maybe.Just(b)
  }
}

Defining structs.

infer("Foo")

{
  struct Foo { a: int }

  Foo { a: 1 }
}

Generic structs.

infer("Foo")

{
  struct Foo<T> { a: T }

  Foo { a: 1 }
}

Generic structs with multiple params.

infer("Foo<int, bool>")

{
  struct Foo<T, Y> { a: T, b: Y, c: T }

  Foo { a: 1, b: false, c: 3 }
}

Structs with not enough arguments.

errorContains("Missing fields")

{
  struct Foo { a: int, b: int }

  Foo { a: 1 }
}

Structs with too many arguments.

errorContains("field not found")

{
  struct Foo { a: int, b: int }

  Foo { a: 1, b: 2, c: 3 }
}

Accessing struct fields.

infer("int")

{
  struct Foo { a: int }

  let x = Foo { a: 1 }
  x.a
}

Error when reassign to wrong type.

errorContains("mismatch")

{
  let mut x = 1
  x = "foo"
}

Error when updating structs.

errorContains("mismatch")

{
  struct Foo { a: int }

  let mut x = Foo { a: 1 }
  x.a = "foo"
}

Structs can be updated

infer("Foo")

{
  struct Foo { a: int }

  let mut x = Foo { a: 1 }
  x.a = 3
  x
}

Structs need mutability

errorContains("mutable")

{
  struct Foo { a: int }

  let x = Foo { a: 1 }
  x.a = 5
}

Nested struct update

infer("Bar")

{
  struct Foo { x: int }
  struct Bar { f: Foo }

  let mut b = Bar { f: Foo { x: 1 } }
  b.f.x = 99
  b
}

Spreading a struct into another.

infer("Foo")

{
  struct Foo { a: int, b: string }

  let x = Foo { a: 1, b: "foo" }
  Foo { b: "bar", ..x }
}

Error when spreading in different structs.

errorContains("mismatch")

{
  struct Foo { a: int, b: string }
  struct Bar { a: int, b: string }

  let x = Foo { a: 1, b: "foo" }
  let y = Bar { a: 1, b: "bar" }
  Foo { b: "bar", ..y }
}

Nested updates.

infer("Bar")

{
  struct Foo { a: int, b: string }
  struct Bar { a: int, b: string, f: Foo }

  let x = Foo { a: 1, b: "foo" }
  let y = Bar { a: 1, b: "bar", f: x }
  Bar { a: 2, b: "baz", f: Foo { a: 4, ..x } }
}

Let bindings with annotation.

errorContains("mismatch")

{
  let x: [int] = [1,2,3]
  let y: [bool] = [1,2,3]
}

Return statements should unify.

infer("fn () -> int")

{
  fn foo() -> int {
    let x = 5
    return x
  }
}

Early return statements should unify with return type.

errorContains("mismatch")

{
  fn foo() -> int {
    if true {
      return "foo"
    }

    return 1
  }
}

Multiple early return all unify.

errorContains("mismatch")

{
  fn foo() -> int {
    if true {
      return 1
    }

    if true {
      return "bar"
    }

    2
  }
}

A function within a function gets its own return type.

infer("fn () -> int")

{
  fn foo() -> int {

    fn bar() -> string {
      if true {
        return "foo"
      }

      "bar"
    }


    @ensure bar(), string

    return 2
  }
}

Can't have return statements outside of functions.

errorContains("return")

{
  return false
}

Errors must be of the same type.

errorContains("mismatch")

{
  fn foo() -> Result<(), ErrFoo> {
    if true {
      return Err(ErrFoo.A)
    }

    Err(ErrBar.X)
  }
}

Function calls with different errors don't unify.

errorContains("mismatch")

{
  fn foo1() -> Result<int, ErrFoo> { Err(ErrFoo.A) }
  fn foo2() -> Result<int, ErrFoo> { Err(ErrBar.X) }
  fn bar() -> Result<int, ErrFoo> {
    foo1()?
    foo2()?
    Ok(1)
  }
}

Functions with no error get inferred ok.

infer("[int]")

{
  list_map([1,2,3], |x| sum(x, 1))
}

Callbacks with errors are automatically wrapped into a Result.

infer("[Result<int, ErrFoo>]")

{
  fn foo(x: int) -> Result<int, ErrFoo> {
      return Err(ErrFoo.A)
      Ok(x)
  }
  list_map([1,2,3], foo)
}

Callbacks with different error types can still be passed to the same function.

infer("bool")

{
  fn foo() -> Result<int, ErrFoo> { Err(ErrFoo.A) }
  fn bar() -> Result<int, ErrBar> { Err(ErrBar.X) }

  fn baz(f: fn () -> Result<int, ErrFoo>, g: fn() -> Result<int, ErrBar>) {
    ()
  }

  @ensure foo, fn () -> Result<int, ErrFoo>
  @ensure bar, fn () -> Result<int, ErrBar>

  baz(foo, bar)
  true
}

A function that is already wrapped, doesn't get wrapped again.

infer("bool")

{
  fn foo(x: int) -> Result<string, ErrFoo> { Err(ErrFoo.A) }

  fn bar(f: fn (x: int) -> Result<string, ErrFoo>) {
    ()
  }

  bar(foo)
  true
}

The ? operator can only be used in functions that return a Result.

errorContains("mismatch")

{
  fn foo() -> Result<int, ErrFoo> { Ok(1) }
  fn bar() {
    let x = foo()?
    ()
  }
}

Equality

infer("bool")

{
  let a = 1
  let b = 2
  a == b
}

Can shadow vars in block

infer("string")

{
  let a = "mutable"
  {
    let a = "block"
  }
  a
}

Math operands on ints

infer("int")

{ 1 + 5 }

Wrong type in operands

errorContains("numeric type")

{ 1 + false }

boolean operators

infer("bool")

{ (1 == 2) && (false || true) }

Match weirdness

infer("bool")

{
    match false {
        true => print("asdf"),
    }

    match 1 {
        1 => false,
    }
}

Match Type.Fun with Type.Con

errorContains("mismatch")

{
  fn bar() -> bool { false }
  fn foo() -> int {
    bar
  }
}

Negative numbers

infer("int")

5 * -3

Negate expressions

infer("bool")

!false

Neg only works with numbers

errorContains("numeric type")

-false

Not only works on bools

errorContains("mismatch")

!"asf"

Generic function arguments should not get instantiated

errorContains("mismatch")

{
  fn foo<T>(x: T) -> int {
    @ensure x, T
    match x {
      1 => 1
    }
  }
}

Sanity check, can't make up types out of thin air

errorContains("not found")

{
  fn foo<T>(x: Y) -> int {
    1
  }
}

Characters

infer("rune")

'a'

Tuple fields

infer("int")

{
  let a = (1, "a")
  a.0
}

Sanity check: can't invent constructors in pattern match

errorContains("Green not found")

{
  enum Color { Red, Blue }

  match Color.Red {
    Red => 1,
    Green => 2,
  }
}

Struct inference in lambdas

infer("[string]")

{
  struct Foo { a: int, b: string }

  let f = Foo { a: 1, b: "a" }
  list_map([f], |x| str_concat(x.b, "!"))
}

Generics should get instantiated to the same type in pattern match

errorContains("mismatch")

{
  enum Foo<T> {
    Bar(T),
    Baz(T),
  }

  match Foo.Bar(12) {
    Bar(x) => {
      let a = x + 1
      int_to_string(a)
    },

    Baz(y) => str_concat(y, "doh"),
  }
}

Floats

infer("float64")

9.12

Math ops with floats

infer("float64")

1.3 + 5.2

Operands between floats and ints

infer("float64")

3.1 * 4

Plus operator works with strings

infer("string")

"a" + "b"

Bidirectional inference for closure params

infer("int")

{
  struct Foo { a: int }

  fn bar<T, Y>(start: T, f: fn (x: T) -> Y) -> Y {
    f(start)
  }

  bar(Foo { a: 1 }, |x| x.a)
}

Struct patterns

infer("int")

{
  struct Foo { x: int, y: string }

  let f = Foo { x: 1, y: "a" }
  match f {
    Foo { x, y } => x
  }
}

Tuple patterns

infer("int")

{
  fn foo((x, y): (int, string)) -> int { x }
  foo((1, "a"))
}

Pattern with too many arguments

errorContains("mismatch")

{
  fn foo((x, y, z): (bool, bool)) -> bool { x }
  foo((false, false))
}

Tuple patterns in let bindings

infer("int")

{
  let (x, y) = (1, "a")
  x
}

Tuple patterns in match arms

infer("string")

{
  match (2, "b") {
    (_, y) => y,
    _ => "c",
  }
}

Parse unit type

infer("fn (()) -> ()")

{
  fn foo(x: ()) { () }
}

Missing methods give the target type.

errorContains("Foo has no field or method: bar")

{
  struct Foo<T> { x: T }
  let f = Foo{ x: 34 }
  f.bar()
}

Pattern matching on structs

infer("bool")

{
  struct Foo { x: int, y: string }

  let f = Foo{ x: 34, y: "yo" }
  match f {
    Foo { x, y: "bar" } => false,
    Foo { x: 34, y: "bar" } => false,
    Foo { x, y } => true,
  }
}

Not equal operator

infer("bool")

{
  1 != 2
}

Tuple fields II

infer("[string]")

{
  struct Foo<T> { x: int, y: [T] }
  let a = Foo { x: 1, y: ["yo"] }

  @ensure a.x, int
  a.y
}

Struct patterns on generic structs

infer("[string]")

{
  struct Foo<T> { x: int, y: [T] }
  let a = Foo { x: 1, y: ["yo"] }

  match a {
    Foo { x: 1, y } => y,
    _ => ["asdf"],
  }
}

Unit pattern match arm

infer("int")

match () {
  () => 1,
}

No method found error

errorContains(".bar")

{
  struct Foo {}
  let f = Foo {}

  f.bar()
}

Mutable variables

infer("int")

{
  let mut x = 0
  x = x + 1
  x
}

Only mutable variables can be mutated

errorContains("y is not declared as mutable")

{
  let y = 0
  y = 3
}

Functions can take mutable params

infer("int")

{
  fn foo (a: int) -> int {
    a = a + 1
    a
  }

  foo(1)
}

If statements skip unification

infer("int")

{
  let n = 0

  if true {
    n + 1
  }

  if false {
  }

  1
}

Reference types

infer("int")

{
  struct Bar { x: int }

  fn foo(a: *Bar) -> int {
    a.x
  }

  foo(&Bar{ x: 1 })
}

Slice syntax in types

infer("fn ([int]) -> ()")

{
  fn foo(x: [int]) {}
}

Result type must have one type param.

errorContains("Wrong arity")

{
    fn foo() -> Result {
      Ok(1)
    }
}

Statements can't be returned

errorContains("Type mismatch")

{
    fn foo() -> Result<(), string> {
        for i in [] {}
    }
}

Explicit return value when function returns Result<()>

errorContains("Type mismatch")

fn foo() -> Result<(), string> {
    let a = 1
}