  Programs are an increasingly popular representation for visual data, exposing
compact, interpretable structure that supports manipulation. Visual programs
are usually written in domain-specific languages (DSLs). Finding "good"
programs, that only expose meaningful degrees of freedom, requires access to a
DSL with a "good" library of functions, both of which are typically authored by
domain experts. We present ShapeCoder, the first system capable of taking a
dataset of shapes, represented with unstructured primitives, and jointly
discovering (i) useful abstraction functions and (ii) programs that use these
abstractions to explain the input shapes. The discovered abstractions capture
common patterns (both structural and parametric) across the dataset, so that
programs rewritten with these abstractions are more compact, and expose fewer
degrees of freedom. ShapeCoder improves upon previous abstraction discovery
methods, finding better abstractions, for more complex inputs, under less
stringent input assumptions. This is principally made possible by two
methodological advancements: (a) a shape to program recognition network that
learns to solve sub-problems and (b) the use of e-graphs, augmented with a
conditional rewrite scheme, to determine when abstractions with complex
parametric expressions can be applied, in a tractable manner. We evaluate
ShapeCoder on multiple datasets of 3D shapes, where primitive decompositions
are either parsed from manual annotations or produced by an unsupervised cuboid
abstraction method. In all domains, ShapeCoder discovers a library of
abstractions that capture high-level relationships, remove extraneous degrees
of freedom, and achieve better dataset compression compared with alternative
approaches. Finally, we investigate how programs rewritten to use discovered
abstractions prove useful for downstream tasks.
