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



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*)

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

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

R.I.P. Dennis Ritchie

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

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

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

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.

Prolog

Certamente Prolog não é meu forte… nunca fiz nada útil em Prolog e não conheço a linguagem tanto quanto gostaria, mas já tive meu samadhi.

Prolog é uma linguagem de programação declarativa de propósito geral, voltada para inteligência artificial e linguística computacional.

Seu nome significa programmation en logique e foi criada no começo da década de 1970 por um grupo liderado por Alain Colmerauer em Marseille, França.

Predicados e domínio

A programação Prolog consiste em definir um conjunto de verdades chamadas fatos e relações entre os fatos, chamadas regras.

De um modo geral, fatos e regras são chamados predicados e o conjunto de predicados do programa é chamado domínio do problema.

Um fato define uma afirmação, uma verdade:

flor(cravo).

Esta linha de código está dizendo «cravo é uma flor», e é um predicado do domínio.

Regra é um predicado condicional:

gosta(ana, X) :- flor(X).

Ana gosta de X se X for uma flor, ou de forma mais precisa: se Ana gosta de X implica que X é um flor, ou seja, leia :- como implica em.

Lembre-se que implicância é uma operação não recíproca.

Consultas

O uso de Prolog se dá através de consultas (queries). Por exemplo, salve as duas linhas acima no arquivo ana.pro, execute o interpretador e digite:

| ?- [ana].
compiling ~/ana.pro for byte code...
~/ana.pro compiled, 2 lines read - 419 bytes written, 14 ms

(1 ms) yes
| ?- gosta(ana, cravo).

yes
| ?- gosta(ana, gato).

no

Tipos

Prolog possui quatro tipos: átomo, termo composto, número e lista. Um fato precisa ser um átomo ou um termo composto.

• Átomo: é uma constante. Representado por uma sequência de letras, números e underscore iniciada por uma letra minúscula ou uma sequência entre plicas. Ex.: cravo, 'ana.pro', 'Cacilhας, La Batalema'.


• Termo composto: é uma estrutura complexa. Consiste em um funtor seguido por um ou mais parâmetros entre parêntesis. O funtor deve ser um átomo, os parâmetros podem ser de quaisquer tipos. Ex.: gosta(ana, gato).


• Número: exatamente o que diz. É representado por dígitos numéricos e ponto (para ponto flutuante.) Ex.: 123, 3.1415.


• Lista: é uma sequência de elementos de outros tipos. Os delimitadores de início e fim são [] e os elementos são separados por vírgulas. O símbolo pipe (|) por ser usado para representar resto da lista. Ex.: [a, b, c], [abc | SX] (SX é uma lista).


• String: é um tipo especial de lista que contém apenas números inteiros entre 0 e 255. Ex.: "ABC" ≡ [65, 66, 67].

Incógnita

O equivalente a variável em Prolog é a incógnita, que consiste em um valor desconhecido, porém constante, representado por uma sequência similar ao átomo, mas iniciada por uma letra maiúscula.

Por exemplo, em:

gosta(ana, X) :- flor(X).

X é uma incógnita. A solução das consultas feitas acima é obtida encontrando o valor de X, o que é responsabilidade do programa.

Exemplo

Um exemplo clássico de Prolog é a implementação de fatorial:

factorial(0, 1).

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

O que o código diz é que o fatorial de 0 é 1 e se o fatorial de N é F implica que:

• N é maior que 0 (já está coberto pelo predicado anterior);
• N1 é igual a N menos 1;
• O fatorial de N1 é F1;
• E F é igual a N vezes F1.

Uso:

| ?- [factorial].
compiling ~/factorial.pro for byte code...
~/factorial.pro compiled, 7 lines read - 941 bytes written, 14 ms

(1 ms) yes
| ?- factorial(5, X).

X = 120 ?

yes

Um bom exemplo também é a implementação da solução da torre de Hanói, mas vai fritar seu cérebro:

hanoi(N) :- move(N, esquerda, direita, central).

move(1, X, Y, _) :-
    write('mova o disco da torre '),
    write(X),
    write(' para a torre '),
    write(Y),
    nl.

move(N, X, Y, Z) :-
    N > 1,
    M is N - 1,
    move(M, X, Z, Y),
    move(1, X, Y, _),
    move(M, Z, Y, X).

É claro que isso não é nem o começo. O objetivo é apenas causar água na boca.

[]’s
Cacilhας, La Batalema