Translation of programs

The translation of programs in programming, also called compilation of programs, is a systematic process that transforms any program $ ip $ in the input algorithmic language $ LI $ into some program $ op $ in the object language $ LO $; furthermore, both programs $ ip $ and $ op $ should realize the same function, that is, if $ d $ is the input data of the program, then $ ip ( d) = op ( d) $.

A translation of programs in the theory of computable functions and theory of algorithms (cf. Algorithms, theory of; Computable function) is any mapping of one enumeration of computable functions to another that preserves the property that the image and pre-image are the numbers of the same function (the presence of an effective translating mapping is also called reducibility of one enumeration to another).

In programming practice, the programming language used by the human being is usually the input language, while the object language is usually the language that is carried out directly by the machine programs. The translation of programs itself is, as a rule, carried out automatically, that is, by means of a program $ t $ in some realization language $ LR $, called the translator (or compiler), that is, $ t ( ip) = op $. The systematic development of translators for any input language $ LI $ from some class of languages is what constitutes automatic programming, and the corresponding devices of such a development are called systems of compiler construction, or compilers of compilers, $ tt $: $ tt ( LI ) = t $. Here, the realization language either contains the object language or coincides with it: $ LO \subseteq LR $.

The notion of a translation of programs (reducibility) in the theory of computable functions leads to the notion of principal enumerations, that is, enumerations to which any other enumeration of some class can be reduced. The existence has been proved of principal computable enumerations for all concrete models of computable functions; in particular for partial recursive functions and for Turing machines. In turn, the existence of principal computable enumerations is enabled by the ability of computable functions to perform so-called partial computations, that is, by the existence of a general recursive function (in programming, a partial computer; in the theory of computable functions, an $ s- m- n $- function) $ S ^ {m} ( x _ {0} \dots x _ {m} ) $ such that if $ U ^ {n} ( x _ {0} \dots x _ {n} ) $ is a universal function for computable functions of $ n $ variables, then for any computable function $ F $ of $ m + n $ variables and with number $ NF $, one has the identity

$$ F ( x _ {1} \dots x _ {m + n } ) = \ U ^ {m + n } ( NF, x _ {1} \dots x _ {m + n } ) = $$

$$ = \ U ^ {n} ( S _ {n} ^ {m} ( NF, x _ {1} \dots x _ {m} ), x _ {m + 1 } \dots x _ {m + n } ). $$

As is obvious from this identity, a partial computer constructs from a program of $ m + n $ variables and given values of $ m $ variables a program of a function of $ n $ variables obtained from the original program by associating $ m $ of its arguments with these values. The result of a partial computation is called the projection $ NF _ {x _ {1} \dots x _ {m} } $ of the program $ NF $ on the given values $ x _ {1} \dots x _ {m} $ of $ m $ of its arguments. The existence of principal computable enumerations (see [1], Chapt. 1, Sect. 2) and partial computers (see [2], Sect. 65), as well as their connection (see [3], Sect. 11, Theorem 3) is one of the fundamental aspects of the theory of computable functions.

There is a direct relationship between problems of practical translation in programming and partial computations (see [4]). Suppose that the realization language $ LR $ has a principal computable enumeration and let $ NS $ be the program of a partial computer for $ LR $ expressed in the same language. Suppose further that the input language $ LI $ is defined by a program $ NLI $ of its universal function expressed in an object subset $ LO $ of $ LR $, that is, $ NLI ( ip, d) = ip ( d) $. (In programming, such a program is called an interpreter of the input language.) Then the following relations hold:

$$ \forall d NS ( NLI, ip, d) = op ( d), $$

$$ \forall ip NS ( NS, NLI , ip) = t ( ip), $$

$$ \forall NLI NS ( NS, NS, NLI) = it ( NLI), $$

that is, the object program is the projection of the interpreter of the input language onto the input program; the compiler is the projection of the partial computer onto the interpreter of the input language; while the compiler of compilers is the projection of the partial computer onto itself.

References

[1]	Yu.L. Ershov, "Theorie der Numierungen" , I-II , Deutsch. Verlag Wissenschaft. (1973–1976) (Translated from Russian)
[2]	S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[3]	V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[4]	A.P. Ershov, , All-Union Conference. Methods of mathematical logic in problems of artificial intelligence and systematic programming. Palanga, 3–5 Sept. 1980 , 2 , Vilnius (1980) pp. 26–55 (In Russian)

References

[a1]	N.D. Jones, "Partial evaluation, self-application and types" M.S. Paterson (ed.) , Automata, Languages and Programming (Proc. ICALP 17, Warwick, July 1990) , Lect. notes in comp. science , 443 , Springer (1990) pp. 639–659