David Lazar avatar David Lazar committed 37e1dd3

Import utm.

Comments (0)

Files changed (5)

+Copyright (c) 2012 David Lazar <lazar6@illinois.edu>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+# About
+
+This is an implementation of Turing machines in Haskell.
+Currently, this package only provides an abstract syntax for Turing machines.
+Concrete syntax and an interpreter will be added later.
+
+# Contributing
+
+This project is available on [GitHub](https://github.com/davidlazar/utm) and [Bitbucket](https://bitbucket.org/davidlazar/utm/). You may contribute changes using either.
+
+Please report bugs and feature requests using the [GitHub issue tracker](https://github.com/davidlazar/utm/issues).
+import Distribution.Simple
+main = defaultMain

src/Language/UTM/Syntax.hs

+{-# LANGUAGE GeneralizedNewtypeDeriving #-}
+module Language.UTM.Syntax where
+
+import Data.Map (Map)
+import Data.String
+
+data TuringMachine = TuringMachine
+    { startState :: State
+    , acceptState :: State
+    , rejectState :: State
+    , blankSymbol :: Symbol
+    , inputAlphabet :: [Symbol]
+    , transitionFunction :: TransitionFunction
+    } deriving (Eq, Show)
+
+tapeAlphabet :: TuringMachine -> [Symbol]
+tapeAlphabet tm = blankSymbol tm : inputAlphabet tm
+
+type TransitionFunction = Map (State, Symbol) (State, Symbol, Action)
+
+data Action
+    = L -- ^ move head to the left
+    | R -- ^ move head to the right
+    deriving (Eq, Ord, Show)
+
+data Tape = Tape [Symbol] Symbol [Symbol]
+    deriving (Eq, Show)
+
+data Configuration = Configuration State Tape
+    deriving (Eq, Show)
+
+-- | <https://en.wikipedia.org/wiki/Computation_history>
+type ComputationHistory = [Configuration]
+
+type Input = [Symbol]
+
+newtype State = State String
+    deriving (Eq, Ord, Show, IsString)
+
+newtype Symbol = Symbol String
+    deriving (Eq, Ord, Show, IsString)
+
+syms :: String -> [Symbol]
+syms = map (Symbol . return)
+
+unsyms :: [Symbol] -> String
+unsyms = concatMap (\(Symbol s) -> s)
+Name:               utm
+Version:            0.1.0
+Synopsis:           Universal Turing Machine
+Homepage:           https://github.com/davidlazar/utm
+License:            MIT
+License-file:       LICENSE
+Author:             David Lazar
+Maintainer:         David Lazar <lazar6@illinois.edu>
+Category:           Language
+Build-type:         Simple
+Cabal-version:      >=1.6
+
+Extra-source-files:
+    README.md
+
+source-repository head
+  Type:             git
+  Location:         https://github.com/davidlazar/utm
+
+Library
+  ghc-options:      -Wall
+
+  Hs-source-dirs:   src
+
+  Exposed-modules:
+    Language.UTM.Syntax
+
+  Build-depends:
+    base >= 4 && < 5,
+    containers
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.