0

考虑一个简单的 Haskell Brainf*ck解释器。只看interpret功能。

import Prelude hiding (Either(..))
import Control.Monad
import Data.Char (ord, chr)

-- function in question
interpret :: String -> IO ()
interpret strprog = let (prog, []) = parse strprog
                    in execBF prog


interpretFile :: FilePath -> IO ()
interpretFile fp = readFile fp >>= interpret


type BF = [BFInstr]
data BFInstr = Left | Right | Inc | Dec | Input | Output | Loop BF

type Tape = ([Integer], [Integer])

emptyTape = (repeat 0, repeat 0)

execBFTape :: Tape -> BF -> IO Tape
execBFTape = foldM doBF

execBF :: BF -> IO ()
execBF prog = do
  execBFTape emptyTape prog
  return ()

doBF :: Tape -> BFInstr -> IO Tape
doBF ((x:lefts),   rights)   Left     = return (lefts,         x:rights)
doBF (lefts,    (x:rights))  Right    = return (x:lefts,         rights)
doBF (left,     (x:rights))  Inc      = return (left,      (x+1):rights)
doBF (left,     (x:rights))  Dec      = return (left,      (x-1):rights)
doBF (left,     (_:rights))  Input    = getChar >>= \c -> return (left, fromIntegral (ord c):rights)
doBF t@(_,      (x:     _))  Output   = putChar (chr (fromIntegral x)) >> return t
doBF t@(left,   (x:     _)) (Loop bf) = if x == 0
                                        then return t
                                        else do t' <- execBFTape t bf
                                                doBF t' (Loop bf)

simpleCommands = [('<', Left),
                  ('>', Right),
                  (',', Input),
                  ('.', Output),
                  ('+', Inc),
                  ('-', Dec)]

parse :: String -> (BF, String)
parse []          = ([], [])
parse (char:prog) = case lookup char simpleCommands of
                      Just command -> let (rest, prog') = parse prog
                                      in (command : rest, prog')
                      Nothing      ->
                        case char of
                          ']' -> ([], prog)
                          '[' -> let (loop, prog')  = parse prog
                                     (rest, prog'') = parse prog'
                                 in (Loop loop:rest, prog'')
                          _   -> parse prog

所以我有一个像interpret "[->+<]". 这给了我一个IO ()执行给定程序的单子动作。它具有成为main某些程序的正确类型。

假设我想将此操作编译为可执行文件，也就是说，我想生成一个可执行文件，其结果为interpret ...main 函数。当然，这个可执行文件必须包含 GHC 运行时系统（用于无限列表、整数运算等）。

问题：

  1. 我认为根本不可能只采取单子动作并将其保存为新文件。这是真的？
  2. 一个人怎么能找到一个类似的解决方案呢？GHC Api 和提示有帮助吗？

编辑

抱歉，我在原始问题中过于简单化了。当然，我可以像这样写一个文件：

main = interpret "..."

但这不是我们在尝试编译某些东西时通常会做的事情，所以请考虑一下interpretFile :: FilePath -> IO ()。让BF程序保存在一个文件中（helloworld.bf )。

我将如何创建一个可执行文件，该可执行文件在helloworld.bf实际上不需要该文件的情况下执行该文件的内容？

$ ./MyBfCompiler helloworld.bf -o helloworld
4

2 回答 2

2

我不确定您是否在问如何编写可以将文件作为输入的编译器helloworld.bf，或者如何编译运行的 Haskell 程序helloworld.bf。

在前一种情况下，你会想要一些比这更充实的东西：

import System.Environment (getArgs)

main :: IO ()
main = do
  (_:fileName:_) <- getArgs
  source <- readFile fileName
  interpret source

interpret :: String -> IO ()
interpret = undefined -- You can fill in this piddly little detail yourself.

如果你想要后者，有几个不同的选择。首先，您可以将*.bf文件的内容存储在字符串常量（或者更好的是 aText或 strict ByteString）中，并将其传递给您的解释器函数。如果 GHC 足够乐观以在编译时完全内联和扩展该调用，我会感到惊讶，但原则上 Haskell 编译器可以。

第二个是用你定义的运算符将 Brainfuck 变成一种特定领域的语言，这样你就可以实际编写类似的东西

interpret [^<,^+,^>,^.]

如果您定义(^<)和其他运算符，Brainfuck 命令将编译为表示 Brainfuck 程序的字节码。

在这种情况下，与第一种方法相比没有明显的好处，但是使用更结构化的语言，您可以进行优化，将源代码编译为更适合解释器执行的基于堆栈的字节码，或者生成更多复杂的AST。

你也可以将这个想法表达为

interpret
  (^< ^+ ^> ^.)
  input

在这里，如果 Brainfuck 命令是具有从右到左优先级的高阶函数，并且interpret bf input = (bf begin) input，Brainfuck 代码将简单地编译为解释器调用的函数。这最有可能变成快速的本机代码。

上一个答案

在某些情况下，编译器可以内联函数调用（GHC 中有编译指示告诉它这样做）。如果您命名闭包，编译器也更有可能做您想做的事情，例如：

main = interpret foo

在 GHC 中，您可以通过添加来给编译器一个提示

{-# INLINE main #-}

甚至

{-# INLINE interpret #-}

您可以通过编译模块-S并查看源代码来检查 GHC 生成的代码。

于 2018-07-19T04:35:14.790 回答
2

答案基本上是否定的。

IO构造值的方法有很多：

  1. 内置功能，如putStrLn
  2. Monad 操作像returnor>>=

获得 IO 值后，可以通过三种方式对其进行分解：

  1. 设置main等于值
  2. unsafePerformIO
  3. 作为导出的 C 函数的返回值

所有这些都分解为将 aIO a转换为a. 没有其他方法可以检查它以查看它的作用。

同样，您可以对函数做的唯一事情是将它们放入变量中或调用它们（或将它们转换为 C 函数指针）。

没有明智的方法来检查函数。

您可以做的一件不是编译而是链接的事情是让您的解释器主函数在一些外部 c 字符串上运行，将其构建到一个静态对象中，然后您的“编译器”可以使用这个 C 字符串创建一个新对象其中的程序并将其链接到您已有的程序。

有这种部分评估理论说，如果你对应用于某些输入的解释器的部分评估器进行部分评估，那么你得到的是一个编译器，但 ghc 不是一个足够先进的部分评估器。

于 2018-07-19T08:47:03.920 回答