domingo, 22 de janeiro de 2012

Média harmónica

Poliedro 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ção o 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?

(40Km/h + 60Km/h) / 2 = 50Km/h


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:

2 / ((1 / 40Km/h) + (1 / 60Km/h)) = 48Km/h


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))xi:
(map (lambda (x) (/ 1 x)) *list*)


Feio 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

segunda-feira, 16 de janeiro de 2012

Dissecando a variância

Paradigma funcional 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 xi é xi - x.

A variância populacional pode ser descrita como:
σ²x=1/n Σ(xi - xm)


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:
s²x=1/(n - 1) Σ(xi - xm)


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)²)xi, 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

domingo, 15 de janeiro de 2012

Variância

Glider 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

segunda-feira, 17 de outubro de 2011

Racket

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 DesignerControls, 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 FileGenerate 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

sábado, 15 de outubro de 2011

R.I.P. Dennis Ritchie

Artigo original nas Reflexões de Monte Gasppa e Giulia C..

Dennis Ritchie No mesmo mês em que morreu o mago da distorção da realidade, também nos deixa Dennis Ritchie, criador das linguagens de programação B (baseada em APL) e C e cocriador do sistema operacional UNIX.

Se Steve Jobs esteve envolvido direta ou indiretamente com cada avanço tecnológico que não fosse voltado para resolver problemas da própria máquina, salvo raríssimas exceções, Dennis Ritchie foi o criador da linguagem de programação – e dos conceitos envolvidos – usada como base para quase todas as linguagens modernas, além de ter participado ativa e diretamente da criação do sistema operacional que serve de base para todos os sistemas atuais que funcionam.

A parte mais triste é ver todo o bafafá em cima do falecimento de Jobs, mas nada se fala de Ritchie, tão importante quanto. Ou pior… vi programadores que não sabem quem foi Dennis Ritchie!

Como eu disse, um programador que não conheça Dennis Ritchie, Dijkstra e Knuth precisa mudar de profissão ou tomar muita porrada.


[]’s
Cacilhας, La Batalema

quarta-feira, 14 de setembro de 2011

Falsa indução ou a falácia da metodologia infalível

Glider Reza a lenda que um código bem testado é um código sem bugs.

Além de não acreditar em código sem bugs, ainda há um problema com a definição de «bem testado».

Hoje em dia os evangelistas das novas velhas metodologias de programação defendem que a experiência profissional seja secundária – quiçá irrelevante – caso as metodologias agile sejam corretamente aplicadas, e uma das regras de outro é entupir o código de testes.

Porém quantidade não é qualidade. Não adianta encher o código de testes se você não tem feeling sobre o que testar – e feeling só se adquire com experiência profissional.

Há uma série de armadilhas prontas para pegar os incautos que se creem blindados pelas metodologias.

Uma armadilha comum é a falsa indução.

Por exemplo, tenho um código que calcula a raiz quadrada e trinta testes para ele, todos passando:
bash$ nosetests
..............................
----------------------------------------------------------------------
Ran 30 tests in 0.013s

OK


No entanto, quando eu tento alguns valores:
bash$ python
Python 2.6.1 (r261:67515, Jun 24 2010, 21:47:49)
[GCC 4.2.1 (Apple Inc. build 5646)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from sqr import sqr
>>> sqr(16) # 4
7
>>> sqr(25) # 5
7
>>> sqr(144) # 12
45
>>> sqr(225) # 15
27
>>> sqr(256) # 16
58


Valores completamente loucos! Isso porque o código caiu em uma falsa indução:
# coding: UTF-8

from math import ceil

__all__ = ['sqr']

def sqr(num):
d = 10 ** int(ceil(len(str(num)) / 2.))
return (num % d) + (num // d)


É claro que uma boa metodologia, como TDD, é um ferramenta poderosíssima nas mãos de um programador experiente, mas pode se tornar uma arma de autodestruição nas mãos de um novato com excesso de confiança.

Então repito o conselho de um autor que escreveu, mais ou menos isto: não aprenda a programar em dez horas ou em dez dias; aprenda a programar em dez anos.

[]’jn
Cacilhας, La Batalema


PS: Você pode baixar os testes de http://cacilhas.info/falsa-inducao/tests.py. Repare que se substituir:
from sqr import sqr

por:
from math import sqrt as sqr

os testes continuam passando.