epfl-lara / stainless

Verification framework and tool for higher-order Scala programs
https://epfl-lara.github.io/stainless/
Apache License 2.0
349 stars 50 forks source link

Collection types in Stainless should be inductive #1457

Open vkuncak opened 9 months ago

vkuncak commented 9 months ago

Collections should be backed by lists or similar structures.

Example of some discussion of this for arrays: https://github.com/epfl-lara/stainless/issues/1281

It should in particular also apply to maps (which we should clarify if they are finite!) and sets.

The benefit is that we can use induction whenever the solvers are not behaving like we want (performance or limitations of their first-order axiomatization).