Estados y Arreglos

Expresiones, Sentencias y Estado

Expresiones son fragmentos de código que producen un valor. Por ejemplo, 2 + 2 es una expresión que produce el valor 4.

Sentencias son fragmentos de código que realizan una acción. Por ejemplo, printf("Hola") o x = 2 + 2.

Estado el conjunto de variables y sus valores en un momento dado.

Un programa sencillo, que utilice estos conceptos, podría ser:

\[\begin{array}{c} \textnormal{Var} \; x, y : Int; \\ [\![ \sigma_0 : (x \mapsto 1, y \mapsto 2) ]\!] \\ x := 5 + 5; \\ [\![ \sigma_1 : (x \mapsto 10, y \mapsto 2) ]\!] \end{array} \]

Donde \(\sigma_0\) es el estado inicial, \(\sigma_1\) es el estado final, donde hay una sentencia \(x := y + x\) que modifica el valor de la variable \(x\) en el estado \(\sigma_0\) y produce el estado \(\sigma_1\). Las expresiones dependen del estado en el que se evalúan.

Declaración de Variables

En el formalismo, declaramos variables y constantes con la palabra reservada \(Var\) y \(Const\), respectivamente.

\[\begin{array}{c} \textnormal{Var} \; x, y : Int; \\ \textnormal{Const} \; z : Int; \\ \end{array} \]

También podemos hacerlo en C de la siguiente forma:


#define N 5
 
int x, y;

Usamos #define para declarar una constante y int para declarar variables de tipo entero.
Si bien existe la palabra reservada const, usamos #define para definir la constante a nivel de preprocesador (antes de la compilación, sin asignar memoria).

Las variables pueden tener un valor inicial:

\[\begin{array}{c} \textnormal{Var} \; x, y : Int; \\ [\![ \sigma_n : (x \mapsto 1, y \mapsto 2) ]\!] \end{array} \]


int x = 1, y = 2;

Evaluación de Sentencias

Existen distintos elementos para trabajar con sentencias que modifican el estado de un programa.

\(;\;\), llamado secuenciación permite concatenar sentencias.

\[\begin{array}{c} S_1 ; \; S_2 \\ \; \\ \textnormal{(o también,)} \\ \; \\ S_1; \\ S_2 \end{array} \]

Un programa es en realidad una sola sentencia, cuando hablamos de varias sentencias estas se forman una sola a través de la secuenciación.

En C, sería:


x = 1;
y = 2;

\(:=\), llamado asignación nos permite cambiar el valor de una variable y por ende, cambiar el estado del programa.

\[x:=10 \]

Y en C sería:


x = 10;

Para el formalismo también podemos hacer uso de la asignación múltiple:

\[\begin{array}{c} \textnormal{Var} \; x, y : Int; \\ [\![ \sigma_0 : (x \mapsto 1, y \mapsto 2) ]\!] \\ x, y := y, x; \\ [\![ \sigma_1 : (x \mapsto 2, y \mapsto 1) ]\!] \end{array} \]

Es importante mencionar que algunos lenguajes de programación cumplen con la propiedad, pero otros no, necesitando una variable temporal:


# Python si tiene asignación múltiple
 
x, y = 1, 2
x, y = y, x
 
print(x, y) 
# 2, 1


// C no tiene asignación múltiple
 
int x = 1, y = 2;
int temp = x;
x = y;
y = temp;
 
printf("%d %d", x, y);
// 2, 1

\(\mathbf{if, fi}\), llamado condicional nos permite ejecutar una sentencia o instrucción si se cumple una expresión booleana. Dicha expresión también se conoce como guarda:

\[\begin{aligned} &\textnormal{Var} \; x : Int; \\ &[\![ \sigma_0 : (x \mapsto 1) ]\!] \\ &\mathbf{if} \; x > 0 \rightarrow \\ &\quad x := 0; \\ &□ \; x \leq 0 \rightarrow \\ &\quad x := 1; \\ &\mathbf{fi}; \\ &[\![ \sigma_1 : (x \mapsto 0) ]\!] \end{aligned} \]

En C, sería:


int x = 1;
 
if (x > 0) {
    x = 0;
} else {
    x = 1;
}

\(\mathbf{skip}\) es una sentencia que no hace nada, pero útil si necesitamos no alterar el estado del programa.

\[\begin{aligned} &\textnormal{Var} \; x : Int; \\ &[\![ \sigma_0 : (x \mapsto 1) ]\!] \\ &\mathbf{if} \; x \geq 0 \rightarrow \\ &\quad \mathbf{skip}; \\ &□ \; x < 0 \rightarrow \\ &\quad x := x * (-1); \\ &\mathbf{fi}; \\ &[\![ \sigma_1 : (x \mapsto 1) ]\!] \end{aligned} \]

En el caso de C, no es aplicable, pero basta con dejar el espacio en blanco.


int x = 1;
 
if (x < 0) {
  x = x * (-1);
}

\(\mathbf{do, od}\), llamado repetición sirve para la ejecución repetida de una acción (ciclo).

\[\begin{aligned} &\textnormal{Var} \; i, \; x : Int; \\ &[\![ \sigma_0 : (i \mapsto 0, x \mapsto 3) ]\!] \\ &i := 0; \\ &\mathbf{do} \; i < 3 \rightarrow \\ &\quad[\![ \sigma^1_1 : (i \mapsto 0, x \mapsto 3), \; \sigma^2_1 : (i \mapsto 1, x \mapsto 2), \; \sigma^3_1 : (i \mapsto 2, x \mapsto 1) ]\!] \\ &\quad x := x - 1; \\ &\quad i := i + 1; \\ &\quad[\![ \sigma^1_2 : (i \mapsto 1, x \mapsto 2), \; \sigma^2_2 : (i \mapsto 2, x \mapsto 1), \; \sigma^3_2 : (i \mapsto 3, x \mapsto 0) ]\!] \\ &\mathbf{od}; \\ &[\![ \sigma_3 : (i \mapsto 3, x \mapsto 0) ]\!] \end{aligned} \]

Estos estan compuestos de la siguiente forma:

Inicialización: Se inicializan las variables de control del ciclo (en este caso \(i := 0\))
Guarda: Se evalúa una expresión booleana que determina si se ejecuta el ciclo o no (en este caso \(i < 3\))
Cuerpo de ciclo: Es el bloque de código que se ejecuta si la guarda es verdadera (en este caso \(x := x - 1; \; i := i + 1\))
Invariante: Es una expresión que se mantiene verdadera en cada iteración del ciclo (útil para poder determinar la inicialización y el cuerpo)

En C, sería:


int i = 0, x = 3;
 
while (i < 3) {
    x = x - 1;
    i = i + 1;
}

Arreglos

Un arreglo o vector es una función definida sobre un segmento de los naturales. Declarado de la siguiente forma:

\[a : array[p, q)of[A] \]

Donde \(p \leq q\) y \(A\) es el tipo de dato que tienen los elementos.

La cantidad de elementos de un arreglo es \(q - p\). Si \(q = p\), el arreglo es vacío.
Un elemento de un arreglo se referencia como \(a.n\) donde \(n \in [p, q)\).
Es posible usar variables cuantificadas en relación a arreglos. Por ejemplo si \(a : array[p, q)ofInt\),
entonces \(\bigl \langle \; \textnormal{Max} \; i : p \leq i < q : a.i \; \bigr \rangle\) indica el máximo elemento del arreglo.

En C, la declaración de un arreglo sería:


int a[10];
 
a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
printf("Indexando el arreglo: %d", a[0]);
 
// Indexando el arreglo: 1

Donde a es el nombre del arreglo y 10 es la cantidad de elementos, para acceder a un elemento se usa el índice entre [].

A diferencia de las listas, los arreglos tienen un tamaño fijo. El acceso al elemento de un arreglo es instantáneo, mientras que en una lista es lineal (depende de la cantidad de elementos).
Es más complejo insertar o eliminar elementos en un arreglo ya que deben moverse los elementos restantes, en una lista es más sencillo.