terça-feira, 17 de novembro de 2009

Camel case stripper

Estava conversando com o Chico e ele me falou da implementação do camel case stripper que ele fez em Smalltalk.

Enquanto ele me explicava o algoritmo, pensei em como seria simples uma versão funcional e acabei escrevendo este código.


isUpper = (flip elem) ['A'..'Z']

stripCamel (x:xs)= stripCamel' xs [x] []

stripCamel' [] [] b = reverse b
stripCamel' [] a@(x:xs) b = stripCamel' [] [] ((reverse a):b)
stripCamel' (x:xs) a b | isUpper x = stripCamel' xs [x] ((reverse a):b)
| otherwise = stripCamel' xs (x:a) b


Sei lá... Parece mais simples! :-)

terça-feira, 10 de novembro de 2009

IFCP 2009 - O final

Desculpe desapontá-los, mas abandonei o projeto de terminar o problema do ICFP2009 antes do final do ano. Na verdade, fiquei um pouco aborrecido pois queria ter implementado um visualizador das órbitas, e não estou com tempo de aprender OpenGL.

Coloco aqui a última versão do código de transferência entre órbitas. O algoritmo é bastante simples: uma outra mônada RWS que envolve o IO, apenas para escrever a saída na tela. Ainda não critico o final da execução e nem escrevo o arquivo de saída no formato do problema, mas dá para se divertir vendo a distância entre o satélite e a órbita destino diminuindo!! Aproveitem!


module Main where

import System.IO
import System.Environment
import Control.Monad.RWS
import qualified Data.ByteString.Lazy as BL
import OBFFile
import Vector
import OBFProgram
import OBFData
import OVM

-- Read Write State
-- Program Time,Input Time,VMInput,Memory
type SimVM a=RWST (OVM()) [(Integer,OBFData)] (Integer,OBFData,OBFData) IO a


main::IO ()
main=do
(fn:scene:args)<-getArgs
withBinaryFile fn ReadMode (readAndRun (read scene))


readAndRun::Double->Handle->IO ()
readAndRun s h=
do
(p,d)<-readOBFFile h
let i=singleton 0x3e80 s
dum<-case s of
s | s>=1000 && s<2000 ->print "Hohmann"
s | s>=2000 && s<3000 ->print "Meet and Greet"
s | s>=3000 && s<4000 ->print "Eccentric Meet and Greet"
s | s>=4000 && s<5000 ->print "Operation Clear Skies"
s | s>=5000 && s<6000 ->print "Operation Dance with Stars"
ret<-execSim hohmannSim p i d
print ret

execSim::SimVM()->OVM()->OBFData->OBFData->IO [(Integer,OBFData)]
execSim s p i d=liftM snd $ execRWST s p (0,i,d)

hohmannSim::SimVM ()
hohmannSim=
do
i<-gets (input)
(co ,v, tgt )<-getPositionSpeedTarget
let (dv1,dv2,tof_d)=calcHohmann co tgt
let tof=floor tof_d ::Int

liftIO $ print $ "targetOrbit="++show(tgt)
liftIO $ print $ show(tgt>co)
liftIO $ print $ "currentSpeed="++show(v)
liftIO $ print $ "dV1="++show(dv1)
liftIO $ print $ "dV2="++show(dv2)
liftIO $ print $ "tof_d="++show(tof_d)
liftIO $ print $ "tof="++show(tof)
let (dx1,dy1)=colinearVector dv1 v
liftIO $ print $ "deltaVector="++show(dx1,dy1)
let i'=i `union` (fromList [(2,dx1),(3,dy1)])
applyInput i'
(_,_)<-stepOVM
applyInput i
replicateM_ (tof-4) stepOVM
(co ,v, tgt )<-getPositionSpeedTarget
let (dx2,dy2)=colinearVector dv2 v
let i'=i `union` (fromList [(2,dx2),(3,dy2)])
applyInput i'
(_,_)<-stepOVM
applyInput i
replicateM_ (1000) stepOVM
return ()
where
input (t,i,d)=i
time (t,i,d)=t
memory(t,i,d)=d


getPositionSpeedTarget::SimVM (Double, Vector Double,Double)
getPositionSpeedTarget=do
(t ,o )<-stepOVM
(t ,o')<-stepOVM
return (currOrbit o', currSpeed o o', o'!-!4)


stepOVM::SimVM (Integer,OBFData)
stepOVM=do
p<-ask
(t,i,d)<-get
let (d',o)=execOVM p d i
put ((t+1),i,d')
let co=currOrbit o
let tgto=o!-!4
liftIO $ print $ "-------------- At time "++show (t+1)++" --------------"
liftIO $ print $ "Score: "++show(o!-!0)
liftIO $ print $ "Fuel: "++show(o!-!1)
liftIO $ print $ "Position: "++show(myPosition o)
liftIO $ print $ "Current Orbit: "++show(co)
liftIO $ print $ "Target Orbit: "++show(tgto)
liftIO $ print $ "Distance to go: "++show(tgto-co)
return ((t+1),o)

applyInput::OBFData->SimVM()
applyInput=modify.changeInput
where
changeInput i (t,_,d)=(t,i,d)

myPosition::OBFData->Vector Double
myPosition = liftM2 (,) (!-!2) (!-!3)

currOrbit::OBFData->Double
currOrbit=magnitude.myPosition

currSpeed::OBFData->OBFData->Vector Double
currSpeed a b=diff (myPosition a) (myPosition b)

{- Helpful constants -}
earthMu= constG * earthM
constG = 6.67428e-11 ::Double
earthM = 6.00000e24 ::Double
earthR = 6.357e6 ::Double




{- returns the delta-vs and time of flight of a hohmann transfer
between two circular orbits. -}

calcHohmann::Double->Double->(Double,Double,Double)
calcHohmann r1 r2=(dv1,dv2,tof)
where
dv1=(f r1)*((g r2)-1)
dv2=(f r2)*(1-(g r1))
tof=pi*sqrt((a^3)/earthMu)
a=(r1+r2)/2
f x=sqrt (earthMu/x)
g x=sqrt (x/a)





PS: Vector é um type synonim para (Int,Int)!

domingo, 16 de agosto de 2009

Um cruzeiro ao som de Roberto Carlos

Pois é pessoal! Ainda estou devendo a parte final do meu programa do ICFP2009. O programa ainda está muito mal estruturado, e enquanto não o arrumar, não pretendo colocar aqui. Além disso, comecei a brincar com o OpenGL em Haskell, pois quero visualizar as órbitas traçadas.

Mudando de assunto, semana que vem é meu aniversário de casamento, e como diria o Roberto, "São tantas emoções". Estava passeando no Shopping Avenida Central com um colega, quando me deparei com o cartaz ao lado. Imediatamente tive a idéia de fotografá-lo e convidar a Paty para comemorar o nosso aniversário de casamento em um cruzeiro ao som de Roberto Carlos. Após alguma desconfiança ("você? Roberto Carlos?") e questionamentos ("mas esse cruzeiro é uma nota..."), mostrei para ela o cartaz de Carlos Evanney, o cover oficial do Rei, que fará o seu terceiro cruzeiro pela Baía de Guanabara. Claro que a Paty caiu na risada, e achou uma excelente idéia (para não dizer o contrário)!

O cartaz informa que o cruzeiro tem duração de 6 horas, saindo da Marina da Glória, passando por Niterói, Ilha Fiscal, Urca, Botafogo e Flamengo. Durante o passeio serão servidos cerveja, refrigerante, água mineral, pizza, salgadinhos e frutas. E tem diversão para todo mundo, pois o videokê está liberado!

Agora, imagine você, leitor, fazendo aquele cruzeiro, em uma lanchinha, pela Baía de Guanabara com seu aroma típico, comendo uma coxinha de galinha e tomando um Baré-cola ou um Paquera, tudo ao som de um cover do Roberto Carlos. Além disso, quando a música parar, poder fazer aquele dueto com sua amada no karaokê. Pode ser mais romântico?

sábado, 1 de agosto de 2009

O funk e a liberdade de expressão

Em 13 de julho de 2009 a Revista Época publicou uma reportagem onde criticava a truculência da PM que, ao coibir bailes funk irregulares em algumas favelas cariocas, acabava por cercear a liberdade de expressão dos moradores, ao proibir qualquer tipo de funk em qualquer tipo de evento.

A PM se vale da Lei Estadual 5265/2008 que exige, para a realização de bailes funk, uma série de requisitos, como banheiros, câmeras de vigilância, controle de entrada de menores, e, principalmente, autorização do Batalhão de Polícia Militar responsável pela área aonde o baile se realizará. Nem preciso comentar aqui que quase nenhum baile se adequa, se adequou, ou se adequará a essa Lei.

Escrevi, na noite de 3 de julho, uma carta aonde expunha minha indignação com o baile funk que não me deixava dormir. Versões dessa carta foram enviadas ao jornal O Globo, a editoria do programa Profissão Repórter e, finalmente, para a Revista Época. Esta última, demonstrando o seu caráter democrático, publicou-a na edição do dia 27 de Julho, mas por razões editoriais a resumiu, talvez até em demasia.

Valendo-me da minha garantia constitucional de liberdade de expressão, reproduzo abaixo, na íntegra, a carta enviada a Revista Época.



"Prezados repórteres,


Lendo a revista Época desta semana, me deparei com a reportagem "Um 'créu' no funk" aonde o jornalista Nelito Fernandes questiona até que ponto a Lei Estadual 5265 é uma ameaça a liberdade de expressão. Desta forma sinto-me compelido a expor a minha visão de morador da Tijuca no Rio de Janeiro.

A cada sexta-feira, sinto que Tim Lopes morreu em vão, em sua tentativa de mostrar a ligação dos bailes funk com a prostituição e exploração sexual de menores!

Na sexta, dia 3 de julho, a noite, após uma semana exaustiva no trabalho, desligamos o despertador e nos deitamos mais cedo. O que seria, para alguns, a receita perfeita para começar o final de semana, para nós representou o início de uma noite de tortura, que vem se repetindo semana após semana. Por volta de 1:45 e eu e minha esposa fomos acordados abruptamente, como toda a sexta-feira nas últimas semanas, por um baile funk no morro do Salgueiro, com uma música tão alta que parecia haver um rádio ligado dentro de nossa casa.

O baile funk no morro do Salgueiro, conhecido como o Caldeirão, começa toda a sexta, por volta de meia-noite, e vai até as cinco horas da manhã. Tudo ao som de uma música violentamente alta, ouvida perfeitamente a distância pelos moradores da Tijuca. Música que proclama o tráfico, e, principalmente, a pedofilia e a violência sexual. Em uma das músicas tocadas nesta madrugada, o DJ, que se identificava como Adriano, da equipe Pitbull, "declamava em versos" o que gostava de fazer (sexualmente) com "a novinha de 15 anos".

O baile do Salgueiro é objeto de diversas comunidades da rede de relacionamentos Orkut. Não fica difícil identificar menores adolescentes que consultam horários e rotas para chegar ao morro, e que contam suas experiências.

Moro em uma região em que há três hospitais e fico imaginando como deve ser estressante para os pacientes destas instituições. Imagino que mais estressante ainda é a vida do morador do morro, trabalhador, e que pega cedo no batente na manhã de sábado. Não acredito que todos no morro compactuem com esse baile, e nem que seja a minoria.

A cada sexta-feira o baile começa mais tarde, com um som mais alto, e com letras de mais baixo calão, que colocam a mulher como prostituta e nós, cidadãos de bem, como otários. Como começa mais tarde, acaba mais tarde, mas nunca antes das 5:00 da manhã.

Já tentei Polícia e Disque-denúncia. Os primeiros me informaram que sem um endereço completo, não há como deslocar a viatura para averiguação. O segundo, que foi aberta uma denúncia e que esta vai ser investigada. Concreto mesmo só os tampões de ouvido que eu e minha esposa compramos, mas cuja eficiência, quando posta a prova, mostrou-se muito baixa.

O síndico do prédio, em contato com uma das associações de moradores da Tijuca, descobriu uma denúncia feita ao Ministério Público e prontamente aderiu a lista de denunciantes. Nada ocorreu!

Face a estes bailes, penso que, como tantas outras leis, a Lei Estadual 5265 demonstrou-se apenas mais um texto bonito tramitado em nossas Assembléias. Nem a Polícia e nem qualquer outro orgão público Estadual age para cumprí-la, seja por falta de pessoal, ineficiência ou pura burocracia.

As 2:50h da referida sexta-feira, o DJ avisava: "Desentoca aí galera! O baile está só começando, com muita putaria e orgia!". Durma-se com esse barulho!

Na sexta-feira passada, dia 10 de julho, o baile funk teve um nível sonoro aceitável, percebido ao longe apenas com as janela bem abertas. Acredito que a mudança de comportamento tenha sido oriunda da presença da Polícia Militar no morro, após o assassinato do cabo Ênio Santiago, do BOpE. Isto prova que o nível sonoro dos bailes só é alto como forma de provocação e intimidação por parte do tráfico que o organiza.

De forma alguma quero discriminar pessoas que gostam, fazem ou frequentam bailes funk, mas é importante que tudo isto seja feito dentro dos limites legais, com respeito ao próximo.


Atenciosamente,


Rafael Gustavo da Cunha Pereira Pinto"


De um ano para cá, dormir na sexta-feira vinha sendo apenas um sonho, enquanto a realidade se mostrava através do baile funk aqui perto de casa. Infelizmente, a vida de um cabo da PM (mais especificamente do BOpE) precisou ser ceifada para que minhas noites de sono voltassem. Há três semanas o baile funk ocorre em níveis sonoros aceitáveis, e me questiono constantemente da correlação entre os fatos.

De qualquer forma, reafirmo: não sou contra o funk. Cada um ouve o que gosta! Entretanto, o direito a liberdade de expressão acaba exatamente onde o dever de respeitar às leis e ao próximo começa.

Há um Projeto de Lei tramitando na Assembléia Legislativa do Rio de Janeiro, que pretende anular os efeitos da Lei Estadual 5265, e transformar o funk carioca em patrimônio cultural.

Para mim, tanto faz, pois não pretendo organizar bailes de qualquer espécie, mas gostaria muito que meu direito de dormir sossegado (garantido pela Lei do Silêncio, Lei Estadual 126/1977) fosse garantido, independente da música, da localidade.

Afinal, nem todo funk é criminoso e ruim: vide a letra de "Eu fico assim sem você", de Claudinho e Bochecha, regravado por Adriana Calcanhoto.

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!

Postagens populares