Interpreter für Brainfuck in Haskell

Question

Ich mache ein Haskell-Problem in codewar, das ist ein Interpreter für Brainfuck, die berühmte esoterische Sprache zu schreiben.

Zunächst dachte ich an das Programm mit Array zu schreiben. Unmittelbar nachdem ich mit der Implementierung des Interpreters begonnen hatte, wurde mir klar, wie ineffizient der Interpreter sein würde, weil es viele Änderungen am Array gibt. Dann wechselte ich zu STArray. Aber abgesehen von einem Array von Datenzeigern benötige ich auch eine veränderbare Referenz für den Ausgang String, die in STArray unmöglich ist. Ich war total verblüfft.

Einen monadischen Parser schreiben könnte eine gute Idee sein, dachte ich dann. Aber es stellt sich heraus, dass ich nicht weiß, welche Ausdrücke ich verwenden sollte, um das Problem zu modellieren. Ich lese nur ein paar Artikel über den monadischen Parsing-Stil und das ist alles. Brainfuck ist viel komplizierter als naiv Add und Minus, etc.

Jede Anleitung zur Lösung des Problems wird geschätzt. Unten ist mein Code. Ich poste es hier nur, um zu zeigen, wie unordentlich der Code ist. Versuchen Sie nicht, es zu kompilieren, da es voller Typfehler ist.

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

Einige Tipps, um Brainfuck Interpreter in einer Sprache wie Haskell zu schreiben.

Zunächst dachte ich an das Programm mit Array zu schreiben. Unmittelbar nachdem ich mit der Implementierung des Interpreters begonnen hatte, wurde mir klar, wie ineffizient der Interpreter sein würde, weil es viele Änderungen am Array gibt. Dann wechselte ich zu STArray. Aber abgesehen davon, dass ich ein Array von Datenzeigern halte, brauche ich auch eine veränderbare Referenz für die Ausgabezeichenfolge, was in STArray unmöglich ist. Ich war total verblüfft.

Studie über List Zippers. Es ist eine Datenstruktur, die definiert werden kann -> [Links vom Pivot-Element] {Pivot-Element} [Rechts vom Pivot-Element], die im Code aussieht.

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

mit, dass man >, <, +, - usw. auf diesem Datentyp leicht definieren.

einen monadischen Parser schreiben könnte eine gute Idee sein, dachte ich dann. Aber es stellt sich heraus, dass ich nicht weiß, welche Ausdrücke ich verwenden sollte, um das Problem zu modellieren. Ich lese nur ein paar Artikel über den monadischen Parsing-Stil und das ist alles. Brainfuck ist viel komplizierter als naive Add und Minus usw.

Das ist nicht wahr, Brainfuck ist eher weniger komplex als ein typischer arithmetischer Parser. wie in einem der Kommentare ausgeführt. Das Folgende sollte Sie auf den richtigen Weg bringen.

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 ']' 

` ``

Schließlich werden Sie eine Evaluierungsstrategie benötigen, würde ich so etwas wie die folgenden dafür. eval :: String -> Tape Token -> Tape Int -> String wobei 1st Argument ist die Eingabe in das Programm, Tape Token wäre das geparste Programm, Tape Int wäre die manipulierten Werte auf dem Band, auf dem Sie die Werte anwenden und das letzte Argument wäre die Ausgabe.

Ich glaube, das sollte Ihnen helfen, auf dem richtigen Weg zu gehen.

Ich habe einmal etwas ähnliches geschrieben https://gist.github.com/sherubthakur/16a784e61efbe54d885ad60c6e18f254.