Programación de alto orden: los dos conceptos claves

En la sección anterior mencionamos que aún nos faltaba cierta parte para considerar completo nuestro lenguaje kernel, pero también para considerar completa nuestra definición del paradigma funcional. Si bien lo que hemos estado viendo hasta ahora es parte del paradigma funcional, sería más correcto decir que sin los conceptos introducidos en esta sección, ese paradigma correspondía a una versión más simple conocida como programación funcional de primer orden. Ya con los conceptos, y especificamente, con los dos conceptos que presentaremos en esta sección, entonces podremos dar por terminada nuestra definición. Estos conceptos son la programación de alto orden y los registros. La programación de alto orden se refiere a la capacidad de usar las funciones como entidades de primera clase en el lenguaje. Esto quiere decir que podemos tratar a la funciones como si se trataran de un valor cualquiera, y con ello, ser capaces de pasar y retornar funciones a través de otras funciones. Podríamos, por lo tanto, tener funciones que reciban a otras funciones y retornen una función con un comportamiento completamente nuevo basado en las funciones de entrada. Esta posibilidad, es de hecho, una habilidad completamente poderosa que subyace en las bases de la abstracción de datos, incluyendo a la programación orientada a objetos. De modo que todas estas ideas sofisticadas que veremos en secciones posteriores, como las clases, los objetos, las metaclases, la herencia, y todo lo demás, se pueden definir en términos de la programación de alto orden. El otro concepto, el de registro, se refiere a un tipo de dato compuesto (o estructura de datos) que permite la indexación simbólica como ya revisaremos en su momento. Esta estructura nos será de gran utilidad tanto en la programación simbólica como en la abstracción de datos para hacer legibles abstracciones más complejas.

Bien, aclarado el tema de esta sección, comencemos explorando el primer concepto.

Programación de alto orden

La programación de alto orden está basada en dos conceptos: el entorno contextual y el procedimiento como valor. A continuación, revisaremos cada concepto por separado, comenzando con el entorno contextual, y luego finalizaremos mostrando el poder que tienen los dos juntos.

Entorno contextual

Para entender este concepto, realicemos un pequeño ejercicio. Revisemos cierto código escrito sobre alcance estático. Mediante la revisión de este ejercicio, podremos ver como surge de forma natural la necesidad de un entorno contextual. Bien, aquí está el programa. Asume que nuestro código está aislado de modo que todas las variables presentes son locales a un determinado contexto alcance local ¿Qué crees que debería desplegar?

alcance local:
  declare P, Q

  proc P
    Imprime(100)
  end

  proc Q
    P()
  end

  alcance local:
    declare P

    proc P()
      Imprime(200)
    end

    Q()
  end
end

Bien, cómo puedes ver, se han definido dos contextos locales, uno anidado dentro de otro. En el externo declaramos dos variables P y Q, y a cada una le asignamos un procedimiento. Posteriormente, declaramos una nueva variable P en el contexto interno y le asignamos otra función completamente distinta, para finalizar llamando a Q. En esta situación, ¿Qué valor crees que se imprime? ¿100 ó 200? ¿La función Q llama a la definición dada a P en el alcance exterior o en el interior? ¿Qué piensas?. Para responder rigurosamente a esta pregunta, debemos encontrar cuál es el alcance de la variable P qué está al interior de la definición de Q. Así que, bien, ¿Cuál es su alcance?. Su alcance es aquella parte del programa donde todas las ocurrencias de P hacen referencia a la misma declaración y su variable. ¿Y qué parte es esa? pues toda la sección que corresponde al alcance exterior. Aquella que comienza con las declaraciones de P y Q, y que luego se pausa con la introducción del alcance interno que declara un identificador P nuevamente, para luego reaparecer y terminar con la instrucción end que le corresponde. Por lo tanto, la definición que le corresponde al identificador P dentro de la definición de Q, es aquella dada afuera, la que imprime 100. Así que bueno, 100 es entonces que imprimirá el código anterior. Ahora, ¿Cómo le hace Q para saber cuál es la definición que tiene P en el contexto que se definió Q, si la llamada al procedimiento Q se realiza en un contexto completamente diferente? ¿Cómo sabe Q que la definición de P que le corresponde es la que imprimía 100 y no la que imprimía 200? Bueno, de algun modo debe recordarlo. En especifico, lo que sucede es que Q cuenta con una estructura de datos personal dentro de su definición a la que llamamos el entorno contextual. Y es, en este entorno contextual, donde se almacena la correspondencia entre la P dentro de Q y su definición. Siendo más precisos, el entorno contextual de una función (o procedimiento) contiene todos los identificadores que se usan dentro de la función pero que están declarados afuera de ella. Bien, ahora que ya comprendimos cómo funciona la llamada a Q, veamos otro ejemplo:

declare A = 1

proc Inc(X, Y):
  Y = X + A
end

En este caso, tenemos un procedimiento Inc que suma una variable A que declaramos afuera del procedimiento a un argumento X, y luego almacena esta suma en una variable Y. Posteriormente, dado que Y es el último argumento del procedimiento, se retorna este valor automáticamente. Bien, ahora dado que la declaración de A se encuentra afuera del procedimiento y no directamente en su definición, el identificador A será parte del entorno contextual del procedimiento Inc. Este hecho se puede denotar matemáticamente tal como se muestra a continuación:

$Ec = {A \rightarrow a}, \text{ donde } a = 1$

Aquí se puede ver al entorno contextual como un conjunto que almacena una correspondencia entre A y una variable $a$ declarada afuera de la función, que en el caso del ejemplo, además está enlazada al valor 1.

Nota: A los identificadores incluidos en la definición de una función (o procedimiento), que están declarados afuera de la misma se les denomina identificadores libres.

Para tomar en cuenta: ¿Qué piensas sobre el entorno contextual? ¿Es fácil de comprender? ¿Se te ocurren ejemplos complicados?

Procedimiento como valor

Ahora que ya vimos qué era un entorno contextual, pasemos al siguiente concepto. En este caso, el nombre lo dice prácticamente todo. Procedimiento como valor quiere decir que los procedimientos se consideran valores, y como cualquier otro valor, se pueden almacenar en memoria y vincular a variables. En general, a pesar que en muchos lenguajes la sintaxis para definir un procedimiento o una función, es de algún modo similar a la que se muestra a continuación:

proc Inc(X, Y):
  Y = X + A
end

Pero si en ese lenguaje los procedimientos están definidos como valores, entonces la sintaxis anterior corresponde en realidad a un azúcar sintáctico. En estos casos, lo que en verdad sucede es que un valor de «tipo procedimiento» se asigna a una variable enlazada a un determinado identificador. Es decir, si tomamos en cuenta el ejemplo anterior, lo que realmente está sucediendo es la asignación de la definición de un procedimiento a la variable enlazada al identificador Inc, tal como se muestra a continuación:

Inc = proc (X, Y) Y = X + A end

Nota que en estos casos el procedimiento(o la función) ya no posee un «nombre», sino que es un procedimiento anónimo. Podríamos decir, por lo tanto, que es un procedimiento anónimo (una colección de instrucciones sin un identificador determinado) lo que se asigna a la variable del identificador Inc. Bien, en definitiva eso es un procedimiento como valor. Ahora ya sabes que si el lenguaje trata a los procedimientos como valores entonces esa forma de definirlos usada hasta ahora no es más que un azúcar sintáctico para el acto de vincular un procedimiento anónimo a una variable. De hecho, en nuestra posterior actualización al lenguaje kernel, los procedimientos ya no serán instrucciones en sí, sino valores que se asignan a variables. Comprendido esto, ahora podemos revisar cómo lo anterior se almacena en la memoria. En realidad, no es nada complicado. Hasta este punto sabemos que una asignación de una variable a un identificador se conoce como un entorno, y que lo podemos representar matemáticamente así:

$E: {Id \rightarrow var}$

Como un procedimiento también es un valor, entonces lo que ocurre es exactamente lo mismo. En este caso, también se define un entorno, aunque este entorno puede ser algo especial, ya que además de incluir la correspondencia entre identificador-variable, además puede incluir entornos contextuales, es decir, correspondencias entre identificadores al interior del procedimiento/función y sus declaraciones dadas afuera. Por lo tanto, una variable inc vinculada a un identificador Inc, almacenaría un valor como el siguiente:

inc = (proc(X, Y) Y = X + A end, {A -> a})

Y todo lo anterior se podría representar matemáticamente así:

$E = {A \rightarrow a, Inc \rightarrow inc}$

Bien, con lo anterior podemos ver como los procedimientos son tratados como cualquier otro valor (como un número, por ejemplo). Y si bien son un tipo de valor más complicado, son valores al fin y al cabo. Adicionalmente, podemos ver que cuando se trata de almacenar un procedimiento en la memoria, se almacena como un par compuesto de su definición (su código) y su entorno contextual. Y es este par lo que finalmente se vincula a una variable.

Nota: En la memoria, el código que representa a la definición de la función se puede almacenar de muchas formas. Aunque, por supuesto, se almacena en alguna especie de código compilado más eficiente.

Nota2: Otro término usado bastante para referirse al concepto de procedimiento como valor es el término closure.

Para tomar en cuenta

¿Qué comprendías por procedimiento o función antes de leer el contenido anterior? ¿Qué usos interesantes crees que pueden tener los closures?