Jump to content
Ferreirinha.pt

BrainFuck / Haskell

Recommended Posts

Ferreirinha.pt

Olá...

Sou estudante de Ciências da Computação e foi-me proposto fazer um trabalho em Haskell à cerca de BrainFuck. O enunciado é o seguinte:

"Um programa BF pode ser representado em Haskell simplesmente usando uma String. Embora essa representac~ao seja a ideal para programar, n~ao e muito util para executar programas, pois n~ao ca claro qual o alinhamento entre um comando [ e o correspondente ]. Uma alternativa mais util passa por considerar que estes dois comandos em conjunto denotam um unico comando de ciclo parametrizado pelo programa entre eles. Sendo assim, podemos representar todos os programas BF sintaticamente correctos pelo seguinte tipo de dados:

data BF = BF [bFCommand]

data BFCommand = IncPtr | DecPtr | IncVal | DecVal | Read | Print | While BF

Por exemplo, o programa ,[.-] seria representado por

BF [Read, While (BF [Print, DecVal])]

Tarefa 1 (8 valores) A primeira tarefa deste projecto consiste, precisamente, em implementar conversores entre estas duas representac~oes. Mais concretamente pretende-se uma uma implementac~ao das classes Show e Read para o tipo BF, por forma a ser possvel fazer pretty-printing e parsing de programas. Por exemplo,

show (BF [Read, While (BF [Print, DecVal])]) == ",[.-]"

read ",[.-]" == BF [Read, While (BF [Print, DecVal])]

Obviamente a func~ao read deve falhar quando o programa tem erros sintaticos. Opcionalmente, para facilitar a compreens~ao dos programas, estas func~oes podem introduzir ou ignorar espacos  (incluindo tabs e newlines).

Tarefa 2 (6 valores) A segunda tarefa consiste em desenvolver um interpretador de BF, que execute os respectivos programas de acordo com o signicado assima descrito. Mais concretamente, pretende-se uma func~ao com a seguinte assinatura.

run :: BF -> IO ()

Com esta func~ao poderemos executar os programas acima descritos. Por exemplo:

> run (read ",[.-]")

5

5

4

3

2

1

O tipo IO () no resultado representa o facto de esta func~ao realizar operac~oes de input e output. Este tipo sera leccionado no nal do semestre, pelo que esta tarefa deve ser realizada em ultimo lugar.

Tarefa 3 (6 valores) Como ja deve ter reparado, programar em BF n~ao e muito agradavel. Para remediar esta situac~ao vamos desenvolver nesta tarefa uma linguagem imperativa um pouco mais amigavel. Nesta linguagem, que vamos designar por PL - Programming Language, vamos usar variaveis para indexar explicitamente celulas de memoria. Tal como em BF, os programas s~ao sequ^encias de comandos (separados por ;), havendo apenas tr^es comandos:

Comando Signicado

print x Imprime no ecran o conteudo da celula indexada por x.

read x L^e do teclado um inteiro e armazena-o na celula indexada por x.

x := e Calcula o valor da express~ao aritmetica e e armazena o resultado

na celula indexada por x.

As express~oes aritmeticas podem ser constantes inteiras, conteudos de celulas indexados por variaveis, ou operac~oes aritmeticas aplicadas a outras express~oes. Por exemplo, o seguinte programa PL l^e um inteiro do teclado para a celula indexada por x, armazena o resultado de calcular (x+x)+1 na celula indexada por y e imprime o valor desta celula.

read x; y := (x+x)+1; print y

Um programa PL pode ser representado em Haskell usando os seguintes tipos de dados:

data Expr = Const Int

| Var String

| Plus Expr Expr

data PL = PL [PLCommand]

data PLCommand = Input String

| Output String

| Atrib String Expr

Por exemplo, o programa apresentado acima pode ser representado da seguinte forma:

PL [input "x"; Atrib "y" (Plus (Plus (Var "x") (Var "x")) (Const 1)); Output "y"]

Em vez de implementar uma func~ao para executar programas PL, pretende-se reutilizar a

func~ao run denina anteriormente. Para tal ter~ao que desenvolver um compilador de PL para BF,

ou seja implementar a seguinte func~ao que traduz um programa PL num programa BF equivalente.

compile :: PL -> BF"

Share this post


Link to post
Share on other sites
Baderous
2.4) Não é permitido a criação de tópicos a pedir para que se façam trabalhos. Pedir ajuda é diferente de pedir trabalhos feitos. Tópicos com este tipo de conteúdos estão sujeitos a serem bloqueados e o autor do mesmo avisado por mensagem privada.

Regras do FÓRUM

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.