Aug 23, 2007

Lisp e parênteses

As pessoas sempre reclamam da quantidade de parênteses em Lisp. Contudo elas falham em perceber que outras linguagens tem tantos elementos sintáticos quanto lisp, ou até mais, só que como eles são diferentes entre si ficam "espalhados" pelo código não dando uma sensação tão presente como os parênteses de Lisp. Como um exemplo simples, comparemos uma função simples e não otimizada para calcular números de fibonacci em Pascal e em Common Lisp: O código em Pascal: 
function fib(N : integer) : integer;
begin
  if N < 2 then 
    fib := N;
  else
    fib := fib (N - 1) + fib (N - 2);
end;
O código em Lisp: 
(defun fib (n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))
A primeira vista o código em Lisp parece mais "poluído", com inúmeros parênteses, né? Bom, se excluirmos todas as coisas que o código em Pascal tem em comum com o código em Lisp (por exemplo, function é equivalente a defun, if, +, e - tem em ambos, etc) deixamos somente os elementos sintáticos que Pascal tem mas Lisp não precisa, teremos algo como: 
: integer : integer ;
begin
then
fib :=
else
fib := ;
end;
Ou seja, 15 elementos sintáticos. Por outro lado, se fizermos o mesmo com Lisp, isso é, tirarmos tudo que o código Lisp tem em comum com o código em Pascal, vamos terminar com isso: 
(
(()
(()())))
ou seja, um total de 12 elementos sintáticos. Não apenas o código em Lisp tem menos elementos sintáticos, como eles são uniformes (apenas parênteses), enquanto o código em Pascal tem vários elementos diferentes que o programador tem que se lembrar. Esse é um ponto-chave ao se programar em Lisp; na superfície parece que a linguagem é inundada de parênteses, mas no fundo, o número de elementos sintáticos é o mesmo, ou até menor, que a maioria das linguagens. Com a vantagem de que os elementos sintáticos usados são mais uniformes (apenas parênteses), enquanto que outras linguagens usam diversas coisas como parênteses, virgulas, pontos, colchetes, etc.

Posted at 14:05

May 26, 2007

Comandos mais usados

O comando abaixo permite ver de maneira simples quais os comandos que você executa mais frequentemente no linux: 
history | awk '{print $2}' | awk 'BEGIN {FS="|"} {print $1}'| \
        sort | uniq -c | sort -rn| head -10
Só por diversão é comum alguns hackers verificarem seus comandos mais comuns e postarem em algum lugar. O Dorneles postou seus comandos mais comuns, e de quebra mostrou uma implementação em Python.

Como Lisp não é (erroneamente) considerada uma linguagem apropriada para escrever scripts de sistema eu gosto de fazer uma uma versão em Lisp de scripts como esse para ver como ela se sai. A minha implementação pode ser vista abaixo. Eu usei apenas ANSI Common Lisp. Se eu tivesse usado bibliotecas externas o código poderia ser ainda mais compacto. 

(defun get-comandos ()
  (with-open-file (stream "/home/kroger/.bash_history")
    (loop for line = (read-line stream nil nil) while line
       collect (subseq line 0 (position #\Space line)))))

(defun conta-itens ()
  (let ((comandos (get-comandos)))
    (mapcar (lambda (item) (list (count item comandos :test #'string=) item))
            (remove-duplicates comandos :test #'string=))))

(format t "~{~{~a ~}~%~}" (sort (conta-itens) #'> :key #'first))
O objetivo aqui não é, naturalmente, fazer uma comparação com python (no estilo "minha linguagem é melhor que a sua"), mas sim ver como Lisp se sai nesse tipo de coisa. Eu acho que o resultado foi bem satisfatório. Lisp não tem nenhum comando padrão para ler todo o arquivo em uma string, mas dá para fazer isso com apenas 2 linhas de código. A função count conta quantas vezes um item aparece em uma sequencia, de modo que foi possivel implementar o código para contar os elementos de uma maneira funcional.

Um pouco de estatísticas: a implementação de python tem 14 linhas e 46 caracteres, enquanto a implementação em lisp tem 10 linhas e 52 caracteres. A implementação em lisp é mais curta, porém mais densa.

Eu não tenho dúvidas que é possível escrever um código em python ainda menor, mas como eu disse anteriormente, esse não é o objetivo aqui. Meu objetivo foi mostrar como é possível escrever um código simples, curto, e elegante em Lisp para lidar com coisas corriqueiras do dia-a-dia.

Posted at 12:15

Feb 14, 2007

Lisp Não é Uma Linguagem de Programação Funcional.

Repita comigo: Lisp não é uma linguagem de programação funcional. Novamente: Lisp não é uma linguagem de programação funcional. Uma última vez: Lisp não é uma linguagem de programação funcional.

Acho que agora posso começar o artigo :-)

Primeiramente, Lisp não é uma linguagem. O termo "Lisp" se refere a uma família de linguagens. Nos anos 80 iniciou-se um esforço para padronizar os diversos dialetos de Lisp que existiam como Maclisp, Interlisp, Zetalisp, entre outros. Esse esforço resultou no Common Lisp, que é definido pelo padrão ANSI. Hoje em dia existem três dialetos principais: Common Lisp, Scheme, e Emacs Lisp, sendo que os dois primeiros são usados para programação geral e o último como linguagem de extensão para o Emacs.

Sim, o criador do Lisp, John McCarthy, incorporou diversas idéias do cálculo lambda na linguagem. Isso não é surpreendente, já que McCarthy foi aluno do Alonzo Church (o criador do cálculo lambda). Mas isso foi no final dos anos 50! Nesse meio-tempo (ou deveria dizer meio século?) diversos paradigmas de programação foram incorporados nos mais diversos dialetos de Lisp. Na verdade, não só esses paradigmas foram incorporados como Lisp foi usado como inspiração ou veículo de pesquisa para trabalhos chaves como o Smalltalk. Mas isso é conversa para outro post.

O ponto chave desse post é que Common Lisp tem suporte integrado para os mais diversos tipos de paradigmas como funcional, imperativo, aspectos, além de ter um dos mais avançados sistemas de programação a objetos. Então dá para imaginar minha surpresa quando eu envio o texto abaixo para divulgar o II Encontro Lisp-br no FISL 8.0: 

Lisp abrange uma família de linguagens como Common Lisp e Scheme. Lisp
é uma linguagem multi-paradigma com diversos recursos e abstrações
para programação funcional, procedural, imperativa, aspectos, um
sistema avançado e flexível de programação orientada a objetos, e um
carater dinâmico sem precedentes.
E eles publicam no lugar o seguinte texto: 
O Lisp é uma família de linguagem de programação funcional,
sendo que as mais conhecidas são Common Lisp e Scheme.
Pô, eu sei que as vezes tem que cortar o texto para ficar menor, mas que tal colocar: 
O Lisp é uma família de linguagem de programação
multi-paradigma, sendo que as mais conhecidas são Common Lisp e
Scheme.
Seria muito mais fiel com o texto que eu enviei e com a verdade. Segundo o Mario Goulart (do Lisp-br) esse não é um caso isolado. Esse tipo de coisa já aconteceu com ele. Porque as pessoas tem dificuldade em aceitar que Common Lisp e Scheme são linguagens multi-paradigma?

Na verdade você fazer programas puramente funcionais com Lisp (como eu faço), ou usar apenas classes e objetos sem nenhum recurso funcional. Ou ainda, você pode usar um estilo de programação do tipo fluxograma (com algo semelhante ao GOTO com esteróides e tudo), útil para estudar e testar os algoritmos do The Art of Computer Programming (TAOCP). A propósito, antes de fazer cara feia para o GOTO, você já leu o clássico Structured Programming with Goto Statements do Knuth?

O livro Practical Common Lisp (ou PCL para os íntimos) é uma excelente referência para quem quer saber mais sobre Common Lisp e como usar os diversos paradigmas, como programação orientada a objetos.

Posted at 00:05

Jan 20, 2007

Processando XML com Lisp

Esse post bastante interessante sobre um (pequeno) programa em Factor para converter um documento no formato de XML do Excel para CSV (comma separated value) me inspirou a escrever algo sobre processamento de XML com Lisp.

Naturalmente, existem diversas maneiras de se trabalhar com XML em Lisp, incluindo representação em objetos, DOM, SAX, Xpath, etc. Nesse artigo eu vou falar sobre uma maneira "old school" (da velha guarda :-) que é bastante produtiva e interessante.

Talvez você tenha observado que as expressões simbólicas (a representação que Lisp usa para dados e código) e XML são bem parecidas. O exemplo abaixo mostra um arquivo em XML para representar produtos. Cada produto possui dados como nome do produto, preço, e fornecedor: 

<produtos>
  <produto>
    <nome>Cadeira</nome>
    <preco>35.13</preco>
    <fornecedor>Pedro</fornecedor>
  </produto>
  <produto>
    <nome>Mesa</nome>
    <preco>45.13</preco>
    <fornecedor>Pedro</fornecedor>
  </produto>
</produtos>
O exemplo anterior poderia ser representado da seguinte maneira usando expressões simbólicas em Lisp: 
(produtos
  (produto
   (nome "Cadeira")
   (preco "35.13")
   (fornecedor "Pedro"))
  (produto
   (nome "Mesa")
   (preco "45.13")
   (fornecedor "Pedro"))
Sim, eu posso copiar o trecho acima e colar no meu código Lisp e usar tranquilamente, sem conversão ou parseamento. Para clarificar vamos ver um exemplo prático. O exemplo abaixo guarda uma lista de produtos na variável produtos: 
(setf produtos 
  '((produto (nome "Cadeira") (preco 35.13) (fornecedor "Pedro"))
    (produto (nome "Mesa") (preco 45.13) (fornecedor "Pedro"))
    (produto (nome "Tapete") (preco 95.13) (fornecedor "Pedro"))))
A vantagem dessa abordagem é que como a representação acima é um código válido de Lisp, eu posso usar as funções padrões para extrair informações. Por exemplo, (first produtos) retorna a lista com a representação do primeiro produto: 
  (produto (nome "cadeira") (preco 35.13) (fornecedor "pedro"))
O comando (second produtos) retorna a lista do segundo produto e assim por diante. Naturalmente, combinações são permitidas, como pegar o segundo elemento dentro do terceiro elemento do segundo produto, que nesse caso vai retornar o preço do produto: 
(second (third (second produtos))) => 45.13
Common Lisp é a linguagem para trabalhar com listas. Então fazer coisas como usar filtros para selecionar os produtos com o preço maior que 40 é tão simples como: 
  (remove-if-not (lambda (x) (> (second x) 40)) produtos :key #'third)
Então, visto que XML e expressões simbólicas são semelhantes, uma maneira muito comum e natural de trabalhar XML com Lisp é usar um parser que converte uma expressão XML em uma expressão simbólica. Existem vários parsers que fazem isso. Nesse exemplo eu vou usar o s-xml. O programa do post original converte arquivos do Excel. Como eu não tenho esse programa, vou criar um programa que converte arquivos do scalc, a planilha do OpenOffice, para CSV. Claro que o OpenOffice tem uma função para exportar para csv, esse código que veremos é só um exemplo.

Para parsear um arquivo XML e converter para expressões simbólicas (sexp), é apenas necessário rodar o comando parse-xml-file. Ele retorna uma lista com a representação em sexp. 

  (s-xml:parse-xml-file "arquivo.xml")
Para extrair o valor da primeira célula, por exemplo, o seguinte código poderia ser usado: 
  (second (second (second (third (second (second (fifth (s-xml:parse-xml-file "arquivo.xml"))))))))
Contudo, essa é a pior maneira lidar com dados. Nenhum programador deveria escrever algo assim em qualquer linguagem. Dessa maneira não há abstração de dados. Que parte do documento está sendo extraída? É impossivel dizer em uma primeira olhada. Outro problema é que se o arquivo XML mudar, o código vai extrair alguma informação errada, no lugar da que queremos. A melhor maneira de lidar com esse tipo de coisa é criando barreiras de abstração.

A primeira função que vamos criar aceita uma expressão contendo o documento inteiro e retorna apenas o corpo do documento. Tudo que está na marcação office:body 

(defun get-body (expr)
  (first (remove-if-not (lambda (x) (and (listp x) (eql (first x) '|office|:|body|)))
                        expr)))
A segunda função retorna o código que contém a marcação office:spreadsheet 
(defun get-spreadsheet (expr)
  (second (get-body expr)))
A próxima função retorna a folha (sheet) dentro de uma planilha que desejamos extrair os dados. Cada arquivo pode ter inúmeras colhas diferentes. Por padrão ela retorna a primeira folha. 
(defun get-sheet (expr &optional (sheet-n 1))
  (nth (1- sheet-n) (remove-if-not #'listp (get-spreadsheet expr))))
A próxima função retorna apenas o código com as linhas da tabela (ficam dentro da marcação table:table-row: 
(defun get-rows (expr &optional (sheet-n 1))
  (remove-if-not (lambda (x) (eql '|table|:|table-row| x))
                 (remove-if-not #'listp (get-sheet expr sheet-n) :key #'first)
                 :key #'caar))
Essa função retorna uma lista com os valores e dados das células: 
(defun get-cell-data (expr &optional (sheet-n 1))
  (mapcar (lambda (x) (subseq x 1)) (get-rows expr sheet-n)))
Observe que cada função que criamos chama a anterior. get-cell-data chama get-rows, que chama get-sheet, que chama get-spreadsheet, que finalmente chama get-body. Isso acontece porque essas sessões (linhas, páginas, planilha) estão aninhadas no documento. Escrever funções específicas para partes específicas do documento ajuda na legibilidade e em manutenções futuras.

Finalmente, a função seguinte retorna uma lista com listas com os dados para cada linha da planilha. Por exemplo, ((foo bar) (10 100)): 

(defun extract-cell-data (expr &optional (sheet-n 1))
  (mapcar #'(lambda (w) (mapcar #'(lambda (x) (second (second x))) w))
          (get-cell-data expr sheet-n)))
Pronto, o código abaixo vai ler o arquivo XML e extrair apenas as informações da planilha e colocar em um formato de listas. 
  (extract-cell-data (s-xml:parse-xml-file "arquivo.xml"))
Por exemplo, os dados dessa planilha: planilha
seriam representados da seguinte maneira, após a execução do código acima: 
  (("nome" "telefone" "profissao") ("pedro" "3333-4040" "hacker")
  ("joao" "4444-1010" "programador") ("fulano" "5555-2020" "faxineiro"))
Tudo que precisamos agora é um código para converter a lista acima em um formato separado por vírgulas. Isso é bem simples de fazer com format: 
  (format stream "~{~{~a~^, ~}~%~}" lista)
O formato do OpenOffice na verdade é um arquivo compactado com diversos arquivos dentro. Por exemplo, o comando unzip -l em um arquivo do openoffice mostra a seguinte saida: 
  46  01-20-07 22:03   mimetype
   0  01-20-07 22:03   Configurations2/statusbar/
   0  01-20-07 22:03   Configurations2/accelerator/current.xml
   0  01-20-07 22:03   Configurations2/floater/
   0  01-20-07 22:03   Configurations2/popupmenu/
   0  01-20-07 22:03   Configurations2/progressbar/
   0  01-20-07 22:03   Configurations2/menubar/
   0  01-20-07 22:03   Configurations2/toolbar/
   0  01-20-07 22:03   Configurations2/images/Bitmaps/
5644  01-20-07 22:03   content.xml
6155  01-20-07 22:03   styles.xml
1032  01-20-07 22:03   meta.xml
 952  01-20-07 22:03   Thumbnails/thumbnail.png
8389  01-20-07 22:03   settings.xml
1873  01-20-07 22:03   META-INF/manifest.xml
De todos esses arquivos o que nos interessa é o content.xml. A próxima função usa o unzip para extrair esse arquivo, converte a representação de listas para formato separado por vírgulas (usando o código com format visto acima) e envia tudo para um arquivo de saída: 
(defun lista->csv (ods-file csv-file &optional (sheet-n 1))
  (sb-ext:run-program "/usr/bin/unzip" (list "-d" "/tmp/" "-o" ods-file "content.xml"))
  (with-open-file (stream csv-file :direction :output :if-exists :supersede)
    (format stream "~{~{~a~^, ~}~%~}"
            (extract-cell-data (s-xml:parse-xml-file "/tmp/content.xml")
                               sheet-n))))
Finalmente, o seguinte código vai converter o arquivo de planilha do openoffice foo.ods para foo.csv, usando a função acima: 
  (lista->csv "foo.ods" "foo.csv")
Para converter diferentes folhas é só acrescentar o número da folha no final. Por exemplo, para converter a terceira folha: 
  (lista->csv "foo.ods" "foo.csv" 3)
Esse foi um post longo porque eu fui mostrando como fazer as coisas passo-a-passo. Eu espero que não pareça mais complexo do que é na verdade. O código total tem 30 linhas, o que é um número razoável. O código poderia ser "expremido" para ficar com menos linhas. Por exemplo, a função get-spreadsheet só tem uma linha e só é usada em get-sheet. Eu poderia fundir as duas em uma só. Mas a vantagem de ter o código dividido em funções como está é que a legibilidade é maior e ajuda na manutenção do código. Se no futuro o formato do arquivo XML mudar fica mais fácil saber onde fazer a mudança no código.

Uma grande vantagem dessa abordagem é que praticamente nenhum código no programa foi específico de XML, nós trabalhamos com listas o tempo inteiro. Isso ajuda a separar a apresentação do conteúdo, e não deixa o código fixo em nenhuma tecnologia. Se no futuro o openoffice usar outro formato diferente do XML eu só precisarei mudar uma linha no meu código fonte.

Uma outra vantagem é que a função extract-cell-data retorna os valores em listas simples. Com isso podemos facilmente usar funções para converter essa representação de listas para outros formatos como HTML, LaTeX, ou CSV, como foi nosso caso. Por exemplo, o seguinte código é suficiente para gerar uma tabela em HTML a partir da lista gerada por extract-cell-data 

(format stream "<table>~{<tr>~{<td>~a</td>~}</tr>~%~} </table>" lista)
Espero que tenha gostado de ver como se pode trabalhar com XML em Lisp. Tudo sem vodu de XML :-)

Posted at 19:53

Jan 18, 2007

Ruby e Lisp

As vezes os usuários de linguagens novas como Tcl, Python, e Ruby não percebem o quanto essas linguagens foram influenciadas por Lisp. Talvez essa mensagem do criador do Ruby, Yukihiro Matsumoto, ajude a enteder o processo:
Ruby é uma linguagem criada nos seguintes passos:
  • pegue uma linguagem lisp simples (como uma antes de CL)
  • remova macros e expressões simbólicas
  • acrescente um sistema de objetos simples (muito mais simples que CLOS)
  • acrescente blocos, inspirado por funções de ordem superior
  • acrescente métodos encontrados em Smalltalk
  • acrescente funcionalidades encontradas em Perl (mas em uma maneira orientada a objetos)
Então, Ruby foi um tipo de Lisp originalmente, teoricamente. Vamos chama-lo de MatzLisp de agora em diante. ;-)
Claro que os lispers vão dizer que Ruby seria melhor se tivesse os itens que lisp tem e que foram "retirados", e os programadores de Ruby vão dizer que essa é uma das razões que Ruby é uma boa linguagem :-)

Posted at 08:55