Namespaces
Variants
Actions

Difference between revisions of "Translation of programs"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
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" />.
+
<!--
 +
t0938401.png
 +
$#A+1 = 43 n = 0
 +
$#C+1 = 43 : ~/encyclopedia/old_files/data/T093/T.0903840 Translation of programs
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
The translation of programs in [[Programming|programming]], also called compilation of programs, is a systematic process that transforms any program $  ip $
 +
in the input [[Algorithmic language|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|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).
 
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" />.
+
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 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|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 <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
+
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
  
<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>
+
$$
 +
F ( x _ {1} \dots x _ {m + n }  )  = \
 +
U ^ {m + n } ( NF, x _ {1} \dots x _ {m + n }  ) =
 +
$$
  
<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>
+
$$
 +
= \
 +
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 <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.
+
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 [[#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:
+
There is a direct relationship between problems of practical translation in programming and partial computations (see [[#References|[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:
  
<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>
+
$$
 +
\forall d  NS ( NLI, ip, d)  = op ( d),
 +
$$
  
<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>
+
$$
 +
\forall ip  NS ( NS, NLI , ip)  = t ( ip),
 +
$$
  
<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>
+
$$
 +
\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.
 
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.
Line 25: Line 85:
 
====References====
 
====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>
 
<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====
 
====Comments====
 
  
 
====References====
 
====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>
 
<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>

Latest revision as of 08:26, 6 June 2020


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)

Comments

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
How to Cite This Entry:
Translation of programs. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Translation_of_programs&oldid=49017
This article was adapted from an original article by A.P. Ershov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article