We give a variant of the Gödel-Gentzen-negative translation, and a syntactic characterization which entails conservativity result for formulas.

Inλ-calculus, the strategy of leftmost reduction (“call-by-name”) is known to have good mathematical properties; in particular, it always terminates when applied to a normalizable term. On the other hand, with this strategy, the argument of a function is re-evaluated at each time it is used.To avoid this drawback, we define the notion of “storage operator”, for each data type. IfT is a storage operator for integers, for example, let us replace the evaluation, by leftmost reduction, ofϕτ (whereτ is an integer, (...) andϕ anyλ-term) by the evaluation oftτϕ. Then, this computation is the same as the following: first computeτ up to some reduced formτ 0, and then applyϕ toτ 0. So, we have simulated “call-by-value” evaluation within the strategy of leftmost reduction.The main theorem of the paper (Corollary of Theorem 4.1) shows that, in a second orderλ-calculus, using Gödel's translation of classical intuitionistic logic, we can find a very simple type (or specification) for storage operators. Thus, it gives a way to get such operators, which is to prove this type in second order intuitionistic predicate calculus. (shrink)

The paper presents a refined method of extracting reasonable and sometimes unexpected programs from classical proofs of formulas of the form ∀x∃yB . We also generalize previously known results, since B no longer needs to be quantifier-free, but only has to belong to a strictly larger class of so-called “goal formulas”. Furthermore we allow unproven lemmas D in the proof of ∀x∃yB , where D is a so-called “definite” formula.

We show that Shoenfield's functional interpretation of Peano arithmetic can be factorized as a negative translation due to J. L. Krivine followed by Gödel's Dialectica interpretation. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim).