HiveBrain v1.2.0
Get Started
← Back to all entries
patternCritical

Charmander Brainfuck interpreter in Haskell

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
interpretercodereviewstackoverflowbeginnerhaskellbrainfuck
brainfuckinterpreterhaskellcharmander

Problem

I just started learning Haskell and this is my first big project (ie not factorials, fibonacci or graphers). This is kind of a gift for somebody so the language is a bit different. The program works, but I felt that some parts of the code could be improved, specifically:

  • Is Vector the best choice for representing current memory state in the program state record, Program?



  • I executed the program by splitting the source code into a list of words (the code state), then recursively going through the list and parseing it on each loop. Is there a better way to do it? Tokenization maybe?



  • I created loops by putting the current code state into a stack named loopback, and using this to "go back in time" when needed. Is there a better way to do it?



  • I just felt the way I handled loops are inelegant; such as toChaCharmanderChar'.



  • Did I use guards and pattern matching correctly?



  • Is it confusing in general?



I consider myself a beginner-intermediate programmer, having just learnt monads.

Documentation

Char: Previous 1
Char-char: Next 1
Cha: Input
Charmander: Output
Cha-cha: Minus 1
Charmander-charmander: Plus 1
Charmander-char: Loop start; if data at DP is 0, jump to corresponding Cha-charmander-char.
Cha-charmander-char: Loop end; if data at DP is not 0, jump to corresponding Charmander-char.

DP: Data Pointer, starts at 0. Points to an integer in memory.
Memory: A tape of 128 integers.


Main.hs

```
module Main
(
main
) where

import Data.Vector (Vector, replicate, (//), (!), accum)
import Data.Char (ord, chr, toLower)
import System.Environment (getArgs)
import System.IO (IOMode(ReadMode), BufferMode(NoBuffering), openFile, hGetContents, hSetBuffering, stdin)

-- Program state

type DP = Integer
type Memory = Vector Integer
type Code = [String]

data Program = Program {
dp :: DP,
memory :: Memory,
code :: Code,
loopback :: [Code]
} deriving Show

initial :: Code -> Program
initial code = Program {
dp = 0,
memory = Da

Solution

Congratulations on your first large project. I'm not sure whether this review has grown a little bit overboard, as it is now both a review as well as a mini tutorial. Either way:

What the char?

Charmander-char Char cha Charmander Char. Char? Charmander!



  • Is it confusing in general?




Char! I mean, yes. Mostly due to the names of your functions. As you already acknowledged, Charmander is essentially Brainfuck. Therefore, it has some simple operations, +, -, >,  (*) again

First of all, you should rename your programs. While it's "just" a gift to someone, you still want to know what your program actually meant, later:

-- instead of char
previousCell :: Program -> IO Program
previousCell = return $ move (-1) Program

-- instead of charChar
nextCell :: Program -> IO Program
nextCell = return $ move 1 Program


Remember, you are the person most likely to read the code again, so you want to grasp what's going on quickly. Now parse only changes slightly:

parse :: String -> Program -> IO Program
parse "char"                  = previousCell
parse "char-char"             = nextCell
parse "cha"                   = getCell
parse "charmander"            = putCell
parse "cha-cha"               = decreaseCell
parse "charmander-charmander" = increaseCell
parse "charmander-char"       = startLoop
parse "cha-charmander-char"   = endLoop
parse _                       = unknown


A nice side effect: if you lose your original documentation of Charmander, you can still look it up here.

However, this is clunky. We have to interpret and parse the program over and over again. Which brings us to your other questions:



  • I executed the program by splitting the source code into a list of words (the code state), then recursively going through the list and parseing it on each loop. Is there a better way to do it? Tokenization maybe?



  • I just felt the way I handled loops are inelegant; such as toChaCharmanderChar'.




Here is were we start the real journey.

Proper types (aka use an AST)

Let us review your types:

type Code = [String]

data Program = Program {
    dp :: DP,
    memory :: Memory,
    code :: Code,
    loopback :: [Code]
} deriving Show


The name Code is true: you're "just" saving a list of words. However, when you work with a programming language, you don't want to work with the original code too long (unless it contains parser errors). Instead, you want to work with something that describes your program in terms of instructions, or syntax (an abstract syntax tree, AST, if you want to look for more information).

Let's think of instructions for your program:

data CharmanderInstruction 
     = IncreaseCell
     | DecreaseCell
     | MoveRight
     | MoveLeft
     | PutChar
     | GetChar
     | Loop [CharmanderInstruction]
     deriving Show


That contains all actions we can do in Charmander: we can increase/decrease the cell, move left or right, put a character or get one, and we can loop. Note that there isn't a StartLoop and EndLoop. Either we've got a correct loop, or we don't.

Now, your Code can be thought of [CharmanderInstruction]:

type Code = [CharmanderInstruction]


Separation of concerns

This method gives us an easier separation of concerns. If we split the responsibility of our functions, it will also be easier to reason about their behaviour.

Pretty printing

The nice part about this is that you can now print the program as you like. Maybe you want to read a rather verbose version:

pretty :: (CharmanderInstruction -> String) -> [CharmanderInstruction] -> String
pretty f xs = concatMap f xs

prettyVerbose :: [CharmanderInstruction] -> String
prettyVerbose = pretty verbose
   where
     verbose IncreaseCell = "Increase the current cell\n"
     verbose DecreaseCell = "Decrease the current cell\n"
     ...


Or you want to print Charmander code:

prettyCharmander :: [CharmanderInstruction] -> String
prettyCharmander = pretty charmander
   where
     charmander IncreaseCell = "charmander-charmander\n"
     charmander DecreaseCell = "cha-cha\n"
     ...


Or you want to print… Brainfuck:

prettyBrainfuck :: [CharmanderInstruction] -> String
prettyBrainfuck = pretty brainfuck
   where
     brainfuck IncreaseCell = "+"
     brainfuck DecreaseCell = "-"
     ...


As you can see, using CharmanderInstruction will enable you to print the code in many different ways.

Parsing

But printing instructions doesn't help. We need to somehow parse them. You would rewrite parse to

parse :: String -> Code


and parse the code as instructions instead of changing the program. Parsing the loop can be tricky, but is manageable. However, this will actually show you the instructions, whereas your previous program only showed you the code you already had in your file.

Also, you can write parseBrainfuck and parseBulbasaur` the same way, and the rest of your pipeline will still work.

Execute



  • I created

Code Snippets

parse :: String -> Program -> IO Program
parse "char"                  = char
parse "char-char"             = charChar
parse "cha"                   = cha 
parse "charmander"            = charmander
parse "cha-cha"               = chaCha
parse "charmander-charmander" = charmanderCharmander
parse "charmander-char"       = charmanderChar
parse "cha-charmander-char"   = chaCharmanderChar
parse _                       = unknown
parse :: Char -> Program -> IO Program
parse '<' = lessThan
parse '>' = greaterThan
parse '+' = plus
parse '-' = minus
parse '.' = dot
parse ',' = comma
parse '[' = leftBracket
parse ']' = rightBracket
parse _   = unknown
-- instead of char
previousCell :: Program -> IO Program
previousCell = return $ move (-1) Program

-- instead of charChar
nextCell :: Program -> IO Program
nextCell = return $ move 1 Program
parse :: String -> Program -> IO Program
parse "char"                  = previousCell
parse "char-char"             = nextCell
parse "cha"                   = getCell
parse "charmander"            = putCell
parse "cha-cha"               = decreaseCell
parse "charmander-charmander" = increaseCell
parse "charmander-char"       = startLoop
parse "cha-charmander-char"   = endLoop
parse _                       = unknown
type Code = [String]

data Program = Program {
    dp :: DP,
    memory :: Memory,
    code :: Code,
    loopback :: [Code]
} deriving Show

Context

StackExchange Code Review Q#128833, answer score: 52

Revisions (0)

No revisions yet.