Generic programming in Macaulay2

[mahrud]

This is a proposal stub for introducing generic programming in Macaulay2 following discussions at the internals metting on 3/4/21 and comments I wrote here and here.

Generic programming allows for designing code and data structures that work in the most general setting without loss of efficiency. This is parallel to the "type inheritance" system for methods and would allow reducing duplicate code in Macaulay2 by taking advantage of a mathematical hierarchy rather than a type hierarchy.

Here's a simple example:

AlgebraicType  = new Type of Type
Group = new AlgebraicType of AlgebraicType

foo = method()
foo Group := G -> print concatenate("foo on a ", class G, " called")

S  = new Group of List
GL = new Group of HashTable

S2  = new S  from { (), (1, 2) }
GL2 = new GL from hashTable { V => RR^2 }

foo S2  -- stdio:21:1:(3): error: no method found for applying foo to ... of class S
foo GL2 -- stdio:21:1:(3): error: no method found for applying foo to ... of class GL

One possible notation for making this work is allowing a list of parents:

S  = new AlgebraicType of {List, Group}
GL = new AlgebraicType of {HashTable, Group}

The idea being that the first element in the list indicates the "structure" of the class and the rest are the "traits" of the class. Ideally there should be a way to append to the list later so packages can add functionality on top of existing types without declaring tons of methods again.