CategoricalData / hydra

Transformations transformed
Apache License 2.0
72 stars 10 forks source link

Use topological sort in type inference #67

Closed joshsh closed 1 year ago

joshsh commented 1 year ago

Currently in Hydra, the type of every element must be given along with the data (term) of the element. This is a holdover from Hydra's initial type system, which was based on STLC rather than Hindley-Milner (which permits type inference). While it is possible now to infer the type of many elements rather than relying on type annotations (which are labor intensive and error-prone for the developer), this must be done by ordering the elements in a graph to take into account the dependencies introduced by element references. Only in those cases where the reference structure forms a cycle will type annotations be required.

Currently, types are inferred on a term-by-term or element-by-element basis, but the change described above will require types to be inferred for an entire graph at once.

joshsh commented 1 year ago

Done.