terça-feira, 7 de outubro de 2014

Inception

4525295943286785564630898738613180402752865746514908141289658206399306834966472673922031069344230677865113693205407878709601660268
[]’s

domingo, 24 de agosto de 2014

Combinador de ponto fixo

Glider 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

sábado, 24 de maio de 2014

Erlang vs Prolog

Poliedro

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

segunda-feira, 19 de maio de 2014

PL Framework

Glider
Falei sobre como gerenciar dados mutáveis em Prolog. O código final ficou assim:


-*- Prolog -*-
:- module(profile, [profile/2]).
:- dynamic profile/2.

set(ID, X) :- profile(ID, X), !.
set(ID, X) :- X =.. [Attr, _],
              E =.. [Attr, _],
              retractall(profile(ID, E)),
              assertz(profile(ID, X)), !.

set(_, []) :- !.
set(ID, [X|Rest]) :- set(ID, X), set(ID, Rest).

get(ID, R) :- findall(X, profile(ID, X), R).

drop(ID) :- retractall(profile(ID, _)).

Mas e se quisermos que os dados sejam persistentes, ou seja, sobrevivam entre execuções, como um banco de dados?

O dialeto SWI Prolog oferece um arcabouço com inúmeros recursos chamado PL Framework.

Para persistência, há a biblioteca persistency.pl.

O que temos de fazer é substituir algumas partes de nosso código pelos predicados da biblioteca. Começaremos importando o módulo: logo após a declaração do nosso módulo, na linha abaixo, acrescente a importação:
:- use_module(library(persistency)).

Em seguida, não precisamos mais declarar o predicado profile/2 como dinâmico, em vez disso vamos declarar uma persistência. Substituia a linha com dynamic por:
:- persistent profile(id:atom, attr:compound).

Agora precisamos subtituir as chamadas de retractall/1 por retractall_profile/2, protegidas por with_mutex/2.

Onde está:
              retractall(profile(ID, E)),

Substitua por:
              with_mutex(profile,
                         retractall_profile(ID, E)),

E substitua:
drop(ID) :- retractall(profile(ID, _)).

Por:
drop(ID) :- with_mutex(profile,
                       retractall_profile(ID, _)).

Agora precisamos substituir assertz/1 por assert_profile/2. Onde está:
              assertz(profile(ID, X)), !.

Substitua por:
              with_mutex(profile, 
                         assert_profile(ID, X)), !.

Você pode juntar os predicados dentro de with_mutex/2.

Precisamos agora de uma regra para conectar a uma base de dados em disco, por exemplo:
connect(File) :- db_attach(File, [gc]).

Se quiser um arquivo padrão:
connect :- connect('profile.db').

Código final com persistência

-*- Prolog -*-
:- module(profile, [profile/2]).
:- persistent profile(id:atom, attr:compound).

set(ID, X) :- profile(ID, X), !.
set(ID, X) :- X =.. [Attr, _],
              E =.. [Attr, _],
              with_mutex(profile,
                         (retractall_profile(ID, E),
                          assert_profile(ID, X))), !.

set(_, []) :- !.
set(ID, [X|Rest]) :- set(ID, X), set(ID, Rest).

get(ID, R) :- findall(X, profile(ID, X), R).

drop(ID) :- with_mutex(profile,
                       retractall_profile(ID, _)).

connect :- connect('profile.db').

connect(File) :- db_attach(File, [gc]).

Este artigo foi apenas um exemplo prático de Prolog.

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

sábado, 17 de maio de 2014

Pequeno glossário de Prolog

Glider Ontem eu escrevi um artigo simples sobre Prolog.

O artigo na Wikipédia em português me pareceu pouco completo e bastante confuso. Tem informações legais lá, mas em comparação com a versão em inglês deixa a desejar.

Não pretendo completar o que está escrito na Wikipédia (senão deveria completar lá), apenas descomplicar um pouco.

Pra começar, é preciso entender a estrutura de um programa em Prolog: consiste em um domínio de verdades, parecido com uma base de dados, e o ponto de entrada é uma pergunta (query). Dito isso, vamos definir os conceitos dentro do código:
  • Termo: qualquer dado em Prolog é chamado termo.
  • Átomo: é um nome de propósito geral sem significado inerente. É representado por uma sequência de letras e alguns caracteres, começando por uma letra minúscula, ou qualquer sequência entre piclas ('…'). Por exemplo: hanoi
  • Número: pode ser inteiro ou de ponto flutuante, não diferente de outras linguagens.
  • Termo composto: consiste em um átomo, chamado functor (que é uma cabeça ou cabeçalho) seguido de uma sequência de termos e/ou incógnitas separados por vírgulas e entre parêntesis, chamada argumentos. Por exemplo: hanoi(5, R)
  • Predicado: é uma função booleana, ou seja, que retorna verdadeiro ou falso. Um predicado pode ser um átomo ou um termo composto e deve ser definido por um fato ou por uma regra.
  • Operador: é um predicado normal de aridade 2, mas que pode ser representado de forma diferente. Por exemplo, o sinal de igual:
X = 2

É o mesmo que:
'='(X, 2)

  • Variável: prefiro evitar a expressão “variável”, pois ela é falsa, apesar de ser o nome oficial. Prefiro “incógnita”: a incógnita pode estar ligada (bound) ou não (unbound) a um termo e tem comportamento diferente de acordo com estar ou não ligada. É representada por uma sequência de letras iniciando por uma letra maiúscula ou um underscore (_). Por exemplo: X
  • Fato: indica que determinado predicado retorna verdadeiro. É um átomo ou termo composto seguido de um ponto. Por exemplo:
default(5).

  • Regra: condiciona o resultado de um predicado ao resultado de outro. É um átomo ou termo seguido de :- e então o predicado ao qual ele está condicionado. Por exemplo:.
move(_, X, Y, _, R) :- move(1, X, Y, _, R).

  • Pergunta (query): É a chamada de um predicado. Pode retornar verdadeiro, falso ou gerar uma exceção. No código, é uma linha iniciada por :- e terminada por ponto. No prompt ?- basta digitar o predicado seguido de um ponto e pressionar a tecla Enter.

Um detalhe importante é que coisas que não parecem predicados, também são! Por exemplo:
  • Vírgula: é operador (','/2) que avalia o primeiro um predicado (argumento) e só avalia o segundo se o primeiro for verdadeiro, ou seja, E lógico.
N1 is N - 1, fact(N1, F1)

  • Ponto e vírgula: operador (';'/2) que avalia o primeiro predicado e só avalia o segundo se o primeiro for falso, ou seja, OU lógico.
  • Exclamação: é um predicado de aridade 0 ('!'/0) que indica que, se a regra atual “casar” (match) com a pergunta, os próximos fatos ou regras não serão avaliados.
  • Qualquer operação matemática.

Como exemplo, segue uma implementação da resolução da torre de Hanói:
% -*- Prolog -*-
:- module(hanoi, [hanoi/0, hanoi/1, hanoi/2]).

hanoi :- hanoi(R), findall(_, show(R), _).
hanoi(R) :- default(N), hanoi(N, R).
hanoi(N, R) :- N > 0,
               findall(X,
                       move(N,
                            'a esquerda',
                            'a direita',
                            'o centro', X),
                       R).

default(5).

move(1, X, Y, _, move(X, Y)) :- !.
move(N, X, Y, Z, R) :- N1 is N - 1, move(N1, X, Z, Y, R).
move(_, X, Y, _, R) :- move(1, X, Y, _, R).
move(N, X, Y, Z, R) :- N1 is N - 1, move(N1, Z, Y, X, R).

show(move(X, Y)) :- format('mova o disco d~w para ~w~n', [X, Y]).
show([X|_]) :- show(X).
show([_|Rest]) :- show(Rest).

Consegue entender como funciona?

Para gerar um executável com SWI Prolog:
bash$ prolog -f hanoi.pl \
-g 'use_module(library(save)), qsave_program(hanoi, [goal(hanoi)])' \
-t halt

Bônus

Há um açúcar sintático em prolog, que é -->:
a --> b, c(x), d.

Significa o mesmo que:
a(Start, End) :- b(Start, V1), c(x, V1, V2), d(V2, End).

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

Dados em Prolog

Glider Há uns anos falei um pouquinho sobre Prolog: sobre predicados, átomos, termos compostos, fatos, regras, incógnitas, etc.

Só pra relembrar: um programa em Prolog é um conjunto de predicados – fatos e regras – e sua execução consistem em perguntas (queries) feitas a esse domínio de verdades. Na programação declarativa, a ideia não é dizer como o computador deve resolver o problema, mas sim descrever o problema.

O entendimento de Prolog é essencial ao entendimento da programação declarativa e, assim, para poder extrair o máximo do poder de linguagens mais modernas, como Erlang.

É uma história bonita, mas um exemplo um pouco mais prático iria bem, não?

Então imaginei um exemplo: um módulo que representa perfis de dados – por exemplo, dados de perfil de usuário.

Podemos começar o código dizendo para o sistema nosso módulo:
% -*- Prolog -*-
:- module(profile, [profile/2]).

A primeira linha é um comentário que avisa a alguns editores que o arquivo se trata de um código Prolog, a segunda declara o módulo profile, que exporta o predicado profile/2 (com aridade 2).

A seguir, podemos declarar nosso predicado profile/2:
:- dynamic profile/2.

Essa declaração diz que o predicado profile/2 é dinâmico, ou seja, muda ao longo da execução do programa.

Agora precisamos de um predicado para gravar novos dados de perfil. Façamos isso com uma regra:
set(ID, X) :- profile(ID, X), !.

Essa regra diz ao sistema que, se alguém questionar set(ID, X) – onde ID é o identificador do perfil e X é um atributo do perfil – e essa combinação for verdadeira, ele não deve assumir isso como ver dade e não avaliar demais regras ou fato (!).

A próxima regra é um pouco longa, então vou falar dela linha a linha:
set(ID, X) :- X =.. [Attr, _],

Aqui diz que o predicado é set(ID, X) (exatamente igual ao anterior), e X é um termo composto de aridade 1, cujo cabeçalho será atrelado à incógnita Attr.

Caso verdade, continua a próxima linha da regra:
              E =.. [Attr, _],

Então E é termo composto com mesmo cabeçalho e aridade de X, porém com parâmetro _, que significa qualquer coisa.

Então, se X for name(john), E será name(_).
              retractall(profile(ID, E)),

Remove o predicado com o dado de perfil com o mesmo identificador e o mesmo cabeçalho informados.
              assertz(profile(ID, X)).

Cria o predicado armazenando o atributo de perfil informada – e assim termina nossa regra.

E se quisermos criar uma lista de atributos para o mesmo identificador de perfil?

Podemos criar um predicado para isso. Comecemos pelo ponto de parar, que é quando nossa lista de atributos já foi esgotada:
set(_, []) :- !.

Essa regra diz que, se a lista de atributos está vazia, não precisa fazer mais nada. Mas e se contiver algum elemento? Precisaremos questionar o set/2 para aquele atributo e continuar chamando para o resto da lista:
set(ID, [X|Rest]) :- set(ID, X), set(ID, Rest).

Resolvido.

Podemos criar um predicado para retornar todos os atributos de uma identidade:
get(ID, R) :- findall(X, profile(ID, X), R).

Precisamos agora de um predicado de limpeza, um para remover todos os atributos de um identificador (o que significa apagar o identificador):
drop(ID) :- retractall(profile(ID, _)).

Vamos testar agora nosso módulo:
?- [profile].
true.

?- profile:set(1, [name(john), age(20), city(rio)]).
true.

?- profile:set(2, [name(jack), age(21), city(sao_paulo)]).
true.

?- profile(ID, city(City)).
ID = 1
City = rio ;
ID = 2
City = sao_paulo.

?- profile:get(1, R).
R = [name(john), age(20), city(rio)].

?- profile:drop(1).
true.

?- profile(ID, _).
2 ;
2 ;
2.

?- drop(_).
true

?- profile(ID, _)
false.

?- 

Espero que o exemplo tenha sido esclarecedor. Para fazer um tracing, você pode fazer a pergunta gtrace.

Observação: para a execução, foi usando SWI Prolog, uma das mais confiáveis e robustas implementações de Prolog da atualidade.

Complemento a este artigo: Pequeno glossário de Prolog.

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

sábado, 12 de abril de 2014

Modelo de dados em Python

Ao escrever uma classe em Python, é preciso ficar atento a algumas convenções a serem respeitadas.

Métodos especiais

Em Python, métodos começando e terminando com sublinha dobrado (__*__) são reservados e chamados especiais. Você não deve implementá-los se não souber o que está fazendo.

Métodos especiais podem fazer coisas maravilhosas ou criar comportamentos inesperados que zoarão com sua aplicação. São divididos em 12 tipos:
  1. Personalização básica;
  2. Acesso personalizado a atributos;
  3. Criação personalizada de classes;
  4. Verificações personalizadas de instâncias e subclasses;
  5. Emulação de chamada;
  6. Emulação de recipiente;
  7. Emulação de tipos sequenciais;
  8. Emulação de tipos numéricos;
  9. Regras de coerção;
  10. Gerenciamento de contexto;
  11. Pesquisa de classes old-style;
  12. Pesquisa de classes new-style.

Recomendo fortemente a leitura do documento Data model, é essencial ao bom programador.

Métodos privados

Métodos privados são iniciados com sublinha dobrado, mas não terminados da mesma forma (__*).
Um método privado não pode ser acessado de outro contexto a não ser da classe onde ele foi definido.

Isso não é de todo verdade… o que acontece de fato é que métodos privados são prefixados com um sublinha seguido do nome da classe, para evitar que sejam sobrescritos e prevenir acesso a partir de subclasses ou de fora do contexto da classe.

Por exemplo, no contexto da classe Person, todos os métodos iniciados com sublinha dobrado serão prefixados com _Person. Assim, __fix_data vira _Person__fix_data.

Isso permite que você faça herança múltipla de classes que possuem o mesmo nome de método privado sem conflitos.

Métodos protegidos

Há uma convenção em Python de que métodos com nome iniciado com um sublinha (_*) são protegidos, ou seja, só devem ser acessados no contexto da classe e de suas subclasses.

Nenhum tratamento é feito para evitar que sejam acessados de outros contextos, mas se espera que os programadores sigam a convenção.

A orientação em Python é que o programador não é nenhum bebezinho que precisa ser guiado e sabe o que está fazendo, portanto não aja como um bebê e respeite as convenções.

Atributos e propriedades

Tudo o que foi dito sobre métodos especiais, privados e protegidos também vale para atributos e propriedades.

[]’s
Cacilhας, La Batalema

Ordem de chamada dos métodos de inicialização

Quando você cria e instancia uma classe em Python, muita coisa acontece e acho que nem todos estão familiarizados com os passos.

Vamos dar uma olhada na sequência.

Criação da classe

Quando você cria uma classe com o statement class, a primeira coisa que acontece é o construtor (__new__) da metaclasse (por padrão type) ser chamado.

O construtor recebe como parâmetros a própria metaclasse, o nome da classe (str), uma tupla contendo as classes base da classe criada e um dicionário com métodos e atributos declarados no corpo da classe.

Caso você sobrescreva o construtor da metaclasse, ele precisa retornar o objeto instanciado, que você obtém do construtor da classe pai da metaclasse.

Em seguida o método de inicialização (__init__) da metaclasse é chamado, recebendo como parâmetros o retorno do construtor, o nome da classe, a tupla de classes base e o dicionário de métodos e atributos.

É recomendável não sobrescrever o construtor da metaclasse. Qualquer procedimento pode ser tranquilamente executado nos métodos e inicialização e de chamada.

Instanciação da classe

Quando você instancia a classe, o primeiro método a ser chamado é o método de chamada (__call__) da metaclasse. Ele recebe como parâmetros a classe e quaisquer parâmetros passados no comando de instanciação.

Em seguida é evocado o construtor da classe, recebendo a classe e quaisquer parâmetros passados no comando de instanciação.

É obrigatório que a instância criada pelo construtor de super seja retornada, caso o construtor seja sobrescrito.

Após o construtor, o método de inicialização da classe é chamado, recebendo como parâmetros o retorno do construtor e quaisquer parâmetros passados no comando de instanciação.

Chamando a instância

Caso o método de chamada seja implementado na classe, a instância é “chamável” (callable). Na chamada o método de chamada é executado recebendo a instância e quaisquer parâmetros passados na chamada da instância.

Quem é quem

Um pequeno código apenas com boilerplates que não executam nada, com o único objetivo de demonstrar onde fica cada método citado:
class Metaclasse(type):

    def __new__(meta, name, base, dict_):
        """ Este é o construtor da metaclasse """
        return type.__new__(meta, name, base, dict_)

    def __init__(cls, name, base, dict_):
        """ Este é o método de inicialização da metaclasse """
        type.__init__(cls, name, base, dict_)

    def __call__(cls, *args, **kwargs):
        """ Este é o método de chamada da metaclasse """
        return type.__call__(cls, *args, **kwargs)


class Classe(object):
    __metaclass__ = Metaclasse

    def __new__(cls, *args, **kwargs):
        """ Este é o construtor da classe """
        return super(Classe, cls).__new__(cls)

    def __init__(self, *args, **kwargs):
        """
        Este é o método de inicialização da classe.
        Como ela herda de object, não há necessidade de
        chamar super, mas quando houver, a forma é:
        super(Classe, self).__init__(*args, **kwargs)
        """

    def __call__(self, *args, **kwargs):
        """ Este é o método de chamada da classe """
        return None

[update 2015-04-18] Esta é a versão do código acima em Python 3:
class Metaclasse(type):

    def __new__(meta, name: str, base: tuple, dict_: dict) -> type:
        """ Este é o construtor da metaclasse """
        return type.__new__(meta, name, base, dict_)

    def __init__(cls, name: str, base: tuple, dict_: dict):
        """ Este é o método de inicialização da metaclasse """
        type.__init__(cls, name, base, dict_)

    def __call__(cls, *args, **kwargs) -> object:
        """ Este é o método de chamada da metaclasse """
        return type.__call__(cls, *args, **kwargs)


class Classe(object, metaclass=Metaclasse):

    def __new__(cls, *args, **kwargs) -> object:
        """ Este é o construtor da classe """
        return super().__new__(cls)

    def __init__(self, *args, **kwargs):
        """
        Este é o método de inicialização da classe.
        Como ela herda de object, não há necessidade de
        chamar super, mas quando houver, a forma é:
        super().__init__(*args, **kwargs)
        """

    def __call__(self, *args, **kwargs) -> None:
        """ Este é o método de chamada da classe """
        return None
[/update]

Dois dedos de prosa sobre método destruidor

O método destruidor (__del__) não é chamado quando o objeto perde todas as referências ativas, mas sim quando é coletado pelo garbage collector (gc).

Como o gc não tem hora certa para rodar e seu comportamento varia muito de uma implementação de Python para outra, não é recomendável confiar nele para executar procedimentos críticos.

O que você pode fazer é usá-lo para garantir determinados estados que podem ter sido esquecidos ou perdidos depois que a instância ficou sem referências.

Observações finais

As assinaturas do construtor e do método de inicialização da classe devem ser rigorosamente iguais.

[update]
Um detalhe importante é que, se o método de inicialização for sobrescrito alterando sua assinatura, não há necessidade de sobrescrever o construtor, porém se o construtor for sobrescrito alterando sua assinatura, é obrigatório que o método de inicialização também seja sobrescrito.

Detalhes da linguagem…
[/update]

A chamada do método de chamada da classe pai da meta classe deve passar os parâmetros esperados pelos argumentos nas assinaturas do construtor e da inicialização da classe. No exemplo acima, esta chamada (precedida por return) é:
type.__call__(cls, *args, **kwargs)

[update]
Um detalhe que esqueci de mencionar é que é justamente nessa chamada que o construtor e o método de inicialização são evocados.
[/update]

Os parâmetros passados são os esperados nas assinaturas citadas.

[]’s
Cacilhας, La Batalema

quarta-feira, 19 de março de 2014

RLock

Dando continuidade o artigo sobre thread, um recurso muito útil é lock reentrante.

Lock reentrante é uma variação de lock que pode ser realocado múltiplas vezes pelo mesmo thread e não pode ser liberado por outro thread. É muito útil em funções recursivas, mas funciona também para garantir que o lock seja alocado e liberado pelo mesmo thread.

A fábrica (factory) para criar locks reentrantes é threading.RLock.

É preciso tomar cuidado para que todos os threads compartilhem o mesmo lock, senão ele se torna inútil:
lock = RLock()

thr1 = Thread(target=func1, args=(lock, ))
thr2 = Thread(target=func2, args=(lock, ))
thr3 = Thread(target=func3, args=(lock, ))

Dentro da função, é preciso alocá-lo (acquire) no inicío e liberá-lo (release) ao final. Por exemplo:
def func1(lock):
    lock.acquire()
    try:
        # executa o procedimento
        ...
    finally:
        lock.release()

Protegendo um objeto mutável

Uma utilidade para o lock reentrante é proteger métodos que alterem o conteúdo de um objeto.

Imagine que temos uma classe Person com dados, como identity_code (CPF) que podem sofrer alterações em threads diferentes (sei que não é uma boa abordagem, mas apenas como exemplo).

Podemos criar um decorador que torna um método thread-safe usando lock reentrante:
def lock(wrapped):
    lock_ = RLock()

    @wraps(wrapped)
    def wrapper(*args, **kwargs):
        with lock_:
            return wrapped(*args, **kwargs)

    return wrapper

Esse decorador pode ser usado nos setters de cada propriedade:
class Person(object):

    ...

    @property
    def identity_code(self):
        return self.__identity_code

    @identity_code.setter
    @lock
    def identity_code(self, value):
        self.__identity_code = value

    ...

Na verdade essa abordagem não resolve 100% o problema, mas já reduz muito a ocorrência de bugs.

Protegendo qualquer objeto

Porém a abordagem acima apenas protege parcialmente o objeto e não funciona para classes de terceiros.

Outra abordagem é usar um lock para todo o objeto, tanto leitura quanto gravação, agnóstico a qual objeto está sendo protegido. Assim, não há necessidade de usarmos propriedades.

Vamos criar uma classe para trancar qualquer objeto:
class ObjectLocker(object):

    def __init__(self, obj):
        self.__obj = obj
        self.__lock = RLock()

    def __enter__(self):
        self.__lock.acquire()
        return self.__obj

    def __exit__(self, etype, exc, traceback):
        self.__lock.release()

No código a instância dessa classe será passada para os threads, que terá de usar with para acessar o objeto original.

Ao usar with, o objeto original será trancado para o thread atual e liberado ao final.

A passagem será:
locker = ObjectLocker(Person(...))
thr = Thread(target=func, args=(locker, ))

Dentro da(s) função(ões) func a instância de Person deve ser acessa da seguinta forma:
with locker as person:
    name = person.name
    person.identity_code = data['identity_code']

Espero que os exemplos tenham sido úteis.

[]’s
Cacilhας, La Batalema

sábado, 15 de março de 2014

Thread-safe

Tenho tido a necessidade de lidar com muitas bibliotecas de terceiros e teno percebi um erro (ou seria uma abordagem?) comum nas mais novas: quase nenhuma delas é thread-safe.

Acredito que, com o modismo do uso de corrotinas (chamadas lightweight threads), os programadores mais novos passaram a considerar os threads de sistema obsoletos, deixando de tomar cuidados essenciais para boas bibliotecas.

Bem, tenho uma novidade para vocês: threads não são obsoletos e corrotinas não resolvem todos os problemas do mundo. Há situações em que usar corrotinas pode ser a melhor opção sim, mas em alguns casos os bons e velhos threads ainda são o salva vidas.

Para que isso seja possível, na criação de bibliotecas é necessário tomar alguns cuidados:
  • Prefira sempre que possível usar objetos imutáveis. Prefira tuplas, strings, tipos numéricos básicos, etc.
  • Evite permitir que objetos agregados façam alteração em seu objeto contentor sempre que possível.
  • Em todos métodos e propriedades de um objeto que pode ser compartilhado (como o contentor citado) que alterem o estado do objeto, inicie com um RLock, chamando seu método acquire, e encerre chamando seu método release. Tome cuidado para que seja usada a mesma instância de RLock!
  • Não tenha medo de usar objetos do módulo threading: Condition, Event, Lock, RLock e BoundedSemaphore. Eles são seus amigos. ;-)
  • Se estiver difícil escrever testes, substitua threading por dummy_threading para os testes unitários, mas use threading para testes de aceitação.

[]’s
Cacilhας, La Batalema

terça-feira, 18 de fevereiro de 2014

Aspectos – parte II: mixins

Na parte I demos uma passada geral no conceito de aspectos. Aqui veremos os mixins.

Mixins são classes incompletas que apenas atribuem determinado comportamento às classes herdeiras.

Vamos a um exemplo bem esdrúxulo, mas suficiente: um objeto que armazena notas de alunos em um arquivo.
from cPickle import dumps, loads
import gdbm

__all__ = ['Banco', 'Notas']


class Banco(object):

    def __init__(self, file=None):
        if file is None:
            file = 'notas.db'
        if isinstance(file, basestring):
            file = gdbm.open(file, 'c')
        self.file = file

    def close(self):
        if self.file:
            self.file.close()
            self.file = None


class Notas(object):

    def __init__(self, matricula, db):
        self.matricula = matricula

        if not isinstance(db, Banco):
            raise TypeError(
                'expected Banco instance, got {}'
                .format(type(db).__name__)
            )

        self.db = db

        try:
            self.notas = loads(db[str(matricula)])
        except KeyError:
            self.notas = {}


    def save(self):
        db[str(self.matricula)] = dumps(self.notas)


    @property
    def primeiro_bimestre(self):
        return self.notas.get('1bim')

    @primeiro_bimestre.setter
    def primeiro_bimestre(self, value):
        self.notas['1bim'] = float(value)

    @property
    def segundo_bimestre(self):
        return self.notas.get('2bim')

    @segundo_bimestre.setter
    def segundo_bimestre(self, value):
        self.notas['2bim'] = float(value)

    @property
    def terceiro_bimestre(self):
        return self.notas.get('3bim')

    @terceiro_bimestre.setter
    def terceiro_bimestre(self, value):
        self.notas['3bim'] = float(value)

    @property
    def quarto_bimestre(self):
        return self.notas.get('4bim')

    @quarto_bimestre.setter
    def quarto_bimestre(self, value):
        self.notas['4bim'] = float(value)

    @property
    def recuperacao(self):
        return self.notas.get('rec')

    @recuperacao.setter
    def recuperacao(self, value):
        return self.notas['rec'] = float(value)

    @property
    def media(self):
        soma = sum(
            self.primeiro_bimestre or 0,
            self.segundo_bimestre or 0,
            self.terceiro_bimestre or 0,
            self.quarto_bimestre or 0,
        )
        m = soma / 4.

        rec = self.recuperacao
        if rec is not None:
            m = (m + rec) / 2.

        return m

Repare que temos o mesmo problema apresentando na parte I: está tudo misturado em uma única classe!

Podemos separar as partes de gerência de banco e serialização em classes diferentes, dedicadas a seu próprio aspecto, chamadas mixins.

A classe de faz serialização pode ser apenas isso:
class NotaSerializavelMixin(object):
    def load(self):
        s = self.retrieve()
        self.notas = loads(s) if s else {}

    def __str__(self):
        return dumps(self.notas)

A gerência de banco vai para outro mixin:
class PersistenciaMixin(object):
    def retrieve(self):
        try:
            return self.db[str(self.matricula)]
        except KeyError:
            return None

    def save(self):
        db[str(self.matricula)] = str(self)

Preferindo, é possível separar a gerência de notas em um mixin também:
class NotasMixin(object):

    @property
    def primeiro_bimestre(self):
        return self.notas.get('1bim')

    @primeiro_bimestre.setter
    def primeiro_bimestre(self, value):
        self.notas['1bim'] = float(value)

    ...

    @property
    def media(self):
        soma = sum(
            self.primeiro_bimestre or 0,
            self.segundo_bimestre or 0,
            self.terceiro_bimestre or 0,
            self.quarto_bimestre or 0,
        )
        m = soma / 4.

        rec = self.recuperacao
        if rec is not None:
            m = (m + rec) / 2.

        return m

Ao final, a classe principal será apenas uma cola dos mixins:
class Notas(NotaSerializavelMixin, PersistenciaMixin, MotasMixin):

    def __init__(self, matricula, db):
        self.matricula = matricula

        if not isinstance(db, Banco):
            raise TypeError(
                'expected Banco instance, got {}'
                .format(type(db).__name__)
            )

        self.db = db
        self.load()

A API da classe continua idêntica: recebe o número da matrícula e o banco na instanciação, propriedades para acessar as notas e método save() para salvá-las em arquivo, porém agora cada aspecto está isolado e encapsulado em seu próprio mixin.

[]’s
Cacilhας, La Batalema

Aspectos – parte I

Atualizado no blog novo.

Um paradigma muito útil é a Programação orientada a Aspectos.

Consiste em separar e encapsular as funcionalidades de um código conforme sua importância.

Nesta primeira parte, abordaremos de forma simples tal separação e deixaremos o conceito de mixins para a parte II.

Vamos começar com um exemplo: imagine uma view que modifica o estado de um objeto, retornando um hash do novo estado:
@app.route('/people/<uuid>/', methods=['PATCH'])
def update_person(uuid):
    person = db.person.find({ '_id': uuid }).first()
    if not person:
        raise Http404

    try:
        data = json.loads(request.data)
    except ValueError:
        return json.dumps({ 'error': 'invalid request' }), \
               400, \
               { 'Content-Type': 'application/json' }

    person.update(data)
    db.person.save(person)

    r = [(str(k), repr(v)) for k, v in person.iteritems()]
    r.sort()
    s = ';'.join('{}:{}'.format(k, v) for k, v in r)

    return json.dumps({ 'etag': md5(s).hexdigest() }), \
           200, \
           { 'Content-Type': 'application/json' }

A solução atende, mas é de difícil manutenção. Perceba que a função chamada update_person (atualiza pessoa) faz muito mais do que simplesmente atualizar os dados:
  • Recupera o documento do banco, retornando 404 se não existir;
  • Faz os parsing dos dados recebidos, retornando 400 em caso de erro;
  • Efetivamente atualiza o documento;
  • Serializa o objeto para a resposta;
  • Gera um hash da serialização;
  • Responde a requisição com formato conveniente.

Cada um desses passos é um aspecto do processo e pode ser isolado do restante.

Vamos então separar o primeiro aspecto: recuperação do documento.
def retrieve_person_aspect(view):
    @wraps(view)
    def wrapper(uuid):
        person = db.person.find({ '_id': uuid }).first()
        if not person:
            raise Http404

        return view(person)
    return wrapper

@app.route('/people/<uuid>/', methods=['PATCH'])
@retrieve_person_aspect
def update_person(person):
    try:
        data = json.loads(request.data)
    except ValueError:
        return json.dumps({ 'error': 'invalid request' }), \
               400, \
               { 'Content-Type': 'application/json' }

    person.update(data)
    db.person.save(person)

    r = [(str(k), repr(v)) for k, v in person.iteritems()]
    r.sort()
    s = ';'.join('{}:{}'.format(k, v) for k, v in r)

    return json.dumps({ 'etag': md5(s).hexdigest() }), \
           200, \
           { 'Content-Type': 'application/json' }

Agora a recuperação do documento está isolada, podendo inclusive ser usada em outras views. Nossa view já recebe o documento recuperado e não precisa lidar com o fato dele existir ou não.

Porém ainda temos muita coisa misturada. Por exemplo, a obtenção e parsing dos dados recebidos: isso caracteriza outro aspecto do código, que não a atualização do documento.

Podemos portanto, separá-los:
def parse_data_aspect(view):
    @wraps(view)
    def wrapper(person):
        try:
            data = json.loads(request.data)
        except ValueError:
            return json.dumps({ 'error': 'invalid request' }), \
                   400, \
                   { 'Content-Type': 'application/json' }

        return view(person, data)
    return wrapper

def retrieve_person_aspect(view):
    ...

@app.route('/people/<uuid>/', methods=['PATCH'])
@retrieve_person_aspect
@parse_data_aspect
def update_person(person, data):
    person.update(data)
    db.person.save(person)

    r = [(str(k), repr(v)) for k, v in person.iteritems()]
    r.sort()
    s = ';'.join('{}:{}'.format(k, v) for k, v in r)

    return json.dumps({ 'etag': md5(s).hexdigest() }), \
           200, \
           { 'Content-Type': 'application/json' }

A função update_person já está muito mais limpa: atualiza o documento, serializa e retorna o hash, mas ainda faz coisas demais. Vamos separar o tratamento do retorno:
def respond_etag_aspect(view):
    @wraps(view)
    def wrapper(person, data):
        response = view(person, data)
        return json.dumps({ 'etag': md5(response).hexdigest() }), \
               200, \
               { 'Content-Type': 'application/json' }
    return wrapper

def parse_data_aspect(view):
    ...

def retrieve_person_aspect(view):
    ...

@app.route('/people/<uuid>/', methods=['PATCH'])
@retrieve_person_aspect
@parse_data_aspect
@respond_etag_aspect
def update_person(person, data):
    person.update(data)
    db.person.save(person)

    r = [(str(k), repr(v)) for k, v in person.iteritems()]
    r.sort()
    return ';'.join('{}:{}'.format(k, v) for k, v in r)

As coisas estão ficando cada vez mais separadas. A única coisa que a função update_person faz agora além de atualizar o documento é serializá-lo. Isso também pode ser isolado:
def serialize_person_aspect(view):
    @wraps(view)
    def wrapper(person, data):
        response = view(person, data)
        r = [(str(k), repr(v)) for k, v in response.iteritems()]
        r.sort()
        return ';'.join('{}:{}'.format(k,v) for k, v in r)

def respond_etag_aspect(view):
    ...

def parse_data_aspect(view):
    ...

def retrieve_person_aspect(view):
    ...

@app.route('/people/<uuid>/', methods=['PATCH'])
@retrieve_person_aspect
@parse_data_aspect
@respond_etag_aspect
@serialize_person_aspect
def update_person(person, data):
    person.update(data)
    db.person.save(person)
    return person

Perceba que, com a separação dos aspectos em funções distintas, o código ficou muito mais semântico:
  • retrive_person_aspect apenas recupera o documento do banco;
  • parse_data_aspect apenas faz o parsing dos dados recebidos;
  • respond_etag_aspect apenas gera o formato correto da resposta;
  • serialize_person_aspect apenas serializa o documento;
  • finalmente, update_person apenas atualiza o documento.

Observações

  • db é um objeto de banco de dados MongoDB, apenas para fim de exemplo.
  • app é uma aplicação Flask, apenas para fim de exemplo.
  • A ordem dos decoradores é importante.
  • Os imports foram omitidos:
import json
from functools import wraps
from hashlib import md5

Na parte II abordaremos mixins.

[]’s
Cacilhας, La Batalema