Programación imperativa: mutación, sentencias y closures

En la programación imperativa el estado del programa se mantiene en forma de datos en la memoria del computador. Estos datos son modificables mediante sentencias de asignación.

val unoDosTres = Array("uno","dos","tres")

unoDosTres(2) = unoDosTres(0)

def llenaArray(array: Array[String]) = {
   var i = 1
   while (i < array.length) {
      array(i) = array(0)
      i += 1
   }
}

var x = 10
var y = x
x = 20
y 

var x = Array(1,2,3,4)
var y = x
x(0) = 10
x
y

La otra característica fundamental de la programación imperativa tiene también su origen en la arquitectura de Von Newman. Se trata de la ejecución de pasos elementales en los que el control va modificando el contador de programa que indica la siguiente instrucción a ejecutar.

Las sentencias de control de los lenguajes imperativos que utilizan la programación estructurada se pueden agrupar en: secuencia, selección e iteración:

• Las sentencias de secuencia definen instrucciones que son ejecutados una detrás de otra de forma síncrona. Una instrucción no comienza hasta que la anterior ha terminado.
• Las sentencias de selección definen una o más condiciones que determinan las instrucciones que se deberán ejecutar.
• Las sentencias de iteración definen instrucciones que se ejecutan de forma repetitiva hasta que se cumple una determinada condición.

Además, en la programación imperativa también debemos entender una llamada a un procedimiento o una función como una sentencia de control. En ella se modifica el contador del programa y se pasan a ejecutar las sentencias definidas en el procedimiento.

El modelo de evaluación de la programación imperativa ya no es el modelo de sustitución, sino un modelo basado en la ejecución de sentencias y la modificación de los datos almacenados.

(set! <simbolo> <expresion>)
(set-car! <pareja> <expresion>)
(set-cdr! <pareja> <expresion>)

Un ejemplo de mutación y efecto lateral con una pareja:

(define a (cons 1 2))
(define b a)
(set-car a 10)
a
b

La introducción de la mutación nos obliga a diferenciar entre igualdad de valor e igualdad de contenido:

• La igualdad de referencia se comprueba con la función eq?: (eq? x y) devuelve #t cuando x e y apuntan al mismo dato
• La igualdad de contenido se comprueba con la función equal?: (equal? x y) devuelve #t cuando x e y contienen el mismo valor

Si dos variables son eq? también son equal?.

(define a (cons 1 2))
(define b (cons 1 2))
(define c a)
(equal? a b)
(equal? a c)
(eq? a b)
(eq? a c)

Una ventaja de los operadores de mutación es la actualización eficiente de estructuras de datos. Por ejemplo, una inserción en una lista ordenada en Scheme:

(define (make-olist)
   (list '*list*))

(define (insert! n olist)
   (cond 
      ((null? (cdr olist)) (set-cdr! olist (cons n '())))
      ((< n (cadr olist)) (set-cdr! olist (cons n (cdr olist))))
      ((= n (cadr olist)) #f) ; el valor devuelto no importa
      (else (insert! n (cdr olist)))))

Podemos probar la función anterior:

(define a (make-olist))
(insert! 15 a)
a
(insert! 1 a)
a

Se necesita añadir una cabecera a la lista, porque si no lo hiciéramos y quiséramos insertar un elemento en la primera posición de la lista, perdieríamos su referencia. Añadiendo una cabecera todos los elementos se insertarán a continuación de ella, por lo que esta cabecera funcionará como un elemento inmutable al que apuntar para referenciar la lista.

Otro ejemplo: una tabla hash definida con una lista de asociación.

(define (make-table)
   (list '*table*))

(define (get key table)
   (let ((record (assq key (cdr table))))
      (if (not record)
         #f
         (cdr record))))

(define (put key value table)
   (let ((record (assq key (cdr table))))
      (if (not record) 
         (set-cdr! table
            (cons (cons key value) (cdr table)))
         (set-cdr! record value))))

Por defecto, los objetos de cualquier clase en Scala son mutables. Lo veremos en programación orientada a objetos.

Scala tiene una gran cantidad de colecciones mutables: http://www.scala-lang.org/api/current/scala/collection/mutable/package.html

Vamos a comentar la clase ListBuffer, que implementa listas mutables a las que se pueden añadir elementos por el principio y por el final en tiempo constante. La lista completa de métodos se puede consultar en el API de Scala.

import scala.collection.mutable.ListBuffer
val buf = new ListBuffer[Int]
buf += 1 
buf += 2
3 +: buf

Son tipos de referencia. Las siguientes instrucciones asigna la referencia de buf a buf2. Cuando modificamos buf2 también estamos modificando buf:

val buf = new ListBuffer[Int]
val buf2 = buf
buf2 += 4

La función ++= añade a una lista el contenido de otra colección:

val buf = new ListBuffer[Int]
buf += 1
val buf2 = new ListBuffer[Int]
buf2 ++= List(2,3,4)
buf ++= buf2

La función -= elimina un elemento de la lista (sólo uno, el primero que encuentra):

val buf = new ListBuffer[String]
buf ++= List("Paris","Madrid","Londres")
buf -= "Paris"

La función indexOf devuelve la posición de un dato.

val buf = new ListBuffer[String]
buf ++= List("Paris","Madrid","Londres")
buf.indexOf("Madrid")

La función update modifica el dato situado en una determinada posición de la lista.

val buf = new ListBuffer[String]
buf ++= List("Paris","Madrid","Londres")
buf.update(1,"Barcelona")

En Scheme es posible definir en el cuerpo de una función o de un let más de una expresión. En este caso todas las expresiones se ejecutan secuencialmente y se devuelve el resultado de la última expresión. En Scala funciona igual.

(define x 3)
(define y 5)
(define (cambia-vars a b)
   (set! x a)
   (set! y (+ a b x))
   (+ x y))

Interesante en el ejemplo: ámbito de variables x e y y pasos de ejecución.

El mismo ejemplo en Scala:

var x=3
var y=5
def cambiaVars(a: Int, b: Int) = {
   x=a
   y=a+b+x
   x+y }

Además, en Scheme tenemos la forma especial begin que permite ejecutar expresiones como pasos de ejecución en aquellos lugar. También es posible definir un cuerpo de una función o de un let con más de una expresión que también se ejecutan secuencialmente. Se devuelve el valor de la última expresión. Un ejemplo:

val filename = if (!args.isEmpty) args(0) else "default.txt"
println(filename)

def pruebaMatch(str: String) = {
   str match { 
      case "salt" => println("pepper") 
      case "chips" => println("salsa") 
      case "eggs" => println("bacon") 
      case _ => println("huh?")
   }
}

def pruebaMatch2(str: String): String = {
   str match { 
      case "salt" => "pepper"
      case "chips" => "salsa"
      case "eggs" => "bacon"
      case _ => "huh?"
   }
}

Aunque Scheme también tiene bucles, vamos a centrarnos en Scala.

def gcdLoop(x: Long, y: Long): Long = {
   var a = x
   var b = y
   while (a != 0) {
      val temp = a
      a = b % a
      b = temp
   }
   b
}

def leerEntrada() = {
   var line = ""
   do {
      line = readLine()
      println("Read: " + line)
   } while (line != "")
}

def printFiles() = {
   val filesHere: Array[java.io.File] = (new java.io.File(".")).listFiles
   for (file <- filesHere)
      println(file)
}

def numsCuadrados(n: Int): (Array[Int],Array[Int]) = {
   val nums = new Array[Int](n)
   val cuadrados = new Array[Int](n)
   for (i <- 0 until n) {
      nums(i) = i
      cuadrados(i) = i*i
   }
   (nums,cuadrados)
}

def divisorPattern(n: Int) = {
   for (i <- 1 to n) {
      for (j <- 1 to n) {
         if ((i % j == 0) || (j % i) == 0)
            print("* ")
         else
            print("  ")
      }
      println(i);
   }
}

Las variables se guardan en un entorno. Por defecto existe un entorno global en el que se crean las variables cuando ejecutamos setencias en el intérprete. Veremos que dentro de este entorno global se van a crear entornos locales, por lo que es importante saber en cada momento en qué entorno nos encontramos. Las sentencias del programa se ejecutan en un entorno dado (el global o algún entorno local). Dependendiendo de en qué entorno se ejecute una sentencia, las variables que aparecen en ellas tendrán un valor u otro.

Se crea una variable en un entorno cuando se ejecuta una sentencia define en Scheme o se declara una variable con var o val en Scala. Las variables cambian de valor con sentencias de asignación y se evalúan a su último valor asignado.

Para representar gráficamente los entornos Dibujaremos un entorno como un rectángulo que contiene variables. Las variables las asociaremos con su valor con ":". Cuando el tipo que se asocia a una variable es un tipo de referencia mutable lo indicaremos con una flecha.

Por ejemplo, supongamos las siguientes sentencias.

En Scheme:

(define x 1)
(define y (+ x 2))
(set! x 5)
(set! y (+ x y))
(define a (cons 1 2))
(define b a)

En Scala:

var x=1
var y=x+2
x=5
y=x+y
var a = new ListBuffer[Int]
a ++= List(1,2)
var b = a

El entorno resultante de estas expresiones se muestra en la siguiente figura. Vemos que las variables x e y han modificado su valor y que las variables a y b referencian ambas el mismo objeto mutable. Una modificación en ese dato afectaría a ambas variables.

Vamos a avanzar más en el modelo de entornos, añadiendo los entornos locales. ¿Cuándo se crea un entorno local? En Scheme y Scala cuando se invoca una función. Todas las sentencias de la función se ejecutan un entorno local creado en el momento de la invocación.

Veamos el siguiente ejemplo.

En Scheme:

(define x 0)
(define z 100)
(define (crea-vars)
   (define x 10)
   (define y (+ x 20))
   (+ x y z))

(crea-vars 10)
x
y

En Scala:

var x=0
var z=100
def creaVars() = {
   var x=10
   var y=x+20
   x+y+z
}

creaVars()
x
y

Estamos definiendo una función creaVars que crea las variables locales x e y, les asigna valor y devuelve su suma más el valor de una variable z definida en el entorno global. ¿Es accesible el valor de z desde el entorno local? Podemos comprobar que sí. ¿Se modifican el valor de x del entorno global al modificarlo en el entorno local? Comprobamos que no. Y que tampoco toma valor en el entorno global la variable y creada en el local.

La representación gráfica de los entornos es la siguiente. Vemos a la derecha de cada entorno las sentencias ejecutadas en él. En el entorno global se crean dos variables y se define la función creaVars. Después se invoca la función. Se crea entonces un entorno local dentro del global en el que se ejecutan las sentecias de la función creaVars: se crea la variable local x, la variable y y se devuelve la expresión x+y+z. Hay que hacer notar que las variables definidas en el entorno que contiene al entorno local (en este caso el entorno global) son accesibles desde él. En este caso, la variable z se puede utilizar sin problemas dentro del entorno local. Se obtiene su valor en el entorno global.

Vamos a explorar esto último un poco más. Las variables del entorno "padre" (el entorno contenedor) pueden ser accedidas desde el entorno local. Pero, ¿pueden ser modificadas?

Lo podemos comprobar con el siguiente ejemplo. Creamos la variable x en el entorno global y una función en donde modificamos su valor. Es importante que en la función no definimos x (no usamos var ni val ni define en Scheme), por lo que estamos accediendo a la variable definida en el entorno global.

var x = 10
def cambiaX(y: Int) = {
   x = x+y
   x 
}

cambiaX(20)
x

En Scheme:

(define x 10)
(define (cambia-x y) 
   (set! x (+ x y))
   x)

(cambia-x 20)
x

Si ejecutamos cualquiera de estos ejemplos podemos comprobar que se modifica el valor de x en el entorno global.

La representación gráfica es la siguiente:

En el ejemplo definimos también el parámetro y en la función cambiaX. Cuando invocamos la función le damos el valor 20. Los parámetros son similares a variables creadas en la función. Su nombre se define en el entorno local y se usa su valor en las sentencias de la función. Una diferencia entre Scala y Scheme es que los parámetros en Scheme pueden ser modificados, pero en Scala no.

Un resumen de lo que hemos aprendido hasta ahora:

• La invocación a una función crea un entorno local contenido en el entorno global
• Las variables creadas en ese entorno local no son accesibles desde el entorno global
• Las variables del entorno global son accesibles desde el entorno local

Vamos a dar un paso más. Aunque las variables creadas en un entorno local no son accesibles desde el entorno global, no pasa lo mismo con los objetos. Podemos crear un objeto de referencia dentro del entorno local y devolverlo como resultado de la función. Por ejemplo, con el siguiente código:

def creaListBuffer() = {
   var a = new ListBuffer[String]
   a += "Nueva York"
   a
}

var b = creaListBuffer()

O un código similar en Scheme:

(define (crea-pareja)
   (define a (cons 1 2))
   a)

(define b (crea-pareja))

Tanto en el caso de Scala como en el de Scheme, el objeto creado en el entorno local se devuelve como resultado de la invocación de la función. No se devuelve una copia, sino el propio objeto creado en el entorno local.

Y ahora llegamos al último y más importante punto del modelo de entornos ¿Qué sucede si en el entorno local creamos y devolvemos una función? Vamos a verlo en el apartado siguiente. Adelantamos que estamos definiendo una closure y que la función devuelta tiene acceso a las variables definidas en el entorno local.

Veamos lo que sucede con lo que se denominan closures, funciones creadas en un ámbito local. La regla de creación de funciones (closures) en entornos locales es la siguiente:

Regla de creación de closures: Cuando se crea una función anónima en un entorno local y se devuelve como resultado, la función queda asociada al entorno local en que se ha creado. Una posterior invocación a la función anónima se ejecutará dentro de este entorno local.

Esto es, si en un entorno local creamos una función anónima y la devolvemos, cuando la invocamos posteriormente podrá acceder a las variables definidas en el entorno local. De ahí proviene el nombre de closure. Cuando se devuelve una función creada en un ámbito, la función se queda guardada en el entorno en el que se ha creado. Al devolver la función y asignarla a una variable en el entorno global podemos considerar que se devuelve todo: la propia función y su ámbito.

Podemos generalizar este comportamiento con la regla de invocación de funciones del modelo de entornos:

Regla de invocación de funciones: Cuando se invoca a una función se crea un entorno local dentro del entorno en el que la función se creó y se ejecutan todas sus sentencias en este entorno local.

Es importante notar que se trata de una regla general que sirve tanto para funciones creadas en el entorno global como para funciones creadas en entornos locales. Las funciones que se denominan closures son estas últimas.

Veamos un ejemplo de este comportamiento. Definimos en Scheme la función make-contador que crea una variable x inicializada a 0 y después una función anónima que incrementará esta x. Una vez definida la función, la invocamos y asignamos su resultado (una función anónima) a la variable f. Por último, invocamos un par de veces a f y consultamos el valor de x en el entorno global:

(define (make-contador)
   (define x 0)
   (lambda ()
      (set! x (+ x 1))
      x))

(define f (make-contador))
(f)
(f)
x

En el ejemplo podemos comprobar que cada invocación a f va incrementando el valor de la variable local x. Esta variable es el estado local de la función, que se modifica en cada invocación. La invocación a f se ejecuta dentro del entorno en el que f se creó (el mismo en el que está definido x), por lo que se tiene acceso a esta variable.

Vemos que hay dos elementos nuevos que no existían en el paradigma funcional:

• Estado local: un conjunto de valores no accesibles desde el entorno global, que persisten durante el tiempo de ejecución del programa y a los que es posible acceder desde ciertas funciones (closures en nuestro caso).
• Funciones que devuelven distintos valores: la llamada a la función f devuelve un valor distinto en cada invocación. Recordemos que esto es incompatible con el paradigma funcional, en el que una función siempre debe devolver el mismo resultado si se invoca con los mismos parámetros.

El ejemplo anterior se puede programar también en Scala de una forma similar:

def makeContador() = {
   var x = 0 
   () => {   
      x = x+1   
      x         
   }         
}

f = makeContador()
f()
f()
x

La representación de los ámbitos creados es la siguiente:

Repasemos sobre la figura el funcionamiento del modelo. Recordemos que a la derecha del entorno aparecen las sentencias que se ejecutan:

1. En primer lugar se define la función makeContador() en el entorno global.
2. Después se llama a esta función. Se crea un entorno local dentro del entorno global en el que se ejecuta la función. Lo llamamos con el mismo nombre de la función, makeContador. En él se crea la variable x con el valor 0 y se crea una función anónima sin parámetros que incremente el valor de x y lo devuelve. Esta función es la que se devuelve como resultado de la ejecución de makeContador() y se asigna a la variable f (en el entorno global). La función queda asociada al entorno local en el que se ha creado.
3. En el siguiente paso se invoca esta función. Se crea un entorno local dentro del entorno de makeContador en el que se ejecuta la función. Se incrementa el valor de x y se devuelve. La variable x a la que se accede es la variable local creada en el entorno local makeContador.
4. Se vuelve a invocar f y vuelve a suceder lo mismo que en el caso anterior.
5. Por último se intenta acceder al valor de x desde el entorno global. Se obtiene un error, porque no existe ninguna variable x definida en este entorno.

Después de haber comprobado el funcionamiento de los entornos con los distintos ejemplos que hemos presentado, podemos resumir el funcionamiento del modelo con las siguientes reglas:

1. Las variables se definen en entornos, asociando un valor a su nombre.
2. Por defecto existe un entorno global.
3. Las instrucciones se ejecutan en los entornos. Cuando se referencia una variable en un entorno se devuelve su valor definido en ese entorno. Si la variable no existe en ese entorno, se busca en su entorno padre, hasta que se llega al entorno global.
4. Una invocación a una función crea un ámbito local, dentro del ámbito en el que se creó la función.
5. El cuerpo de la función se ejecuta en el ámbito local creado por su invocación.

El concepto de estado local es muy importante. En programación orientada a objetos el estado se asocia a los objetos, pero hemos comprobado que es posible otro enfoque. La mezcla de programación funcional y programación imperativa permite construir closures (funciones) que almacenan estado local.

En el ejemplo anterior, la variable x es un estado local a la función que devuelve makeContador. Hay que hacer notar que se crean tantos ámbitos locales como invocaciones a makeContador. Por ejemplo, podemos crear dos funciones, cada una con su propio estado local:

var c1 = makeContador()
var c2 = makeContador()
c1() -> 1
c1() -> 2
c1() -> 3
c2() -> 1

Podemos modificar ligeramente la función anterior, añadiéndole un parámetro con el valor inicial del contador:

def makeContador(i: Int) = {
   var x = i
   () => {
      x = x + 1
      x
   }
}

var c1 = makeContador(100)
var c2 = makeContador(10)
c1() -> 101
c2() -> 11

Por último, en el siguiente ejemplo podemos comprobar que es posible acceder al estado local desde otros entornos (el global, en el caso del ejemplo):

import scala.collection.mutable.ListBuffer
def makeClosure() = {
   var b = new ListBuffer[String]
   (s: String) => {
      b += s
      b
   }
}
var g = makeClosure()
var buf = g("Londres")
buf += "Roma"
g("París")

La función makeClosure() define un ListBuffer que se guarda en la variable local b y crea una función anónima de tipo (String) => ListBuffer[String]. La función recibe una cadena y la añade a la variable local b. Después se devuelve el listBuffer. Este listBuffer será un objeto compartido entre el entorno global y la closure que devuelve makeClosure.

Una vez creada la función makeClosure(), se llama y se guarda su resultado (una closure que añade cadenas a b) en la variable g. Cuando invocamos a g con una cadena, esta cadena se añade a b y (lo más importante) se devuelve el listBuffer modificado. Vemos que se asigna a la variable buf. De esta forma hemos conseguido un dato mutable que puede ser accedido desde el entorno global (con la variable buf) y desde la función g.

La siguiente figura muestra los entornos resultantes de la ejecución del programa anterior. Las variables buf y g se definen en el entorno global y la variable b en el entorno local makeClosure. Los entornos locales g se producen por la invocación (dos veces) a la función g, una con el parámetro Londres y otra con el parámetro París. Los parámetros se guardan en estos entornos en los que se ejecutan las sentencias de g.

Las variables buf y g son variables definidas en el entorno global, pero ambas referencian objetos creados en el entorno local. La primera un listBuffer y la segunda una closure. Las dos invocaciones a g se realizan desde el entorno global (con los parámetros Londres y París) pero se ejecutan dentro del entorno local makeClosure, el entorno en el que se creó la closure, creando los dos entornos locales llamados g que aparecen en la figura.

Veamos un último ejemplo. Supongamos que queremos añadir al ejemplo del constructor de contadores una variable local, pero compartida por todos los contadores. Queremos que en esta variable local se acumulen los incrementos de todos los contadores creados. ¿Cómo lo podríamos hacer?

La solución pasa por utilizar en makeContador una variable llamada total que esté definida en un entorno superior:

def makeContador() = {
   var x=0
   () => {
      total = total+1
      x = x+1
      (x,total)
   }
}

Ahora makeContador, además de declarar la variable local x que guarda el valor de cada contador, utiliza una nueva variable total que va a estar compartida por todos los contadores creados. ¿Dónde declaramos total?. Podríamos hacerlo en el entorno global, pero esto permitiría que otro programa externo a los contadores lo modificara. Queremos que total se accesible sólo desde los contadores.

La forma de hacerlo es creando makeContador dentro de otro entorno y para ello necesitamos una nueva función de orden superior, que devuelva makeContador cuando la invoquemos. Será una función de segundo orden, que devuelve una función que, a su vez, devuelve otra función. Llamamos a esta función: constructor:

def constructor() = {
   var total=0
   def makeContador() = {
      var x=0
      () => {
         total = total+1
         x = x+1
         x
      }
   }
   def getTotal() = {
      total
   }
   (makeContador _, getTotal _)
}

Vemos que la función constructor() define la variable local total y después las funciones makeContador y getTotal. Por último devuelve una pareja con ambas funciones definidas. La variable total es una variable local accesible sólo desde makeContador() y getTotal().

El funcionamiento sería el siguiente:

scala> var funcs = constructor()
   funcs: (() => () => Int, () => Int) = (<function0>,<function0>)
scala> var makeContador = funcs._1
   makeContador: () => () => Int = <function0>
scala> var getTotal = funcs._2
   getTotal: () => Int = <function0>
scala> var c1 = makeContador()
   c1: () => Int = <function0>
scala> var c2 = makeContador()
   c2: () => Int = <function0>
scala> c1()
   res34: Int = 1
scala> c1()
   res35: Int = 2
scala> c1()
   res36: Int = 3
scala> c2()
   res37: Int = 1
scala> getTotal()
   res38: Int = 4

---

Lenguajes y Paradigmas de Programación
Curso 2010-2011
Departamento de Ciencia de la Computación e Inteligencia Artificial
Universidad de Alicante

Sitio web realizado con org-mode y el estilo CSS del proyecto Worg