diff options
| -rw-r--r-- | Readme.md | 50 | ||||
| -rw-r--r-- | turinglog.icl | 38 |
2 files changed, 82 insertions, 6 deletions
@@ -5,6 +5,7 @@ Turing machines implementation in [Clean](http://wiki.clean.cs.ru.nl/Clean). Fea * Straightforward types for turing machines and their states * Running and stepping a turing machine in execution * Simple `toString` instances for easy display of the types + * A `turinglog` program as an example and to be used to get a trace of the execution of a machine Read further for examples. @@ -18,16 +19,16 @@ This program and the example are distributed under the MIT license. For more det Provides two general classes: - class step a :: a -> a - class rewind a :: a -> a + class step a :: !a -> a + class rewind a :: !a -> a Both are meant to be instantiated by types that can be 'stepped'. For example, the TuringMachineState instantiates the `step` class to be able to compute the next state for a current state. The `rewind` class is currently unused, but it only made sense to include it and make this a separate module. It allows a type to step backwards. Note, that for a Turing machine it is impossible to instantiate this class, because the transition function need not have an inverse. There are three derivative functions: - stepn :: Int a -> a | step a - rewindn :: Int a -> a | rewind a - stepOrRewindn :: Int a -> a | step, rewind a + stepn :: Int !a -> a | step a + rewindn :: Int !a -> a | rewind a + stepOrRewindn :: Int !a -> a | step, rewind a The first and second simply iterate `step` and `rewind`. Negative values for the first argument will never terminate. The latter function will evaluate to either `rewindn` or `stepn`, depending on the sign of the first argument. @@ -73,7 +74,7 @@ The following is a simple machine to replace `a` with `b` and vice versa. It is  - replace :: TuringMachine Char Char + replace :: TuringMachine Char replace = { alphabet = ['a','b'], inputs = ['a','b'], transition = f } @@ -123,6 +124,43 @@ As you can see, the machine definition is in no way represented by this function Blanks (`Nothing` on the tape) are represented with 'B'. +## Using `turinglog` + +`turinglog` is a simple implementation of the library and can be used to get a trace of the execution of a machine. + +Compile with: + + clm -I /opt/clean/lib/StdLib turinglog -o turinglog + +Replace `/opt/clean/lib/StdLib` with the appropriate path. + +Run with: + + ./turinglog + +Example output: + + [q0]BabbabaB (Running) + B[q1]abbabaB (Running) + Bb[q1]bbabaB (Running) + Bba[q1]babaB (Running) + Bbaa[q1]abaB (Running) + Bbaab[q1]baB (Running) + Bbaaba[q1]aB (Running) + Bbaabab[q1]B (Running) + Bbaaba[q2]bB (Running) + Bbaab[q2]abB (Running) + Bbaa[q2]babB (Running) + Bba[q2]ababB (Running) + Bb[q2]aababB (Running) + B[q2]baababB (Running) + [q2]BbaababB (Running) + [q2]BbaababB (Normally terminated) + +As you can see, for each iteration the state is outputted. + +This example is using the `replace` machine of above and using the input `abbaba`. This is also the values in `turinglog` at the moment. Replace the machine and the tape as needed. + ## Future ideas * It would be really cool to have some kind of graphical frontend and a possibility to step through the machine with some input diff --git a/turinglog.icl b/turinglog.icl new file mode 100644 index 0000000..273c70b --- /dev/null +++ b/turinglog.icl @@ -0,0 +1,38 @@ +module turinglog + +import StdEnv +import TuringMachines + +Start :: *World -> *World +Start w +# (io,w) = stdio w +# m = initTuringMachine machine tape +# io = fwrites (toString m +++ "\n") io +# io = loop m io +# (ok,w) = fclose io w +| not ok = abort "Couldn't close stdio\n" +| otherwise = w +where + loop m f + # m = step m + # f = fwrites (toString m +++ "\n") f + | m.running == Running = loop m f + | otherwise = f + +tape :: Tape Char +tape = [Just c \\ c <- fromString "abbaba"] + +machine :: TuringMachine Char +machine = { alphabet = ['a', 'b'], + inputs = ['a', 'b'], + transition = f } +where + f :: Int (Maybe Char) -> TuringMachineMove Char + f 0 Nothing = Step 1 Nothing Right + f 1 Nothing = Step 2 Nothing Left + f 1 (Just 'a') = Step 1 (Just 'b') Right + f 1 (Just 'b') = Step 1 (Just 'a') Right + f 2 (Just 'a') = Step 2 (Just 'a') Left + f 2 (Just 'b') = Step 2 (Just 'b') Left + f _ _ = Halt + |