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


-- | A Haskell implementation of the 1# Text Register Machine
--   
--   An implementation of Lawrence S. Moss' <tt>1#</tt> language and Text
--   Register Machine (<a>http://www.indiana.edu/~iulg/trm/</a>).
@package text-register-machine
@version 0.2.0


-- | An implementation of Lawrence S. Moss' <tt>1#</tt> language and Text
--   Register Machine (<a>http://www.indiana.edu/~iulg/trm/</a>).
--   
--   This module also includes a slightly higher-level language,
--   <tt>1#L</tt>, that replaces the forward and backward relative jumps of
--   <tt>1#</tt> with labels and goto instructions.
module Language.TRM

-- | Typed representation of the <tt>1#</tt> letters.
data Letter
One :: Letter
Hash :: Letter

-- | A wrapper around a list of <a>Letter</a>s with an <a>IsString</a>
--   instance, so that literal strings of <tt>1</tt>s, <tt>#</tt>s, and
--   whitespace can be used instead of lists of <a>One</a>s and
--   <a>Hash</a>es. This requires the <tt>-XOverloadedStrings</tt> flag.
--   
--   <pre>
--   loop :: Word
--   loop = "1### 11####"
--   </pre>
newtype Word
W :: [Letter] -> Word

-- | Convert a <a>Word</a> back into a <a>String</a>.
wordToString :: Word -> String

-- | Register identifiers.
newtype Register
R :: Int -> Register

-- | Abstract syntax for the primitive <tt>1#</tt> instructions.
data Instruction
SnocOne :: Register -> Instruction
SnocHash :: Register -> Instruction
Forward :: Int -> Instruction
Backward :: Int -> Instruction
Case :: Register -> Instruction

-- | Convert an <a>Instruction</a> to concrete syntax.
instructionToString :: Instruction -> String

-- | A <tt>1#</tt> program is a <a>Vector</a> of <a>Instruction</a>s.
type Program = Vector Instruction

-- | Convert a <a>Program</a> to concrete syntax.
programToString :: Program -> String

-- | Parse a <a>Word</a> into a <a>Program</a>; returns <a>Nothing</a> if
--   an invalid instruction is found.
parseProgram :: Word -> Maybe Program

-- | A <a>Machine</a> consists of a <a>Program</a>, a program counter, and
--   a <a>Map</a> from registers to the words they contain.
data Machine
M :: Program -> Int -> Map Register Word -> Machine
program :: Machine -> Program
pc :: Machine -> Int
regs :: Machine -> Map Register Word

-- | Performs the single <a>Instruction</a> indicated by the program
--   counter, if available. Returns 'Left mach' if a step cannot be
--   performed, and 'Right mach' with an updated <a>Machine</a> otherwise.
step :: Machine -> Either Machine Machine

-- | Given a <a>Program</a> and the initial state of the registers, return
--   the final state of the registers.
run :: Program -> Map Register Word -> Map Register Word

-- | Wrapper around <a>run</a> that parses the given <a>Word</a> into a
--   <a>Program</a>, and then runs it in the given register state. Returns
--   the value in register 1 once the program halts.
--   
--   Returns <a>Nothing</a> when either the given <a>Word</a> fails to
--   parse, or if the machine halts abnormally with an invalid program
--   counter or values in registers other than register 1.
phi :: Word -> [(Register, Word)] -> Maybe Word

-- | Label representation.
type Label = Int

-- | Abstract syntax for a variant of <tt>1#</tt>, <tt>1#L</tt> with labels
--   and gotos instead of forward and backward jumps.
data LInstruction
LSnocOne :: Register -> LInstruction
LSnocHash :: Register -> LInstruction
LCase :: Register -> LInstruction
LGoto :: Label -> LInstruction
LLabel :: Label -> LInstruction

-- | A <tt>1#L</tt> program is a <a>Vector</a> of <a>LInstruction</a>s.
type LProgram = Vector LInstruction

-- | Convert a <tt>1#</tt> <a>Program</a> into a semantically-equivalent
--   <tt>1#L</tt> <a>LProgram</a>. May fail with an error if the original
--   <a>Program</a> is <i>non-tidy</i>, that is it contains forward or
--   backward jumps to instructions outside of the program.
toLabeledProgram :: Program -> LProgram

-- | Convert a <tt>1#L</tt> <a>LProgram</a> into a semantically-equivalent
--   <tt>1#</tt> <a>Program</a>. May fail with an error if the
--   <a>LProgram</a> contains duplicate labels, jumps to undefined labels.
--   An error will also occur if the <a>LProgram</a> contains a goto that
--   would translate into a jump of 0 instructions, as this is impossible
--   to express in <tt>1#</tt>.
fromLabeledProgram :: LProgram -> Program

-- | Concrete syntax for <tt>1#L</tt>, indexed by backend representation in
--   the typed tagless style
--   (<a>http://okmij.org/ftp/tagless-final/index.html</a>).
class LSymantics repr
snocOne :: LSymantics repr => Register -> repr ()
snocHash :: LSymantics repr => Register -> repr ()
freshLabel :: LSymantics repr => repr Label
label :: LSymantics repr => Label -> repr ()
goto :: LSymantics repr => Label -> repr ()
cond :: LSymantics repr => Register -> repr () -> repr () -> repr () -> repr ()

-- | The default backend for <a>LSymantics</a>.
newtype LComp a
LC :: StateT (Int, Set Label) (Writer LProgram) a -> LComp a
unLC :: LComp a -> StateT (Int, Set Label) (Writer LProgram) a

-- | Compiles an <a>LComp</a> program into an <a>LProgram</a>.
compileL :: LComp () -> LProgram

-- | Given an <a>LComp</a> program and an initial register state, and then
--   runs it in the given register state. May return <a>Nothing</a> if the
--   program does not halt cleanly, as with <a>run</a>.
runL :: LComp () -> [(Register, Word)] -> Maybe Word

-- | A combinator to cleanly implement looping structures in <a>LComp</a>
--   code.
--   
--   Takes a function that expects two arguments, <tt>continue</tt> and
--   <tt>break</tt>. The body of the function is a block of <a>LComp</a>
--   code that gets repeated whenever <tt>continue</tt> is run. If
--   <tt>break</tt> is run, control jumps to the instruction after the call
--   to <a>do_</a>.
do_ :: (LComp () -> LComp () -> LComp ()) -> LComp ()

-- | Convenience function to create a fresh label and place it at the
--   current position.
freshLabelHere :: (Monad repr, LSymantics repr) => repr Label

-- | Encodes an <a>Integral</a> type into a <a>Word</a> of backwards-binary
--   digits using <tt>1</tt>s and <tt>#</tt>s for <tt>1</tt>s and
--   <tt>0</tt>s, respectively. Note that the representation of zero is a
--   single <tt>#</tt> rather than the empty <a>Word</a>.
encodeBB :: Integral a => a -> Word

-- | Decodes a <a>Word</a> containing backwards-binary digits into a
--   <a>Num</a> type. Fails with an error if the <a>Word</a> is empty.
decodeBB :: Num a => Word -> a
clear :: Register -> LComp ()
move :: Register -> Register -> LComp ()
copy :: Register -> Register -> Register -> LComp ()
succBB :: Register -> Register -> LComp ()

-- | Yields the successor of the backwards-binary number in register 1.
--   
--   <pre>
--   *Language.TRM&gt; decodeBB &lt;$&gt; phi succBB [(1, encodeBB 0)]
--   Just 1
--   *Language.TRM&gt; decodeBB &lt;$&gt; phi succBB [(1, encodeBB 119)]
--   Just 120
--   </pre>
succBB' :: Word

-- | Yields the sum of two backwards-binary numbers in registers 1 and 2.
--   
--   <pre>
--   *Language.TRM&gt; decodeBB &lt;$&gt; phi plusBB [(1, encodeBB 2), (2, encodeBB 3)]
--   Just 5
--   *Language.TRM&gt; decodeBB &lt;$&gt; phi plusBB [(1, encodeBB 100), (2, encodeBB 20)]
--   Just 120
--   </pre>
plusBB' :: Word
instance Eq Letter
instance Eq Word
instance Monoid Word
instance Eq Register
instance Ord Register
instance Show Register
instance Enum Register
instance Real Register
instance Integral Register
instance Num Register
instance Eq Instruction
instance Show Instruction
instance Eq Machine
instance Show Machine
instance Eq LInstruction
instance Show LInstruction
instance Functor LComp
instance Applicative LComp
instance Monad LComp
instance MonadFix LComp
instance MonadState (Int, Set Label) LComp
instance MonadWriter LProgram LComp
instance LSymantics LComp
instance Show Word
instance IsString Word