A Database Workbench: an interface for mixed-initiative design space search

Edward Misback, Pavel Panchekha, Zachary Tatlock

Design space search

“Mixed-initiative”: computers and humans can both make or suggest moves collaboratively

Outline

• Intro – 15 minutes
• What is Herbie?
• Quick Herbie demo
• What is Herbie missing?
• Users don’t understand results (e.g. asking questions on GitHub, PHerbie curve)
• Hard for experts to use profitably (“it’s like a drunk numerical analyst”)
• Hard to integrate new features
• Adding new visuals involves reaching into Herbie’s pipeline and making new APIs to get/send data
• Current interface is talking about spec + one “best” program; it’s hard to change from that
• Kind of “done”
• What do we want to enable?
• More user control over search + analysis, with more options
• “I’d like to run Herbie for a single iteration and see what the output looks like”
• “I’d like to see a very simple/accurate/fast replacement expression”
• “I’d like to compare several options”
• “I’d like to evaluate these expressions on my own set of inputs/do the validation myself”
• “I’d like to use my own rewrite rule”
• “I’d like to see how changing the input interval affects the error”
• “I’d like to see how the subexpressions behave (local error)”
• Bigger dreams
• Numerical workbench – something that’s capable of easily incorporating other tools from the community
• ​
• Our solution (Database Workbench) – 15 minutes, with “Wizard of Oz”-ish demo/mock-up
• Basic intuition
• Herbie works by building a database of candidate solutions as it searches a design space
• We can expose this design space to the user directly with formal types for solutions
• We can build functions that visualize and compare solutions and expose them in a UI
• We can show the generation relationships between solutions to track user edits + automated rewriting
• We can use any other tool that generates/analyzes solutions as long as the types work

My Background

• Not a numerics expert!
• 3rd-year grad student studying live programming
• LP is about “interfaces” that make programs easy to
• Inspect – embedding visualizations in a Jupyter notebook
• Operate - executing programs via the command line
• Extend - defining new functions at runtime in a REPL

How do we make working with programs easy?

• Target the programming process
• Show lots of feedback
• On the data going through the program now
• On the behavior of other versions of the program
• Suggest and automate decisions when possible

What is Herbie?

• https://herbie.uwplse.org/

​

​

Includes a link to this result

What is Herbie missing?

• Hard for novices to understand
• Hard for experts to use profitably (“it’s like a drunk numerical analyst”)
• Hard for us to integrate new features, especially meaningful interactivity
• Adding new visuals involves reaching into Herbie’s pipeline and making new APIs to get/send data
• Current interface only presents the spec + one “best” program
• Kind of “done”

​

​

What do we want to enable?

• More user control over search + analysis
• Bigger dreams
• “A numerical workbench”
• Something that can incorporate other tools from the community
• Something that can work as a good starting point for many other tools

​

How does Herbie work? What is its “essence”?

(Spoiler: it’s not just one tool!)

End-to-End: Herbie as an Automated Space Search Tool

Herbie builds a database of candidate solutions as it searches the space of possible rewritings of an initial expression for the “best” rewriting.

​

What the user can see:

Herbie as a Sampling Tool

Herbie uniformly samples valid inputs for a given expression.

​

Herbie as a Calculation Tool

Herbie calculates the result of an expression on each input for a numeric representation (including an exact representation).

​

Herbie as a Visualization & Analysis Tool

Herbie visualizes the error across the domain for each variable in the inputs (and also computes the average error).

Pareto Herbie/“PHerbie”

Herbie as a Derivation Tool

Herbie tracks rewritings and shows the user the steps it took to get from the starting expression to the final expression.

We have a lot of tools. How can we make them into a workbench?

Building a workbench for _________

Building a workbench for expressions?

There are other types of things involved too, like the spec and sets of sampled inputs…

Inputs

Analysis (exacts, outputs, and errors)

Expression

Spec (including an interval, a precision, and other sampling config)

*

*

0 or more items from any of 0 or more other tables

Exactly one item from the table

Expression Generation config

= “an input sample is fully determined by a spec + a random seed”

Applying LP design principles

• Inspect
• For any object in these tables, we should know
• what the object “looks” like
• where the object came from (how it was generated)
• how the object compares to other objects in the design space (e.g. on graphs or side-by-side)
• Operate
• For any object or set of objects, we should be able to call functions that analyze it or generate more objects
• Extend
• It should be relatively easy for a developer to plug in new inspectors and operators (or maybe even add new tables and object relationships)

Applying LP design principles

• Inspect
• For any object in these tables, we should know
• what the object “looks” like LaTeX/AST
• where the object came from (how it was generated) Derivation (but we can go further)
• how the object compares to other objects in the design space (e.g. on graphs or side-by-side) Error graph
• Operate
• For any object or set of objects, we should be able to call functions that analyze it or generate more objects (Use Herbie)
• Extend
• It should be relatively easy for a developer to plug in new inspectors and operators (or maybe even add new tables and object relationships) This depends on the interface

(Wizard of Oz) Demo

How is this relevant to the FPBench community?

1. It may be able to incorporate and interoperate other tools as plugins
2. Could be a good model for new tools focused on flexible, user-driven analysis