WIP: Make more types extern instead of builtin

[marzipankaiser]

This PR is a draft to move types from being builtins (in symbols.builtins) to extern type declarations in the prelude. To do so, it annotates the operations using those types (If, While for Boolean, Assign for Unit (and Ref)) with Ids referring to them, which are then resolved by Namer and used by Typer.

For phases after core, it will also add an ExternContext (sim. to DeclarationContext in #204).

Implications:

• Using e.g. If in a backend that does not support Booleans yet will lead to an error in Namer
• All of the builtin types are identified by name (only) and can potentially be overwritten, possibly leading to strange behaviour
  • This might be solved by having a #30.
  • On the plus side, this also allows individual backends to decide that, e.g., Boolean is a data type (not builtin)

[marzipankaiser]

Unit is harder than I thought, since State (Ref) depends on it as the return type of put. The symbols regarding State are used extensively in multiple backends, so this will be some work to move.

[marzipankaiser]

For Ref (and also maybe for the other changes here, but to a lesser degree), an interesting question comes up: We can

1. Add the relevant Ids to the source Tree and annotate them (e.g. put to Assign, Ref to State, ...), or
2. use new kinds of annotation to annotate the nodes with the Getter/Setter/...

1 is what I am doing so far, but there is a difficulty for Var: We do not actually know if get is used until we resolve it in Namer. So we can either use 2 here, or we will have a spurious reference to get for each reference to a val.

[b-studios]

On the plus side, this also allows individual backends to decide that, e.g., Boolean is a data type (not builtin)

But wouldn't this also require overloading literals true and false?

[b-studios]

For Ref [...]

TBH I don't understand the discussion. Are you talking about "how can we figure out the correct symbols for state in Typer"?

[marzipankaiser]

On the plus side, this also allows individual backends to decide that, e.g., Boolean is a data type (not builtin)

But wouldn't this also require overloading literals true and false?

Yes, it would (in some way) - Handling of literals in general is not great with this; but I think there is no way around transforming them explicitly in the backend transformer, which then has to agree with the prelude on the representation.

[marzipankaiser]

For Ref [...]

TBH I don't understand the discussion. Are you talking about "how can we figure out the correct symbols for state in Typer"?

Yes, exactly. Currently, this adds the symbols to the source tree (like for Literal). Though now, I am leaning more towards introducing them in Namer as a new kind of annotation (e.g. Getter on Var to annotate the symbol of the get function, ReferenceTypeConstructor on State etc).

[marzipankaiser]

For Ref (mutable state) the possible strange behaviour without a #30 occurs. Some tests (at least examples/pos/probabilistic.effekt) define Ref themselves.

[marzipankaiser]

While I still would support the direction this tries to move in, and this did create some insights, I don't think that it's worthwhile to update this to the current version (in contrast to similar changes in the current one), so closing.