Commits

David Lazar committed efe9ae8

Add and improve documentation.

Comments (0)

Files changed (3)

src/Language/PCPL.hs

 import Language.PCPL.Solver
 import Language.PCPL.CompileTM
 
--- ^ Run a PCPL program on the given input, producing a PCP match.
+-- | Run a PCPL program on the given input, producing a PCP match.
 runProgram :: Program -> Input -> [Domino]
 runProgram pgm w = map (dss !!) indices
   where
     Just initialConfig = updateConf (Top []) d
     indices = reverse $ search (zip [1..] ds) [Node [0] initialConfig]
 
+-- | Return the string across the top of a list of Dominos.
+-- Useful after finding a match.
 topString :: [Domino] -> String
 topString ds = concat [ s | Domino xs _ <- ds, Symbol s <- xs]
 
+-- | Turing machine that adds unary numbers.
+-- For example: @1+11@ becomes @111@.
 unaryAdder :: TuringMachine
 unaryAdder = TuringMachine
     { startState = "x"
         ]
     }
 
+
+-- | Turing machine that accepts strings of balanced parentheses.
+-- Note: due to the restrictions described in 'compileTM', the input must
+-- start with a @$@ symbol. For example: the input @$(())()@ is accepted.
+-- This Turing machine is based on:
+-- <http://www2.lns.mit.edu/~dsw/turing/examples/paren.tm>.
 parensMatcher :: TuringMachine
 parensMatcher = TuringMachine
     { startState = "S"

src/Language/PCPL/CompileTM.hs

--- | This module implements the translation from Turing machines to PCP
--- described in Sipser's /Theory of Computation/.
+-- | This module implements the Turing machine to PCP(L) compiler described in
+-- Michael Sipser's textbook /Introduction to the Theory of Computation/,
+-- second edition, section 5.2.
 module Language.PCPL.CompileTM
     ( compileTM
     , compileTM'
 -- | Symbol used to separate TM configurations
 type Seperator = Symbol
 
+-- | Compile a Turing machine into an equivalent PCPL program.
+-- This function assumes that the Turing machine never attempts to move its
+-- head left of the starting position. Any Turing machine can be converted
+-- into one that satisfies this assumption.
 compileTM :: TuringMachine -> Program
 compileTM = compileTM' (Symbol "#")
 
+-- | Like 'compileTM', but can specify a 'Seperator' symbol.
+--
+-- > compileTM = compileTM' (Symbol "#")
+--
 compileTM' :: Seperator -> TuringMachine -> Program
 compileTM' s tm = Program
     { startDomino = part1 s tm

src/Language/PCPL/Syntax.hs

 
 import Language.UTM.Syntax
 
+-- | PCPL program
 data Program = Program
     { startDomino :: Input -> Domino
     , dominos     :: [Domino]