Outer join

[julianhyde]

In #72 we added join, with new join and on keywords, and in this case we add outer join, with left, right and full keywords.

Representing extra rows as option

The hardest question is how we represent the extra rows that are generated by outer joins. In SQL, these extra rows are represented by rows whose column values are all NULL. Morel does not have NULL values, so we use optional. Thus the type of

from d in depts
  left join e in emps on d.empno = e.deptno

is {d:{deptno:int, dname:string} option, e: {empno:int, ename:string, deptno:int}} list. Note that d is optional and e is not.

In the on clause neither d nor e are optional.

Writing predicates on option values is a bit verbose:

from d in depts
  left join e in emps
  where case e of SOME e2 => d.deptno = e2.deptno | _ => false

Field accessors

In a future change, we might add some syntactic sugar to make it easier to deal with optional fields. If d has type {deptno:int, dname:string} option, then we can write d.deptno or #deptno d to get a value of type int option.

Thus you could write

from d in depts
  left join e in emps
  where case e.deptno of SOME x => d.deptno = x | _ => false

Note that option is a monad, and so is list. We could generalize so that accessors can push into all monads, not just option. For example, depts.deptno would return an int list, and if z has type {x:{y:int} option} option then z.y would have type int option option.

Flattening option

If the type of from d in depts left join e in emps is {d: Dept, e: Emp option} then it would be logical that the type of from d in depts left join e in emps left join a in assignments is {d: Dept, e: Emp option, a: Assignment option option}. But the double option in Assignment option option is inconvenient, and doesn't give us much useful information. So we flatten: the type is {d: Dept, e: Emp option, a: Assignment option}.

Bushy joins

Other than these new keywords, the grammar is unchanged. The join operation is still left-associative.

If you want to create a join expression that is not left-deep, you will have to write intermediate from expressions. it's not too great a hardship. The following is a bushy join ((a . b ) . (c. d)):

from (a, b) in (from a in as left join b in bs)
  left join (c, d) in (from c in cs left join d in ds)
  where a.x = c.y

Note how we use tuple patterns (a, b) and (c, d) to so that we have four variables a, b, c, d rather than just two. The one compromise of the nested from expressions is that we can't flatten the optional wrappers: the type of d is { ... } option option.

[segeljakt]

Hi, I am wondering, have you considered using union types and flow-sensitive typing (similar to Python/TypeScript/Scala) in Morel? I think it could be useful for addressing the typing challenges of joins.

With union types, the type {d: Dept option, e: Emp} could be represented as {d: Dept | None, e: Emp}. When combined with flow-sensitive typing, it would enable you to write:

from d in depts
  left join e in emps
  where d is Dept and d.deptno = e.empno

In this code, if d is Dept (or alternatively d is not None or d != None) evaluates to true, the type of d is proven to be Dept, which means the field access operation d.deptno will be legal.

A more concise version with syntax sugar for options can also be:

from d in depts
  left join e in emps
  where d and d.deptno = e.empno

Finally, union types imply that (T | None) | None is equivalent to T | None.

[julianhyde]

I definitely thought about making NONE values behave more like SQL's type system. I didn't know about flow-sensitive typing and union types, and I'm grateful that I now know the names.

I'm nervous to add a new concept to the type system, especially if it only solves outer joins. The key questions are:

1. Do flow-sensitive or union types solve some other problems that we have?
2. Can we keep the existing type system (based on the Option sum-type) and instead make the operators type inference better?

Regarding 1. I am already thinking about constraints being part of a type, and certain operations add and remove constraints. For example, in from e in emps where e.deptno > 20, the type of deptno changes from int to int > 20 as it passes through the where. In SQL, if I write select * from emps as e where e.commission is not null, the type of commission changes from DECIMAL to DECIMAL NOT NULL.

Can you think of other uses of union types besides nulls?

It is notable that Standard ML allows you to create product types on the fly (both records and tuples) but doesn't support anonymous sum types. Maybe union types fill that gap in the type system.

Regarding 2. Suppose we overload the "." operator so that if e is NONE, e.empno returns NONE: int Option, and e.commission returns NONE: real Option. (Assuming empno has type int and commission has type real Option.) Currently, neither case would be valid, because . cannot be applied to Option (or any sum type). But in the second case, . is doing more work, because it is flattening NONE: real Option Option down to NONE: real Option.

By the way, SQL's . operator already does this. It is usually convenient, but people get a little spooked when e.address.zipcode returns NULL. It is difficult to distinguish a NULL value of address from one that is non-NULL but its fields are all NULL.

[segeljakt]

1. Do flow-sensitive or union types solve some other problems that we have?

I think one use case for union types is when you want to pass a parameter that can have different types to a function without declaring a new type, for example in the Scala tutorial they show this:

case class Username(name: String)
case class Password(hash: Hash)

def help(id: Username | Password) =
  val user = id match
    case Username(name) => lookupName(name)
    case Password(hash) => lookupPassword(hash)

Also, you can potentially use union types to support if-else expressions where the branches have different types:

def parse(data: String): Username | Password =
    if data.isName() then
        Username(data)
    else
        Password(hash(data))

I can think of at least three main differences between union types and sum types.

1. Union types (in Scala3) cannot be self-referential, unlike sum types.
2. Union types derive their tag from the type, while sum types have an explicitly defined tag. This means that for example String | String is equal to String. If you need a union type that distinguishes usernames and emails, you would need to wrap them in newtypes. OCaml's polymorphic variants seem to be like union types but with an explicit tag.
3. The tags of union types are determined by type inference, while the tags of sum types are declared by the user. I'm not sure how ergonomic union types are in a language with global Hindley Milner type inference. I could imagine that they are easy to use in some cases and unpredictable in others. The size of the union could grow quite a bit I imagine if you are dealing with complex conditional expressions.

I think flow sensitive typing can be a general useful feature even with sum types. For example, if Rust had it you would be able to write:

fn surround_with_chars(v: impl Display, o: Option<(char, char)>) {
    let Some((l, _)) = o else { return };
    print!("{l}");
    print!("{v}");
    let Some((_, r)) = o; // Irrefutable pattern
    print!("{r}");
}

There are maybe some more interesting examples, I need to think more about it.

2. Can we keep the existing type system (based on the Option sum-type) and instead make the operators type inference better?

This seems like a good solution, it works just like SQL would. It should be similar to implement as traits/type classes. Will other operations like arithmetics also work with NONE, for example 1 + NONE == 1?

Regarding 1. I am already thinking about constraints being part of a type, and certain operations add and remove constraints. For example, in from e in emps where e.deptno > 20, the type of deptno changes from int to int > 20 as it passes through the where. In SQL, if I write select * from emps as e where e.commission is not null, the type of commission changes from DECIMAL to DECIMAL NOT NULL.

This seems interesting and also very similar to flow-sensitive typing. I am currently trying to understand better how to implement flow-based typing. I think it can be built on top of Hindley Milner by storing type predicates in the environment. There is something called bidirectional typing that I'm currently investigating which might be related. I can reply back once I have a better picture of it.