sábado, 28 de novembro de 2015

A outra porta

O Paradoxo de Monty Hall consiste no fato de que, em se descartando algumas escolhas erradas, as que sobram desconhecidas combinam as probabilidades de estarem certas das descartadas.

Por exemplo, em três portas, atrás de uma há um prêmio. Você escolhe uma das três e o mestre de cerimônias abre uma das outras duas, mostrando que o carro não está lá. A porta que você escolheu continua com ⅓ de chance de ser a correta, mas a outra porta não escolhida ganha a possibilidade de conter o prêmio da que foi aberta, passando a ser de ⅔.

Isso acontece porque a porta com o prêmio e a porta escolhida (independente de ser a do prêmio ou não) influenciaram juntas na escolha da porta a ser aberta, mesmo que você não saiba qual a porta do prêmio.

Muita gente discorda disso, diz que se sobraram duas portas, as chances passa a ser ½+½ e não ⅓+⅔. Pode-se ficar horas (ou dias) discutindo isso. A melhor forma de se verificar isso é testando!

Vamos escrever uma classe que MasterOfCeremonies que oferece três portas, sendo uma premiada:
from random import choice


class MasterOfCeremonies:

    __slots__ = '__doors __prize __choice'.split()

    def __init__(self) -> None:
        self.__doors = 'ABC'
        self.__prize = choice(self__doors)
        self.__choice = None

    @property
    def doors(self) -> str:
        return self.__doors

    @property
    def wins(self) -> bool:
        if not self.__choice:
            raise TypeError
        return self.__choice == self.__prize

    def choose(self, door: str) -> None:
        if door not in self.__doors:
            raise ValueError
        self.__choice = door

Nossa classe guarda três portas (A, B e C), apenas uma premiada. Para testar, podemos jogar mil vezes e vermos em quantas vezes ganhamos.

Para facilitar, vamos escolher sempre a porta do meio:
if __name__ == '__main__':
    wins = 0
    for _ in range(1000):
        wc = MasterOfCeremonies()
        door = wc.doors[1]  # sempre a porta do meio
        wc.choose(door)
        wins += 1 if wc.wins else 0
    print('Wins:', wins)

Não importa quantas vezes você execute esse programa, vai sempre retornar um valor próximo de 333 vitórias – o que faz todo sentido! São mil lances, ⅓ dá 333.

Agora vamos adicionar o paradoxo: um método que abre aleatoriamente uma porta sem prêmio e outro que permite ao jogador trocar para a porta fechada restante.

Dentro da classe MasterOfCeremonies adicione os seguintes métodos:
    def remove(self) -> None:
        if not self.__choice or len(self.__doors) == 2:
            raise TypeError
        doors = set(self.__doors)
        others = doors - {self.__choices, self.__prize}
        other = choice(list(others))
        doors -= {other}
        self.__doors = ''.join(list(doors))

    def change(self) -> str:
        if not (self.__choice and len(self.__doors) == 2):
            raise TypeError
        doors = set(self.__doors)
        doors -= {self.__choice}
        self.__choice = list(doors)[0]
        return self.__choice

Agora vamos mudar nosso procedimento principal para trocar de porta após a abertura (remove) da porta sem prêmio:
if __name__ == '__main__':
    wins = 0
    for _ in range(1000):
        wc = MasterOfCeremonies()
        door = wc.doors[1]  # sempre a porta do meio
        mc.choose(door)
        mc.remove()         # descarta uma das portas sem prêmio
        door = mc.change()  # troca a porta escolhida
        wins += 1 if wc.wins else 0
    print('Wins:', wins)

Agora vem o mindfuck: não importa quantas vezes você execute esse programa, o número de vitórias em mil será sempre por volta de 667, ⅔ das tentativas!

Ou seja, o paradoxo realmente funciona. Volte lá na Wikipédia, porque a explicação é realmente muito boa. ;-)

[]’s

PS: Eu ia escrever os códigos em Prolog, pois sua abordagem de lidar com domínio de verdades é muito conveniente para este problema, no entanto Python é muito mais didática: já basta a dificuldade em entender o Paradoxo de Monty Hall, não precisamos de mais complicação com uma implementação complexa.

quarta-feira, 19 de agosto de 2015

Processamento e significância de dados

Glider Em T.I.C., Tecnologias da Informação e da Comunicação, há uma teoria muito importante de processamento e significância de dados.

Há três níveis de dados/informações, e entender esses níveis é essencial para a aplicação prática de data mining.

Dado

Dado é todo e qualquer elemento cru de informação, como números, textos, nomes, datas e até combinações de outros dados.

Por exemplo, a quantidade de pessoas na sala, seus nomes, suas datas de nascimento, etc.

Conceitos como “não sei” (termo técnico: indefinido), “não existe” (t.t.: nulo) e “vou ver” (t.t.: futuro) também são dados válidos.

Informação

Informação é o resultado da contextualização do dado, ou seja, o significado ou valor do dado dentro de um contexto. Quais as relações entre os dados.

No nosso exemplo, como cada pessoa se relaciona como cada uma das outras.

Conhecimento

O terceiro nível é o conhecimento, que é, dado um conjunto de informações, como posso tornar isso útil.

Por exemplo, dadas as pessoas na sala e suas relações, como isso pode ser útil pra mim e como eu posso ser útil nesse domínio.

[]’s

sábado, 8 de agosto de 2015

Instalando MoonScript sobre LuaJIT

Atualizado no blog novo.

MoonScript
Colocar MoonScript para trabalhar com LuaJIT não é trivial. É preciso uma série de pequenos hacks pra funcionar.

Vamos começar pelas dependências.

Dependências

MoonScript depende de quatro outros módulos para funcionar:
Instale alt-getopt normalmente no LUA_PATH de seu LuaJIT. Aqui para mim é /usr/share/lua/jit.

Para instalar LuaFileSystem, clone o repositório do GitHUB e não se esqueça de editar o arquivo config. As mudanças principais são:
PREFIX=/usr
LUA_LIBDIR=$(PREFIX)/lib/lua/jit
LUA_INC=$(PREFIX)/include/luajit-2.0

Isso considerando que seu LUA_CPATH esteja em /usr/lib/lua/jit.

Compile e instale normalmente.

Já LPeg merece uma atenção extra, já que ele não funciona com LuaJIT. No lugar, use LPegLJ.

Clone e instale LPegLJ no seu LUA_PATH, depois execute o seguinte comando:
cd /usr/share/lua/jit/
sudo ln -s lpeglj.lua lpeg.lua

Isso fará com que MoonScript pense tratar-se do LPeg original.

Instalando MoonScript

Com as três dependências instaladas, clone o projeto do GitHUB. Edite o Makefile, substituindo as ocorrências de lua5.1 e lua por luajit.

Remova as entradas local e global do Makefile.

Edite o hashbang dos arquivos bin/moon e bin/moonc trocando lua por luajit.

Execute make compile.

Copie os diretórios moon/ e moonscript/ para seu LUA_PATH.

Copie os arquivos bin/moon e bin/moonc para o diretório /usr/bin do sistema.

E pronto! Já deve estar funcionando! Qualquer dúvida, me avisem pra eu revisar o texto.

[]’s

segunda-feira, 22 de junho de 2015

MoonScript

Adaptado no blog novo.
MoonScript 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

sábado, 18 de abril de 2015

Tipos em Cython

Ontem fiz uma pequena introdução ao Cython.

Cython é uma plataforma que traduz código Python para C e o compila em biblioteca compartilhada importável no próprio Python. A linguagem em si é um superset de Python, com tipagem estática ou dinâmica (duck-typing) e suporte a código especial que pode ser traduzido diretamente para C.

Uma parte importante de Cython é sua tipagem estática, mas os tipos pode ser um pouco diferentes de Python.

Há tipos específicos, como struct e enum, que são traduzidos diretamente para o equivalente C, e tipo de extensão (cdef class). Entre eles:

Tipo CythonTipo CCoerção para Python 3
bool PyLongObject * bool
bint int bool
size_t size_t int
char char int
unsigned char unsigned char int
int int int
long long int
long long long long int
float float float
double double float
const char * const char * bytes
bytes PyBytesObject * bytes
const Py_UNICODE * const Py_UNICODE * str
unicode struct PyUnicodeObject str
object PyObject * object
list PyListObject * list
dict PyDictObject * dict
set PySetObject * set
tuple PyTupleObject * tuple
void * void * sem equivalência
struct S struct S dict
enum E enum E int

Todos os modificadores C (unsigned, const, long, *…) são aceitos. Na coerção de tipos, também é aceito &. Se um valor numérico for recebido por uma variável do tipo object, será usado PyLongObject * (inteiro de tamanho arbitrário) ou PyFloatObject * (ponto flutuante, equivalente a double de C).

[]’s
ℭacilhας, La Batalema

sexta-feira, 17 de abril de 2015

Cython

Nas últimas semanas tenho desenvolvido uma aplicação usando Cython e me surpreendi com o resultado.

Comecei usando o Cython apenas para compilar código Python – o que de fato rendeu o aumento de desempenho prometido –, mas então resolvi ir mais longe pra ver o quanto poderia extrair dessa plataforma: comecei a usar tipagem estática, funções C (cdef) e depois acabei migrando minhas classes para tipos de extensão (cdef classes).

A cada novo passo era perceptível o crescimento do desempenho e da coerência geral do código. Minha única crítica é quanto aos testes: o código fica muito difícil de ser testado, já que não é possível fazer monkey-patch para colocar os mocks.

Segundo a documentação, ao compilar código Python com Cython, você tem um aumento de 35% no desempenho do código. Usando a tipagem estática, o aumento é de 300% e usando funções C e tipos de extensão o aumento é de aproximadamente 15.000%.

Não posso confirmar esses números, pois não fiz medições exatas, mas uma fila do RabbitMQ que enchia com 6, 7 mil mensagens, encheu com 64 mil no mesmo período de tempo (eu estava fazendo apenas carga, sem consumir a fila).

Uma coisa que gostei muito no Cython é o feeling: tem uma pegada bastante parecida com a do Objective C, o que faz sentido.

Vou dar um exemplo da própria documentação do Cython:

Dado o seguinte código Python puro:
def f(x):
    return x**2-x

def integrate_f(a, b, N):
    s = 0
    dx = (b-a)/N
    for i in range(N):
        s += f(a+i*dx)
    return s * dx
Você pode salvar esse código em integrate.pyx e compilá-lo assim:
bash$ cythonize -ib integrate.pyx
Isso irá gerar o código equivalente em C (integrate.c) e compilá-lo na biblioteca integrate.so, que pode ser diretamente importada em Python:
bash$ python
>>> from integrate import integrate_f
>>>
Se você tiver o IPython, pode usar o Cython no prompt:
bash$ ipython
Python 2.7.9 (default, Jan  7 2015, 11:49:12) 
[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.56)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> %load_ext Cython
>>> %%cython
from integrate cimport integrate_f
De qualquer forma, só usando a biblioteca compilada em vez do código Python importado, Cython já promete um aumento de 35% de performance – o que não me frustrou.

Além disso, podemos adicionar tipagem ao código: Cython é um superset em Python, ou seja, é uma linguagem em si e um código Python é também código válido Cython.
def f(double x):
    return x**2-x

def integrate_f(double a, double b, int N):
    cdef:
        int i
        double s, dx
    s = 0
    dx = (b-a)/N
    for i in range(N):
        s += f(a+i*dx)
    return s * dx
Segundo a documentação, isso garante um desempenho 4 vezes superior ao de Python.

No entanto ainda é possível otimizar mais ainda o código! Cython tem uma sintaxe específica que gera código C diretamente, cdef:
cdef double f(double x) except? -2:
    return x**2-x

def integrate_f(double a, double b, int N):
    cdef:
        int i
        double s, dx
    s = 0
    dx = (b-a)/N
    for i in range(N):
        s += f(a+i*dx)
    return s * dx
O desempenho dessa função f em C promete ser 150 vezes melhor do que a mesma função em Python puro.

O except? -2 na função é usado para passar exceções para o código C. Em um outro momento posso entrar em mais detalhes.

Tipo de extensão

Tipos de extensão são equivalentes às classes de Python, porém mais restritos e muito mais eficientes.

Por exemplo, da a seguinte classe:
class Consumer(object):

    def __init__(self, backend):
        self.backend = backend

    def run(self, handler):
        resp = self.backend.get()
        return handler.handle(resp)
Considerando que as instâncias só serão executadas em Cython, o código equivalente estaria em dois arquivos, o primeiro consumer.pxd:
from backends.base cimport Backend
from handlers.base cimport Handler

cdef class Consumer:

    cdef:
        Backend backend
        int run(self, Handler handler) except? -1
Esse código .pxd equivale ao cabeçalho .h de C. Agora, o arquivo de implementação deve ser chamado consumer.pyx:
from backends.base cimport Backend
from handlers.base cimport Handler

cdef class Consumer:

    def __cinit__(self, Backend backend):
        self.backend = backend

    cdef int run(self, Handler handler) except? -1:
        cdef dict resp = self.backend.get()
        return handler.handle(resp)
Esse código promete ser muito mais eficiente que sua versão em Python, infelizmente métodos declarados como cdef são acessíveis apenas em C (e em Cython). Para que o método seja acessível em Python, ele deve ser criado como um método Python comum (def) ou pode ser usado cpdef.

O comando cpdef (C/Python def) cria a função C (como cdef) e um wrapper em Python para torná-la acessível. Se o módulo for importando com cimport, será usada a função C original; se for importado com o clássico import, será usado o wrapper.

Conclusão

Até agora não tive motivos para me arrepender de usar Cython, recomendo.

[]’s
ℭacilhας, La Batalema

quarta-feira, 15 de abril de 2015

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]

domingo, 29 de março de 2015

Gxref

Glider
Estou experimentando o ambiente gxref, parte do XPCE do SWI-Prolog, e tenho algumas impressões para compartilhar.


Editor de texto

O editor de texto, PceEmacs, é muito ruim. Baseado na porcaria do Emacs, possui comandos muito verborrágicos, é dolorosamente dependente do mouse e o search-replace é uma bosta.

Para quem está acostumado com o Vim, de comando curtos e eficientes, que não precisa do mouse pra nada – você não precisa tirar a mão do teclado enquanto edita –, o PceEmacs é um retorno às cavernas.

A única vantagem é que o syntax highlight é bastante eficiente.

File info

A aba File info é simplesmente maravilhosa! Relaciona todos os predicados, onde eles são usados e que predicados de outros módulos são usados no módulo atual.

É uma ferramenta caída dos céus para depurar erros de sintaxe e até mesmo de lógica.

Dependencies

A aba Dependencies exibe um grafo das relações entre os módulos que deixa muito claro como sua imagem se comporta.

Conclusão

O XPCE+gxref perde pontos pelo editor de texto ruim e por depender do X (não roda nativo no Mac OS X), mas todo o resto é muito eficiente, merecendo uma nota, de zero a dez, oito (8).

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