Combinador de ponto fixo

A beleza da matemática e do cálculo é que algo não precisa ter uma aplicação prática imediata para ser estudado em profundidade. A aplicabilidade pode surgir 150, 200 anos após sua concepção.

Um dos tópicos mais magníficos do cálculo-λ é o combinador de ponto fixo, apesar de ser de interesse mais acadêmico do que diretamente prático.

Ainda assim, seu entendimento engrandece em tamanha proporção o conhecimento do programador, que vale a pela dedicar-lhe algum tempo.

Conceitos básicos

Há alguns pré-requisitos que você precisa conhecer para começar nosso estudo:

Cálculo-λ

Cálculo-λ é uma parte da lógica matemática criada da década de 1930 como parte da investigação dos fundamentos da matemática. No cálculo-λ, todos os elementos são funções de primeira classe, inclusive os números.

Por exemplo, o número 2 é uma função que aplica uma outra função duas vezes, e é representado como λsz.s(sz).

O sinal + (ou S em alguns textos) significa incremento, e é descrito como λwyx.y(wyx). Ou seja, +3 é 3 incrementado, que é igual a 4. 2+3 é a função 2 recebendo como parâmetros + e 3, ou seja, incrementa duas vezes o número 3, +(+3), o que resulta em 5.

A multiplicação é prefixal, não mesoclítica, ou seja, 2x escreve-se como *2x (ou M2x) e sua definição é λab.a(b+)0 ou λxyz.x(yz).

O cálculo-λ é o princípio de onde deriva a programação funcional.

[update 2014-08-25]
A definição de decremento é (caso eu não tenha copiado errado):

DEC = λnfx.n (λgh.h(gf)) (λu.x) I

[/update]

Ponto fixo

Impossível entender combinador de ponto fixo sem saber o que significa ponto fixo. Ponto fixo é o ponto de uma função onde o valor retornado é igual ao valor fornecido.

Por exemplo, dada a função f(x) = 2x-1, o que em notação cálculo-λ fica f = λx.DEC(*2x), o ponto fixo é aquele onde fx = x, ou seja, o resultado é igual ao parâmetro.

Usando aritmética básica:

f(x) = 2x - 1
x = 2x - 1
2x - 1 = x
2x - 1 - x = 0
x - 1 = 0
x = 1

Portanto o ponto fixo de λx.DEC(*2x) é 1.

Repare que a recursão sobre o ponto fixo resulta sempre no mesmo resultado. Se:

x = fx

Podemos substituir x por fx:

x = fx = f(fx) = f(f(fx))) = ...

Variáveis livres e vinculadas

Em cálculo-λ, no corpo de uma função, todas as variáveis que vêm de sua assinatura são vinculadas e as que vêm de fora são livres.

Por exemplo, na função:

λfx.Δxf

As variáveis x e f são vinculadas e a variável Δ é livre.

Combinadores

Combinadores são funções que não possuem variáveis livres. Por exemplo:

λx.xx
λx.y

A primeira linha é um combinador, já a segunda não.

Veja que, a rigor, números e operadores aritméticos são variáveis livres, porém, como são valores constantes e bem definidos, tratam-se de exceções aceitáveis em um combinador.

Construção let

A construção let é uma construção clássica em cálculo-λ e em linguagens funcionais de programação.

Darei um exemplo: seja fx igual a *2x em f4, o resultado é 8 – fx é o dobro e x e o caso é f4. Isso é descrito assim:

let fx = *2x in f4

Podemos construir uma função assim, por exemplo, dado o parâmetro x, sendo fa igual a *2a em fx-1:

λx.let fa = *2a in DEC(fx)

É o mesmo que:

λx.DEC(*2x)

Em Haskell isso pode ser escrito assim:

func x = let f a = 2 * a in f x - 1

Em Racket fica assim:

(describe func
  (λ (x)
    (let ((f (λ (a) (* 2 a)))
      (- (f x) 1))))

A forma genérica da construção let é:

let fx = y in z

E sua abertura é:

(λf.z)(λx.y)

Finalmente: o combinador de ponto fixo

Combinador de ponto fixo é uma função que retorna o ponto fixo da função fornecida como parâmetro. Em cálculo e mesmo em programação isso é muito útil na implementação de funções recursivas.

Função recursiva é aquela que faz chamada a ela mesma, por exemplo, fatorial:

FACT = λn.(ISZERO n) 1 (*n (FACT (DEC n)))

Olhando para o corpo da função, mesmo desconsiderando números e operadores (ISZERO, 1, * e DEC), ainda há a variável livre FACT, que não é definida na assinatura da função.

[update 2014-08-25]
A definição de ISZERO é:

TRUE = λxy.x
FALSE = λxy.y
ISZERO = λn.n(λx.FALSE)TRUE

[/update]

A forma de resolver isso é criar uma função que recebe a si mesma na assinatura:

ALMOST-FACT = λfn.(ISZERO n) 1 (*n (f (DEC n)))

Quando esse combinador recebe como parâmetro o fatorial, ele retorna o próprio fatorial, assim a função fatorial é o ponto fixo dele!

O combinador de ponto fixo é aquele que, ao receber a função como parâmetro, retorna seu ponto fixo – e quando a função recebe o ponto fixo, retorna o próprio ponto fixo, segundo o seguinte comportamento:

yf = f(yf)

Só aqui já seria possível implementar uma função que calcule o ponto fixo. Em Haskell:

fix f = f (fix f)

E em Lazy Racket:

(define fix
  (λ (f)
    (f (fix f))))

Porém seria sem sentido, pois essa mesma função que resolve o problema, é parte do problema, já que ela própria possui variável livre.

Resolver este problema não é difícil: basta pegarmos a definição: dada uma função f, queremos o ponto x onde fx seja igual a x… é uma construção let!

Data uma função que recebe f (λf.), seja x igual a fx (let x = fx) em x (in x):

λf.let x = fx in x

De fato isso já funciona em Haskell:

fix :: (a -> a) -> a
fix f = let x = f x in x

Combinador Y

Para Scheme (Lazy Racket), precisamos destrinchar um pouco mais, abrindo o let.

Precisamos de dois parâmetros na primeira posição, portanto dobraremos o x:

λf.let x = fx in x
λf.let xx = f(xx) in xx
λf.(λx.xx)(λx.f(xx))

Mais um passo e chegamos ao famoso combinador Y de Curry!

Aplicando o parâmetro λx.f(xx) à função λx.xx, temos (λx.f(xx))(λx.f(xx)), exatamente o combinador Y de Curry:

Y = λf.(λx.f(xx))(λx.f(xx))

Em Lazy Racket:

(define Y
  (λ (f)
    ((λ (x) (f (x x))) (λ (x) (f (x x))))))

Linguagens estritas

A maioria das linguagens não suporta lazy evaluation, então é preciso fazer um truque para que a definição do combinador não entre em loop infinito.

O truque é aplicar a função λsv.sv (que é o número 1, equivalente à identidade: I = λx.x). Por exemplo:

g = 1g
g = (λsv.sv) g
g = (λv.gv)

Por exemplo, o combinador Y em Python:

Y = lambda f: (lambda x: x(x))(lambda x: f(x(x)))

Esse código entra em loop infinito! Mas se substituirmos xx por λv.xxv, tudo se resolve:

Y = lambda f: (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args)))

Outros combinadores de ponto fixo

Curry foi o que obteve a solução mais simples para o combinador de ponto fixo, mas não foi o único. Há outras soluções possíveis.

Combinador de Turing:

Θ = (λx.xx)(λab.b(aab))

Combinador de ponto fixo estrito (vimos acima):

Z = λf.(λx.xx)(λx.f(λv.xxv))

Combinador de ponto fixo não padrão:

B = λwyx.w(yx)
∆ = λx.xx
N = B∆(B(B ∆)B)

[]’s

Dissecando a variância

Este artigo dá seguimento ao artigo sobre variância amostral.

A variância pode ser entendida como a média aritmética dos quadrados dos desvios de cada elemento da população.

O desvio de um elemento é a diferença entre o elemento e seu valor esperado. Quando lidamos com um conjunto, o valor esperado é a média dos elementos.

Então o desvio do elemento x_i é x_i - x.

A variância populacional pode ser descrita como:


Na maioria dos casos, não se tem disponível todos os elementos de um conjunto, mas apenas uma amostra. Nesses casos, calculamos a variância de amostra ou variância amostral.

A diferença no cálculo é que, em vez de dividirmos pelo número total de elementos da amostra no cálculo da média, dividimos pelo número total menos um, o que aumenta o resultado do desvio padrão, compensando não conhecermos todos os elementos do conjunto.

Então o cálculo muda para:


Em Erlang, para calcular o somatório dos desvios, primeiros usamos list comprehension para gerar uma lista dos quadrados desvios:

[math:pow(Xi - Xm, 2) || Xi <- List]

O que este código diz é: retorne a lista dos quadrados (math:pow/2) das diferenças entre cada elemento (Xi) da lista (Xi <- List) e sua média (Xm, calculado anteriormente).

Depois ele usa math:sum/1 para gerar um somatório e retorna a divisão do resultado do somatório pelo tamanho da lista menos um (Num / Demon).

Volte ao artigo anterior para ver como fica o código.

Em Scheme, a lógica é quase a mesma, mas em vez de list comprehension, é usado map/reduce. O #'map roda a função anónima (lambda) em cada elemento, extraindo os quadrados dos desvios.

[update]
Troquei o link para map/reduce, que apontava para um arcabouço do Google, quando as referências reais seriam encontradas no segundo parágrafo do texto referenciado.
[/update]

A função usada foi (λx.(x - x)²)x_i, ou: (lambda (x) (expt (- x xm) 2)) em LISP.

Para o reduce (#'apply) é usado somatório (#'+), aplicado ao conjunto resultante.

Novalmente, volte ao artigo anterior para ver o código.

[]’s
Cacilhας, La Batalema

Racket

Outro dia procurando por um bom interpretador/compilador para R⁶RS, encontrei algo muito mais interessante…

Encontrei o RAD-IDE Racket, antigo DrScheme.

O interessante do Racket é que, além de ser um interpretador e compilador de R⁵RS e R⁶RS, também suporta – aliás, por padrão – uma linguagem de programação baseada em Scheme, também chamada Racket – antiga PLT Scheme –, muito poderosa; também traz um ambiente de desenvolvimento chamado DrRacket.

Quando você escreve um script em Scheme, a primeira linha indica a versão que você pretende usar:

#!r4rs

Ou:

#!r5rs

Ou:

#!r6rs

Se o interpretador suportar a versão, ela será usada. Já no caso do Racket, outras opções são suportadas, como o padrão:

#lang racket

Para a linguagem padrão.

[update 2011-10-18]
Um script R⁶RS começa sempre com um import, por exemplo:

#!r6rs
(import (rnrs))

Você pode ter as funções de R⁶RS em um código Racket (PLT), basta usar:

#lang racket
(require rnrs)

O módulo rnrs traz toda a funcionalidade de R⁶RS.

Outra coisa legal da linguagem Racket é que, em vez de lambda, você pode usar λ (⌘\ / C-\).
[/update]

E até mesmo:

#lang planet jaymccarthy/c

Para linguagem de programação C – uma opção de C interpretado!

Para tanto você precisa ter em seu ~/.racketrc o seguinte conteúdo:

#lang racket
(require (planet jaymccarthy/c:1:2))

Para instalar o módulo C, você pode executar no widget de definições (⌘D no Mac OS X, C-d no Windows e no GNU/Linux):

> (require (planet "main.rkt" ("jaymccarthy" "c.plt" 1 2)))

[update 2011-10-18]
Eu acho que você não precise instalar o módulo, basta colocar sua chamada em ~/.racketrc e, na primeira execução, o módulo será automaticamente baixado e instalado.

Só não posso afirmar com certeza porque eu já havia instalado ele antes.

No Windows, o arquivo é racketrc.rktl e deve ficar no diretório de perfil do usuário.
[/update]

Programação visual

Para facilitar a vida de quem precisa desenvolver aplicações gráficas, você pode usar o MrEd Designer.

Para instalá-lo, execute no widget de definições do DrRacket:

> (require (planet orseau/mred-designer:3:7))

Para iniciar o processo, use (recomendo criar um alias):

bash$ gracket -e '(require (planet orseau/mred-designer:3:7))'

Olá Mundo!

Vamos criar um programa simples. Primeiro abra o MrEd Designer.

[update 2011-10-19]
Troquei os nomes dos widgets pelos nomes usados no código Racket.
[/update]

Na janela Hierarchy selecione project-XXX.

Na janela MrEd Designer, na seção Containers, clique no primeiro botão, frame%.

Vai surgir uma janela pequena e, na hierarquia do projeto, um frame% (frame-XXXX) sob o projeto.

Na janela Hierarchy selecione o frame% que apareceu e repare que a janela Properties mudou.

Em Properties, mude o valor de label (que está Frame) para Olá Mundo! e clique em Save & Update Preview.

Veja que o título da janela mudou.

Agora, ainda com o frame% selecionado, na janela MrEd Designer, na seção Controls, clique no primeiro botão, message%. Repare que surgiu um elemento message% (message-XXXX) na hieraquia, sob o frame%.

Selecione o novo elemento e mude o label (em Properties) para Olá Mundo!.

Clique em Choose Font… e escolha uma fonte maior, sugiro Arial Bold 20, e clique em Ok.

Clique novamente em Save & Update Preview.

Selecione de novo o frame% em Hierarchy e, em MrEd Designer → Controls, clique no segundo botão, button%.

Surgirá um elemento button% (button-XXXX) sob o frame%. Selecione-o.

Mude o label para Ok e a fonte para Arial 14. Clique em Save & Update Preview.

Agora, na janela MrEd Designer, no menu File clique em Save Project – ou pressione ⌘S / C-s. Escolha o diretório e salve como ola.

Depois clique em File → Generate Scheme File… – ⌘F5 no Mac. Salve como ola.ss no mesmo diretório onde você salvou o projeto.

Repare que você terá dois arquivos: ola.*.med (o projeto) e ola.ss (o código).

Abra agora o arquivo ola.ss no DrRacket:

bash$ drracket ola.ss

Procure a seguinte linha:

(button-XXXX-callback (lambda (button control-event) (void))))

Onde XXXX é uma sequência de dígitos decimais.

Mude para:

(button-XXXX-callback (lambda (button control-event) (displayln "Olá Mundo!"))))

Veja a linha 8 do script:

;;; Call (project-XXX-init) with optional arguments to this module

Acrescente a linha sugerida ao final do arquivo:

(project-XXX-init)

Salve o arquivo – ⌘S / C-s – depois rode/corra o programa – ⌘T / C-t – e veja a mágica.

Para executar o script sem precisar levantar o DrRacket, use o comando:

bash$ gracket ola.ss

Se preferir tornar o script executável, acrescente a primeira linha:

#!/usr/bin/env gracket

Outros recursos

Você pode encontrar uma série de módulos interessantes no PLaneT, como facilidades web, conexão a banco de dados, bzlib, Plan9, JSON, etc.

Sobre construção de aplicações web, leia Continue: Web Applications in Racket.

[]’s
Cacilhας, La Batalema

Paradigmas de programação

Muito mais empolgante do que aprender uma nova linguagem de programação é aprender um novo paradigma de programação.

A parte mais louca é perceber como o paradigma funciona. Isso acontece de modo intuitivo, muito parecido com como quando se aprende uma língua nova: nada faz sentido no começo, tudo é muito mecânico; de repente um estalo e tudo faz sentido!

Há muitos paradigmas de programação, já andei falando disso antes, mas muitos são variações dos mesmos tipos básicos: paradigmas imperativo, funcional e declarativo.

Programação imperativa

É o primeiro paradigma com o qual a maioria dos programadores trava contato.

Na programação imperativa, o programa se parece com uma receita de bolo: uma sequência de ordens, chamadas comandos ou instruções (statements em inglês), que devem ser executadas.

A partir desse conceito, derivam diversos paradigmas secundários. O principal é a programação estruturada ou procedimental (procedural em inglês), onde os comandos são organizados em grupos, chamados funções, que podem ser evocados em momentos diferentes.

As funções podem receber ou não parâmetros, que alteram seu comportamento, e podem retornar valores. Em algumas linguagens, quando o grupo de comandos não recebe parâmetros nem retorna valores, ele é chamado subrotina.

Para exemplificar o funcionamento da programação imperativa, vamos implementar fatorial em C – mais simples impossível.

Para quem não sabe, fatorial consiste em uma função recursiva cuja parada é:

0! = 1

E o passo é:

n! = n * (n - 1)!

Outra forma de entender é reiterativamente:

n! = 1 * 1 * 2 * 3 * … * (n - 2) * (n - 1) * n

Vamos implementar a função reiterativa em C para ilustrar melhor o paradigma:

#include <stdlib.h>
#include <stdio.h>

int factorial(int);


int main(int argc, char **argv) {
    printf("O fatorial de 5 é %d\n", factorial(5));
    return EXIT_SUCCESS;
}


int factorial(int x) {
    int result = 1;
    int i;
    for (i=1; i<=x; ++i)
        result *= i;
    return result;
}

Cada comando é uma ordem dada ao sistema: atribua 1 à variável result; para cada i de 1 até o valor do argumento x, multiplique o valor de result pelo valor de i; retorne o valor de result.

São ordens dadas ao sistema.

[update 2011-07-24]
Na programação imperativa, é muito comum a manipulação de alterações de estado, daí o uso de variáveis – contentores (ou slots) que podem sofrer alterações de valor ao longo da existência do processo em execução.
[/update]

Orientação a objetos

Orientação a objetos não passa de um variante da programação imperativa, mas um variante digno de citação.

Na orientação a objetos, as ordens não são dadas a um sistema abstrato, mas objetos recebem as ordens e as executam.

O conceito de objeto é bem genérico: qualquer coisa pode ser um objeto, um número, uma janela na tela, uma coleção…

Na orientação a objetos as ordens dadas a um objeto são chamadas mensagens e a definição de como o objeto reage a cada mensagem é chamada método.

O exemplo será a versão recursiva de fatorial implementada em Smalltalk:

!Integer methodsFor: 'mathematical functions'!

    factorial
        self = 0 ifTrue: [↑ 1].
        self > 0 ifTrue: [↑ self * (self - 1) factorial].
        self error: 'Not valid for negative integers'.
    !
!!


Transcript
    show: 'O fatorial de 5 é ';
    show: 5 factorial printString;
    cr.

[update 2011-07-16]
Atualizei o código em Smalltalk segundo implementação da máquina virtual Pharo.
[/update]

O princípio é parecido com o anterior, mas em vez de dar uma ordem ao sistema – calcule o fatorial de 5 –, é dada ao próprio número – número 5, qual seu fatorial?

Observação: a orientação a objetos pode ser aplicada também à programação funcional.

Programação funcional

Enquanto na programação imperativa ordens são dadas ao sistema ou a objetos, no paradigma funcional são definidas funções, como as matemáticas, e o programa nasce da interação entre as funções: o resultado de umas funções é passado como parâmetro para outras.

[update 2011-07-24]
Na programação funcional, o estado do sistema tende a ser constante, havendo apenas a troca de informação por parâmetros. Assim é comum que não haja variáveis, mas incógnitas constantes, que não sofrem (ou não devem sofrer) alteração de valor ao longo da execução do programa.
[/update]

O mesmo exemplo, fatorial, em Common Lisp:

(defun factorial ((x integer))
    (if (zerop x)
        1
        (* x (factorial (- x 1)))))


(format t "~%O fatorial de 5 é ~A~&" (factorial 5))

O conceito é ligeiramente difente: a função factorial, que recebe um parâmetro inteiro nomeado x, é definida como o resultado da função if; a função if recebe como primeiro parâmetro o resultado da função zerop, que é verdadeiro quando x é igual a zero; o segundo parâmetro de if, 1, é o resultado caso o primeiro parâmetro seja verdadeiro; o terceiro parâmetro é o resultado caso seja falso; o terceiro parâmetro é o resultado da função de multiplicação. Entendendo até aqui, o resto é autoexplicativo.

[update 2011-06-19]

Bônus!

Fatorial em Scheme:

(define (factorial x)
  (if (zero? x)
    1
    (* x (factorial (- x 1)))))

(display "O fatorial de 5 é ")
(display (factorial 5))
(newline)

E em Erlang:

-module (fact).
-export([factorial/1]).

factorial(0) -> 1;
factorial(X) -> X * factorial(X - 1).

Salve como fact.erl. No prompt:

1> c("fact.erl").
{ok,fact}
2> fact:factorial(5).
120

[/update]

Programação declarativa

Este paradigma é um dos mais complicados para pescar…

[update 2011-07-24]
Na programação declaração o código diz o que o programa deve fazer, não como.
[/update]

O programa consiste em uma lista de declarações de verdades.

Nos paradigmas anteriores havia variáveis, que sofriam atribuições. Na programação declarativa há incógnitas, que não sofrem atribuições! O valor de cada incógnita é constante e inicialmente desconhecido. O que o programa faz é cruzar as consultas (queries) com as declarações que formam o conjunto verdade para deduzir o valor das incógnitas.

O exemplo consiste no fatorial implementado em Prolog:

factorial(0, 1).

factorial(N, F) :-
    N > 0,
    N1 is N - 1,
    factorial(N1, F1),
    F is N * F1.

O que este conjunto verdade diz é que o fatorial de 0 é 1 e que o fatorial de N é F quando:

1. N é maior que zero;
2. N1 é N menos 1;
3. o fatorial de N1 é F1;
4. e F é igual a N vezes F1.

Para a consulta:

| ?- [factorial].
fatorial.pro compiled, 7 lines read - 869 bytes written, 7 ms
(1 ms) yes
| ?- factorial(5, X),
write('O fatorial de 5 é '),
write(X),
nl.

Para entender como funciona, há um applet em Java em um tutorial que demonstra o chinês. É só encontrar o applet na página, ir clicando em Step e ver acontecer.

A linguagem declarativa da vez é Erlang.

[update 2011-06-19]
Na época deste artigo, em vez de estudar Erlang, perguntei por aí e fui informado que Erlang seria uma linguagem declarativa. Agora que tomei vergonha na cara e estudei um pouco, descobri que é uma linguagem funcional, extremamente similar a Haskell.

Para experimentar Erlang, há o applet Try Erlang.
[/update]

[]’s
Cacilhας, La Batalema

FizzBuzz (No Stairway to Heaven)

Hoje um amigo meu veio falar comigo de uma brincadeira velha – e que eu não conhecia – chamada FizzBuzz.

[update 2010-01-15]
Sugestão de apontador do Cesar Barros: If something is worth doing….

A propósito, atualizei o código Lisp.
[/update]

A brincadeira consiste em imprimir uma sequência de números, tradicionalmente de 1 a 100. Porém os números múltiplos de 3 devem ser substituídos por fizz e os números múltiplos de 5 por buzz. Os números que são divisíveis por 3 e por 5 devem ser substituídos por fizzbuzz.

No Stackoverflow você pode encontrar as versões mais loucas, como LOLCODE, Brainf*ck, Ook, assembly de 8051, 6502 e Linux IA-32, Hebreu Estruturado, Cobol e Forth, como destaque para o poético código em Perl.

Aqui quero postar algumas soluções que achei interessantes.

**

Em Haskell:

putStr (concat [if (mod x 15)==0 then "fizzbuzz\n" else if (mod x 3)==0 then "fizz\n" else if (mod x 5)==0 then "buzz\n" else (show x) ++ "\n" | x <- [1..100]])

Em Python:

print "\n".join('fizzbuzz' if x%15==0 else 'fizz' if x%3==0 else 'buzz' if x%5==0 else str(x) for x in xrange(1, 101))

Em Perl:

print +(fizz)[$_%3] . (buzz)[$_%5] || $_, $/ for 1..100;

Em Common Lisp:

(format t "~{~A~%~}" (loop for x from 1 to 100 collect (if (zerop (mod x 15)) "fizzbuzz" (if (zerop (mod x 3)) "fizz" (if (zerop (mod x 5)) "buzz" x)))))

[]’s
Cacilhas, La Batalema

Mais sobre reiteração

A reiteração ou iteração é um dos mais efetivos algoritmos para para processamento de sequências, mas sua eficiência não se limita a processamento de conjuntos prontos, essa técnica de algoritmo também pode ser usada para processamento de amostragens em plena coleta.

Vamos a um algoritmo bem simples, a média aritmética:


O algoritmo reiterativo pode ser expresso da seguinte forma:

(defun mean ((a-list list))
  (/
    (apply #'+ a-list)
    (length a-list)))

Agora imagine que você tem o registro contínuo do comportamento de um dado específico ao longo do tempo e gostaria de manter sua média sem preocupação como os valores em si (acho um caso pouco provável, mas…).

Se reparando bem, há dois dados importantes para o cálculo da média aritmética: a própria média e a quantidade de elementos. Basta que a função receba esses valores além dos novos valores que serão usados para atualizar a média anterior.

Assim é possível armazenar apenas a média atual e a quantidade de elementos avaliados:

(defun update-mean ((the-mean hash-table) (a-list list))
  (let ((*count* (+ (gethash 'count the-mean) (length a-list))))
    (setf (gethash 'mean the-mean)
      (/
        (+
          (apply #'+ a-list)
          (* (gethash 'mean the-mean) (gethash 'count the-mean)))
        *count*))
    (setf (gethash 'count the-mean) *count*)
    the-mean))

Então, além de receber a lista com os dados mais recentes (segundo parâmetro), a função recebe como primeiro parâmetro um hash com os dados de média anteriores.

O formato inicial do hash deve ser:

#s(hash-table :test fasthash-eql (count . 0) (mean . 0))

Ou seja, 'mean zero (0) e 'count zero (0). O hash será atualizado e retornado:

(setq *mean*
  (make-hash-table
    :initial-contents (list
      (cons 'count 0)
      (cons 'mean 0))))

Na próxima falarei em variância on-line.

[]'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 (zerop n)
    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>

Cálculos estatísticos: polinómio de Lagrange

Dando sequência aos artigos sobre cálculos estatísticos no Kodumaro – e em outros blogs amigos –, tive a ideia de falar sobre interpolação polinomial.

Por ser um método simples, decidi usar o polinómio de Lagrange:


Não é preciso calcular os coeficientes – é possível simplificar o cálculo final transformando parte do polinómio em um vetor de coeficientes, mas é mais fácil de visualizar sem fazê-lo.

C++

Dessa vez não vou usar C, mas C++, para poder usar recursos de orientação a objetos, como encapsulamento.

Primeiro vamos criar um namespace kodumaro e uma classe Lagrange. Abra o arquivo lagrange.h:

#ifndef LAGRANGE_H_
#define LAGRANGE_H_

namespace kodumaro {
    class Lagrange {
        public:
            Lagrange(const double *, const double *, int);
            ~Lagrange() {}

            double getY(double);

        private:
            const double *vector_x;
            const double *vector_y;
            int           length;
    };
}

#endif /*LAGRANGE_H_*/

O construtor irá receber um vetor de abscissas, um vetor de ordenadas e o tamanho dos vetores. Esses vetores representarão as coordenadas dos pontos a serem interpolados.

O método getY() retornará a ordenada para uma determinada abscissa, de acordo com a interpolação de Lagrange.

Agora o arquivo lagrange.cc contendo a implementação dos métodos:

#include "lagrange.h"

using namespace kodumaro;

Lagrange::Lagrange(const double *vx, const double vy, int len):
    vector_x(vx), vetory(vy), length(len) {}

double Lagrange::getY(double x) {
    double y = 0;

    for (int i = 0; i < length; ++i) { // ciclo do somatório
        double aux = vector_y[i];
        for (int j = 0; j < length; ++j) // ciclo do produtório
            if (i != j)
                aux *= (x - vector_x[j]) / (vector_x[i] - vector_x[j]);
        y += aux;
    }

    return y;
}

E está pronto! Basta incluir lagrange.h e compilar lagrange.cc junto com seu código teste.

O uso é simples:

kodumaro::Lagrange lagr(vx, vy, len);
y = lagr.getY(x);

Common Lisp

Não seria legal fazer isso sem usar uma linguagem funcional. =)

Também vamos aproveitar orientação a objetos – sim! É possível combinar orientação a objetos e programação funcional – para guardar nossos dados.

A classe será similar à de C++, mas o atributo será uma lista de pares de coordenadas:

(defclass lagrange ()
  ((pairs :initarg :pairs :accessor lagrange-pairs)))

Agora o método para calcular a ordenada em relação a uma abscissa:

(defmethod lagrange-get-y ((a-lagrange lagrange) x)
  (reduce '+
    (loop
      for '(xi . yi) in (lagrange-pairs a-lagrange)
      for i from 0
      collect (* yi (reduce '*
        (loop
          for '(xj . yj) in (lagrange-pairs a-lagrange)
          for j from 0
          collect (if (= i j)
            1
            (/ (- x xj) (- xi xj)))))))))

A relação entre esse código e a expressão matemática acima é praticamente 1:1.

O uso é:

(let ((a-lagrange (make-instance 'lagrange :pairs coordinates)))
  (setq y (lagrange-get-y a-lagrange x)))

Smalltalk

Se foi legal usar orientação a objetos numa linguagem onde a orientação foi costurada como em uma colcha de retalhos e em uma linguagem funcional, imaginem em uma linguagem realmente orientada a objetos!

Smalltalk é uma das linguagens mãe da orientação a objetos: criada antes de C a partir de Simula, é praticamente a linguagem que define os conceitos de orientação a objetos.

Como já disse antes, tornei-me fã do Squeak, devido a sua aplicabilidade educacional e ao XO.

No Squeak, abra o System Browser, se não houver um pacote Kodumaro crie-o e, dentro dele, uma categoria Kodumaro-Interpolation.

Na categoria, crie um classe:

PointArray subclass: #Lagrange
    instanceVariableNames = ''
    classVariableNames = ''
    poolDictionaries: ''
    category: 'Kodumaro-Interpolation'

Agora crie o método para calcular a ordenada para uma abscissa:

getY: x
    | y |

    y := 0.
    1 to: self size do: [ :i | | aux |
        aux := (self at: i) y.
        1 to: self size do: [ :j |
            (i ~= j) ifTrue: [
                aux := aux * (
                    (x - (self at: j) x)
                    /
                    ((self at: i) x - (self at: j) x)
                )
            ]
        ].
        y := y + aux.
    ].

    ↑ y

E pronto! Você pode testar instanciando Lagrange – o método new: recebe o tamanho do vetor como parâmetro – e passando a mensagem getY:.

Io

Io é uma linguagem prototipada baseada principalmente em Self e Lua, mas também em outras, como Smalltalk e Lisp.

O código Io pode ser:

Point := Object clone do(
    x := 0
    y := 0
)

Lagrange := List clone do(
    // Gostei da ideia desse método add
    add := method(sx, sy,
        p := Point clone
        p x = sx
        p y = sy
        append(p)
    )

    getY := method(x,
        y := 0
        for(i, 0, size - 1,
            aux := at(i) y
            for(j, 0, size - 1,
                // Havia feito diferente antes,
                // mas acho o if assim mais claro:
                if(i != j) then(
                    aux = aux * ( \
                        (x - at(j) x) \
                        / \
                        (at(i) x - at(j) x) \
                    )
                )
            )
            y = y + aux
        )
        return y
    )
)

Vou dar um exemplo de código pois, devido a ser uma linguagem recente, não há muita documentação.

Digamos que você salvou o código acima no arquivo lagrange.io:

Io> Importer FileImporter import("lagrange")
Io> v := Lagrange clone
Io> v add(1, 10)
Io> v add(2, 100)
Io> v add(3, 1000)
Io> v getY(2)
==> 100
Io> v getY(2.5)
==> 448.75

Conclusão

Bem, desta vez deixo a conclusão ao leitor e convido a quem quiser fazer também suas implementações.

Outro método muito interessante é o polinómio de Newton.

[]'s
Cacilhas, La Batalema

Cálculo da variância com linguagem funcional

A implementação de cálculos básicos de estatística em linguagens funcionais é tremendamente mais simples do que usando linguagens imperativas, como a tradicional C, muito usada devido a sua abstração matemática¹.

Escolhi como exemplo o cálculo da variância, que determina o grau de dispersão dos elementos de um conjunto ou vetor.

Para o cálculo da variância é preciso calcular a média dos elementos do vetor.

Média

Em quase todos os textos que li sobre variância, covariância e outras operações estastísticas, é aconselhado usar a média quadrada dos elementos, mas meu professor de estatística diz pra usar a média aritmética.

Então vamos implementar as duas.

Média aritmética

Média aritmética consiste no somatório de todos os elementos dividido pelo número de elementos.

Em C a implementação é:

double arithmetic_mean(double *v, int len) {
    double sum = 0;
    int i;
    for (i = 0; i < len; ++i)
        sum += v[i];
    return sum / len;
}

Em Common Lisp o mesmo algoritmo é implementado assim:

(defun arithmetic-mean (a-list)
  (/ (reduce '+ a-list) (length a-list)))

Desconsiderando a implementação em duas linhas contra seis ou sete em C, podemos citar algumas vantagens:

1. Em C é preciso informar o tamanho do vetor, enquanto em Common Lisp não – em C++ usando STL também não seria necessário.
2. Em C usamos diversar variáveis que mudam de estado em ciclos. Em Common Lisp usamos funções e retornos, numa relação 1:1 com a Matemática – por exemplo, Σx vira (reduce '+ x).
3. Realmente… duas linhas em Lisp contra seis ou sete em C. =)

Média quadrada

Média quadrada ou RMS consiste na raiz quadrado da razão do somatório dos quadrados dos elementos pela quantidade:

double root_mean_square(double *v, int len) {
    double sum = 0;
    int i;
    for (int i = 0; i < len; ++i)
        sum += v[i] * v[i];
    return sqrt(sum / len);
}

Observação: para usar sqrt() é preciso incluir o cabeçalho math.h.

Agora vamos fazer a mesma coisa em Common Lisp:

(defun root-mean-square (a-list)
  (sqrt
    (/
      (reduce '+ (mapcar (lambda (e) (* e e)) a-list))
      (length a-list))))

[update 2008-06-14]O código acima foi alterado segundo a sugestão do Pedro – veja comentários abaixo.[/update]

Esse ficou maiorzinho, no entanto mantém uma relação muito mais próxima com a expressão matemática do que C. No caso o form loop criou um novo vetor contendo os quadrados dos elementos, que foi reduzido por reduce e '+ – Σ.

Escolhendo uma média

Se você escolher a média aritmética, faça:

#define mean(v, len) arithmetic_mean(v, len)

Em Lisp:

(defun mean (a-list)
  (arithmetic-mean a-list))

E se escolher média quadrada:

#define mean(v, len) root_mean_square(v, len)

(defun mean (a-list)
  (root-mean-square a-list))

Numerador da variância

Há dois tipos de variância: populacional e da amostra. O cálculo é similar, mudando apenas o denominador. Portanto vamos calcular primeiro o numerador, idêntico para os dois tipos de variância.

Em C, o cálculo do numerador é:

double varnum(double *v, int len) {
    double mean_x = mean(v, len);
    double sum = 0;
    int i;
    for (i = 0; i < len; ++i)
        sum += pow(v[i] - mean_x, 2.);
    return sum;
}

Observação: para usar pow() é preciso incluir o cabeçalho math.h.

Agora em Common Lisp:

(defun var-num (a-list)
  (reduce #'+
    (mapcar (lambda (e) (expt (- e (mean a-list)) 2)) a-list)))

[update 2008-06-14]O código acima foi alterado segundo a sugestão do Pedro – veja comentários abaixo.[/update]

É claro, para quem está acostumado a ver códigos e mais códigos em linguagens derivadas de C o código em Lisp pode parecer confuso, mas se você for tentar explicar a um matemático sem conhecimento de C, verá que programação funcional se encaixa melhor à Matemática pura.

Variância populacional

A variância populacional consiste na razão do numerador calculado pela quantidade de elementos e é usada quando o vetor representa todos os elementos do universo desejado.

double populational_variance(double *v, int len) {
    return varnum(v, len) / len;
}

Em Common Lisp:

(defun populational-variance (a-list)
  (/ (var-num a-list) (length a-list)))

Variância da amostra

A variância da amostra consiste na razão do numerador calculado pela quantidade de elementos menos um e é usada quando o vetor representa apenas uma amostragem do universo desejado.

double sample_variance(double *v, int len) {
    return varnum(v, len) / (len - 1);
}

Em Common Lisp:

(defun sample-variance (a-list)
  (/ (var-num a-list) (-(length a-list) 1)))

Conclusão

Para operações estatísticas ou puramente matemáticas, linguagens funcionais podem ser uma alternativa mais eficiente do que linguagens imperativas.

[update 2008-06-07]Versão em Ruby pelo Tiago no Programando sem cafeína![/update]
[update 2008-06-10]Versão em Python pelo LKRaider no LKVenia! =)[/update]

[]'s
Cacilhas, La Batalema

¹Abstração matemática: quis dizer abstração de alto nível em busca de uma representação mais matemática.

Kanamit?

O Érico Andrei e o Ricardo Bánffy fizeram uma pegadinha de 1º de abril muito interessante, chamada Kanamit.

Na brincadeira, é feita a suposição de um framework para aplicações web em Lisp.

Mas sabe que a ideia não é tão estúpida assim? Ela me deixou cheio de ideias malignas…

É claro, não é um framework, mas vamos bricar de usar Lisp em aplicações web em ambiente GNU/Linux!

Primeiro baixe e instale o LIGHTTPD fly light. Não vou entrar em detalhes de instalação.

Habilite o uso de CGI – ainda preciso ver como habilitar FastCGI – e configure cgi.assign em lighttpd.conf com as seguintes entradas mínimas:

cgi.assign = (
    ".el"   => "/usr/bin/clisp",
    ".fas"  => "/usr/bin/clisp",
    ".lisp" => "/usr/bin/clisp",
    ".ss"   => "/usr/bin/guile"
)

Depois a gente brinca com Smalltalk.

Acrescente também index.lisp à variável index-file.names.

Tendo reiniciado o LIGHTTPD, podemos ir ao script index.lisp, que deve estar no diretório raiz do LIGHTTPD, configurado pela variável server.document-root.

; index.lisp

(defun floor-div (a b)
  (multiple-value-bind
    (resp)
    (floor (/ a b))
    resp))

(let (
    (content-type "text/html")
    (title "Teste de Lisp")
    (date "")
    (century ""))

  (multiple-value-bind
    (S M H d m y)
    (get-decoded-time)
    (setq date
      (format nil "~2,'0d/~d/~4,'0d" d m y))
    (setq century
      (format nil "~@r" (+ (floor-div (- y 1) 100) 1))))

  (format t "Content-type: ~A~%~%" content-type)
  (format t "<html>~%")
  (format t "<head>~%")
  (format t "<title>~A</title>~%" title)
  (format t "</head>~%")
  (format t "<body>~%")
  (format t "<h1 align=\"center\">~A</h1>~%" title)
  (format t "<p>Ol&aacute; Mundo!</p>~%")
  (format t "<p>Data: ~A</p>~%" date)
  (format t "<p>S&eacute;culo: ~A</p>~%" century)
  (format t "</body>~%")
  (format t "</html>~%"))

Agora acesse http://localhost/index.lisp.

Ok! Ok! Até aqui é só CGI… mas vou dar uma olhada com mais calma em FastCGI e quem sabe desenvolver um rascunho de framework só por curtição. =)

É claro, preferiria fazer em Smalltalk, mas alguém já fez primeiro. Deem uma olhadinha na Superfície Reflexiva.

[]'s
Cacilhas

PS: Artigo publicado nas Reflexões de Monte Gasppa e Giulia C..

Common Lisp

Uma das linguagens de programação mais interessantes que já conheci é Lisp.

Antes de começar, gostaria de pedir um pouco de tolerância e boa vontade do leitor, pois não sei programar em Lisp, só conheço o básico, portanto vou me arrastar pelo artigo tentando dizer algo útil… =/

Lisp é uma linguagem de programação funcional muito usada em projetos de IA. Há também algumas aplicações conhecidas feitas em Lisp, como Emacs e AutoCAD.

Antes de ser padronizada como Common Lisp, havia muitos dialetos.

Se você possui um sistema GNU/Linux a mão, podemos começar a experimentar:

bash$ clisp
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2006

[1]> 

Os comandos em Lisp são chamados forms e representados sempre entre parêntesis. Por exemplo:

[1]> (print "Olá Mundo!")

"Olá Mundo!"
"Olá Mundo!"
[2]> 

A primeira impressão é o resultado do form print, a segundo é o retorno.

Para criar uma variável podemos usar setq:

[2]> (setq foo 12)
12
[3]> foo
12
[4]> 

Outra forma é com let, que faz atamento, mas então a variável só existe no escopo:

[4]> (let ((bar 15)) (print foo) (print bar))

12
15
15
[5]> 

O último 15 é o retorno de let, que é o mesmo retorno do último form do escopo – (print bar).

Agora veja:

[5]> foo
12
[6]> bar


*** - EVAL: variable BAR has no value
The following restarts are available:
USE-VALUE      :R1      You may input a value to be used instead of BAR.
STORE-VALUE    :R2      You may input a new value for BAR.
ABORT          :R3      ABORT
Break 1 [7]> abort
[8]> 

Há alguns símbolos especiais, como t (verdadeiro), nil (nulo) e as palavras-chave, iniciadas por ::

[8]> :teste-de-lisp
:TESTE-DE-LISP
[9]> 

Lisp possui uma estrutura de par chamada cons:

[9]> (cons 3 4)
(3 . 4)
[10]> 

Listas em Lisp são conses aninhados:

[10]> (cons 1 (cons 2 (cons 3 (cons 4 nil))))
(1 2 3 4)
[11]> 

Um apelido para isso é:

[11]> (list 1 2 3 4)
(1 2 3 4)
[12]> 

O form car retorna o primeiro elemento do cons e o form cdr retorna o segundo:

[12]> (car (list 1 2 3 4))
1
[13]> (cdr (list 1 2 3 4))
(2 3 4)
[14]>

Só alguns forms – nem de longe tudo:

• push – coloca um elemento no começo de uma lista, retornando a lista;
• pop – remove o primeiro elemento de uma lista, retornando-o;
• defun – define e retorna uma função;
• format – imprime e/ou retorna uma string;
• if, case, cond e when – forms condicionais;
• block, prog e progn – bloco;
• loop – ciclo (loop) incondicional;
• dolist – equivale mais ou menos ao for de Python;
• lambda – lambda!!!
• sort – ordenação;
• =, eq e equal – igualdade;
• find – procura elemento numa lista.

Uma coisa curiosa de Lisp é sua sintaxe extremamente funcional:

[14]> (if (= foo 12) "sim" "não")
"sim"
[15]> 

Repare em (= foo 12)! Primeiro a função a ser executada – igualdade –, depois os parâmetros.

Para terminar de forma interessante esse artigo, segue o crivo de Aristóstenes:

(let ((c 0) (noprime (list)) (index 1) (max 5000))
  (loop
    (setq index (+ index 1))
    (if (not (find index noprime))
      (progn
        (format t "~D~4@T" index)
        (setq c (+ c 1))
        (let* ((j (* index 2)))
          (loop
            (pushnew j noprime)
            (when (>= j max) (return))
            (setq j (+ j index))))))
    (when (>= index max) (return)))
  (format t "~%Contagem de primos: ~D~%" c))

[update 2008-06-13]Código sugerido pelo Pedro:

(defun primos (max)
  (let ((c 0) (noprime ()))
    (loop
      for index-1 from 2 to max
      unless (member index-1 noprime)
      do (format t "~D~4@T" index-1)
      (incf c)
      (loop
        for index-2 from (* index-1 2) to max by index-1
        do (pushnew index-2 noprime)))
        (format t "~%Contagem de primos: ~D~%" c)))

Valeu Pedro![/update]

Em outro momento explicarei comando a comando. Por ora, espero que achem Common Lisp tão interessante quanto achei. Para mais informações, vejam em meu del.icio.us, principalmente esse tutorial.

[]'s
Cacilhas, La Batalema