La Sombra de Dijkstra

Sobre el arte y la práctica de la programación

Resultado Desafío Enero 2013

| Comentarios

RESULTADO FINAL: (NOTA del 21 de febrero) Se cumplió el plazo final ofrecido el 15 de febrero. Gracias a Cristóbal Leiva, Israel Leiva y Tomás Hermosilla, por seguir participando. Los programas mejoraron bastantes, y la verdad es que no me gusta dejar este desafío sin ganador.

Por un lado el programa de Cristobal mejoró bastante, y pasa la segunda prueba. Los programas de Israel y Tomás también, aunque aún tienen problemas con condiciones de borde en el manejo de strings.

Debo admitir que el manejo de strings complica más de lo necesario el desafío, así que para revertir esta situación he decidido entregar igual el premio a Cristobal, que escribió el mejor programa de acuerdo a los requisitos, es decir, es el que tiene el menor valor para E de acuerdo al ranking que aparece más abajo.

Así que felicitaciones a Cristóbal, y a los demás gracias por participar. Los espero en nuevos desafíos.


ATENCIÓN: (NOTA del 15 de febrero) Debido al comentario de Cristóbal Leiva se hizo una corrección en la gramática de mi reconocedor ANTLR, pueden revisar el cambio acá. Esto implica un ajuste en el valor de E para algunos participantes, pero no alteró el ranking, ver los ajustes más abajo).


Bien, se cumplió el plazo para responder al desafío de enero: “Las Métricas de Halstead”. Al parecer estuvo más complicado de lo que esperaba. Finalmente sólo se presentaron 7 participantes, por lo que, lamentablemente, no tendremos premio :( …

Pero… con el fin de estimularlos, y animarlos a que participen en el desafío que viene (en marzo), voy a hacer una excepción, y dado que sólo falto un participante, vamos a tener premio de Gift Card Amazon por 30 dólares en esta oportunidad!!

Los participantes son:

Para medir el esfuerzo de implementación (E) usé este programa en ANTLR. Para los que no lo conocen, ANTLR es una herramienta para generar compiladores (o parsers). Por razones de tiempo no voy a explicar como funciona mi programa, pero ahí está disponible para que lo analicen y me manden sus observaciones.

A continuación va el ranking en función del valor E, recuerden que las reglas decían que ganaría aquel programa con el menor valor para E. Sin embargo, el programa debe funcionar correctamente, así que primero vamos a ordenar a los participantes por el valor E, y luego iremos ejecutando sus programas para verificar que estén correctos. Sólo voy a ejecutar el programa con menor valor E, si este funciona adecuadamente para los archivos de prueba, entonces ganará inmediatamente, sino continuaré con el siguiente de la lista.

Ranking

(Se hizo un ajuste en el ranking de algunos participantes debido a la observación de Cristóbal Leiva, ver [este comentario])

  1. cleiva: E=5.101,61

  2. mannungo: E=8.437,93

  3. thermosilla: E=9.729,20 // E=8.716,17

  4. aldrinmartoq: 10.990,32 // anterior E=10.963,06

  5. rodrigore: E=13.036,08 // anterior E=13.278,09

  6. ileiva: E=32.833,86 // anterior E=33.844,43

  7. edmt: E=34.034,31

  8. lnds: E=83.483,11 // anterior E=83.285,76

Evaluación

Los archivos de prueba son:

  • fuente1.test: este archivo es el ejemplo mencionado en el desafío. Hay que notar que la lista de operadores es distinta, así que los valores esperados no son los mismos.

  • Halstead.g4: esta es mi solución en Antlr 4.

  • ileiva.pl: Perl tiene algunas particularidades bien especiales con respecto a las expresiones regulares, la idea es ver que tal se manejan con este lenguaje.

  • edmt.py: Este programa en python tiene strings con triple comillas (“”“), es interesante observar cómo maneja esa condición cada programa.

El archivo de operadores definitivo es el siguiente:

Resultados

Probé primero el programa de Cristobal, que es el que tiene el menor valor para E.

Este es el resultado de las pruebas:

Programa: cleiva.php

  1. fuente1.test: Calcula perfecto el valor de E: 115,64.
  2. Halstead.g4: calcula correctamente n1 y N1, pero falla al evaluar n2, y N2, con lo que el valor de E difiere de lo esperado. n2 debería ser 199, y N2 debería ser 443, sin embargo el programa de Cristóbal calcula n2 como 197 y N2 como 441. La diferencia se debe a que mi programa considera esta secuencia \r\n\t como 3 tokens distintos, en cambio el programa cleiva.php lo considera como una sóla secuencia de 6 caracteres. Lo que está incorrecto, ¡prueba no superada!

Así que pasamos al siguiente participante.

Programa: mannungo.php

  1. fuente1.test: Acá nos fue mal :(, por alguna razón obtengo una división por cero en la linea 18 y un mensaje “unknown modifier” en las lineas 8 y 12. Así que mannungo, espero que me expliques en los comentarios que pasó. ¡prueba no superada!

Pasamos al siguiente participante en el ranking.

Programa: thermosilla.py

  1. fuente1.test: Calcula perfecto E y los otros valores.
  2. Halstead.g4: Los valores para n1 y N1 no coinciden, claramente hay un problema con las expresiones regulares. n1 debería ser 14, pero arroja 8, y N1 debería ser 248 pero calcula 108. No reconoce los símbolos >, <, @, $, ~, *. ¡Prueba no superada!

Vamos al cuarto participante.

Programa: aldrinmartoq.rb

  1. fuente1.test: sin problemas.
  2. Halstead.g4: prueba no superada. Problemas con n1 y N1, calcula 9 y 102 respectivamente, tampoco reconoce >, <, @, $ y ~. ¡Prueba no superada!

Veamos cómo le va al quinto partecipante:

Programa: rodrigore.rb

  1. fuente1.test: prueba superada.
  2. Halstead.g4: falla al no reconocer el operador ~.

Esto salió bastante difícil para nuestros concursantes, vamos al sexto participante:

Programa: ileiva.pl

  1. fuente1.test: en este caso el programa lleva el consumo de la cpu al tope, y después de varios minutos sin avanzar decidí detenerlo. Así que Israel, espero en los comentarios tus indicaciones para ver como lo puedo probar.

El último participante:

Programa: edmt.py

  1. fuente1.test: sin complicaciones
  2. Halstead.g4: falla al calcular n1, lamentablemente este programa no entrega la lista de operadores, así que no puedo indicar donde está el error.

¡Y el ganador es!

–Bueno, ¡hasta el momento no hay ganador! :( – Cristóbal Leiva (ver nota del 21 de febrero al inicio de este post).

¡Felicitaciones Cristóbal! Me contactaré contigo en los próximos días.

–A menos que antes de 5 días alguno de los participantes entregue un programa que supere las pruebas. ¡Ah! y si no has participado, y crees que puedes superar a los finalistas puedes intentarlo también, de todas maneras tendrá preferencia cualquiera de los otros 7 finalistas, pero puedes intentarlo…–

Desafío Enero - Las Métricas De Halstead

| Comentarios

Ha llegado la hora de empezar los desafíos de este año. La meta es prepararse para el gran desafío de octubre, que tendrá un premio especial y que llamaremos el Premio DMW (como homenaje póstumo a nuestro colega Daniel Molina Wegener).

Este primer desafío es bien especial, porque nos servirá para construir la herramienta que nos permitirá medir a los futuros participantes.

Se trata de las métricas de Halstead.

Warmup Fibonacci (Desafío)

| Comentarios

Este ejercicio es un calentamiento para los ejercicios que vendrán y los desafíos que tendremos el próximo año.

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.

Tu Jefe Es Un Programador Funcional

| Comentarios

Probablemente tu jefe, y mi jefe, sin ser informáticos, ni programadores sean mejores programadores funcionales que tu mismo, claro, porque es probable que ellos utilicen uno de los lenguajes funcionales más populares que existen: Excel.

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

Adios Daniel

| Comentarios

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.

Qué Es La Programación Funcional?

| Comentarios

La programación funcional, o mejor dicho, los lenguajes de programación funcionales, son aquellos lenguajes donde las variables no tienen estado — no hay cambios en éstas a lo largo del tiempo — y son inmutables — no pueden cambiarse los valores a lo largo de la ejecución. Además los programas se estructuran componiendo expresiones que se evalúan como funciones. Dentro de los lenguajes funcionales tenemos Lisp, Scheme, Clojure, Haskell, OCaml y Standard ML, entre otros. Estos lenguajes están diversidad de tipificación, donde se encuentran lenguajes dinámicos, estáticos y estáticos fuertes.

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.

Reboot

| Comentarios

Hola, bienvenidos al reboot de La Sombra De Dijsktra, a partir de hoy este sitio tendrá un nuevo estilo. La idea es reformular este proyecto invitando a participar a nuevos autores. Además tendremos otro tipo de material no tan técnico, pero necesario para desarrollar otras habilidades necesarias para todo profesional de la programación.

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

| Comentarios

Tomado de la Real Academia de la Lengua:

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.