Doctor of Philosophy

dissertationl turns a first-order language into a higher-order one, introducing novel control and environment behaviors into programs. These behaviors can be reasoned about using controlflow and environment analysis, respectively, but only for whole programs; current theories of control-flow and environment analysis are formulated to be sound only when they are exhaustive. Having to purchase exhaustive bundles of control-flow and environment facts is inconvenient for clients who, on average, may value each such fact less than its price and consequently forego control-flow and environment analysis entirely. Demand environment analysis changes the pricing model presented to clients by allowing them to purchase environment facts individually (on demand). Demand environment analysis requires theories of environment analysis that admit demand algorithms. Demand UVA and Pushdown DCFA are two such theories, each operating independently of its supporting control-flow analysis. Because environment behavior is so closely linked to control-flow behavior, demand environment analysis requires theories of control-flow analysis that admit demand algorithms as well. Demand 0CFA and demand pushdown 0CFA are two such theories, meaning that they allow clients to pose pointed control-flow questions (such as what flows to f in ( f x)?) and consider only the control flow relevant to the answer. Enabled by these theories, demand environment analysis offers (for example) compilers a selective and often-affordable means to justify valuable program optimizations sensitive to environment behavior, such as procedure inlining