andrew-johnson-4 / lambda-mountain

Compiler Backend for LSTS (Typed Macro Assembler)
https://github.com/andrew-johnson-4/lambda-mountain/wiki
MIT License
20 stars 1 forks source link

Metrics #322

Open andrew-johnson-4 opened 6 months ago

andrew-johnson-4 commented 6 months ago

Metrics are multipoint integers that can be sorted according to their first digits. For example the polynomial x^5+2x^3 could be reduced to simply (Polynomial, 5) or equivalently Polynomial.5 with a single point. Other complexity classes could be describe as (Exponential, 2) for 2^x or something like this.

To sort, the first number is compared, then next after the point, and further on. This is a fairly simple order that can describe a lot of different shapes.

andrew-johnson-4 commented 6 months ago

Some terms might not exist until they are needed. So metric specialization can potentially touch terms that are not further processed if not selected. Locally they should behave like a hard declared term, but might need no further processing if not chosen.