Fundament-Software / scopes

Fundament fork of the Scopes language
Other
3 stars 1 forks source link

Implement Meet and Join #18

Open ErikMcClure opened 1 year ago

ErikMcClure commented 1 year ago

Implement the meet and join type system operation to allow scopes to be less pedantic about types.

aiverson commented 1 year ago

The operations are called meet and join, not merge.

aiverson commented 1 year ago

The goal of this change is to make the type system slightly more friendly when writing branching constructs such as loops and conditionals.

Currently, the types produced by both sides of an if or by the initial condition and every way a loop can repeat must be exactly equivalent. This is inconvenient when, for example, one type is a pointer and the other type is a pointer to something that lives inside the function. These can easily be cast to the same type, but doing so can be annoying.

The design of this system is based on lattice subtyping. scopes types don't actually form a lattice, but we can pretend. meet should produce a type which can be cast to any of the argument types, and also that any type which can be cast to all of the argument types can also be cast to. Complementarily, join should produce a type which any of the argument types can be cast to (ideally also a type that any type which can be cast to the argument types can be cast to, but scopes doesn't have transitive castability in general.) ((by cast in the preceding paragraph I mean with the imply operator)).

Meet and join should be new operators named meet and join that use a metamethod on types for them to allow custom types to participate. Any place where scopes attempts to generate a phi node, such as at the conclusion of a conditional or the variable binding of a loop, if the types from both sources don't match, the compiler should invoke a join operation and insert an imply on both branches to produce a common types, and only raise an error if this fails.