segunda-feira, 20 de julho de 2009

ICFP 2009 - a máquina virtual - parte II

Como prometido, vou explicar a segunda mônada existente no código da máquina virtual. Observem o código abaixo:

       dType op r1 r2 ip (st,mem) = let !result=(liftM2 op (!-! r1) (!-! r2)) mem in
(st,insert ip result mem)

Esta função implementa as instruções de dois operandos da máquina virtual. Essencialmente, essa função deve ler os dois valores da memória endereçados por r1 e r2, executar a operação e escrever o resultado na posição ip.

A parte de escrever na memória é, simplesmente, uma chamada a insert. Mas notem a declaração de result. A par de usar o bang-pattern (redundante, visto que insert já é estrito nos parâmetros), estou usando liftM2. Essa função possui como tipo:

liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r

ou seja: dada uma função de dois argumentos, liftM2 a transforma em uma função de duas mônadas, com comportamento equivalente. Vamos olhar rápidamente a declaração de (!-! r1), segundo parâmetro usado em liftM2.

(!-! r2) :: M.IntMap Double -> Double
Peraí, mas Data.IntMap não é uma mônada! O que liftM2 está fazendo então? Se olharmos rapidamente Control.Monad.Instances, encontraremos que existe uma instância de mônada definida para ((->) r), ou seja, funções que recebem parâmetro do tipo r e retornam alguma outra coisa!

Analisando então a função, vemos que liftM2 op (!-! r1) (!-!r2) é uma mônada contendo um Double, e essa mônada é uma função que recebe um Data.IntMap. Ou seja, o tipo de liftM2 op (!-! r1) (!-! r2) é Data.IntMap->Double! Não é lindo??

No próximo post, vou, finalmente, mostrar meu simulador de transferência de órbitas. Até lá!

sexta-feira, 17 de julho de 2009

ICFP 2009 - a máquina virtual - parte I

Finalmente chegamos a máquina virtual! Vou analizá-la passo a passo pois se trata do código mais monádico que fiz até agora. Na verdade, esse é o código mais modificado até o momento! Começamos como sempre importando os módulos necessários.

{-# LANGUAGE BangPatterns #-}
module OVM where

import Control.Arrow
import Control.Monad
import Control.Monad.RWS.Strict
import OBFProgram
import OBFData


Podemos imaginar a máquina virtual como algo que recebe uma entrada, escreve uma saída, guardando na memória as etapas intermediárias. Isso é, por definição, o que a mônada RWS faz. Uma mônada RWS é a composição de 3 mônadas

  1. Reader: definida como as funções que recebem um valor e retornam outro. Hã?! Sim, isso mesmo. O lance é que o parâmetro passado para a mônada na chamada de runReader é levado até o final, como uma espécie de "variável de ambiente". Essa variável pode ser lida a qualquer momento com a chamada a ask. Como em toda mônada, o desenvolvedor não precisa se preocupar com a passagem dessa variável: a passagem é toda através do operador (>>=)

  2. Writer: definida pelo par de um valor e um monóide. Monóides são objetos de uma categoria que implementa o vazio e a concatenação, algo como uma lista. Usando a chamada tell, executamos a concatenação do parâmetro a esse monóide. A passagem do monóide entre chamadas é, também, feita pelo operador (>>=).

  3. State: definida como as funções que recebem um valor e retornam um par, cujo segundo tipo é igual ao recebido. É como uma mônada Reader aonde, ao invés de apenas podemos consultar o ambiente, podemos alterá-lo. A consulta é feita pela chamada get, e a atualização com a chamada put. Nem preciso falar como o estado é levado de uma chamada a outra...



A mônada RWS faz tudo isso ao mesmo tempo. Para iniciar a execução da mônada, diversas funções, como runRWS, execRWS e evalRWS. Cada uma delas retorna uma parte diferente. Para nós, a versão interessante é a execRWS, que recebe a mônada RWS, a entrada e o estado inicial, e responde com a saída e o estado final. O valor da mônada, nesse caso específico, é sempre ().


-- Read Write State
-- Input Output Status+Memory
type OVM a=RWS OBFData OBFData (Bool,OBFData) a

execOVM::OVM ()->OBFData->OBFData->(OBFData,OBFData)
execOVM !program memory input=
let ((st,mem),out)=execRWS program input (False,memory) in
(mem,out)


Mas como construímos a mônada? No caso do problema do ICFP, como não temos jumps, é fácil: é só fazer um foldM sobre a lista de instruções retornada da leitura do arquivo:


toOVM::OBFProgram->OVM ()
toOVM=foldM (\() !inst->runInst inst) ()


Agora, o "problema" está em como tratar cada uma das operações. A mônada RWS possui uma função chamada modify, que recebe uma função responsável por modificar o estado. Então, tudo que temos que fazer é identificar a instrução e modificar o estado de forma apropriada. Há dois casos especiais: para Input, usamos diretamente a função ask e gravamos no estado com put, e para o Output, usamos o get e chamamos tell para escrever na saída.


runInst::(Int,OBFInst)->OVM()
runInst inst@(ip,i)=
case i of
Add r1 r2->modify (dType (+) r1 r2 ip)
Sub r1 r2->modify (dType (-) r1 r2 ip)
Mult r1 r2->modify (dType (*) r1 r2 ip)
Div r1 r2->modify (dType (//) r1 r2 ip)
Phi r1 r2->modify (dTypePhi r1 r2 ip)
Out r1 r2-> (dTypeOutput r1 r2)
Noop ->return ()
Cmpz LTZ r2->modify (sTypeCmpz (<0) r2)
Cmpz LEZ r2->modify (sTypeCmpz (<=0) r2)
Cmpz EQZ r2->modify (sTypeCmpz (==0) r2)
Cmpz GEZ r2->modify (sTypeCmpz (>=0) r2)
Cmpz GTZ r2->modify (sTypeCmpz (>0) r2)
Sqrt r2->modify (sType sqrt r2 ip)
Copy r2->modify (sType id r2 ip)
Inp r2-> (sTypeInput r2 ip)
where
(//) v1 v2 = if v2==0.0 then 0.0 else v1/v2
dType op r1 r2 ip (st,mem) = let !result=(liftM2 op (!-! r1) (!-! r2)) mem in
(st,insert ip result mem)
sType op r2 ip (st,mem) = let !result=(op . (!-! r2)) mem in
(st,insert ip result mem)
sTypeCmpz op r2 (st,mem) = let !result=(op . (!-! r2)) mem in
(result,mem)
dTypePhi r1 r2 ip (!st,mem)=let ix=(if st then r1 else r2) in
(st,(insert ip (mem!-!ix) mem))

sTypeInput r2 ip=do
!inp<-asks (!-!r2)
modify (second (insert ip inp))

dTypeOutput r1 r2=do
(!st,!mem)<-get
tell (singleton r1 (mem!-!r2))


Como falei antes, não me interessa como o operador (>>=) está implementado. O que me interessa é apenas o que é levado de uma função para outra por ele.

Como a explicação é um pouco extensa, no próximo post vou mostrar alguns detalhes adicionais de como uma das funções que modifica o estado também é monádica. Não percam!

quinta-feira, 16 de julho de 2009

ICFP2009 - estrutura de dados

Uma das partes mais importantes em um programa em linguagem funcional é a escolha da estrutura de dados. Isto, principalmente, pois acesso direto a memória fere a pureza da linguagem.

Para o ICFP2009, escolhi um IntMap como estrutura de dados. A escolha foi baseada no fato que a implementação do IntMap possui busca e inserção (que também funciona como modificação) em O(n), mas limitado por um fator constante O(32).

Se tivesse usado um Map comum, teria inserções e buscas em O(log n). Um array, mutável ou não, ofereceria inserção em O(n) e busca em O(1). Como temos 2 vezes mais buscas que inserções (a maior parte das instruções é binária), teriamos O(n+2), que é sempre pior que o O(3 log n) do Map, e muito pior que o O(32) do pior caso do IntMap.


{-# LANGUAGE BangPatterns #-}
module OBFData where

import qualified Data.IntMap as M


type OBFData=M.IntMap Double

singleton::Int->Double->OBFData
singleton=M.singleton

insert::Int->Double->OBFData->OBFData
insert !k !a !m=M.insert k a m

union::OBFData->OBFData->OBFData
union=M.union

fromList::[(Int,Double)]->OBFData
fromList=M.fromList

toList=M.toList

(!-!) :: M.IntMap Double -> Int -> Double
(!-!) = flip (M.findWithDefault 0.0)
infixl 9 !-!


Peço ao leitor que note algumas coisas:

  1. Estou forçando os tipos da estrutura de dados. Faço isso pois não tenho a necessidade de que essa estrutura de dados permaneça polimórfica. Se assim fosse, poderia usar IntMap diretamente.
  2. Uso bang patterns nos argumentos da chamada de insert. Faço isso para que não se acumulem thunks dentro do IntMap, o que seria péssimo para o desempenho
  3. Implementei um operador que retorna 0.0 caso acesse uma posição de memória não inicializada. Isto evita que eu tenha que criar o IntMap com as 16384 entradas preenchidas de cara.

Espero ter surpreendido, sim, pela simpliciade. Muito pior que fazer a estrutura, é a escolha de qual utilizar. A programação funcional força o programador a pensar no algoritmo mais eficiente, ao invés de pensar em hacks para tornar o código mais rápido.
Para quem quiser se aprofundar em estruturas de dados funcionais, sugiro dar uma lida no livro "Purely functional data structures" de Chris Okasaki, que desbrava as estruturas de dados neste universo imutável.

PS: Pensei também em amortizar o custo das inserções, mas acho que não é possível, pois todos os acessos de consulta são intercalados às buscas.

quarta-feira, 15 de julho de 2009

ICFP2009 - decodificando o programa

Linguagens funcionais são fantásticas quando sabemos aproveitá-las. Uma das coisas mais legais de se fazer em uma linguagem funcional é outra linguagem! Na tarefa do ICFP Contest 2009, uma das etapas é construir a VM para executar o binário fornecido.

Poderíamos decodificar as instruções apenas na hora de executá-las, mas em Haskell (ou qualquer linguagem funcional), é bem mais simples aplicar um map na lista de Word32 lida, convertendo-a em uma lista de dados do tipo instrução.

Começamos isso definindo o tipo:

module OBFProgram where

import Data.Word
import Data.Bits
import OBFData


type OBFProgram=[(Int,OBFInst)]

data OBFInst= Add !Int !Int |
Sub !Int !Int |
Mult !Int !Int |
Div !Int !Int |
Out !Int !Int |
Phi !Int !Int |
Noop |
Cmpz CmpzType !Int |
Sqrt !Int |
Copy !Int |
Inp !Int
deriving (Show,Eq)

data CmpzType= LTZ |
LEZ |
EQZ |
GEZ |
GTZ
deriving(Show, Enum,Eq)

Haskell é uma linguagem de avaliação tardia, mas nem sempre isso é bom. O map utilizado em decode só vai ser executado quando pegarmos o primeiro item da nova lista. Mas se cada elemento dentro do map também for tardio, significa que iremos ler o arquivo também nessa primeira execução, o que pode tornar tudo muito lento. Outro problema é que, a medida que vamos "acumulando" execuções atrasadas (thunks), elas vão se juntando em memória, criando um enorme bloco. Para reduzir isso, coloquei os ! antes de cada elemento dentro da declaração do tipo. Esse ! (também conhecido como bang) identifica um placeholder onde o dado só pode entrar depois de computado. Desta forma, quando crio, por exemplo, Add x y, a execução dos thunks que geram x e y vai ser forçada, e o elemento irá guardar efetivamente um inteiro em cada uma das posições.

decode::[Word32]-> OBFProgram
decode x=filter ((/=Noop).snd) (zip [0..] (map decodeInstruction x))

O restante do código é bastante básico. Mastigamos os bits de cada Word32 e, utilizando case, convertemos cada elemento da lista em uma instrução.

decodeInstruction::Word32->OBFInst
decodeInstruction x=
case opcode of
0 -> decodeSType par1 par2
1 -> Add par1 par2
2 -> Sub par1 par2
3 -> Mult par1 par2
4 -> Div par1 par2
5 -> Out par1 par2
6 -> Phi par1 par2
where
opcode=fromIntegral( (x `shiftR` 28) .&. 15 )
par1 =fromIntegral( (x `shiftR` 14) .&. 16383 )
par2 =fromIntegral( x .&. 16383 )

decodeSType::Int->Int->OBFInst
decodeSType par1 par2=
case opcode of
0->Noop
1->Cmpz (toEnum imm) par2
2->Sqrt par2
3->Copy par2
4->Inp par2
where
opcode = (par1 `shiftR` 10).&.15
imm = (par1 `shiftR` 7).&. 7

No próximo post, vou apresentar a minha versão da representação dos dados. Essa sim, vai surpreender.

terça-feira, 14 de julho de 2009

ICFP2009 - lendo o arquivo

Essa é a primeira parte da tarefa do ICFP2009: ler o arquivo. Nada demais, uma vez que você conheça a Data.Binary e a Data.Binary.IEEE754! Vou percorrer um pouco desse código.

Inicialmente, declaramos o módulo e importamos as libraries:

module OBFFile where

import qualified Data.ByteString.Lazy as BL
import Control.Arrow
import Data.Binary.Get
import Data.Binary.IEEE754
import System.IO
import Data.Word
import OBFProgram
import OBFData
import OVM


A função principal é dividida em duas partes: primeiro, lemos o conteúdo inteiro em um ByteString e o passamos para a segunda parte. Na segunda parte, abusando da notação point-free, lemos todos os frames do arquivo, usando uma mônada Get do pacote Data.Binary. Em seguida, convertemos a lista de tuplas em uma tuplas de listas. Com a primeira lista, decodificamos as instruções do programa e convertemos em uma mônada OVM, que descreverei mais tarde. A segunda lista é convertida em um IntMap, e corresponde a inicialização da memória. O return está aí somente para empacotar o resultado em uma mônada IO.


readOBFFile::Handle->IO (OVM(),OBFData)
readOBFFile h=BL.hGetContents h >>= readOBFFile'

readOBFFile':: BL.ByteString->IO (OVM(),OBFData)
readOBFFile'=return.(toOBFProgram *** toOBFData). unzip . runGet getFrames
where
toOBFData=fromList .(filter ((/=0.0).snd)). (zip [0..])
toOBFProgram=toOVM.decode


Finalmente a leitura propriamente dita funciona como um fold em duas etapas. Se a entrada não está vazia, lemos o frame par, que tem o formato (memória, instrução) e chamamos a função do frame ímpar, com o formato invertido. A cada operação, concatenamos o resultado na cabeça de uma lista acumuladora. Finalmente, quando a entrada está vazia, retornamos a lista acumuladora revertida, nos valendo da amortização da operação.


getFrames::Get [(Word32,Double)]
getFrames=getEvenFrames []

getEvenFrames::[(Word32,Double)]->Get [(Word32,Double)]
getEvenFrames acc=
do
b<-isEmpty
if b then return (reverse acc)
else do
d<-getFloat64le
i<-getWord32le
getOddFrames ((i,d):acc)


getOddFrames::[(Word32,Double)]->Get [(Word32,Double)]
getOddFrames acc=
do
b<-isEmpty
if b then return (reverse acc)
else do
i<-getWord32le
d<-getFloat64le
getEvenFrames ((i,d):acc)


Se não fossem os dos e eu ter citado, o leitor provavelmente não notaria o uso da mônada Get, e imaginaria que Get é uma composição de funções. O segredo está na definição do Get:


newtype Get a = Get { unGet :: S -> (a, S) }

Na verdade, a poderosa mônada Get não passa de uma função que leva um estado a uma saída e outro estado. A função runGet chama unGet (a implementação do Get) com a inicialização do estado, obtida a partir do Lazy ByteString que é passado como parametro.

Quando combinamos mônadas, usando os getWord32le e getFloat64le, estamos gerando uma composição de função aonde não precisamos nos importar em costurar o estado de uma chamada para outra. Toda essa composição é feita na implementação do operador (>>=) e se torna irrelevante para o "usuário" da mônada.

Mas o leitor pode perguntar: "Legal, mas aonde esse operador foi usado?? Não o vejo em lugar nenhum, depois de readOBFFile". Fácil! Nesse ponto entra o maior syntatic sugar do Haskell, destinado a transfomar as mônadas em warm, fuzzy things: a notação do! Podemos subentender cada linha como separada por um >>= e cada "retorno" como uma definição lambda. Assim, i<-getWord32le poderia ser escrito "getWord32le >>= \i->" (em pseudo-Haskell).

Foi por isso que falei que as mônadas não são coisa de outro mundo! Continuarei dissecando meu código nos próximos posts!

terça-feira, 7 de julho de 2009

Tutoriais sobre mônadas

Pensei bem no último post e não quero construir mais um tutorial de mônadas. Acho que não consigo atingir a mesma profundidade, mantendo a mesma simplicidade apresentada nos dois tutoriais abaixo:

  • The Haskell Programmer’s Guide to the IO Monad - Don't Panic - Um tutorial bastante teórico, ligando a teoria das categorias a linguagem Haskell. Apesar de toda a matemática hardcore, é interessante para aprender que as mônadas não são um mecanismo de computação ou de sequenciamento, e sim que esses mecanismos podem ser emulados por uma mônada. Vale a pena também olhar o que a Wikipedia tem a dizer.
  • Monads for functional programming - Este artigo de Philip Wadler é exatamente o oposto do anterior: trata as mônadas apenas nos seus aspectos relacionados a implementação dos efeitos colaterais da linguagem, sem se preocupar com as questões matemático-filosóficas da teoria das categorias.

Os piores exemplos de mônadas são os tipos Maybe e as listas. Esses tipos, apesar de poderem ser monadicos, não demonstram o poderio dessa abstração. Wadler apresenta exemplos muito mais úteis, baseados em funções monadicas (Reader e State) e em monóides (Writer e Error). Vale a pena dar uma olhada, pois é exatamente isto que estou usando no código do concurso do ICFP 2009.

sexta-feira, 3 de julho de 2009

Haskell, as mônadas e o ICFP

Mônadas (monads em inglês) são o ponto alto da programação funcional. Em Haskell, uma linguagem que se proclama puramente funcional, elas são a saída honrosa para os efeitos colaterais inexoráveis, também conhecidos como E/S.

Segundo Simon Peyton-Jones, um dos pais do Haskell, um programa puramente funcional é como uma caixa fechada. Não temos como saber se ela está funcionando, pois nem esquenta. O E/S é fundamental, mas quebra o conceito da pureza, por alterar "todo o universo" cada vez que ocorre. Para isolar os efeitos colaterais do corpo da linguagem, os criadores do Haskell utilizaram o conceito das mônadas. O grande problema surge então quando vamos tentar entendê-las: mônadas são entes matemáticos oriundos da teoria das categorias, um ramo tresloucado da álgebra abstrata. É uma piada recorrente dizer que o rito de iniciação do neófito em Haskell é escrever um tutorial sobre mônadas!

Após ler cerca de uma dúzia de tutoriais, que incluem desde o mais mão-na-massa a um tutorial sobre teoria das categorias, não consegui, de forma alguma, entender como essas mônadas poderiam me ajudar em alguma coisa. Para piorar, por ser uma linguagem com avaliação tardia, toda ação que exigia sequência se tornava tediosamente complexa. No concurso do ICFP 2009, finalmente entendi uma frase famosa de Simon Peyton Jones: "O grande erro foi usarmos o nome mônadas. Deveríamos ter chamado de 'coisas fofinhas' (warm, fuzzy things, no original)".

Na verdade, toda a teoria das categorias serve apenas para explicar por que as mônadas funcionam. O programador que vai criar uma mônada precisa de um conhecimento mínimo sobre elas, e o programador que vai usar precisa saber apenas como as funções expostas para a mônada interagem com ela, ignorando o funcionamento interno. Com este ponto de vista, o mais importante é entender o funcionamento do operador (>>=), que, inclusive, é a logomarca atual do Haskell.

Nas próximas postagens, vou colocar exemplos retirados do código que estou escrevendo para solução do problema do ICFP 2009, procurando demonstrar esta minha tese.

Alias, talvez até possamos considerar isto um tutorial de mônadas. Aí, quem sabe, deixo de ser um neófito!

quinta-feira, 2 de julho de 2009

ICFP2009 Contest

Mais um ICFP, mais uma tentativa, mais uma vez em Haskell... Só que desta vez não foi uma tentativa tão frustrada quanto a do ano passado! Diversos motivos me levam a crer isso:

  1. A linguagem Haskell deixou de ser uma barreira: as mônadas não são mais tão complexas para mim. Começo a entender por que Simon Peyton-Jones considera o nome warm, fuzzy thing mais apropriado
  2. Apesar de mais complexa (ninguém discorda que mecânica orbital é difícil) , os arquivos de entradas eram mais tratáveis, e não envolviam conexões com rede, comunicação entre processos, e outras coisas que nem são tão funcionais assim
  3. Tá certo que apanhei muito na elaboração da máquina virtual, mas muito mais por não consultar o HackageDB do que por não saber a linguagem. A quantidade de bibliotecas lá é consideravelmente grande, cobrindo diversas áreas de conhecimento
Não concluí por falta de tempo, e por ter tropeçado em algumas bobagens. Acho que a pior delas foi ter me atrapalhado na leitura do arquivo usando a biblioteca Data.Binary, pois não percebi que ela tinha algumas funções especializadas nos tipos nativos do Haskell e outras destinadas a leitura de tipos genéricos como o word32le (inteiro sem sinal de 32 bits em little-endian). Pra completar, depois que descobri essas funções acabei escrevendo uma função que lia um word64le e o tratava como número de ponto flutuante IEEE-754. Só que o tratamento de números de ponto flutuante estava em outra biblioteca, a Data.Binary.IEEE754, que só descobri na manhã de segunda-feira. Com todos os tropeços, só consegui concluir a máquina virtual na noite de quarta-feira, dois dias depois do prazo.

Pelo lado positivo, eu concluí a máquina virtual! Além disso, usei a mônada RWS sem grandes dificuldades, e meu código não tem space leak pois consegui que todas as rotinas iterativas fossem tail-recursive.

Semana que vem devo começar a tentar resolver os problemas. Coloquei como meta terminar as tarefas do concurso até o final deste ano, e sinto que vou conseguir bem antes disso.

Postagens populares