Uniendo los conceptos: Ejemplos de programación de alto orden

Bien, hemos llegado a una de las lecciones claves del curso: mostrar qué podemos hacer con la programación de alto orden. En la lección anterior establecimos que en la programación funcional los procedimientos son un par compuesto de un procedimiento como valor y un entorno contextual. Esta definición es enormemente expresiva. De hecho, se podría decir que es la invención más importante en los lenguajes de programación, ya que desde que fue inventada en los años 50 ha hecho posible construir sistemas grandes basados en abstracción de datos (usando capas, encapsulación, etc). Muchas de las buenas propiedades de los lenguajes de programación están basadas en esta idea clave de la programación de alto orden, así que es sumamente relevante revisar más de cerca su potencial. Pero antes de revisar algunos ejemplos de uso, primero necesitamos comprender cierto marco teórico, en específico, ciertas nociones y conceptos habituales en la jerga de la programación de alto orden que nos permitirán entendernos mejor cuando se trate de describir las distintas características que la rodean. Bien, lo primero y más esencial, es estar al tanto que en la programación de alto orden contamos con la capacidad de pasar procedimientos (o funciones) como entradas a otras funciones y, también de retornar procedimientos como salida. Esto, de hecho, es una consecuencia directa de considerar a los procedimientos como valores: tal como podemos pasar y retornar enteros, podemos pasar y retornar funciones. Otra noción clave es que las funciones tienen un orden. De hecho, nota que estamos hablando de programación de alto orden. Así que, ¿a qué nos referimos con el concepto de orden de una función? ¿A qué nos referimos también con la idea de alto orden?. Bueno, básicamente cuando nos referimos al orden de una función lo que buscamos describir es el «nivel de profundidad de una función en una cadena de funciones», o en otras palabras, cuántas llamadas dentro de otras funciones se han realizado antes para llegar a la llamada de una función en específico. Por ejemplo, si para llamar a una función c() hay que realizar el siguiente camino [dato -> a() -> b() -> c()], entonces podríamos decir que c() es una función de «tercer» orden o orden tres. Adicionalmente, también podríamos decir que b() es de segundo orden, y a() de primer orden, pues recibe un dato que no es una función, y luego también, asumimos que no retorna una función, sino un valor que obtiene tras pedir ayuda a b() (donde, a su vez, b() pide ayuda a c()).

A continuación, se muestra una definición un tanto más compacta de cómo se define el orden de una función.

Orden de una función

Definimos el orden de una función de la siguiente manera:

  • Una función cuya entrada y salida no son funciones es una función de primer orden

  • Una función en cuya entrada o salida hay una función de orden máximo N se considera un función de orden N + 1

Nota que en la medida que vamos aumentando el orden de las funciones (definiendo mayor profundidad), también nos vamos abstrayendo más y más de los distintos cómo definidos en el programa. A mayor orden, mayor abstracción y generalidad.

Nota: El nombre de programación de alto orden viene justamente de la idea de programar utilizando funciones de orden superior a uno.

Genericidad

Bien, ahora que ya tenemos en cuenta estas dos nociones claves de la programación de alto orden, vayamos revisando los otros conceptos al mismo tiempo que vemos ejemplos de lo que podemos hacer con la programación de alto orden. El primer ejemplo da cuenta del concepto de genericidad. El término genericidad, por lo general, básicamente se refiere a cuando una función se pasa como argumento a otra función. Toma como ejemplo el siguiente programa:

fun Map(Funcion, Lista):
  case Lista:
    of nil
      return nil
    elseif E|C
      return Funcion(E)|Map(Funcion, C)
  end
end

En este caso, definimos una función Map que toma como argumentos a otra función y una lista, y que nos debería retornar una nueva lista creada a partir de aplicar la función pasada como argumento a cada uno de los elementos de la lista. Si posteriormente ejecutamos esta función pasando como argumento una determinada función anónima y lista como se muestra a continuación:

Map(fun(x) return x*x end , [5, 6, 7])

entonces lo que obtenemos es una lista compuesta con el cuadrado de cada uno de los elementos de la lista pasada como segundo argumento (es decir, obtenemos la lista [25, 36, 49]). Ahora, ¿Cuál es el orden de esta función Map? Bueno, eso depende de la función que reciba como argumento. En este caso, dado que la función que recibe es de orden uno, entonces el orden de map es dos.

Instanciación

Veamos otro ejemplo. En este caso el concepto subyacente es el de instanciación. Así como la genericidad se refería a tomar una función como entrada, la instanciación se refiere a la otra parte, al retorno de una función como salida. El siguiente código da muestra de un ejemplo de instanciación:

fun hacerSuma(A):
  return fun(x) return x + A end
end

Sumar5 = hacerSuma(5)

Imprimir(Sumar5(100))

Definimos una función hacerSuma() que toma como argumento un entero, y luego retorna una función anónima que incluye en su entorno contextual la correspondencia entre A y el argumento que le hayamos dado a la función. Luego, tal como se muestra debajo de la definición de hacerSuma(), podemos llamar a la función con un valor en específico, como 5, y almacenar la función anónima de retorno en una variable. En este caso, la variable está enlazada al identificador Sumar5. Nota además que este identificador se puede tratar posteriormente como si se tratara de una función (pues, de hecho, es a lo que enlaza), siendo posible usarlo como intermediario para acceder a la función anónima que toma un entero y le suma 5 que obtuvimos anteriormente. Luego, el código finaliza imprimiendo 105. Bien, en definitiva, esto es la instanciación. Si ya conoces algo de orientación a objetos puedes haber notado la cercanía de esta idea con la relación entre las clases y sus instancias. De hecho, como ya veremos, hay una conexión muy fuerte entre estas ideas. Ahora, repitamos la pregunta que nos hicimos para Map ¿Cuál es el orden de la función hacerSuma?. Bueno, dado que retorna una función de primer orden, entonces su orden es dos.

Nota: Como el identificador A dentro de la función anónima está declarado afuera de la misma, en particular, al momento de hacer una llamada a la función hacerSuma, entonces A es parte del entorno contextual de la función anónima. Cada vez que llamamos a hacerSuma, retornamos una nueva versión de la función anónima con A asociado al valor del argumento en específico que hayamos pasado. Por lo tanto, si bien en Sumar5 se almacena una versión dónde siempre A = 5, podríamos llamar a la función con un argumento distinto cada vez que queramos contar con una versión donde A tenga otro valor.

Composición de funciones

El siguiente concepto ya lo mencionamos antes: la composición de funciones. Aunque ahora lo vemos más bien desde su definición matemática, en lugar de simplemente como la capacidad de llamar a una función dentro de otra. En matemáticas, cuando se habla de componer una función, se hace referencia a lo siguiente:

a(b(x)) a(b(x))

Es decir, a la inclusión de una función como parámetro de otra, con el fin de obtener otra función completamente distinta. Así, por ejemplo, si a=x2a = x^2 y b=x+1b = x + 1, entonces mediante la composición de aa y bb obtendríamos a(b(x))=(x+1)2a(b(x)) = (x + 1)^2. En programación de alto orden, dado que podemos pasar funciones como argumentos y también retornar funciones, componer funciones como en la matemáticas resulta natural. Podríamos, de hecho, definir una función que tome otras dos funciones y retorne la composición entre ellas:

fun Composicion(Funcion1, Funcion2):
  return fun(X): Funcion1(Funcion2(X))
end

Básicamente, retornamos una función anónima que toma un argumento X y retorna el resultado de evaluar el retorno Funcion2(X) con Funcion1. Por ejemplo, podríamos obtener la función (x+1)2(x + 1)^2, tal como la obtenemos mediante composición matemática:

cuadratica = Composicion(fun(X) return x*x end, fun(X) return x + 1 end)

cuadratica(3) //=> (3 + 1)^2 = 16

En este caso, pasamos las funciones que deseamos componer como funciones anónimas. Ahora, nota que las funciones usadas en la función anónima retornada se declaran afuera de esta función, y por lo tanto, son parte del entorno contextual de la función que se retorna. El argumento X, en cambio, se puede especificar cada vez que llamemos a la función retornada.

Ejercicio
¿Qué sucede si se realiza la composición Composicion(cuadratica, cuadratica) y a la función retornada se le pasa cómo argumento el valor 3?

Abstracción de un acumulador

Bien, ahora revisemos otro concepto: la abstracción de un acumulador. Resulta que cuando se programa en estilo funcional, debido a que las variables son de asignación única, suele estar la preocupación de que uno vaya a necesitar muchas, muchas variables, y que debido a eso, se arme un completo desorden en tu programa. Sin embargo, esta preocupación es completamente infundada. Una opción para evitar esto, es ocultar un acumulador usando programación de alto orden. Y justamente de eso se trata cuando hablamos de abstraernos de un acumulador. Considera el siguiente ejemplo, digamos que queremos sumar los elementos de una lista. Contamos con una lista L=[a0,a1,a2,…,an−1]L = [a_0, a_1, a_2, \ldots, a_{n-1}] y queremos obtener S=a0+a1+a2+…+an−1S = a_0 + a_1 + a_2 + \ldots + a_{n-1}. Nota que como empezamos la numeración desde 0, el n-ésimo elemento tiene subíndice n−1n-1. Bueno, resulta que esta operación la podemos escribir de forma asociativa de la siguiente manera:

S=(…(((0+a0)+a1)+a2)+…an−1) S = (\ldots (((0 + a_0) + a_1) + a_2) + \ldots a_{n - 1})

Primeros sumamos a 0 el primer elemento de la lista, luego a ese resultado le sumamos el segundo elemento, y luego a ese resultado le sumamos el tercero, y así en adelante, hasta sumar todos elementos. En otras palabras, asumiendo la existencia de una función F que retorna la suma de dos elementos, podríamos reemplazar cada una de las sumas presentes en la fórmula anterior con una llamada a esta función F. Realizando ello la suma total se podría ver también cómo una composición de funciones F una sobre otra. De modo que podríamos escribir genéricamente esta suma de la siguiente manera:

S=F(F(…F(F(F(0,a0),a1),a2)),an−1) S = F(F(\ldots F(F(F(0, a_0), a_1), a_2)), a_{n-1})

Y decimos genéricamente, ya que si bien para que lo anterior retorne la suma de los elementos de la lista, F debe retornar la suma de sus dos argumentos, F no necesariamente se tiene que limitar a esta definición. F podría ser una función cualquiera, y de ser eso posible, podríamos utilizar la perspectiva anterior para resolver mucho más que la suma de los elementos de una lista. Si F retornara el producto de sus argumentos, podríamos obtener la productoria de los elementos de la lista (si el primer argumento inicial fuera 1, claro). O si F retornara el máximo entre dos elementos, podríamos obtener el máximo de una lista de elementos. Se entiende la idea. Bien, ahora para solucionar este problema desde esta perspectiva, podemos definir una función que haga justamente lo que muestra la expresión de más arriba. Una función que tome como argumentos, una lista, una función, y un elemento inicial, y realice toda esa serie de composiciones, para luego retornar el resultado buscado. Llamemos a esta función AsociatividadIzq, ya que la asociatividad se va realizando justamente desde esa dirección.

S = AsociatividadIzq(Lista, Funcion, i)

Ahora, si pasamos a AsociatividadIzq como segundo argumento una función que retorne la suma de dos números, y pasamos como tercer argumento el valor 0, entonces obtenemos la suma de todos los elementos de cuál sea la lista que se pase como primer argumento. Finalmente, nota como mediante la composición de funciones evitamos completamente el uso de un acumulador. El acumulador está oculto dentro de la definición de AsociatividadIzq.

A continuación se muestra una definición para nuestra función AsociatividadIzq:

fun AsociatividadIzq(Lista, Funcion, A): //A = acumulador
  case L:
    of nil
      return A
    elseif E|C
      return AsociatividadIzq(C, Funcion, Funcion(A, E))
  end
end

Toma como argumentos una lista, una función, y el valor inicial que queremos para el acumulador. Luego realiza un case con el fin de verificar si la lista está vacía o tiene al menos un elemento. Si está vacía, entonces retorna el acumulador. Si tiene al menos un elemento, entonces realiza una llamada recursiva pasando la cola de la lista como primer argumento (o sea una versión reducida de la lista original), la función pasada como entrada sin ninguna modificación como segundo argumento y finalmente el resultado de aplicar la función de entrada al acumulador y el encabezado como último argumento. Ya con esta definición, podemos solucionar como caso particular el problema de sumar los elementos de una lista que planteamos al inicio:

S = AsociatividadIzq(Lista, fun(x, y) return x + y end, 0)

Encapsulación

Aunque ya hemos visto varios conceptos y ejemplos asociados a esos conceptos, aún no hemos agotado para nada las habilidades de la programación de alto orden. El siguiente concepto que vamos a revisar es la encapsulación. Con encapsulación nos referimos a una cosa bastante interesante que podemos hacer: ocultar un valor dentro de una función. Considera el siguiente ejemplo:

fun Cero():
  return 0
end

fun Inc(H):
  declare N = H() + 1
  return fun() return N end
end

Definimos dos funciones, una llamada Cero y otra Inc. La función Cero es sencilla, no toma ningún argumento y retorna el valor 0. Inc, en cambio, toma una función como argumento, y luego declara un identificador N al que asocia la suma de llamar a la función del argumento y sumarle 1. Finalmente, Inc retorna una función anónima que no toma argumentos y devuelve el valor de N oculto en su entorno contextual. Ahora, si por ejemplo, anidamos llamadas a Inc como se muestra a continuación:

Tres = Inc(Inc(Inc(Cero)))

Imprimir(Tres()) //=> 3

Entonces obtenemos un efecto curioso. Con la llamada más interna de Inc, la que tiene como argumento la función Cero, obtenemos una función anónima cuyo valor de N en su entorno contextual es 1. Luego, con la siguiente llamada de Inc a la que pasamos la función anónima obtenida anteriormente, obtenemos otra función anónima, pero esta vez una cuyo valor de N está asociado a 2. En la última llamada el efecto se repite, y obtenemos una función anónima con N igual a 3 en su entorno contextual, que es la función que almacenamos en Tres. Cuando después imprimimos el valor que se obtiene al llamar a tres, podemos observar como efectivamente este número es 3. Este ejemplo es algo trivial, pero nos muestra como las funciones pueden ocultar cosas dentro de ellas, o más especificamente, valores dentro de su entorno contextual y cómo podemos hacer uso de estos valores ocultos. Esto, de hecho, es la base de la encapsulación. Y aunque es un ejemplo trivial, como ya dijimos, se volverá muy importante más adelante cuando lo combinemos con otras técnicas y lo usemos en abstracción de datos.

A tener en cuenta:
¿Qué pasaría si en la definición de Inc, en lugar de declarar una variable N que almacene H() + 1 fuera de la función anónima, se retornara directamente una función con esta suma? Es decir, ¿Qué pasaría si la definición de Inc fuera la siguiente?

Inc(H):
  return fun() return H() + 1 end
end

¿Cuál es la diferencia entre las dos funciones?¿Qué almacenaría ahora el identificador Tres?

Ejecución retardada

El siguiente concepto también es bastante poderoso. Resulta que usando programación de alto orden podemos definir nuestras propias estructuras de control. En específico, podemos definir funciones que tomen a otras funciones como argumentos, como ya nos es común, pero que tengan la particularidad de «decidir» si ejecutar o no esa función. Y esto es lo que se conoce como ejecución retardada. Ahora, ¿Cómo se supone que la función «toma una decisión»?. El mecanismo es bastante simple. Es el mismo que hemos venido usando en todos nuestros programas anteriores, evaluar una condición usando una instrucción if. Sin embargo, la diferencia está en que la condición es la llamada a una función que retorna un valor de verdad, tal como se muestra a continuación:

proc IsTrue(Condicion, Funcion):
  if Condicion():
    Funcion()
  end
end

Nota que para este ejemplo, tanto Condicion como Funcion deben ser funciones que no tomen ningún argumento. Además, por supuesto, que Condicion debe retornar un booleano. Respecto al funcionamiento, IsTrue simplemente se limita a tomar las dos funciones, y luego tras ejecutar a Condicion, «decide» si ejecutar o no a Funcion. Bien, el comportamiento que podemos obtener con la función anterior es bastante interesante, veamos un ejemplo. Supongamos que llamamos a la función de la siguiente manera:

AlgunaFuncion = fun() Imprimir(1000) end
AlgunaCondicion = fun() return 1 < 2 end

IsTrue(AlgunaCondicion, AlgunaFuncion)

En este caso, definimos dos funciones anónimas que vinculamos a los identificadores AlgunaFuncion y AlgunaCondicion. Luego llamamos a IsTrue haciendo uso de estas funciones. El resultado, como podrás pensar, es la impresión de 1000. Esto debido a que AlgunaCondicion siempre retornará true. Ahora bien, lo que vale la pena notar, es que dentro de la función se evalúa una condición que pasamos desde fuera. Y con ello, hacemos una completa diferenciación entre declarar una función y determinar si ejecutarla o no. Esta separación entre definición y condición resulta bastante útil, pues como afirmamos al principio, incluso se puede usar para construir estructuras de control, como instrucciones if, while, for, completamente desde cero. Aunque, claro, no necesitas porque inventar estas estructuras por ti mismo en un lenguaje que ya las proporciona, pero usando programación de alto orden, puedes añadir tus propias estructuras de control sofisticadas.

Resumen

Bien, aún quedan muchas cosas más que se pueden hacer con programación de alto orden. Pero los seis ejemplos y los conceptos asociados que hemos visto hasta ahora, ilustran bastante bien su potencial y expresividad. En siguientes secciones iremos mostrando aún más ejemplos de la fuerza que rodea a esta idea. En especifico, cuando comencemos a hablar de abstracción de datos en detalle, usaremos estas técnicas junto a otras, y mostraremos como la abstracción de datos está construida sobre la programación de alto orden.

Conceptos y ejemplos de uso de la programación de alto orden

  • Genericidad
  • Instanciación
  • Composición de funciones
  • Abstracción de un acumulador
  • Encapsulación
  • Ejecución retardada

Ejercicio:
El siguiente ejercicio se centra en el uso de funciones que toman funciones como entrada.

Considera la siguiente función:

fun FunnyFunc(ListaFunciones, Lista):
  case Lista:
    of E|C
      return ListaFunciones.head(E)|FunnyFunc(ListaFunciones.cola C)
    else
      return nil
  end
end

ListaFunciones es una lista de funciones que toman un entero como entrada y Lista es una lista de enteros. Estas dos listas DEBEN tener el mismo tamaño y su tamaño tiene que ser estrictamente mayor a 1.

Se te pide llamar al siguiente procedimiento de prueba:

proc Prueba(ListaFunciones, Lista, ListaSolucion):
  Imprimir(FunnyFunc(ListaFunciones, Lista) == ListaSolucion)
end

Junto a ello, se te pide crear un cierto número de funciones y llamar al procedimiento de prueba con una lista que contenga a estas funciones, una lista de enteros de tu elección y la lista que se espera como resultado.

Más precisamente, si Fun1, Fun2, ..., FunN son las funciones que creaste y que colocas en ListaFuniones. Y si Int1, Int2, ..., IntN es la lista de números de tu elección que corresponde a Lista, y Sol1, Sol2, ..., SolN son los resultado esperados puestos en ListaSolucion, tienes que hacer la siguiente llamada:

Prueba(ListaFunciones, Lista, ListaSolucion)

Ejercicio:

Este ejercicio se centra en el uso de las funciones como salida.

Tu profesor de matemáticas te pide que le escribas una función. Te da el dominio y codominio de su función matemática y tu función tiene que producir otra función que represente a la función matemática de tu profesor.

Tanto el dominio como el codominio son listas de números de la misma longitud. La función que retornes debería recibir como argumento un valor del dominio y retornar el valor que le corresponde del codominio. En específico, a cada i-ésimo elemento del dominio, le debe corresponder el i-ésimo elemento del codominio. Es decir f(D[i]) == C[i]. Adicionalmente, si el valor pasado como argumento no se encuentra en el dominio, la función debería devolver la cadena "No encontrado".

Para tomar en cuenta:

¿Cómo usarías la programación de alto orden en la práctica?¿Qué ejemplos se te ocurren?