[Question] Use-cases for computations, other than running them?

In imperative programming languages, the main purpose of a program is to specify a computation, which we then run. But it seems a rather… unimaginative use of a computation, simply to run it.

Having specified a computation, what else might one want to do with it?

Some examples:

  • Differentiate numerical computations (i.e. backprop)

  • Ask whether any possible inputs could yield a particular output (i.e. NP problems)

  • Search for data within the computation’s output space (i.e. grep)

  • Given output from the computation, find a data structure which traces its execution (i.e. parsing with context-free grammars)

  • Parallelize the computation

  • Interventions & counterfactuals: ask what will happen/​what would have happened if some internal variable at some step of the computation were assigned a different value, keeping the rest of the computation the same

  • Generate a new computation which optimizes the output of the original computation via dynamic programming

  • Find summary statistics describing the computation (i.e. profiler, maximum forces encountered in a physical simulation, …?)

  • Embed one computation within another (i.e. a compiler embeds computation specified in Python into the computation performed by a CPU)

    • Use knowledge of the internal structure of the two computations to optimize the embedding (i.e. optimizing compiler)

  • Ask what parameters/​outputs of the computation need to be observed in order to reliably deduce other parameters/​outputs (i.e. inference, identifiability, & experiment design in causal models)

  • Ask whether observed data is consistent with the computation (i.e. regexes & CFGs; causal model comparison)

  • Dependency: is the output (or some set of intermediates) independent of some internal value, or independent of the distinction between two (or more) possible values at some point in the computation?

  • Can we keep around a small amount of data sufficient to quickly reconstruct anything we might want to know about the full computation (i.e. intermediate values and execution path)?

  • Was any computation repeated (i.e. something we could optimize out via memoization)?

  • Are there any unused patterns/​symmetries in the computational DAG (i.e. potential for refactoring the code)?

  • Big-O runtime analysis

I’m also interested in more general meta-use-cases for computations, which generate use-cases that aren’t just “run the computation”. For instance, some patterns in the examples above:

  • When considering physical processes as computations (i.e. simulations), we often want to query/​visualize intermediates in the computation in various ways

  • When treating computations algebraically—i.e. solving computation(input) = output given the computation and the output—we usually want to reason about the internal structure of the computation.

  • More generally, given only partial information from the computation, deducing other information usually involves operations other than just running the computation. Again, this is especially relevant when the computation simulates some physical process about which we have partial information.

  • Anything involving runtime, profiling, optimization, debugging, etc will typically involve looking at the internal structure of the computation.