Haskell的Brainfuck译员

Question

我在codewar中做了一个与Haskell相关的问题，这个问题是为着名的神秘语言Brainfuck写一个解释器。

最初，我正在考虑使用Array来编写程序。在我开始实施解释器之后，立即意识到解释器的效率会很低，因为阵列有很多变化。然后我开始使用STArray。但除了保存一组数据指针外，我还需要输出String的可变引用，这在STArray中是不可能的。所以我完全惊呆了。

写一个monadic解析器可能是一个好主意，我当时想。但事实证明，我不知道我应该用什么样的表情来模拟问题。我只阅读了一些关于monadic解析风格的论文，仅此而已。 Brainfuck比天真Add和Minus等复杂得多

任何指导解决这个问题，表示赞赏。以下是我的代码。我只是在这里发布它来显示代码是多么混乱。不要试图编译它，因为它充满了类型错误。

executeString' :: String -> String -> Maybe String 
executeString' []  _  = Just "" 
executeString' "," _  = Nothing 
-- executeString' source input = Just $ map chr $ elems $ consume 

length' ::String -> Int 
length' source = right - left 
    where step (l, r) '>' = (l, r+1) 
      step (l, r) '<' = (l+1, r) 
      (left, right) = foldl' step (0, 0) source 

-- decrement the data pointer 
neverMinus :: Int -> Int 
neverMinus n = if n == 0 then 255 else n - 1 

-- increment the data pointer 
alwaysPlus :: Int -> Int 
alwaysPlus n = if n == 255 then 0 else n + 1 

consume :: String -> String -> (Array Int Int, Array Int Char) 
consume source input = runSTArray $ do 
     pointer <- newArray (0, arrlength') 0 
     forM_ source $ \t -> do 
      pointed <- readArray pointer point 
      elem <- readArray pointer pointed 
      isWrong <- readArray pointer error 
      status' <- readArray pointer status 
      when (1 == isWrong) $ return 0 
      when (doJump status') $ return 0 
      case t of 
       '>' -> writeArray pointer point (pointed + 1) 
       '<' -> writeArray pointer point (pointed - 1) 
       '+' -> writeArray pointer pointed (alwaysPlus elem) 
       '-' -> writeArray pointer pointed (neverMinus elem) 
       ',' -> do index <- readArray pointer inputIndex 
          writeArray pointer pointed (ord $ 
           head . drop index input) 
          writeArray pointer inputIndex (index+1) 
          1 
       '[' -> writeArray pointer status jump 
       ']' -> writeArray pointer status execute 
     return pointer 
    where arrlength' = length'' + 4 
      length'' = length' source 
      strlength' = 1 + foldl' (\count s -> case s of 
               '.' -> count + 1) 0 source 
      point  = length'' + 1 
      inputIndex = length'' + 2 
      status  = length'' + 3 -- should the program execute current instruction or jump 
      error  = length'' + 4 -- if there is program error during execution 

-- Program status 
jump = 1 
execute = 0 

doJump :: Int -> Bool 
doJump jump = True 
duJump execute = False 

Answer 1

使用haskell这样的语言编写brainfuck解释器的一些技巧。

最初，我正在考虑使用Array编写程序。在我开始实施解释器之后，立即意识到解释器的效率会很低，因为阵列有很多变化。然后我转而使用STArray。但除了保存数据指针数组之外，我还需要一个可变参考用于输出String，这在STArray中是不可能的。所以我完全惊呆了。

研究约List Zippers。这是一个可以定义的数据结构 - > [主元左边] {枢轴元素} [主元右边]，代码看起来像。

`data Tape a = Tape [a] a [a]` 

与您可以轻松地>，<，+，-等定义这个数据类型。

写一个monadic解析器可能是一个好主意，我想那么。但事实证明，我不知道我应该用什么样的表情来模拟问题。我只阅读了一些关于monadic解析风格的论文，仅此而已。 Brainfuck比天真的Add和Minus等复杂得多。

这不是真的，Brainfuck不如一个典型的算术分析器复杂。正如其中一条评论所指出的那样。即类似以下的内容会让你走上正轨。

stripComments = filter (`elem` "+-<>[],.")

```

token :: Parser Token 
token = const TRight <$> char '>' 
    <|> const TLeft <$> char '<' 
    <|> const TInc <$> char '+' 
    <|> const TDec <$> char '-' 
    <|> const TPrint <$> char ',' 
    <|> const TRead <$> char '.' 
    <|> const TLoopS <$> char '[' 
    <|> const TLoopE <$> char ']' 

```

最后，你需要评估的策略，我会用像对下面。 eval :: String -> Tape Token -> Tape Int -> String 其中第一个参数是程序的输入，Tape Token是解析的程序，Tape Int是磁​​带上的操纵值，您将在其上应用值，最后一个参数是输出。

我相信这应该有助于您走上正确的轨道。

我曾经写过类似的东西https://gist.github.com/sherubthakur/16a784e61efbe54d885ad60c6e18f254。