-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A simple interpreter for arrayForth, the language used on GreenArrays chips.
--   
--   This is a package for working with arrayForth. This is a variant of
--   Forth used by GreenArrays chips. This package contains an arrayForth
--   simulator, two different representations of arrayForth programs and
--   some utilities like parsing. It also supports synthesizing arrayForth
--   programs using MCMC. The basic idea is to find arrayForth programs by
--   taking a simple prior distribution of programs and using a randomized
--   hill-climbing algorithm to find a program fulfilling certain tests.
@package array-forth
@version 0.2.1.4

module Language.ArrayForth.Parse

-- | Possible ways the input string can be malformed.
data ParseError
BadOpcode :: String -> ParseError
NotSlot3 :: String -> ParseError
NotJump :: String -> ParseError
NoAddr :: String -> ParseError
BadNumber :: String -> ParseError

-- | Is the given string a valid number with no other tokens?
isNumber :: String -> Bool

-- | Tries to read a word, giving an error if it fails.
readWord :: Read a => String -> Either ParseError a
instance Show ParseError

module Language.ArrayForth.Opcode

-- | The 18-bit word type used by Greenarrays chips.
type F18Word = Word18

-- | Each F18A instruction, ordered by opcode.
data Opcode
Ret :: Opcode
Exec :: Opcode
Jmp :: Opcode
Call :: Opcode
Unext :: Opcode
Next :: Opcode
If :: Opcode
MinusIf :: Opcode
FetchP :: Opcode
FetchPlus :: Opcode
FetchB :: Opcode
Fetch :: Opcode
StoreP :: Opcode
StorePlus :: Opcode
StoreB :: Opcode
Store :: Opcode
MultiplyStep :: Opcode
Times2 :: Opcode
Div2 :: Opcode
Not :: Opcode
Plus :: Opcode
And :: Opcode
Or :: Opcode
Drop :: Opcode
Dup :: Opcode
Pop :: Opcode
Over :: Opcode
ReadA :: Opcode
Nop :: Opcode
Push :: Opcode
SetB :: Opcode
SetA :: Opcode

-- | The names of the different instructions, ordered by opcode.
names :: [String]

-- | All of the opcodes, in order.
opcodes :: [Opcode]

-- | Tries to read a given string as an opcode from the list of names.
readOpcode :: String -> Either ParseError Opcode

-- | Converts a word to an opcode. The word has to be < 32.
toOpcode :: F18Word -> Opcode

-- | Converts an Opcode to its 18-bit word representation.
fromOpcode :: Opcode -> F18Word

-- | Returns whether the given opcode is a jump instruction expecting an
--   address.
isJump :: Opcode -> Bool

-- | Can the given opcode go in the last slot?
slot3 :: Opcode -> Bool

-- | Estimates how long a given opcode will take to execute. Normal opcodes
--   take 1.5 nanoseconds where ones that access the memory take 5
--   nanoseconds.
opcodeTime :: Opcode -> Double
instance Eq Opcode
instance Bounded Opcode
instance Enum Opcode
instance Read Opcode
instance Show Opcode

module Language.ArrayForth.NativeProgram

-- | Represents a word in memory. This word can either contain opcodes,
--   opcodes and a jump address or just a constant number.
data Instrs
Instrs :: Opcode -> Opcode -> Opcode -> Opcode -> Instrs
Jump3 :: Opcode -> Opcode -> Opcode -> F18Word -> Instrs
Jump2 :: Opcode -> Opcode -> F18Word -> Instrs
Jump1 :: Opcode -> F18Word -> Instrs
Constant :: F18Word -> Instrs

-- | A program in the F18A instruction set.
type NativeProgram = [Instrs]

-- | Splits a list into chunks of at most four, breaking off a chunk
--   whenever it sees an element matching the given predicate. This is
--   useful for splitting a program along word boundaries, accounting for
--   jump addresses.
splitWords :: (a -> Bool) -> [a] -> [[a]]

-- | Read a whole program, splitting instructions up into words.
readNativeProgram :: String -> Either ParseError NativeProgram

-- | Returns the given instructions as an actual word. This assumes the
--   address is sized appropriately.
toBits :: Instrs -> F18Word

-- | Reads in a word as a set of opcodes.
fromBits :: F18Word -> Instrs

-- | Returns the opcodes in the given instruction word. A constant
--   corresponds to not having any opcodes.
toOpcodes :: Instrs -> [Opcode]

-- | Estimates the running time of the program in nanoseconds. This is
--   based on the numbers provided in the manual: faster instructions take
--   1.5 nanoseconds and slower ones take 5. For now, this estimate ignores
--   control flow like ifs and loops.
runningTime :: NativeProgram -> Double
instance [overlap ok] Eq Instrs
instance [overlap ok] IsString NativeProgram
instance [overlap ok] Read NativeProgram
instance [overlap ok] Show Instrs

module Language.ArrayForth.Stack

-- | A stack containing only 0s.
empty :: Stack

-- | Pushes the given element on top of the stack, discarding the last
--   element.
push :: Stack -> F18Word -> Stack

-- | Pops the top of the stack, returning the value and the new stack.
pop :: Stack -> (Stack, F18Word)

-- | Push the given elements onto the stack one-by-one.
fill :: Stack -> [F18Word] -> Stack
data Stack
instance Eq Stack
instance Show Stack


-- | Defines the basic operations for reading and writing through ports.
--   
--   Each core has four ports connecting it to its neighbors. The cores
--   around the edges have ports connected to IO devices. A <a>Channel</a>
--   is just a type containing the four ports that you can write to or read
--   from.
module Language.ArrayForth.Channel

-- | A channel representing the four communication directions a core may
--   use. In practice, these will either be hooked up to other cores or to
--   IO. Nothing represents no message; if there is a word, execution will
--   block.
data Channel
Channel :: Maybe F18Word -> Maybe F18Word -> Maybe F18Word -> Maybe F18Word -> Channel
right :: Channel -> Maybe F18Word
down :: Channel -> Maybe F18Word
left :: Channel -> Maybe F18Word
up :: Channel -> Maybe F18Word

-- | The four possible port directions.
data Port
R :: Port
D :: Port
L :: Port
U :: Port

-- | An empty channel has no reads or writes and doesn't block execution.
emptyChannel :: Channel

-- | Write to the ports specified by the given memory address. This will
--   clear all the channels not being written to (by setting them to
--   Nothing).
--   
--   The ports to use are specified by bits 5–8 of the address. These bits
--   correspond respectively to up, left, down and right. Bits 5 and 7 are
--   inverted—0 turns the channel *on*.
writePort :: F18Word -> F18Word -> Channel

-- | Read the inputs from the ports specified by the given address. The
--   address is handled the same way as in <tt><a>writePort</a></tt>.
--   Returns <tt>Nothing</tt> if blocked on the read.
--   
--   If more than one of the read ports has data, this currently just
--   chooses the first one based on the right, down, left, up order. I
--   don't know if this is the correct behavior—perhaps I should just xor
--   them together or something?
readPort :: F18Word -> Channel -> Maybe F18Word
instance Show Channel
instance Eq Channel
instance Show Port
instance Eq Port
instance Bounded Port
instance Enum Port
instance Monoid Channel


-- | This module defines types and functions for working with the state of
--   a single core.
--   
--   The most important type is State, which contains all the information
--   about the core. This includes the registers, the memory, both stacks
--   and communication ports. Right now, it's just a big record; in the
--   future, I might make it more polymorphic using lenses.
--   
--   There are also some useful types and functions for working with the
--   memory of a chip and its communication channels.
module Language.ArrayForth.State

-- | The chip's RAM, ROM and IO channels. The RAM and ROM should each
--   contain 64 words.
--   
--   For now, input and output is split into two different types, even
--   though they're combined on the physical chip. I'm simply not sure how
--   to handle the case that both chips simultaneously write to the same
--   channel.
data Memory
Memory :: Vector Int -> Vector Int -> Channel -> Channel -> Memory
ram :: Memory -> Vector Int
rom :: Memory -> Vector Int
input :: Memory -> Channel
output :: Memory -> Channel

-- | Memory with RAM and ROM zeroed out and nothing on the communication
--   channels.
emptyMem :: Memory

-- | The number of words in memory. Both ram and rom are this size. For
--   some reason, the ram and rom address spaces are *double* this size
--   respectively, wrapping around at the half-way point.
memSize :: Num a => a

-- | A state representing the registers, stacks, memory and communication
--   channels of a core. Note that all the fields are strict; they should
--   also be unboxed thanks to <tt>-funbox-strict-fields</tt> (set in the
--   .cabal file).
--   
--   For now, this is just a record; however, I might rewrite it to use
--   lenses in the near future.
data State
State :: !F18Word -> !F18Word -> !F18Word -> !F18Word -> !F18Word -> !F18Word -> !(Maybe F18Word) -> !Stack -> !Stack -> !Memory -> State
a :: State -> !F18Word
b :: State -> !F18Word
p :: State -> !F18Word
r :: State -> !F18Word
s :: State -> !F18Word
t :: State -> !F18Word

-- | the i register can be <tt>Nothing</tt> if it is blocked on a
--   communication port.
i :: State -> !(Maybe F18Word)
dataStack :: State -> !Stack
returnStack :: State -> !Stack
memory :: State -> !Memory

-- | The state corresponding to a core with no programs loaded and no
--   instructions executed.
startState :: State

-- | Increment the p register for the given state. If p is in RAM or ROM,
--   this wraps p as appropriate. If p is in IO, this does nothing and p
--   remains unchanged.
incrP :: State -> State

-- | The next word of instructions to execute in the given state. Returns
--   <tt>Nothing</tt> if <tt>p</tt> is blocked on a communication channel.
next :: State -> Maybe Instrs

-- | Pops the data stack of the given state, updating <tt>s</tt> and
--   <tt>t</tt>.
dpop :: State -> (State, F18Word)

-- | Push a word onto the data stack, updating <tt>s</tt> and <tt>t</tt>.
dpush :: State -> F18Word -> State

-- | Pops the return stack of the given state, updating <tt>r</tt>.
rpop :: State -> (State, F18Word)

-- | Push a word onto the return stack, updating <tt>r</tt>.
rpush :: State -> F18Word -> State

-- | Force an address to be in range of memory: [0,64), also converting
--   between different integral types.
toMem :: (Integral a, Integral b) => a -> b

-- | Read the memory at a location given by a Forth word. Returns
--   <tt>Nothing</tt> if blocked on a communication channel.
(!) :: Memory -> F18Word -> Maybe F18Word

-- | Set the memory using Forth words. A state with anything in the output
--   channel remains blocked until one of the active ports is read.
set :: State -> F18Word -> F18Word -> State

-- | Is the state is blocked because it has written to a port? Note that
--   this does *not* consider being blocked on a read!
blocked :: State -> Bool

-- | Loads the given program into memory at the given starting position.
setProgram :: F18Word -> NativeProgram -> State -> State

-- | Load the given memory words into the state starting at the given
--   address.
loadMemory :: F18Word -> [F18Word] -> State -> State

-- | Sets the input value at the given port.
sendInput :: Port -> F18Word -> State -> State
instance Show Memory
instance Eq Memory
instance Show State

module Language.ArrayForth.Interpreter

-- | A trace of a progam is the state after every word is executed.
type Trace = [State]

-- | Runs a single word's worth of instructions starting from the given
--   state, returning the intermediate states for each executed opcode.
wordAll :: Instrs -> State -> [State]

-- | Runs a single word's worth of instructions, returning only the final
--   state.
word :: Instrs -> State -> State

-- | Executes a single word in the given state, incrementing the program
--   counter and returning all the intermediate states.
stepAll :: State -> [State]

-- | Executes a single word in the given state, returning the last
--   resulting state.q
step :: State -> State

-- | Trace the given program, including all the intermediate states.
traceAll :: State -> Trace

-- | Returns a trace of the program's execution. The trace is a list of the
--   state of the chip after each step.
traceProgram :: State -> Trace

-- | Trace a program until it either hits four nops or all 0s.
stepProgram :: State -> Trace

-- | Runs the program unil it hits a terminal state, returning only the
--   resulting state.
eval :: State -> State

-- | Executes the specified program on the given state until it hits a
--   "terminal" word--a word made up of four nops or all 0s.
runNativeProgram :: State -> NativeProgram -> State

-- | Estimates the execution time of a program trace.
countTime :: Trace -> Double

-- | Checks that the program trace terminated in at most n steps, returning
--   Nothing otherwise.
throttle :: Int -> Trace -> Either Trace Trace

-- | Does the given opcode cause the current word to stop executing?
endWord :: Opcode -> Bool

-- | Extends the given trace by a single execution step. The trace cannot
--   be empty.
run :: Opcode -> [State] -> [State]

-- | Executes an opcode on the given state. If the state is blocked on some
--   communication, nothing changes.
execute :: Opcode -> State -> State

-- | Execute a jump instruction to the given address.
jump :: Opcode -> F18Word -> State -> State

module Language.ArrayForth.Distance
type Distance = Sum Double

-- | Counts the number of bits that differ between two numbers.
countBits :: (Integral n, Bits n) => n -> n -> Int

-- | Return a distance function that counts the different bits between the
--   given registers. You could use it like `compareRegisters [s, t]`.
registers :: [State -> F18Word] -> (State -> State -> Distance)

-- | Returns a distance function that counts the different bits between the
--   given memory locations.
locations :: [F18Word] -> (State -> State -> Distance)

-- | Returns a score that counts the number of matching states according to
--   some projection function.
matching :: Eq a => (State -> a) -> (Trace -> Trace -> Distance)
instance Score Distance

module Language.ArrayForth.Program
data Addr
Concrete :: F18Word -> Addr
Abstract :: String -> Addr

-- | Represents a single instruction as viewed by the synthesizer. This can
--   be an opcode, a numeric literal or a token representing an unused
--   slot.
data Instruction
Opcode :: Opcode -> Instruction
Jump :: Opcode -> Addr -> Instruction
Number :: F18Word -> Instruction
Label :: String -> Instruction
Unused :: Instruction

-- | A program to be manipulated by the MCMC synthesizer
type Program = [Instruction]

-- | Tries to parse the given string as an instruction, which can either be
--   a number, an opcode or "_" representing Unused.
readInstruction :: String -> Either ParseError Instruction

-- | Reads a program in the synthesizer's format.
readProgram :: String -> Either ParseError Program

-- | Takes a program as handled by the synthesizer and makes it native by
--   turning literal numbers into @p and fixing any issues with
--   instructions going into the last slot as well as prepending nops
--   before + instructions.
toNative :: Program -> NativeProgram

-- | Does this instruction force a word boundary?
boundary :: Instruction -> Bool

-- | Resolves labels into addresses, assuming the program starts at the
--   given memory location.
labels :: F18Word -> Program -> Program

-- | Insert extra nops to account for instructions that cannot go into the
--   last slot.
fixSlot3 :: Program -> Program

-- | Gets a synthesizer program from a native program. Currently does not
--   support jumps.
fromNative :: NativeProgram -> Program

-- | Runs a given program from the default starting state.
runProgram :: State -> Program -> State

-- | Loads the given synthesizer-friendly program into the given state.
load :: Program -> State -> State
instance [overlap ok] Eq Addr
instance [overlap ok] Eq Instruction
instance [overlap ok] IsString Program
instance [overlap ok] Read Program
instance [overlap ok] Show Instruction
instance [overlap ok] Show Addr

module Language.ArrayForth.Synthesis

-- | A score type that contains a correctness value and a performance
--   value.
data DefaultScore
DefaultScore :: Double -> Double -> DefaultScore

-- | Creates an evaluation function from a spec, a set of inputs and a
--   function for comparing program traces.
trace :: Monoid score => Program -> [State] -> (Trace -> Trace -> score) -> Program -> score

-- | Using a given correctness measure, produce a score also containing
--   performance.
withPerformance :: Score s => (Trace -> Trace -> s) -> (Trace -> Trace -> DefaultScore)

-- | Given a specification program and some inputs, evaluate a program
--   against the specification for both performance and correctness.
--   Normalize the score based on the number of test cases.
evaluate :: Program -> [State] -> (State -> State -> Distance) -> Program -> DefaultScore

-- | The default distribution of instructions. For now, we do not support
--   any sort of jumps. All the other possible instructions along with
--   constant numbers and unused slots are equally likely. The numeric
--   value of constants is currently a uniform distribution over 18-bit
--   words.
defaultOps :: Distr Instruction
pairs :: [(Instruction, Instruction)]
removePairs :: Distr Instruction -> Mutation Program

-- | The default mutations to try. For now, this will either change an
--   instruction or swap two instructions in the program, with equal
--   probability.
defaultMutations :: Mutation Program
instance [overlap ok] Ord DefaultScore
instance [overlap ok] Eq DefaultScore
instance [overlap ok] Random F18Word
instance [overlap ok] Monoid DefaultScore
instance [overlap ok] Show DefaultScore
instance [overlap ok] Score DefaultScore


-- | This module defines a type representing the location of a core in the
--   8 × 18 grid.
--   
--   All of the actually interesting code is in the typeclass instances.
module Language.ArrayForth.Core

-- | The address of a core. There are 144 cores in an 8 × 18 array. The
--   address has the row number followed by the column number.
--   
--   As a string, the core addresses are displayed as a single three-digit
--   number, just like in the GreenArray documentation. So <tt>Core 7
--   17</tt> becomes <tt>"717"</tt>.
--   
--   Core addresses behave like numbers: you can use numeric literals and
--   add them together. For example, <tt>[0..] :: [Core]</tt> gets you the
--   list of all the core addresses. <tt>(move core = core + Core 1 1)</tt>
--   is a function that moves you up and over by one core.
data Core
Core :: !(ℤ / 8) -> !(ℤ / 18) -> Core

-- | Returns all the neighbors of a core. Most cores have four neighbors;
--   the ones along the edges only have three and the ones at the corners
--   two.
--   
--   They always come in the order right, down, left up, with Nothing in
--   place of non-existant cores.
neighbors :: Core -> [Maybe Core]
instance Ord Core
instance Eq Core
instance Num Core
instance Bounded Core
instance Enum Core
instance Show Core