(blog ‘lucindo)

Para testar algumas coisas refiz hoje o código do post Common Lisp e Ajax. Desta vez estou usando o patch para o HT-AJAX com suporte e jQuery. Além disso, para gerar código JavaScript uso Parenscript. Assim todo HTML e JS é produzido por s-exps:

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter *dependencies*
    ‘(:asdf :hunchentoot :ht-ajax :cl-who :parenscript))
  (map nil ‘require *dependencies*))

(defpackage :ajax-test
  (:use :common-lisp :hunchentoot :ht-ajax :cl-who :parenscript))

(in-package :ajax-test)

(defparameter *local-dir* “/Users/lucindo/Documents/Lisp/web/3rdparty/”)
(defparameter *ajax-handler-url* “/ajax”)
(defparameter *ajax-processor*
  (make-ajax-processor :type :jquery
                       :server-uri *ajax-handler-url*
                       :js-file-uris “/static/jquery.js”))

(defun testfunc (command)
  (prin1-to-string (handler-case (eval (read-from-string command nil))
                                 (error (c) (format nil “~a” c)))))

(defun js ()
  (ps
   (defun command_clicked ()
     (let ((command (document.get-element-by-id “command”)))
       (with-slots (value) command
                   (ajax_testfunc_set_element “result” value))))))

(defun main-page ()
  (with-html-output-to-string
   (*standard-output* nil :prologue t)
   (:html
    (:head
     (:script :type “text/javascript” :src “/js”)
     (:title “AJAX test”)
     (fmt “~a” (generate-prologue *ajax-processor*)))
    (:body
     (:h1 “ajax test”)
     (:table :width “50%”
             (:tr
              (:td :colspan “2″
                   (:span :id “result”
                          (:i “no results yet”))))
             (:tr
              (:td :width “70%”
                   (:input :type “text”
                           :size “70″
                           :name “command”
                           :id “command”))
              (:td (:input :type “button”
                           :value “eval”
                           :onclick (ps-inline (command_clicked))))))))))

(eval-when (:load-toplevel :execute)
  (export-func *ajax-processor* ‘testfunc :method :post)
  (setf *dispatch-table*
        (list ‘dispatch-easy-handlers
              (create-folder-dispatcher-and-handler “/static/”
                                                    *local-dir* “text/plain”)
              (create-prefix-dispatcher *ajax-handler-url*
                                        (get-handler *ajax-processor*))
              (create-prefix-dispatcher “/js” ‘js)
              (create-prefix-dispatcher “/” ‘main-page))))

(defparameter *webserver* nil)

(defun start-web (&optional (port 4242))
  (setf *webserver* (start-server :port port)))

(defun stop-web ()
  (stop-server *webserver*))

Download: ajax2.lisp

HT-AJAX (documentação aqui) é uma extenção do Hunchentoot que permite exportar suas funções lisp de modo que elas podem ser acessadas via JavaScript, usando AJAX. Um pequeno exemplo de uso dessa biblioteca está nesse post.

HT-AJAX suporta vários AJAX processors, como Prototype e Dojo, mas não jQuery. Então fiz um pequeno patch adicionando suporte a jQuery.

Download: ht-ajax_0.0.7-jquery.patch

Aplicando o patch (SBCL):

$ cd ~/.sbcl/site/ht-ajax_0.0.7
$ wget http://lucindo.com.br/lisp/ht-ajax_0.0.7-jquery.patch
$ cat ht-ajax_0.0.7-jquery.patch | patch -p0
$ sbcl
* (require :asdf)
* (asdf:oos 'asdf:compile-op :ht-ajax)

Warning: Isso deve ser muito manjado, eu que nunca tinha visto. Estou escrevendo só para não esquecer

Imagine o seguinte caso de uma aplicação web: o usuário executa uma ação e o servidor apenas precisa ser notificado, todos os dados necessários para uma eventual alteração da tela já estão presentes. É o caso por exemplo de marcar um item (star-it), votar em um sistema de ratings, adicionar uma tag a um item, e por aí vai.

Podemos fazer da seguinte maneira: um link que o usuário vai clicar para executar uma ação:

<a id=’a_theid’ onclick=“return ajax(this)” href=“/action?user=x&a=y”>

Nesse link, no campo id colocamos uma codificação simples de um eventual objeto a ser alterado, nesse caso usamos a_theid, onde deve um existir um objeto na página com o id theid que poderá ser alterado. A URL que fará a notificação da execução no server esta no href. Dessa forma podemos implementar a função JavaScript ajax assim:

function ajax(node) {
    var v = node.id.split(/_/); // a_theid
    var item = v[1]; // theid

    // Executa a alteração de tela
    document.getElementById(item).innerHTML = …

    // notifica o servidor
    var action = new Image();
    action.src = node.href;

    return false;
}

O browser carrega imagens de forma assíncrona, então essa função não bloca, a alteração na tela é feita na hora e o server é notificado. A vantagem é que isso funciona em qualquer browser, mesmo alguns bem velhos.

Bom, a desvantagem é que você não sabe se o request falhou. Mas isso pode acontecer em poucos casos como:

• O servidor está fora do ar: assim o usuário não conseguirá continuar navegando no sistema por muito tempo sem perceber isso, e o número de usuários que acessou o sistema antes dele cair e tem como executar umas ações que vão falhar (sem ele saber) é reduzido. E nessa caso o que você ia fazer? Cuspir um alert na cara do usuário com “Ooops, We did it again!“?
• Existe um problema de rede entre a máquina do usuário e o servidor: isso recai no problema acima, tem o mesmo efeito.
• O servidor está se comportando de maneira inesperada, gerando erros: aí amigo, o AJAX é o menor dos seus problemas.

Bom, eu vi isso no código do YCombinator News (Hacker News). Dá uma olhada lá para ver isso funcionando. Já o Digg e o Reddit usam Prototype. Alias, o Reddit poderia usar isso, pois eles não passam uma função de callback no caso de erro do Ajax.Request. Já o Digg passa uma função com um alert “ERROR: …”

E não é que funciona! Usei:

• Hunchentoot
• HT-AJAX
• CL-WHO

(eval-when (:compile-toplevel :load-toplevel :execute)
  (require :hunchentoot)
  (require :cl-who)
  (require :ht-ajax))

(defpackage :ajax-test
  (:use :cl :hunchentoot :cl-who)
  (:export #:start-web #:stop-web))

(in-package :ajax-test)

;; local directory with lokris.js
(defparameter */static-local-dir* “/Users/lucindo/Documents/Lisp/tmp/”)
;; can be any url
(defparameter *ajax-handler-url* “/ajax”)
;; using lokris (very small)
(defparameter *ajax-processor* (ht-ajax:make-ajax-processor
                                :type :lokris
                                :server-uri *ajax-handler-url*
                                :js-file-uris “/static/lokris.js”))

;; hunchentoot handlers setup
(eval-when (:compile-toplevel :load-toplevel :execute)
  (setf *dispatch-table*
        (list ‘dispatch-easy-handlers
              (create-folder-dispatcher-and-handler “/static/”
                                                    */static-local-dir*
                                                    “text/plain”)
              (create-prefix-dispatcher *ajax-handler-url*
                                        (ht-ajax:get-handler
                                         *ajax-processor*))
              (create-prefix-dispatcher “/js” ‘java-script)
              (create-prefix-dispatcher “/” ‘main-page))))

(defparameter *web-server* nil)

(defun start-web (&optional (port 4242))
  (setf *web-server* (start-server :port port)))

(defun stop-web ()
  (stop-server *web-server*))

;; eval and print a lisp expression
(defun testfunc (command)
  (prin1-to-string (eval (read-from-string command nil))))
(ht-ajax:export-func *ajax-processor* ‘testfunc :method :post)

(defun java-script ()
  “function command_clicked(txt) {
    var command = document.getElementById(’command’).value;
    ajax_testfunc_set_element(’result’, command); }”)

(defun main-page ()
  (with-html-output-to-string (*standard-output* nil :prologue t)
    (:html
     (:head
      (:script :type “text/javascript” :src “/js”)
      (:title “AJAX test”))
      (fmt “~a” (ht-ajax:generate-prologue *ajax-processor*))
     (:body
      (:h1 “AJAX test”)
      (:table :width “50%”
              (:tr
               (:td :colspan “2″
                    (:span :id “result”
                           (:i “no results yet”))))
              (:tr
               (:td :width “70%”
                    (:input :type “text”
                            :size “70″
                            :name “command”
                            :id “command”))
               (:td
                (:input :type “button”
                        :value “Eval”
                        :onclick “javascript:command_clicked();”))))))))

Source: ajax-test.lisp (nele mudei para usar Prototype. O legal é o que o HT-AJAX suporta vários processadores ajax: Lokris, Prototype, Dojo, Yahoo! [YUI]).

Se você também não gosta de HTML junto com código pode usar HTML-TEMPLATE. Se você não gosta mesmo de HTML pode usar o Weblocks em que o design fica em CSS e o resto é codigo Lisp (o framework gera todo o HTML e JavaScript para AJAX).

Quase tudo tendo como base Ediware.

Tem gente que acredita que algoritmos e linguagens de programação são dois mundos distintos. Eu discordo. São raríssimas as pessoas que conseguem separar as duas coisas, incluse eu e você que está lendo isso.

Pegue qualquer livro de introdução a algoritmos e estrutura de dados, pode até mesmo ser um clássico. Os algoritmos são dados em uma linguagem de programação. Pseudo-código é baseado numa linguagem de programação. Todo pseudo-código que eu conheço é pseudo-C ou pseudo-Pascal (um pseudo-Algol-like), inclusive a maioria dos que eu escrevo (pelo menos até agora).

Quando pensamos num problema e estamos desenvolvendo um algoritmo para resolvê-lo estamos limitados às ferramentas de construção de algoritmos que conhecemos, que aprendemos. Mas mais do que isso, acabamos usando as que estamos mais acostumados. Um exemplo disso são algoritmos recursivos. Eu conheço um sem número de programadores com uma dificuldade tremenda de entender recursão. Eu sei que é um exemplo simples e que todo programador deveria saber recursão. Mas pegue uma linguagem mainstream, escolha um projeto qualquer open source e veja quantas definições recursivas você encontra.

Digo isso por experiência própria. Eu aprendi e entendi recursão como todo mundo no curso de computação, mas eu quase nunca pensava recursivamente. Quando eu fui programar em Erlang pela primeira vez, de cara o obstáculo foi single assignment. “Como assim eu não posso fazer i++?”. “Não dá pra fazer quase nada se não dá pra fazer i++!”. “Que linguagem tosca!!”. Acontece que dá para fazer de tudo sem i++ e coisas assim te forçam a exercitar outras formas de resolver problemas, como usar recursão e todo pensamento indutivo que você precisa para isso.

Mas como eu disse, recursão é um exemplo tolo. O grande problema que eu vejo é que o Blub Paradox está diretamente ligado não apenas à linguagem de programação mas também na forma como pensamos e resolvemos problemas, ou seja, como desenvolvemos algortimos.

Agora um exercício de uma dessas coisas que a maioria das pessoas acha perda de tempo.

Segundo a Wikipedia Memoização é: “… memoization is an optimization technique used primarily to speed up computer programs by storing the results of function calls for later reuse, rather than recomputing them at each invocation of the function…“.

Memoização é uma técnica, assim como muitas outras coisas, como backtracking, como programação dinânima, como divisão e conquista. E porque não como design patterns? São técnicas.

Fica difícil definir memoização como um algoritmo em pseudo-código, mas não porque não seja possível, mas porque falta alguma coisa no pseudo-código, no pseudo-C. Memoização poderia se resumir simplesmente ao algoritmo memoizar que recebe como entrada uma função e devolve a mesma função memoizada. Tendo esse algoritmo seria possível escrever algo assim em JavaScript:

function fib(n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

function test(n) {
    var t1 = new Date();
    var v = fib(n);
    var t2 = new Date();
    print(“fib(”+ n + “) = “+ v + ” took: “ + (t2 - t1) + ” ms”);
}

function runtest() {
    test(42);
    fib = memoize(fib);
    test(42);
}

Dessa forma seria natural pensar que utilizando a função memoize a segunda chamada a test(42) fosse mais rápida que a primeira. De fato, é o que realmente acontece:

fib(42) = 267914296 took: 279094 ms
fib(42) = 267914296 took: 20 ms


A implementação de memoize é simples numa linguagem de programação com suporte a higher-order functions, mas eu não sei fazer algo parecido numa linguagem como Java/C# (por exemplo).

function memoize(fun) {
    var cache = new Array();
    return function () {
        arguments.toString = Array.prototype.toString;
        if (cache[arguments.toString()] == undefined) {
            var value = fun(arguments);
            cache[arguments.toString()] = value;
        }
        return cache[arguments.toString()];
    }
}

Essa é uma idéia de memoização que o Peter Norvig apresenta no PAIP.
De novo, isso não serve para nada, além claro de mudar um pouco a maneira como pensamos em resolver problemas. Alguns que concordam:

Lisp has jokingly been called “the most intelligent way to misuse a computer”. I think that description is a great compliment because it transmits the full flavor of liberation: it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts.

Edsger Dijkstra, CACM, 15:10

Lisp is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days, even if you never actually use Lisp itself a lot.

Eric Raymond

Lisp … made me aware that software could be close to executable mathematics.

L. Peter Deutsch

Although my own previous enthusiasm has been for syntactically rich languages, like the Algol family, I now see clearly and concretely the force of Minsky’s 1970 Turing Lecture, in which he argued that Lisp’s uniformity of structure and power of self reference gave the programmer capabilities whose content was well worth the sacrifice of visual form.

Robert Floyd, Turing Award Lecture, 1979

Mais uns códigos continuando as idéias do post sobre closures, só que em JavaScript (acho que mais gente entende JavaScript do que Ruby).
Antes de mais nada: códigos e inspirações do SICP (video-aulas aqui).

Bom, anteriormente cons, car e cdr foram definidos assim:

function cons(a, b) {
    return function(first) {
        return first ? a : b;
    }
}

function car(c) {
    return c(true);
}

function cdr(c) {
    return c(false);
}

Com isso acabamos definimos um padrão de como representar listas e operar nelas, e o mais legal, tudo construido do “nada”, apenas com lambdas. Uma maneira um pouco diferente de definir essas três funções é dada a seguir. Gerald Jay Sussman chamou de “Alonzo Church’s hack”:

function cons(x, y) {
    return function(m) {
        return m(x, y);
    }
}

function car(x) {
    return x(function(a, d) { return a; });
}

function cdr(x) {
    return x(function(a, d) { return d; });
}

As duas implementações são praticamente equivalentes, só que essa segunda é feita excusivamente de lambdas (na primeira temos um condicional na definição de cons) e além disso ela traz o controle para o car e cdr, e o cons passa apenas a ser um dispatcher. Agora conseguimos introduzir operações para alterar uma lista feita a partir de conses:

function cons(x, y) {
    return function (m) {
        return m(x, y, function (n) { x = n }, function (n) { y = n });
    }
}

function car(x) {
    return x(function (a, d, sa, sd) { return a; });
}

function cdr(x) {
    return x(function (a, d, sa, sd) { return d; });
}

Agora, no dispatcher (cons) adicionamos duas outras operações, que são usadas a seguir para alterar o valor do car ou do cdr de um cons:

function setcar(x, y) {
    return x(function (a, d, sa, sd) { sa(y); });
}

function setcdr(x, y) {
    return x(function (a, d, sa, sd) { sd(y); });
}

As funções list, mapcar, reduce e filter permanecem como definidas nos outros posts:

function list() {
    arguments.shift = Array.prototype.shift;
    if (arguments.length == 0) {
        return null;
    } else {
        return cons(arguments.shift(), list.apply(this, arguments));
    }
}

function mapcar(fun, lst) {
    if (null == lst) {
        return null;
    } else {
        return cons(fun(car(lst)), mapcar(fun, cdr(lst)));
    }
}

function reduce(fun, init, lst) {
    if (null == lst) {
        return init;
    } else {
        return fun(car(lst), reduce(fun, init, cdr(lst)));
    }
}

function filter(fun, lst) {
    if (null == lst) {
        return null;
    } else {
        if (fun(car(lst))) {
            return cons(car(lst), filter(fun, cdr(lst)));
        } else {
            return filter(fun, cdr(lst));
        }
    }
}

Uma nova função que podemos escrever agora que é possível alterar uma lista é append:

function append() {
    var lst = null;
    var i = 0;
    for (; i < arguments.length && null == lst; i++) {
        if (null != arguments[i]) {
            lst = copylist(arguments[i]);
        }
    }
    for (; i < arguments.length; i++) {
        if (null != arguments[i]) {
            setcdr(last(lst), copylist(arguments[i]));
        }
    }
    return lst;
}

As duas funções auxiliares que append usa são:

function last(lst) {
    if (null == lst) {
        return null;
    } else if (null == cdr(lst)) {
        return lst;
    } else {
        return last(cdr(lst));
    }
}

function copylist(lst) {
    return mapcar(function (x) { return x; }, lst);
}

Mas append não precisa ser implementada necessáriamente usando funções destrutivas, e de fato, mesmo nessa implementação temos que é uma função pura. Usei append nesse exemplo porque é uma função simples e nos permite fazer algumas coisas legais como:

function qsort(lst) {
    if (null == lst) {
        return null;
    } else {
        var pivot = car(lst);
        var nlst = cdr(lst);
        return append(qsort(filter(function (x) { return x < pivot; }, nlst)),
                      list(pivot),
                      qsort(filter(function (x) { return x >= pivot; }, nlst)));
    }
}

Ou mesmo:

function powerset(lst) {
    if (null == lst) {
        return null;
    } else {
        var first = car(lst);
        var rest  = powerset(cdr(lst));
        return append(list(list(first)),
                      mapcar(function (x) { return append(list(first), x); }, rest),
                      rest);
    }
}

De novo rodei tudo isso com o Rhino. Mais brincadeiras desse tipo nos próximos posts

Implementação do código do post sobre closures em JavaScript (com umas coisinhas a mais):

function cons(a, b) {
    return function(first) {
        return first ? a : b;
    }
}

function car(c) {
    return c(true);
}

function cdr(c) {
    return c(false);
}

function list() {
    arguments.shift = Array.prototype.shift;
    if (arguments.length == 0) {
        return null;
    } else {
        return cons(arguments.shift(), list.apply(this, arguments));
    }
}

function mapcar(fun, lst) {
    if (null == lst) {
        return null;
    } else {
        return cons(fun(car(lst)), mapcar(fun, cdr(lst)));
    }
}

function reduce(fun, init, lst) {
    if (null == lst) {
        return init;
    } else {
        return fun(car(lst), reduce(fun, init, cdr(lst)));
    }
}

function filter(fun, lst) {
    if (null == lst) {
        return null;
    } else {
        if (fun(car(lst))) {
            return cons(car(lst), filter(fun, cdr(lst)));
        } else {
            return filter(fun, cdr(lst));
        }
    }
}

Um teste tosto:

var lst = list(1, 2, 3, 4);
mapcar(print, lst);
print(reduce(function (a, b) { return a + b; }, 0, lst));
mapcar(print, filter(function (a) { return a % 2; }, lst));

Para rodar, usei o Rhino.