Recordemos que los números de Fibonacci se definen como la secuencia de números que se construyen de la siguiente manera:

Fib(1) = 1

Fib(2) = 1

Fib(3) = 2

Fib(4) = 3

Fib(i) = Fib(i-1)+Fib(i-2)  (para i>= 3)

Es decir, cada número de fibonacci es la suma de los números previos de Fibonacci.

El ejercicio consiste en lo siguiente: construir un programa que reciba 2 números a y b, la salida del programa debe ser la cantidad de números de Fibonacci que hay entre a y b.

Por ejemplo, para los siguientes valores  a=1234567890 y  b=9876543210 el programa debe entregar el valor 4, porque hay sólo 4 números de fibonacci entre a y b.

En otras palabras, para los número a y b, se debe contar los números de Fibonacci Fi tales que a <= Fi <= b.

Tienen 2 semanas de plazo para resolver este desafío.

Sí, Excel, ese que usan muchos de tus colegas no informáticos, soporta perfectamente el paradigma funcional.

Primero en Excel tienes valores, números, o a veces textos, que colocas en celdas. Por ejemplo, puedes colocar en la celda A1 el valor 2, y en la celda A2 el valor 3.

Después tienes funciones, u operaciones que trabajan sobre valores que se encuentran en una celda, por ejemplo, puedes definir que el valor de la celda A3 se calcula como A3 = A1 * A2. Excel te mostrará el valor de aplicar esta operación a los valores disponibles en ese momento en las celdas A1 y A2, en nuestro caso se verá en A3 el número 6.

Definiendo el valor de una celda en función de otras dos

Lo “interesante” es que esta operación  no cambia el valor de las celdas que son usadas como argumentos. Esto quiere decir que en Excel no hay efectos laterales, el resultado de la función sólo afecta a aquellos que usen el resultado, pero no a los argumentos de entrada.

Veamos que pasa si agregamos otras ecuaciones a nuestra planilla, haciendo que unos valores dependan de resultados previos.

Por ejemplo: A4=A1+2, B3=A2*A2, B4=A1-A2, C3 = B3-B4, C4 = B3*B4.

Excel nos permte ver las dependencias de esta secuencia de cálculos:

Dependencias entre las celdas

Decimos que el orden de evaluación está dado por las dependencias de los datos.

Otra cosa interesante es que dados los mismos valores de entrada el resultado final no cambia, en nuestro caso, si A1 contiene el valor 1, y A2 contiene el valor 2, entonces la celda C4 siempre tendrá el valor -4, no hay sorpresas, el valor de la celda C4 depende sólo de los argumentos de entrada y la secuencia de cálculos intermedios.

Consideren la siguiente función en C:

int calc(int x, int y)
{
static int z = 0;
z = z + x * y;
return z;

}

Si invocamos esta función la primera vez con los valores 1 y 2, el resultado será 2, pero si lo invocamos por segunda vez, con los argumentos 2 y 3, el resultado será 8, si la invocamos por tercera vez, con los valores 1 y 2, ¡el resultado será 10!

Esto pasa porque C permite efectos laterales, en particular al declarar la variable z como static hace que ese valor se mantenga a lo largo de cada invocación a la función.

Los lenguajes de programación funcional prohiben esta opción, no pueden haber efectos laterales como estos, el resultado de la función solo debe ser el mismo para los mismos argumentos de entrada.

Ahora bien, excel, usada a este nivel, junto con algunas funciones pre definidas, opera como lenguaje funcional, pero no todo excel es funcional, por ejemplo, cuando se usan macros, o se crean funciones con lenguajes de extensión en VBA u otros lenguajes (como C#), podemos violar el paradigma funcional, que exige que no hayan “efectos laterales”, y todo se obtenga mediante el proceso de reducción y combinación.

Pero la mayor parte de los usuarios la usan a este nivel, y sin darse cuenta, programan usando el paradigma funcional.

Las propiedades más importantes de la programación funcional están disponibles en Excel a nivel básico. Lo demás, todo lo complicado, que asusta a tantos programadores, como los combinadores, la monadas, el currying,  las reducciones, el lambda cálculus, etc, son temas más avanzados, que a pesar de sus nombres intimidantes, y de la costumbre de la comunidad funcional de “hablar en difícil”, son temas perfectamente abordables por cualquier programador.

Pero si nunca te has animado a aprender la programación funcional, quizás es hora de que abras una planilla de cálculo y empieces a jugar con ella, verás que es muy iluminador.

Ejercicios:

• Calcula la sucesión de Fibonacci en Excel
• ¿Es posible crear funciones recursivas en Excel? (sin usar VB  o algún lenguaje de programación para “extender” excel).

Daniel Molina Wegener, @damowe, dmw

Daniel Molina dejó este mundo este lunes, de forma inexplicable, este joven brillante ya no estará con nosotros.

Daniel era un programador extraordinario, que nos regaló probablemente su último post, que salió publicado este domingo en este mismo sitio.

Qué es la programación funcional.

Daniel era brillante, y ganó desafíos, de hecho participaba activamente resolviendo algunos de los desafíos que planteamos.

Su trabajo en estos desafíos está en este repositorio GitHub, de hecho me he encargado de clonar ese repositorio en particular, ante la eventualidad de que desaparezca dada su partida.

En particular su trabajo en el desafío de Octubre es notable, a pesar de que el problema tenía una solución sencila, y pretendía medir otra cosa, él fue más allá, esta imagen muestra el análisis que estaba haciendo para parsear programas en Fortran IV, este grafo se genera a partir de su analizador del código recibido en la entrada:

No sólo hemos perdido a una gran mente, a un gran programador y hacker, también a una buena persona, por lo poco que pude conocerlo, y por el testimonio de los que lo conocieron.

Humildemente, este espacio mantendrá su nombre, los desafíos volverán, y una vez al año entregaremos el premio Daniel Molina Wegener al mejor competidor, si me ayudan podemos hacer algo muy bonito y conmemorativo por él. Veré la manera de conseguir un premio adecuado que honre su memoria. Ustedes pueden honrarlo participando o promoviendo la participación entre sus amigos programadores o hackers. Estoy seguro que el sonreiría feliz con la idea.

En los lenguajes funcionales las instrucciones cíclicas como for, while y do-while no existen. Todo se procesa usando recursividad y funciones de alto orden. Esto se debe a los fundamentos matemáticos de la mayoría de los lenguajes funcionales, principalmente con bases en el sistema formal diseñado por Alonzo Church para definir cómputos y estudiar las aplicaciones de las funciones llamado Cálculo Lambda. En este sistema formal se puede expresar recursividad en las funciones, y entre otras cosas interesantes, se pueden expresar combinadores — funciones sin variables libres — como el Combinador de Punto Fijo o Y-Combinator, que expresa recursividad sin hacer llamadas recursivas. En el Cálculo Lambda existen tres transformaciones esenciales, la conversión α, la reducción β y la conversión η. En la conversión α se sustituyen los nombres de las variables para dar mas claridad a la aplicación de las funciones, por ejemplo evitando duplicados en sus nombres. En la reducción β se traza el llamado de las funciones sustituyendo las funciones por sus expresiones resultantes. Finalmente en las conversiones η se busca las equivalencias de trazado de funciones sustituyéndolas por sus equivalentes. Estas transformaciones también pueden ser aplicadas en los lenguajes funcionales — o en su mayoría — dando lugar lenguajes que cuentan con una gran expresividad y consistencia.

Les pondré el clásico ejemplo del chiste geek del castigo “Debo poner atención en clases”. La respuesta geek expresada en PHP esta escrita a continuación. Donde PHP es un lenguaje dinámico, no necesita declarar variables y es un lenguaje orientado a objetos con raíces imperativas. Sus instrucciones son paso a paso, y no constituyen una única expresión reducible.

<?php

    /* codigo PHP */
    for ($i = 0; $i < 500; $i++) {
        echo "Debo poner atencion en clases";
    }

 ?>

Si usamos Haskell como ejemplo, que es un lenguaje funcional con tipificación estática fuerte, requiere que las variables sean declaradas con un tipo — la mayoría de las veces — y es muy expresivo, donde el siguiente ejemplo dice repetir la cadena, tomar 500 elementos y con esa lista ejecutar la función monádica putStrLn, que esta hecha para el Monad IO e imprime la el mensaje las 500 veces solicitada.

module Main (main) where

-- codigo Haskell

main :: IO ()
main = mapM_ putStrLn $ take 500 $ repeat "Debo poner atencion en clases"

En Lisp sería similar, pero Lisp es de tipificación dinámica y no necesita declarar variables, dando lugar a un programa muy simple de una sola linea. Donde también tenemos lenguajes como Clojure, que es un dialecto de Lisp y soporta construcciones muy similares a las del ejemplo en Lisp, dando lugar a programas expresivos y simples, pero que corren sobre la máquina virtual de Java o JVM.

;;; codigo Lisp

(loop repeat 500 do (format t "Debo poner atencion en clases~%"))

Un ejemplo clásico para la conversión η en Haskell, es reducir las llamadas a funciones en su combinador de identidad. Por ejemplo se tiene la función f(g(x)), que en Cálculo Lambda se expresa como λx.(λy.y)x, se puede reducir a g(x), que se expresa como λy.y en Cálculo Lambda. Esto expresado en Haskell, se vería como el siguiente ejemplo, donde absN y absN' son funciones equivalentes y absN' es la reducción η de absN.

absN :: Num a => a -> a
absN n = abs n

absN' :: Num a => a -> a
absN' = abs

Actualmente los lenguajes orientados a objetos más comunes están integrando características funcionales, como Java, que acaba de incluir funciones anonimas. Pero también están los lenguajes que a lo largo de su historia han sido multi-paradigma, como Python, e implementa características funcionales, procedurales y orientadas a objetos. El bien conocido algoritmo para verificar si un RUT es válido o no, se puede expresar funcionalmente en Python como esta escrito en el siguiente ejemplo.

def val_rut(rut):
    """
    Valida un string con un RUT con el guion incluido, retornando
    cero si es valido.

    Ejemplo: print(val_rut("22222222-2"))
    """
    return cmp(rut[-1],
               str((range(10) + ['K'])[
                   (11 - sum(map(lambda x: (int(x[0]) * x[1]),
                                 zip(reversed(rut[:-2]),
                                     (2 * range(2, 8))))) % 11)]))

Como se aprecia en el ejemplo, la validación se realiza utilizando expresiones o llamadas a funciones, sin uso de variables con estado y mutabilidad, donde cada llamada a una función se puede reducir a un valor determinado, y como resultado final se tiene un valor cero o distinto de cero que indica si el RUT es válido. Este mismo algoritmo funcional, se puede expresar en Haskell con llamadas muy similares, debido a que los nombres de las funciones y funciones de alto orden son bastante comunes entre los lenguajes funcionales.

valRut :: String -> Bool
valRut s = (((['0'..'9'] ++ ['K'])
             !! (11 - sum(zipWith (*)
                          (fmap digitToInt $ drop 2 $ reverse s)
                          (take 10 $ cycle [2..7])) `mod` 11)) == (last s))

De estos dos ejemplos, se puede decir que son funciones puras, principalmente debido a que no tienen variables libres y son una única expresión sin estado y no mutable a lo largo de la ejecución. El problema de la pureza es conceptualmente algo que se idealiza en la programación funcional, siendo abordado de diferentes formas por diferentes lenguajes. El objetivo es mantener las funciones y rutinas puras. En Haskell, con su abstracción más clásica conocida con el nombre de Mónada, permite entregar pureza a expresiones que parecen no ser puras, y en términos muy sencillos el Mónada reúne una identidad y una composición de funciones del tipo f(g(x)), todo a través de un tipo de dato que permite componer funciones sin abandonar ese tipo de dato y darle un aspecto procedural.

Personalmente creo que es importante aprender algo de programación funcional porque de alguna forma cambia la perspectiva que uno tiene de los programas. Uno generalmente esta acostumbrado a pensar en los programas como si fuesen una lista ordenada de instrucciones a seguir, cuando generalmente esa misma lista ordenada de instrucciones a seguir puede ser expresada como una función y más aun, como una función pura.

Durante un tiempo vamos a tener algunos baches, y puede que algunas cosas no estén funcionando tan bien como esperamos. Les pido paciencia.

Inicialmente se incorpora a este blog Daniel Molina Wegener , quien escribirá algunos artículos con mayor frecuencia en este sitio, y estará además a cargo de la sección Programación Funcional.

En esta nueva etapa este sitio funcionará más como una revista, con secciones permanentes las que aparecen destacadas en el front page.

Los invito a visitarnos, porque vamos a tener muchas novedades y una mayor cantidad de contenido útil para todos los apasionados de la programación en habla hispana.

Esperamos  que les guste esta nueva etapa.

codear.

1. intr. Mover los codos.

2. intr. Dar golpes con los codos frecuentemente.

3. intr. Am. Mer. Pedir con insistencia.

4. prnl. Dicho de una persona: Tener trato habitual, de igual a igual, con otra o con cierto grupo social.

Usted programa, los necios codean frente a sus computadores, se van a cansar y no lograrán alzar vuelo nunca.

Codear sería en inglés algo así como jostle, hustle o prod. Code es es código, y Coding sería codificar, o escribir código, también se podría decir desarrollar, pero eso es más amplio, o los profesionales simplemente preferimos traducirlo como programar.

Porque codificar denota transcribir código, en cambio programar implica más, mucho más.

Pronto la solución al último desafío (cuyo premio queda desierto) y la reformulación de este blog.

/Via Destroy All Software

Hay lenguages antiguos, como Fortran IV que usan sentencias goto condicionales e incondicionales, en vez de estructuras como if y while.

Además en Fortran IV cada sentencia ocupa una linea de código. Las primeras 5 posiciones están reservadas para colocar una etiqueta numérica, que corresponde a un número entero. La posición 6 está reservada para una marca de continuación, pero no la vamos a considerar en este ejercicio, la dejaremos en blanco. Por lo tanto las sentencias propiamente tal empiezan a partir de las posiciones 7 en adelante.

Una sentencia goto se ve así:

      goto etiqueta

y una sentencia condicional se escribe así:

      if (expresion)goto etiqueta

Donde “etiqueta” es un número.

Hay otras sentencias, pero sólo los goto condicionales empiezan con “if(” y finalizan con “)goto etiqueta”. En Fortran IV los espacios se ignoran. Consideraremos que la sentencia “stop” sólo aparece al final de un programa, y detiene la ejecución del programa.

Si les interesan conocer las posibles operaciones de un programa Fortran IV consideren las descritas en este enlace.

Desafío
El desafío es determinar si dos programas Fortran IV son equivalentes. Diremos que dos programas son equivalentes si, para todas las entradas posibles, ejecutan exactamente la misma secuencia de sentencias, ignorando los gotos incondicionales y las etiquetas. Diremos que dos secuencias de sentencias son las mismas si son textualmente identicas después de eliminar espacios y etiquetas.
Asuman que cada goto condicional se tomará en algunos casos y no en otros. Los gotos incondicionales se ejecutan siempre.

Los siguientes programas de ejemplo son equivalentes:

Programa 1:

Programa 2:

Se debe crear un programa que reciba como entradas dos programas Fortran IV y escriba en pantalla: “los programas son equivalentes” o “los programas no son equivalentes”.

El plazo para este desafío es el 30 de octubre, los programas deben ser capaces de procesar programas de hasta 1.000 lineas.

Ganará el programa más rápido y más sencillo (menor cantidad de lineas de código) que resuelva este desafío. Si hay suficientes participantes (más de 6) habrá premio

“May the odds be ever in your favor”

Son dos soluciones muy buenas, la de Daniel como siempre en Haskell con un código bastante elegante, la pueden ver en su repositorio GitHub. Sin embargo, hasta ahora no contiene la solución a la flor.

La versión de Hector es sorprendente, al menos para mi, porque no esperaba una solución en JavaScript! Lo otro que me gusta es la elegancia y concisión del código, 70 lineas de javascript. Excelente!

Hector además entrega la solución al L-System de la flor:

Así que el ganador de esta oportunidad de Hector Rodriguez, felicitaciones! Gracias también a Daniel por participar.

Me pondré en contacto con Hector para hacerle entrega de su GiftCard.

Al parecer este desafío estuvo bastante difícil, espero que en el próximo tengamos más participantes. Les pido a todos ustedes que me ayuden a promover esta actividad.

• Transaccional: crear un formulario y copiar los datos ingresados a través de este a una base de datos.
• Batch: leer o escribir archivos desde o hacia una base de datos.

Niklaus Wirth expresó una famosa ecuación como título a uno de sus libros:

 Algoritmos + Estructuras de Datos = Programas

Eso puede haber sido cierto en 1976, pero ¿sigue siéndolo aún en el siglo XXI?

Hemos evolucionado mucho en un desarrollo espiral, para un observador poco atento pareciera que la computación se moviera como un péndulo, van de un paradigma al opuesto y vuelven, pero yo no creo que sea así, con cada ciclo aprendemos algo y lo incorporamos.

Sin embargo hay que reconocer que hay mucho de re inventar la rueda, muy poco de investigación profunda, la urgencia por resolver el problema lleva a muchos a rehacer una solución que ya existía, y con peor desempeño muchas veces.

En su discurso de recepción del premio Turing de 1968 Richard Hamming dijo lo siguiente:

Whereas Newton could say, “If I have seen a little farther than others, it is because I have stood on the shoulders of giants,” I am forced to say, “Today we stand on each other’s feet.” Perhaps the central problem we face in all of computer science is how we are to get to the situation where we build on top of the work of others rather than redoing so much of it in a trivially different way.

Mientras que Newton podía decir, “Si he visto más lejos que otros, es porque me paré sobre hombros de gigantes¨, yo estoy forzado a decir, “Hoy en día nos paramos sobre los pies de los otros”. Quizás el problema principal que enfrentamos en toda la ciencia de la computación es cómo llegaremos a la situación donde construyamos sobre el trabajo de otros más que rehaciendo tanto de aquello de una forma trivialmente diferente.

Así que ahí está el desafío de todo gran programador, construir a partir de lo que ya existe, no reinventar la rueda para que le salga cuadrada .

Nos movemos entre algoritmos y patrones de diseño, estamos llamados a innovar a partir de las herramientas básicas de nuestra profesión y a partir del trabajo previo de quienes nos precedieron. Domina los algoritmos, estudia los patrones, conoce tus frameworks, sus fortalezas, sus limitaciones, juega en el área chica, donde se aplican esos conocimientos para crear una solución a un problema, o una gran innovación. Pero preocúpate de aprender de los que estuvieron antes que tú en este mundo, no seas tan soberbio, la rueda te puede salir cuadrada.

Off Topic: queda una semana para el cierre del desafío Julio Agosto, espero sus respuestas…