31 de dezembro de 2012

OpenGL em Haskell

Continuo trabalhando no DuDuHoX.

A primeira interface do jogo é em console. Utiliza o pacote System.Console.ANSI. Funciona muito bem em Linux e Mac OS, apenas no Windows tem um pequeno problema de buffer, forçando com que o jogador tenha que apertar enter após cada jogada.

DuDuHoX versão console

Esta semana decidi fazer uma nova interface para o jogo: com gráficos e sem o problema de buffer do console do Windows.

Primeiramente tentei utilizar SDL, pois foi ela que utilizei para fazer DuDuRoX em C. Infelizmente, não tive sucesso nenhum, nem mesmo consegui fazer um exemplo compilar.

Pensei em utilizar diretamente OpenGL para o gráfico, mas não sabia o que utilizar para gerenciar a entrada do usuário (apertar de teclas). Já vi reclamações a respeito de OpenGL/GLUT. Foi então que depois de algumas pesquisas conheci o GLFW, um biblioteca C open-source que fazia tudo que eu precisava, e o mais importante: existe o pacote GLFW para Haskell que faz o binding.

Depois de algumas horas aprendendo OpenGL e GLFW para Haskell, o resultado é este:

DuDuHoX versão gráfica

Já está jogável com esta interface, porém a versão console possui mais funcionalidades. Então, para as próximas semanas, vou tentar passar todas as funcionalidades da versão console para a versão gráfica e adicionar algumas texturas bacanas. A lista de coisas a fazer e todo o código está disponível no GitHub: https://github.com/thiago-negri/DuDuHoX.

Feliz 2013!

15 de agosto de 2012

Programação funcional pura e útil

Acho que todos os programadores acostumados com o modelo imperativo ficam espantados em imaginar quão maluco é o modelo funcional puro. Afinal, como podemos fazer qualquer coisa útil sem gerar efeitos colaterais? Sem imprimir no console? Sem abrir uma tela? Sem gerar logs? Sem alterar variáveis? OMG.

Este também foi um espanto meu ao conhecer Haskell e por uma feliz insistência descobri que o problema está na cabeça do programador e não no modelo funcional puro.

Diferenças

Viver muito tempo no contexto das linguagens imperativas acabou modelando minha forma de pensar em uma maneira sequêncial. Eu sempre precisei dizer como fazer cada passo da computação, quais estados manter, quais variáveis alterar, quando retornar um valor, etc.

Enquanto que no mundo funcional puro, fui obrigado a pensar em uma maneira de transformação de dados. Ao invés de pensar em como fazer cada etapa, preciso pensar como transformar um dado em outro, i.e. como extrair a representação que quero a partir do dado que tenho.

Os exemplos clássicos para demonstrar esta diferença envolve a manipulação de listas.

Exemplo #1

Para calcular a somatória no estilo imperativo, é necessário pensar no controle sobre o estado da soma atual, que deve ser acumulado durante a iteração da lista.

int sum(int[] list) {
  int result = 0;
  for (int i : list)
    result += i;
  return result;
}

Do outro lado, no mundo funcional, é necessário pensar em como transformar uma lista em um único número que represente a soma de todos os elementos, i.e. a soma de uma lista vazia sempre será zero e a soma de qualquer outra lista é definida pelo seu primeiro valor acrescentado da soma do restante da lista.

sum [] = 0
sum (x:xs) = x + sum xs

Exemplo #2

Já em um exemplo um pouco mais complexo, em que precisamos manter duas listas no mundo imperativo, uma de entrada e outra de saída, precisamos incluir o controle sobre o índice de cada lista, para evitar erros de indexação.

String[] toText(int[] list) {
    String[] result = new String[list.length];
    for (int i = 0; i < list.length; ++i)
        result[i] = Integer.toString(list[i]);
    return result;
}

Enquanto que o mesmo exemplo no mundo funcional continua simples como a somatória da lista, a única diferença é que ao invés de transformarmos a lista utilizando a adição, utilizamos o próprio construtor de listas (representado pelo operador ':').

toText [] = []
toText (x:xs) = show x : toText xs

Motivação

Para demonstrar que o modelo funcional puro pode fazer muitas coisas além dos exemplos clássicos, de uma forma que considero bonita e com vantagens gratuitas, escrevo este post.

Calculadora

Hoje vamos criar uma calculadora em Haskell. Todo o código será puro, sem nenhum tipo de efeito colateral, incluindo uma DSL para escrever testes, o próprio executor dos testes e dois transformadores de cenários de teste, um para escrever o teste no formato de texto e outro para escrever o mesmo teste no formato de um JUnit.

Formato dos testes

Primeiramente, definimos o formato em que os testes serão escritos. Neste caso, será uma sequência de ações e validações:

data TestSequence =
    Do Action TestSequence
  | Check Assertion TestSequence
  | Done

Com esta estrutura de dados, os testes poderão ser escritos neste formato:

test =
  Do a.
  Do b.
  Do c.
  Check d$
  Done

A necessidade de ter o "Done" no final do teste me incomoda. Para evitar que precise escrever isto, indicarei que os testes sempre terminem de forma aberta, i.e. permitindo continuar a sequência:

type Test = TestSequence -> TestSequence

Agora podemos escrever o teste da seguinte forma:

test =
  Do a.
  Do b.
  Do c.
  Check d

Para mim, já está classificada como uma DSL funcional para testes.

O único tipo de ação disponível na calculadora é o de apertar seus botões e a única validação será a verificação do seu display. Os botões disponíveis são os padrões de uma calculadora.

data Action =
    Press Button

data Assertion =
    DisplayHasNumber Int

data Button =
    Zero
  | One
  | Two
  | Three
  | Four
  | Five
  | Six
  | Seven
  | Eight
  | Nine
  | Plus
  | Minus
  | Times
  | Divide
  | Equals
  | Clear
    deriving (Show)

Primeiro teste

O primeiro passo está pronto. Já temos uma DSL para testes compilando. Hora de escrever nosso primeiro teste, que também já compila:

sample :: Test
sample =
    Do (Press One).
    Do (Press Plus).
    Do (Press One).
    Do (Press Equals).
    Check (DisplayHasNumber 2).

    Do (Press Clear).
    Check (DisplayHasNumber 0).

    Do (Press Two).
    Do (Press Zero).
    Check (DisplayHasNumber 20).
    Do (Press Divide).
    Do (Press Two).
    Check (DisplayHasNumber 2).
    Do (Press Equals).
    Check (DisplayHasNumber 10)

Transformadores do teste

Como nosso teste está escrito na forma de uma estrutura de dados, isto nos dá muitas possibilidades para tratamento do caso de teste. Para facilitar as transformações desta estrutura, definimos uma função que aplica uma função genérica a cada passo do teste e agrupa os resultados em uma lista:

unroll :: (TestSequence -> a) -> Test -> [a]
unroll f t = g (t Done)
  where g Done = [f Done]
        g v@(Do _ next) = f v : g next
        g v@(Check _ next) = f v : g next

Teste -> Texto

Podemos processar o teste e gerar uma saída textual do cenário:

prettyPrint :: Test -> String
prettyPrint = unlines . unroll prettyPrintTestSequence

prettyPrintTestSequence :: TestSequence -> String
prettyPrintTestSequence s =
    case s of
      Done              -> "end"
      Do action _       -> prettyPrintAction action
      Check assertion _ -> prettyPrintAssertion assertion

prettyPrintAction :: Action -> String
prettyPrintAction (Press button) = 
    "press " ++ prettyPrintButton button

prettyPrintButton :: Button -> String
prettyPrintButton = map toLower . show

prettyPrintAssertion :: Assertion -> String
prettyPrintAssertion (DisplayHasNumber number) = 
    "the display should be showing the number " ++ 
    show number

Testando no GHCi:

\> putStr $ prettyPrint sample
press one
press plus
press one
press equals
the display should be showing the number 2
press clear
the display should be showing the number 0
press two
press zero
the display should be showing the number 20
press divide
press two
the display should be showing the number 2
press equals
the display should be showing the number 10
end

Teste -> JUnit

Também podemos gerar casos de teste para uma possível solução Java da nossa calculadora:

generateJUnit :: Test -> String
generateJUnit = 
    ("@Test\npublic void test() {\n" ++) . 
    unlines .
    unroll generateJUnitTestSequence

generateJUnitTestSequence :: TestSequence -> String
generateJUnitTestSequence s =
    case s of
      Done      -> "}"
      Do a _    -> generateJUnitAction a
      Check a _ -> generateJUnitAssertion a

generateJUnitAction :: Action -> String
generateJUnitAction (Press b) =
    generateJUnitButton b ++ ".press();"

generateJUnitButton :: Button -> String
generateJUnitButton b = "getButton" ++ show b ++ "()"

generateJUnitAssertion :: Assertion -> String
generateJUnitAssertion (DisplayHasNumber n) =
    "assertEquals(" ++ show n ++ ", getDisplayNumber());"

Testando no GHCi:

\> putStr $ generateJUnit sample
@Test
public void test() {
getButtonOne().press();
getButtonPlus().press();
getButtonOne().press();
getButtonEquals().press();
assertEquals(2, getDisplayNumber());
getButtonClear().press();
assertEquals(0, getDisplayNumber());
getButtonTwo().press();
getButtonZero().press();
assertEquals(20, getDisplayNumber());
getButtonDivide().press();
getButtonTwo().press();
assertEquals(2, getDisplayNumber());
getButtonEquals().press();
assertEquals(10, getDisplayNumber());
}

Teste de fato

E claro, também podemos utilizar nosso teste no formato de uma estrutura de dados para realmente testar uma calculadora:

data TestResult =
    Ok
  | Failed FailureMessage

type FailureMessage = String

instance Show TestResult where
    show Ok = "Test passed"
    show (Failed m) = "Test failed: " ++ m

checkTest :: Test -> TestResult
checkTest t = 
    evalState 
    (threadCheckState . unroll checkTestSequence $ t)
    mkCalculator

threadCheckState :: [State Calculator TestResult] ->
                    State Calculator TestResult 
threadCheckState = go 0
  where go _ [] = return Ok
        go n (x:xs) = x >>= (f n xs)
        f n xs Ok = go (n + 1) xs
        f n _ (Failed m) = 
          return . Failed $
            "Step " ++ show n ++ ". " ++ m

checkTestSequence :: TestSequence -> 
                     State Calculator TestResult
checkTestSequence Done = return Ok
checkTestSequence (Do a _) = checkAction a
checkTestSequence (Check a _) = checkAssertion a

checkAction :: Action -> State Calculator TestResult
checkAction (Press b) = do
    modify $ pressButton b 
    return Ok

checkAssertion :: Assertion -> State Calculator TestResult
checkAssertion (DisplayHasNumber n) =
    get >>= \c ->
      if displayNumber c == n
        then return Ok
        else return . Failed $ 
          "Wrong number in display, should be " ++
          show n ++ " but was " ++ show (displayNumber c)

O coração da calculadora

Finalmente, para que o testador-de-fato compile, precisamos definir uma primeira versão da nossa calculadora. Aqui você poderia tentar criar sua própria implementação. Cheguei neste código para atender ao cenário do teste:

data Calculator = Calculator {
    displayNumber :: Int
  , operation :: Maybe (Int -> Int -> Int)
  , savedNumber :: Int
  }

pressButton :: Button -> Calculator -> Calculator
pressButton b =
  case b of
    Zero    -> appendNumber 0
    One     -> appendNumber 1
    Two     -> appendNumber 2
    Three   -> appendNumber 3
    Four    -> appendNumber 4
    Five    -> appendNumber 5
    Six     -> appendNumber 6
    Seven   -> appendNumber 7
    Eight   -> appendNumber 8
    Nine    -> appendNumber 9
    Plus    -> saveOperation (+)
    Minus   -> saveOperation (-)
    Times   -> saveOperation (*)
    Divide  -> saveOperation div
    Equals  -> performOperation
    Clear   -> clear

appendNumber :: Int -> Calculator -> Calculator
appendNumber i c = 
  c { 
    displayNumber = (displayNumber c) * 10 + i 
  }

saveOperation :: (Int -> Int -> Int) -> 
                 Calculator -> Calculator
saveOperation f c = 
  c { 
    savedNumber = (displayNumber c)
  , displayNumber = 0
  , operation = Just f
  }

performOperation :: Calculator -> Calculator
performOperation c = 
  c { 
    savedNumber = newNumber
  , displayNumber = newNumber 
  }
  where newNumber = 
          case (operation c) of
            Nothing -> displayNumber c
            Just f  -> let a = savedNumber c
                           b = displayNumber c 
                        in
                           f a b

clear :: Calculator -> Calculator
clear = const mkCalculator

mkCalculator :: Calculator
mkCalculator = 
  Calculator { 
    displayNumber = 0
  , operation = Nothing
  , savedNumber = 0
  }

Testando a calculadora

Agora podemos executar o testador-de-fato contra nossa calculadora no GHCi. Vamos experimentar:

\> checkTest sample
Test passed

Isto significa que nossa calculadora está atendendo ao cenário de teste. Para garantir que o teste capture um comportamento que não corresponda ao cenário de teste, podemos introduzir um erro: alteramos o valor da multiplicação na função "appendNumber" de "10" para "100". Se rodarmos novamente o teste, teremos este resultado:

\> checkTest sample
Test failed: Step 9. Wrong number in display, should be 20 but was 200

Magavilha.

Conclusão

Construímos um código básico de uma calculadora funcionando que atende ao especificado no cenário de teste. Agora basta adicionarmos novos testes e continuar incrementando nossa calculadora, parecido com um TDD. Tudo isto foi feito de uma forma 100% pura, sem depender de nada que envolva IO, estado, variáveis ou logs.

Além do benefício de podermos fazer qualquer tipo de transformação nos cenários de teste, também podemos rodar quantas transformações e quantos testes quisermos de forma paralela, pois tanto o teste quanto a calculadora são thread-safe pelo simples fato de serem escritos de forma pura.

Conseguimos fazer tudo isto em míseras 251 linhas de código ou 5635 caracteres, incluindo comentários e linhas em branco. Quantas classes e/ou linhas seriam necessárias para contemplar todas as funcionalidades e seguranças demonstradas neste post na sua linguagem imperativa favorita?

Espero que este post sirva para inspirar vossas mentes a pensar "fora-da-caixa" do mundo imperativo. Existem muitas vantagens em aprender uma linguagem funcional pura, mesmo que você utilize linguagens imperativas para trabalhar.

O código inteiro está disponível no GitHub: https://gist.github.com/3354394. Para testar, é só baixar o código e carregar no GHCi.

Exemplos reais

Apenas para finalizar, alguns exemplos de aplicativos reais em uso desenvolvidos em Haskell:

12 de agosto de 2012

Criando um jogo de labirinto em Haskell

Quando eu estava aprendendo a programar em C, eu fiz vários pequenos projetos para colocar meu conhecimento à prova.

É muito bom olhar estes códigos antigos e perceber que aprendi muito nestes anos. Também é prazeroso ver que mesmo sem conhecer quase nada, consegui fazer muitas coisas divertidas.

Uma das primeiras coisas que fiz em C, foi um jogo de labirinto para terminal do Windows. Fiquei inacreditavelmente feliz e me achando muito inteligente por conseguir fazer um jogo assim.

Após algum tempo já programando, depois de conhecer a biblioteca SDL para criar jogos gráficos em C, o joguinho de labirinto chegou na sua terceira versão: DuDuRoX.

Como agora estou aprendendo Haskell e quero manter a tradição, irei criar um novo DuDuRoX nesta linguagem: DuDuHoX. Notem a pequena variação no nome demonstrando minha imensa criatividade.

Quem quiser acompanhar o progresso e fazer comentários, todo o código está disponível no GitHub (link no parágrafo acima).

Bastantes coisas já estão funcionando, até já é possível jogar. Quem quiser experimentar, é só baixar a plataforma Haskell, fazer um clone do repositório, executar o comando cabal install na pasta do jogo e ele estará disponível no seu terminal como "DuDuHoX".

Quem quiser dar uma olhada em códigos antigos, meus primeiros passos na programação estão postados no site Viva O Linux:

Alguns códigos mais "avançados", acabei não compartilhando, porém tenho eles salvos no meu computador, se alguém se interessar posso compartilhar também:

  • MultiMines: Jogo de campo minado.
  • HChess: Jogo de xadrez.
  • ObjectDetector: Tratador de imagem para realçar as bordas de objetos.
  • LConv: Conversor de "linguagens", a partir de uma pseudo-linguagem, o usuário conseguia definir regras de criptografia e aplicar a textos.
  • GATesting: Algoritmo genético para encontrar qualquer formula matemática que trouxesse como resultado o valor informado.

14 de julho de 2012

O futuro da programação

Postado originalmente em Seniortec.

De acordo com o índice TIOBE, em 1996 a linguagem de programação mais utilizada era C. Apenas dez anos mais tarde, em 2006, Java passou a ocupar o primeiro lugar. Por quê?

Com o baixo custo e o fácil acesso a grandes quantidades de memória, a transição de C para Java foi um reflexo natural dos programadores em busca de maneiras mais fáceis de gerenciar este recurso que crescia de maneira muito rápida.

Novamente estamos passando por uma quebra no paradigma computacional. A busca incansável por maior quantidade de ciclos é deixada de lado e da lugar à busca por paralelismo de operações e quantidade de núcleos de processamento.

As linguagens atuais estão preparadas para estas mudanças? Java ainda é bom o suficiente para manter sua hegemonia? Perguntas como estas começam a aparecer em artigos, fóruns, apresentações e congressos de nossa área.

Juntamente com estas perguntas, começa a surgir um interesse súbito por linguagens funcionais, como mostra a mensagem deste mês do índice TIOBE:

"Last month we asked ourselves the question what language could become the next big new programming language. We suggested several candidates such as Scala, Erlang and Clojure. Clearly, the new thing was expected to come from the functional programming field. A functional language not explicitly mentioned was Haskell. And this month it was Haskell that jumped from #35 to #25. Looking at the TIOBE trend graph of Haskell (starting in 2003) it shows a constant rise, with peaks in 2006, 2010 and now in 2012. This certainly sounds promising."

Todo este interesse não é preciosismo de alguns estudiosos. O paradigma funcional puro soluciona de uma forma muito suave a maioria dos problemas encontrados quando tratamos de assuntos de importância fundamental para esta nova arquitetura computacional: concorrência, paralelismo e escalabilidade.

A linguagem Haskell, por exemplo, oferece:

  • Estruturas de dados persistentes: seguras para ambientes concorrentes.
  • Operações que envolvem I/O são discriminadas de forma estática pelo sistema de tipos, o que gera uma cultura que preza pela pureza das bibliotecas. Garantindo escalabilidade de forma natural.
  • Operações que envolvem I/O são modeladas dentro de um conceito puro (Monad), permitindo composição, backtracking, computação não determinística, etc.
  • Polimorfismo aberto permite uma consolidação de uma única biblioteca e conceito, mesmo que construído de forma incompleta no primeiro release.
  • Avaliação preguiçosa possibilita um melhor gerenciamento do processamento e localidade em ambientes com escalabilidade.
  • Multiparadigmas para concorrência e paralelismo: locks, memória transacional, mensageria, filas, tópicos, paralelismo grátis com balanceamento de carga automático e threads baratas.

É fácil notar que Java já percebeu sua deficiência e busca soluções com as liberações novas. Neste ano será feita a liberação do Java 8 com suporte a mecanismos funcionais (projeto Lambda). A Apache decidiu não esperar pela nova versão e já têm a biblioteca Functor para tentar suprir estas necessidades. Assim também fez o Google com adições funcionais à biblioteca Guava.

Para a JVM já existem algumas linguagens tentando manter a plataforma aderente ao novo modelo de computação, por exemplo: Clojure, Groovy e Scala.

E você, está se preparando? Se você ainda não experimentou nenhuma linguagem funcional, te aconselho a ir logo conhecer o que este paradigma oferece. Seguindo o paradoxo de Blub, o ideal é começar com uma linguagem funcional pura, como Haskell, antes de avaliar linguagens como Scala que são híbridas e oferecem o paradigma tradicional.

15 de maio de 2012

Haskell Chat

Este post apresentará um programa simples de bate-papo por Telnet na linguagem Haskell.

Este programa servirá como um servidor de bate-papo, bastando que as pessoas conectem nele para que possam trocar mensagens entre si. As pessoas não precisarão conhecer onde os outros participantes do bate-papo estão na rede, o servidor se encarregará de redirecionar cada mensagem. Ele atuará parecido com um roteador.

As informações trafegadas na rede serão texto puro, tanto do cliente quanto do servidor, sendo assim não é necessário um cliente especial para utilização do serviço de bate-papo. Os clientes poderão se conectar ao servidor utilizando o Telnet.

Cabeçalho

Nosso servidor de bate-papo será um módulo Haskell projetado para rodar como um aplicativo O nome deste módulo será Main:

module Main(main) where

Imports

Para que o bate-papo funcione e possamos enviar informações pela rede, precisamos de acesso à camada de rede do sistema operacional:

import Network

Além disto, precisaremos utilizar controles sobre efeitos colaterais para que possamos atender mais de um usuário ao mesmo tempo:

import System.IO
import Control.Monad
import Control.Concurrent

Para que nosso servidor não fique apenas como um mediador de mensagens, faremos alguns tratamentos aos textos recebidos pelos usuários, por exemplo a utilização de alguns comandos, para isto precisaremos manipular Strings, que nada mais são do que listas de caracteres:

import Data.List

Tipos

Para controlar as informações que serão armazenadas e trafegadas. Iremos definir alguns tipos para nos ajudar a realizar este controle.

Mensagens

As mensagens trocadas entre usuários nada mais são do que Strings, então esta será nossa definição de mensagem:

type Message = String

Usuários

Será necessário dinstinguir quem mandou cada mensagem para saber para quem repassar cada mensagem, evitando que o próprio usuário receba sua própria mensagem e para que o bate-papo faça sentido.

Para isto precisaremos de um tipo que represente um usuário do bate-papo e que seja possível compará-lo com outros usuários. Este usuário será identificado por um nome e, para que seja possível distinguir usuários com o mesmo nome, por um identificador único.

data ChatUser = ChatUser { 
    userId :: Int, 
    username :: String }
        deriving Eq

Mensagens de bate-papo

A mensagem que recebemos pela rede é texto puro, mas precisamos associá-la ao usuário que fez o envio. Por isto temos um tipo que vincula uma mensagem a um usuário.

data ChatMessage =
    ChatMessage { 
        messageFrom :: ChatUser, 
        messageText :: Message }

E, para que seja possível notificar sobre a entrada ou saída de algum usuário, iremos declarar também outros dois tipo de mensagens do bate-papo: as mensagens de saída e as mensagens de entrada. As mensagens de saída poderão ter algum texto de despedida do usuário.

| QuitMessage { 
        messageFrom :: ChatUser,
        messageText :: Message }
    | JoinMessage {
        messageFrom :: ChatUser }

Instâncias

Como o servidor irá transmitir apenas texto puro, ao receber uma mensagem de um usuário e repassá-la a outro, será necessário exibir o usuário que enviou a mensagem de forma textual. Para isto declaramos uma instância de Show para nosso tipo ChatUser:

instance Show ChatUser where
    show (ChatUser uid name) = 
        name ++ "(" ++ show uid ++ ")"

Também será necessário trafegar os diferentes tipos de mensagens na forma de texto puro pela rede:

instance Show ChatMessage where
    show (ChatMessage user message) =
        show user ++ ": " ++ message
    show (QuitMessage user message)
        | null message =
            "! " ++ show user ++ " saiu."
        | otherwise =
            "! " ++ show user ++ " saiu: " ++ message
    show (JoinMessage user) =
        "! " ++ show user ++ " entrou."

Main

Porta de comunicação

Nosso bate-papo tem como principal objetivo funcionar via Telnet, então para isto faremos com que o servidor escute na porta 23, que é a porta padrão utilizada pelo Telnet.

port :: PortID
port = PortNumber 23

Identificação dos usuários

O identificador único de cada usuário será determinado pela ordem de chegada no servidor, i.e. o primeiro usuário terá o identificador 1, o segundo terá o identificador 2, e assim por diante.

Suportando múltiplos usuários

Para que nosso servidor não fique travado lidando com apenas um usuário, iremos criar Threads para lidar com cada usuário de forma concorrente.

Ao receber uma mensagem de um usuário, a Thread responsável por aquela conexão terá que repassar esta informação às demais, para isto utilizaremos um canal de envio e recebimento de mensagens que será compartilhado entre todas as Threads.

Este canal funciona como um tópico, quando alguém escreve nele, todos que estiverem escutando irão receber a mensagem. Assim será possível que a Thread lidando com outro usuário receba esta mensagem através deste canal de comunicação e repasse ao cliente.

Porém, se utilizarmos apenas uma Thread por cliente, esta só teria a chance de ler deste canal de comunicação depois do cliente enviar alguma mensagem. Pois a Thread ficaria bloqueada esperando por uma escrita no Socket.

Para evitar este problema, serão utilizadas duas Threads por cliente: uma responsável pelo recebimento de mensagens e outra responsável pelo envio.

Main

Nosso servidor iniciará definindo o número inicial de conexões (userCount), criando um canal de comunicação (chan), abrindo um Socket para escutar na porta definida anteriormente (socket) e aguardando conexões.

main :: IO ()
main = withSocketsDo $ do
         let userCount = 0
         chan <- newChan
         socket <- listenOn port
         handleConnections socket userCount chan

Aceitando conexões

Ao receber uma conexão, precisamos manter o handle para realizar a leitura e escrita de mensagens. Desligamos o buffer para que as mensagens sejam trocadas em tempo real.

Após definida a conexão, precisamos liberar nosso servidor para que possa atender outros usuários, então será criado um processo concorrente que atenderá esta conexão. O identificador único do usuário será definido no processo principal para evitar que dois usuários tenham o mesmo identificador.

handleConnections :: Socket -> 
                     Int -> 
                     Chan ChatMessage ->
                     IO ()
handleConnections socket userCount chan = do
    (socketHandle, _, _) <- accept socket
    hSetBuffering socketHandle NoBuffering
    let nextUser = (userCount + 1)
    _ <- forkIO $
      handleUserConnection chan socketHandle nextUser
    handleConnections socket nextUserNumber chan

Atendendo uma conexão

Para iniciar o atendimento à uma conexão, precisamos inicialmente do nome do usuário.

handleUserConnection :: Chan ChatMessage ->
                        Handle ->
                        Int ->
                        IO ()
handleUserConnection chan socketHandle userNumber = do
    name <- readUsername socketHandle

Com o nome do usuário e o identificador único fornecido pelo processo principal do servidor, conseguimos definir o usuário desta conexão e enviar uma mensagem ao canal de comunicação informando que o usuário entrou no bate-papo.

let thisUser = ChatUser userNumber name
    broadcast chan $ JoinMessage thisUser

Para que este usuário comece a receber as mensagens do bate-papo, criamos uma Thread separada para efetuar a leitura do canal de comunicação:

chanReader <- dupChan chan
    readerThread <- forkIO $
      startReader chanReader socketHandle thisUser

Este processo irá efetuar a escrita do canal de comunicação a partir das mensagens recebidas pelo Socket do cliente. O resultado deste processo, será uma mensagem de saída do usuário, caso ele deixe alguma. Caso ele desconecte sem deixar nenhuma mensagem, a exceção será capturada e convertida em uma mensagem vazia de despedida do usuário.

quitMessage <- (startSender chan 
                            socketHandle thisUser)
                            `catch` (\_ -> return "")

Com a mensagem de despedida em mãos, informamos os demais usuários que este deixou o bate-papo. Encerramos a Thread responsável por fazer a leitura do canal de comunicação e fechamos a conexão com o cliente:

broadcast chan $ QuitMessage thisUser quitMessage
    killThread readerThread
    hClose socketHandle

Recebendo o nome do usuário

Para receber o nome do usuário, apenas enviamos uma mensagem pedindo que ele informe seu nome e fazemos a leitura do Socket:

readUsername :: Handle -> IO String
readUsername socketHandle = do
    hPutStr socketHandle "Informe seu nome: "
    readLine $ socketHandle

Recebendo mensagens do canal de comunicação

O processo responsável por receber as mensagens do canal de comunicação só será encerrado com a desconexão do usuário, então ele sempre deve estar lendo do canal e publicando ao usuário. O próprio usuário irá enviar mensagens para o canal de comunicação, para evitar que ele receba mensagens dele mesmo, é aplicado um filtro para que só sejam exibidas mensagens de usuários diferentes dele.

startReader :: Chan ChatMessage ->
               Handle ->
               ChatUser ->
               IO ()
startReader chanReader socketHandle thisUser =
    forever $ do
        message <- readChan chanReader
        when ((messageFrom message) /= thisUser) $
            display message socketHandle

Enviando mensagens ao canal de comunicação

O processo responsável por enviar mensagens ao canal de comunicação deverá terminar de alguma forma. Seja por desconexão do usuário ou por uma mensagem de despedida do mesmo.

Para que o usuário saia do bate-papo, basta que ele envie uma mensagem iniciando com /quit seguido de sua mensagem de despedida. As demais mensagens recebidas do usuário serão repassadas ao canal de comunicação e não encerrarão o processo.

startSender :: Chan ChatMessage ->
               Handle ->
               ChatUser ->
               IO String
startSender chan socketHandle thisUser = do
    line <- readLine socketHandle
    if "/quit" `isPrefixOf` line
        then return . dropWhile (== ' ') $ drop 5 line
        else do
             broadcast chan $
                 ChatMessage thisUser line
             startSender chan socketHandle thisUser

Utilitários

Notificando os processos responsáveis por cada usuário

Para enviar uma mensagem a todos os usuários, basta realizar uma escrita no canal de comunicação.

broadcast :: Chan ChatMessage -> ChatMessage -> IO ()
broadcast = writeChan

Enviando mensagens para um usuário

Para enviar uma mensagem a um usuário, escrevemos a mensagem no Socket seguida de uma quebra de linha no formato Windows, para que a utilização via Telnet seja agradável.

display :: ChatMessage -> Handle -> IO ()
display message socketHandle = do
    hPutStr socketHandle (show message ++ "\r\n")
    hFlush socketHandle

Lendo mensagens de um usuário

Para ler uma mensagem do usuário, lemos uma linha do Socket e removemos o retorno do carro, para que fique apenas a mensagem escrita por ele.

readLine :: Handle -> IO String
readLine = liftM (filter (/= '\r')) . hGetLine

Código completo

O código completo está disponível no GitHub com a descrição Sample telnet chat in Haskell.

3 de abril de 2012

Sobrevivente.run()

Como sobreviver sem repetição de código no reino dos substantivos?

O que fazer quando encontramos código deste tipo:

A.java

Button button = new Button("Limpar");
button.addActionListener(new ActionListener() {
  public void performAction() {
    if (foo) {
      askConfirmation();
      bar.clear();
    }
  }
});

B.java

Button button = new Button("Limpar");
  button.addActionListener(new ActionListener() {
    public void performAction() {
      if (bacon) {
        askConfirmation();
        eggs.clear();
      }
    }
});

C.java

Button button = new Button("Limpar");
button.addActionListener(new ActionListener() {
  public void performAction() {
    if (baz) {
      askConfirmation();
      spam.clear();
    }
  }
});

Meu jeito é criar um verbo disfarçado de substantivo que leva consigo a ação que eu quero:

interface MagicClearWord {
  boolean isDirty();
  void clear();
}
class MagicClearWordExecutor implements ActionListener {
  private final MagicClearWord e;
  MagicClearWordExecutor(MagicClearWord e) {
    this.e = e;
  }
  public void performAction() {
    if (e.isDirty()) {
      askConfirmation();
      e.clear();
    }
  }
}

E depois utilizar como se fosse um "substantivo anônimo" (#nonsense):

A.java

Button button = new Button("Limpar");
button.addActionListener(new MagicClearWordExecutor(
  new MagicClearWord() {
    public boolean isDirty() {
      return foo;
    }
    public void clear() {
      bar.clear();
    }
  })
);

B.java

Button button = new Button("Limpar");
button.addActionListener(new MagicClearWordExecutor(
  new MagicClearWord() {
    public boolean isDirty() {
      return bacon;
    }
    public void clear() {
      eggs.clear();
    }
  })
);

C.java

Button button = new Button("Limpar");
button.addActionListener(new MagicClearWordExecutor(
  new MagicClearWord() {
    public boolean isDirty() {
      return baz;
    }
    public void clear() {
      spam.clear();
    }
  })
);

Ainda assim os substantivos e seus amigos gulosos comem seu tempo e seu espaço em disco com tanta palavra vazia. Parece que estamos presos mesmo.

Oh God, why?

13 de março de 2012

Almoço grátis de paralelismo em Haskell

Hoje irei exagerar um pouco e verificar o quão grátis é o almoço de paralelismo servido pelo ecossistema Haskell.

Para fins de estudo, irei criar um algoritmo bastante simples e ideal para utilizar paralelismo: duas funções distintas com cargas de trabalho parecidas que não possuem dependência entre si.

Uma destas funções calculará qual é o menor valor de uma lista e a outra calculará o maior valor. Sendo assim, as duas precisarão consultar todos os elementos da lista e fazer a mesma quantidade de comparações. Os dois valores serão somados e impressos ao usuário:

module Main where

import Data.List (foldl1')

main = print result
  where result = a + b
        a = foldl1' min list
        b = foldl1' max list
        list = [1..19999999]

Compilei o código com ghc -rtsopts e executei ele com +RTS -s para verificar como ele se comportou:

20000000
     803,172,764 bytes allocated in the heap
     860,135,516 bytes copied during GC
     233,464,876 bytes maximum residency (9 sample(s))
      30,086,296 bytes maximum slop
             483 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  1523 collections,     0 parallel,  0.80s,  0.97s elapsed
  Generation 1:     9 collections,     0 parallel,  0.92s,  1.30s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.90s  (  0.98s elapsed)
  GC    time    1.72s  (  2.27s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    2.62s  (  3.25s elapsed)

  %GC time      65.5%  (69.8% elapsed)

  Alloc rate    887,674,003 bytes per MUT second

  Productivity  34.5% of total user, 27.8% of total elapsed

Esta saída significa que o programa levou 3,25 segundos para executar e ocupou 483 MB de memória. Um valor um tanto absurdo para algo que deveria ser simples e rápido em Haskell. O problema do algoritmo é que durante o cálculo do valor mínimo, o coletor de lixo não coleta os itens já passados pois o cálculo do valor máximo possui referência para o inicio da lista.

Para resolver o problema é possível gerar listas diferentes, uma para cada cálculo na forma de uma função constante:

module Main where

import Data.List (foldl1')

main = print result
  where result = a + b
        a = foldl1' min $ list ()
        b = foldl1' max $ list ()
        list _ = [1..19999999]

Esta versão termina em 1,6 segundos e consome apenas 1 MB de memória. Atenção: se o programa for compilado com -O2, o GHC irá otimizar a declaração de função deixando a referencia para a lista no lugar e o programa continuará a usar os 483 MB de memória.

Este é o momento de refatorar o algoritmo para evitar duplicidade de código. Para um programa deste tamanho, acredito que normalmente não é feito, porém para que a transição para a utilização de paralelismo fique mais suave, é um passo necessário:

module Main where

import Data.List (foldl1')
import Control.Arrow ((&&&))

main = print result
  where result = (+) `uncurry` constMinMax list
        list _ = [1..19999999]

(.:) f g a b = f a (g b)
constApp = ($ ())
constMinMax = constMinList &&& constMaxList
constFold = foldl1' .: constApp
constMinList = constFold min
constMaxList = constFold max

O resultado e o tempo do algoritmo continuam os mesmos. Agora como tornamos este algoritmo preparado para rodar em paralelo? Simples: trocamos a utilização da função uncurry por parUncurry:

module Main where

import Data.List (foldl1')
import Control.Arrow ((&&&))
import Control.Parallel (par, pseq)

main = print result
  where result = (+) `parUncurry` constMinMax list
        list _ = [1..19999999]

(.:) f g a b = f a (g b)
constApp = ($ ())
constMinMax = constMinList &&& constMaxList
constFold = foldl1' .: constApp
constMinList = constFold min
constMaxList = constFold max
parUncurry f (a, b) = a `par` b `pseq` f a b

Adicionamos à compilação do programa o argumento -threaded e para executar utilizamos +RTS -s -N2 para que o programa utilize duas threads do sistema operacional. O resultado:

20000000
   1,606,300,044 bytes allocated in the heap
          74,364 bytes copied during GC
          28,352 bytes maximum residency (1 sample(s))
          24,896 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  1566 collections,  1565 parallel,  0.06s,  0.02s elapsed
  Generation 1:     1 collections,     1 parallel,  0.00s,  0.00s elapsed

  Parallel GC work balance: 1.79 (15355 / 8588, ideal 2)

                        MUT time (elapsed)       GC time  (elapsed)
  Task  0 (worker) :    0.00s    (  0.81s)       0.00s    (  0.00s)
  Task  1 (worker) :    0.75s    (  0.81s)       0.06s    (  0.01s)
  Task  2 (bound)  :    0.83s    (  0.81s)       0.00s    (  0.00s)
  Task  3 (worker) :    0.00s    (  0.00s)       0.00s    (  0.00s)

  SPARKS: 1 (1 converted, 0 pruned)

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    1.58s  (  0.81s elapsed)
  GC    time    0.06s  (  0.02s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    1.64s  (  0.83s elapsed)

  %GC time       3.8%  (1.9% elapsed)

  Alloc rate    1,019,478,198 bytes per MUT second

  Productivity  96.2% of total user, 189.6% of total elapsed

gc_alloc_block_sync: 78
whitehole_spin: 0
gen[0].sync_large_objects: 0
gen[1].sync_large_objects: 0

Conseguimos reduzir o tempo de execução para 0,83 segundos: a metade do tempo da versão sequencial. Tudo isto com a mudança de uma chamada (partindo do principio de que o programa está bem escrito).

Qual seria o tamanho da mudança necessária na linguagem que você utiliza hoje para ter este mesmo ganho de desempenho?

Apesar do exemplo deste post ser levemente exagerado, este tipo de ganho com apenas uma mudança é algo real em Haskell. A apresentação The Future is Parallel, and the Future of Parallel is Declarative feita por Simon Peyton Jones dá exemplos de aplicações que se beneficiaram deste paralelismo grátis.

2 de março de 2012

Convenções e obrigações

Aviso. Este post apenas levanta algumas questões sem oferecer nenhuma resposta, apenas sugestões.

Na programação orientada a objetos, os principios SOLID são bem difundidos. São cinco principios reunindo boas práticas em forma de convenções que tornam a programação orientada a objetos melhor, porém não são exigências do paradigma, i.e. os principios melhoram a vida e deveriam ser aplicados, mas não existe maneira de assegurar que eles foram. São eles:

  1. Single responsibility principle (SRP): Cada classe deve ter apenas uma responsabilidade e apenas uma razão para que ela sofra mudanças.
  2. Open/closed principle (OCP): As classes devem estar abertas para extensão e fechadas para modificações. Funcionalidades são adicionadas ao sistema através de código novo e não através de modificações de código existente.
  3. Liskov substitution principle (LSP): Uma classe só pode ser subclasse de outra se o funcionamento do código que utilize esta hierarquia não for alterado ao substituir uma pela outra.  Isto é, se uma função depende de uma coleção de objetos, não importa se o argumento é uma lista ou uma árvore, o resultado deve ser o mesmo.
  4. Interface segregation principle (ISP): Contratos devem ser resumidos, funções devem depender de contratos que reflitam apenas sua necessidade e nada mais.  Vários contratos pequenos são melhores do que um alguns contratos grandes.
  5. Dependency inversion principle (DIP): Métodos devem depender de contratos e não de tipos concretos. 

Além destes existe um principio que vale para todos os paradigmas: "Don't repeat yourself" (DRY).  O nome deste é bem intuitivo: não repita código.

Apesar de todas estas convenções serem boas, todas elas possuem a mesma falha: são convenções. Convenções são facilmente esquecidas, postergadas e até mesmo ignoradas. Nem todos os programadores possuem o mesmo nível de apreço pelo código produzido. O respeito a cada uma das convenções é medido de forma qualitativa e não quantitativa. Não existe fornecimento de segurança apenas utilizando convenções.

Esta falta de segurança resulta em dividas técnicas para as bases de código. O sistema inteiro vira um espagueti, quanto mais o código é trabalhado, mais enrolado ele fica.

Assim como utilizamos equipamentos de segurança para garantir a integridade de algum objeto ou entidade, por que não asseguramos a integridade de nossas bases de código? Fábricas de software asseguram a integridade do ambiente de trabalho utilizando catracas, cancelas, guaritas, etc. Mas utilizam o quê para assegurar a integridade do seu produto (código)? Sistemas de controle de versão apenas garantem a versão atual do seu sistema caso uma cagada colossal aconteça em uma versão futura.

Dividas técnicas custam caro no fechamento das contas: quanto mais espagueti o código está, mais tempo e empenho serão gastos para novas funcionalidades e correções. Então por quê não previnimos isto de alguma forma? Como poderíamos prevenir?

Recentemente li o artigo Why Concatenative Programming Matters de Jon Purdy e notei a ligação direta entre o paradigma de programação concatenativa e o principio DRY. Pelo fato da programação concatenativa ser livre de contexto, é possível eliminar todo código duplicado com um simples find/replace. Sendo assim, este é o paradigma de programação ideal para que o principio DRY seja aplicado. É possível que o próprio compilador dê sugestões para eliminar ou obrigue a eliminação de repetições no código, garantindo um código melhor para todos.

Com a leitura do artigo de Jon Purdy, comecei a ponderar sobre as questões lançadas neste post e percebi que as type classes da linguagem Haskell se encaixam como uma solução brilhante para OCP. Elas permitem que contratos sejam definidos de forma aberta, aceitando extensões de forma fácil e com garantia em tempo de compilação (nada de monkey patching).

Se olharmos as type classes, podemos perceber que elas sempre abstraem um único tipo de dado e suas funções. Garantindo coesão de código e o cumprimento da convenção ISP, pois cada type class se restringe a um tipo de operação.

A linguagem Haskell possui inferencia de tipos, o que permite que o compilador produza assinaturas dos tipos mais abstratos possíveis, garantindo o cumprimento da DIP de forma automática.

Sobre a LSP, acredito que linguagens como Coq podem garantir o cumprimento desta convenção. Porém, não me aventurei muito sobre este tipo de linguagem ainda, então não posso garantir. Mas vale a pena dar uma verificada no assunto.

tl;dr Convenções podem ser checadas de forma estática:

  • DRY: Concatenative programming.
  • OCP & ISP: Haskell type classes.
  • DIP: Haskell type inference.
  • LSP: Coq.

29 de fevereiro de 2012

Levando o conhecimento de Haskell para Java

Resgatando o blog e trocando um pouco o tema para falar sobre programação.

Existem muitos tutoriais sobre orientação a objetos e desenvolvimento orientado por testes (TDD) pela internet. Grande parte se utiliza de um exemplo simples: uma calculadora.

Para desenvolver a calculadora, demonstram o poder do polimorfismo construindo abstrações sobre operações binárias e a utilidade do TDD através de uma programação incremental.

Neste post tentarei extender este exemplo de calculadora, porém focando em outro ponto do problema: a interação com o usuário.

Os exemplos estão na linguagem orientada a objetos mais utilizada do planeta: Java.

  • Programa: Calculadora para terminal.
  • Requisito: Ler cálculos no formato "2 + 2" e informar o usuário sobre o resultado do cálculo: "4".
  • Problema: Como testar a interação com o usuário?

Por ser um programa feito para rodar em terminal, utilizaremos System.in e System.out para interagir com o usuário. Porém, se amarrarmos o algoritmo de cálculo diretamente à estes recursos, ficará muito difícil e não-produtivo criar e manter testes para este sistema.

Algo importante que aprendi com a linguagem Haskell é a de separar o código em áreas puras e impuras. Uma área de código pura é um conjunto de funções que dependem apenas de seus argumentos e só produzem um resultado, i.e. funções que não alteram nenhuma informação e dependem apenas de seus argumentos. A área de código impura é aquela composta pelas demais funções que dependem de I/O, alterações na memória, banco de dados, etc.

A linguagem Haskell faz um trabalho incrível para assegurar que esta distinção seja mantida pelos programadores através do seu sistema de tipos que diferenciam funções puras e funções impuras. Nas linguagens tradicionais, como Java, não existe esta distinção: todo pedaço de código tem a liberdade de ser impuro. Desta forma, os programadores devem sempre prestar atenção para o que cada parte do código está executando.

Para separar a parte "pura" e "impura" da nossa calculadora, precisamos primeiro identificar quais funções pertencem a cada parte.

Toda a parte de código que realiza o cálculo pode se encaixar perfeitamente na área de código pura, afinal são apenas representações para funções matemáticas, que são puras por definição.

Por outro lado, a parte que faz a interação com o usuário é impura, pois altera informações que vão além de seu alcance em termos de código: imprime caracteres no terminal, e recebe informações que vão além de seus argumentos: teclas pressionadas pelo usuário.

A parte impura do código é muito difícil de ser testada e por isto deve ser mantida reduzida e de forma controlada, que faça apenas o necessário para o funcionamento. No caso da calculadora para terminal, a parte impura é apenas interação com o usuário no seguinte formato:

  1. Usuário digita um texto.
  2. Programa responde com outro texto.
  3. Volte para 1.

Esta interação é abstrata o suficiente para ser totalmente separada da parte que realiza o processamento. Por exemplo, o seguinte código encapsularia toda a parte impura da nossa calculadora:

public interface Programa {
  String processar(String entrada);
}

public class InteracaoTerminal {
  public void interagir(Programa programa) {
    Scanner s = new Scanner(System.in);
    while (true) {
      String entrada = s.nextLine();
      String saida = programa.processar(entrada);
      System.out.println(saida);
    }
  }
}

Desta forma a interface Programa é 100% testavel, por exemplo:

assertEquals("4", programa.processar("2 + 2"));
assertEquals("6", programa.processar("2 + 2 * 2"));

Além de testavel, a implementação da nossa calculadora apenas manipulará Strings, sem dependência direta com o System. Isto significa que poderemos aproveitar o código em outros lugares, quem sabe utilizar o mesmo código para duas interfaces diferentes: uma interage com o usuário através de um terminal e outra através de um aplicativo gráfico.

A abstração colocada como exemplo tem uma limitação: cada interação com o usuário é feita através de uma linha de entrada e uma linha de saída. Deixo como exercício aprimorar esta abstração para que seja possível ter mais de uma linha de entrada e mais de uma linha como saída de uma única interação. Se você conhece Haskell, poderá se basear na função interact, e se você não conhece: Aprender Haskell será um grande bem para você!