0

Every program P which built of function sequence (order counts): $F_1,..,F_n$, where $F_i$ returns $R_i$ and $F_{i+1}$ takes $R_i$ as an argument, can be shown as $F_1(F_2(F_3(...(F_n))))$, i.e. we do not need to store intermediary program states.

Can every program be transformed to such without intermediary states?

tesgoe
  • 131
  • 8
  • What is your computation model? If you allow any model and provide denotational semantics, the answer is "trivially, yes": Just take the function induced by the denotational semantics. Edit: This also works with other formal semantics, e.g., small-step operational semantics or natural semantics. – Johannes Kloos Mar 17 '14 at 21:44
  • To be more concrete, suppose you have big-step semantics for an imperative programming language without function calls. Then for each statement, we get a (computable) function mapping a variable context to a variable context. Chain all these functions, and you have a representation of your program as a sequence of function applications. – Johannes Kloos Mar 17 '14 at 21:53
  • I allow any model. Just to make sure- is this true if the connection between $R_{i+j}$ and $R_{i}$, for an arbitrary $j$, is recursive? – tesgoe Mar 17 '14 at 21:56
  • As long as you can give effective semantics to your model/programming language, yes. Does this answer your question? – Johannes Kloos Mar 17 '14 at 21:58
  • Yes, thank you very much. – tesgoe Mar 17 '14 at 21:58
  • Oh, wait. You may need higher-order functions; see the answer. – Johannes Kloos Mar 17 '14 at 22:04

1 Answers1

1

Yes, as long as the semantics of the underlying programming language are effective and we allow higher-order functions.

Assume for the sake of the argument that we are given big-step semantics for the underlying programming language, using the notation $s_1 \to s_2$, where $s_1$ and $s_2$ are program states. Suppose furthermore that the underlying programming language is "roughly imperative": We have several base commands (e.g., assignment) that are joined into a sequence. Then the execution of a sequence $c_1; c_2; \ldots c_n$ of commands corresponds to executing the big-step reductions for $c_1, c_2, \ldots, c_n$ in sequence. Since we assumed that the semantics are effective, in the sense that there are recursive functions implementing the reduction rules, this boils down to applying the corresponding functions implementing the semantics in sequence.

If we add control-flow constructors like if or while, things get a bit more interesting. Consider for example the following simple if command: $\text{if } e \text{ then } c$, where $e$ is an expression and $c$ is a command. The semantics could be given by the two big-step reduction rules $$ \frac{e(s_1)=1\quad s_1 \to_c s_2}{s_1 \to_{\text{if } e \text{ then } c} s_2} \qquad \frac{e(s_1)=0}{s_1 \to_{\text{if } e \text{ then } c} s_1} $$ This gives rise to an evaluation function of the form $E_\text{if}(E_e,E_c,s)$ which takes two functions as arguments, namely the evaluation functions for $e$ and $c$, and the execution state $s$. $E_\text{if}$ is clearly recursive. Since the evaluation functions for $E_e$ and $E_c$ can be derived from the program being considered, we can treat them as parameters and therefore get an implementation function $E_{\text{if } e \text{ then } c}$ that maps execution states to execution states, as above.

Johannes Kloos
  • 9,091