Переводчик Brainfuck в Хаскелл

Question

Я делаю связанную с Haskell проблему в Codewar, которая заключается в написании интерпретатора для Brainfuck, известного эзотерического языка.

Первоначально я думал о написании программы с использованием Array, Сразу после того, как я начал реализовывать интерпретатор, я понял, насколько неэффективным будет интерпретатор, потому что в массиве много изменений. Затем я перешел на использование STArray, Но помимо хранения массива указателей данных, мне также нужна изменяемая ссылка для вывода Stringчто невозможно в STArray, Так что я был совершенно ошеломлен.

Я подумал тогда, что написание монадического парсера может быть хорошей идеей. Но оказывается, что я не знаю, какие выражения мне следует использовать для моделирования проблемы. Я только прочитал несколько статей о монадическом стиле синтаксического анализа, и это все. 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

Несколько советов по написанию интерпретатора Brainfuck на таком языке, как Haskell.

Изначально я думал о написании программы с использованием Array. Сразу после того, как я начал реализовывать интерпретатор, я понял, насколько неэффективным будет интерпретатор, потому что в массиве много изменений. Затем я переключился на использование STArray. Но помимо хранения массива указателей данных, мне также нужна изменяемая ссылка для выходной строки, что невозможно в STArray. Так что я был совершенно ошеломлен.

Изучите Список Застежек-Молний. Это структура данных, которую можно определить -> [Слева от элемента сводки] {Элемент сводки} [Справа от элемента сводки], которая в коде выглядит следующим образом.

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

с этим вы можете легко определить >, <, +, - и т. д. для этого типа данных.

Я подумал тогда, что написание монадического парсера может быть хорошей идеей. Но оказывается, что я не знаю, какие выражения мне следует использовать для моделирования проблемы. Я только прочитал несколько статей о монадическом стиле синтаксического анализа, и это все. Brainfuck гораздо сложнее, чем наивный Адд и Минус и т. Д.

Это неправда, 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 где 1-й аргумент является входом в программу, Tape Token будет разобранная программа, Tape Int будет манипулировать значениями на ленте, к которой вы будете применять значения, а последним аргументом будет вывод.

Я считаю, что это должно помочь вам встать на правильный путь.

Однажды я написал нечто подобное https://gist.github.com/sherubthakur/16a784e61efbe54d885ad60c6e18f254.