-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | An optimizing Brainfuck compiler and evaluator -- -- hbf is a compiler and executor of Brainfuck programs. It provides two -- executables: hbfc the Brainfuck compiler, and hbf -- the virtual machine that executes compiled Brainfuck programs. @package hbf @version 0.2.0.0 -- | All the basic types for the Brainfuck compiler and VM are defined in -- this module. This includes the different instructions (Ops), -- the Program and the MachineIO. module HBF.Types -- | Operations or instructions in the Brainfuck virtual machine. -- -- Some of these operations are "native" to Brainfuck and others are the -- result of optimization during compilation. The compiler generates -- these types of instructions and the virtual machine can execute them. -- -- In all these instructions the MemOffset represents a shift -- relative to the current position of the pointer. The operation will -- refer and apply its action to this shifted position. data Op -- | Increment by the amount specified by the Int Inc :: {-# UNPACK #-} !Int -> {-# UNPACK #-} !MemOffset -> Op -- | Move the current pointer by the specified amount Move :: {-# UNPACK #-} !MemOffset -> Op -- | Repeatedly read a byte into the machine and write the last one read to -- the shifted position. n is usually 1 in real programs, but -- not always. Where the byte is read from will depend on the -- MachineIO impleentation. In :: {-# UNPACK #-} !Int -> {-# UNPACK #-} !MemOffset -> Op -- | Repeatedly write the byte in the shifted position. Where the byte is -- written will depend on the MachineIO impleentation. Out :: {-# UNPACK #-} !Int -> {-# UNPACK #-} !MemOffset -> Op -- | Native Brainfuck looping instruction. Loop :: ![Op] -> Op -- | Optimized instruction. Set the shifted position to zero. In Brainfuck -- this is usually written as [-] Clear :: {-# UNPACK #-} !MemOffset -> Op -- | Optimized instruction. Multiply by the factor the byte in the first -- MemOffset, writting to the second one. Second -- MemOffset is relative to the first one. In brainfuck this is -- usually written as [->+<] and similar expressions. Mul :: {-# UNPACK #-} !MulFactor -> {-# UNPACK #-} !MemOffset -> {-# UNPACK #-} !MemOffset -> Op -- | Find the nearest zero in the given direction, starting at the offset -- position. See Direction. Scan :: !Direction -> {-# UNPACK #-} !MemOffset -> Op -- | An offset into the Brainfuck VM memory. Positive numbers are in the -- direction of higher memory. newtype MemOffset MemOffset :: Int -> MemOffset -- | A factor to multiply by in the Mul instruction. newtype MulFactor MulFactor :: Int -> MulFactor -- | A direction to Scan for a memory position. Up is in the -- direction of higher memory. data Direction -- | Scan in the direction of higher memory. Up :: Direction -- | Scan in the direction of lower memory. Down :: Direction -- | Marker type to distinguish optimized and Unoptimized -- Programs. data Optimized -- | Marker type to distinguish Optimized and unoptimized -- Programs. data Unoptimized -- | A list of Ops. opt will be one of Optimized or -- Unoptimized to distinguish both types of programs at the type -- level. newtype Program opt Program :: [Op] -> Program opt -- | The list of instructions in the program. [instructions] :: Program opt -> [Op] -- | Return the full list of instructions in a program, by unrolling -- Loop instructions into the list. -- -- 
--   >>> flattened $ Program [Inc 1 0, Loop [Move 1, Scan Up 0]]
--   [Inc 1 0,Move 1,Scan Up 0]
--
flattened :: Program o -> [Op] -- | The state of a Brainfuck virtual machine. data Machine v Machine :: v -> MemOffset -> Machine v -- | The full memory of the machine. This will be a Vector or a -- List. [memory] :: Machine v -> v -- | The current execution pointer, information is written and read at this -- position. [pointer] :: Machine v -> MemOffset -- | Provide input and output to a Brainfuck virtual machine. -- -- This class allows to run the VM in different monads, like IO or -- StateT. class MachineIO m putByte :: MachineIO m => Int8 -> m () getByte :: MachineIO m => m (Maybe Int8) -- | A data structure for mocking input and output to the VM. This can be -- used to run the VM in a StateT monad for testing purposes. data MockIO MockIO :: [Int8] -> [Int8] -> MockIO -- | Every time the machine executes an In instruction, input will -- be taken from this list. [machineIn] :: MockIO -> [Int8] -- | Every time the machine executes an Out instruction, output will -- be put into this list, in LIFO order. [machineOut] :: MockIO -> [Int8] -- | Create a MockIO that will have the given input available. mkMockIO :: [Int8] -> MockIO -- | Create a MockIO that will have the given input available. ASCII -- encoding. mkMockIOS :: String -> MockIO -- | Get the output after a VM has ran using this MockIO. mockOutput :: MockIO -> [Int8] -- | Get the output after a VM has ran using this MockIO. ASCII -- encoding. mockOutputS :: MockIO -> String -- | <$> with arguments reversed. (<&>) :: Functor f => f a -> (a -> b) -> f b -- | Helper function to convert a Right into a Just and a -- Left into a Nothing. eitherToMaybe :: Either a b -> Maybe b instance Control.DeepSeq.NFData HBF.Types.MockIO instance GHC.Generics.Generic HBF.Types.MockIO instance GHC.Classes.Eq HBF.Types.MockIO instance GHC.Show.Show HBF.Types.MockIO instance GHC.Classes.Eq v => GHC.Classes.Eq (HBF.Types.Machine v) instance GHC.Show.Show v => GHC.Show.Show (HBF.Types.Machine v) instance Control.DeepSeq.NFData (HBF.Types.Program opt) instance Data.Binary.Class.Binary (HBF.Types.Program opt) instance GHC.Classes.Eq (HBF.Types.Program opt) instance GHC.Show.Show (HBF.Types.Program opt) instance GHC.Generics.Generic (HBF.Types.Program opt) instance Control.DeepSeq.NFData HBF.Types.Op instance Data.Binary.Class.Binary HBF.Types.Op instance GHC.Generics.Generic HBF.Types.Op instance GHC.Classes.Eq HBF.Types.Op instance GHC.Show.Show HBF.Types.Op instance Control.DeepSeq.NFData HBF.Types.Direction instance Data.Binary.Class.Binary HBF.Types.Direction instance GHC.Generics.Generic HBF.Types.Direction instance GHC.Classes.Eq HBF.Types.Direction instance GHC.Show.Show HBF.Types.Direction instance Control.DeepSeq.NFData HBF.Types.MulFactor instance Data.Binary.Class.Binary HBF.Types.MulFactor instance GHC.Num.Num HBF.Types.MulFactor instance GHC.Classes.Eq HBF.Types.MulFactor instance GHC.Show.Show HBF.Types.MulFactor instance GHC.Generics.Generic HBF.Types.MulFactor instance Control.DeepSeq.NFData HBF.Types.MemOffset instance Data.Binary.Class.Binary HBF.Types.MemOffset instance GHC.Classes.Ord HBF.Types.MemOffset instance GHC.Num.Num HBF.Types.MemOffset instance GHC.Classes.Eq HBF.Types.MemOffset instance GHC.Show.Show HBF.Types.MemOffset instance GHC.Generics.Generic HBF.Types.MemOffset instance GHC.Base.Monad m => HBF.Types.MachineIO (Control.Monad.Trans.State.Strict.StateT HBF.Types.MockIO m) instance HBF.Types.MachineIO GHC.Types.IO instance GHC.Base.Semigroup (HBF.Types.Program o) instance GHC.Base.Monoid (HBF.Types.Program o) -- | Parsing Text into Program Unparsed module HBF.Parser -- | Parser for a full Program. -- -- 
--   >>> isRight $ parse program "  +[->>+  +[<] ##garbage## ],.[-]  can ignore garbage"
--   True
--
program :: Parser (Program Unoptimized) -- | Parser for an Op, ignoring unknown characters. -- -- 
--   >>> parse operation "  +///"
--   Right (Inc 1 0)
--
-- -- 
--   >>> parse operation "fooo  [+>]  baaar  "
--   Right (Loop [Inc 1 0,Move 1])
--
operation :: Parser Op -- | The characters allowed in a Brainfuck program except for the loop -- characters [ and ]. bfSimpleTokens :: String -- | The characters allowed in a Brainfuck program. bfTokens :: String -- | Parser for unknown characters -- -- 
--   >>> parse garbage "this is @#! garbage"
--   Right 't'
--
-- -- 
--   >>> isLeft $ parse garbage "+"
--   True
--
garbage :: Parser Char -- | Parser for simple operations (not loops). -- -- 
--   >>> parse simpleOp ">"
--   Right (Move 1)
--
-- -- 
--   >>> parse simpleOp "."
--   Right (Out 1 0)
--
simpleOp :: Parser Op -- | Parser for loops. -- -- 
--   >>> parse loopOp "[+-]"
--   Right (Loop [Inc 1 0,Inc (-1) 0])
--
loopOp :: Parser Op -- | Parse program stream. Returns an error or the parsed Program parseProgram :: Text -> Either ParseError (Program Unoptimized) -- | The abstract data type ParseError represents parse errors. It -- provides the source position (SourcePos) of the error and a -- list of error messages (Message). A ParseError can be -- returned by the function parse. ParseError is an -- instance of the Show and Eq classes. data ParseError -- | Functions to evaluate a compiled Brainfuck program. module HBF.Eval -- | An alias for a Machine in which memory is an unboxed vector of -- bytes. type MachineType = Machine (Vector Int8) -- | Evaluate the given program returning the end state of the -- Machine. The evaluation can happen in any PrimMonad for -- which we can do I/O. The reason to use PrimState is that we -- will use mutable vectors for the evaluation. eval :: (PrimMonad m, MachineIO m) => Program Optimized -> m MachineType -- | Evaluate the given program returning the end state of the -- Machine. The evaluation can happen in any PrimMonad for -- which we can do I/O. The reason to use PrimState is that we -- will use mutable vectors for the evaluation. VMOptions are used -- to tune the details of the VM, like available memory, verbosity, etc. evalWith :: (PrimMonad m, MachineIO m) => VMOptions -> Program Optimized -> m MachineType -- | Evaluate the given program returning the end state of the -- Machine. The evaluation happens in IO, so Input/Output is done -- to the console. evalWithIO :: VMOptions -> Program Optimized -> IO MachineType -- | Evaluate the given program returning the end state of the -- Machine. The evaluation can happen in any PrimMonad for -- which we can do I/O. The reason to use PrimState is that we -- will use mutable vectors for the evaluation. VMOptions are used -- to tune the details of the VM, like memory available, verbosity, etc. -- The evaluation starts with the specified MachineType, so the -- memory and initial pointer can be configured before running. evalWithMachine :: forall m. (PrimMonad m, MachineIO m) => VMOptions -> MachineType -> Program Optimized -> m MachineType -- | A VM Machine with the default memory available. emptyMachine :: MachineType -- | Create a new machine with the given memory mkMachine :: Word -> MachineType -- | Command line arguments for the VM evaluator. data VMOptions VMOptions :: Word -> Bool -> FilePath -> VMOptions -- | Available memory in bytes. [vmOptsMemoryBytes] :: VMOptions -> Word -- | Dump the contents of the memory after executing a program [vmOptsDumpMemory] :: VMOptions -> Bool -- | Path to the compiled program [vmOptsProgramPath] :: VMOptions -> FilePath -- | Default configuration for the VM. defaultVMOptions :: VMOptions -- | Parse a list of command line arguments printing errors to the stderr unsafeParse :: [String] -> IO VMOptions -- | Parse command line arguments printing errors to the stderr parse :: IO VMOptions -- | Parse a list of command line arguments parsePure :: [String] -> ParserResult VMOptions instance GHC.Show.Show HBF.Eval.VMOptions -- | In this module we: -- -- module HBF.Compiler -- | This parser is used to implement the mul optimization. See -- mulOpt. type ProgramParser a = ParsecT [Op] () Identity a -- | Command line flags to the Brainfuck compiler data CompilerOptions CompilerOptions :: Maybe FilePath -> Bool -> Bool -> Bool -> Bool -> Bool -> Bool -> FilePath -> CompilerOptions -- | Where to put the compiled output, if Nothing use the input -- basename with bfc extension [cOptsOut] :: CompilerOptions -> Maybe FilePath -- | Enable fusion optimization [cOptsFusionOptimization] :: CompilerOptions -> Bool -- | Enable clear loop optimization [cOptsClearLoopOptimization] :: CompilerOptions -> Bool -- | Enable mul loop optimization [cOptsMulOptimization] :: CompilerOptions -> Bool -- | Enable scan loop optimization [cOptsScanOptimization] :: CompilerOptions -> Bool -- | Enable offset instructions optimization [cOptsOffsetInstructionsOptimization] :: CompilerOptions -> Bool -- | Output more debugging information [cOptsVerbose] :: CompilerOptions -> Bool -- | Input source to the compiler, this should be Brainfuck code [cOptsSource] :: CompilerOptions -> FilePath -- | Helper datastructure to implement a stateful transformation in -- offsetInstructionOpt. data OffsetState OffSt :: [Op] -> [Op] -> MemOffset -> OffsetState -- | The optimized program so far [stOptimized] :: OffsetState -> [Op] -- | The current batch of instructions being optimized (between loops) [stBatch] :: OffsetState -> [Op] -- | The current offset since the last loop [stOffset] :: OffsetState -> MemOffset -- | Helper type to apply the Fuse optimization using a Monoid. newtype FusedProgram Fused :: Program Optimized -> FusedProgram [unfused] :: FusedProgram -> Program Optimized -- | Compilation summary for the user. It contains overview information and -- statistics about the compilation result. newtype CompilationSummary CompilationSummary :: Int -> CompilationSummary [compNumInstructions] :: CompilationSummary -> Int -- | Encode the compiled file into the given path. saveCompilerOutput :: Program Optimized -> FilePath -> IO () -- | Use the given CompilerOptions to parse, compile and optimize -- the text representation of a Brainfuck program into the IR. -- cOptsSource and cOptsOut in the compiler options are -- ignored. inMemoryCompile :: CompilerOptions -> Text -> Either ParseError (Program Optimized, CompilationSummary) -- | Summarize a compiled program creating the CompilationSummary summarizeCompilation :: Program Optimized -> CompilationSummary -- | Use CompilerOptions to read, compile, optimize, and save a -- program from/to the filesystem. Input and output files are provided by -- cOptsSource and cOptsOut. compile :: CompilerOptions -> IO (Either ParseError CompilationSummary) -- | Apply optimizations to the Unoptimized program turning. The -- optimizations that will be available are the ones specified by the -- CompilerOptions given. optimize :: CompilerOptions -> Program Unoptimized -> Program Optimized -- | Given a parsed program, turn it into an optimized one, but with the -- null optimization. Effectively this is only a type change. toIR :: Program Unoptimized -> Program Optimized -- | Apply the fusion optimization using the FusedProgram -- Monoid instance. -- -- The fusion optimization consist of turning multiple instructions into -- one. For example if the original Brainfuck code contains -- ++++, this would be parsed as -- -- 
--   Program [Inc 1 0, Inc 1 0, Inc 1 0, Inc 1 0]
--    
--
-- -- but it would be fused to a single IR instruction: Inc 4 0. -- -- 
--   >>> fusionOpt $ Program [Inc 1 0, Inc 1 0, Inc 1 0, Inc 1 0]
--   [Inc 4 0]
--
-- -- Similarly, other instructions, like Move, In, -- Out, Clear and Scan can be fused as long as the -- offset at which they must be applied is the same. -- -- Non fusable operation remain unchanged: -- -- 
--   >>> fusionOpt $ Program [Inc 1 0, Inc 1 1]
--   [Inc 1 0,Inc 1 1]
--
fusionOpt :: Program Optimized -> Program Optimized -- | Helper function used to implement optimizations Iterate over all -- Program instructions searching for Loops. For each -- Loop apply f. If f returns a list of new -- operations, replace the original loop with the new instructions. If -- f returns Nothing, process recursively the loop -- instructions. liftLoop :: ([Op] -> Maybe [Op]) -> Program o -> Program o -- | Basic optimization that turns the loop [-] into a single -- instruction Clear. Useful because clearing a memory position is -- a pretty common operation in Brainfuck and very expensive if treated -- as a loop. -- -- 
--   >>> :set -XOverloadedStrings
--   
--   >>> Right (res, _) = inMemoryCompile defaultCompilerOptions "[-]"
--   
--   >>> res
--   [Clear 0]
--
clearOpt :: Program Optimized -> Program Optimized -- | Copy and multiply optimization. A very common usage of loops is to -- copy the value of a memory position to a different: -- [->>+<<] this will move the contents of the -- current memory position to places to the right, also clearing the -- original position to zero. If we change the number of + -- operations we get multiplication, if we have several groups of -- ++.. operations we get multiple copies. In the general case, -- for example: -- -- 
--   >>> :set -XOverloadedStrings
--   
--   >>> Right (res, _) = inMemoryCompile defaultCompilerOptions "[->+>++>++++<<<]"
--   
--   >>> res
--   [Mul 1 0 1,Mul 2 0 2,Mul 4 0 3,Clear 0]
--
-- -- The original Brainfuck copies the current position one place to the -- right, doubles the current position two places to the right, and -- quadruples the current position three places to the right; finally -- zeroing the current position. With the mul optimization in this -- function, all that loop would be replaced by 4 instructions. mulOpt :: Program Optimized -> Program Optimized -- | Implement the scan optimization. Another common operation in Brainfuck -- is to search for the first zero in the neighboring memory, either to -- the right or to the left [>] or [<]. These -- loops can be replaced for a more optimal search, represented as a -- single Scan Up or Scan -- Down instruction. -- -- 
--   >>> scanOpt $ Program [Loop [Move 1]]
--   [Scan Up 0]
--
scanOpt :: Program Optimized -> Program Optimized -- | Start state for offsetInstructionOpt. emptyState :: OffsetState -- | Implement the offset instruction optimization. This is probably the -- most complex optimization implemented in the library. -- -- In streams of instructions between loops, there is no need to keep -- updating the current position if we can keep track of where the -- different operations should be applied. This is a trade-off of time -- (not updating the pointer) by space (keeping track of the offset in -- every operation). For example the following unoptimized code -- -- 
--   >>> offsetInstructionOpt  $ Program [Loop [], Move 1, Inc 1 0, Move 2, Clear 0, Mul 2 0 1, Loop []]
--   [Loop [],Inc 1 1,Clear 3,Mul 2 3 1,Move 3,Loop []]
--
-- -- And the optimization eliminated one Move instruction. In -- general, for larger programs the gain will be more noticeable. -- -- An important detail to take into account is that Scan -- operations break the stream of operations that can be optimized -- together, and turn the accumulated offset back to zero: -- -- 
--   >>> offsetInstructionOpt  $ Program [Loop [], Move 1, Inc 1 0, Scan Up 0, Inc 0 2, Loop []]
--   [Loop [],Inc 1 1,Scan Up 1,Inc 0 2,Loop []]
--
offsetInstructionOpt :: Program Optimized -> Program Optimized -- | Load a compiled program from saveCompilerOutput output. load :: ByteString -> Program Optimized -- | Load a compiled program saved with saveCompilerOutput. loadFile :: FilePath -> IO (Program Optimized) optionsP :: Parser CompilerOptions options :: ParserInfo CompilerOptions -- | Default compiler options: all optimizations, not verbose, no input or -- output files. defaultCompilerOptions :: CompilerOptions -- | Compiler options: all optimizations off. noOptimizationCompilerOptions :: CompilerOptions -- | Parse a list of command line arguments parsePure :: [String] -> ParserResult CompilerOptions -- | Parse a list of command line arguments printing errors to the stderr unsafeParse :: [String] -> IO CompilerOptions -- | Parse command line arguments printing errors to the stderr parse :: IO CompilerOptions -- | Parse successfully if the token satisfies the predicate. satisfy' :: Show t => (t -> Bool) -> ParsecT [t] () Identity t -- | Parse movement to the right (>), returning the offset value. -- -- 
--   >>> Parsec.parse mrightP "" [Move 3]
--   Right 3
--
-- -- 
--   >>> Data.Either.isLeft $ Parsec.parse mrightP "" [Move (-1)]
--   True
--
mrightP :: ProgramParser MemOffset -- | Parsemovement to the left (<), returning the offset value. -- -- 
--   >>> Parsec.parse mleftP "" [Move (-3)]
--   Right 3
--
-- -- 
--   >>> Data.Either.isLeft $ Parsec.parse mleftP "" [Move 1]
--   True
--
mleftP :: ProgramParser MemOffset -- | Parse increment, returning total increment. -- -- 
--   >>> Parsec.parse plusP "" [Inc 3 0]
--   Right 3
--
-- -- 
--   >>> Data.Either.isLeft $ Parsec.parse plusP "" [Inc (-2) 0]
--   True
--
plusP :: ProgramParser Int -- | Parse decrement, returning total decrement. -- -- 
--   >>> Parsec.parse minusP "" [Inc (-3) 0]
--   Right 3
--
-- -- 
--   >>> Data.Either.isLeft $ Parsec.parse minusP "" [Inc 2 0]
--   True
--
minusP :: ProgramParser Int -- | Sum the result of a parser applied repeatedly -- -- 
--   >>> Parsec.parse (summedP plusP) "" [Inc 3 0, Inc 1 0, Inc (-4) 0]
--   Right 4
--
summedP :: Num n => ProgramParser n -> ProgramParser n -- | Full multiple copy/multiply operation parser. Returns the set of -- factors and relative, incremental offsets. -- -- 
--   >>> Parsec.parse mulP "" [Inc (-1) 0, Move 1, Inc 2 0, Move 3, Inc 1 0, Move (-4)]
--   Right [(2,1),(1,3)]
--
mulP :: ProgramParser [(MulFactor, MemOffset)] -- | Is the instruction a right movement? isRight :: Op -> Bool -- | Is the instruction a left movement? isLeft :: Op -> Bool -- | Is the instruction an increment? isPlus :: Op -> Bool -- | Is the instruction a decrement? isMinus :: Op -> Bool -- | The abstract data type ParseError represents parse errors. It -- provides the source position (SourcePos) of the error and a -- list of error messages (Message). A ParseError can be -- returned by the function parse. ParseError is an -- instance of the Show and Eq classes. data ParseError instance GHC.Show.Show HBF.Compiler.CompilerOptions instance GHC.Show.Show HBF.Compiler.OffsetState instance GHC.Show.Show HBF.Compiler.FusedProgram instance GHC.Show.Show HBF.Compiler.CompilationSummary instance GHC.Base.Semigroup HBF.Compiler.FusedProgram instance GHC.Base.Monoid HBF.Compiler.FusedProgram