An implementation of Lawrence S. Moss' 1#
language and Text
Register Machine (http://www.indiana.edu/~iulg/trm/).
This module also includes a slightly higher-level language, 1#L
,
that replaces the forward and backward relative jumps of 1#
with
labels and goto instructions.
- data Letter
- newtype Word = W [Letter]
- wordToString :: Word -> String
- newtype Register = R Int
- data Instruction
- instructionToString :: Instruction -> String
- type Program = Vector Instruction
- programToString :: Program -> String
- parseProgram :: Word -> Maybe Program
- data Machine = M {}
- step :: Machine -> Either Machine Machine
- run :: Program -> Map Register Word -> Map Register Word
- phi :: Word -> [(Register, Word)] -> Maybe Word
- type Label = Int
- data LInstruction
- type LProgram = Vector LInstruction
- toLabeledProgram :: Program -> LProgram
- fromLabeledProgram :: LProgram -> Program
- class LSymantics repr where
- newtype LComp a = LC {}
- compileL :: LComp () -> LProgram
- runL :: LComp () -> [(Register, Word)] -> Maybe Word
- runL' :: LComp () -> [(Register, Word)] -> [(Register, Word)]
- do_ :: (LComp () -> LComp () -> LComp ()) -> LComp ()
- freshLabelHere :: (Monad repr, LSymantics repr) => repr Label
- encodeBB :: Integral a => a -> Word
- decodeBB :: Num a => Word -> a
Basic Text Register Machine
Letters and Words
Registers, Instructions, and Programs
Register identifiers.
data Instruction Source
Abstract syntax for the primitive 1#
instructions.
instructionToString :: Instruction -> StringSource
Convert an Instruction
to concrete syntax.
type Program = Vector InstructionSource
A 1#
program is a Vector
of Instruction
s.
programToString :: Program -> StringSource
Convert a Program
to concrete syntax.
parseProgram :: Word -> Maybe ProgramSource
Machine Implementation
step :: Machine -> Either Machine MachineSource
Performs the single Instruction
indicated by the program
counter, if available. Returns 'Left mach' if a step cannot be
performed, and 'Right mach' with an updated Machine
otherwise.
run :: Program -> Map Register Word -> Map Register WordSource
Given a Program
and the initial state of the registers, return
the final state of the registers.
phi :: Word -> [(Register, Word)] -> Maybe WordSource
Wrapper around run
that parses the given Word
into a
Program
, and then runs it in the given register state. Returns
the value in register 1 once the program halts.
Returns Nothing
when either the given Word
fails to parse, or
if the machine halts abnormally with an invalid program counter or
values in registers other than register 1.
Labels and Gotos
Language Definition
data LInstruction Source
Abstract syntax for a variant of 1#
, 1#L
with labels and
gotos instead of forward and backward jumps.
type LProgram = Vector LInstructionSource
A 1#L
program is a Vector
of LInstruction
s.
Conversion Between Languages
fromLabeledProgram :: LProgram -> ProgramSource
Convert a 1#L
LProgram
into a semantically-equivalent 1#
Program
. May fail with an error if the LProgram
contains
duplicate labels, jumps to undefined labels. An error will also
occur if the LProgram
contains a goto that would translate into a
jump of 0 instructions, as this is impossible to express in 1#
.
Concrete Syntax and Semantics
class LSymantics repr whereSource
Concrete syntax for 1#L
, indexed by backend representation in
the typed tagless style
(http://okmij.org/ftp/tagless-final/index.html).
snocOne :: Register -> repr ()Source
Append a 1
to the end of the given Register
.
snocHash :: Register -> repr ()Source
Append a #
to the end of the given Register
.
freshLabel :: repr LabelSource
label :: Label -> repr ()Source
Place a Label
at the given point in the program. Note that a
particular Label
may be used only once per program.
goto :: Label -> repr ()Source
Unconditional jump to the given Label
.
The default backend for LSymantics
.
Useful helpers
do_ :: (LComp () -> LComp () -> LComp ()) -> LComp ()Source
A combinator to cleanly implement looping structures in LComp
code.
Takes a function that expects two arguments, continue
and
break
. The body of the function is a block of LComp
code that
gets repeated whenever continue
is run. If break
is run,
control jumps to the instruction after the call to do_
.
freshLabelHere :: (Monad repr, LSymantics repr) => repr LabelSource
Convenience function to create a fresh label and place it at the current position.