Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2000

 

Práctica 4

Programación Imperativa

 

Fecha sugerida de finalización: 15 /06 /2000.

Sintaxis del Lenguaje

Sentencias del lenguaje:

<sentencia> ::=     skip

             |      <VarID> := <expresión>

             |      if <expresión_booleana> then <sec_sentencia>

                           else <sec_sentencia> fi

             |      while <expresión_booleana> do <sec_sentencia> od

             |      ret_value := <expresión>

 

<sec_sentencia> ::= <sentencia>;

                 |  <sec_sentencia>; <sentencia>;

 

<expresión> ::= <expresión_booleana> | <expresión_integer> | <expresión_char>

 

<expresión_booleana> ::=   True

                      |    False

                      |    <variable_booleana>

                      |    ( <expresión_booleana> )

                      |    not <expresión_booleana>

                      |    <expresión_booleana> [and | or ] <expresión booleana>

 

<expresión_integer> ::=    <constante_integer>

             |  <variable_integer>

             |  ( <expresión_integer> )

             |  <expresión_integer> [ + | - | * | div | mod] <expresión_integer>

 

<expresión_char> ::=       A | a | B | b | C | c | ... | Z | z

                           | _ | . | , | ; | ( | )           ( _ es el caracter blanco)

                           | 0 | 1 | ... | 9

Declaración de variables y constantes:

<declaración> ::=   const

                         <sec_const_declaración>

                    var

                         <sec_var_declaración>

 

<sec_var_declaración> ::=  <var_declaración>;

                       |   <sec_var_declaración>; <var_declaración>;

 

<sec_const_declaración> ::= <const_declaración>;

                         |   <sec_const_declaración>; <const_declaración>;

 

<var_declaración> ::=      <VarId> : <Tipo> [:= <expresión>]

<const_declaración> ::=    <ConstId> : <Tipo> := <expresión>

Declaración de funciones:

<función> ::= function <NombreFunción> (<ListaParam>) : <TipoDevolución>

                    <declaración>

                    <sec_sentencia>

              endfunction

 

Nota: <sec_sentencia> debe contener al menos una sentencia de la forma

 

ret_value := <expresión>

 

siendo <expresión>  del mismo tipo que  <TipoDevolución>. No es necesario declarar a ret_value ya que ésta es automáticamente declarada con el tipo de retorno declarado en la función. La función retornará como resultado el valor de la última asignación realizada sobre ret_value.

 

<ListaParam> ::=    <IdParam> : <Tipo>

              |     <ListaParam>, <IdParam> : <Tipo>

 

<Tipo> ::=  integer | bool | char | lista de <Tipo> | arreglo de <Tipo>

 

<TipoDevolución> ::=       integer | bool | char | lista de <Tipo>

(Las listas y los arreglos son definidos más adelante.)

 

La evaluación de una función de tipo <TipoDevolución> es una <expresión_tipo>.

 

Nota: Tener en cuenta que las funciones no pueden devolver el tipo arreglo.

 

Ejemplo:

       function SumaLoca(x: integer, y: integer) : integer

             const

                    A : integer := 4;

             var

                    t : bool := False;

                    b : integer;

 

             if t then

                    b := A + A + A;

                    while (b > 2) do

                           b := b - 1;

                    od;

             else

                    skip;

             fi;

             ret_value := (x+y);

       endfunction 

 

       Además, Suma (3, 7) es una <expresión_integer>.

Lenguaje de Estados:

Para describir un instante de la ejecución de un programa, utilizaremos predicados. Estos definen un conjunto de posibles valores que pueden tomar las variables de dicho programa, es decir, un conjunto de posibles estados. Estos predicados los escribiremos entre llaves.

Se pueden usar expresiones del lenguaje de la lógica de primer orden, extendido con cualquier función escrita en el lenguaje funcional. Para evitar posibles confusiones con las funciones del lenguaje imperativo se agrega una ´f´ minúscula y un guión bajo delante de las funciones del lenguaje funcional.

Sólo pueden aparecer libres dentro de un estado las variables que  fueron declaradas previamente dentro de una función o procedimiento (esto incluye a los parámetros).

En una función los parámetros son pasados por copia, por lo tanto, al finalizar la función no se reflejan los cambios realizados en los parámetros, dado que se trabajó con copias. Por lo tanto, la postcondición de una función describe los posibles estados que poseen las variables inmediatamente antes de finalizar la función. Esto significa que si en la postcondición aparecen variables que, o bien son locales a la función o bien son parámetros de la misma, sus valores sólo tienen sentido en el contexto de la función (en el caso de variables locales a la función, éstas ni siquiera serán visibles fuera de ella).

 

Además, se puede utilizar:

{x = X₀}              [X₀ es el valor que toma la variable x en cierto momento. Escribiremos las variables con
                                minúsculas y la representación de sus valores con mayúsculas.]

Ejemplos:

                { ("y) ( y < x Þ Primo (x) ) Ù Par (w) Ù w mod 5 = W₀ }

                Donde Primo y Par son predicados.

 

                { ( N₀>M₀  Ù ret_value = f_mcd(N₀,M₀) Ú (N₀<=M₀ Ù ret_value= M₀) }

                Donde mcd es una función en lenguaje funcional

Estructura formal de un programa imperativo

 

Toda función (o procedimiento como veremos más adelante) implementada en lenguaje imperativo tiene una precondición (lo llamaremos P) que indica que condiciones deben cumplirse para que la función se ejecute correctamente, esto es que valores tienen los parámetros y si éstos deben cumplir con algún requisito en particular. También debemos indicar cual es la postcondición (lo llamaremos Q) de la función, esto es, que resultado devolverá en caso de que se cumplan los requisitos  especificados en P. Especificar tanto la precondición como la postcondición permiten conocer de forma no ambigua que es lo que hace la función facilitando su correcto uso para los usuarios de la misma o su correcta implementación para los responsables de realizarla.

En el caso de que la función posea un ciclo es muy importante especificar formalmente cual es la precondición del ciclo (lo llamaremos Pc), su invariante (lo llamaremos I), la guarda del ciclo (la llamaremos B), la función variante (la llamaremos fv) y la postcondición del ciclo (lo llamaremos Qc). Esta especificación formal nos permitirá deducir fácilmente como implementar el código del ciclo y además verificar que el ciclo funcione correctamente y nos acerque a la postcondición de la función.  En todo momento debemos explicitar el valor de las variables de  nuestro programa. Esto nos permitirá verificar que nuestro programa es correcto, es decir, que realiza lo que la especificación determina.

 

Veamos un ejemplo de una función enriquecida con el lenguaje de estados:

 

function sumaN (n : Integer ) : Integer

 

P º { n = N Ù N>0 } 

 

var

       acum: Integer := 0;

       i: Integer :0 ;

 

Pc º { acum = 0 Ù i= 0  Ù n= N Ù N>0 } 

notar que en el Pc aparecen nuevas variables que necesitamos para la implementación del ciclo.

 

I º { acum = f_sumaN(i) Ù  0<=i<=n Ù n= N Ù N>0}

B º { i<n }

fv = n – i debe ser estrictamente decreciente y acotada inferiormente

 

se debe cumplir { I }

while i<n do

       se debe cumplir { I Ù B }

i := i + 1,

       acum := acum + i;

se debe cumplir{ I }

od;

se debe cumplir { I Ù ØB } º { acum = fsumaN(i) Ù  i=n } y como se ve esto debe implicar Qc

 

Qc º { acum = f_suma(N) Ù n= N Ù N>0} 

 

ret_value = acum;

 

Q º { ret_value = f_sumaN(N) } 

 

 

Endfunction

 

Definimos en  gofer:

 

sumaN :: Int -> Int

sumaN 0 = 0

sumaN (n+1) = (n+1) + sumaN n

 

 

 

Se debe evitar el uso de ciclos anidados, porque complican innecesariamente la confección y verificación de los invariantes trayendo como posible consecuencia errores no detectados en la implementación. En el caso de que se deba realizar un programa que posea un ciclo dentro  de otro, lo más aconsejable es implementar una función auxiliar que provea la funcionalidad del ciclo interior.

Ejercicio 1

 

1.1 Dada la función Producto(n:integer,m:integer):integer que devuelve el producto entre m y n, indicar :

 

i. Cual es la precondición adecuada para la función

 

a)       P º {n=N₀ Ù m=M₀}

b)       P º TRUE

 

ii. Cual es la postcondición adecuada para la función

 

a)       Q º {ret_value = m*n}

b)       Q º {ret_value = M₀*N₀}

c)       Q º TRUE

 

iii. Suponiendo que la idea de implementación de la función es la siguiente:

 

Realizar un ciclo que sume el parámetro m tantas veces como lo indica el valor absoluto del parámetro n. Indicar cuales son los  Pc,  Qc,  I,  B y  Fv que mejor se adecuan a la idea de este ciclo. Suponer una precondición donde vale que: n = n0 Ù m = m0

 

a)   Pc º P

   B º {i £ f_abs m}

   I º {ret_value = n * i}

   Fv = m-i

   Qc º Q

 

b)   Pc º {ret_value = 0 Ù i =0 Ù n = n0 Ù m = m0}

   B º {i < f_abs n }

   I º {ret_value = m*i Ù 0 £ i £ (f_abs n) Ù n = n0 Ù m = m0}

   Fv = (f_abs n) - i

   Qc º {ret_value = (f_abs n) * m Ù n = n0 Ù m = m0}

 

c)   Pc º {ret_value = 0 Ù i =0 Ù n = n0 Ù m = m0}

   B º {i £ n}

   I