(blog ‘lucindo)

Seguindo instruções do Herrmann..

algor:~ lucindo$ ghci
   ___         ___ _
  / _  /  // __(_)
 / /_// /_/ / /  | |      GHC Interactive, version 6.6.1, for Haskell 98.
/ /_\/ __  / /___| |      http://www.haskell.org/ghc/
____// /_/____/|_|      Type : ? for help.

Loading package base ... linking ... done.
Prelude> let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> take 10 fibs
[1,1,2,3,5,8,13,21,34,55]
Prelude> zip [1..] "lisp"
[(1,'l'),(2,'i'),(3,'s'),(4,'p')]
Prelude>

Achei muito doce.

However, C++ isn’t meant to be everything to everybody. No one programming language and no one view of how to write programs is sufficient for everything. Constraints-based programming, logic programming, functional programming, and various forms of concurrent programming are examples of good and useful styles of programming not supported by C++.

Bjarne Stroustrup, em Why C++is not just an Object-Oriented Programming Language

Um trecho de código em ANSI Common Lisp:

(defun -cons (a d)
  #’(lambda (m)
      (funcall m a d)))

(defun -car (c)
  (funcall c #’(lambda (a d) a)))

(defun -cdr (c)
  (funcall c #’(lambda (a d) d)))

O mesmo em Scheme:

(define (-cons a d)
  (lambda (m)
    (m a d)))

(define (-car c)
  (c (lambda (a d) a)))

(define (-cdr c)
  (c (lambda (a d) d)))

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