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!

Nenhum comentário:

Postagens populares