Haskell的Charmander Brainfuck译员

我刚开始学习Haskell，这是我的第一个大项目（即不是阶乘，斐波那契或绘图员）。这是对某人的礼物，因此语言略有不同。该程序可以运行，但是我认为代码的某些部分可以改进，特别是：Vector是在程序状态记录Program中表示当前内存状态的最佳选择吗？ br />我通过将源代码分成单词列表（代码状态），然后递归地遍历列表并在每次循环中对其进行执行，来执行程序。有更好的方法吗？
我通过将当前代码状态放入名为parse的堆栈中，并在需要时使用它来“回到过去”来创建循环。有没有更好的方法呢？
我只是觉得处理循环的方式不雅；例如loopback。
我是否正确使用了防护和模式匹配？
一般来说会令人困惑吗？

我认为自己是初学者中级程序员，刚刚学习过monad。 br />
文档

Char: Previous 1
Char-char: Next 1
Cha: Input
Charmander: Output
Cha-cha: Minus 1
Charmander-charmander: Plus 1
Charmander-char: Loop start; if data at DP is 0, jump to corresponding Cha-charmander-char.
Cha-charmander-char: Loop end; if data at DP is not 0, jump to corresponding Charmander-char.

DP: Data Pointer, starts at 0. Points to an integer in memory.
Memory: A tape of 128 integers.

Main.hs

module Main
(
    main
) where

import Data.Vector (Vector, replicate, (//), (!), accum)
import Data.Char (ord, chr, toLower)
import System.Environment (getArgs)
import System.IO (IOMode(ReadMode), BufferMode(NoBuffering), openFile, hGetContents, hSetBuffering, stdin)

-- Program state

type DP = Integer
type Memory = Vector Integer
type Code = [String]

data Program = Program {
    dp :: DP,
    memory :: Memory,
    code :: Code,
    loopback :: [Code]
} deriving Show

initial :: Code -> Program
initial code = Program {
    dp = 0,
    memory = Data.Vector.replicate 128 0,
    code = code,
    loopback = []
}

-- Microcommands

next :: Program -> Program
next program = program {
    code = tail $ code program
}

move :: Integer -> Program -> Program
move num program = program {
    dp = dp program + num
}

change :: Integer -> Program -> Program
change num program = program {
    memory = accum (+) (memory program) [(fromInteger $ dp program, num)]
}

toChaCharmanderChar' :: Integer -> Program -> Program
toChaCharmanderChar' depth program
    | depth == 0 && current == "cha-charmander-char" = program
    | current == "cha-charmander-char" = toChaCharmanderChar' (depth - 1) $ next program
    | current == "charmander-char" = toChaCharmanderChar' (depth + 1) $ next program
    | otherwise = toChaCharmanderChar' depth $ next program
    where current = head $ code program

toChaCharmanderChar :: Program -> Program
toChaCharmanderChar = toChaCharmanderChar' 0

-- Commands

char :: Program -> IO Program
char program = return $ move (-1) program

charChar :: Program -> IO Program
charChar program = return $ move 1 program

chaCha :: Program -> IO Program
chaCha program = return $ change (-1) program

charmanderCharmander :: Program -> IO Program
charmanderCharmander program = return $ change 1 program

cha :: Program -> IO Program
cha program = do
    input <- getChar
    return program {
        memory = (memory program) // [(fromInteger $ dp program, toInteger $ ord input)]
    }

charmander :: Program -> IO Program
charmander program = do
    putStr [chr $ fromInteger $ (memory program) ! (fromInteger $ dp program)]
    return program

charmanderChar :: Program -> IO Program
charmanderChar program
    | num == 0 = return $ toChaCharmanderChar $ next program
    | num /= 0 = return program {
        loopback = code program : loopback program
    }
    where num = memory program ! (fromInteger $ dp program)

chaCharmanderChar :: Program -> IO Program
chaCharmanderChar program
    | num == 0 = return program {
        loopback = tail $ loopback program
    }
    | num /= 0 = return program {
        code = head $ loopback program
    }
    where num = memory program ! (fromInteger $ dp program)

unknown :: Program -> IO Program
unknown program = return program

-- Parser

parse :: String -> Program -> IO Program
parse "char" = char
parse "char-char" = charChar
parse "cha" = cha
parse "charmander" = charmander
parse "cha-cha" = chaCha
parse "charmander-charmander" = charmanderCharmander
parse "charmander-char" = charmanderChar
parse "cha-charmander-char" = chaCharmanderChar
parse _ = unknown

-- Interpreter

interpret' :: Program -> IO ()
interpret' program
    | code' == [] = do
        putStrLn "\nCore dump: "
        print program
        putStrLn "\nCha char charmander (0)."
    | otherwise = do
        newProgram <- parse (head code') program
        interpret' $ next newProgram
    where code' = code program

interpret :: String -> IO ()
interpret program = interpret' $ initial $ words $ fmap toLower program

-- Main

main :: IO ()
main = do
    hSetBuffering stdin NoBuffering

    args <- getArgs
    if null args
        then
            putStrLn "Cha charmander (-1)."
        else do
            handle <- openFile (head args) ReadMode
            contents <- hGetContents handle
            interpret contents

charmander.cabal

-- Initial charmander.cabal generated by cabal init.  For further 
-- documentation, see http://haskell.org/cabal/users-guide/

name:                charmander
version:             0.1.0.0
synopsis:            Charmander-char!
-- description:         
-- license:             
license-file:        LICENSE
author:              Ignis Incendio
maintainer:          limdingwen@gmail.com
-- copyright:           
category:            Language
build-type:          Simple
cabal-version:       >=1.8

executable charmander
  main-is:             Main.hs   
  -- other-modules:       
  build-depends:       base ==4.6.*, split, vector

示例程序

Loop.char

Charmander-charmander charmander-charmander charmander-charmander charmander-charmander charmander-charmander
Charmander-charmander charmander-charmander charmander-charmander charmander-charmander charmander-charmander
Charmander-char 
    Char-char
    Charmander-charmander charmander-charmander charmander-charmander
    Charmander-charmander charmander-charmander charmander-charmander
    Char
    Cha-cha
Cha-charmander-char
Char-char
Charmander-charmander charmander-charmander charmander-charmander charmander-charmander charmander-charmander
Charmander

Input.char

Cha <- This means to input into 0
charmander <- This outputs the 0

OOB.char

OOB since DP will be at -1 and then try to print it
Char cha charmander

输出

ignis99:~/workspace/charmander $ dist/build/charmander/charmander A\ Loop.char 
A
Core dump: 
Program {dp = 1, memory = fromList [0,65,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], code = [], loopback = []}

Cha char charmander (0).
ignis99:~/workspace/charmander $ dist/build/charmander/charmander Input.char                                                                              
qq
Core dump: 
Program {dp = 0, memory = fromList [113,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], code = [], loopback = []}

Cha char charmander (0).
ignis99:~/workspace/charmander $ dist/build/charmander/charmander OOB.char                                                                                
qcharmander: ./Data/Vector/Generic/Mutable.hs:730 (update): index out of bounds (-1,128)

送给谁的礼物一定会很高兴。

该问题以及@Zeta的答案已被选为“ 2016年最佳代码评论”（Best of Code Review）“日夜”。

#1 楼

祝贺您的第一个大型项目。我不确定此评论是否有所增加，因为它既是评论也是迷你教程。两种方式：

char是什么？

Charmander-char Char cha charmander Char。？ Charmander！

总体上令人困惑吗？

Char！我的意思是主要是由于函数的名称。如您所知，Charmander本质上是Brainfuck。因此，它具有一些简单的操作，+，-，>，<，.，,，[和]，它们具有清晰的语义：increase_current_cell，decrease_current_cell，move_to_cell_right，move_to_cell_left等。
您的命令不会使自己脱离原始语言：

parse :: String -> Program -> IO Program
parse "char"                  = char
parse "char-char"             = charChar
parse "cha"                   = cha 
parse "charmander"            = charmander
parse "cha-cha"               = chaCha
parse "charmander-charmander" = charmanderCharmander
parse "charmander-char"       = charmanderChar
parse "cha-charmander-char"   = chaCharmanderChar
parse _                       = unknown

至此，与*.char文件中的原始代码相比，您几乎没有获得任何收益。相反，您必须将所有含义都保留在（大脑）的记忆中。

要回到Brainfuck，这与写作相同。

parse :: Char -> Program -> IO Program
parse '<' = lessThan
parse '>' = greaterThan
parse '+' = plus
parse '-' = minus
parse '.' = dot
parse ',' = comma
parse '[' = leftBracket
parse ']' = rightBracket
parse _   = unknown

当然可以。但是您的程序名称不正确。

再次获得bulbasane（*）

首先，您应该重命名程序。虽然这只是“赠予”某人的礼物，但您仍然想知道程序的实际含义，稍后：

-- instead of char
previousCell :: Program -> IO Program
previousCell = return $ move (-1) Program

-- instead of charChar
nextCell :: Program -> IO Program
nextCell = return $ move 1 Program

记住，您是最有可能阅读的人再次编写代码，因此您想快速了解正在发生的事情。现在，parse只会稍有变化：

parse :: String -> Program -> IO Program
parse "char"                  = previousCell
parse "char-char"             = nextCell
parse "cha"                   = getCell
parse "charmander"            = putCell
parse "cha-cha"               = decreaseCell
parse "charmander-charmander" = increaseCell
parse "charmander-char"       = startLoop
parse "cha-charmander-char"   = endLoop
parse _                       = unknown

很好的副作用：如果您丢失了Charmander的原始文档，仍可以在此处查找。

但是，这很笨重。我们必须一遍又一遍地解释和解析程序。这给我们带来了其他问题：

我通过将源代码分成单词列表（代码状态），然后递归地遍历列表并在每个循环中对其进行解析来执行程序。有更好的方法吗？可能是令牌化吗？
我只是觉得处理循环的方式不太好；例如toChaCharmanderChar'。

这里是我们开始真正的旅程的地方。
让我们检查您的类型：但是，当您使用编程语言时，您不想使用原始代码的时间太长（除非它包含解析器错误）。相反，您希望使用以指令或语法（如果要查找更多信息，则为抽象语法树AST）来描述程序的内容。让我们考虑以下方面的指令：您的程序：

type Code = [String]

data Program = Program {
    dp :: DP,
    memory :: Memory,
    code :: Code,
    loopback :: [Code]
} deriving Show

其中包含我们在Charmander中可以执行的所有操作：我们可以增加/减少单元格，向左或向右移动，放置一个字符或得到一个，我们可以循环。请注意，没有Code和StartLoop。我们要么有一个正确的循环，要么我们没有。

现在，您的EndLoop可以被认为是Code：

data CharmanderInstruction 
     = IncreaseCell
     | DecreaseCell
     | MoveRight
     | MoveLeft
     | PutChar
     | GetChar
     | Loop [CharmanderInstruction]
     deriving Show

关注点分离

此方法为我们提供了更容易分离关注点。如果我们将功能的职责分开，则也将更容易推断出它们的行为。

漂亮的打印

与此相关的优点是，您现在可以打印您喜欢的程序。也许您想阅读一个相当冗长的版本：

type Code = [CharmanderInstruction]

或者您想打印Charmander代码：

pretty :: (CharmanderInstruction -> String) -> [CharmanderInstruction] -> String
pretty f xs = concatMap f xs

prettyVerbose :: [CharmanderInstruction] -> String
prettyVerbose = pretty verbose
   where
     verbose IncreaseCell = "Increase the current cell\n"
     verbose DecreaseCell = "Decrease the current cell\n"
     ...

或者您想打印…Brainfuck：如您所见，使用[CharmanderInstruction]将使您能够以多种不同的方式打印代码。

解析

但是打印说明没有帮助。我们需要以某种方式解析它们。您可以将CharmanderInstruction重写为

prettyCharmander :: [CharmanderInstruction] -> String
prettyCharmander = pretty charmander
   where
     charmander IncreaseCell = "charmander-charmander\n"
     charmander DecreaseCell = "cha-cha\n"
     ...

并将代码解析为指令，而不是更改程序。解析循环可能很棘手，但是很容易管理。但是，这实际上将向您显示指令，而先前的程序仅向您显示文件中已有的代码。

此外，您可以用相同的方式编写parse和parseBrainfuck，其余的您的管道仍然可以使用。

执行

我通过将当前代码状态放入名为loopback的堆栈中并使用它来创建循环必要时“回到过去”。有更好的方法吗？
我只是觉得处理循环的方式不雅；如toChaCharmanderChar'。

如果使用上述方法，则可以使用

prettyBrainfuck :: [CharmanderInstruction] -> String
prettyBrainfuck = pretty brainfuck
   where
     brainfuck IncreaseCell = "+"
     brainfuck DecreaseCell = "-"
     ...

您可以简单地递归处理循环。另外，由于本质上是作用于状态，因此可以使用parseBulbasaur和lens，但这是优先选择。，这是可能的图像，以及可能的图像：

如果遵循此模型，将很容易添加其他类似Brainfuck的语言。

StateT Program IO a的其他功能

还有一个额外的壮举，就是在解析期间使用CharmanderInstruction而不是CharmanderInstruction。假设您要编写一个简单的IO Program程序，该程序仅接收用户输入并将其写回：

parse :: String -> Code

代码如下所示：

-- Pseudo code
execute :: CharmanderInstruction -> Program -> ...
execute (Loop code) p 
  | currentValueIsZero p = interpret (next p) p
  | otherwise            = interpret code     p
execute ...

现在，如果要测试它，则必须运行解释器，键入一些内容，并验证所有内容是否按预期工作。但是，既然您只使用抽象指令，则可以编写一个使用echo模拟输入的函数：

Charmander Code                 |  Brainfuck
--------------------------------+----------------------------
Cha                             | ,   
Charmander-char                 | [
Charmander                      | .
Cha                             | ,
Cha-charmander-char             | ]

现在，我们可以使用QuickCheck来测试您的功能：

echoCode :: [CharmanderInstruction]
echoCode = [ GetChar , Loop [ PutChar, GetChar ] ]

如果可能的话，应减少String
看到，IO不需要simulate。如果操作正确，则可以使用它来编写原始代码。再次，这使您的代码更易于推理。通过IO的类型，我们知道它具有某种当前程序状态的内部表示形式，并且我们知道它不能自行获取用户的实际输入。

其他回答的问题

如果Vector是在程序状态记录Program中表示当前内存状态的最佳选择？想要有限的内存，是的。但是，由于要对interpret中的向量进行变异，因此您可能想使用可变的变体。哪个模拟了内存的左，当前和右部分： >

总体来说是的。但是，如果使用AST，则simulate中的防护功能将消失。

其他怪癖

将IO用于单元格。由于您最有可能在64位系统上，因此toChaCharmanderChar'是Integer。如果要使其中一个值大于该值，则需要运行maxBound :: Int 9223372036854775807次。即使每个9223372036854775807都只花费一个飞秒（1fs），它也需要一整天的时间进行评估。这也将消除IncreaseCell的调用。使用与上述相同的IncreaseCell，并使用相似的指令级别。
有关更一般的方法，请查看Int monad。

（*）对不起双关语。

\ $ \ begingroup \ $
内容丰富。谢谢！！
\ $ \ endgroup \ $
–伊格尼斯·Incendio
16年5月20日在12:20

\ $ \ begingroup \ $
@IgnisIncendio：不客气。不过，我昨天完全忘了我在IO上的言论。抱歉^^“。
\ $ \ endgroup \ $
– Zeta
16年5月21日在13:03

\ $ \ begingroup \ $
“ *不好意思的双关语。”不，你不是。
\ $ \ endgroup \ $
–莫妮卡基金的诉讼
16年5月21日在15:49

编程黑洞网

Haskell的Charmander Brainfuck译员

评论

#1 楼

评论