¡Otra vez no! Muere John McCarthy, inventor de Lisp

Estamos de tristeza últimamente. Tras la muerte de Ritchie, muere también el inventor de Lisp, John McCarthy. Para un blog escrito en Lisp (y para toda la comunidad informática mundial) una mala noticia. Si C es el padre de la mayoría de los lenguajes imperativos, Lisp lo es de los funcionales. Con esos dos lenguajes casi cubrimos el 99% de la informática... A este seguro que tampoco lo vemos en cientos de periódicos... Os dejo un enlace al artículo original de LISP.

McCarthy

Muere Dennis Ritchie

A todo aquel que haya programado alguna vez en C, o en alguno de los cientos de lenguajes que lo tomaron como guía, no puede más que apenar la noticia de su muerte. Adiós a un grande de la informática (este sí).

Let Over Lambda--50 years of Lisp

Hoy por casualidad he encontrado esta referencia, Let Over Lambda, Closures de Doug Hoyte. Es curioso que sin haberlo leído antes, la solución que he dado al problema de extraer la descripción de una entrada del blog sin tags HTML ha sido así usando un closure.

Búsqueda en el blog

Como véis, todavía no funciona la búsqueda en el blog, pero tengo una idea muy interesante para implementarla. Recordad que el blog se genera estáticamente, así que no puedo depender de ningún proceso de servidor, así que, por decirlo de alguna manera, tengo que precalcular la búsqueda y almacenarla en algún sitio, que además, no entorpezca con el blog (no tarde más tiempo en cargar, por ejemplo). Lo que estoy preparando lo explicaré con tranquilidad. Por ahora, valga una muestra de lo que llevo implementado:

BLOG> (hash-table-count
       *words-to-post-hash*)
18119

18119 palabras diferentes. Ahora los posts que contienen "corba", y sus títulos:

BLOG> (gethash "corba" *words-to-post-hash*)
(#<POST {100A12E8A1}> #<POST {100A12E881}> #<POST {100A12E521}>
 #<POST {100A12E4E1}> #<POST {100A12E4C1}> #<POST {100A12E3E1}>
 #<POST {100A12E021}> #<POST {100A12DBA1}> #<POST {100A12D321}>
 #<POST {100A12CEE1}> #<POST {100A12C821}> #<POST {100A12C641}>
 #<POST {100A12C5A1}> #<POST {100A12C361}> #<POST {100A12C2E1}>
 #<POST {100A12B4E1}> #<POST {1003344011}> #<POST {1003343EB1}>
 #<POST {10033437B1}> #<POST {10033436B1}> #<POST {1007887F81}>
 #<POST {1007887221}> #<POST {10078870A1}> #<POST {1007886801}>)
T
BLOG> (mapcar #'post-title (gethash "corba" *words-to-post-hash*))
("¿Por qué un Weblog?" "5.000.000.000" "CCM page, reloaded"
 "Recent articles on CCM" "German book on CCM" "CCM Wiki updated"
 "Some thoughts on Web Services" "New version of the CCM tutorial"
 "Stefan Tilkov on RPC Web Services" "Trabajo en la tesis" "CORBA Reborn?"
 "Interesting post on XML messaging by Stefan Tilkov" "Sistemas Distribuidos"
 "Prácticas de Sistemas Distribuidos" "Un día de trabajo con mi tesis" "FreeNX"
 "Fowler, inversion del control" "Ser profesor tiene sus cosas buenas"
 "Función C++ rara del día" "The S stands for Simple"
 "Conversión sencilla de tipos CORBA" "Parecía que nunca iba a llegar..."
 "Más avances: Cátedra SAES-UMU" "SOAP, entre lo peor de la década")

Lo cual es, por cierto, una magnífica lista de entradas para esa palabra... Esta información también me permitirá añadir al final un conjunto de "posts relacionados" en cada entrada.

Imágenes en el blog

Iba a introducir imágenes en el blog y he querido escribir una pequeña función que hace más sencillo introducir fácilmente las imágenes con la ruta por defecto, y, si procede, un enlace para las mismas. La función queda como sigue:

(defun blog-img (img-file &key alt anchor title params)
  (let* ((param-list
          (cons `(src . ,(format nil "~A/~A" *base-img-url* img-file))
                (cons `(alt . ,(or alt "Blog image.")) ; alt is obligatory
                      (when title `((title . ,title))))))
         (param-list-1 (append param-list params))
         (img-html (img param-list-1)))
    (if anchor
        (a `((href . ,anchor)) img-html)
        img-html)))

¿No es bonito? En particular me gusta el uso del seudoquote. Las funciones img y a generan el HTML para las imágenes y para los enlaces, respectivamente. Un ejemplo de uso de esa función sería:

(blog-img "abc.jpg" :alt "Alt text" :params '((:width . 500)))

donde se elige el fichero img/abc.jpg con un texto alternativo y con el conjunto de parámetros adicionales, entre ellos el ancho de la imagen. Si se especifica un elemento anchor el código que se genera es el siguiente:

(blog-img "abc.jpg" 'anchor "http://wherever.com"  'alt "bah" 'params '(('width . 500)))
<A HREF="http://wherever.com"><IMG SRC="img/abc.jpg" ALT="bah" WIDTH="500"></IMG></A>

Estadísticas de tiempo de generación del blog

De cara a optimizar la generación de las páginas del blog con multiprogramación, he querido registrar el tiempo que tarda en ejecutar la generación en el ordenador que se genera, para compararla después con la optimización. Para mi sorpresa, la mayor parte del os 8 segundos que lleva la generación se la lleva el leer y compilar el fichero Lisp que contiene las entradas antiguas (1.3MB), mientras que la generación de todas las páginas no tarda más de 4 segundos:

[dsevilla@neuromancer:~/svn/blog]$ sbcl --script packages.lisp
Doing pre-calculations...
Generating index page...
Evaluation took:
  0.116 seconds of real time
  0.120000 seconds of total run time (0.080000 user, 0.040000 system)
  [ Run times consist of 0.040 seconds GC time, and 0.080 seconds non-GC time. ]
  103.45% CPU
  325,871,901 processor cycles
  63,697,264 bytes consed

Generating post pages...
Evaluation took:
  0.408 seconds of real time
  0.410000 seconds of total run time (0.270000 user, 0.140000 system)
  [ Run times consist of 0.010 seconds GC time, and 0.400 seconds non-GC time. ]
  100.49% CPU
  1,144,029,612 processor cycles
  167,055,120 bytes consed

Generating categories pages...
Evaluation took:
  0.074 seconds of real time
  0.070000 seconds of total run time (0.070000 user, 0.000000 system)
  94.59% CPU
  209,026,050 processor cycles
  39,985,040 bytes consed

Generating archives pages...
Evaluation took:
  0.086 seconds of real time
  0.090000 seconds of total run time (0.090000 user, 0.000000 system)
  104.65% CPU
  240,093,459 processor cycles
  43,278,720 bytes consed

Generating RSS...
Evaluation took:
  0.084 seconds of real time
  0.080000 seconds of total run time (0.080000 user, 0.000000 system)
  [ Run times consist of 0.020 seconds GC time, and 0.060 seconds non-GC time. ]
  95.24% CPU
  236,784,003 processor cycles
  35,828,208 bytes consed

Esto hace que la optimización, como máximo, sólo pueda reducir esos 0,4 segundos que tarda la generación. Aún así lo intentaré como un ejercicio de programación. La otra idea será ver optimizar el proceso de carga quizá a través de pre-compilación de los ficheros .lisp. Por cierto, para que luego digan que los lenguajes interpretados son lentos... 1 segundo en generar 34MB de ficheros de texto.

La última sorpresa... Por casualidad he probado clisp... Bien, aquí la carga de los ficheros .lisp es instantánea, y la ejecución es incluso más rápida (diría incluso increíblemente rápida:

[dsevilla@neuromancer:~/svn/blog]$ clisp packages.lisp
Doing pre-calculations...
Generating index page...
Real time: 0.186066 sec.
Run time: 0.19 sec.
Space: 24960736 Bytes
GC: 13, GC time: 0.03 sec.
Generating post pages...
Real time: 0.708989 sec.
Run time: 0.69 sec.
Space: 83706152 Bytes
GC: 36, GC time: 0.06 sec.
Generating categories pages...
Real time: 0.051339 sec.
Run time: 0.05 sec.
Space: 11157832 Bytes
GC: 5, GC time: 0.0 sec.
Generating archives pages...
Real time: 0.249124 sec.
Run time: 0.25 sec.
Space: 13408648 Bytes
GC: 6, GC time: 0.02 sec.
Generating RSS...
Real time: 0.891364 sec.
Run time: 0.88 sec.
Space: 20991880 Bytes
GC: 9, GC time: 0.05 sec.

Comparando el tiempo de ejecución visto por el usuario:

[dsevilla@neuromancer:~/svn/blog]$ time clisp packages.lisp
real	0m2.320s
user	0m1.970s
sys	0m0.310s
[dsevilla@neuromancer:~/svn/blog]$ time sbcl --script packages.lisp
real	0m10.405s
user	0m9.940s
sys	0m0.440s

Esto es, ¡5 veces más rápido en general clisp que sbcl! Sin embargo, mirando los datos de cada parte, hay resultados muy extraños e inconsistentes. Por ejemplo, clisp tarda casi un segundo en generar RSS, mientras que sbcl tarda 0,08 segundos (un orden de magnitud menos). Estudiaré el código para ver dónde puede estar el problema, pero por ahora, usaré clisp para generar el blog, aunque use sbcl, con el magnífico entorno Slime para Emacs para seguir programando y probando.

Multiprocesamiento para generar el blog

Siguiendo este enlace voy a intentar añadir multiprocesamiento a la generación del blog para acelerarlo. No va a ser tan sencillo como debería ser, por ejemplo, debería existir, como en Clojure, un parallel map pero la verdad es que no hay, sólo hilos tradicionales... La ventaja, sin embargo, será grande, ya que todas las páginas se pueden generar en paralelo.

Añadido colorización de código con google-code-prettify

Pues no ha sido complicado. Simplemente he seguido las instrucciones del README de la página de google-code-prettify y ya está.

Y las páginas de los tags

Sólo por curiosidad, he aquí cómo está implementada la generación de los links con diferente tamaño del sidebar:

(defun categories-links ()
  (if *categories-links*
      *categories-links*
      (setf *categories-links* (multiple-value-bind (max-n-posts min-n-posts)
          (loop for c being the hash-values in *posts-for-category*
             maximizing (car c) into max
             minimizing (car c) into min
             finally (return (values max min)))
        (apply #'concatenate 'string
                (loop for k being the hash-keys in *posts-for-category*
                   using (hash-value v)
                   collect (format nil "<a href=\"category-~A.html\"
                             title=\"~A topic~:*~p\" rel=\"category tag\"
                             style=\"font-size: ~Apx;\">~3:*~A</a> "
                             (string-downcase k)
                             (car v)
                             (+ 9 (round
                                   (/ (- (car v) min-n-posts)
                                      (/ (- max-n-posts min-n-posts) 10)))))))))))

Y eso sin contar con el cálculo de *posts-for-category*.

Primera aproximación de un mecanismo de actores para C++

Desde hace tiempo quiero escribir esta entrada, pero por falta de tiempo no he podido. El mecanismo de actores se utiliza en lenguajes de programación como Erlang y Scala para sincronizar diferentes «actores» que están funcionando en el sistema. Tradicionalmente, la programación con hilos (salvo en casos como BSP, por ejemplo) se ha realizado básicamente como la programación monoproceso, pero haciendo que el programador tuviera en la cabeza las posibles colisiones que varios hilos ejecutando un código podrían tener.

La otra cara de esta moneda la han tenido lenguajes y paradigmas que cambiaban la manera de programación hacia esquemas que hicieran más fácil escalar en el número de hilos/cores a la vez que permitían una programación más natural de programas multihilo. Estos nuevos paradigmas también evitaban, por diseño, los problemas que se dan con los candados, reentrancia, etc.

El paradigma sobre el que hablaré hoy es el de los actores. Este mecanismo, que data de 1986, se utiliza en Erlang y en Scala, por ejemplo, pero no he encontrado ejemplos de cómo implementar este mecanismo en C++, salvo un artículo de 1993 de Kafura, Mukherji y Lavender en el que no se hace uso de ninguna característica «moderna» de C++, como los tipos parametrizados o la sobrecarga de operadores.

En resumen, el mecanismo de actores se basa en definir un actor como un objeto reactivo que se ejecuta en su propio hilo. Son similares a los objetos stricto sensu, en el sentido de que se les puede enviar invocaciones (en mi caso eventos), y los actores responden ejecutándolos, como los objetos normales. No obstante, son diferentes porque las invocaciones se ejecutan de manera que no causan problemas de concurrencia. ¿Cómo? Pues asegurando que todas las invocaciones sobre un actor se ejecutan en un mismo hilo. En este sentido, un actor también aglutina, en general, un hilo de ejecución propio en el que se ejecutan las llamadas al mismo (esto puede no ser así exactamente, pero la idea es la misma).

Existe una diferencia con los paradigmas tradicionales de programación. Por ejemplo, para no causar problemas de concurrencia, todos los métodos de un objeto se podrían marcar como «synchronized» al estilo de Java. Esto, efectivamente, hace que no haya problemas de concurrencia (al menos los más usuales), ya que todas las invocaciones a un objeto se realizan en exclusión mutua. Sin embargo, una invocación a objeto normal lleva consigo asociada un hilo de ejecución, y el hilo de ejecución del objeto llamante es el que realiza la llamada al objeto llamado, con lo que también se tienen que prevenir problemas como interbloqueos, esperas de candados, etc.

En resumen, sería casi como un sistema basado en eventos en donde los objetos se envían mensajes que son a su vez procesados en los hilos respectivos de cada actor. Ahora bien, ¿cómo implementar en C++ este mecanismo sin ser excesivamente intrusivo, teniendo en cuenta que el mecanismo de envío de eventos no existe en C++? Pensé en utilizar boost.signal, pero éste no asegura que el objeto receptor va a ejecutar la señal en su propio hilo. Los requisitos que establecí pues para el desarrollo fueron los siguientes:

  1. El mecanismo debe ser poco intrusivo, en el sentido de que las clases que quieran beneficiarse de este mecanismo no tienen por qué escribirse heredando de un interfaz en particular, sino que sólo tienen que definir una serie de tipos para saber tratarlas como actor.
  2. Cualquier clase puede definir de manera sencilla qué eventos puede recibir y cómo actuará ante cualquier evento, y estos serán los únicos requisitos que tendrá que especificar la clase.
  3. Las clases pueden modificar de forma sencilla qué eventos producen y reciben.
  4. Las clases no tendrán que preocuparse de tratar con hilos, asincronía, almacenamiento y reproducción de eventos, etc.
  5. El mecanismo de envío de eventos debe estar integrado en el lenguaje C++ de forma natural. Por ejemplo, con un operador que muestre que se está enviando un evento: objeto << mensaje;.

Con estos requisitos, pensé hacer la clase actor que pudiera aceptar como parámetro cualquier otra clase, y convertirla así en un actor. Este mecanismo es poco intrusivo, sólo obligando a que la clase que se quiere beneficiar de este mecanismo especifique qué eventos es capaz de recibir. La clase actor que me quedó fue la siguiente, con comentarios al estilo de la literate programming (si alguien está interesado le puedo pasar el código sin los comentarios):

template <typename Klass>
struct actor
{
    typedef typename Klass::events_type VariantType;

Uno de los requisitos que tiene que proveer la clase que se va a convertir en actor es ofrecer el tipo VariantType con los distintos eventos que va a poder recibir. Para esto se usará el tipo boost.variant como se verá después.

    typedef actor<Klass> self;

    actor (Klass& a)
        : delegate_ (a)
    {
        thread_ = boost::thread (boost::ref (*this));
    }

Cada actor posee su propio hilo. Esto, por supuesto puede modificarse después. Sólo quería hacer una prueba de concepto. En scala existen schedulers que enlazan actores con hilos.

    // Thread func.
    void operator()()
    {
        std::cout << “running thread” << std::endl;

        while(!stop_)
        {
            bool b;
            {
                boost::lock_guard<boost::mutex> guard (list_mutex_);
                b = el_.empty();
            }

            if (b)
            {
                boost::unique_lock<boost::mutex> lock (mut_);

                // wait on the cond. var.

                cond_.wait (lock);
            }

            while (true)
            {
                VariantType vtv;
                {
                    boost::lock_guard<boost::mutex> guard (list_mutex_);
                    if (el_.empty())
                        break;

                    vtv = el_.front();
                    el_.pop_front();
                }

                // Call the delegate without holding the mutex locked

                boost::apply_visitor (detail::event_caller<Klass> (delegate_),
                                      vtv);
            }
        }
    }

El operator()() de la clase actor ejecuta el código del hilo. He utilizado variables de condición porque me parecen más ricas semánticamente. El hilo básicamente extrae eventos de la cola de eventos y los ejecuta sobre el delegate. Como los eventos de la cola pueden ser de diferentes tipos (nótese que este punto es especialmente difícil en C++), hay que utilizar estructuras que permitan tratar diferentes tipos de eventos de forma genérica. Para eso he usado la construcción boost::apply_visitor de boost.variant. Con el uso de una clase especial, detail::event_caller, que se verá más abajo, se consigue llamar a la clase original, a los métodos process(Evento), para cada uno de los eventos recibidos.

    template <typename Event>
    self& operator<<(Event& e)
    {
        std::cout << “Received event” << std::endl;
        {
            boost::lock_guard<boost::mutex> lock (list_mutex_);
            el_.push_back (e);
        }

        // signal that a new event is available

        cond_.notify_one();

        return *this;
    }

El operador << se puede usar para enviar un evento al actor. Esta es una construcción que queda muy natural. Enviar un mensaje es diferente a realizar una llamada, aunque también se puede pensar en un mecanismo de llamada a función modificado. Al final, el envío de mensajes, como se verá después, será algo así como actor << Clase::Evento(valores);.


    void join()
    {
        thread_.join();
    }

    void stop()
    {
        stop_ = true;
        cond_.notify_one();
    }

private:
    Klass& delegate_;

    typedef std::deque<VariantType>  event_list;
    event_list el_;
    bool stop_; // stop?

    boost::thread thread_;

    boost::mutex mut_;
    boost::mutex list_mutex_;
    boost::condition_variable cond_;
};

Por completitud, aquí está la clase detail::event_caller. Es necesaria para visitar un tipo boost.variant a través de la función boost::apply_visitor. Simplemente llama a la función process() correspondiente.

namespace detail

{

template <typename Klass>
struct event_caller : public boost::static_visitor<>

{
    Klass& instance_;

    event_caller (Klass& i)
        : instance_ (i)
    {
    }

    template <typename T>

    void operator()( T const & operand ) const
    {
        instance_.process (operand);
    }
};
}

Llegamos a la clase sobre la que queremos construir el actor, llamada para este ejemplo TestClass. La clase define internamente un par de eventos (Event1 y Event2), y, como comentamos arriba, el tipo events_type, como un boost.variant de los diferentes eventos que puede recibir. Se pueden ver los métodos process() más abajo. En este caso la clase tiene métodos propios para retornar un actor interno. Esto no tiene por qué ser así, y como se ha visto, los actores son independientes de las clases de las que actúan en representación.

class TestClass
{
public:
    typedef actor<TestClass> actor_type;

    struct Event1

    {
        int data;
    };

    struct Event2
    {
        std::string ss;
    };

    // Obligatory

    typedef boost::variant< Event1, Event2 > events_type;

    actor_type& the_actor()
    {
        return *actor_;
    }

    // Ctor.

    TestClass()
        : actor_ (new actor_type (*this))
    {
    }

    ~TestClass()
    {
        actor_->stop();
        actor_->join();
        delete actor_;
    }


private:
    actor_type* actor_;

public:
    void process (Event1 const& e)
    {
        std::cout << “Processed event: “  << e.data << std::endl;
    }

    void process (Event2 const& e)
    {
        std::cout << “Processed event 2: “  << e.ss << std::endl;
    }
};

Por último, ¿cómo se usa este mecanismo de actores? Lo ideal es proveer de mecanismos que sean semánticamente ricos y que sigan el principio de mínima sorpresa. Con las clases de arriba podemos escribir código sencillo como el siguiente:

    TestClass::Event1 ev;
    ev.data = -2;

    TestClass::Event2 ev2;
    ev2.ss = “abcdef.”;

    TestClass tc;

    TestClass::actor_type& ac = tc.the_actor();

Primero se crean un par de eventos de los dos tipos que puede recibir la clase TestClass, y se obtiene el actor ac. Se puede usar ese actor para enviar eventos a la clase:

    // Send the event2
    ac << ev2;

    // Send message
    ac << ev;
    for (int i = 0; i < 2000; ++i)
    {
        ev.data = i;
        ac << ev;
        ac << ev2;
    }

Aquí se envía primero un evento de tipo Event1, y luego otro del tipo 2. Después se entra en un bucle que envía ambos mensajes, modificando el primer evento con un dato distinto. El programa va mostrando la salida de eventos de la clase en orden:

...
Processed event: 1996
Processed event 2: abcdef.
Processed event: 1997
Processed event 2: abcdef.
Processed event: 1998
Processed event 2: abcdef.
Processed event: 1999
Processed event 2: abcdef.

Un último apunte. Las diferencias con los actores de otros lenguajes dinámicos (Scala, por ejemplo), son que en estos lenguajes se puede especificar un procesado basado en máquinas de estados, como por ejemplo, cuando se recibe el evento 1, después sólo se puede recibir el evento 2. Esta máquina de estados se puede implementar. Es una primera implementación de prueba.

No dudéis en contactar conmigo para ideas o comentarios.