Blog Archive

Thursday, April 16, 2015

La Catedral y el Bazar: Cómo mantener estructuras de datos inteligentes y liberar rápido y a menudo, escuchando a los clientes.




ABSTRACT

En el ensayo a favor del software de código abierto, “La Catedral y el Bazar”, aparece la idea “Estructuras inteligentes y código tonto funcionan mejor que el caso contrario”, la que parece contraponerse a la afirmación del mismo texto: “Libere rápido y a menudo, y escuche a sus clientes”, pues el cliente/colaborador, con el desarrollo presto en mente, privilegia el código por sobre la estructura del sistema; a lo sumo tendrá una idea particular de estructuras para resolver el problema que trata de solucionar. Se proponen dos ideas que dan explicación a la coexistencia de estas dos afirmaciones: (1) cimientos para la construcción de una catedral y (2) gestión de intereses colectivos. Los cimientos entregan una forma de idear un producto antes comenzar a liberar, propone una etapa previa basada en el pensamiento y refinamiento de ideas a crear antes de comenzar con el desarrollo colectivo. Por otro lado, gestión, expone la ventaja de lograr se entienda de tal manera el sistema, que todos tengan una visión compartida de la estructura del mismo. Para ello se exponen varios ejemplos de sistemas catedral y sistemas bazar, contrastando las prestaciones y los objetivos de los productos que se heredan directamente de los modelos de desarrollo. Este paper presenta la descripción de una forma mixta de desarrollo, sus propiedades teóricas y la defensa férrea a la atención que se debe tener en las estructuras, sus relaciones y los algoritmos.

PALABRAS CLAVE

La Catedral y el Bazar, Ingeniería en Software, Algoritmos y Estructuras de datos, Código abierto, Linux, Programación Ágil, Manifiesto Ágil, Linus Torvalds, Eric Raymond, Fectchmail.

1. INTRODUCCION

Actualmente muchas empresas están moviendo sus métodos del tipo ‘catedral’ al tipo ‘bazar’, esto generado por el movimiento pro Manifiesto Ágil, que aparece como una luz que salvará de los problemas de la gestión informática a los grupos y empresas de desarrollo.
Existe una infinidad de libros de programación, de los cuales, en un ranking, 7 de cada 10 de los mejor calificados por la opinión experta se basan en el desarrollo ágil, demonizando estrategias largamente usadas, como el método ‘cascada’ por ejemplo.
Sin embargo no todo lo que brilla es oro, podría ser que en la euforia de la innovación y de estar a la vanguardia, ser conservador se criminalice sin las consideraciones pertinentes, como por ejemplo: poner en valor las capacidades del diseño de las estructuras previo a la escritura de los programas.
Este documento es una reflexión acerca de las capacidades que entrega lo nuevo en programación sin descuidar lo rescatable de los métodos mal llamados obsoletos por evangelizadores del nuevo mundo digital en términos de desarrollo.
La solución podría encontrarse tanto en un punto intermedio o en una nueva metodología que no ha sido ideada aún, como podría ser que en este caso tampoco exista la anhelada bala de plata.

2. INVESTIGACION

En la cuarta edición del libro Algorithms (Sedgewick & Wayne, 2011) se afirma que:

El estudio de algoritmos y estructuras de datos es fundamental en cualquier programa de estudios de ciencias en computación, pero no es solo para programadores y estudiantes de informática. Todo aquel que usa un computador quiere que corra mas rápido o que resuelva problemas más grandes.

El interés por obtener mas de lo que entrega un sistema es un interés generalizado y no responde solo a una inquietud de individuos relacionados con el ámbito de la tecnología y la computación. Es así como entenderemos que muchas veces los clientes/colaboradores que tendremos en un desarrollo, como el expuesto por el autor de ‘La Catedral y el Bazar’ (Raymond, 2001) para su software finalmente llamado ‘Fetchmail’, no serán necesariamente programadores, lo que por un lado puede ser una ventaja verificable, en cuanto no solo habrán muchos ojos mirando el software sino, también, ojos con espectros de visión distintos; es así como un ingeniero especialista en botánica podría dar solución a un software pensado para el control hidráulico gracias a sus extensivos conocimientos de recursos biológicos que resuelven problemas con funciones y procedimientos desconocidos para los expertos en hidráulica. Por otro lado, esos ojos, al ser ajenos a las ciencias de la computación tendrán más conocimiento de ‘coding’ que de ‘data structures’ por lo que trataran de dar con el código que remedia la enfermedad y no con la razón por la cual se enferma para evitar que se vuelva a caer en el infortunio.
La idea anterior se ve reforzada por Clifford Shaffer (2012) quien escribe:

Crear programas eficientes tiene poco que ver con ‘trucos de programación’, por el contrario, se basan en una buena organización de la información y buenos algoritmos. Un programador que no ha dominado los principios básicos de la limpieza del diseño, no será propenso a escribir programas eficientes.

De la cita se desprende que no realizar la tarea previa a la escritura de programas, establecer diagramas, tablas y relaciones que describan y organicen el abstracto conceptual de cualquier problema, es seguro que el programa no será eficiente. Es imperioso dominar los principios de la programación, ya lo dice Linus Torvalds:

Los malos programadores se preocupan del código. Los buenos programadores se preocupan de la estructura de datos y sus relaciones.

Debemos entender de esto que si tenemos estructuras de datos bien construidas será muy fácil de programar, mientras que, por muy bueno que sea un código, jamás se podrá remediar una estructura de datos mal construida.
Publicar rápido y a menudo es el núcleo de la filosofía del desarrollo ágil de software. Afirma que permite una retroalimentación entre cliente/colaborador y equipo de desarrollo y asigna una importancia significativa a la comunicación. Para que este desarrollo exista es necesario que se cumplan algunos requisitos que se encuentran en los doce principio del manifiesto ágil, por ejemplo: programadores motivados, posibilidad de interactuar cara a cara con el cliente, grupos auto-organizados y posibilidad de agregar cambios de último minuto a los proyecto en desarrollo. Hay muy poco que objetar de los doce mandamientos y muchos autores adheridos a esta metodología centran los desafíos del desarrollo en la complejidad que representan las relaciones humanas, como lo indica Alistair Cockburn (2006):

En los resultados de un proyecto, las tecnologías y los procesos causan efectos de secundarios. Los principales efectos los causan las personas […] Las personas no son unidades programables desconectables.

Los procesos, secuencias y practicas son importantes, pero son las personas las que lo hacen funcionar; si queremos que los proyectos lleguen a puerto es necesario que construyamos equipos de trabajo colaborativos y auto-organizados. Llevando a cabo el precepto de entregar rápido y a menudo, puede sacar a empresas y grupos de desarrollo de su lenta productividad, salvándolos del gran problema del método catedral: entregar un producto final obsoleto. Sin embargo el desarrollo ágil lleva inherente el problema del código ‘quick and dirty’ (rápido y sucio), donde la suciedad es más dada a quedarse en el código y la rapidez a ser olvidada en el instante siguiente de la entrega. Si alguno de los principios del manifiesto no se cumple, lo que es muy probable que suceda (en migraciones de ‘waterfall’ a ‘XP’ por ejemplo), según Tom Dabson, la programación ágil te puede llevar a que:

  • La arquitectura y el código puedan ser un desastre.
  • Sea difícil lograr la perfección.
  • Aparezcan Zealots, evangelizadores de la biblia de la programación ágil y sus principios.
  • Programación pareada, si se está en una transición puede que no muchos de los programadores estén preparados para ser corregidos en ‘real time’.

Existe una regla simple, post-ágil, que aparece como una respuesta a los enceguecidos por los principios de la metodología que dice:

Si funciona, hazlo. Si no funciona, no lo hagas.

3. IDEAS DEL AUTOR

“Cuando una rosa deja de serlo”; al analizar el desarrollo de Linus Torvalds con el proyecto Linux y su exito, Eric Raymond intenta testear las conclusiones en su propio proyecto, ‘popclient’. Tras una limpieza de código notó en la implementación de Carl Harris dos razones para reescribirlo:

“[Harris] trataba el código como la parte más importante y las estructuras de datos como un mero apoyo. Como resultado, el código era magnifico, pero las estructuras de datos se habían diseñado con descuido y resultaban bastante espantosas.”(1)
“Conducirlo a algo nuevo que yo [Raymond] entendiera por completo. No es divertido ser el responsable de la depuración de un programa que no comprendes.”(2)

Reconoce en estas afirmaciones la importancia del diseño por sobre el código y además resalta la complejidad que significa tratar con códigos que no son ‘propios’. El completo entendimiento de un código no es necesario para encontrar errores, pero si lo es para depurarlo de forma rápida.
“Lánzalo pronto, lánzalo a menudo”; por otro lado confiesa que, hasta antes de conocer la política de desarrollo abierto de Linus, creía que era perjudicial para el desarrollo de proyectos los lanzamientos tempranos y frecuentes porque no parecía correcto agotar la paciencia de los usuarios. La diferencia radicó principalmente en tratar a los usuarios como colaboradores y una perfecta coordinación y gestión de los mismos a través de Internet, logrado gracias a un sistema de recompensas constante:

“Linus estaba manteniendo a sus colaboradores/usuarios en un continuo estímulo y una recompensa constante – estimulados por la perspectiva de tener un trozo de la acción a su disposición para satisfacer su ego, y recompensados por la visión de una mejora continua (incluso diaria) de su trabajo.”

En la cita podemos ver que, según Eric, Linus gracias a su genio logró generar por lo menos dos de las condiciones necesarias para el desarrollo ágil: programadores motivados (con los estímulos correctos), posibilidad de interactuar cara a cara con el cliente (perfecta gestión por Internet).

4. PROPUESTA

Se hace claro al leer la investigación que el solo hecho de realizar entregas rápidas y frecuentes no es suficiente para que el desarrollo sea realmente ágil, por el contrario, seguir al pie de la letra los principios del manifiesto podría resultar incluso en el retraso o el descarte de ideas o propuestas que hubiesen concluido la realización de un programa o de un proceso.
Se observa que la mayoría de los grandes programadores concuerdan en la importancia de los algoritmos, las estructuras de datos y sus relaciones, sin olvidar que las personas y sus interacciones son las que van a llevar a cabo el trabajo.
Es correcto destacar la importancia de no olvidar métodos considerados obsoletos solo por la explosiva popularidad de los nuevos; rescato del método cascada el tiempo disponible destinado a la investigación previa a la programación, el tiempo destinado a la arquitectura, el tiempo destinado a la programación, en resumen, el tiempo.
Para que el desarrollo sea realmente ágil no basta con programar como un caballo de feria (bazar), pero se podría programar a ojos cerrados si se tiene clara una estructura adaptable en la que se basen todos los ‘codings’.
La contradicción existente entre las dos afirmaciones del documento de Raymond se soluciona construyendo los cimientos de la catedral para albergar el bazar. Lo que Raymond no acentúa en su ensayo es que Torvalds se dedicó, casi a tiempo completo, a desarrollar los cimientos de la catedral, mientras que sus clientes/colaboradores fueron los que establecieron el bazar auto-organizado del que proliferaron variadas distribuciones, las cuales cada vez que se encontraban con un nuevo problema (necesidad de versiones para escritorios, escuelas, universidades, etc.) podían regresar al bazar, limpiarlo y partir un nuevo bazar desde cimientos cada vez más robustos de la catedral de Linus. En ello radica el éxito de la metodología utilizada para el nacimiento de Linux.
No se puede tener un código limpio, simple y comprensible si deben resolver estructuras complejas, sucias e incomprensibles. El requisito fundamental tras las conversaciones iniciales con los clientes/colaboradores es extraer solo la estructura elemental, lo suficientemente limpia como para que no solucione el problema propuesto, sino que solo sirva de mesón y de almacenamiento de herramientas, un taller especializado para comenzar a realizar la obra. Un pintor antes de pintar busca un lugar cómodo, una idea central, un lienzo y un grafito para comenzar a trazar (esa es la estructura), luego su imaginación le solicita herramientas como colores, pinceles, cola fría, etc., las cuales pueden ir variando según sea necesario (estas son las peticiones del cliente/colaborador). Si ponemos el caso de un retrato, el desarrollo meramente ‘bazar’ sería conversar en un restaurante con el cliente y entregarle inicialmente una servilleta con la obra dibujada con lápiz pasta en ella, la que obviamente será desechada, luego al llegar a casa enviarle una foto por ‘WhatsApp’ con un dibujo hecho en la boleta de la cuenta de mientras viajabas en metro, al día siguiente enviarle un correo con las pinturas, pinceles y lienzos que se compraron en la ‘Librería Nacional’, al día siguiente enviarle por correo un bosquejo realizado en una hoja de cuaderno, etc., imaginando ahora que no será solo uno el que dibuje, la tarea de organizar las obras y sus lineamientos ha creado más desechables que entregables. Por otro lado si fuera completamente ‘catedral’, sería programar una agenda de reuniones donde se recaudarían retratos que el cliente admira, fotos donde se siente a gusto, obras de pintores favoritos, etc., luego se acordarían reuniones donde se iría a la ‘Librería Nacional’ para que el cliente elija los colores y el tamaño del lienzo y el artista los pinceles que crea necesarios para realizar la obra, finalmente realizaría el curado diario de la obra para no perder ningún detalle acordado, lo que le tomaría un tiempo tal que el rostro del cliente ya ha cambiado, por lo que la obra es una gran ‘Mona Lisa’, quizás en algunos años más alguien se interese en ella y la ponga en valor como la gran obra que es, pero en un museo.
La propuesta mixta sería tomarse el tiempo necesario para generar un taller con varias iluminaciones distintas (luces amarillas, blancas, etc.), amplio (para agregar más de un lienzo, más de un artista, más de un cliente, etc.), en el que tanto el artista como el cliente/colaborador estén a gusto, un lienzo pequeño al que le podamos adherir otros si la obra quiere crecer, con una paleta grande para probar colores junto con el cliente y un estante para almacenar colores y pinceles. Con esto construido puedo a diario invitar al cliente revisar todos los avances que se vayan realizando a modo de entregas prontas y frecuentes, incluso puedo invitar a más artistas a participar, quienes en un ambiente adecuado colaborarán más a gusto y lograrán finalizarlo correctamente en poco tiempo (a partir desde que se tiene el taller armado) y con un alto grado de satisfacción del cliente.

5. CONCLUSION

Más que fijarnos en las diferencias que aparecen en los distintos modelos de desarrollo es menester rescatar las mejores cualidades y combinarlas para generar un poderoso grupo de colaboradores que a la vez sean clientes del modelo, y sean motivados por la claridad con que sus códigos avanzan para alcanzar objetivos más que por otros estímulos compensatorios.
Las experiencias que muchos autores comparten son un legado que debemos absorber como programadores para perfeccionar las técnicas y crear estrategias que nos permitan crecer como profesionales en cualquier modelo de desarrollo.

6. BIBLIOGRAFIA

Cockburn A. (1997) "The Methodology Space, Humans and Technology”. Reporte técnico HaT TR.97.03
http://members.aol.com/acockburn/papers/methyspace/methyspace.htm.

Dabson T. (2014). “Post-Agile: A Design Thinking Approach to Software Development”. Artículo web. Consultar en:
http://www.artefactgroup.com/content/post-agile-a-design-thinking-approach-to-software-development/

Raymond, E. (2001). “The Cathedral & the Bazaar: Musings on Linux and Open Source by an Accidental Revolutionary”. California, CA: O’Reilly Media.

Sedgewick R. & Wayne K. (2011). “Algorithms, 4th Edition”. Menlo Park, CA: Addison-Wesley.

Shaffer, C. (2012). “Data Structures and Algorithm Analysis”. Blacksburg, VA: Dover Publications.

Wednesday, September 3, 2014

RPN Calculator - Array Based Stack


When I was a student at University of Santiago of Chile, in my first year, teachers told me to buy a calculator that would help me to solve the problems faster.

So I bought this HP48 scientific calculator... it took me about an hour to understand how did it work!!... you have to put first the terms you want to operate and then choose an operation, in other words, if you want to add 1 and 2 (1 + 2) you need to put 1, then 2 and finally +.

A few months after I found out that this way of calculation had a name:
infix (fixed): regular algebraic notation ( a * b + d )
postfix (RPN): Reverse Polish Notation ( a b * d +)

Today I present you this java code to simulate the process of transforming infix to postfix using "array based stacks":

package rpn;
import javax.swing.JOptionPane;

//  Rational:
//      Data type: operand, operator, group
//      Operators order: ^ > [ * = / ] > [ + = - ]
//      Actions:
//          ): pops the last operator.
//          ^: pushes itself directly on (the stack).
//          *, /: pops bigger operators (if any), then pops one equal operator (if any), then pushes itself on.

//          +, -: pops bigger operators (if any), then pops one equal operator (if any), then pushes itself on. 
//          (: if there is no other it pushes itself on and protects the last operator; when a new operator appears, it just replaces the "(".
//      Opeands: non operator and group chars are considered operands and they all are pushed into the stack.


public class RPN {

    public static String read(String message) { return JOptionPane.showInputDialog(message); }
    public static void write(String message) { JOptionPane.showMessageDialog(null, message); }

    public static void main(String[] args)
    {
        char[] infix = read("Algebraic expresion: ").toCharArray();
        Stack operator = new Stack(infix.length);
        Stack postfix = new Stack(infix.length);
        for(char token : infix)
        {
            switch(token)
            {
                case ')':

                    if(!operator.isEmpty())
                        postfix.push(operator.pop());
                    break;
                case '^':

                    operator.push(token);
                    break;
                case '*':
                case '/':
                    if(!operator.isEmpty() && (operator.pick()=='('))

                    {
                        operator.pop();
                        operator.push(token);
                    }
                    else
                    {
                        while(!operator.isEmpty() && operator.pick()=='^')
                            postfix.push(operator.pop());
                        if(!operator.isEmpty() && (operator.pick()=='*' || operator.pick()=='/'))
                            postfix.push(operator.pop());
                        operator.push(token);
                    }
                    break;
                case '+':
                case '-':
                    if(!operator.isEmpty() && (operator.pick()=='('))
                    {
                        operator.pop();
                        operator.push(token);
                    }
                    else
                    {
                        while(! operator.isEmpty() && (operator.pick()=='^' || operator.pick()=='*' || operator.pick()=='/')) 
                            postfix.push(operator.pop());
                        if(!    operator.isEmpty() && (operator.pick()=='+' || operator.pick()=='-'))
                            postfix.push(operator.pop());
                        operator.push(token);
                    }
                    break;
                case '(':
                    if(!operator.isEmpty())
                        if(operator.pick()=='(')
                            break;
                        else
                            operator.push(token);
                    break;
                default:
                    postfix.push(token);
                    break;
            }
        }
        while(!operator.isEmpty())
            postfix.push(operator.pop());

// from here and on is just printing job
        Stack Invertedpostfix = new Stack(infix.length);
        while(!postfix.isEmpty())
            Invertedpostfix.push(postfix.pop());
        String rpnout = "";
        while(!Invertedpostfix.isEmpty())
            rpnout += Invertedpostfix.pop();
        write(rpnout);
    }
}


// This is the Array based stack class used

public class Stack {
    int top;
    char[] list;
    public Stack(int size){ list = new char[size]; top = -1; }
    public void push(char item){ top++; list[top] = item; }
    public char pop(){ top--; return list[top+1]; }
    public char pick() { return list[top]; }
    public boolean isEmpty(){ return -1 == top; }
}

Friday, May 2, 2014

Fibonacci Sequence - Very Long Number Adressing

http://jencropable.com/the-fibonacci-spiral/


I've always heard about sequences, the most famous is "the Fibonacci Sequence", and almost everyone've heard about the starting terms 0, 1, 1, 2, 3, 5, etc. Basically, the first term plus the second results in the third one, the second plus the third results in the fourth one, etc.

There is also a way to calculate any term based on the golden ratio:



If you want to know more about this sequence you can google it or visit this link:
http://en.wikipedia.org/wiki/Fibonacci_number

The problem is that if you want to know a very high term there is no way for a numeric type, on programming languages, to address it.

The solution to this problem is simple, if you want to know the term 1.000.000th first you have to estimate how many digits it has, to know the size of an array to store it, using the UInt64 type as a 19 digit handler (because it can not store the 20 digits number 99.999.999.999.999.999.999) you just need to split the number every 19 digits. 

So, for a 20 digits number you need a length 2 array (at least), to store 19 digits in the last position and 1 digit in the first position (keeping the order). The 1.000.000th term has 207.505 digits, so you should use a 10.922 length array.

Steps:




First: Use the "golden ratio based method" to instantly show the terms (for numbers below the 93rd term).
Second: Use a two* dimensional array to split the longer numbers using the regular method (adding the last 2 terms).

* : Two dimensions because you need to store two terms plus an auxiliar. You can also use three unidimesional arrays.

Why not List?
Array are way faster than Lists for calculations, around N to N^2 times for very long numbers.

What would this work for?
There is a lot of very useful applications, you can use it to implement a random number generator for example.

How does it work?
I use this method:

digits = term * 0.20898438
array length = ( digits / 19 ) + 1

so:

array length = 1 + term * 0.010999

So if you want to know the term 3.000.000th it should have no more than 626.955 digits, so you need a 32.998 length array (at least).

There should be a better, and more precise, way to get the number of digits, you should google it if you want to know, but I find this number by analizing the terms I got. 

Have fun and enjoy.
(This is a C# code) 

using System;
using System.Diagnostics;
namespace ConsoleApplication1
{
    class Program
    {
        static void GetFibonacci (int datoLeido)
        {
            int digitos = 0;
            int largo = (int)(1 + 0.010999 * datoLeido);
            Stopwatch sw = new Stopwatch();
            UInt64[,] fibonacci = new UInt64[largo , 3];
                if (datoLeido <= 93)
                {
                    fibonacci [0, 0] = (UInt64)(Math.Pow ((1 + Math.Sqrt (5)) / 2, datoLeido) / Math.Sqrt (5) - Math.Pow ((1 - Math.Sqrt (5)) / 2, datoLeido) / Math.Sqrt (5));
                    Console.WriteLine ("Term: " + fibonacci [0, 0]);
                    Console.WriteLine ("Press any key to continue...");
                    Console.ReadKey ();
                }
                else
                {
                    sw.Start ();
                    fibonacci [fibonacci.GetLength (0) - 1, 0] = (UInt64)(Math.Pow ((1 + Math.Sqrt (5)) / 2, 91) / Math.Sqrt (5) - Math.Pow ((1 - Math.Sqrt (5)) / 2, 91) / Math.Sqrt (5));
                    fibonacci [fibonacci.GetLength (0) - 1, 1] = (UInt64)(Math.Pow ((1 + Math.Sqrt (5)) / 2, 92) / Math.Sqrt (5) - Math.Pow ((1 - Math.Sqrt (5)) / 2, 92) / Math.Sqrt (5));
                    for (int j = 0; j <= datoLeido - 93; j++)
                    {
                        for (int i = fibonacci.GetLength (0) - 1; i >= 0; i--)
                        {
                            fibonacci [i, 2] = fibonacci [i, 1];
                            if (fibonacci [i, 1] == 0)
                                break;
                        }
                        for (int i = fibonacci.GetLength (0) - 1; i > 0; i--)
                        {
                            fibonacci [i, 1] += fibonacci [i, 0];
                            fibonacci [i - 1, 1] += fibonacci [i, 1] / 10000000000000000000;
                            fibonacci [i, 1] = fibonacci [i, 1] % 10000000000000000000;
                            if (fibonacci [i, 1] == 0)
                                break;
                        }
                        for (int i = fibonacci.GetLength (0) - 1; i >= 0; i--)
                        {
                            fibonacci [i, 0] = fibonacci [i, 2];
                            if (fibonacci [i, 2] == 0)
                                break;
                        }  
                    }
                    sw.Stop ();
                    Console.WriteLine ("Term: ");
                    for (int i = 0; i < fibonacci.GetLength (0); i++)
                    {
                        if (fibonacci [i, 1] != 0)
                        {
                            Console.Write (fibonacci [i, 1]);
                            digitos = digitos + fibonacci [i, 1].ToString ().Length;
                        }
                    }
                    Console.WriteLine ();
                    Console.WriteLine ("Digits: " + digitos);
                    Console.WriteLine ("Elapsed time: " + sw.Elapsed);
                    Console.Write ("Press a key to continue...");
                    Console.ReadKey ();
                }
        }

        static void Main(string[] args)
        {
            string datoLeido;
            int dl;
            do
            {  
                Console.Clear();
                Console.WriteLine ("Fibonacci Sequence");
                Console.WriteLine ("Enter the term you want to know? [X: Exit]");
                datoLeido = Console.ReadLine();
                if(int.TryParse(datoLeido, out dl))
                    GetFibonacci(dl);
                else
                    if(datoLeido.ToUpper()!="X")
                        Console.Write (" ¬¬ It should be an integer number...");
            }while(datoLeido.ToUpper()!="X");
        }
    }
}