Flow Chart Language
   HOME

TheInfoList



OR:

Flow chart language (FCL) is a simple imperative programming language designed for the purposes of explaining fundamental concepts of
program analysis In computer science, program analysis is the process of automatically analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness. Program analysis focuses on two major areas: program op ...
and specialization, in particular,
partial evaluation In computing, partial evaluation is a technique for several different types of program optimization by specialization. The most straightforward application is to produce new programs that run faster than the originals while being guaranteed to ...
. The language was first presented in 1989 by Carsten K. Gomard and Neil D. Jones. It later resurfaced in their book with Peter Sestoft in 1993, and in John Hatcliff's lecture notesJohn Hatcliff. An Introduction to Online and Offline Partial Evaluation using a Simple Flowchart Language. In Partial Evaluation - Practice and Theory,
DIKU The UCPH Department of Computer Science ( da, Datalogisk Institut, DIKU) is a department in the Faculty of Science at the University of Copenhagen (UCPH). It is the longest established department of Computer Science in Denmark and was founded in 1 ...
1998 International Summer School, John Hatcliff, Torben Æ. Mogensen, and Peter Thiemann (Eds.). 1998. Springer-Verlag, London, UK, 20-82.
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 In computer science, Backus–Naur form () or Backus normal form (BNF) is a metasyntax notation for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats ...
. An FCL program is a list of formal parameter declarations, an entry label, and a sequence of ''basic blocks'':

::= "(" * ")" "(" ")" + Initially, the language only allows non-negative integer variables. A basic block consists of a label, a list of assignments, and a jump. ::= ":" * 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: := ":=" := , , "(" * ")" 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 In medicine, a side effect is an effect, whether therapeutic or adverse, that is secondary to the one intended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequence ...
, which includes exceptions, e.g. division by 0: ::= "0" , "1" , "2" , ... ::= "+" , "-" , "*" , "=" , "<" , ">" , ... 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 nth
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
, 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 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 has been jumped to. We can check the correctness of the method for n=4 by presenting the execution trace of the program: \begin & \left(\mathtt,\ \left n \mapsto 4,\ x1 \mapsto 0,\ x2 \mapsto 0,\ t \mapsto 0\rightright) \\ \rightarrow & \left(\mathtt,\ \left n \mapsto 4,\ x1 \mapsto 1,\ x2 \mapsto 1,\ t \mapsto 0\rightright) \\ \rightarrow & \left(\mathtt,\ \left n \mapsto 3,\ x1 \mapsto 1,\ x2 \mapsto 2,\ t \mapsto 0\rightright) \\ \rightarrow & \left(\left\langle\mathtt,\ 3\right\rangle,\ \left n \mapsto 2,\ x1 \mapsto 2,\ x2 \mapsto 3,\ t \mapsto 0\rightright) \end Where \left\langle\mathtt,\ v\right\rangle marks a final state of the program, with the return value v.


Variants


Reversible flow chart language

Reversible flow chart language (RL) is a simple reversible imperative programming language designed for reversible computing, where each computational process is reversible. RL combines step, test, and assertion in a way that ensures the reversibility of the programs. RL emphasizes the construction of reversible programs that permit deterministic backward computation, ensuring that no information is lost during processing. This characteristic makes it distinct from traditional flow chart languages, which usually involve irreversible operations. The syntax and example programs for RL would closely resemble traditional flow chart languages but with added constraints to ensure reversibility. These include reversible loops, reversible conditional, and invertibility of atomic computation steps. Due to the reversibility constraint, RL has less computational power than conventional
Turing machines A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
but is equivalent to reversible Turing machines (RTMs), laying the foundation for reversible programming. The reversible variant of the structured program theorem, for instance, can be effectively analyzed using RL, showcasing its significance in the theoretical bases of
reversible computing Reversible computing is any model of computation where the computational process, to some extent, is time-reversible. In a model of computation that uses deterministic transitions from one state of the abstract machine to another, a necessary c ...
. There is also a structured variant of RL (SRL: structured reversible flow chart language) that combines sequence, selection, and iteration in a way that ensures the reversibility of the programs.


References

{{Reflist Programming languages Programming paradigms