Simplificación de expresiones booleanas mediante álgebra de Boole

George Boole

George Boole, el patrón.

Cuando estamos repasando código podemos encontrarnos expresiones booleanas en condiciones lógicas más complejas de lo necesario que dificultan entender lo que el código hace. Esto puede ser debido a que la persona no tiene los conocimientos necesarios para hacerlo mejor (en esta profesión uno se encuentra hasta biólogos sin mayor interés en la profesión que el salario) o al constreñimiento que sufrió el programador cuando desarrolló el código que estamos repasando. Por lo tanto, puede ser nuestro propio código el que incurra en esos errores que ahora, con más calma, descubrimos y nos preguntamos en qué estaríamos pensando cuando hicimos esos whiles y esos ifs.

Para reducir el total de términos de una expresión booleana existen técnicas como los mapas de Karnaugh o el método de Quine-McCluskey pero en programación generalmente es suficiente con las leyes del álgebra de Boole. Teniendo en cuenta que la condición lógica AND es el producto booleano, OR es la suma y NOT el complemento  , las leyes son:

  • Idempotencia:
    1. x + x = x
    2. x * x = x
  • Doble complemento:
    1. ¬x (doble negación) = x
  • Identidad respecto a la suma y el producto o elementos neutros de la suma y del producto:
    1.  x + 0 = x
    2. x * 1 = x
  •  Maximalidad de los elementos 1 y 0:
    1. x + 1 = 1
    2. x * 0 = 0
  • Leyes asociativas respecto de la suma y del producto:
    1. x + (y + z) = (x + y) + z
    2. x * (y * z) = (x * y) * z
  • Leyes distributivas respecto de la suma y del producto:
    1. x + y * z = (x + y) * (x +z)
    2. x * (y + z) = x * y + x * z

Esta última ley no es tan evidente pero se ve claramente con su tabla de verdad:

x y z y+z x*y x*z x*(y+z) x*y + x*z
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
1 0 1 1 0 1 1 1
1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1
  • Leyes de De Morgan:
    1. x + y = x * y
    2. x * y = x + y

También las podemos comprobar mediante sus tablas de verdad:

x y x y x+y x+y x*y
0 0 1 1 0 1 1
0 1 1 0 1 0 0
1 0 0 1 1 0 0
1 1 0 0 1 0 0

Estas leyes se pueden generalizar a más de dos variables. Además, podemos ver que x * yx*y

  • Ley de absorción:
    1. x(x + y) = x

Su tabla de verdad es:

x y x + y x(x + y)
0 0 0 0
0 1 1 0
1 0 1 1
1 1 1 1

La ley de absorción también se concluye aplicando las leyes anteriormente mencionadas:

x(x + y) = (x + 0)(x + y) = x + 0*y = x + 0 = x

Aplicando las leyes booleanas se deducen las siguientes propiedades:

  • x + xy = x
  • x + xy = x + y
  • x + x = 1
  • x * x = 0

Si bien las dos últimas son evidentes, para las dos primeras podemos crear sus correspondientes tablas de verdad en caso de duda.

También es conveniente conocer un teorema acerca del complemento de una función booleana y  para ello hay que explicar primero qué es una función booleana. Una función booleana es algo tan sencillo como las tablas de verdad que hemos visto antes: dadas unas variables x, y, z… se obtiene un resultado F. El grado de la función es el número de variables. Este es un ejemplo de una función grado dos F2→F:

x y F(x, y)
0 0 0
0 1 1
1 0 1
1 1 1

La expresión booleana que produce tal resultado F es: x* y + x*y + x*y Aunque cómo encontrar la expresión booleana a partir de una tabla de verdad es otro tema. Ahora que ya sabemos qué es una función booleana, dejemos esta función de momento a un lado y volvamos entonces al teorema:

El complemento de una función booleana F se obtiene complementando todas sus variables e intercambiando las operaciones de suma y producto, es decir:

F(x1, x2, … xn,+,* = F(x1, x2, …,xn, *, +)

Por ejemplo el complemento de la función anterior F se podría expresar como:

F = (¬x + y) * (x + ¬y) * (x + y) A + B + C = A + B + C = (x+y) * (x*y) * (x*y)

Con los minterm y maxterm también se acaba viendo que toda función booleana puede expresarse tanto como un conjunto de minterms multiplicados, como un conjunto de maxterms sumados. Aunque los minterm, maxterm y las formas canónicas también podrían ayudarnos, con las leyes anteriores, propiedades y el último teorema no debería haber código que se nos resista a ser simplificado. Veamos algunos ejemplos de despistes que hacen el código poco legible y como quedarían simplificados:

if (($foo && myFunction()) || ($foo && $bar)) {

Con la ley distributiva quedaría: if ($foo && (myFunction() || $bar))

if (!($foo || $bar || myFunction())) {

La expresión booleana de este if sería x + y + z

Aplicando la propiedad asociativa: x + (y + z)

Reemplazando por a: x + a

Aplicando la ley de De Morgan: x * a

Deshaciendo el reemplazo: x * (y + z)

Otra vez De Morgan: x * y * z

Así que el if original quedaría if (!$foo && !$bar && !myFunction()) {

El operador lógico XOR, aunque no forma parte de las operaciones booleanas básicas, tiene tantas utilidades que está en toda clase de circuitos y lenguajes de programación. Su función booleana es:

XOR = x*y + y*x

Devuelve 1 sólo cuando x e y tienen valor diferente. Su tabla de la verdad es:

x y XOR(x, y)
0 0 0
0 1 1
1 0 1
1 1 0

Por lo tanto, el siguiente código:

if (($foo && !$bar) || (!$foo && $bar)) {

Quedaría:

if ($foo xor $bar) {

Ahora bien, si sabemos que ambas variables son booleanas, esto es exactamente lo mismo y según como hasta más legible:

if ($foo !== $bar) {


Nota:

Las leyes de álgebra de Boole están en estrecha relación con la lógica de predicados o de primer orden. Dos ejemplos: la ley de absorción es el modus ponens y las leyes de De Morgan también aplican a los conjuntos. Estas últimas son:

  1. A ∪ B = AB
  2. A ∩ B = AB

Veamos la segunda ley. Ésta nos dice que la intersección de todos los elementos que no son de A con la de todos los que no son de B equivale a la unión de todos los que no son de A con todos los elementos que no son de B. Su demostración es:

Se lee: Todo x tal que x no pertenece a la intersección de A con B

Demostración segunda ley de De Morgan


Una consecuencia muy interesante de las leyes de De Morgan es que AND se puede expresar mediante OR y NOT y viceversa: OR con AND y NOT. Por lo tanto, toda función booleana se puede expresar mediante una de estas combinaciones de tan solo dos condiciones lógicas. Esto se ve más claramente si se expresan en la forma de sustitución:

  1. x + y = ¬x * ¬y
  2. x * y = ¬x + ¬y

Por consiguiente, se puede crear una CPU con tan solo dos de los tres tipos de puertas lógicas capaz de ejecutar cualquier programa, por complejo que sea. Eso sí, no lograría la misma velocidad de ejecución.

 

Un algoritmo de generación de números pseudoaleatorios

En la nota a pie del artículo La privacidad no existe citaba un artículo de la Wikipedia acerca de cómo generar números aleatorios mediante software. En esta entrada voy a poner un ejemplo sencillo desarrollado en Python. Obviamente Python tiene sus propias funciones para ello, pero nada nos impide desarrollar nuestra propia función.

En primer lugar veamos la teoría que hay detrás. Estos algoritmos lo que realmente generan son números pseudoaleatorios porque usan procedimientos sistemáticos. El método más empleado es el de congruencia lineal. Se eligen cuatro números enteros: un módulo m, un multiplicador a, el incremento c y la semilla x0 Estos números deben ser números enteros positivos mayores de 0. El artículo de la Wikipedia también impone que  a, c y x0 deben ser menores que m pero no encuentro ninguna razón para ello. De hecho, al final el artículo entra en contradicción al afirmar que el estándar POSIX para C define a = 1103515245 y m = 32768 Con lo que a > m

Una semilla válida la podemos obtener del reloj interno de la CPU: el RTC. En el ejemplo usaré el método time() de la librería time. Éste nos da el tiempo que ha pasado desde el tiempo Unix: el 1 de Enero de 1970. Como se puede ver, devuelve un número en coma flotante:

>>> time.time()
1487416084.126488

Como necesitamos un entero lo convertimos, el número de segundos será suficiente para el ejemplo.

Siguiendo con la teoría, la semilla nos dará el primer número aleatorio y este mismo número será la semilla para el siguiente. Partiendo de una semilla inicial xn sería:

xn+1 = (axn + c) mod m

Como a, c y m usaré los valores del estándar Posix para C. Este programa genera 10 números aleatorios:

import time

xn = int(time.time()) #Semilla

for i in range(10):
    xn1 = (1103515245 * xn + 12345) % 32768
    print(xn1)
    xn = xn1

Si lo ejecuto este es el resultado:

13566
9311
7852
10101
8970
10107
31128
17905
26070
16471

Lo ejecuto otra vez lo más rápidamente posible:

875
16072
23393
9862
27463
32628
19613
9490
29923
7904

Como vemos hay bastante aleatoriedad. Suficiente para videojuegos y modelos de simulación. Aunque entre ambas ejecuciones sólo pase un segundo los resultados no tienen nada que ver. Si necesitamos diferentes ejecuciones en menos de un segundo podríamos crear un entero fruto de la concatenación de la parte entera y la parte decimal del número que devuelve time()

Llegará un momento en que el resultado obtenido coincida con alguno de los resultados ya obtenidos. Cuando eso pase sabremos que la serie ha acabado y a continuación se repetirán los mismos números. Veámoslo usando unos valores más pequeños: m = 7, a = 5, c = 3 y x0 = 2:

x1 = 5x0 + 3 = 5*2 + 3 = 13 mod 7 = 6
x2 = 5x1 + 3 = 5*6 + 3 = 33 mod 7 = 5
x3 = 5x2 + 3 = 5*5 + 3 = 28 mod 7 = 0
x4 = 5x3 + 3 = 5*0 + 3 = 3 mod 7 = 3
x5 = 5x4 + 3 = 5*3 + 3 = 18 mod 7 = 4
x6 = 5x5 + 3 = 5*4 + 3 = 23 mod 7 = 2
x7 = 5x6 + 3 = 5*2 + 3 = 13 mod 7 = 6

Por lo tanto la serie que se repetirá ad infinitum es: 6, 5, 0, 3, 4, 2, …

De hecho, podríamos decir que la serie empieza por el 2, pues ya x6 = x0. Ahí tenemos la primera coincidencia, antes de llegar a x7 En el algoritmo en Python no se muestra x0 para no tener el primer número pseudoaleatorio de la serie demasiado parecido en diferentes ejecuciones.

En el mejor de los casos posibles el número de elementos de la serie será igual a m. Una mala elección de los valores iniciales m, c y x0 conduciría a una serie muy corta. Según el teorema de Hull-Dobell un generador congruencial tiene una secuencia completa (el número de elementos es igual a m) si y solo si:

  1. m y c son primos entre si.
  2. a -1 es divisible por todos los factores primos de m.
  3. Si 4 divide a m, entonces 4 divide a a – 1.

Además, los algoritmos más eficientes escogerán como m una potencia de 2, pues la operación módulo podrá ser calculada simplemente truncando los 32 o 64 bits más a la derecha.

El estándar POSIX para C ha escogido cuidadosamente los valores cumpliendo con las condiciones del teorema de Hull-Dobell. Veamos:

  1. 1103515245 y 32768 son primos entre si.
  2. El único factor primo de 32768 es 2: 32768 = 215 y 1103515244 | 2 Además es eficiente al ser potencia de 2.
  3. Se cumple tanto 32768 | 4 como 1103515244 | 4

Por lo tanto el algoritmo anterior debería dar una serie 32768 números únicos. Veamos si es cierto con una sencilla modificación del programa anterior que irá añadiendo números a la tupla hasta que se produzca la primera repetición:

import time

xn = int(time.time())
total = []
repeated = False

while (not repeated):
    xn1 = (1103515245 * xn + 12345) % 32768
    xn = xn1
    repeated = xn1 in total
    if (not repeated):
        total.append(xn1)
    
print(total)
print(len(total))

No voy a mostrar la tupla resultante por ser demasiado larga, será bastante con ver el número de elementos que la componen (segundo print):

32768

El número de elementos de la tupla resultante siempre será el mismo por más veces que lo ejecutemos.

Si necesitamos números aleatorios entre 0 y 1 haríamos xn / m :

xn = int(time.time())

for i in range(10):
    xn1 = ((1103515245 * xn + 12345) % 32768) / 32768.00
    print(xn1)
    xn = xn1

Los dos decimales .00 añadidos a c son un «truco» para que Python imprima el resultado xn con decimales: le estamos diciendo al intérprete que queremos un float como resultado de la división. Este es uno de los resultados que da su ejecución:

0.654296875
0.87919062376
0.538866591363
0.578234577039
0.358640995601
0.190647192963
0.728419539036
0.0794397516329
0.638488339469
0.501262168

La operación módulo en teoría de números y cómo la implementan diferentes lenguajes

En informática, la operación módulo, dados dos números, D el dividendo y d el divisor, nos da el resto r de la división entera de D por d, siendo d≠0 y |r|<|d|. Aunque no parece gran cosa, aun menos teniendo en cuenta que hace décadas que las CPUs incorporan coprocesadores matemáticos capaces de hacer a gran velocidad operaciones aparentemente más relevantes como raíces o logaritmos, la realidad es que es una operación fundamental en informática: Desde la generación de tablas de hash y números aleatorios hasta la criptografía, la generación de checksums y el álgebra computacional.

Veamos como Python resuelve esta operación. Abrimos la consola de Python y mediante el operador % le pedimos el módulo con D=27 y d=13:

>>> 27%13
 1

Así es: 27 = 13 * 2 + 1

Lo mismo nos devuelve PHP:

echo 27%13;
1

Nada nuevo bajo el sol, matemáticas básicas. Probemos esto ahora:

>>> -27%13
12

Así es: -27 = 13 * (-3) + 12

Cambiando los signos de D y d:

>>> 27%-13
-12

¡¿Comorll?!?

El resultado esperado es 1:

27 = -13 * (-2) + 1

¿Por qué da -12? ¿Y PHP qué opina de todo esto?

echo 27%-13;
1

Buen chico. ¿Será que un lenguaje tan usado y prestigioso como Python no sabe dividir? ¿Por qué entonces lo escogen en tantas facultades de todo el mundo para la enseñanza? La NASA también lo usa, ¿han escogido un lenguaje que no sabe ni calcular el resto de una división entera?

Siguiendo con PHP:

echo -27%13;
-1

Habíamos visto antes que el resultado era 12 ¿PHP anda también perdido? La definición de la Wikipedia tampoco ayuda a esclarecer que está pasando. En mi opinión, esa definición es inexacta pues dice que la operación módulo calcula el resto de la división euclídea y en la división euclídea se impone la condición r ≥ 0 Cuando no se impone esa condición, y no lo hice en la definición de la operación módulo que di al iniciar esta entrada, las divisiones tendrán dos cocientes y dos residuos posibles: por defecto y por exceso. Mientras que con r ≥ 0 sólo habrá un resultado posible. Si hay un cociente q habrá otro cociente q’ cuyo valor será q + 1 y cada cociente tendrá su respectivo residuo r y r’ Con D=-27 y d=13 tendremos q=-3 y r=12 por un lado y por otro q=-2 y r=-1

-27 = 13 * (-3) + 12

-27 = 13 * (-2) + (-1)

Por lo tanto ambos lenguajes están calculando correctamente. En teoría de números siempre se escoge r ≥ 0 y algunos lenguajes, como Pascal, Scheme o Stata así lo hacen también, para estos lenguajes sí aplica la definición de la Wikipedia, pero la mayoría y los más usados van a escoger la división por exceso o por defecto. Algunos, como PHP, C o C++ escogerán siempre para el resto el signo del dividendo D mientras que otros como Python o Mathematica el del divisor d. Aparentemente para conseguir esta igualdad de signo, usarán la división por exceso o por defecto según sea necesario, aunque lo que realmente hacen es una operación más rápida. Los que usan el mismo signo que el dividendo van realmente rápido, truncan la división:

r = D – d * truncar(D / d)

La función truncar simplemente extermina todos los decimales, o dicho más fino: se redondea al número entero inmediato más cercano a 0. Esto es lo que hace PHP o C:

-1 = -27 – [13*truncar(-27 / 13)] = -27 – [13*truncar(-2.07…)] = -27 – [13*(-2)] = -27 – (-26)

Por otro lado, los que usan el signo del divisor d, usan la función floor (suelo). Esta función proporciona el número entero más pequeño inmediato o igual al número que se le pasa. De manera que por ejemplo Π quedaría en 3 y -Π en -4. Está función se expresa mediante ⌊⌋: floor(x) = ⌊x⌋

r = D – d * ⌊D / d⌋

Esto es lo que Python hace:

12 = -27 – 13[⌊-27 / 13⌋] = -27 – 13[⌊-2.07…⌋] = -27 -13[-3] = -27 + 39

Con la primera extrañeza que nos encontramos, cuando pusimos un divisor negativo, ahora sabemos qué hace Python:

-12 = 27 – (-13)*[⌊27 / -13⌋] = 27 – (-13)⌊-2.07…⌋ = 27 – (-13)*(-3) = 27 – 39

Lenguajes respetuosos con la teoría, como Pascal, hacen esto:

Si d > 0 => q = ⌊D / d⌋

Si d < 0 => q = ⌈D / d⌉

Es decir, si el divisor es negativo usan la función ceiling (techo) Dicha función da el número entero más grande inmediato o igual al número que se le pasa. De manera que Π quedaría en 4 y -Π en -3. Está función se expresa mediante ⌈⌉: ceiling(x) =⌈x⌉

Hay que tener en cuenta que no es esto lo que hacen los lenguajes que cogen el signo del divisor, es decir, no es lo mismo ⌊x⌋ que truncar(), no en el caso de números negativos. Volviendo al ejemplo D = 27 y d = -13 que en Python dio r = -12 mientras que PHP r = 1:

-12 ≠ 27 – (-13*⌈27 / -13⌉) = 27 – (-13*(-2)) = 27 – 26 = 1

Es lo que nos devolvió PHP, porque para números negativos truncar(x) equivale a ⌈x⌉ Para los positivos, en cambio, truncar(x) equivale a ⌊x⌋, por eso para D y d positivos todo lenguaje da el mismo r. Las diferencias surgen con los negativos. Veamos el caso en que ambos son negativos, D = -27 y d = -13. PHP usa truncar(), que en este caso sí equivale a ⌈⌉ :

-27 – (-13* truncar(-27 / -13) = -27 – (-13*truncar(2.07)) = -27 – (-13*2) = -27 + 26 = -1

>>> -27%-13
-1
echo -27%-13;
-1

Mientras que ⌊⌋, que ningún lenguaje la usa, daría:

-27 – (-13*⌊-27 / -13⌋) = -27 – (-13*(⌊2.07⌋) = -27 – (-13)*3 = -27 + 39 = 12

Como q = (D – r) / d Acaba resultando una ecuación sin solución entera:

(-27 – 12) / -13

Por lo tanto r ≠ 12

En la definición de división entera que di al principio introduje una «trampa» para que los resultados de PHP, Python o C fueran correctos: añadí la condición |r|<|d| En teoría de números, la división entera se define sólo para el conjunto de los naturales y la única condición es d ≠ 0 En cambio, para el conjunto de los números enteros (que incluye los naturales más los negativos), se usa la división euclídea, la cual añade la condición r ≥ 0 con el objetivo de obtener unos q y r únicos.

En mi opinión, la razón principal por la que algunos lenguajes usan la división entera también para números negativos es obtener un conjunto de r más amplio. Sin la condición r ≥ 0 se obtienen también r negativos. Con ello, por ejemplo, se consigue reducir el número de colisiones en una tabla de hash. Secundariamente, porque es más rápido el cálculo: truncar es más rápido que redondear. Sacrifican purismo matemático por fines prácticos. Además, el programador puede seguir obteniendo el resto de la división euclídea por otras vías. Puede programar su propia función con ceil() y floor(), o con floor() y truncate() si viene de microsegundos. También es más que probable que el lenguaje tenga una función para obtener dicho resto. Por ejemplo C tiene la función fmod en la librería math.h

Más Modelo y menos Controlador en el patrón MVC

He tenido ocasión de acceder al código de algunas aplicaciones para su desarrollo y veo un patrón que se repite con frecuencia y que demuestra que el desarrollador no está entendiendo el patrón de diseño de software Modelo Vista Controlador (MVC). Veo modelos pequeños que, a parte de la validación de los datos, poca más lógica contienen. Por otro lado y como no podía ser de otro modo, unos controladores gigantes para compensar los raquíticos modelos.

En el fondo una página web es tan solo un interfaz a la base de datos. Siendo aun más generalista: es tan solo un interfaz a un origen de datos (datasource). Ese origen de datos podría un servicio web SOAP, la API Rest de Twitter o cualquier otro, póngale imaginación. Si creamos ese interfaz, esa web, es por razones como que el usuario medio no tiene porque saber SQL ni mucho menos conocer la estructura de la base de datos, porque un XML de medio megabyte no nos resulta muy agradable a los humanos, etc. Siendo aun más generalistas podríamos decir que la inmensa mayoría de las aplicaciones, web o no, son «tan solo» eso. Por lo tanto, es la base de datos lo más importante y siendo los modelos los encargados de interactuar con ella, tienen un peso fundamental en una aplicación que pretende seguir el patrón MVC. Tema para otro artículo es como frecuentemente las bases de datos están mal diseñadas, saltándose a la torera las Formas Normales y no por optimizaciones en sitios con mucho tránsito. Esta alegría para diseñar el modelo de la base de datos la he llegado a ver incluso en personas que han recibido formación en la ingeniería de software.

Para poder dar un ejemplo de infrautilización de los modelos imaginemos una aplicación donde los usuarios, al crear o actualizar su perfil, opcionalmente pueden incluir una imagen a modo de avatar. Es obvio que es en el modelo donde deberemos validar si el fichero no excede un tamaño máximo y si es del tipo esperado: una imagen. Lo que no es tan obvio es que en el modelo también debe ir toda la lógica para tratar posibles errores manejando el fichero en el servidor. Tendremos que mover el fichero desde su ubicación temporal a la definitiva y talvez tengamos que realizar operaciones como cambiarle el nombre o crear un directorio donde alojarlo y lo que no es tan obvio es que esas operaciones también deben hacerse en el modelo evitando la tentación de sobrecargar el controlador. Si el campo «avatar», donde guardamos el nombre del fichero, no es obligatorio en la tabla, posiblemente primero guardaremos el nuevo usuario, luego realizaremos las operaciones con el fichero y si es felizmente renombrado y está en su ubicación actualizaremos la tabla con el nuevo nombre del avatar, de lo contrario informaremos al usuario de que si bien se pudo guardar su registro se produjo un error interno y no se pudo guardar la imagen que envió (por ejemplo haciendo saltar una regla de validación que no impida la inserción o actualización del usuario) En el controlador sólo haría esto o poco más:

if ($this->request->is('post')) {
    $this->User->create();
    if ($this->User->save($this->request->data)) {
        $this->Session->setFlash(__('The user has been saved'));
        $this->redirect(array('action' => 'index'));
    } else {
        $this->Session->setFlash(__('The user could not be saved. Please, try again.'));
    }
}

Este ejemplo se puede generalizar a cualquier acceso a la base de datos para crear o actualizar un registro que dependa de otro factor ajeno a la operación. Otro caso típico es al realizar complejas búsquedas en la base de datos, toda la lógica debe estar en el modelo y desde el controlador llamar a la función del modelo, si por complejidad es necesario dicha función puede estar apoyada por otras funciones «protected» o «privated» del modelo.

Toda acción CRUD (Create, Read, Update and Delete) así como otras operaciones dependientes deben estar en el modelo. Si es nuev@ en el patrón MVC, antes de poner algo en el controlador piense bien si es el lugar más adecuado. Seguir la normal general de mantener los controladores pequeños y los modelos preponderantes le ayudará a desarrollar unas aplicaciones más fáciles de mantener y modificar.

– Editado el 10/03/2012 –

Lo que aquí he expuesto no sólo aplica al MVC, no sólo al desarrollo web sino a todo el desarrollo de software, es uno de los principios básicos de la ingeniería de software. Los datos y su estructura dominan, si no están bien toda lógica que opere sobre esos datos va a ser innecesariamente más compleja. Incluso aparece listado en las reglas de la «filosofía Unix«, según Eric S. Raymond. Aunque estas normas van más allá de Unix y aplican para el desarrollo en cualquier plataforma.

No es recursivo todo lo que parece.

En la entrada anterior hablé sobre la recursividad mediante Scheme y la función de Ackermann. Hay algo curioso, o al menos a mi me sorprende, sobre Scheme y es como interpreta como iterativos algoritmos aparentemente recursivos. Como ejemplo 2 algoritmos para calcular los números de Fibonacci, uno recursivo y el otro iterativo aunque parezca recursivo. Primero recordar que estos números de definen así:

0 Si n = 0

1 Si n = 1

Fib(n – 1) + Fib(n – 2) Si n ≠ 0 y n ≠ 1

Esta definición lleva directamente a este algoritmo recursivo en Scheme:

(define (fib n)
    (cond ((= n 0) 0)
    ((= n 1) 1)
    (else (+ (fib (- n 1))
        (fib (- n 2))))))

Funciona pero es poco eficiente, la complejidad aumenta exponencialmente a medida que el número que buscamos, n, es mayor, pues se trata de recursividad en árbol. Este otro algoritmo es mucho más eficiente:

(define (fib n)
    (fib-iter 1 0 n))

(define (fib-iter a b count)
    (if (= count 0)
    b
    (fib-iter (+ a b) a (- count 1))))

Si queremos saber el Fibonacci para 4 lo invocamos así:

(fib 4)

Y hará:

(fib 4)

(fib-iter 1 0 4)

(fib-iter 1 1 3)

(fib-iter 2 1 2)

(fib-iter 3 2 1)

(fib-iter 5 3 0)

3

Scheme lo ejecuta como iterativo, no como recursivo. ¿Pero que sucede si implementamos ese mismo algoritmo en un lenguaje tipo procedimental como C o Pascal? Veamos como podría ser en PHP, el rey de la web:

function fib ($a, $b, $aCalc) {

    if ($aCalc == 0) {
        return $b;
    }else{
        $aCalc--;
        fib($a + $b, $a, $aCalc);
    }
}

$result = fib (1, 0, 4);
echo $result;

Y no funcionará. ¿Por qué? Pues porque PHP lo interpretará como recursivo, no como iterativo, y hará:

(fib 1 0 4)

(fib 1 0 4)(fib 1 1 3)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 1)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 1)(fib 5 3 0)

Pero en vez de quedarse aquí empezará a hacer los «returns», los «pops» de la pila:

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 0)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 1)

(fib 1 0 4)(fib 1 1 2)

(fib 1 0 3)

:-/

Entonces, ¿como hacer «entender» al compilador o intérprete en este tipo de lenguajes que deseamos una implementación iterativa? La única opción es hacer servir las instrucciones que disponen para bucles: while, for, repeat, etc. Este podría ser un ejemplo en PHP:

function fibonacci($n) {
    $f[0] = 0;
    $f[1] = 1;

    for ($i = 2; $i <= $n; $i++) {
        $f[$i] = $f[$i-1] + $f[$i-2];
    }

    echo $f[$n];
}
fibonacci(8);

Ésta curiosidad se puede expresar también a la inversa: Scheme interpreta como iterativos algoritmos que a quienes estamos acostumbrados a los lenguajes por preocedimientos (procedural languages) nos parecen iterativos. Probablemente ésta es mejor forma de expresarlo.

La función de Ackermann

Llevo un par de meses bastante entretenido con el libro del MIT «Structure and Interpretation of Computer Programs». Si bien el MIT nos permite el acceso gratuitamente a todo su contenido aquí, es un libro genial que realmente vale la pena comprárselo.

En uno de sus primeros capítulos, donde se contrastan los procesos iterativos con los recursivos y como aquel que no quiere la cosa, en un ejercicio aparentemente inocente aparece un procedimiento que computa una variante de la función matemática de Ackermann:

(define (A x y)
    (cond ((= y 0) 0)
    ((= x 0) (* 2 y))
    ((= y 1) 2)
    (else (A (- x 1)
        (A x (- y 1))))))

Dicha función es famosa en teoría de la computación. Lo que sorprende de dicha función, a diferencia de las que habitualmente se usan como función «modelo» para enseñar qué es la recursividad, es que no es recursiva primitiva. El ejemplo típico de la función recursiva es la que nos da el factorial de un número n:

(define (factorial n)
    (if (= n 1)
    1
    (* n (factorial (- n 1)))))

El proceso que seguiría para calcular por ejemplo el factorial de 6 sería:

factorial(6)

6 * factorial(5)

6 * (5 * factorial(4))

6 * (5 * (4 * factorial(3)))

6 * (5 * (4 * (3 * factorial(2))))

6 * (5 * (4 * (3 * (2 * factorial(1)))))

Este es el punto en que más se carga la pila, a partir de aquí serían «pops»:

6 * (5 * (4 * (3 * (2 * 1))))

6 * (5 * (4 * (3 * 2)))

6 * (5 * (4 * 6))

6 * (5 * (24))

6 * (120)

720

Las funciones recursivas «típicas» siguen éste patrón, se van sumergiendo hasta llegar a un punto de inflexión a partir del cual van emergiendo hasta aflorar el resultado final. La función de Ackermann podría parecer que transcurre igual, por ejemplo (A 1 6) sería:

(A 1 6)

(A 0 (A 1 5))

(A 0 (A 0 (A 1 4)))

(A 0 (A 0 (A 0 (A 1 3))))

(A 0 (A 0 (A 0 (A 0 (A 1 2)))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))

(A 0 (A 0 (A 0 (A 0 (A 0 2)))))

(A 0 (A 0 (A 0 (A 0 4))))

(A 0 (A 0 (A 0 8)))

(A 0 (A 0 16))

(A 0  32)

64

Es decir, 26 De hecho, para todo (A 1 n) el resultado siempre será 2n Pero veamos por ejemplo como transcurre al calcular (A 2 4):

(A 2 4)

(A 1 (A 2 3))

(A 1 (A 1 (A 2 2)))

(A 1 (A 1 (A 1 (A 2 1))))

(A 1 (A 1 (A 1 2)))

(A 1 (A 1 (A 0 (A 1 1))))

(A 1 (A 1 (A 0 2)))

(A 1 (A 1 4))

(A 1 (A 0 (A 1 3)))

Como se puede observar, se va profundizando para después emerger y a continuación volver a sumergirse. Después de un largo proceso recursivo, el resultado final que acaba dando es 65536, es decir, 216.