Brain Flak implementation in Haskell

Question

I'm a beginner to Haskell and functional programming as a whole and as a first project I've written a Brain-Flak implementation in Haskell.

I wanted to get some feedback on this implementation because I've never done anything this big in a functional programming language. Is my code two iterative? What could make this better Haskell? I found pattern matching very useful, am I using it too much?

---

BrainHack:

Currently I don't have any fancy IO for this program, just a function that can be called with ghci. The relevant function here is brainflak it takes a String as source and a [Integer] as input to the Brain-Flak. It is really just a wrapper around the function bf that uses balanced to first check if the Brain-Flak code is syntactically valid. bf does most of the computation using pattern matching and the Three Stack Model of Brain Flak.

-- pop is a head that defaults to zero
pop :: (Integral a) => [a] -> a
pop [] = 0
pop (x:_) = x
-- rest is a tail for pop
rest :: (Integral a) => [a] -> [a]
rest [] = []
rest (_:x) = x
-- topadd adds an Integer to the top of a [Integer]
topadd :: [Integer] -> Integer -> [Integer]
topadd [] x = [x]
topadd (a:[]) x = [a+x]
topadd (a:b) x = (a+x):b
-- ir is a helper function of interior
ir :: String -> Integer -> String
ir x 0 = ""
ir ('{':x) y = "{" ++ (ir x (y+1))
ir ('}':x) y = "}" ++ (ir x (y-1))
ir (a:x) y = [a] ++ (ir x y )
-- interior finds the inside of a loop {x}... -> x
interior :: String -> String
interior x = init (ir x 1)
-- ex is a helper function for exterior
ex :: String -> Integer -> String
ex x 0 = x
ex ('{':x) y = ex x (y+1)
ex ('}':x) y = ex x (y-1)
ex (a:x) y = ex x y
-- exterior finds all the code after a loop {...}x -> x
exterior :: String -> String
exterior x = ex x 1
-- bf is the implementation of brain-flak
bf :: String -> ([Integer],[Integer],[Integer]) -> ([Integer],[Integer],[Integer])
bf [] (x,y,z)= (x,y,z)
bf ('(':')':a) (x,y,z)= bf a (x,y,((pop z+1):rest z))
bf ('<':'>':a) (x,y,z)= bf a (y,x,z)
bf ('{':'}':a) (x,y,z)= bf a ((rest x),y,(topadd z (pop x)))
bf ('[':']':a) (x,y,z)= bf a (x,y,(topadd z (toInteger (length x))))
bf ('(':a) (x,y,z)= bf a (x,y,(0:z))
bf ('<':a) (x,y,z)= bf a (x,y,(0:z))
bf ('[':a) (x,y,z)= bf a (x,y,(0:z))
bf (')':a) (x,y,(h:z))= bf a ((h:x),y,(topadd z h))
bf (']':a) (x,y,(h:z))= bf a (x,y,(topadd z (-h)))
bf ('>':a) (x,y,(_:z))= bf a (x,y,z)
bf ('{':a) t = bf (exterior a) (loop (interior a) t)
bf (_:a) t = bf a t
-- loop runs the same code until the TOS is zero
loop :: String -> ([Integer],[Integer],[Integer]) -> ([Integer],[Integer],[Integer])
loop s ([],y,z) = ([],y,z)
loop s (0:x,y,z) = (0:x,y,z)
loop s x = loop s (bf s x)
-- bl is an helper function of balance
bl :: String -> String -> Bool
bl [] [] = True
bl [] _ = False
bl ('(':x) y = bl x (')':y) 
bl ('[':x) y = bl x (']':y) 
bl ('<':x) y = bl x ('>':y) 
bl ('{':x) y = bl x ('}':y) 
bl _ [] = False
bl (a:x) (b:y) = (a == b) && (bl x y)
-- balanced checks if a particular String is balanced
balanced :: String -> Bool
balanced x = bl x []
-- Implements Brain-Flak
brainflak :: String -> [Integer] -> [Integer]
brainflak s x
 | balanced source = (\(a,_,_) -> a) (bf source (x,[],[]))
 | otherwise = error "Unbalanced braces."
 where source = [a|a <- s, elem a "()[]<>{}"]

• Tamoghna Chowdhury: Why use [Char] over its arguably more intuitive alias String?
• Sriotchilism O'Zaic: @TamoghnaChowdhury Didn't think to. I'm new to this :p. Thanks for the advice.

Answer 1

You can make the structure of your code a bit more intuitive and obvious by using something akin to a REPL.

Now back when Lisp was the new hot stuff, people would write interactive programs like so: (loop (print (eval (read (..))))), which is executed from inner to outer. We can adapt this structure for general interpreters, something like: print $ evalBF $ parseBF. Now since haskell doesn't like the side-effects that print entails when we're not in a Monad, we can even go so far as to abstract that away:

main :: IO ()
main = do
 -- making a bit of an assumption as to how things are passed in
 (program:arguments) <- getArgs
 let compiled = parse program
 print $ execute compiled $ asStacks arguments

This separates the responsibility of semantics from the responsibility of syntax, which enables us to theoretically define a different syntax for a BrainFlak equivalent language and choose the syntax through a command line switch or so.

---

So far, so clear.

At this point we want to grab a unified representation of a BF program, that doesn't rely on syntax. Now the esolangs wiki entry you linked specifies exactly these things are called: Monads and Nilads.

Now an OOP programmer would attempt to encapsulate the syntax and the behaviour of these into the same thing, but since we want to keep data and behaviour separate in haskell, it makes more sense to attack this from a different angle.

For that purpose I'd propose the following:

data BfProgram = OneNilad |
 HeightNilad |
 PopNilad |
 ToggleNilad |
 PushMonad BfProgram |
 EvalMonad BfProgram |
 LoopMonad BfProgram |
 ExecuteMonad BfProgram |
 Sequence [BfProgram]

_{thanks to Zeta for suggesting OneNilad and HeightNilad}

This enables us to somewhat cleanly parse a string into a syntax tree like so:

parse :: String -> BfProgram
parse '(':')':cont = Sequence $ OneNilad : (flattenSeq $ parse cont)
parse '[':']':cont = Sequence $ HeightNilad : (flattenSeq $ parse cont)
parse '{':'}':cont = Sequence $ PopNilad : (flattenSeq $ parse cont)
parse '<':'>':cont = Sequence $ ToggleNilad : (flattenSeq $ parse cont)
-- order matters, previous patterns will be matched before these
parse '(':code = Sequence $ (PushMonad $ parse monad) : (flattenSeq $ parse cont)
 where (monad,cont) = divideMonad '(' ')' code
parse '[':code = Sequence $ (EvalMonad $ parse monad) : (flattenSeq $ parse cont)
 where (monad,cont) = divideMonad '[' ']' code
parse '{':code = Sequence $ (LoopMonad $ parse monad) : (flattenSeq $ parse cont)
 where (monad,cont) = divideMonad '{' '}' code
parse '<':code = Sequence $ (ExecuteMonad $ parse monad) : (flattenSeq $ parse cont)
 where (monad,cont) = divideMonad '<' '>' code
parse _ = Sequence []
-- another option would be to throw an error here

Note the similarity to your bf function?

Now this block parses a given syntactically valid BfProgram from a String into an actual Program. To not make it too easy for you, I'll only show you the type-signatures of the helper functions. The divideMonad is the more interesting here (tip, you already have something similar in your code):

divideMonad :: Char -> Char -> String -> (String, String)

and flattenSeq is the following:

flattenSeq :: BfProgram -> [BfProgram]

given this, we can now rewrite bf as execute like so:

execute :: BfProgram -> ([Integer], [Integer], [Integer]) -> ([Integer], [Integer], [Integer])
execute (Sequence []) stacks = stacks
execute (Sequence (x:xs)) stacks = execute (Sequence xs) $ execute x stacks
execute OneNilad (x,y,z) = (x, y, ((pop z+1):rest z))
execute ToggleNilad (x,y,z) = (y,x,z)
execute PopNilad (x,y,z) = ((rest x), y, (topadd z (pop x)))
execute HeightNilad (x,y,z) = (x,y,(topadd z (toInteger (length x))))
-- nilads done, always nice
execute (PushMonad p) (x,y,z) = apply $ execute p (x,y,(0:z))
 where apply (x,y,(h:z)) = ((h:x),y,(topadd z h))
execute (EvalMonad p) (x,y,z) = apply $ execute p (x,y,(0:z))
 where apply (x,y,(h:z)) = (x,y,(topadd z (-h)))
execute (ExecuteMonad p) (x,y,z) = apply $ execute p (x,y,(0:z))
 where apply (x,y,(_:z)) = (x,y,z)
execute (LoopMonad p) stacks = loop p stacks
 where loop p ([],y,z) = ([],y,z)
 loop p (x@(0:_),y,z) = (x,y,z)
 loop p stacks = loop p $ execute p stacks

Written like this we have eliminated the String from execute and thus successfuly separated semantics from syntax (as well as program data from program code)

Now if you compare this with the code you already have, you should notice some striking similarities, and some key differences.

One important difference is that I've opted to use much longer names.
Another one is the use of "local function declarations". That way I eliminate much of -- x is a helper function of y.

Last but not least, I'll recommend considering another step: pop, topadd, and rest are functions that are to be called on BF-stacks. You can clarify their usage by grouping them in a class.

The last thing that remains to say now is: I actually didn't check whether the code I provide here compiles. If you get some compiler errors, please do notify me :)