Fortran I

Take a look

Fortran I, which is an ancient programming language (at least for me), had an exotic algorithm to decide which operator will be calculated first. First of all, let's define somethings we need to proceed.

• Let $S$ be a finite set of binary operators which we should consider.
• Let $f:S\rightarrow \mathbb{N}$ be a function which indicates the priority of each operator in $S$.
• If an operator $\otimes\in S$ has a higher priority than $\oplus\in S$, it must hold that $f(\otimes)<f(\oplus)$.

What I want to prove is the following algorithm transforms an math expression

• to an expression that can be evaluated without the priority information
• wihtout changing the evaluation result.

Let's go ahead to the actual algorithm.

Input: S, f, and an math expression E
Output: the transformed expression E'

M := max(f(S))
E' := <M+1 opening parantheses>
For each c in S:
    If c is opening paranthesis:
        E' := <M+1 opening paranthesis>
    Else If c is closing paranthesis:
        E' := <M+1 closing paranthesis>
    Else If c is an operator in S:
        E' := E'||<f(c) closing parantheses>||c||<f(c) opening parantheses>
    Else:
        E' := E'||c
    End If
End
E' := E'||<M+1 closing parantheses>
Return E'

The following is an illustration of each step in a transformation of expression $7\times (2+3)$.

  ⇒ E' = (((
7 ⇒ E' = (((7
× ⇒ E' = (((7)×(
( ⇒ E' = (((7)×((((
2 ⇒ E' = (((7)×((((2
+ ⇒ E' = (((7)×((((2))+((
3 ⇒ E' = (((7)×((((2))+((3
) ⇒ E' = (((7)×((((2))+((3)))
  ⇒ E' = (((7)×((((2))+((3))))))

The number of preceeding unclosed open parantheses in the transformed expression $E^\prime$ takes a crucial role on analyzing what's going on. Let me call it potential on the latter part of this post. The number over each symbol represents the potential of it.

$$\overset{3}{7} \overset{2}{\times} ( \overset{6}{2} \overset{4}{+} \overset{6}{3} )$$

---

An actual proof

There are two things to be proved:

1. The evaluation result doesn't change.
2. It can be evaluated without knowing the operation priority $f$.

Result consistency I & Evaluability without f

First things first, let's go ahead on the first one. We're going to prove that result consistency holds when $E$ doesn't include any parantheses.

Notice that there is no potential difference between right before and right after of each binary operator.

This allows me to say that a potential of each constant number in $E$ is exactly $M+1$ for an integer $M:=\max f(S)$.

Also, a potential of each binary operator $c$ is $f(c)$ smaller (thus at most $M$) than the number right before it.

So, all symbols (includuing numbers and binary operators) have non-negative potentials, which is exactly $M+1-f(c)$ for each binary operator $c$. This ensures the paranthesis validness of $E^\prime$.

Therefore, the symbol with the highest priority (i.e. the minimum value of $f(c)$) has the highest potential. This leads for it to be evaluated first.

At the same time, it means that the second condition, which is the evaluability of $E$ without $f$, does hold.

---

Result consistency II

This part extends the result of the previous part to an expression which includes parantheses.

It can be done by simple logics:

1. An opening paranthesis increases potential by $M+1$.
2. Every valid expression without parantheses cannot decrease the potential larger than $M$.
3. So, an expression which satisfies the followings must evaluate $e^\prime$ first.
   • includes a paranthesized expression $(e^\prime)$
   • and doesn't include any other parantheses
4. It can be proved that $e^\prime$ must be correctly transformed by the given algorithm by an induction.
5. So any expression $E$ can be transformed to $E^\prime$ which satisfies result consistency condition.

---

Summary

So, the given algorithm correctly transform any valid expression $E$ to $E^\prime$, which satisfies two conditions described before.

$E^\prime$ includes too many parantheses to ensure the result consistency, however one can calculate a potential of each symbol rather than putting the actual parantheses.

If one has calculated a potential of each symbol, it is easy to calculate the evaluation result with an well-known algorithm named topological sort.

This transformation can be interpreted as an embedding process of the operation priority to the expression itself.