Encadeamento de funções

Encadeamento de função é o pattern onde um grupo de funções é encadeado.

Em uma cadeia, sempre a saída de uma função é a entrada da seguinte, o parâmetro inicial é fornecido à primeira função da cadeia, que segue executando as funções, e o resultado da última função é retornado como resultado da cadeia.

Vejamos como criar cadeia.

Python

A forma mais simples simples de encadear funções é simplesmente efetuar a chamada, como o código Python a seguir:

f1 = lambda x: x * 2
f2 = lambda x: x - 1
f3 = lambda x: x // 3

print(f3(f2(f1(8))))

Porém esse código é visualmente confuso e difícil de ser depurado. É conveniente criar uma fábrica (factory) de cadeias:

chain = lambda *funcs: \
    reduce(lambda acc, func: (lambda x: func(acc(x))),
    funcs or [lambda x: x])

the_chain = chain(
    lambda x: x * 2,
    lambda x: x - 1,
    lambda x: x // 3,
)
print(the_chain(8))

Repare que as funções agora estão na ordem em que são executadas:

1. O número é dobrado;
2. O resultado da primeira função é decrementado;
3. O resultado da terceira função é triplicado e retornado.

A função reduce() de Python executa a redução de um map/reduce: o primeiro parâmetro é uma função que recebe o acumulador e o próximo valor, retornando o resultado parcial.

O segundo parâmetro de reduce() é a lista a ser reduzida, no caso, a lista de funções ou, caso nenhuma função tenha sido informada, um função vazia que retorna o próprio parâmetro fornecido.

Com este procedimento, é possível reduzir a lista de funções a uma função representando o encadeamento das funções fornecidas.

Erlang

Em Erlang as coisas também podem ser interessantes.

Criaremos duas funções, uma fábrica a ser exportado (chain/1) e uma função de redução (chain/2) que não deve ser exportada:

-module(chain).
-export([chain/1]).

chain(Funs) when is_list(Funs) ->
    chain(Funs, fun(X) -> X).

chain([], Acc) -> Acc;

chain([Fun|Rest], Acc) when is_function(Fun) ->
    chain(Rest, fun(X) -> Fun(Acc(X)) end).

Você pode então executar no shell:

1> c(chain).
{ok,chain}
2> Fun = chain:chain([
2> fun(X) -> X * 2 end,
2> fun(X) -> X - 1 end,
2> fun(X) -> X div 3 end
2> ]).
#Fun<chain.1.134034448>
3> Fun(8).
5
4> 

Haskell

Haskell por outro lado já possui uma fábrica de cadeias, usando o carácter $, infelizmente na ordem inversa: primeiro as últimas funções a serem executadas, e por último as primeiras.

Então, por exemplo: f1 $ f2 $ f3 x é executado como f1 (f2 (f3 x)).

Crie um módulo:

module Chain where

the_chain :: Int -> Int
the_chain n = (`div` 3) $ (\x -> x - 1) $ (* 2) n

No prompt do ghci execute:

Prelude> :load chain.hs
[1 of 1] Compiling Chain            ( chain.hs, interpreted )
Ok, modules loaded: Chain.
*Chain> the_chain 8
5
*Chain> 

[]’s
Cacilhας, La Batalema

Introdução ao código ASCII (para iniciantes)

Atualizado no blog novo.

Código ASCII é a codificação de caracteres para valores numéricos de 7 bits mais aceita mundialmente e significa American Standard Code for Information Interchange – portanto, nada de ASC-2, por favor.

O ASCII não permite acentos ou diacríticos, apenas os caracteres mais comuns e uma série de 33 caracteres de controle. Porém, como a menor palavra binária (sequência de bits) usada é o byte, que usa 8 bits, um a mais que o ASCII, é possível criar supersets com o dobro¹ da capacidade como, por exemplo, o Latin-1 e o CP-1252.

Para quem está começando a tentar entender o código ASCII, é preciso saber que ele é composto de grupos. O primeiro grupo é o que possui sequência binária 00xxxxx, ou seja, dois zeros nas primeiras casas e qualquer combinação nas 5 seguintes. Isso dá uma combinação de 32 caracteres, com código de 0 (0000000) a 31 (0011111), e consiste nos caracteres de controle, como nulo (0), os caracteres de mudança de linha (10 e 13), o backspace (8), o escape (27) e o tab (9).

Há uma exceção, um carácter de controle perdido fora dessa sequência: o delete (127 – 1111111).

O grupo seguinte, 010xxxx (32 a 47) é uma sequência de caracteres de pontuação e símbolos matemáticos, a começar pelo espaço (32).

Então começam os números, dentro do grupo 011xxxx. Os números começam em 0110000 (48) e seguem até 0111001 (57). Uma forma fácil de pensar qual o código de um dígito numérico é somar 48 ao valor do número. Por exemplo, o código de 7 é (48+7=) 55.

O grupo 011xxxx segue com mais pontuações e símbolos matemáticos.

O o grupo seguinte é o das letras maiúsculas: 10xxxxx. O primeiro elemento, 64 (1000000), é o arroba (@), seguido das letras. Para saber o código de uma letra é só somar 64 ao índice da letra no alfabeto. Por exemplo, a letra F é 6ª letra do alfabeto, portanto seu código é (64+6=) 70.

Depois do Z (90), continuam mais pontuações e símbolos matemáticos, terminando com underscore (–, 95 – 1011111).

A próxima sequência, começando pela crase, são as letras minúsculas. A sequência é idêntica à anterior, apenas trocando o 6º bit (da direita pra esquerda) por 1: 11xxxxx, o que soma 32 ao número, e as letras coincidem o mesmo código.

Ou seja, se o código de F é 70, o código de f é (70+32=) 102.

Como esperado, a sequência após o z (122) continua com pontuações e símbolos matemáticos.

Exemplo

Como exemplo, vamos codificar a palavra Kodumaro:

K = 64 + 11      =  75
o = 64 + 15 + 32 = 111
d = 64 +  4 + 32 = 100
u = 64 + 21 + 32 = 117
m = 64 + 13 + 32 = 109
a = 64 +  1 + 32 =  97
r = 64 + 18 + 32 = 114
o = 64 + 15 + 32 = 111

Kodumaro ≡ 75, 111, 100, 117, 109, 97, 114, 111

Se você preferir, pode pensar em bits (é incrível, mas é mais simples): o 7º bit (1º da esquerda) é sempre 1 (letra), o 6º (2º da esquerda) é 0 para maiúsculas e 1 para minúsculas, os 5 seguintes são a ordem da letra no alfabeto:

A =  1 = 00001
B =  2 = 00010
C =  3 = 00011
D =  4 = 00100
E =  5 = 00101
F =  6 = 00110
G =  7 = 00111
H =  8 = 01000
I =  9 = 01001
J = 10 = 01010
K = 11 = 01011
L = 12 = 01100
M = 13 = 01101
N = 14 = 01110
O = 15 = 01111
P = 16 = 10000
Q = 17 = 10001
R = 18 = 10010
S = 19 = 10011
T = 20 = 10100
U = 21 = 10101
V = 22 = 10110
W = 23 = 10111
X = 24 = 11000
Y = 25 = 11001
Z = 26 = 11010

Voltando ao Kodumaro:

K = (letra)(maiúscula)11ª – 1.0.01011 – 1001011
o = (letra)(minúscula)15ª – 1.1.01111 – 1101111
d = (letra)(minúscula) 4ª – 1.1.00100 – 1100100
u = (letra)(minúscula)21ª – 1.1.10101 – 1110101
m = (letra)(minúscula)13ª – 1.1.01101 – 1101101
a = (letra)(minúscula) 1ª – 1.1.00001 – 1100001
r = (letra)(minúscula)18ª – 1.1.10010 – 1110010
o = (letra)(minúscula)15ª – 1.1.01111 – 1101111

E de fato é assim que é codificado e armazenado:

1001011.1101111.1100100.1110101.1101101.1100001.1110010.1101111

Ou melhor, em bytes:

0100101101101111011001000111010101101101011000010111001001101111

[]’s
Cacilhας, La Batalema

¹A cada bit que se acrescenta a uma palavra binária, sua quantidade de combinações dobra.

Um editor de textos rapidinho

Veremos como é simples criar uma aplicação gráfica rapidamente usando Tkinter.

Vamos começar a a partir de um boilerplate:

#!/usr/bin/env python
# coding: UTF-8
from __future__ import absolute_import, division, print_function, unicode_literals

#-------------------------------------------------------------
# Cabeçalhos
#

# Aqui vão entrar os imports

__all__ = ['Editor']


#-------------------------------------------------------------

class Editor(object):

    def mainloop(self):
        pass


#-------------------------------------------------------------
# Rodapé

if __name__ == '__main__':
    app = Editor()
    app.mainloop()

A primeira coisa que precisamos fazer é criar nossa janela raiz. Para tanto, adicione aos cabeçalhos o import:

from Tkinter import *

Método construtor

Em seguida, no começo da classe Editor, vamos começar a escrever nosso construtor:

class Editor(object):

    def __init__(self):
        root = self.root = Tk()
        root.title('EditPy')

Precisamos então de um frame para colocar os botões de abrir, salvar e salvar-como:

        fbuttons = Frame(root)
        Button(fbuttons, text='Open', command=self.open) \
              .pack(side=LEFT)
        Button(fbuttons, text='Save', command=self.save) \
              .pack(side=LEFT)
        Button(fbuttons, text='Save As', command=self.save_as) \
              .pack(side=LEFT)

O pai (master) do frame fbuttons é nossa janela raiz e o pai dos botões é o frame.

Agora precisamos de uma caixa de texto para editar e exibir o conteúdo dos arquivos. Primeiro vá aos cabeçalhos novamente e acrescente o import:

from ScrolledText import ScrolledText

Então, continuando o construtor, crie a caixa de texto com rolagem:

        steditor = self.steditor = ScrolledText(root)

Para fechar o construtor só falta exibir o frame e a caixa de texto, e colocar o foco na caixa:

        fbuttons.pack(expand=True, fill=X)
        steditor.pack(expand=True, fill=BOTH)
        steditor.focus()

Loop principal

Se você tentar rodar o código agora, nada acontece. Isso porque o método mainloop() faz isso: absolutamente nada.

Precisamos então, neste método, chamar o loop principal do Tkinter. Para isso, altere o método:

    def mainloop(self):
        self.root.mainloop()

Chamamos então o loop principal através da janela raiz (root).

Abrir um arquivo

Porém coisas estranhas e erros esdrúxulos podem acontecer, pois ainda não implementamos nenhum dos métodos chamados pelos botões – self.open, self.save e self.save_as.

Parece-me justo que comecemos pelo método de abertura de arquivo. Criemos a assinatura do método:

    def open(self):

Para abrir um arquivo, precisamos de uma ferramenta chamada askopenfilename que precisamos importar, então nos cabeçalhos acrescente:

from tkFileDialog import askopenfilename

Então, de volta ao método open(), podemos pegar o nome do arquivo e carregá-lo:

        filename = askopenfilename(title='EditPy | Open')
        if filename:
            self.filename = filename
            self.load_file()

O método load_file() é quem vai de fato carregar o arquivo, mas precisamos antes apagar o conteúdo da caixa de texto:

    def load_file(self):
        filename = self.filename
        steditor = self.steditor

        steditor.delete('@0,0', 'end')
        with open(filename) as fd:
            steditor.insert('@0,0', fd.read())

O método delete() da caixa de texto apaga parte do conteúdo da caixa e os parâmetros são os índices de começo e fim:

• @0,0 significa linha 0, coluna 0 (começo do texto);
• end significa o final do texto.

O método insert() inserte a string (lida do descritor de arquivo) na posição indicada (@0,0).

Salvando o texto

Para salvar o texto, precisamos implementar o método save(). Ele precisa:

1. Verificar se temos um nome de arquivo – se não tivermos, é um save_as.
2. Abrir o arquivo para escrita.
3. Obter o texto da caixa de texto.
4. Gravar o texto no arquivo.

Simples, indolor e o código é intuitivo:

    def save(self):
        filename = self.filename
        if not filename:
            return self.save_as()

        with open(filename, 'w') as fd:
            fd.write(
                self.steditor.get('@0,0', 'end')
            )

Repare nos índices usados no método get().

Em seguida é preciso saber o que fazer quando não temos o nome do arquivo ou quando escolhemos Save As.

Primeiro a assinatura do método:

    def save_as(self):

Caso haja um nome de arquivo, é honesto usá-lo como ponto de partida para caixa de diálogo de salvamento. Para isso precisamos separar o nome de diretório do nome base do arquivo e uma forma de fazer isso é com o método de string rfind.

Para sabermos qual o separador de diretórios usado, adicione aos imports:

from os import path

Então continue no método:

        filename, directory = self.filename, None
        if filename and path.sep in filename:
            index = filename.rfind(path.sep) + 1
            directory = filename[:index]
            filename = filename[index:]

[update 2014-04-12]
Optei por usar rfind, mas poderia ter usado path.basename e path.dirname. É uma questão de escolha e estilo.
[/update]

Feito o slice, já podemos exibir a caixa de diálogo de salvamento. Para isso precisamos da ferramenta asksaveasfilename.

Modifique o import do askopenfilename para:

from tkFileDialog import askopenfilename, asksaveasfilename

Continuando agora no método save_as(), podemos exibir a caixa de diálogo e, se algum arquivo for informado, chamar o método save():

        filename = asksaveasfilename(
            title = 'EditPy | Save As',
            initialfile = filename,
            initialdir = directory,
        )

        if filename:
            self.filename = filename
            self.save()

E pronto! Já pode testar seu editor de texto!

Lapidando

Uma forma de melhorar um pouco o visual da aplicação é usando a extensão ajulejada do tk, chamada ttk.

Para tanto, basta adicionar ao cabeçalho, no final dos imports:

from ttk import *

Você também pode usar os métodos wm_protocol() e bind_all() da janela raiz para adicionar funcionalidades interessantes, mas isso é história pra outro dia. ;-)

[]’s
Cacilhας, La Batalema

Tail call optimization

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Chamando fact(5):

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

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

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

[]’s
Cacilhας, La Batalema