`FromTargets` trait

[wborgeaud]

Tentative refactor introducing a new FromTargets trait with a fn to go from an iterator of Targets to Self.

Using this trait, functions like builder.add_virtual_* or add_virtual_*(builder,...) can be removed and replaced with a call to a new builder.add_virtual() function that infers the return type.

As a next step, this can also be used to add functions like builder.add_constant() which would create a constant StructTarget from Struct or builder.add_with_generators() which would create a StructTarget set non-deterministically in the trace.

[dlubarov]

This is really neat in a way, I'm just a bit concerned about the effects on readability. E.g. considering builder.add_virtual_targets(1) vs builder.add_virtual(((), 1)), I think the former is more natural/intuitive - it's more obvious what method is called, the argument has the expected form and name/type (n: usize vs config: ...), etc.

I also just feel since it adds extra code, like length calculations that we didn't need before, we should have a strong reason to add that extra code.

I think an add_constant API might be cleaner in some ways than add_virtual, if those conversions don't require a Config? So we wouldn't have odd, hard-to-explain args like ((), 1). Though it might still increase verbosity a bit, and make it slightly harder to tell what method is being invoked.

[dlubarov]

Hmm maybe I didn't fully understand the idea. Could you explain how constant would work, like would there be a ToTargets, and then the impl is T::from_targets(constant.to_targets)?

Just from this first phase, I worry the API might become a little less user-friendly. E.g. considering add_virtual_cap, currently its param is named cap_height, but that would change to the generic c. On add_virtual_cap we could add a comment if we needed to clarify the parameter, but seems like we lose that option with a generic add_virtual. Users could always find the FromTargets impl to get more info, but that seems higher-friction.

It also just feels a little less natural IMO to wrap args in a tuple, especially e.g. ((), 1). Not an issue once we're used to it, but it'd be something we need to explain in a tutorial/example. And if users need to extend the API, that seems harder, mainly due to len().

I'm probably not seeing the full picture with all the pros and cons though, since I don't have a good sense of what add_constant()/add_with_generators() will look like.

[wborgeaud]

Yes for constants and generators we would need to add a ToFieldElements trait for native types that returns a vector of field elements. Then we'd be able to use it with the FromTargets (linking the two using associated types) for constants, generators. I think that ideally it would be nice to merge the native and target structs (like we do already in some of the Stark code) to make things simpler and remove some redundancy.

For the config, I agree with you it's a bit less clear with this PR. One way to fix it would be to use config structs, like CapConfig { height: usize } instead of just usize.

[pgebheim]

Hello!

This PR has been open for a long time, please review and update as following:

1. If this PR is no l longer relevant, close it.
2. If this PR is relevant but not read, mark it as Draft and make a comment of what else needs to be done.
3. Fix any issues and get it merged / reviewed by 10/27/2023.

If there's no update by 10/27/2023 this PR will be closed.