MoonScript

Adaptado no blog novo.

Há muito pouco tempo atrás um amigo meu me sugeriu dar atenção à MoonScript. Admito que eu via a linguagem com preconceito, mesmo assim resolvi dar uma olhada.

Resultado: todos os meus códigos em Lua acabaram convertidos para MoonScript. :-)

A linguagem é extremamente enxuta, limpa e poderosa. Não vou entrar em detalhes, se estiver curioso, leia o guia da linguagem.

Mas também não puxei assunto por nada, vou dar alguns exemplos.

Paradigma Funcional

Para lidar com o paradigma funcional, a sintaxe de MoonScript é bem mais concisa e que a de Lua. Por exemplo, o combinador Y.

Lua é uma linguagem estrita e não suporta o combinador Y em sua forma lazy. Como MoonScript é compilado para código Lua, sofre do mesmo mal. Assim, é preciso usar o combinador Z, que é versão estrita do combinador Y.

O combinador Z é definido como: λf.(λx.xx)(λx.f(λv.xxv)). Isso é facilmente representado em MoonScript:

Z = (f using nil) -> ((x) -> x x) (x) -> f (...) -> (x x) ...

Com isso é possível, por exemplo, implementar facilmente o quick sort:

Z = (f using nil) -> ((x) -> x x) (x) -> f (...) -> (x x) ...

tconcat = (...) -> [e for t in *{...} for e in *t]

Z (qsort using tconcat) ->
    (xs) ->
        if #xs <= 1
            xs

        else
            x, xs = xs[1], [e for e in *xs[2,]]
            lesser = [e for e in *xs when e <= x]
            greater = [e for e in *xs when e > x]
            tconcat (qsort lesser), {x}, (qsort greater)

Orientação a Objetos

Em Lua é preciso toda uma ginástica com metatabelas para simular eficientemente orientação a objetos. MoonScript tem suporte a classes na linguagem.

Por exemplo, podemos criar uma pilha (stack) facilmente:

import bind_methods from assert require "moon"

class Stack
    list: nil

    set: (x) =>
        @list =
            next: @list
            value: x

    get: =>
        v = nil
        {value: v, next: @list} = @list if @list
        v

bind_methods Stack!

LuaJIT

Como MoonScript compila para código Lua tradicional, você pode gerar código para virtualmente qualquer plataforma que rode Lua, como LuaJIT e LÖVE.

Por exemplo, você pode usar C-structs e metatipos:

ffi = assert require "ffi"
import sqrt from math

ffi.cdef [[
    typedef struct { double x, y; } point_t;
]]

local Point = ffi.metatype "point_t",
    __add: (o) => Point @x + o.x, @y + o.y
    __len: => @\hypot!
    __tostring: => "(#{@x}, #{@y})"
    __index:
        area: => @x * @y
        hypot: => sqrt @x*@x + @y*@y

Point

bash$ luajit
LuaJIT 2.0.3 -- Copyright (C) 2005-2014 Mike Pall. http://luajit.org/
JIT: ON CMOV SSE2 SSE3 SSE4.1 fold cse dce fwd dse narrow loop abc sink fuse
> moon = assert(require "moonscript.base")
> Point = (moon.loadfile "point.moon")()
> p = Point(3, 4)
> = tostring(p)
(3, 4)
> = p:area()
12
> = #p
5
>

Bem, acho que já fiz propaganda suficiente da linguagem. ;-)

[]’s

Uma brincadeira rápida

Um jeito divertido de calcular Fibonacci usando NumPy:

from collections.abc import Callable
from numpy import matrix, long

def fib() -> Callable:
    m = matrix('1, 1; 1, 0', dtype=long)
    
    def fib(n: int) -> long:
        return (m ** n)[0, 0]
    return fib
fib = fib()

Cython

from libc.stdint cimport int64_t
from numpy cimport ndarray
from numpy import matrix, long


cdef:
    ndarray m = matrix('1, 1; 1, 0', dtype=long)


cpdef int64_t fib(int n):
    return (m ** n)[0, 0]

[]’s

[update 2015-11-28]
Código atualizado para Python 3 e versão Cython.
[/update]

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

Erlang vs Prolog

Simon Thompson Joe Armstrong criou Erlang a partir de Prolog – aliás, o primeiro compilador era escrito em Prolog.

[update 2014-05-25]
Faglia nostra: o programador Prolog e criador da linguagem Erlang é Joe Armstrong. Simon Thompson é o mantenedor e um dos resposáveis pela reescrita em C.
[/update]

Apesar de ser uma linguagem funcional, Erlang traz muita herança de Prolog e suporta o paradigma declarativo. Para demonstrar essa similaridade, vou colocar o código de fatorial: em Erlang e em Prolog, implementação simples (e ruim) e usando tail-call optimization.

Código Q&D

Vamos ao rápido e sujo, primeiro em Prolog:

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

Agora em Erlang:

fact(0) -> 1;
fact(N) when N > 1 -> N * fact(N - 1).

A intenção é mostrar como os códigos são parecidos.

Tail call optimization

Tanto Prolog quanto Erlang têm sistemas inteligentes de esvaziamento de pilha e usar um acumulador ajuda a tornar o programa mais eficiente.

O fatorial em Prolog fica assim:

fact(N, F) :- N >= 0,
              fact(N, 1, F).

fact(0, F, F) :- !.
fact(N, A, F) :- N1 is N - 1,
                 A1 is N * A,
                 fact(N1, A1, F).

Agora em Erlang:

fact(N) when N >= 0 -> fact(N, 1).

fact(0, A) -> A;
fact(N, A) -> fact(N-1, A*N).

Bônus

Tente adivinhar em qual linguagem é este código:

fact(N, F) :- N >= 0, fact(N, 1, F).
fact(0) --> { ! }, '='.
fact(N) --> { N1 is N - 1 }, mul(N), fact(N1).
mul(N, A, R) :- R is N * A.

[]’s
ℭacilhας, ℒa ℬatalema

Tail call optimization

Erlang, enquanto derivação funcional de Prolog, não possui loop reiterativo e resolve suas reiterações com recursão.

Porém as aplicações em Erlang são feitas para funcionar ininterruptamente por semanas ou anos, imagine então como ficaria a memória com o empilhamento de chamadas de função!

Para resolver isso, Erlang usa um recurso chamado tail call optimization.

Sempre que o fluxo de execução chega à última chamada da função (chamada last call ou tail call), antes da execução desta chamada, a função é removida da pilha de memória e a memória usada por ela já se torna candidata à coleta de lixo (garbage collection).

Vamos a um exemplo. Tomemos a implementação body recursive de fatorial:

fact(0) -> 1;
fact(N) when N > 0 -> N * fact(N-1).

Agora vamos executar: fact(5). – O que acontece?

• 5 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 5 é vinculado a N. A pilha contém fact(5) e N = 5.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 5 e 1.
• A chamada retorna 4, então é identificada a chamada a fact(4).
• 4 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 4 é vinculado a N. A pilha contém fact(5), N = 5, fact(4) e N = 4.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 4 e 1.
• A chamada retorna 3, então é identificada a chamada a fact(3).
• 3 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 3 é vinculado a N. A pilha contém fact(5), N = 5, fact(4), N = 4, fact(3) e N = 3.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 3 e 1.
• A chamada retorna 2, então é identificada a chamada a fact(2).
• 2 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 2 é vinculado a N. A pilha contém fact(5), N = 5, fact(4), N = 4, fact(3), N = 3, fact(2) e N = 2.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 2 e 1.
• A chamada retorna 1, então é identificada a chamada a fact(1).
• 1 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 1 é vinculado a N. A pilha contém fact(5), N = 5, fact(4), N = 4, fact(3), N = 3, fact(2), N = 2, fact(1) e N = 1.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 1 e 1.
• A chamada retorna 0, então é identificada a chamada a fact(0).
• 0 (zero) casa com a primeira assinatura da função, fact(0).
• A pilha contém fact(5), N = 5, fact(4), N = 4, fact(3), N = 3, fact(2), N = 2, fact(1), N = 1 e fact(0).^†
• fact(0) retorna 1 e é desempilhado.
• Na pilha de fact(1) é reconhecida a last call erlang:'*'/2 com os parâmetros 1 e 1, então fact(1) é desempilhado, assim como suas variáveis.
• Neste ponto tempos na pilhas: fact(5), N = 5, fact(4), N = 4, fact(3), N = 3, fact(2), N = 2 e 1*1.
• 1*1 retorna 1 e é desempilhado.
• Na pilha de fact(2) é reconhecida a last call erlang:'*'/2 com os parâmetros 2 e 1, então fact(2) é desempilhado, assim como suas variáveis.
• 2*1 retorna 2 e é desempilhado.
• Na pilha de fact(3) é reconhecida a last call erlang:'*'/2 com os parâmetros 3 e 2, então fact(3) é desempilhado, assim como suas variáveis.
• 3*2 retorna 6 e é desempilhado.
• Na pilha de fact(4) é reconhecida a last call erlang:'*'/2 com os parâmetros 4 e 6, então fact(4) é desempilhado, assim como suas variáveis.
• 4*6 retorna 24 e é desempilhado.
• Na pilha de fact(5) é reconhecida a last call erlang:'*'/2 com os parâmetros 5 e 24, então fact(4) é desempilhado, assim como suas variáveis.
• 5*24 retorna 120 e é desempilhado.

^†Agora repare como a pilha ficou sobrecarregada com poucas chamadas… imagine com fact(200)!

Essa foi uma implementação body recursive, que não aproveita as vantagens da tail call optimization. Vamos então a uma implementação tail recursive:

fact(N) when is_integer(N), N >= 0 -> fact(N, 1).

fact(0, Acc) -> Acc;
fact(N, Acc) -> fact(N-1, N*Acc).

[update 2013-07-30]
Acho de difícil leitura o uso da vírgula como operador de conjunção em guardas (coloquei no código apenas porque é o mais usado), então você também pode escrever a função fact/1 assim:

fact(N) when is_integer(N) andalso N >= 0 -> fact(N, 1).

É mais verborrágico, porém mais claro.
[/update]

A função fact/2 não possui guarda pois não será exportada, apenas é consumida por fact/1.

Chamando fact(5):

• 5 é inteiro e maior ou igual a 0, então pode ser tratado pela função fact/1.
• 5 é vinculado a N. Neste ponto temos na filha fact(5) e N = 5.
• É identificada a last call fact/2 com os parâmetros 5 e 1, então fact(5) é desempilhada, assim como suas variáveis.
• 5 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 5 é vinculado a N e 1 é vinculado a Acc.
• Neste ponto temos na pilha: fact(5, 1), N = 5 e Acc = 1.
• É executada a função erlang:'-'/2 com os parâmetros 5 e 1, retornando 4.
• É executada a função erlang:'*'/2 com os parâmetros 5 e 1, retornando 5.
• É identificada a last call fact/2 com os parâmetros 4 e 5, portanto fact(5, 1) é desempilhado, assim como suas variáveis.
• 4 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 4 é vinculado a N e 5 é vinculado a Acc.
• Neste ponto temos na pilha: fact(4, 5), N = 4 e Acc = 5.
• É executada a função erlang:'-'/2 com os parâmetros 4 e 1, retornando 3.
• É executada a função erlang:'*'/2 com os parâmetros 4 e 5, retornando 20.
• É identificada a last call fact/2 com os parâmetros 3 e 20, portanto fact(4, 5) é desempilhado, assim como suas variáveis.
• 3 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 3 é vinculado a N e 20 é vinculado a Acc.
• Neste ponto temos na pilha: fact(3, 20), N = 3 e Acc = 20.
• É executada a função erlang:'-'/2 com os parâmetros 3 e 1, retornando 2.
• É executada a função erlang:'*'/2 com os parâmetros 3 e 20, retornando 60.
• É identificada a last call fact/2 com os parâmetros 2 e 60, portanto fact(3, 20) é desempilhado, assim como suas variáveis.
• 2 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 2 é vinculado a N e 60 é vinculado a Acc.
• Neste ponto temos na pilha: fact(2, 60), N = 2 e Acc = 60.
• É executada a função erlang:'-'/2 com os parâmetros 2 e 1, retornando 1.
• É executada a função erlang:'*'/2 com os parâmetros 2 e 60, retornando 120.
• É identificada a last call fact/2 com os parâmetros 1 e 120, portanto fact(2, 60) é desempilhado, assim como suas variáveis.
• 1 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 1 é vinculado a N e 120 é vinculado a Acc.
• Neste ponto temos na pilha: fact(1, 120), N = 1 e Acc = 120.
• É executada a função erlang:'-'/2 com os parâmetros 1 e 1, retornando 0.
• É executada a função erlang:'*'/2 com os parâmetros 1 e 120, retornando 120.
• É identificada a last call fact/2 com os parâmetros 0 e 120, portanto fact(1, 120) é desempilhado, assim como suas variáveis.
• 0 casa com a primeira assinatura da função fact/2, portanto 120 é vinculado a Acc.
• Neste ponto temos na pilha: fact(0, 120) e Acc = 120.
• A função retorna 120, que é consumido pela chamada original.

Repare que a pilha permaneceu com tamanho constante por todo o processo. É possível executar fact(200) sem estourar a pilha, aumentando apenas o tempo de processamento.

Esta é então a dica para a programação de loops em Erlang: use funções tail recursive, que são aquelas cuja chamada da recursão (da própria função) é a última do procedimento, e armazena a resposta em um acumulador em vez de aguardar o retorno de cada reiteração para processar o próximo resultado.

[]’s
Cacilhας, La Batalema

Média harmónica

Já que falávamos de variâncias e médias, um dos cálculos mais belos de média é a média harmónica.

Vou roubar
a explicaçãoo exemplo da Wikipédia por pura preguiça… :-/

[update]
Roubar a explicação não… roubei o exemplo. Para a explicação deixei o apontador para o artigo na Wikipédia – mais preguiçoso ainda!
[/update]

Você se lembra do colégio, quando tinha de calcular a velocidade média percorrida por um carro, certo? Imagine que um carro faz uma viagem de x horas, tendo percorrido metade do tempo a 40Km/h e a outra metade a 60Km/h.

Calcular a velocidade média é bem fácil, não?



Então o carro percorreu a distância a uma velocidade média de 50Km/h, tornando fácil calcular, por exemplo, a distância: se o carro andou por 3h, percorreu 150Km.

Porém imagine que a proposição do problema não fosse quanto ao tempo, mas quanto à distância…

O carro percorreu metade do percurso (não do tempo) a 40Km/h e outra metade a 60Km/h. Qual a velocidade média?

Para obter esse resultado, precisamos da média harmónica:



Então é o equivalente a percorrer todo o trajeto a 48Km/h.

Isso também se aplica a diversos outros ramos, como a matemática financeira: se um investidor aplica um mesmo valor em compra de ações todos os meses, no final o preço médio das ações será a média harmónica dos preços das ações em cada mês.

Mãos à massa

Conversamos até agora sobre matemática, agora é hora de ver o código! Usarei novamente Scheme.

Vamos nos concentrar primeiro no cálculo do denominador. Novamente apelaremos para map/reduce.

O map será usado para inverter cada um dos elementos, para tanto usaremos a função lambda (λx.(1/x))x_i:

(map (lambda (x) (/ 1 x)) *list*)

Feito isso, precisaremos de um somatório desses elementos, portanto usaremos reduce novamente com #'apply e #'+:

(apply +
       (map (lambda (x) (/ 1 x)) *list*))

O numerador é fácil, é a quantidade de elementos, ou tamanho da lista:

(length *list*)

Basta dividirmos um pelo outro e, quase sem querer, já temos o cálculo da média harmónica!

(define harmonic-mean
  (lambda (*list*)
    (/
      (length *list*)
      (apply +
             (map (lambda (x) (/ 1 x)) *list*)))))

Se quiser testar com os valores do exemplo (40Km/h e 60Km/h):

(let ((params '(40 60)))
  (display (harmonic-mean params))
  (newline))

[update]
Ainda esperando o pessoal do Prettify corrigir o syntax highlighting para LISP.
[/update]

[]’s
Cacilhας, La Batalema

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

Variância

Uma das operações mais importantes e necessárias da matemática é a variância de amostra. É usada, por exemplo, para o cálculo do desvio padrão e da regressão linear.

Usando linguagens funcionais, a implementação fica muito mais elegante.

Erlang

Em Erlang, a função para o cálculo da variância toma o seguinte formato:

variance(List) ->
    Xm = mean(List),
    Num = lists:sum([math:pow(Xi - Xm, 2) || Xi <- List]),
    Denom = length(List) - 1,
    Num / Denom.

É preciso ainda definir a função de média, mean/1:

mean(List) ->
    lists:sum(List) / length(List).

LISP

Em Scheme a implementação é um pouco mais verbosa, mas ainda assim elegante.

Segue o código em R⁵RS:

(define variance
  (lambda (*list*)
    (let ((xm (mean *list*)))
      (/
       (apply +
              (map (lambda (x) (expt (- x xm) 2)) *list*))
       (- (length *list*) 1)))))

Também precisamos implementar a média:

(define mean
  (lambda (*list*)
    (/
     (apply + *list*)
     (length *list*))))

Paradigma imperativo

Para comparação, segue a implementação de variância em uma linguagem imperativa, C:

double variance(int length, double *list) {
    double x_mean = mean(length, list);
    double sum = 0;
    int i;

    for (i=0; i<length; ++i)
        sum += pow(list[i] - x_mean, 2.);

    return sum / (length - 1);
}

É preciso incluir o cabeçalho math.h. Segue a implementação da função mean():

double mean(int length, double *list) {
    double sum = 0;
    int i;

    for (i=0; i<length; ++i)
        sum += list[i];

    return sum / length;
}

Perceba a mudança de estado, o que não ocorre nos códigos funcionais.

Escolhi C em vez de Python, porque Python também suporta bem o paradigma funcional, enquanto C é quase necessariamente imperativa.

[]’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á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

Por que paradigma funcional é mais lento do que imperativo?

Alguém procurou no Google por que paradigma funcional é mais lento do que imperativo e caiu na página do Walter.

É uma pergunta interessante e a resposta não é muito difícil.

Se você programar recursivamente usando paradigma imperativo, vai ficar ainda mais lento do que funcional.

No paradigma funcional, recursividade é um recurso muito usado, enquanto que no paradigma imperativo é comum o uso de ciclos de repetição condicional – loops – para resolver os problemas por meio de reiteração – apesar de corrente, o uso do estrangeirismo iteração não é correto.

[update 2008-04-23]Eduardo Willians avisou que o dicionário Houaiss data a palavra «iteração» de 1858. Vide comentários abaixo.[/update]

Algoritmos reiterativos são conhecidamente mais eficientes do que algoritmos recursivos. Mesmo a recursão linear, sabidamente rápida, é ligeiramente mais lenta do que seu equivalente reiterativo.

Linguagens funcionais são otimizadas para trabalhar com recursividade, portanto mais eficientes em recursões do que linguagens imperativas, no entanto tal otimização não compensa a diferença de desempenho entre algoritmos recursivo e reiterativo.

No entanto o paradigma funcional não é necessariamente mais lento do que o imperativo para todos os casos.

Em procedimentos que exigem muita álgebra ou inteligência artificial, linguagens funcionais são mais eficientes, especialmente quando se faz a substituição dos algoritmos recursivos por funções fechadas.

Funções fechadas são difíceis de serem definidas, mas extremamente eficientes, muito mais do que reiterações. Combinadas com a otimização para recursividade, o uso de funções fechadas pode tornar o paradigma funcional mais eficiente do que o imperativo para casos específicos.

[]'s
Cacilhas, La Batalema