Flow chart language

Flow chart language (FCL)

Paradigm	imperative
Designed by	Carsten K. Gomard, Neil D. Jones, John Hatcliff
First appeared	1989, 1993, 1998

Flow chart language (FCL) is a simple imperative programming language designed for the purposes of explaining fundamental concepts of program analysis and specialization, in particular, partial evaluation. The language was first presented in 1989 by Carsten K. Gomard and Neil D. Jones. ^[1] It later resurfaced in their book with Peter Sestoft ^[2] in 1993, and in John Hatcliff's lecture notes ^[3] in 1998. The below describes FCL as it appeared in John Hatcliff's lecture notes.

FCL is an imperative programming language close to the way a Von Neumann computer executes a program. A program is executed sequentially by following a sequence of commands, while maintaining an implicit state, i.e. the global memory. FCL has no concept of procedures, but does provide conditional and unconditional jumps. FCL lives up to its name as the abstract call-graph of an FCL program is a straightforward flow chart.

An FCL program takes as input a finite series of named values as parameters, and produces a value as a result.

Syntax

We specify the syntax of FCL using Backus–Naur form.

An FCL program is a list of formal parameter declarations, an entry label, and a sequence of basic blocks:

<p>::= "(" <x>* ")" "(" <l> ")" <b>+ 

Initially, the language only allows non-negative integer variables.

A basic block consists of a label, a list of assignments, and a jump.

<b>::=<l> ":" <a>* <j>

An assignment assigns a variable to an expression. An expression is either a constant, a variable, or application of a built-in n-ary operator:

<a> := <x> ":=" <e><e> := <c> | <x> | <o> "(" <e>* ")" 

Note, variable names occurring throughout the program need not be declared at the top of the program. The variables declared at the top of the program designate arguments to the program.

As values can only be non-negative integers, so can constants. The list of operations in general is irrelevant, so long as they have no side effects, which includes exceptions, e.g. division by 0:

<c>::= "0" | "1" | "2" | ... <o>::= "+" | "-" | "*" | "=" | "<" | ">" | ... 

Where =, <, ... have semantics as in C. The semantics of - is such that if x-y<0, then x-y=0.

Example

We write a program that computes the n^th Fibonacci number, for n>2:

(n) (init)  init: x1 = 1       x2 = 1  fib:  x1 = x1 + x2        t = x1       x1 = x2       x2 = t        n = -(n 1)        if >(n 2) then fib else exit  exit: return x2 

Where the loop invariant of fib is that x1 is the (i+2-1)^th and x2 is the (i+2)^th Fibonacci number, where i is the number of times fib has been jumped to.

We can check the correctness of the method for n=4 by presenting the execution trace of the program:

${\displaystyle {\begin{aligned}&\left({\mathtt {init}},\ \left[n\mapsto 4,\ x1\mapsto 0,\ x2\mapsto 0,\ t\mapsto 0\right]\right)\\\rightarrow &\left({\mathtt {fib}},\ \left[n\mapsto 4,\ x1\mapsto 1,\ x2\mapsto 1,\ t\mapsto 0\right]\right)\\\rightarrow &\left({\mathtt {fib}},\ \left[n\mapsto 3,\ x1\mapsto 1,\ x2\mapsto 2,\ t\mapsto 0\right]\right)\\\rightarrow &\left(\left\langle {\mathtt {halt}},\ 3\right\rangle ,\ \left[n\mapsto 2,\ x1\mapsto 2,\ x2\mapsto 3,\ t\mapsto 0\right]\right)\end{aligned}}}$

Where ${\displaystyle \left\langle {\mathtt {halt}},\ v\right\rangle }$ marks a final state of the program, with the return value ${\displaystyle v}$.

References

1. Carsten K. Gomard and Neil D. Jones. Compiler generation by partial evaluation. In G. X. Ritter, editor, Information Processing '89. Proceedings of the IFIP 11th World Computer Congress, pages 1139–1144. IFIP, North-Holland, 1989.
2. Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial Evaluation and Automatic Program Generation. With chapters by L.O. Andersen and T. Mogensen. Prentice Hall International, June 1993. xii + 415 pages. ISBN   0-13-020249-5. Freely available at http://www.itu.dk/~sestoft/pebook/pebook.html
3. John Hatcliff. An Introduction to Online and Offline Partial Evaluation using a Simple Flowchart Language. In Partial Evaluation - Practice and Theory, DIKU 1998 International Summer School, John Hatcliff, Torben Æ. Mogensen, and Peter Thiemann (Eds.). 1998. Springer-Verlag, London, UK, 20-82.