<figure><img src="image_1.png" /></figure>

HAL
open science

# Duality and hierarchy in data processors

Michel Depeyrot

► To cite this version:

Michel Depeyrot. Duality and hierarchy in data processors. [Research Report] IRIA-RR-090, IRIA. 1974, pp.43. hal-04715938

HAL Id: hal-04715938

https://inria.hal.science/hal-04715938v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Duality and hierarchy
in data processors

<figure><img src="image_3.png" /></figure>

Rapport de Recherche n° 90

Novembre 1974
# DUALITY AND HIERARCHY IN DATA PROCESSORS

## M. DEPEYROT

### Sommaire

Les opérateurs $\lambda$ de CHURCH et $\mu$ de FRASER sont généralisés afin de définir
le traitement de l'information comme une fonctionnelle v mettant en évidence les
propriétés de dualité et permettant d'exprimer de manière cohérente la composi-
tion de calculs parallèles et les instructions conditionnelles de contrôle. Les
notations existantes pour spécifier la traduction et l'exécution des programmes
sont réévaluées de même manière afin de prendre en compte les représentations
de données et de les intégrer dans un modèle présentant les relations formelles
entre compilateurs et interpréteurs.

Trois applications sont déduites :
- une notation en chevrons pour la
manipulation aisée des processeurs et de leurs langages de description,

- un remplacement des schémas actuels
de programmes fondé sur les représentations de langages horizontaux ainsi qu'une
définition syntactique des processus,

- une classification des processeurs
matériels selon le type de leurs grammaires duales.

Afin de montrer la généralité du principe de dualité, la relation est
présentée avec une récente technique de conception de circuits intégrés à grande
échelle.
CHURCH'S λ and FRASER'S µ-operators are generalized to define information processing as a **functional v** exhibiting duality properties and enabling to express consistently both composition of parallel computations and conditional control statements. Notations for specifying program translation and execution are reconsidered in a similar way to take into account data representations and to embed them within a model presenting the formal relationship between compilers and interpreters.

Three applications are derived : - a Chevron notation for handy manipulation of processors and of their description languages,
- a substitute for present program schemata based on horizontal language representations together with a syntactic definition of processes,
- a classification of hardware processors according to the types of their dual grammars.

For the sake of showing the generality of this duality principle, the relationship with a novel LSI circuit design technique is outlined.

**Key words and phrases :** Compiler, interpreter, processor, register transfer language, duality, hierarchy, process, stream, λ-calculus, coassignment, program scheme, portability, transparency, parallelism, design-automation.

"The absence of a rigorously defined notation in which distinct concepts are distinguished separately is one major obstacle to any discussion of system design. A notation in which contexts appear explicitly would be helpful when discussing the design of file systems and other name-handling mechanisms".
Table of Contents

<table><thead><tr><th></th><th></th><th>pages</th></tr></thead><tbody><tr><td>I.</td><td>THE v-FUNCTIONAL FOR λ AND µ-CALCULUS.</td><td>1</td></tr><tr><td>II.</td><td>TRENDS AND TOOLS IN TRANSLATOR MODELING.</td><td>5</td></tr><tr><td>III.</td><td>TRANSLATION AND EXECUTION.</td><td>9</td></tr><tr><td>IV.</td><td>HIERARCHY AND THE CONSISTENCY LAW.</td><td>13</td></tr><tr><td>V.</td><td>THE CHEVRON CONSTRUCTS AND THE CLOSURE ALGORITHM.</td><td>17</td></tr><tr><td>VI.</td><td>DUALITY BETWEEN CONTROL AND DATA TRANSFERS.</td><td>22</td></tr><tr><td></td><td>APPENDIX</td><td>40</td></tr><tr><td></td><td>BIBLIOGRAPHY AND REFERENCES.</td><td>42</td></tr></tbody></table>
# I. THE v-FUNCTIONAL FOR $\lambda$ AND $\mu$ CALCULUS.

Present formal models of data processing - program-schemata, PETRI-nets or $\lambda$-operator - do not yield convincing practical results, while optimization and portability problems in hardware as well as in software design are nowadays acquiring an acute importance, but are still awaiting adequate models of the translation and computation processes.

This paper reports some advances gained through the restructuring of present models using a Duality Principle between program and data structures. Perhaps the most striking application it reveals is a new domain of application of syntactic analysis and grammar synthesis in the architecture of information processors and computation processes.

## I.1. The new functional.

We start with the simplest model of an abstract processor at the level of abstraction of CHURCH's calculus.

### Definition.

The v-operator can be defined as follows :
the expression $v(\varphi_1, ..., \varphi_p) < (k_1, ..., k_p), (d_1, ..., d_q) > (\delta_1, ..., \delta_q)$ can be evaluated through substituting value $\delta_j$ to name $d_j$ in each expression body $\varphi_i$ named by $k_i$ wherever this argument is applied. (Notice the use of special brackets <, > renders the appearance of symbol v redundant).

### Assertion.

CHURCH's $\lambda$-operator [1] and FRASER's $\mu$-operator [13] for $p = 1$ only correspond to the v-functional as follows :
the expression $v(\varphi) < (k), (d_1, ..., d_q) > (\delta_1, ..., \delta_q)$ has the same value as $\lambda[d_1, ..., d_q](\varphi)[\delta_1, ..., \delta_q]$ where $d_j$ is a bound variable identifier and $\varphi$ is the expression body, as well as $\mu[d_1, ..., d_q][\delta_1, ..., \delta_q](\varphi)$ where the first two terms formalize the execution context of $\varphi$.
Basic advantages to be expected from the v-functional result from exhibiting the formal duality between context data and functions (text) as well as between algorithm-control parallelism and argument-access parallelism (called in [2] parallelism of identifier definition); in particular, composition of expressions can be handled in a structured manner so that the following holds:

Occurrence of use of argument $\delta_j$ in expression $\varphi_i$ can be statically represented in a $p \times q$ application matrix $A$, where $a_{ij} = 1$ if $\varphi_i$ requires $\delta_j$, and 0 otherwise. Symbols $k_i$ and $d_j$ respectively are bound body and variable identifiers.

Now the v-calculus opens the way to expressing the calling mechanism of auxiliary functions through intermediate identifiers:

$$ 
\begin{align*}
v(f(x)) < (k), (f,x) > (\varphi, \delta) &\equiv \\
v(f(\delta)) < (k), (f) > [v(\varphi) < (g), (h) >] &\equiv \\
v(\varphi) < (g), (h) > (\delta).
\end{align*}
$$

If a function is defined by $f = \lambda[y,z](2y + 4z)$, then $f \stackrel{\Delta}{\equiv} v(2y + 4z) < (k), (y,z) > (..,..)$ and dually evaluation of $f(x)$ can be denoted $\epsilon = \langle f,x \rangle$ or $v(f) \langle k,d \rangle(x)$ such that $x \stackrel{\Delta}{\equiv} v(\epsilon) < (k), (y,z) > (g,h)$.

## I.2. Duality between compiling and interpreting.

### COMPENSATION THEOREM. I.

Evaluation of compound expressions can be effected in two ways: through context composition of leftward (interpretive approach) or dually through function composition or rightward (compilative approach).

### Proof.

Let us evaluate $\epsilon = v(2y + 4z) < (k), (y,z) > [v(3v+w), 2w) < (g,h), (v,w) > (3,2)]$.

The first way consists in progressive value substitution without explicit generation of an intermediate expression (interpretation):

$$ 
\begin{align*}
\epsilon &= v(2y + 4z) < (k), (y,z) > [v(3v+w) < (g), (v,w) > ; v(2w) < (h), (v) > (2)] \\
&= v(2y + 4z) < (k), (y,z) > (11,4) = 38.
\end{align*}
$$
The dual way consists in progressive expression substitution without intermediate value computation (compiling) :

$$ 
\begin{aligned}
\epsilon &= v[v(2y + 4z) < (k),(y,z) > (3v+w, 2w)] < (1),(v,w) > (3,2) \\
&= v(6v + 10w) < (1),(v,w) > (3,2) = 38.
\end{aligned}
$$

Q.E.D.

All component functions $\phi_i$ have been simultaneously processed in the above example as suggested by parenthesis nesting. It is however possible to get away with this constraint using a **substitution indicator** $\sigma$ specifying for every function $\phi_i$ or argument $\delta_j$ whether it is to be evaluated by **reference** (indirectly from the $v$ expression outside : $\sigma_I$), by **value** (from right to left : $\sigma_V$) or **literally** (from left to right in expression : $\sigma_E$).

**Applications.** 1) Substitution methods can be mixed (applying $\sigma_E$ first, then $\sigma_V$) : 
$$(2y + 4z) < k,(y,z) > (\sigma_V : 3v + w, \sigma_E : 2w) < (g,h),(v,w) > (3,2) = \\ = (2y + 8w) < k,(y,w) > (\sigma_V : 3v + w, \sigma_V : 2) < (1),(v,w) > (3,2) = \\ = (2y + 16) < k,y > (11) = 38.$$

2) A more complex case is encountered when substitution is performed literally with a context being an expression containing as subexpressions variables substituted by value in the global evaluation $\epsilon$ :

$$ 
\begin{aligned}
(2y + 4z) < (k),(y,z) > (\sigma_E : 3v + w, \sigma_V : 2w) < (g,h),(v,w) > (3,2) \\
= (6v + 2w + 4z) < (k),(v,w,z) > (\sigma_V : 3, \sigma_V : 2, \sigma_V : 2w) < 1,w > (2) \\
= (22 + 4z) < k,z > (4) = 38.
\end{aligned}
$$

Relationship between processor duality as in functional $v$ and auto-mata or linear system duality [7,18] can be exhibited in the case of application matrix composition.

$$ \text{Let } A_k = (1 \ 1), A_{g,h} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \text{ and } A_l = (1 \ 1) \text{ be the three} $$

application matrices of the above example. Boolean matrix multiplication (with $1+1=1$) provides the application matrix of corresponding expression composition.
Now let $\alpha_{\varphi}$ and $\omega_{\delta}$ be boolean vectors such that $\alpha_{\varphi} = 1$ in $\varepsilon$ whenever $\varphi_i$ is evaluated (and 0 otherwise), while $\omega_{\delta_j} = 1$ if $\delta_j$ is substituted (and 0 otherwise). The application functional hence appears as $\psi(\varepsilon) = \alpha \Pi_k A_k \omega$ with $\Pi$ the non commutative boolean matrix multiplications with expression index $k$:

$$ \psi(\varepsilon) = (1) (1 \ 1) \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \alpha A_k A_{g,h} \omega. $$

Interpretive evaluation yields $\psi(\varepsilon) = (1) (1 \ 1) \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \alpha A_k \omega' = (1)$, while compilative translation dualy yields $\psi(\varepsilon) = \alpha' A_l \omega = (1)$. The former corresponds to costate transition and the latter to state transition in [18].
## II. TRENDS AND TOOLS IN TRANSLATOR MODELING.

As a first area of application of the v formalism, let us consider problems related to the representation and composition of translators.

### II.1. Historical background.

In [6], WEGNER presents a formalism for the translation and execution processes which is more natural than a previous notation [5]. Two unexplained features however render his function approach unconvincing : first, the representation of a processor as a function with a domain L but no specified range ; second, the repetition of the processor symbol whenever more than a single execution or translation is described.

In [11], EARLEY and STURGIS present a formalism which leads to an algorithm for generating all translators constructible from an initial set of various translators. They differentiate between metacompiler input and compiler input, but they assimilate universal machines as well as specific machines to mathematical functions, and straightforward composition of compiler functions cannot be handled.

In [9], Mc KEEMAN et al. make a thorough use of such notational systems, which makes convincing the need for a rigorous formulation. The main drawback is the inadequacy of these formalisms for Processor Simulation [8] and Register Transfer Languages [10,12].

These problems can be solved using a unified model for functions, processor [11] and data [§III], to which the same cancellation law applies [§V], together with a new consistency law [§IV], based on the concepts of functionals and duality from lattice and category algebra [3]. This leads to a novel definition of information processors in terms of dual grammars pictured as whirl-interconnected oriented graphs [§VI].

We must first transfer the v-functional concepts into the field of sequential machines, graph-representations and black-box notations ; as a result we ultimately will generalize use of the v-functional from assignment statements to conditional control statement.
## II.2. Functions for information processors.

Let $V$ be the automaton-theoretic **Vocabulary** to be used for coding computer data (be they bits, characters, words or larger records). The iterate $V^*$ is the set of all finite structured sets of elements from $V$ displayed as sequences. We will occasionally denote by $U$ the instruction-code or algorithm vocabulary.

A function may be defined as a rule of correspondence between a domain $X$ and a range $Y$ both represented in $V^*$. Following [6], the set of such functions can be denoted $(X/Y)$. The precise correspondence between the domain and the range can be specified as a set of values in $Y$ for arguments in $X$ as in [3] :

$f : X \to Y : x \mapsto f(x)$ (i.e. as a set of values with a coded representation in $V^*$).

A functional [1; chapter 10] is a mapping defined on a couple of functions like $k$ and $d$ and noted $\langle k,d \rangle$.

When translators are concerned, we are not so much interested in the equality of functions since object-programs may well vary from one translator to another for a given source-program, but in the identity of domains and ranges which are the source-language and object-language respectively.

More generally this interest in set-identity rather than value-equality is the case whenever we want to consider the function of a "universal processor" like a universal TURING machine [1,17] or like a digital computer [14], the function of which at a given time in no way characterizes the processor but merely characterizes a specific program fed into it.

The **composite** of two functions $f$ and $g$ is the function obtained by applying them in succession (starting from the left) :

$$ (x) (g \circ f) = f(g(x)), \quad x \in X. $$
For any set S, the function $1_S : S \to S$, which takes every element $s \in S$ into itself, is referred to as the identity function. Different sets hence have different identity functions. The identity law states that for any $f : X \to Y$,

$$1_X \circ f = f = f \circ 1_Y.$$

In order to develop the formalism necessary for expressing the Duality Principle in Computer Science, we need to be able to treat similarly arguments and functions, inasmuch as $f(x)$ can be considered as the application of $x$ on $f$ or as the functional $\langle f, x \rangle$.

Recall every set $S$ can be considered as the set of **element functions** $\{1_S | s \in S\}$ since each element $s \in S$ determines a function $1_S$, whose domain is the identity function $I_S = \{1\}$, that applies each element $s \in S$ onto itself, so that $1_S : I_S \to S : 1 \mapsto s$. Using this fact allows applying the $(X/T)$ set notation of [6] to the application of a function upon a specific argument in $X$.

### II.3. The cancellation law and commutative diagrams.

A diagram, informally speaking, consists of labelled **vertices** $\eta_1, \dots, \eta_N$ together with labelled **arrows** from one vertex to another. Each vertex $\eta_i$ is labelled by an **Entity set** $E_i$ and each arrow $\eta_i \eta_j$ is labelled by a function $f_i$ on $E_i$ to $E_j$.

A **path** is a sequence of arrows $\eta_1 \eta_2 \dots \eta_k$ corresponding to a composite function $f_1 \circ f_2 \circ \dots \circ f_k$ with rightward composition.

A diagram is **commutative** if there exist two paths for the same composite function $f : E_i \to E_j$.

If $f = f_1 \circ f_2 \circ \dots f_k \in (E_1/S_1) (E_2/S_2) \dots (E_k/S_k)$ and the
range $S_i$ of $f_i$ is the domain $E_{i+1}$ of $f_{i+1}$ for $i = 1,2,...,k-1$, then domains and ranges can be cancelled according to the law :

$$C = B \Rightarrow (A/B) (C/D) \subset (A/D) \text{ so that } f \in (E_1/S_k).$$

The corresponding diagram is commutative

<figure><img src="image_4.png" /></figure>

Informally and by analogy with lattice duality [3, chapter XIV], we say that the dual of a diagram is the one obtained by reversing all arrows, so that the dual of $k \subset (X/Y)$ is $d \subset (\bar{Y}/\bar{X})$ where $\bar{S}$ denotes the dual of a set $S$.

But as any scalar a functional is a self-dual operator, i.e. $\langle f,x \rangle \equiv \langle \bar{x}, \bar{f} \rangle = \langle \bar{f}, x \rangle$, up to an adequate interpretation of $\bar{x}$ and $\bar{f}$.

A functional is said to be *weighted* with some weight functional $\langle f, \bar{x} \rangle$ if it can be factorized as $\langle f(\bar{f}), x(\bar{x}) \rangle = \langle f, x \rangle \langle \bar{f}, \bar{x} \rangle$. The meaning of such an expression appears in the sequel [§ IV].
### III. TRANSLATION AND EXECUTION.

#### III.1. Universal processors.

When considering functions which accomplish program translation, we are generally more interested in the domains and ranges, which are source and object-languages, than in the precise rule of correspondence between them. Moreover composition of translations - be they instruction recoding or data reformatting - is applicable even before an argument is applied to the program. This is due to the fact that such functions are universal in the sense that they cannot by themselves result in an execution.

When a function is applied to its argument though, both must be represented, as an algorithm in some programming language L and a data item in some record format F respectively. Then execution can be performed by some interpreter ("software" and/or "hardware").

Following [14; pp. 615-628], we denote P a universal processor, the function of which is to apply programs in (machine-) language K to data in (machine-) format D. Equivalently K is the control unit interpreting the instructions and D is the Data unit transforming the data. A processor executes a function φ on an argument δ; in that sense a function is a specific processor with its control unit fixed and only its data unit variable. But it subsumes an abstract processor v since it does not correspond to some algorithmic realization and it requires no choice of a representation. We hence can write

$$P \triangleq \text{pro}_{\text{KD}} \quad \text{and} \quad v = \text{pro}_{11}.$$

More generally a virtual processor pro<sub>LF</sub> can be defined as the function which applies programs in a higher level language L to their data records in a higher level format F. It requires the execution of a lower level of interpretation in order to provide results.

Let us denote a processor as a universal functional <K,D>, i.e. a generalization of the application <φ,δ> of a function and its argument upon each other. The abstract universal processor v appears to be pro<sub>11</sub> = <1,1>.
### III.2. Algorithm representation.

To go from the abstract functional level to the universal functional level in order to provide an execution, let "cod<sub>L</sub>" be a function that converts a function φ into its coded representation, the algorithm text in the programming Language L, i.e. cod<sub>L</sub> : φ → U* where U is the instruction code. Since normal programming languages are only defined over specific data sets, let us complete the representation with a function "for<sub>F</sub>" which formats the arguments δ into adequate records in F, i.e. for<sub>F</sub> : (X,Y) → V*. This pair (X,Y) belongs to the execution context C ≜ (X,Y). With the function notation of §. II.2., we get :

$$ \text{cod}_L := (1_L/L) \quad \text{and dually} $$

$$ \text{for}_F := (1_F/F). $$

Hence a language L appears as the set of all partial functions from an infinite data alphabet V* representing arguments in context C, to the set of all partial functions (X/Y) on it, coded in the infinite algorithm alphabet U* :

$$ L : V^* \to U^*. $$

Dually a format F appears as the set of all partial functions from the set of all partial functions (X/Y) in U* representing the algorithm text, to the set of all data transformations (X,Y) by it in V* :

$$ F : U^* \to V^*. $$

A universal processor having both its K and D parts free to be specified, is able to execute any function recorded in a manner it can decode. Specifying it requires a transcription which is the pair (cod<sub>K</sub>, for<sub>D</sub>) : (φ,δ) → (U*,V*).

### III.3. Data and value assignment.

The weakness of previous approaches amounted to the traditional attitude of computer scientists paying more attention to structuring programs than data, which leads to an erroneous perception of the nature of information processors.
An **algorithm** for a function $\varphi \in (X/Y)$ now appears as a function $(\varphi/1_K) \in ((X/Y)/1_{(X/Y)^*})$ while a record $\delta$ dually appears as a function $(\delta/1_D) \in (1_X/X)$. The data set of a function with domain X hence is $(1_D/X)$, while the program set of a record in range Y is $(1_K/Y)$. The dual $\bar{\varphi}$ of a function $\varphi \in (X/Y)$ is defined as its transpose $\bar{\varphi} \in (Y/\bar{X})$. Hence $\delta$ is dual to $\varphi$.

**Computation** of the value of a function $\varphi$ for an argument $\delta$ is denoted $\epsilon = \langle\varphi, \delta\rangle$ as a functional in Y. Variables in context C changing value as a result of the computation form the **value** in Y and the **side-effect** of $\epsilon$.

Factorization permitted by the cancellation law provides us with an equivalent formula $\epsilon = (\varphi/1_K) <1_K, 1_C> (1_C/\delta)$, where the computation appears as a functional weighted by the abstract universal processor $\text{pro}_{11} = <1_K, 1_C>$ which is self-dual itself, so that $\epsilon = \langle\varphi, \delta\rangle_I$.

More generally **execution** of a program for $\varphi$ in language K with data record $\delta$ in format D can be denoted as the value assignment $\epsilon = \langle\varphi, \delta\rangle_P$ with its weight $P = \langle K, D\rangle$ being a self-dual universal processor functional : $\langle K, D\rangle = (K/D) = (D/K)$. Hence any computation is a functional weighted by some execution processor P upon which program and data act in similar ways.

## CODING THEOREM. II.

1. $\text{cod}_K(\varphi) = (\varphi/K)$.

2. $\text{for}_D(\delta) = (\delta/D)$.

3. Application of the cancellation law both left and right upon a processor functional results in a higher-level processor (the inversion rule).

### Proof.

1. $\text{cod}_K(\varphi) = (\varphi/1_K) (1_K/K) = (\varphi/K)$ (the Cancellation law).

2. $\text{for}_D(\delta) = (\delta/1_D) (1_D/D) = (\delta/D)$

3. $\epsilon = \langle\varphi, \delta\rangle_P$, $\forall P \Rightarrow \langle\varphi, \delta\rangle_P = \text{cod}_K(\varphi) \cdot P \cdot \text{for}_D(\delta)$ so that $\epsilon = (\varphi/K) \langle K, D\rangle (D/\delta) = \langle\varphi, \delta\rangle$, i.e. the inversion rule permits the replacement of $\text{pro}_{KD}$ by $\text{pro}_{11}$. The same applies more generally as follows :

$$ (L/K) \langle K, D \rangle (D/F) = \langle L, F \rangle = \text{pro}_{LF}. $$

Q.E.D.
Let "bin_L" be the function which applies programs in L to their arguments (abstract data) and let "int_F" be the interpreter of Language L which applies data in F to their functions (abstract programs):

$\text{bin}_L = (L/1_F)$ and $\text{int}_F = (1_L/F)$.

APPLICATION THEOREM. III.

1. $\text{bin}_L = \text{pro}_{\text{FL}} \cdot \overline{\text{for}}_F$.

2. $\text{int}_F = \text{cod}_L \cdot \text{pro}_{\text{FL}}$.

Proof.

From $\epsilon = \text{cod}_L \cdot \text{pro}_{\text{FL}} \cdot \overline{\text{for}}_F$ it appears that:

$$ 
\left. 
\begin{array}{l}
1. \quad \text{bin}_L = (L/1_F) = \langle L,F \rangle (F/1_F) \\
2. \quad \text{int}_F = (1_L/F) = (1_L/L) \langle L,F \rangle
\end{array}
\right\} \text{by the cancellation law.}
$$

Q.E.D.

It is enlightening to notice that forms "bin_L" and "int_F" correspond to the generalizations seen in paragraph I of operators $\mu$ and $\lambda$ respectively.
#### IV. HIERARCHY AND THE CONSISTENCY LAW.

An assembler A which translates from language N with data format G to language K with data format D and which is coded over $<K,D>$ itself must be specified as a pair of functions : the **code-translation** (N/K) and the **data-reformatting** (G/D). This pair of functions $A = ((N/K),(G/D))$ require a processor P to operate jointly. It induces the definition of the assembler-level virtual processor $J = \langle (N/K),(G/D) \rangle_p = \langle A \rangle_p$.

Now consider a higher-level virtual processor H provided by a Translator T from language L with format F : $H = (T)_J$. An execution is **interpretation-like** if it does not produce an intermediate representation of the program and its data. It is **compilation-like** otherwise. In other words, compiler object programs may refer to their data through names, while an interpreter must perform **name-binding** [13], much like a processor performs **address binding** for conditions and actions between its control and data units (§. VI).

##### CONSISTENCY LAW THEOREM. III.

1. The inversion rule is associative and $H = \langle T \rangle_J = \langle (T)_A \rangle_P$.

2. A virtual processor H performs an interpretation-like translation iff the only "cod" and "for" functions that can be defined map into L and F respectively.

##### Proof.

Remember (./.) denotes transcoding, while <.,> denotes executing :

1. $(\varphi, \delta) = (\varphi/L) \langle L,F \rangle (F/\delta) = (\varphi, \delta)_H = (\varphi/L) [(L/N) \langle N,G \rangle (G/F)] (F/\delta) =$
$= (\varphi/L) \langle T \rangle_J (F/\delta) = (\varphi/N) [(N/K) \langle K,D \rangle (D/G)] (G/\delta) =$
$= (\varphi/L) \langle T \rangle_{\langle A \rangle_P} (F/\delta) = (\varphi/L) (L/K) \langle K,D \rangle (D/F) (F/\delta) =$
$= (\varphi/L) \langle (T)_A \rangle_P (F/\delta) = (\varphi/K) \langle K,D \rangle (D/\delta)$.

2. Suppose T is a compiler : $(\varphi/1_L) (1_L/L) J (F/1_F) (1_F/\delta) = \varepsilon$
and $J = \langle A \rangle_P \Rightarrow (\varphi/1_K) (1_K/K) P (D/1_D) (1_D/\delta) = \varepsilon$
so that $T : (\text{cod}_L, \text{for}_F) \rightarrow (\text{cod}_K, \text{for}_D)$.
In otherwords, application of program ($\varphi/L$) for data ($\delta/F$) on compiler T as a functional $\langle\varphi, \delta\rangle_T$ is effective in producing ($\varphi/K$) and ($\delta/D$), while, in an interpretation-like translation, functional $\epsilon = \langle\varphi, \delta\rangle$ can only be effective if it is weighted by virtual processor J. A virtual processor is the site of actual reference binding between its input control and data structures.

Q.E.D.

It is thus useful to distinguish between the (assembler-level) translator $A = ((N/K),(G/D))$ and the (assembler-level) interpreter $\langle A \rangle_P = \langle (N/K), (G/D) \rangle_P$ weighted by an execution processor.

Translation of function $\varphi$ programmed in language L denoted ($\varphi/L$) into program text ($\varphi/K$) by translator ($T_A$) is represented by :

($\varphi/L$) ($L/N$) ($N/K$) $\rightarrow$ ($\varphi/K$).

The dual translation of argument $\delta$ recorded in format F denoted ($\delta/F$) into data context ($\delta/D$) by the translator is represented by :

($\delta/F$) ($F/G$) ($G/D$) $\rightarrow$ ($\delta/D$).

Conjoint translations are mandatory for performing *Type checking*.

The replacement of a sequence of functions by a single function in the translation process is identified with a merging of processor levels. Application of the program ($\varphi/L$) to its data ($\delta/F$) involves an execution over a virtual processor at a given level and the consistency law expresses the fact that execution requires the dual translations at each level. The distinction between compilers and interpreters is in the existence per se of an object-program, i.e. in the factorizability of translation and execution : this distinction can be naturally extended to type-checking that can be performed using argument declarations in F or using actual values in D respectively.

**The Duality Principle : (first version).**

$\epsilon = \langle\varphi, \delta\rangle_P = \overline{\langle\delta, \varphi\rangle_P} \Rightarrow$ Every statement that can be made about a computation can be rephrased through the interchange of function-related and argument-related terms without affecting statements concerning processors (abstract, real or virtual).
Remarks [15].

1. **Transparency** of machine-level A for the L language user means that $K \cap L = \emptyset$ and dually that $D \cap F = \emptyset$ (use of low-level features impossible). One could also say that $T = ((L/N),(G/F))$ is **opaque**: in both cases, what is meant is that P is not visible to the (L,F) user.

2. **Portability** of a translator T with object-language (N,G) that of the virtual processor J means there exists some other processor J' for (N,G) such that T object-code can be equivalently fed into J and J'.

3. Portability is the capability to adapt either a low-level module to a class of interface-compatible higher-level modules, or conversely a higher-level module to a class of interface-compatible lower-level modules. The former sense is basic to the idea of a "universal" or *general-purpose machine*, while the latter is basic to the idea of a "virtual machine".

4. **Adaptability** is the capability to replace a module by a different but equivalent one with respect to others at the same level.

It is interesting at this point to underline a motivation of this work on a new notational system through a comparison with classical commutative diagrams. The inversion rule could be presented as shown on figure 1. (Commutative diagram of the inversion rule).

But function and argument have to be expressed, modified or used simultaneously and the above diagram does not permit an easy factorization of translation and execution. The associativity of function composition with compatible domains and ranges and the dual inversion rule allow us to exhibit new meaningful function groupings like context $C = (X,Y)$ and $int_D$. While $bin_K$ corresponds to data-driven programming, the former is best-fitted to more conventional programming.
<figure><img src="image_5.png" /><figcaption>Fig. 1. Commutative diagram of the inversion rule.</figcaption></figure>
V. THE CHEVRON CONSTRUCTS AND THE CLOSURE ALGORITHM.

Previous notational systems [5,6,9,11] have been shown (§.II.) to be
inconsistent or incomplete. A natural replacement should be provided by func-
tional diagrams of the following type where the context appears as a whole,
subsuming domain X and codomain Y.

A functional diagram of the inversion rule is displayed on figure 2.

But we now present an equivalent set of construct boxes more in the
spirit of previous notational systems.

Definitions.

1) A **chevron** is a V-shaped construct representing a compiler-like translator T.
The left side indicates the source-language and the right side indicates the
record format that T accepts as input, while the basis specifies the object-
processor.

2) An abstract function φ is indicated in the left side of a **rectangle** with the right side reserved for indicating its argument δ. **Transcription** of (φ,δ) into a programmed algorithm is given on an upside down **triangle**, the point of which can be fitted into some chevron accepting its language as input.

3) A processor P is the **basis** of the chevron constructs and merely indicates the
source-code it can accept for execution.

Notice that **vertical adjacency** of constructs denotes translation
as in $(T)_{A}$ as is shown on figure 3 (compiler hierarchy).

Meanwhile **horizontal adjacency** denotes execution duality.

As opposed to [11], the chevron-notation does not present on a single
scheme both the input and output formalism together with a processor construct.
<figure><img src="image_6.png" /><figcaption>Fig. 2. Functional diagram of the inversion rule.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 3. Compiler hierarchy.</figcaption></figure>
4) Notational complements.

<figure><img src="image_8.png" /><figcaption>Fig.4. Application functions : P, µ and λ.
Function bin_L was first called ap_L in [6].</figcaption></figure>

At each translation level like T, the language $\tilde{L}$ and the computer $\tilde{C}$ in which the translator is written, as well as the file system $\tilde{F}$ and the peripheral storage $\tilde{M}$ supporting the data, can be indicated as additional constructs on each side of the chevrons.

<figure><img src="image_9.png" /><figcaption>Fig.5. Carrier language and file.</figcaption></figure>

5) $\tilde{L}$ is the carrier-language and $\tilde{F}$ is the carrier-file. If $\tilde{L} \subseteq L$ and $\tilde{F} \subseteq \tilde{F}$, then language L is said to be self-translatable.

6) If $(\tilde{L}, \tilde{F}) \neq (N, G)$ while $P \in \tilde{C}$, a bootstrap of T on C must be performed [5] through a translator $\tilde{T}: (\tilde{L}, \tilde{F}) \to (N, G)$.
7) A compiler-like translator is represented as a chevron, while an interpreter has the shape of a processor. If the interpreter corresponds to a virtual processor, then a lower translation process is required with adequate transcription :

<figure><img src="image_10.png" /><figcaption>Fig. 6. Interpreter hierarchy.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 7. Constructs and Composition rules.</figcaption></figure>

We can now show that our formalism subsumes all previous approaches ;
in the last section (§. VI), we show how it actually permits to tackle a new
class of problems and phenomena.

The chevron-notation can be defined as a pair $\mathfrak{F} \triangleq \{C, \mathcal{R}\}$ where $\mathcal{R}$ is the set of four constructs (function, transcription, translator, processor), and $\mathcal{R}$ is the set of four composition rules defined as shown on figure 7.
## CLOSURE THEOREM. IV.

The closure $C^*$ of the set of possible processor constructs that can be derived from an initial set $C$ is automatically generated through repeated applications of $\mathcal{R}$.

The proof is essentially the same as that in [11].

## COROLLARY. (Secable Compilers)

<figure><img src="image_12.png" /></figure>

A compiler whose semantic phase produces a (quadruple) intermediate abstract program form can be de-composed into a processor and a transcriptor.

As an illustration of the chevron notation, let us use the CWL meta-compiler example of [11] with $f : SL \to ML$.

<figure><img src="image_13.png" /><figcaption>Fig. 8. Metacompilation.</figcaption></figure>

Here the source language SL and the object language ML appear in the CWL context, i.e. as data with respect to the compiler function (ML is in the range). A metac Compiler basically is a *Translator Simulation Language*. As a natural next step, we now apply the duality formalism upon *Processor Description Languages* (or Register Transfer Languages [12]).
# VI. DUALITY BETWEEN CONTROL AND DATA TRANSFERS.

Lack of structure in program schemata is responsible for the fact that architectural problems of processors could not be handled with them.

The Duality Principle in Information processing is the clue for a better understanding of Computer System structures and it reveals in what sense sequential and TURING-type machines are too degenerate models for architectural purposes.

## VI. I. Static description of a processor.

<figure><img src="image_14.png" /><figcaption>Fig.9. Formal processor.</figcaption></figure>

A computer system is a universal function which inputs some data set X in $V^*$ (including both program $\varphi$ and data $\delta$), processes it through intermediate storage components called **registers** (one per record) and outputs a data set Y in $V^*$. So it is similar to a language permitting to express every specific computation. More symmetry can be introduced between K and D if K is allowed to write on U* (non pure programming).
Inadequacies of TURING model arise from its inability to handle words, i.e. data formats subsuming spatial iteration in processors (e.g. one iteration per bit in a word). Insufficiency of sequential machines is due to their inability to express parallel activities, i.e. non independent synchronous control state transitions (e.g. simultaneous control of memory access for one word and data transformation for another). We hence propose a model whereby a processor can be considered as a pair of languages with dual grammars for control and assignment statements.

## Definition.

A processor P is a self-dual functional pair (K,D) where K and D are whirl-interconnected units respectively processing control activations and data operations (with state spaces Z in U* and W in V* respectively) according to dual sets of statements taking the form of grammar rules. The control statement grammar is:

$$G_K \stackrel{\Delta}{=} \{\text{CONDITION ON } W : w, z_i \rightarrow \text{ACTIVATE}(z_1, \dots, z_j, \dots, z_p)\},$$

where p is the degree of parallelism in K, meaning that whenever K in state $z_i$ receives condition signal w out of W, its next active states $z_j$ are selected according to the ACTIVATE statement; $z_j$ represents the state eventually activated within submodule $K_j$ capable of autonomous simultaneous activity within K.

Similarly, if we denote a variable $M_s$ (a memory register) by its value $w_s$ (its contents), the assignment statement grammar is:

$$G_D \stackrel{\Delta}{=} \{\text{ACTION ON } Z : z, w_r \leftarrow \text{OPERATE}(w_1, \dots, w_s, \dots, w_q)\},$$ where q is the number of word registers in D, meaning [12] that in order to transfer register contents according to the OPERATE statement into register $w_r$, D must receive action signal z out of Z.

$G_K$ and $G_D$ grammars specify the semantics for each other through output function $\sigma$ from K: $W \times Z \rightarrow Y$ and valuation function $\alpha$ from D: $M \rightarrow W$, respectively imbedded within ACTION and CONDITION for the sake of simplicity here.

## SELF-DUALITY THEOREM. V.

Self-dual processor model $<G_K, G_D>$ subsumes previous computer languages and processors [16].

Control statements (binding Instruction Sequencing) and Assignment statements (binding Data Access) can be put in one-to-one correspondance, up to a reversal of the arrow of time.
## Proof.

Any ACTIVATE rule being conditioned by W, it can be straightforwardly transformed into a BRANCH (IFTHENELSE) or JUMP (GO TO) sequential instruction, or else into a FORK (AND), a JOIN (WAIT) or QUIT parallel instruction, through adequate definition of a condition register in D.

Any OPERATE rule being actionned by Z, it can dually be transformed
into a MOVE (with MASK), a STORE or LOAD or IMMEDIATE, through adequate action
signal distribution from K.

Notice a TURING machine is a degenerate form of a processor P since
$G_D$ rules have a monomial codomain ($q = 1$) so that
$z_j, w_r \leftarrow \text{OPERATE}(w_s)$, where values $w_s$ and $w_r$ are successively
contained by the same register $M_h$ such that $\alpha(M_h) = w_s$ initially and
$w_s, z_i \rightarrow \text{ACTIVATE}(z_j)$.

Also the uniform recurrent equation model of [4] is a degenerate case
of a transfer unit D, the rules of which are independent of any z :
$\{w_r \leftarrow \text{OPERATE} (..., w_s, ...}\}$.

Q.E.D.

Dual grammars $G_K$ and $G_D$ of a processor P formalize a horizontal language in a way comparable to "program schemata" for vertical languages (with labels and JUMPS). The ACTIVATE and OPERATE statements are advantageous with respect to sequential machine state tables since most algorithms K correspond to incompletely specified machines, and dually not all possible register interconnections are linked in an operator unit D.

$G_D$ can be viewed as a set of **access restrictions** on the data set much
like $G_K$ is a set of **ordering constraints** on instructions. Now **programming P**
amounts to stating a non-ordered set of (OPERATE) declarations in $G_D$ and of
(ACTIVATE) instructions in $G_K$. Then **executing** amounts to specifying $G_D$ initial
input assignment $w_\lambda$ in $V^*$ and $G_K$ initial state $z_0$ in $U^*$, i.e. pointing to a
grammar axiom in the latter case.

For properly representing the dynamics of a computation, context C
should actually be defined as a triple $C \triangleq (W, X, Y)$ of potentially overlapping
sets where X is the domain, Y the range and W is the set of intermediate local
variables.
Note: Processor P is deterministic or non-ambiguous whenever both its grammars $G_K$ and $G_D$ are deterministic or non-ambiguous respectively.

Now a Register Transfer Language (RTL) or a Processor Description Language can be represented with Chevron Constructs in C according to their simulation mode.

<figure><img src="image_15.png" /><figcaption>Fig. 10. RTL Compiler and Interpreter.</figcaption></figure>

Duality implies that trade-offs are possible between rules in $G_K$ and $G_D$ at design-time for a given processor P. This is SHANNON'S Theorem [17, chapter 11] on Turing machine transformations : it was rediscovered in [10] for micromachines. What is more, the Chevron notation elaborated on more mathematical grounds than previous notations, now appears to be the only one fitting the RTL representation problem. It helps formalize the fact that an RTL like [12]
must receive as inputs: first a description of K and a description of D, then
an instance $\tilde{u}$ of program executable through calls of K-microprograms for a
set of operands given in the format executable through D. The Chevron notation
also helps express the fact that program $\tilde{u}$ must be able to be compiled into a
sequence of microinstructions independently of the choice of operands.

## VI.2. Oriented graph whirl-interconnection and syntactic classification of processors.

$G_K$ is a transition-output machine (MEALY-type), while $G_D$ is a state-output machine (MOORE-type).

Let $G_K$ be an oriented graph associated with control grammar $G_K$ so that each arrow corresponds to a state $z_i$ and each vertex admits an ACTIVATE statement as its entity set; dually $G_D$ is an oriented graph associated with access grammar $G_D$ so that each arrow corresponds to a data register $w_s$ and each vertex admits an OPERATE statement as its entity set. Outputs from either graph to the other leave arrows to reach vertices, i.e. whirl interconnection is from one function set to the other entity set (§. II.3.).

See Fig. 11. Dual graphs of a processor.

Dual graphs $G_K$ and $G_D$ with a whirl-interconnection provide with two different ways of dynamically following execution of an algorithm $\varphi$ with argument value $\delta$ along paths between nodes ordered by the grammar rules. It is noticeable that transitions in $G_K$ and $G_D$ occur alternately.

Recall [9] there exist four classes of languages defined in terms of grammars that are quadruples $G = (\gamma, T, \rho, \sigma)$ where
1. $\gamma$ is a *vocabulary* (or alphabet),
2. $T$ is the *subalphabet* in $\gamma$ of *terminal symbols*,
3. $\rho$ is a finite set of *rules* (or *productions*), and
4. $\sigma$ is the *axiom-symbol*, belonging to the alphabet $M = \gamma\backslash T$ of *metalinguistic* (or *grammatical*) variable.
<figure><img src="image_16.png" /><figcaption>Fig. 11. Dual graphs of a processor.</figcaption></figure>
Type 3 or regular language :

s :: = u or s :: = s'v with u,v ∈ T, and s,s' ∈ M (symbols).

Type 2 or context-free language :

s :: = ṽ (or Λ) with ṽ ∈ V* and s ∈ M.

Type 1 or context-sensitive language :

x s y :: = x ṽ y with ṽ ∈ V⁺ ⪢ V* \ Λ, and s ∈ M and x,y ∈ V*.

Type 0 or phrase-structure language :

s :: = ṽ with ṽ ∈ V* and s ∈ V⁺.

Grammars $G_K$ and $G_D$ of a processor P can be put under one of these forms as follows :

$\{w, z_i \to \text{ACTIVATE} (z_1, \dots, z_j, \dots, z_p)\} \equiv \{z_i :: = w z_1 \oplus \dots \oplus w z_p\}$ and

$\{z, w_r \to \text{OPERATE} (w_1, \dots, w_s, \dots, w_q)\} \equiv \{w_r :: = z w_1 \oplus \dots \oplus z w_q\}$.

Axioms correspond to initial state $(z_0)$ and final result register $(w_0)$ specification. Metalinguistic symbols are actions $(z_i \in K_i)$ and variables $(w_r \in M_r)$ respectively. Terminal elements are (w-ACTIVATE) conditions for $G_K$ as well as final states (QUIT or STOP), and (z-OPERATE) actions for $G_D$ as well as immediate values or interface registers forming context $w_\lambda$ in D.

## SINGLE CONTENTS RULE. VI.

Grammars $G_K$ and $G_D$ are subjected to the consistency constraint whenever the same metalinguistic symbol appears several times within the same derivation $(v_1 s v_2 s v_3)$, i.e. for two occurrences of the s symbol, a single derivation results :

for a complex state transition $(k_1 z_i k_2 z_i k_3)$, successors of $z_i$ are identical, dually for multiple operand access $(d_1 w_j d_2 w_j d_3)$, predecessors of $w_j$ are identical.
Now two languages $L_K$ and $L_D$ are associated with a processor P by its grammars $G_K$ and $G_D$: on the one hand, from any initial state $z_0$, the set $Z^*$ of state sequences that can follow until any final state $z_\lambda$; on the other hand, for any specified register for result $w_0$, the set of value sequences $W^*$ that may converge into it from any specified initial context $w_\lambda$ of immediate values and interface registers.

Analysis $\mathcal{A}$ of an assignment or access expression E resulting in $w_0$ in D, through $G_D$, yields a sequence $Z^*$ of transitions in K that activate the generation of this expression E. The execution *stream* in $G_D$ is the sequence of register contents $w_\lambda, w_{\lambda-1}, \dots, w_1, w_0$ as generated by D from $w_0$.

Dual analysis $\bar{\mathcal{A}}$ of control or sequencing expression $\bar{E}$ initialized by $z_0$ in K, through $G_K$, yields a sequence $W^*$ of register conditions required for the processing of this expression $\bar{E}$. The execution *process* in $G_K$ is the sequence of state descriptors $z_0, z_1, \dots, z_{\lambda-1}, z_\lambda$ as generated by K until final state $z_\lambda$ is reached.

We have thus emphasized how duality implies the reversal of the arrow of time, much like in Algebra [3].

## CHARACTERIZATION LEMMA. VII.

1) Processor grammars are of types 3,2 or 1 only.

2) $G_K$ is context-free if there is no FORK state ($k_1, z_1, k_2, z_2, k_3$ then impossible), while $G_D$ is context-free if there is no MULTIPLE STORE action, i.e. any duplication of some register content ($d_1, w_j, d_2, w_j, d_3$ then impossible).

3) Grammar $G_D$ of a processor performing translations only (a Link L in PMS), or complementing and shifting, is regular (linear stream).

4) Grammar $G_K$ of a processor without parallelism (neither FORK, nor JOIN) is regular.

**Note**: Points 3 and 4 correspond to the case of a TURING machine.
Application of $(z_0, w_\lambda)$ upon P initializes K which spreads activity throughout D. Reading of final state $(z_\lambda, w_0)$ stops K which halts activity within D. Processor execution $\epsilon$ thus appears as a dynamical system jointly defined by a process $\{z_t\}^t$ and a stream $\{w_{\lambda-t}\}^t$ with dual trajectories so that :

$$ \epsilon_t = (z_t, w_{\lambda-t}). $$

In terms of the v-calculus one can write :

$\epsilon_t = (z_t) < (\text{ACTION } k), (\text{CONDITION } d) > (w_{\lambda-t})$, and this shows how register contents resolve stream generation ambiguities, i.e. among all possible execution sequences, algorithm u chosen in U* selects possible streams at programming time (compilative manner), and argument v given in V* enables the chosen process at computation-time (interpretive manner) to yield the desired stream.

It is remarkable that interpretation of a program corresponds to a generation by $G_K$ and an analysis $\bar{a}$ (from $w_\lambda$ to $w_0$) by $G_D$, while compiling corresponds to an analysis $\bar{a}$ by $G_K$ and to fragmenting a program into processes through a generation by $G_D$.

### VI.3. Handling control statements within v-expressions.

In order to emphasize to which extent v-functionals help put together present scattered models (from sequential machines to $\lambda$-calculus), it is enlisting to develop a paradigm for composition of conditional statements.

See Fig. 12. Graph $G(K,K')$ of an algorithm with parallel control. (Completely specified automaton).

For the sake of generality, the example [generalized from 18] includes control parallelism, so that states $z'_1, z'_2$ can be considered as those of a separate submodule K' with $Z' = \{z'_0, z'_1, z'_2\}$, while $\{z_0, z_1, z_2, z_3\}$ belong to submodule K and both are connected through FORK-state $z_1$ and JOIN-state $z_3$.

Graph $G(K,K')$ is the carrier of our paradigm text $\tilde{u}$ (e.g. a microprogram) which corresponds to an incompletely specified automaton possibilistic (i.e. with parallelism) and is given in an ALGOL-LIKE language :
<figure><img src="image_17.png" /><figcaption>Fig. 12. Graph G(K,K') of an algorithm with parallel control (completely specified automaton).</figcaption></figure>
BEGIN UTILDA,

WHILE Z = 0 THEN R := 2 AND D := 0 THEN Z := 1,

WHILE Z = 1 THEN Y := R + 2T AND V := SIGN(X) AND IF V = 0 THEN Z := 1

ELSE IF V = 1 THEN Z := 2 AND ZPRIME := 1,

WHILE ZPRIME = 1 THEN X := R + V THEN ZPRIME := 2,

WHILE ZPRIME = 2 THEN W := PARITY (X) AND X := X + 1 AND D := 1

AND IF W = 1

THEN ZPRIME := 2 ELSE IF W = 0 THEN ZPRIME := 0,

WHILE Z = 2 THEN R := -Y AND V := PARITY(T) AND IF V = 0 THEN Z := 2

ELSE IF V = 1 AND W = 0 AND D = 1 THEN Z := 3,

WHILE Z = 3 THEN Y := Y + X THEN Z := 0, END UTILDA.

Notice that both the FORK and JOIN states have an AND control logic.

See Fig. 13. Graph $G_D$ of the v context (V,W,R,T,X,Y).

Dual grammars separating control rules and assignment rules can now be exhibited as follows :

$G_K$ : CONDITION, STATE → ACTIVATION (PARALLEL STATES),

$G_D$ : ACTION, RESULT REGISTERS ← OPERATION (OPERAND REGISTERS).

<figure><img src="image_18.png" /></figure>

It is remarkable that time operates in opposite ways with respect to the productions of one and the other grammars.
<figure><img src="image_19.png" /><figcaption>Fig. 13. Graph $G_D$ of the v context (V,W,R,T,X,Y).</figcaption></figure>
<table><thead><tr><th>Z</th><th>Z'</th><th>RESULT</th><th>OPERATE (OPERANDS)</th></tr></thead><tbody><tr><td>0</td><td>V</td><td>R</td><td>TRANSFER : 2</td></tr><tr><td>1</td><td>V</td><td>Y</td><td>WEIGHT(1,2) : R,T</td></tr><tr><td>1</td><td>V</td><td>V</td><td>SIGN : X</td></tr><tr><td>2</td><td>V</td><td>R</td><td>COMPLEMENT : Y</td></tr><tr><td>2</td><td>V</td><td>V</td><td>PARITY : T</td></tr><tr><td>3</td><td>V</td><td>Y</td><td>SUM : X,Y</td></tr><tr><td>V</td><td>1</td><td>X</td><td>SUM : R,V</td></tr><tr><td>V</td><td>2</td><td>W</td><td>PARITY : X</td></tr><tr><td>V</td><td>2</td><td>X</td><td>INCREMENT : X</td></tr><tr><td>0</td><td>V</td><td>D</td><td>RESET : 0</td></tr><tr><td>V</td><td>2</td><td>D</td><td>SET : 1</td></tr></tbody></table>

Developing this paradigm tends to demonstrate that v-functionals provide us with the adequate tool for investigating problems related to whirl-interconnections of automata interlacing their outputs.

The `{(Z,Z')|(V,V')}` or `{ACTIONS/CONDITIONS}` interface form the "vertical" or "execution" interface of the processor $P = \langle K,D \rangle$ as defined by program u.

See Fig. 14. Graph $G_K$ of the u algorithm text (incompletely specified automaton).

Let the initial values v for immediate operands be $V = 0$, $T = -3$ and $X = 1$. Terminal text Context `{z<sub>0</sub>,z'<sub>0</sub> : INITIAL (V,T,X), FINAL (Y,R,V,W)}` of P forms an interface said "horizontal" between the call-level and the z-transition level. It corresponds to vertical adjacency (fig. 3).

See Fig. 15. Graph $G(D)$ of Register Transfers in D.

A third type of interface called "transverse" can be distinguished between processors at the same semantic level, like $\langle K,D \rangle$ and $\langle K',D' \rangle$ where $D'$ is that part of D activated by $K'$. Here $\langle (z_1,z_3) : (V,R,W) \rangle$ form this interface. See the remark (4) on adaptability in §.IV.

When a function-argument pair in $\epsilon = \langle f,x \rangle$ is replaced by a text-context pair in $\epsilon = u \langle K,D \rangle$, two activation modes can be chosen according to whether a data transfer on v or an algorithm transition in u is to be per-
<figure><img src="image_20.png" /><figcaption>Fig. 14. Graph G_K of the u algorithm text
(incompletely specified automaton).</figcaption></figure>
<figure><img src="image_21.png" /><figcaption>Fig. 15. Graph G(D) of Register Transfers in D.</figcaption></figure>
formed first. The latter is most frequent reflecting the fact that D-Units generally take the form of a MOORE-machine (state-output) ; executions can be expressed respectively as follows :

$$
\begin{align*}
 w_r ::&= z_i\text{-OPERATE } (w_1, \dots, w_q) \text{ or} \\
 w_r ::&= (\sigma_v : z_i) < K_i, (M_1, \dots, M_q) \\
       &> (w_1, \dots, w_q)
\end{align*}
$$

then

$$
z_i ::= w_r - \text{ACTIVATE} (\dots z_j \dots) \text{ or}
$$

$$
z_j :: \Leftrightarrow (z_i) < K_i, M_r > (\sigma_E : w_r)
$$

yields

$$
\epsilon = (z_i) < K_i, M_r > (\sigma_v : z_i) < K_i, M_s > (w_s)
$$

<figure><img src="image_22.png" /></figure>

$$
z_i ::= w_s - \text{ACTIVATE} (\dots z_j \dots) \text{ or}
$$

$$
z_j ::= (z_i) < K_i, M_s > (\sigma_E : w_s)
$$

for $j \in \{1, \dots, p\}$

then

$$
w_r ::= z_j - \text{OPERATE } (w_1, \dots, w_q)
$$

$$
w_r ::= (\sigma_v : z_j) < K_j, (M_1, \dots, M_q) \\
      > (w_1, \dots, w_q)
$$

yields

$$
\epsilon = (z_i) < K_i, M_s > (\sigma_E : w_s) P (w_1, \dots, w_q)
$$

<figure><img src="image_23.png" /></figure>

The overall execution becomes in the former case :

$$
\epsilon = (z_1, \dots, z_i, \dots, z_p)(K, M_r)(\sigma_v : z_i) < K_i, D > (w_1, \dots, w_s, \dots, w_q)
\text{and in the latter case : } (z_1, \dots, z_i, \dots, z_p) < K, M_s > (\sigma_E : w_s) < K_j, D > (w_1, \dots, w_s, \dots, w_q).
$$

This can be summed up by stating that any state is either a control
"function" : $z_i < K_i, M_s > (\sigma_E : .)$ or dually an assignment function :
$(\sigma_v : z_i) < K_i, M_s > (.)$.

Self-duality implies that :

$$
\begin{align*}
\epsilon(z_i, w_s) &= z_i < K_i, M_s > w_s = w_s < M_s, K_i > z_i \\
&\equiv (z_j, w_r) \triangleq \epsilon(z_j, w_r).
\end{align*}
$$

And this whole transformation corresponds to a processor clock cycle-time.
But it can be decomposed as follows :

$$z_i <K_i, M > (\sigma_E : w_s) = (\sigma_V : z_j) <K, M > w_s = z_j <K, D > (\sigma_E : w_r).$$

$$\text{or } (\sigma_V : z_i) <K_i, M > (w_s) = z_i <K_i, D > (\sigma_E : w_s) = (\sigma_V : z_i) <K, D > w_r.$$

And the application matrix is a fixed matrix specifying which ACTIONS are effected by which states (See graphs G(D) or G_D).

**Example** : In our paradigm, this functional presentation yields the following dual trajectories :

$$\begin{align*}
\epsilon_0 &= \sigma_V : (0,0) < (K,K') ; (V,W,R,T,X,Y) > (0,*,*,-3,1,*) \\
&= (0,0) < (K,K') ; D) > \sigma_E : (0,0,2,-3,1,*) = \\
\sigma_V &= (1,0) \quad P \quad (0,0,2,-3,1,*) \\
&= (1,0) P \quad \sigma_E : (1,0,2,-3,1,-4) = \\
\sigma_V &= (2,1) P \quad (1,0,2,-3,1,-4) \\
&= (2,1) P \quad \sigma_E : (1,0,+4,-3,3,-4) = \\
\sigma_V &= (2,2) P \quad (1,1,+4,-3,4,-4) \\
&= (2,2) P \quad \sigma_E : (1,0,+4,-3,5,-4) = \\
\sigma_V &= (3,0) P \quad (1,0,+4,-3,5,-4) \\
&= (3,0) P \quad \sigma_E : (1,0,+4,-3,+5,+1) = \\
\sigma_V &= (0,0) <K,D> (1,0,+4,-3,5,+1) = \epsilon_{\lambda} \quad (\text{Here } \lambda = 5).
\end{align*}$$

## VI.4. Toward a general Duality Principle.

We have shown that $\lambda$ and $\mu$ operators provide static models of information processors while their whirl-interconnection within the v-functional provides a representation of their dynamics much like a composition of sequential machines with proper additional semantics.

Moreover we can now formulate a second version of the Duality principle :

Every statement that can be made about a program execution can be rephrased through the interchange of terms related to control sequencing (scheduling, synchronization) and to data access (allocation, communication) together with a reversal of the arrow of time, thus putting program structure and data structure in one-to-one correspondance.
A thorough application of such a principle in Control Science [7,17] has proved to be most fruitful; its generalization to Information Processing [18] appears promising. In particular, the present appearance of Syntactic Analysis in the field of processor design should give a renewed emphasis to the theoretical study of grammars in the area of horizontal (or label-free) languages.

It opens a new area of investigation that could lead to the design of an optimizing compiler for "horizontal microprograms" (label-free) as opposed to programs for units disposing of an instruction counter for "vertical programs".

Finally this functional approach provides us with a rigorous way to distinguish among three classes of interfaces (vertical between K and D, horizontal between processors at different levels in a hierarchy, transverse at the same semantic level). The kind of distinction should lead to a better understanding of compatibility and portability features with the ultimate aim of being able to design a universal K/D interface for arbitrary instruction codes and data formats [15].

It is enlightening at this point to ponder upon reading the excerpt following in the Appendix. The difficulty in formulating any basic principle in Computer Science precisely is the "absence of a rigorously defined notation" mentioned by FRASER as quoted in the Abstract.
"SOFTWARE ENGINEERING TECHNIQUES".

Editors: J.N. BUXTON, B. RANDELL.

ROME - ITALY (27-31 October 1969).

**STRACHEY** : Until we have a sufficient body of topics which are important, relevant and well developed, we cannot call the subject a "science". I am quite convinced that in fact computing will become a very important science. But at the moment we are in a very primitive state of development ; we don't know the basic principles yet and we must learn them first. If universities spend their time teaching the state of the art, they will not discover these principles and that, surely, is what academics should be doing.

I do not for a moment underestimate the importance of the state of the art in engineering. Clearly it is essential and furthermore, from engineering practice, we must get our experience and material from which we develop theory. But, before teaching students, we must get our basic principles right.

**WOODGER** : I wonder what a basic principle in computer science would look like if I saw one. Seriously, in what terms might it be expressed ? It is no good using unexplained terms like "language" or "compiler" ; we have very few clear terms in which to express any fundamental principle of computer science. Would any professor here tell me here a single basic principle ?

**PERLIS** : Some principles : every interesting program has at least one *variable*, one branch and one loop. An interesting program is one whose number of execution steps is not linearly proportional to the length of the text.

**STRACHEY** :

And at least one bug !

**PERLIS** :

No, I don't accept that that is a principle.
**WOODGER :**

Well, the concept of "variable" is far from trivial, at the least.

**FALKOFF :**

I'm not a university professor but I would like to say something about basic principles. Last summer we assembled a group of school mathematics teachers and set out collecting material to give them a basis for working with APL in teaching high school mathematics. We found there were only a few essential notions that the pupils needed in order to use a programmable machine. These were:

1. THE NOTION OF ASSIGNMENT, which I think covers the idea of a variable.

2. THE NOTION OF A CONDITIONAL EXPRESSION or branch.

3. THE NOTION OF FUNCTION DEFINITION.

I propose that these three ideas are central to computing and will remain so.

**GOTLIEB :**

One basic principle with regard to programs is that *execution time* and *store utilization* are interchangeable. In a good program, you can improve one only at the expense of the other.

REPORT ON A CONFERENCE SPONSORED BY THE
NATO SCIENCE COMMITTEE (pp. 65-66).
[1] M.DAVIS. "Computability and unsolvability".
Mc Graw Hill. (1958).

[2] P.J.LANDIN. "The mechanical evaluation of expressions".
Computer Journal, Vol.6, pp.308-320. (January 1964).

[3] S.Mac LANE, G.BIRKHOFF. "Algebra".
The Mac Millan Company. (1967).

[4] R.M.KARP, R.E.MILLER, S.WINOGRAD. "The organization of computations for uniform recurrence equations". J.ACM, Vol.14, nr.3, pp 563-590. (July 1967).

[5] J.SLANSKY, M.FINKELSTEIN, E.C.RUSSELL. "A formalism for program translation".
J.ACM., Vol.15, nr.2, pp.165-175. (April 1968).

[6] P.WEGNER. "Translation networks and function composition".
J.ACM., Vol 16, nr.2 ; pp. 263-265. (April 1969).

[7] R.E.KALMAN, P.L.FALB, M.A.ARBIB. "Topics in Mathematical System Theory".
Mc Graw Hill. (1969).

[8] M.DEPEYROT. "Un modèle algébrique réaliste de calculateur".
Proceedings AFCET, [PARIS], S.I-4, pp.59-73. (Septembre 1970).

[9] Mc KEEMAN et al. "A compiler generator implemented for the IBM System/360". Prentice Hall. (1970).

[10] E.P.STABLER. "Microprogram Transformations".
IEEE-C, Vol. 19, nr.10, pp, 908-916. (October 1970).

[11] J.EARLEY, H.STURGIS. "A formalism for translator interactions".
Com.ACM, Vol.13, nr.10, pp.607-617. (October 1970).
[12] F.ANCEAU et al. "A language to describe Digital Systems". Edited by J.TOU in "Software Engineering". Academic Press. (1970).

[13] A.G.FRASER. "On the meaning of names in programming systems". Com.ACM, Vol.14, nr.6, pp.409-416. (June 1971).

[14] C.G.BELL, A.NEWELL. "Computer Structures : readings and examples". Mc Graw Hill. (1971).

[15] M.DEPEYROT. "Link dynamics and interface decomposition in PMS". Proceedings of the "Advanced EEC Course on Computer System Architecture". (December 1972). [To be published : HERMANN].

[16] J.L.BAER. "A survey of some theoretical aspects of multiprocessing". ACM. Computing Surveys, Vol.5, nr.1, pp 31-80. (March 1973).

[17] P.FAURRE, M.DEPEYROT. "Eléments d'Automatique". DUNOD. (1974).

[18] M.DEPEYROT. "Coassignment on universal macromodules for diode-free LSI programming". (submitted for publication).