(blog ‘lucindo)

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