Lenguaje de diagramas de flujo

El lenguaje de diagramas de flujo (FCL) es un lenguaje de programación imperativo simple diseñado para explicar conceptos fundamentales de análisis y especialización de programas, en particular, la evaluación parcial . El lenguaje fue presentado por primera vez en 1989 por Carsten K. Gomard y Neil D. Jones. ^{[ 1 ]} Posteriormente reapareció en su libro con Peter Sestoft ^{[ 2 ]} en 1993, y en las notas de clase de John Hatcliff ^{[ 3 ]} en 1998. A continuación se describe FCL tal como apareció en las notas de clase de John Hatcliff.

FCL es un lenguaje de programación imperativo similar a la forma en que una computadora Von Neumann ejecuta un programa. Un programa se ejecuta secuencialmente siguiendo una secuencia de comandos, manteniendo un estado implícito, es decir, la memoria global. FCL no tiene el concepto de procedimientos, pero sí proporciona saltos condicionales e incondicionales. FCL hace honor a su nombre, ya que el grafo de llamadas abstracto de un programa FCL es un diagrama de flujo sencillo.

Un programa FCL toma como entrada una serie finita de valores con nombre como parámetros y produce un valor como resultado.

Especificamos la sintaxis de FCL utilizando la forma Backus-Naur .

Un programa FCL es una lista de declaraciones de parámetros formales, una etiqueta de entrada y una secuencia de bloques básicos :

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

Inicialmente, el lenguaje solo permite variables enteras no negativas.

Un bloque básico consta de una etiqueta, una lista de asignaciones y un salto.

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

Una asignación asigna una variable a una expresión. Una expresión puede ser una constante, una variable o la aplicación de un operador n-ario integrado:

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

Tenga en cuenta que los nombres de las variables que aparecen a lo largo del programa no necesitan declararse al principio del mismo. Las variables declaradas al principio del programa designan los argumentos del mismo.

Como los valores solo pueden ser enteros no negativos, también lo pueden ser las constantes. La lista de operaciones en general es irrelevante, siempre que no tengan efectos secundarios , lo que incluye excepciones, por ejemplo, la división por cero:

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

Donde = , < , ... tienen la misma semántica que en C. La semántica de - es tal que si xy<0, entonces xy=0.

Escribimos un programa que calcula el n ^-ésimo número de Fibonacci , para n>2:

(norte) (inicialización) inicialización: x1 = 1 x2 = 1 Fibonacci: x1 = x1 + x2 t = x1 x1 = x2 x2 = t n = -(n 1) si >(n 2) entonces fib sino salir salir: devolver x2 

Donde el invariante de bucle de fib es que x1 es el (i+2-1) ^-ésimo y x2 es el (i+2) ^-ésimo número de Fibonacci, donde i es el número de veces que se ha saltado a fib .

Podemos comprobar la corrección del método para n=4 presentando el rastro de ejecución del programa:

${\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 {detener}},\ 3\rango\derecho,\ \left[n\mapsto 2,\ x1\mapsto 2,\ x2\mapsto 3,\ t\mapsto 0\right]\right)\end{aligned}}}$

Dónde${\displaystyle \left\langle {\mathtt {detener}},\ v\right\rangle }$marca un estado final del programa, con el valor de retorno${\displaystyle v}$.