Notepad 6.0 ha sido lanzado

NotepadDediqué una entrada a hablar sobre editores e IDEs y me olvidé de mencionar a ese editor que casi todos los programadores instalamos en Windows para suplir nuestras necesidades de edición rápida, el Vim de Windows: Notepad++. Y al igual que Vim, dispone de muchos plugins que lo pueden llegar a convertir en un auténtico IDE: FTP, Debuger, comparador de ficheros, corrector ortográfico y un largo etcétera.

Es esa herramienta que está ahí, que cada día usas pero no la valoras hasta el día que se estropea, como el limpiaparabrisas del coche. (A quién se le haya roto sabrá de su importancia: al llegar la noche ya no ves nada a través del vidrio) Aprovecho que acaba de salir la versión 6 para dedicar un breve espacio a este excelente editor.

Vuelvo a Debian

Cuando en agosto del 2010 adquirí el portátil que estoy actualmente usando, un Dell Vostro 3300, éste venia con Windows 7 Pro. Previamente había estando usando Ubuntu en mi ordenador personal durante casi 2 años y antes de eso, bueno, una larga lista de alternancias entre distribuciones de Linux y diferentes versiones de Windows.

Cuando me llegó el portátil le instalé Cygwin y no añoré demasiado a Linux. Cygwin es, básicamente, una DLL que proporciona una API para que funcionen muchas de las herramientas GNU: scp, gcc, rsync, ssh, vim, emacs, chown, chmod, gzip, tar, wget, find, grep,  cat, etc. También nos permite manejar trabajos o jobs (pasarlos a ejecutar de fondo, eliminarlos…), pipes, instalar en intérprete de Python, Exim (el servidor de correo electrónico), Guile, Git y en definitiva todas las herramientas que esperamos encontrar en GNU. Eso sí, recomiendo el uso de Putty pues la consola que viene con Windows es un tanto deficiente. Todo esto es posible gracias a que Windows es compatible, hasta cierto grado, con el estándar POSIX.

Logo de DebianDe todas formas seguía añorando Linux pero nunca encontraba el tiempo para instalarlo, volver a configurar todo el software, recuparar los archivos y demás tareas. También consideraba la posibilidad de comprar otro ordenador donde instalar Linux hasta que el fin de semana pasado compartí mis cuitas con Gabriel, compañero y administrador sistemas, quien me recordó la posibilidad de virtualizar, algo que ya tenía casi olvidado pues mi portátil “sólo” dispone de 4 GB de RAM, lo cual es algo justo para sistemas de 64 bits. Ese mismo fin de semana lo amplié a 8GB e instalé VMware. Estaba dudando entre Debian, el primer Linux que tuve (2004, ¡hace ya 8 años de eso!) y la distribución que más se ha popularizado en los servidores de hosting web: CentOS, la versión no comercial de RedHat. Al final me decanté por Debian, lo instalé, configuré y… ¡ya no puede parar! Me encuentro pasando más tiempo en la máquina virtual que en el sistema operativo anfitrión. Windows 7 es un muy buen sistema operativo, pero un Unix es un Unix, aquí lo explico más detalladamente.

Inefficiencies due to CakePHP ORM implementation

First let me say this article is not a critic against CakePHP (except one point I will talk about later), Object Relational Mapping, far than a trivial thing, it’s a very complicated one.

Let’s begin explaining what this TLA (three-letter acronym) is :-) Object Relational Mapping is a programming technique for allowing objects interact with a relational database, trying to allow the programmer to create, insert, update and delete objects in the database without typing a single line of SQL. The technical difficulties are well know (by the name “Object-relational impedance mismatch”) and there is a lot of theory about them. In fact, some frameworks like CodeIgniter or Zend Framework avoid not only ORM but the models. This is not because these frameworks don’t follow the MVC pattern but because they follow a different philosophy: as it’s impossible to know how the datasource will be, better to don’t provide models and let them for the developer. They just provide some classes to interact with databases. The fact CakePHP implements ORM helps us to rapid develop an application, CRUD interfaces creation can be automatized, etc. CakePHP is RAD!

Now let’s see how the way CakePHP implements ORM creates some inefficiencies. I will follow the examples the documentation shows. If an ingredient can have many recipes and ingredients can belong to many recipes we need and intermediate table to join them, following the Normal Forms for designing the database, this intermediate table should look like:

ingredient_id, receipe_id

These two fields form the compound primary key and both have a foreign key to their respective tables. (From now on the primary key is underlined) We can add attributes for the relation: quantity or whatever. First inconvenience: CakePHP doesn’t support compound primary keys. The documentation says this relationship is “Has and Belongs to Many” and specifically:

The contents of the table should be two fields, each foreign keys (which should be integers) pointing to both of the primary keys of the involved models. To avoid any issues – don’t define a combined primary key for these two fields, if your application requires it you can define a unique index.

The inefficiencies start, following the “CakePHP way” for developing, the table should look:

id (autonumeric), ingredient_id, receipe_id

And add an unique key formed by the two fields. Despite what the documentation warns, I have a join table that follows Normal Forms (the two fields are the PK) and I still haven’t had any issues, but this is absolutely no possible when the relationship has attributes. For this cases CakePHP, following Ruby on Rails, has the relationship “hasMany through“. If students take courses, courses can be taken by many students and we want to store for every student the attended days and final grade, the table should look like:

student_id, course_id, days_attended, grade

Instead, CakePHP requires this table design:

id, student_id, course_id, days_attended, grade

To ensure the integrity we create an unique index formed by the fields student_id and course_id, because a student attends x days to a course and has only one grade for that course. When the user modifies a grade Cake doesn’t perform an update query, first deletes the record and then inserts it again with the new attributes, two queries instead of one. But it can be far worst. Imagine a situation where the user is viewing the student’s profile, for each students has a button for accessing a page to edit his/her grades. If the user edits a profile and saves the database will trigger an integrity violation error because Cake is trying to insert a new record instead of update the existing one (remember there is an unique index). This time Cake can’t automagically help us so we must type some code into the Model’s beforeSave method, something like:

  1. public function beforeSave($options = array()) {
  2.     if (empty($this->id)) {     // Pretends an insert.
  3.         $conditions = array(
  4.             ‘student_id’ => $this->data[‘CoursesStudents’][‘student_id’],
  5.             ‘course_id’ => $this->data[‘CoursesStudents’][‘course_id’]
  6.         );
  7.         $id = $this->find(‘first’, array(‘conditions’ => $conditions, ‘fields’ => ‘id’));
  8.         if (!empty($id[‘CoursesStudents’][‘id’])) {
  9.             $this->id = $id[‘CoursesStudents’][‘id’];
  10.         }
  11.     }
  12.  
  13.     return true;
  14. }

First Cake performs a query trying to know if it’s an insert or an update, then in beforeSave we perform another query to know if the record really exists, if it does we tell Cake to perform an update assigning a value to $this->id But this will not work! Before the execution arrives to the beforeSave method, CakePHP already determined if it is an insert or an update and it’s too late for us to change it. The solution is to delete the record, a slight but significant modification in the previous code:

  1. public function beforeSave($options = array()) {
  2.     if (empty($this->id)) {     // Pretends an insert.
  3.         $conditions = array(
  4.             ‘student_id’ => $this->data[‘CoursesStudents’][‘student_id’],
  5.             ‘course_id’ => $this->data[‘CoursesStudents’][‘course_id’]
  6.         );
  7.         $id = $this->find(‘first’, array(‘conditions’ => $conditions, ‘fields’ => ‘id’));
  8.         if (!empty($id[‘CoursesStudents’][‘id’])) {
  9.             $this->id = $id[‘CoursesStudents’][‘id’];
  10.             $this->delete();
  11.         }
  12.     }
  13.  
  14.     return true;

With the delete already 3 queries have been executed and with a final insert the process of updating a student’s grade will finish. Four queries instead of one makes CakePHP a bit chatty, don’t you think? Databases are usually the bottleneck in websites and we must avoid any unnecessary access. The fact that the primary key can’t be changed in beforeSave is something already mentioned as an improvement and maybe will be implemented in future versions. At the time I’m writing this the last version is 2.1 and it’s still pending. But seems that implementing compound primary keys it’s not one of CakePHP core developers objectives. Seems this feature has been requested since years ago but never came to fruition. Some argue Normal Forms aren’t efficient for highly transited sites. This debate it’s a complicated one and I would love to hear your opinions and learn!

Ventajas de los Unix-like para un profesional

Primero permítanme definir quien está a cada lado. Los Unix-like son todos los sistemas operativos Unix, por ejemplo OS X, FreeBSD, OpenBSD, Solaris… En este lado también pongo a Linux, aunque no sea exactamente un UNIX pues la licencia GNU significa “GNU’s not Unix” y una distribución Linux es básicamente el kernel de Linux más las herramientas GNU. Por otro lado… Windows, ¿es que hay alguno más? :-)

Los Unix-like tienen la ventaja de que nos permiten optimizar esfuerzos pues los conocimientos adquiridos con ellos no caducan. Incluso conocimientos adquiridos en los años 70, antes de que surgieran los ordenadores personales o los modernos lenguajes de programación, siguen siendo válidos hoy en día. El equivalente en historia a 40 años en tecnología serían muchos siglos. En un mundo tan cambiante, donde en menos de una década todo cambia, Unix es la única constante de la que tengo constancia. El lenguaje C, las llamadas al sistema, los comandos, las “pipes”… ahí están desde el principio de los tiempos con pocas variaciones, así como su filosofía, probablemente la responsable de que haya podido sobrevivir tantas décadas.

Los desarrolladores y administradores de sistemas del otro lado siempre tienen que estar pendientes de lo que la compañía propietaria decida. Por ejemplo a finales del año pasado a todos los desarrolladores .NET les preocupó el anuncio de que se enfatizaría HTML y Javascript  como plataforma de desarrollo para Windows 8. ¿Iba .NET a ser extinguido? ¿Y todo el tiempo que le dedicaron y títulos oficiales de Microsoft pagados a precio de oro? Al final parece ser que la Runtime va a ser cambiada a COM y si los programadores .NET no quedan tirados es porque será accesible desde C/C++, .NET, etc. Aunque no sería la primera vez ni la última que una empresa deja abandonados a su suerte a los especialistas en alguna de sus tecnologías. ¿Qué pasaría por ejemplo si Sun abandonase Java? Tres años atrás me habrían tildado de loco por el mero hecho de plantear la posibilidad. Ahora las tecnologías de Sun pertenecen a Oracle, quien adquirió a la primera. ¿Qué futuro reserva Oracle para MySQL y Java? El que más le convenga a sus accionistas, obviamente.

Desde una perspectiva más general, las soluciones tecnológicas de Microsoft, Sun y demás enmascaran el problema solucionado detrás de otros problemas. Un profesional en una de esas soluciones tecnológicas es experto en solucionar esos problemas, pero si desconoce el problema principal, el problema que tecnologías como Java, .NET o Windows Server 200X quieren solucionar, al ser reemplazadas esas soluciones por otras el profesional tiene que partir otra vez, casi de cero, a aprender el reemplazo a la vieja solución y pagar de nuevo certificaciones que cuando proceden de grandes multinacionales son siempre costosas.

Nunca he odiado a Microsoft, algo bastante extendido entre los seguidores de las soluciones open source, bien al contrario le reconozco su gran labor de sacar la informática de las grandes multinacionales, bancos, ejércitos y grandes universidades y llevarla a los hogares, escuelas, oficinas y universidades, algo que les agradezco como esperan: pagando las licencias del software suyo que utilizo, básicamente Windows. Ahora bien, por el futuro de mi carrera profesional, prefiero soluciones open source como muchos de los Unix-like que existen ahora mismo y recomendaría lo mismo.

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:

  1. if ($this->request->is(‘post’)) {
  2.     $this->User->create();
  3.     if ($this->User->save($this->request->data)) {
  4.         $this->Session->setFlash(__(‘The user has been saved’));
  5.         $this->redirect(array(‘action’ => ‘index’));
  6.     } else {
  7.         $this->Session->setFlash(__(‘The user could not be saved. Please, try again.’));
  8.     }
  9. }

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.

Different ways from preventing form resubmission

HTTP is stateless, every request is independent from the previous one, when the connection is established there is a request, a respond and the connection finishes. That’s all. One common problem in web programming is when the user, after drinking more coffee than he can remember, compulsively and possessed by an extreme urge, clicks repeatedly the send button until the mouse wants to commit suicide. Then, the server receives all these requests without knowing if the user (the client) is sending the same information again and again. Another similar situation is when users, after submitting data to the server via a web form, decide they want to come back and click the browser’s previous button. Then, the browser pops up a message saying that they will resubmit the data again. If they don’t care and accept it, here there is our server receiving the same information again. A variant of this one is when the user refreshes the page after sending the post. (Forms that include files or server lag may trigger the user’s impatience) How to deal with those requests is something that we, as programmers, must take care of.

Now the solutions! First I will show you the way to prevent resending the form if the user navigates backwards or refreshes the page. The nicest solution is to implement two pages, let’s call them A and B. In page A the user submits the form and a Post request is send to the server. Our code must process this request and, if valid, resend it to the page B in a Get request. Let’s see server’s side code for page A for one of the nicest PHP frameworks out there, CakePHP:

  1. public function admin_proxy() {
  2.     $params = array();
  3.     foreach ($this->data[‘User’] as $key=>$value) {
  4.         if (!empty($value)) {
  5.             $params[$key] = rawurlencode($value);
  6.         }
  7.     }
  8.     $destination = array_merge(array(‘controller’ => ‘users’, ‘action’ => ‘admin_index’), $params);
  9.     $this->redirect($destination);
  10. }

First we encode the parameters before passing them to the action “admin_index”, the B page that will receive the parameters via Get. Just if you are curious and / or you aren’t used to build applications for languages with accents, this will not work for languages like Spanish, Catalan or French:

  1. urlencode(htmlentities($value, ENT_NOQUOTES, ‘UTF-8′))

The website is in Spanish, that’s why I use rawurlencode() After this, you can see a redirect in the code. This will send a HTTP 302 status code to the browser, the usual method (although 303 is more standard friendly) for performing a redirection forcing the type to Get, regardless the previous request type. Now the page B receives the parameters, decodes them, and informs the user about the operation’s results or any other logic we may want to perform:

  1. public function admin_index() {    
  2.     if (!empty($this->params[‘named’])) {
  3.         foreach ($this->params[‘named’] as $key=>$value)
  4.             $this->data[‘User’][$key] = rawurldecode($value);
  5.     }
  6.        
  7.     /*
  8.      * Some cool things to do here…
  9.     */
  10. }

If we want to do anything with the data the user sends, like store a record in the database, send an e-mail, deface NASA web page, whatever, we must do it before the redirect, in the logic for page A.

Now a fast and dirty solution for preventing the user clicking the submit button multiple times: disable the send button after the user sends it using client side code in Javascript. Please, read carefully: after the user sends it, not after clicks the button. What about if the user clicks but the form isn’t submitted because has an error the user must correct? We can’t leave it disabled or the user will have real trouble trying to send it. Let’s see a solution with jQuery and Validate library:

  1. $(document).ready(function() {
  2.     $(‘#MyForm’).validate({
  3.         rules: {
  4.             // Some rules here.
  5.         },
  6.         messages: {
  7.             // Messages for rules violation.
  8.         },
  9.         submitHandler: function(){
  10.             $(‘input.submit’).attr(‘disabled’, ‘disabled’);
  11.             $(‘#MyForm’).submit();
  12.         }
  13.     });
  14.  });

SubmitHandler will be executed only after the user clicks the send button and the form is correctly filled, only then, the function it contains will disable the submit button. As stated before, this solution is fast, but what about the user that disables Javascript? It will not work. A good solution is to use the session variable in the server side. When the form is created we generate a token and we store it both in the session and in a form’s hidden input field. When the user submits the form we check if the session has the form’s token stored, if it does and both match we delete the variable from the session and the form’s data process continues, if it doesn’t exist or they don’t match, we refuse to process the request. The token can be generated with any hash function like md5 or sha1, being md5 faster.

  1. <input type=”hidden” name=”myform_hash” value=”<?php echo md5(Configure::read(‘Site.salt’)); ?>” />

And what about a malicious user doing form tampering? First of all, let me explain what form tampering is: it’s the name for an attack that consists in store the form into a file and modify it for sending it again against the server, the intentions aren’t always good. Thanks to CakePHP you don’t need to worry about this, if you use the “Security” component and the “Form” helper, automagically your site is protected. Well, let me explain the magic: the Form helper will add hidden token fields and the Security component will check them. Among other things, form submissions will not be accepted after a period of time that depends on the setting of “Security.level”. The same idea can be implemented in any script for the web.

This weekend I was curious about how WordPress (3.3.1) solves this because I’m developing some projects with this CMS and I was surprised for my findings. The function wp_new_comment(), called from wp-comments-post.php calls wp_allow_comment(), both functions are located in comment.php, look what this last function does:

  1. // Simple duplicate check
  2. // expected_slashed ($comment_post_ID, $comment_author, $comment_author_email, $comment_content)
  3. $dupe = "SELECT comment_ID FROM $wpdb->comments WHERE comment_post_ID = ‘$comment_post_ID‘ AND comment_approved != ‘trash’ AND ( comment_author = ‘$comment_author‘ ";
  4. if ( $comment_author_email )
  5.     $dupe .= "OR comment_author_email = ‘$comment_author_email‘ ";
  6. $dupe .= ") AND comment_content = ‘$comment_content‘ LIMIT 1";
  7. if ( $wpdb->get_var($dupe) ) {
  8.     do_action( ‘comment_duplicate_trigger’, $commentdata );
  9.     if ( defined(‘DOING_AJAX’) )
  10.         die( __(‘Duplicate comment detected; it looks as though you&#8217;ve already said that!’) );
  11.  
  12.     wp_die( __(‘Duplicate comment detected; it looks as though you&#8217;ve already said that!’) );
  13. }

Is doing a query against the database, looking into the table “comments” if the content the user is commenting (post) has any comment not in the trash that belongs to that user (using the author name or the email if set) and the content (the comment’s body) is exactly the same. It works and prevents both multiple clicking and repeating yourself two years later, but what about performance? Any comment a user does requires this overload? If we examine the table comments we can see that the field comment_content type is “text”. I’m not saying this query is slow, but it’s necessary? Databases are usually the bottleneck in websites, therefore the philosophy of avoiding as much as possible queries is great. Furthermore, WordPress sites are usually in shared servers and don’t expect great performance there… But WordPress has come a long way and sure their contributors are experienced developers therefore I guess they have a good reason for doing it this way and I would like to know. Anybody can bring me some light about this?

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:

  1. (define (fib n)
  2.     (cond ((= n 0) 0)
  3.     ((= n 1) 1)
  4.     (else (+ (fib (- n 1))
  5.         (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:

  1. (define (fib n)
  2.     (fib-iter 1 0 n))
  3.  
  4. (define (fib-iter a b count)
  5.     (if (= count 0)
  6.     b
  7.     (fib-iter (+ a b) a (- count 1))))

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

  1. (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:

  1. function fib ($a, $b, $aCalc) {
  2.  
  3.     if ($aCalc == 0) {
  4.         return $b;
  5.     }else{
  6.         $aCalc–;
  7.         fib($a + $b, $a, $aCalc);
  8.     }
  9. }
  10.  
  11. $result = fib (1, 0, 4);
  12. 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:

  1. function fibonacci($n) {
  2.     $f[0] = 0;
  3.     $f[1] = 1;
  4.  
  5.     for ($i = 2; $i <= $n; $i++) {
  6.         $f[$i] = $f[$i-1] + $f[$i-2];
  7.     }
  8.  
  9.     echo $f[$n];
  10. }
  11. 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:

  1. (define (A x y)
  2.     (cond ((= y 0) 0)
  3.     ((= x 0) (* 2 y))
  4.     ((= y 1) 2)
  5.     (else (A (- x 1)
  6.         (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:

  1. (define (factorial n)
  2.     (if (= n 1)
  3.     1
  4.     (* 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.

IDE, Vim o Emacs

¿Qué editor usar para programar? Es un tema que despierta pasiones, sólo las discusiones Emacs vs Vim ya se encienden con usuarios de estos editores, que en algunos casos llegan a llevar incluso décadas usándolos, pero no es sobre esto sobre lo que quiero opinar aquí sino sobre si usar uno de estos clásicos editores o un “moderno” IDE como Eclipse o NetBeans (mi favorito). Aquí también alguien podrá objetar que tanto Vim mediante plugins y sobretodo Emacs son auténticos IDEs, para quienes piensen así que por favor interpreten que el debate es entre viejos y nuevos IDEs.

En mi opinión, IDEs como NetBean o Eclipse sirven para trabajar en EL PROYECTO, ese proyecto que se va desarrollando durante meses o años y que puede que tenga a otros desarrolladores involucrados. Mientras que prefiero usar editores tipo Vim o Emacs en esos proyectos más pequeños y diversos. Hasta hace poco creía que un editor como Nano era suficiente para trabajar en el servidor con los ficheros de configuración o para arreglar algún marrón en vivo pero ahora veo que es rentable molestarse en aprender lo básico de una herramienta más sofisticada como Vim o Emacs.

Y si me preguntan si Vim o Emacs respondo que Vim. Emacs es un monstruo que hace parecer a Unix un plugin suyo :-) Basta decir que su lenguaje para ampliarle funcionalidades es Emacs Lisp, un dialecto de Lisp.

Creear una comunidad sobre tecnología en Cali

Me gustaría crear una comunidad de desarrolladores, administradores de sistemas y de todo tipo de personas interesadas en las nuevas tecnologías aquí en Cali. Una comunidad que se pueda reunir periódicamente para tratar y desarrollar los temas que más nos plazcan, compartir conocimientos… una especie de hacklab donde colaborar y socializar. Más detalles como dónde nos reuniríamos, periodicidad y demás concretémoslos cuando seamos algunos. Si estás interesad@ en llevar acabo esta idea puedes ponerte en contacto conmigo a través de la página de contacto o bien puedes dejar aquí mismo un comentario.

¡Espero que la idea guste y podamos llegar a ser unos cuantos! Si conoces a alguien que crees pudiera estar interesad@ por favor difunde este mensaje, ¡gracias!

– Editado el 01/02/2012 –

Esta propuesta me ha llevado a conocer al grupo caleño DELM ¡Espero que nos podamos reunir próximamente!

– Editado el 04/02/2012 –

En espera de la próxima reunión de DELM los interesados en el proyecto del que hablo aquí nos reunimos mañana domingo a las 10 de la manaña en el centro comercial Chipichape.

– Editado el 24/03/2012 –

Estuvo muy interesante la reunión y estoy esperando la próxima. No obstante, aunque pude conocer interesantes personas y proyectos, encontré a faltar más personas interesadas en el aspecto ingenieril para poder formar una comunidad más similar a la aquí descrita. Interesad@s ya sabéis, poneros por favor en contacto conmigo.