Desarrollo del diseño

Como se ha dicho, el enfoque funcional caracteriza un problema como una función a ser definida. Desde el punto de vista de la programación interesan, fundamentalmente, las definiciones de funciones que son dadas en la forma de reglas que definen la construcción del correspondiente de cualquier objeto del dominio.

Una forma (en principio, simplificada) de una tal definición es:

«f» es la función que a cada valor de x hace corresponder «exp»

donde:

«f»

es el nombre de la función a definir,

x

es una variable que representa un objeto genérico del dominio,

«exp»

es la expresión que define el correspondiente de x en f. Como ya se vió, consistirá en general, de aplicaciones de otras funciones.

Se usan las comillas para denotar objetos cuya forma concreta se determinará como consecuencia de decisiones tomadas durante el proceso de diseño. Este estará terminado cuando todos ellos hayan sido sustituidos por construcciones de significado convenido.

La frase usada: «es la función que a cada valor de x hace corresponder» cumple dos roles: por una parte asocia el nombre de la función a su definición. Por otra, indica cuál es el argumento nominal de esta definición. Para abreviar, se usará en su lugar: :- (x), donde la asociación nombre - definición es representada por :- y la indicación de argumento nominal, por su nombre entre paréntesis.

Puede parecer que la notación es extraña y, más aún, invertida en relación a la usanza corriente. Sin embargo, se verá luego que es más razonable, incluso, que la tenida por normal.

El caso más general parecería exigir la posibilidad de definir funciones de más de un argumento. De otro modo, funciones elementales, como la simple suma de enteros, no podrían ser expresadas. Aunque más adelante esta tesis será rebatida, se aceptará de momento y, de hecho, será aplicada al caso de estudio, como surge de las siguientes consideraciones:

El argumento obvio de la función a definir es una fórmula, cuya dimensión debe ser construída como resultado. Sin embargo, éste depende también de las dimensiones de los componentes más primitivos de la fórmula, es decir, de las constantes y variables a partir de las cuales ésta se construye.

Por explicación adicional de lo anterior véase que

$$ma - f$$

por ejemplo, tendrá distintas dimensiones según si $m$ representa una cantidad de masa o de velocidad, e idénticamente ocurre para las demás variables.

De modo que las dimensiones de las variables y constantes intervinientes en la fórmula deben constituir un segundo argumento de esta función, y así aparecerá en su definición, que será de la forma:

dimension :- (f,datom) «exp»

donde

f

representa una fórmula,

datom

representa la asociación de dimensiones a los componentes atómicos (variables, constantes) de f,

«exp»

es una expresión que define el correspondiente de todo par (f, datom) posible en la función dimension.

Es ya inevitable iniciar la discusión acerca de la forma de «exp». Para ésto es necesario definir el conjunto de fórmulas con precisión. Una técnica general que puede usarse con este próposito es la de inducción. Como se verá, constituye una poderosa herramienta de diseño, que será aplicada reiteradamente. Para el caso de las fórmulas pueden usarse las siguientes ideas:

(Base)

Las fórmulas primitivas son las que consisten de apenas una variable o una constante. Se reunirán éstas en una clase, que llamaremos de fórmulas atómicas.

(Inducción)

El resto de las fórmulas puede construirse usando cuatro funciones constructoras: Suma, Resta, Producto, Cociente. La idea será denotar dichas fórmulas como expresiones que sean aplicaciones de estas funciones.

Entonces, si $f$ y $g$ son fórmulas ya construidas,

         Suma     (f, g)
         Resta    (f, g)
         Producto (f, g)
       y Cociente (f, g)

son expresiones cada una de las cuales denota una nueva fórmula, respectivamente la suma, resta, producto y cociente de las denotadas por las $f$ y $g$ originales.

Se exigen propiedades de los constructores:

Para cualesquiera constructores $K$ y $K'$ y fórmulas $f1$, $f2$, $g1$, $g2$ vale:

• Si $f$ es una fórmula atómica, entonces $f \not= K (f1,g1)$
• $K (f1,g1) = K' (f2,g2)$ implica $K$ idéntico a $K'$, $f1 = f2$ y $g1 = g2$

Es decir, las fórmulas construidas por aplicación de constructores son todas diferentes entre sí y diferentes de las atómicas.

En adelante se llamará fórmula a toda expresión formada de acuerdo con las reglas anteriores. Estas permiten establecer que una fórmula cumple una (y sólo una) de las condiciones siguientes:

• es atómica (variable o constante)
• es Suma aplicada a dos fórmulas
• es Resta aplicada a dos fórmulas
• es Producto aplicado a dos fórmulas
• es Cociente aplicado a dos fórmulas

De este modo, se clasifican las fórmulas en cinco clases, según como han sido construídas.

Ahora bien, volviendo al problema, dada una fórmula genérica deberá ser posible distinguir entre sus cinco posibles formas y definir las respectivas dimensiones asociadas por separado. En base a esta idea puede resolverse al problema en cuestión.

Algunas funciones, con significado conveniente, deben ser usadas para expresar lo anterior. En principio, puede pensarse en las siguientes:

i.

Una función asociada a cada clase de las arriba definidas, teniendo como dominio el conjunto de fórmulas y como codominio el conjunto de valores de verdad (Verdadero, Falso). Que una tal función aplicada a una fórmula $f$ dé como resultado Verdadero significará que $f$ está en la clase asociada a dicha función.

ii.

Una función cuyo resultado pueda escogerse de entre varios en base a la verificación de cierta condición.

El candidato para 2 está sugerido en una construcción conocida desde los lenguajes imperativos; se usará:

if b then v1 else v2

con el significado habitual. Es interesante enfatizar que esta construcción denota una función aunque esta idea sea ajena a su pariente imperativo. El carácter funcional podría quedar más de manifiesto si se usara la notación prefija:

if-then-else (b, v1, v2)

más familiar cuando se habla de funciones, en lugar de la empleada, llamada infija.

Cualquiera sea la notación usada, el significado de if-then-else se establece como sigue:

• $b$ puede tomar uno de los dos valores: Verdadero o Falso.
• si $b$ vale Verdadero, entonces if-then-else toma el valor de $v1$ y, en caso contrario, el de $v2$.

A poco de razonar sobre el problema puede verse que los requisitos exigidos en 1 pueden relajarse. En efecto, es necesario usar funciones de la forma citada para distinguir todos los posibles comportamientos de una fórmula genérica en relación a su dimensión asociada, pero también es cierto que los comportamientos diferentes no coinciden con las cinco clases de construcciones definidas. El lector que haya pensado en la relación entre los operadores aritméticos y las dimensiones de sus resultados habrá detectado que la suma y la resta se comportan idénticamente (si no fue así, he aquí una nueva oportunidad para pensarlo).

De modo, pues, que sólo cuatro casos deben ser distinguidos. Uno de ellos puede decidirse por el simple descarte de los otros, si se asume que el argumento $f$ es siempre una fórmula correctamente formada.

Estas consideraciones conducen a la siguiente versión de la función:

  
    dimension :- (f,datom)
  
             if Atómica? (f)      then «exp_atom»
        else if Suma-o-Resta? (f) then «exp_+_-»
        else if Producto? (f)     then «exp_*»
        else                           «exp_/»

El proceso de descomposición comienza a insinuarse. La función dimensión se expresa en términos de otras funciones, en el caso:

if-then-else, Atómica?, Suma-o-Resta?, Producto? y de las que se usen para especificar las aún desconocidas expresiones denotadas entre comillas, que serán precisamente las que construyan los resultados para cada caso.

Nótese que, a la manera de lo anunciado en la sección anterior, las funciones son usadas sólo citando su nombre y no su propia estructura, como «módulos abstractos» de significado convenido. Obviamente deberán continuar el diseño de dimensión.

Este debe ocuparse ahora de las «expresiones» todavía no especificadas.

Entonces:

i.

si la fórmula es atómica, el argumento datom define su dimensión asociada, como ya ha sido dicho; datom mismo puede verse, de hecho, como una función (dada) cuyo dominio es el conjunto de las fómulas atómicas y cuyo codominio es el conjunto de las dimensiones posibles. No importando como estén definidas las dimensiones, lo anterior establece que si f es atómica, entonces datom (f) es su dimensión. Esto resuelve la especificación de «exp_atom».
Nótese el uso de una función como argumento de otra. Esto es permitido ya en algunos lenguajes imperativos, pero como se verá, alcanza toda su generalidad dentro del esquema funcional: las funciones podrán ser, sin restricciones, argumentos y resultados de otras funciones.

ii.

si la fórmula no es atómica, entonces es el resultado de aplicar un constructor a dos operandos que son fórmulas y su dimensión puede expresarse como la aplicación de una transformación conveniente a las dimensiones de los operandos, siguiendo un esquema recursivo.
Para ésto será necesario disponer de funciones que, aplicadas a una fórmula no atómica, devuelvan las fómulas operandos a partir de las cuales aquella fue construida. Tales funciones son, usualmente, denominadas selectores. En el caso, los selectores de fómulas serán las funciones $PrimerOperando$ y $SegundoOperando$.
Hay tres casos interesantes de fórmulas no atómicas, como ya se ha visto. Estas definen tres formas de combinar las dimensiones de los operandos para dar la de la fómula compuesta.
Se llamarán

            DimAd   (adición de dimensiones),
            DimProd (producto de dimensiones) y
            DimCoc  (cociente de dimensiones)

Lo analizado justifica la nueva versión:

   dimension :- (f, datom)

            if Atómica? (f)      then datom (f)

       else if Suma-o-Resta? (f) then
               DimAd ( dimension (PrimerOperando  (f), datom),
                       dimension (segundoOperando (f), datom) ) 

       else if Producto? (f)     then
               DimProd ( dimension (PrimerOperando  (f), datom),
                         dimension (segundoOperando (f), datom) ) 

       else    DimCoc  ( dimension (PrimerOperando  (f), datom),
                         dimension (segundoOperando (f), datom) )

Esto completa un nivel del diseño. En efecto, todas las construcciones «entrecomilladas» han sido sustituídas por expresiones cuyo significado, a este nivel, se da por conocido, siguiendo la idea de la sección 5.1.

Estas expresiones son siempre de la forma:

    «nombre de función» («lista de argumentos»)

denotando aplicaciones de funciones sobre argumentos convenientes.

De este modo, el significado de la función dimensión, se resuelve en términos de los significados de otras funciones, cada uno de los cuales debería, en principio, ser definido en niveles inferiores más detallados.

Se dará un nuevo paso en esa dirección, definiendo las funciones de adición, producto y cociente de dimensiones.

Estas son funciones sobre el conjunto de las dimensiones (más precisamente sobre el conjunto de pares de dimensiones). Como en el caso de las fómulas, debe definirse este conjunto.

En la sección 5.2 se sugirió caracterizar las dimensiones por el producto de tres mangitudes fundamentales afectadas por exponentes enteros. Con esta aproximación, construir una dimensión requiere proveer los valores de esos exponentes, es decir, una terna de dimensiones, que se llamará DimCons. El conjunto de todas las dimensiones es el conjunto de las aplicaciones de DimCons a toda posible terna de enteros.

Inversamente, dada una dimensión genérica b, será necesario obtener los valores de sus exponentes. Para esto se usarán tres funciones: $PrimerExp$, $SegundoExp$, $TercerExp$, a la manera de selectores.

También se usará una función que detecta si dos dimensiones dadas son idénticas. Su codominio es, obviamente, (Verdadero, Falso) y su nombre DimEq. Su comportamiento, el esperable.

A partir de estos supuestos, se desarrollan las tres funciones requeridas:

i.

La adición de dos dimensiones está definida sólo para el caso en que éstas sean idénticas, y el resultado es la misma dimensión.
La restricción impuesta es la manera de expresar el hecho de que no se puedan sumar (ni restar) velocidades con fuerzas, naranjas con libros, o cualquier otro par de cantidades que no hayan sido expresadas idénticamente en relación a las magnitudes fundamentales que se manejen.
En el lenguaje de funciones:

        DimAd :- (d1, d2)
                    if DimEq (d1, d2)
                       then d1
                       else ERROR

ERROR juega aquí como un valor especial distinguido, empleado para denotar casos de excepción como el anotado. En particular representa un caso de dimensión especial (la de las fómulas mal formadas, que intentan combinar operandos «incompatibles»).

ii.

El producto de dos dimensiones es, en todos los casos, otra dimensión cuyos exponentes son, cada uno, la suma de los respectivos exponentes de los operandos:

      DimProd :- (d1, d2)
                    DimCons
                        (PrimerExp  (d1) + PrimerExp  (d2),
                         SegundoExp (d1) + SegundoExp (d2),
                         TercerExp  (d1) + TercerExp  (d2))

iii.

El cociente de dos dimensiones es otra dimensión, cuyos exponentes son, cada uno, la diferencia de los respectivos exponentes de los operandos:

      DimProd :- (d1, d2)
                    DimCons
                        (PrimerExp  (d1) - PrimerExp  (d2),
                         SegundoExp (d1) - SegundoExp (d2),
                         TercerExp  (d1) - TercerExp  (d2))

Aquí han aparecido ya funciones que el lector puede, sin duda, aceptar como «primitivas»: son las denotadas por los conocidos símbolos $+$ y $-$ y que representan la suma y resta de enteros. Seguramente no extrañará que no se den definiciones sobre dimensiones, por ejemplo.

A la vez, durante el desarrollo se ha hecho referencia a otras funciones que parecerían merecer una definición detallada, como las llamadas Atómica?, Suma-o-Resta?, etc.

En definitiva, debe convenirse acerca de cuál es el conjunto de funciones primitivas. Tal convención debe establecerse en forma precisa y definitiva para todos los problemas que quieran ser resueltos y determina el nivel de explicación al que debe llegarse, en un lenguaje dado, para que una solución se considere suficientemente descripta.

En este caso, el lenguaje no ha sido definido con precisión de antemano, lo que autoriza a detener el proceso de diseño en el momento en que las explicaciones dadas se consideren suficientes para ilustrar la técnica de descomposición modular. Ese momento ya ha llegado.

En efecto, se ha mostrado la utilización del concepto de «módulo abstracto» en su forma funcional y definiciones de algunos de éstos han sido desarrolladas con independencia de la del módulo de mayor jerarquía que los utilizaba. En capítulos siguientes habrá ocasión de someterse a reglas rigurosas que obliguen a llegar a niveles de refinamiento precisamente establecidos.

También se ha mostrado el empleo de algunas técnicas de diseño generales, como las de definiciones inductivas, y algunas características novedosas de los lenguajes funcionales han comenzado a insinuarse, en especial la posibilidad de tratar a las funciones como argumentos y resultados de otras funciones.

Estos puntos serán especialmente considerados en el siguiente capítulo.

Problemas.

5.1

Escribir la definición de la función que calcula el máximo común divisor de dos naturales dados.

5.2

Usando selectores y funciones auxiliares apropiadas (que no se definirán) escribir la definición de una función que sume todos los elementos de un árbol binario.

5.3

Escribir la definición de una función que, aplicada a una lista de enteros, devuelve un árbol binario «ordenado».

5.4

Escribir definiciones de funciones que, aplicada a un árbol binario, devuelvan la lista de sus elementos, en:

a)

pre orden

b)

orden central

c)

post orden

5.5

Usando 3 y 4 escribir la definición de una función que ordene una lista dada.

Hosted by www.Geocities.ws