Remove Defaults and Change Relations

[saulshanabrook]

To simplify the model, there is an open conversation/proposal to remove the ability to specify `defaults for functions.

This would entail changing how Unit/relation is implemented, since currently relation desugars to a function that returns a Unit type of () constructor as a default.

Instead, I believe the proposal is to desugar relation into a function that returns a fresh eqsort. That way, you can't union multiple relations.

It comes from this PR https://github.com/egraphs-good/egglog/pull/309 but I don't believe there is a public issue/PR describing the proposal yet.

I was trying to think about how to implement this in Python. In a few places currently, I don't use the relation helper, but manually create functions that return Unit and have a default, since they are methods instead of top-level functions, like here:

https://github.com/egraphs-good/egglog-python/blob/83d7785f6a32621b10233f4d56503ff914eb5f70/python/egglog/exp/program_gen.py#L86-L90

So how should this be typed?

One option would be to keep the same typing, returning a Unit type, but just remove the default and do a pre-processing step to translate any functions that return Unit to relations.

However, I think a better way could be just to use the builtin Unit type in Python, None. So the Unit type would be removed, and any function that returns the None type would be translated to a relation. We would still provide the top level relation constructor as well.

This would work well because it would mean that you couldn't pass the result of relations into other functions, i.e. it would no longer be valid to take Unit as an arg. This could be checked statically in Python now.

There is one confusion, that currently some functions can take None arguments, which are upcast to Option<X> types:

https://github.com/egraphs-good/egglog-python/blob/83d7785f6a32621b10233f4d56503ff914eb5f70/python/egglog/exp/array_api.py#L358-L365

I don't think this would cause any ambiguities though, since this None conversion for upcasting would only take place for args, which a Unit couldn't be, and the return of None only is for Unit. The only other place we return None currently as a type annotation is for functions which mutate their args, like __setitem__:

https://github.com/egraphs-good/egglog-python/blob/83d7785f6a32621b10233f4d56503ff914eb5f70/python/egglog/exp/array_api.py#L626

This is translated into function which returns a new changed NDArray, so it doesn't return Unit. This is automatically set for builtin functions that mutate their arguments, but can also be set for any function that mutates its first arg:

https://github.com/egraphs-good/egglog-python/blob/83d7785f6a32621b10233f4d56503ff914eb5f70/python/egglog/exp/array_api.py#L1244-L1248

So the behavior would be, that for any function with returns None, if it is mutates_first_arg then it will return the type of the first arg. Otherwise, it will be relation.

[saulshanabrook]

I got a question if None in Python is intended to be used as a "Unit" type.

Let's see what the Python docs have to say about this:

None: An object frequently used to represent the absence of a value, as when default arguments are not passed to a function. Assignments to None are illegal and raise a SyntaxError. None is the sole instance of the NoneType type.

From the typing docs:

When used in a type hint, the expression None is considered equivalent to type(None).

Compare to the definition in Wikipedia of:

a unit type is a type that allows only one value (and thus can hold no information)

It does say in that article in Python, the NoneType works as a Unit type.