Choice in Dynamic Linking

We introduce a computational interpretation for Hilbert’s choice operator (epsilon). This interpretation yields a typed foundation for dynamic linking in software systems. The use of choice leads to interesting difficulties – some known from proof theory and others specific to the programming-language perspective that we develop. We therefore emphasize an important special case, restricting the nesting of choices. We define and investigate operational semantics. Interestingly, computation does not preserve types but it is type-sound.