Ideias poderosas por trás de uma piada

Ricardo Bánffy fez uma piada de 1º de abril no ano passado lançando um pretenso framework em Lisp chamado Kanamit.

No entanto a parte da piada é somente o terceiro tópico do texto e o Bánffy aproveitou o ar de piada para rasgar o verbo e dizer umas verdades sem medo.

Como concordo quase 100% com o texto, decidi reproduzi-lo aqui de forma séria:

Eu sempre gostei de escrever aqui sobre linguagens «exóticas». Já houve um tempo em que Python era exótico. Hoje Python é mainstream. Ruby, idem. Há até suporte a Rails no NetBeans 6 e para Python no Visual Studio. Não dá pra ser muito mais mainstream do que isso.

Nem todas as linguagens exóticas que eu conheci deram certo. Smalltalk, por exemplo, continua sendo aquela linguagem muito sofisticada, anos-luz à frente do Java, mas que quase ninguém usa. Smalltalk tem ideias poderosas demais. A ideia de rodar dentro de uma máquina virtual, de todo o código poder ser examinado e modificado «ao vivo», do compilador incremental, do class browser, do late-binding, das mensagens... Tudo isso era demais pras cabecinhas da maioria dos programadores que só conseguem entender Visual Basic ou PHP e olha lá.

Mas «Visual Basic e PHP resolvem todos os meus problemas», dizem eles. Claro. Se tudo o que eles conhecem se resume a isso, eles não imaginam sequer que existam outros tipos de problema. É uma limitação de capacidade expressiva: eles não têm as ferramentas intelectuais necessárias para expressar as classes de problemas que outras ferramentas expressam e resolvem.

Não se pode pensar em uma lâmpada fluorescente se tudo o que você conhece são pedras lascadas e peles de urso.

Uma outra linguagem muito além do seu tempo é o Lisp. Além do seu tempo porque, se ela é uma coisa poderosa hoje comparada ao que temos hoje, imaginem em 1960 quando ela foi inventada…

Por muito tempo, havia implementações de Lisp para computadores desktop, mas, com processadores de 16 bits e menos de um megabyte de RAM, essas máquinas serviam apenas como brinquedos. Você podia fazer um loop e imprimir 10 vezes «fulano é bobo», mas não muito mais do que isso.

Naquele tempo, para se rodar programas em Lisp, você precisaria de uma Lisp machine, um computador dedicado, com um processador único capaz de coisas que nenhum outro processador da época – ou de hoje – era capaz de fazer. Eram incrivelmente caras.

Mas as implementações de brincquedo eram o bastante para abrir as cabeças dos jovens computólogos (antes deles se chamarem assim). Lisp e Scheme (um dialeto de Lisp) são usados como ferramenta didática em todos os bons cursos de ciência da computação. Se no seu curso não tem, pare de perder tempo e paça seu dinheiro de volta. Não sei quanto é a mensalidade, mas é certo que o curso vale menos.

E, claro, hoje em dia, temos computadores amplamente capazes de rodar boas implementações de Lisp. Meu notebook consegue emular uma Lisp machine da Texas Instruments (uma Micro-Explorer) mais depressa do que ela era originalmente.

Artigo original: O Kanamit Web Framework.

[]'s
Cacilhas, La Batalema

Mais sobre programação funcional

Aproveitando o ensejo do artigo anterior sobre programação funcional, gostaria de puxar mais este artigo sobre três algoritmos tradicionais: sequência de Fibonacci, fatorial e quick sort.

Fatorial

Fatorial é um dos algoritmos recursivos mais tradicionais da Matemática. É também um dos algoritmos mais simples:


Sua implementação tanto em Haskell quanto em Common Lisp descreve exatamente esse algoritmo.

Em Haskell:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * (factorial (n - 1))

Em Common Lisp:

(defun factorial ((n integer))
  (if (= n 0)
    n
    (* n (factorial (- n 1)))))

Já em Scheme a coisa pode complicar… se o interpretador (uso guile) tiver sido compilado com suporte a bignum, tudo bem, se não, é preciso fazer uma pequena mágica, multiplicando os resultados do maior para o menor:

(define (factorial n)
  (define (loop k l)
    (if (zero? k)
      l
      (loop (- k 1) (* k l))))
  (loop n 1))

Sequência de Fibonacci

A Sequência de Fibonacci é uma progressão natural iniciando por 1, 1 e progredindo ao passo de que cada elemento é a soma dos dois anteriores:


É uma sequência recursiva em árvore binária, o pesadelo dos programadores. =D

Mas como já foi muito estudada, há diversas formas de implementá-la sem usar código recursivo, como algoritmo reiterativo, potência de matrizes e função fechada.

A seguinte implementação em Haskell utiliza recursão e lista infinita:

fib :: [Integer]
fib = 1 : 1 : zipWith (+) fib (tail fib)

Já em Common Lisp foi uma boa ideia usar reiteração, muito mais elegante do que seria possível em qualquer linguagem imperativa:

(defun fib (index)
  (check-type index (integer 0 *))
  (loop
    for a = 1 then b
    and b = 1 then (+ a b)
    repeat index
    finally (return a)))

Quick sort

O algoritmo de ordenação quick sort é a exceção das exceções: um algoritmo de ordenação recursivo em árvore binária, o que deveria ser o pior dos casos, no entanto é um dos métodos de ordenação mais rápidos e eficientes que conhecemos.

O princípio é o seguinte: toma-se um elemento qualquer da lista, tradicionalmente o primeiro, então separa-se a lista em duas, uma de elementos menores que o tomado e outra de elementos maiores. Aplica-se a mesma ordenação quick sort a cada uma das novas listas e concatena-as com o elemento tomado no meio.

Em Haskell isso pode ser descrito assim:

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
    where
        lesser =  [e | e <- xs, e < x]
        greater = [e | e <- xs, e >= x]

Em Common Lisp o princípio é o mesmo, mas com aquele monte de parêntesis característicos de Lisp:

(defun qsort ((a-list list))
  (if (< (length a-list) 2)
    a-list
    (let ((x (pop a-list)))
      (concatenate 'list
        (qsort
          (loop for e in a-list
            if (< e x)
              collect e))
        (list x)
        (qsort
          (loop for e in a-list
            if (>= e x)
              collect e))))))

**

Espero que este artigo tenha sido interessante e cause curiosidade aos leitores sobre programação funcional.

[]'s
Cacilhas, La Batalema

Oddwording de novo

Em maio de 2007 publiquei um artigo sobre a implementação do algoritmo oddwording em diversas linguagens de programação.

Para relembrar, segue o código em Haskell:

module Main where

import IO


main = mainloop


mainloop :: IO ()
mainloop = do
    ph <- readString
    if ph == ""
        then
            return ()
        else do
            let nph = oddword ph
            putStrLn nph
            mainloop


readString :: IO String
readString = do
    putStrLn "Digite uma frase: "
    putStr "> "
    hFlush stdout
    s <- getLine
    return s


oddword :: String -> String
oddword s = listToStr $ invodd $ strToList s


strToList :: String -> [String]
strToList "" = []
strToList s = (take spi s) : (strToList (drop (incr spi) s))
    where spi = nextspace s


incr :: Int -> Int
incr = (+ 1)


nextspace :: String -> Int
nextspace "" = 0
nextspace (x:xs) =
    if x == ' '
        then
            0
        else
            1 + (nextspace xs)


listToStr :: [String] -> String
listToStr [] = ""
listToStr (x:xs) = x ++ " " ++ (listToStr xs)


invodd :: Ord a => [[a]] -> [[a]]
invodd [] = []
invodd (x:xs) = x : (inveven xs)


inveven :: Ord a => [[a]] -> [[a]]
inveven [] = []
inveven (x:xs) = (inv x) : (invodd xs)


inv :: Ord a => [a] -> [a]
inv [] = []
inv (x:xs) = (inv xs) ++ [x]

<update ressaca>
Havia esquecido de forçar o flush de STOUT na função readString. Corrigido!
</update>

No entanto ficou faltando uma linguagem excepcionalmente importante, Lisp.

Lisp (LISt Processing) é uma família de linguagens funcionais concebida por John McCarthy em 1958, baseada no cálculo lambda. As principais linguagens da família Lisp são Common Lisp, Scheme e Emacs Lisp.

O código acima será reimplementado abaixo em Common Lisp.

Observação: os blocos de código deverão ser escritos em arquivo na ordem inversa em que aparecem aqui, ou seja, digite cada bloco no arquivo em linhas acima do bloco digitado anteriormente.

Ciclo principal

O ciclo principal será a função mainloop. Sua lógica de funcionamento é a seguinte:

1. Pegar uma string digitada na entrada padrão;
2. Se a string for vazia, sair do programa;
3. Aplicar o algoritmo oddwording;
4. Exibir na tela o resultado;
5. Recomeçar o ciclo.

A função fica assim:

(defun mainloop ()
  (loop do
    (format t "~&~a~%"
      (oddword (*exit-if-empty* (*read-string*))))))

Lendo uma linha da entrada padrão

Para ler uma linha da entrada padrão, devemos exibir um prompt, ler a entrada digitada pelo usuário e remover os espaços em branco do começo e do fim:

(defun *read-string* ()
  (format t "~&Digite uma frase:~%> ")
  (string-trim " " (read-line)))

Saindo caso a string esteja vazia

Caso nada tenha sido digitado, o programa encerra. Para isso é preciso avaliar a string, encerrando o processo se apropriado, caso contrário retornar a string:

(defun *exit-if-empty* ((a-string string))
  (if (string= a-string "")
    (exit)
    a-string))

Descrição do algoritmo em alto nível

Podemos agora definir em alto nível o algoritmo oddwording:

1. Transformar a string em uma lista de palavras;
2. Inverter somente o conteúdo dos elementos de índice ímpar da lista;
3. Transformar novamente a lista de palavras em uma string.

(defun oddword ((a-string string))
  (list-to-str (invodd (str-to-list a-string))))

String para lista

Para transformar uma string em uma lista, basta quebrada em cada ocorrência de espaço (#\Space):

(defun str-to-list ((a-string string))
  (loop
    for i = 0 then (1+ j)
    as j = (position #\Space a-string :start i)
    collect (subseq a-string i j)
    while j))

Lista para string

Para transformar uma lista de palavras em uma string única, é preciso concatenar todos os elementos da lista, sem esquecer de acrescentar espaços entre eles:

(defun list-to-str ((a-list list))
  (string-trim " "
    (apply #'concatenate 'string
      (loop for e in a-list
        collect (concatenate 'string e " ")))))

Inversão dos elementos ímpares

Só faltou inverter os elementos de índice ímpar da lista. Nada mais simples: pegar cada elemento, se o índice for ímpar, inverter:

(defun invodd ((a-list list))
  (loop
    for x in a-list
    and i from 0
    collect (if (oddp i)
      (reverse x)
      x)))

Fazendo funcionar

Para que tudo aconteça, no final do arquivo acrescente uma chamada à função principal:

(mainloop)

E execute o arquivo com o comando clisp (aconselho o uso dos parâmetros -K full e -q).


**

Lisp tem uma abordagem extremamente elegante e clara, aproveita o paradigma funcional perfeitamente e seus programas podem ser retroalimentados recursivamente para obter-se um comportamento de aprendizado, apreciado no desenvolvimento de IA.

[]'s
Cacilhas, La Batalema

<update 2009-10-20>
Adicionada tipagem aos argumentos das funções e removido código redundante.
</update>

IDEs em ambiente GNU/Linux

Semana passada escrevi um artigo sobre alguns ambientes de desenvolvimento integrado e editores de texto, alguns deles RAD. No entanto o artigo ficou muito longo, daí tive a ideia de quebrá-lo em três partes.

Publiquei em meu blog Reflexões de Monte Gasppa e Giulia C., mas agora, pensando bem, acho que cabe pelo menos uma referência aqui no Kodumaro.

As três partes do artigo são:

1. Editores de texto
2. IDEs focadas em projeto
3. RAD

A quem se interessar, boa leitura!

[]'s
Cacilhas, La Batalema

Dev in Rio 2009

Gente,

Notícia fresquinha no blog do Henrique Bastos:

Dev in Rio 2009: EU VOU!

Finalmente o Rio de Janeiro ganhou um grande evento de tecnologia focado no que é mais importante: Pessoas!

É com muito orgulho que apresentamos o Dev in Rio 2009, uma conferência bombástica sobre desenvolvimento de software que acontecerá no próximo dia 14 de setembro no Centro de Convenções SulAmérica, no Rio de Janeiro!

O Dev in Rio 2009, contará com palestrantes nacionais e internacionais que falarão sobre Java, Ruby e Ruby on Rails, Python, Django, Open Source, Joomla!, Métodos Ágeis, e muito mais. Nomes como Fábio Akita, Vinícius Manhães Teles, Jacob Kaplan-Moss, Guilherme Silveira, Nico Steppat, Ryan Ozimek e Jeff Patton agitarão um dia inteiro de muita tecnologia e diversão. Veja a programação detalhada no site da Dev in Rio 2009.

Mas não é só isso. Como eu disse no início, este é um evento focado em pessoas. Toda a organização do evento está voltada para promover ao máximo a interação e integração entre os presentes.

Por isso, o Dev in Rio 2009 contará com uma Arena DojoRio onde participantes e palestrantes poderão programar lado à lado, experimentando diversas linguagens e técnicas, buscando juntos as melhores formas de desenvolver software.

O evento está sendo organizado por mim (Henrique Bastos) em parceria com o meu amigo Guilherme Chapiewski, contando com todo o apoio dos membros da PythOnRio, DojoRio e #Horaextra.

A realização está sendo coordenada pelas nossas experientes amigas da Arteccom. E tê-las ao nosso lado já garante que este será um evento para marcar o circuito carioca.

Você não pode perder esta incrível oportunidade de participar desse mega evento, interagir com grandes nomes do cenário mundial de tecnologia, conhecer pessoas interessantes que compartilham a paixão pelo desenvolvimento de software, e ainda por cima começar sua semana só na terça-feira. Inscreva-se já!

Nos vemos por lá!

[]’s!

[]'s
Cacilhas, La Batalema

Ponteiro opaco

Muitas vezes programadores de C++ e Java confundem encapsulamento com ocultação, o que não é a intenção da orientação a objetos.

No entanto, o contrário da ocultação, a exposição, também não é desejável para o encapsulamento, pois causa uma confusão entre interface e implementação.

Em C++, a declaração de uma classe força a exposição de sua estrutura privada. Um exemplo bem simples:

class X {
    public:
        X(int);
        ~X();

        int get(void) const;

    private:
        int value;
}

Neste exemplo insanamente simples, é possível ver a estrutura privada da classe X, o que no caso não é um problema muito sério, mas em casos ligeiramente mais complexos, é possível corromper o encapsulamento.

Uma forma de resolver o problema é usando um design pattern¹ chamado ponteiro opaco ou Pimpl.

A ideia é que a classe de interface seja apenas uma moldura (wrapper) para a classe de implementação. A classe de implementação é declarada no corpo da classe de interface, mas nada é exposto ali.

A classe de implementação vai ser finalmente implementada no arquivo onde os métodos da classe de interface são implementados. Os métodos da classe de interface então simplemente chamam os métodos da classe de implementação.

Voltemos ao exemplo… o arquivo de cabeçalho de nossa classe (x.h por exemplo) passa a ser:

class X {
    class Ximpl;

    public:
        X(int);
        ~X();

        int get(void) const;

    private:
        Ximpl *pimpl;
}

Como é possível ver, nada da implementação está exposto.

Então a classe de implementação é finalmente definida no arquivo de implementação (x.cc):

class X::Ximpl {
    public:
        Ximpl(int);
        ~Ximpl();

        int get(void) const;

    private:
        int value;

}

O resto do código fica:

X::X(int value): pimpl(new X::Ximpl(value)) {
    // Nada mais a fazer
}

X::Ximpl::Ximpl(int value): value(value) {
    // Nada mais a fazer
}

X::~X() {
    delete this->pimpl;
}

X::Ximpl::~Ximpl() {
    // Nada mais a fazer
}

X::get(void) const {
    return this->pimpl->get();
}

X::Ximpl::get(void) const {
    return this->value;
}

É claro que é um pattern extremamente desconfortável, pois é preciso implementar cada método duas vezes, uma para a classe de interface, outra para a classe de implementação… e há sim formas melhores de fazer isso.

Mas Pimpl funciona, é uma saída viável e pode salvar sua vida. =D

[update 2009-08-01]Sugestão de leitura de 0xc0de: Compilation Firewalls.[/update]

[]'s
Cacilhas, La Batalema


¹ Design patterns: antes que me crucifiquem por usar esta expressão fora do mundinho pequeno de Java, a definição de design pattern é «um jeito formal de documentar a solução para um problema de desenvolvimento», o que define corretamente ponteiro opaco.

Variaridade

Uma função variádica variária – em inglês variadic, variable arity, aridade¹ variável – é aquela que suporta uma quantidade variável de parâmetros.

Muitas linguagens suportam funções variárias, aliás de forma bem simples. Python usa o operador * para indicar quantidade variável de parâmetros, Lua usa o operador ... e Common Lisp o operador &rest.

Outras linguagens podem ser ainda mais simples, como por exemplo Perl, onde toda função é variária e os parâmetros são recebidos na lista @_, tradicionalmente capturados por shift.

Já Java não suporta funções verdadeiramente variárias devido a sua limitação forçada de tipagem, no entanto é possível simular com o uso de Object e casting («vazamento» na falta de uma tradução melhor):

void myFunction(Object... args) {
    // Código do método
    …
}

Funções variárias em C/C++

C/C++ usa o cabeçalho stdarg.h para suporte a funções variárias.

O exemplo apresentado na Wikipédia é bastante simples: uma função printargs que recebe uma quantidade arbitrária de números inteiros, encerrando com -1 (ou qualquer número negativo em nosso exemplo), e os exibe na saída padrão.

Precisamos incluir dois cabeçalhos em C++, cstdarg para suporte a funções variária e cstdio para exibir o resultado:

#include <cstdio>
#include <cstdarg>

Ou, em C:

#include <stdio.h>
#include <stdarg.h>

A assinatura da função fica assim:

void printargs(int arg1, ...) {

Para acesso aos parâmetros múltiplos é usado um objeto va_list:

    va_list args;

A função va_start() inicializa o objeto. Ela recebe dois parâmetros: o objeto va_list e o nome do último argumento antes da lista:

    va_start(args, arg1);

Portanto é preciso haver pelo menos um argumento antes da lista variável. Podemos então exibir o primeiro parâmetro, recebido no argumento arg1:

    printf("%d", arg1);

A função va_arg() retorna o argumento seguinte. Ela recebe como parâmetros o objeto va_list e o tipo do parâmetro da lista a ser recuperado.

O tipo precisar ser plenamente promovido, ou seja, ponteiro, inteiro, ponto flutuante ou precisão dupla. Outros tipos, como char precisam sofrer casting, como por exemplo (não faz parte do código de printargs):

char c = static_cast<char>(va_arg(va, int));

Continuando o código, podemos agora reiterar sobre os resultados de va_arg() até encontrarmos o valor de parada negativo:

    int arg;
    while((arg = va_arg(args, int)) >= 0)
        printf(" %d", arg);

Após o fim da reiteração dos parâmetros obtidos do objeto va_list através de va_arg(), é preciso encerrar o objeto:

    va_end(arg);
    printf("\n");
}

Caso você queira restringir o formato de entrada da função, isso é possível usando __attribute__ em sua declaração. Por exemplo, se a função log() recebe o nível de log como primeiro parâmetro, uma string de formatação como segundo parâmetro (2) e os parâmetros variáveis a partir do terceiro (3), com formato similar ao da função printf(), isso é feito com a seguinte assinatura:

extern void
log(int level, cons char *fmt, ...)
__attribute__((format(printf, 2, 3)));

As opções para format() são printf, scanf, strftime e strfmon. Veja Declaring Attributes of Functions da documentação do GCC.

[]'s
Cacilhas, La Batalema


¹Aridade: em Matemática é o número de operandos de uma função.