View source for Translation of programs

The translation of programs in [[Programming|programming]], also called compilation of programs, is a systematic process that transforms any program <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t0938401.png" /> in the input [[Algorithmic language|algorithmic language]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t0938402.png" /> into some program <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t0938403.png" /> in the object language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t0938404.png" />; furthermore, both programs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t0938405.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t0938406.png" /> should realize the same function, that is, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t0938407.png" /> is the input data of the program, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t0938408.png" />.

A translation of programs in the theory of computable functions and theory of algorithms (cf. [[Algorithms, theory of|Algorithms, theory of]]; [[Computable function|Computable function]]) is any mapping of one [[Enumeration|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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t0938409.png" /> in some realization language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384010.png" />, called the translator (or compiler), that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384011.png" />. The systematic development of translators for any input language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384012.png" /> from some class of languages is what constitutes [[Automatic programming|automatic programming]], and the corresponding devices of such a development are called systems of compiler construction, or compilers of compilers, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384013.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384014.png" />. Here, the realization language either contains the object language or coincides with it: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384015.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384016.png" />-function) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384017.png" /> such that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384018.png" /> is a universal function for computable functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384019.png" /> variables, then for any computable function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384020.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384021.png" /> variables and with number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384022.png" />, one has the identity

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384023.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384024.png" /></td> </tr></table>

As is obvious from this identity, a partial computer constructs from a program of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384025.png" /> variables and given values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384026.png" /> variables a program of a function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384027.png" /> variables obtained from the original program by associating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384028.png" /> of its arguments with these values. The result of a partial computation is called the projection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384029.png" /> of the program <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384030.png" /> on the given values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384031.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384032.png" /> of its arguments. The existence of principal computable enumerations (see [[#References|[1]]], Chapt. 1, Sect. 2) and partial computers (see [[#References|[2]]], Sect. 65), as well as their connection (see [[#References|[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 [[#References|[4]]]). Suppose that the realization language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384033.png" /> has a principal computable enumeration and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384034.png" /> be the program of a partial computer for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384035.png" /> expressed in the same language. Suppose further that the input language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384036.png" /> is defined by a program <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384037.png" /> of its universal function expressed in an object subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384038.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384039.png" />, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384040.png" />. (In programming, such a program is called an interpreter of the input language.) Then the following relations hold:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384041.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384042.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093840/t09384043.png" /></td> </tr></table>

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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  Yu.L. Ershov,   "Theorie der Numierungen" , '''I-II''' , Deutsch. Verlag Wissenschaft.  (1973–1976)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  S.C. Kleene,   "Introduction to metamathematics" , North-Holland  (1951)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.A. Uspenskii,   "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  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)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR></table>