Negative cost for extraction?

[yangdinglou]

Hi, I'm working on a task when setting negative cost as "reward" can be useful, which doesn't seem to work

can't convert negative int to unsigned

To illustrate why I want negative, considering a conjunction among FOL formulas (AND phi_1 phi_2 ...), and the task is to rewrite it to (AND phi_1' phi_2' ... phi_n') with most n (without different phi being the same). So the way I (want to) implement is to use head-tail for AND with negative cost, then whenever phi_i === (and p1 p2), we can split it into top-level phi_i1, phi_i2 with the preference.

Since I didn't find document on it, what's the restriction on cost? and any suggestion on how to achieve the "reward"? Thanks

[saulshanabrook]

Hey! Yeah egglog doesn't support negative costs by default. Feel free to open an issue upstream to allow negative integers as costs.

However, if you use a custom cost model negative costs should work, since they should be supported by the default extractor. When using a custom cost model in Python, the cost type can be any Python value that support comparison instead of unsigned ints.

EDIT: cc @FTRobbin here's a negative cost model example, which I was saying I hadn't seen yet!

[yangdinglou]

Thanks, the feature looks really useful. Could you clarify on the "Python-specific" of the custom cost model? Is the extraction going to be done totally in Python?

I did try greedy_dag_cost_model previously, but it threw a panic when calling the Rust extract

cost, term = extractor.extract_best(self._state.egraph, termdag, value, egg_sort)
pyo3_runtime.PanicException: called Option::unwrap() on a None value

Haven't managed to minimise the code triggering this, but with the default cost model there is no such error. So I'm wondering if implementing the custom model, whether it's likely to face the same problem.

[saulshanabrook]

The greedy dag cost model has an issue currently with the extractor... But one that just does negative costs shouldn't have the same issue. There is an open issue about that an in progress branch to fix it.

Most of the extraction still happens in rust, just the cost calculation happens in Python.