Forth翻译

Question

我最近开始学习Haskell,我正在尝试使用Haskell为FORTH语言编写解释器.但是我在尝试运行最基本的操作时遇到了问题.例如,FORTH中的一个简单程序(在Haskell中作为字符串)将如下:"1 2 +"返回包含整数3的堆栈,在Haskell中可以表示一个整数列表:[3].

我还有从堆栈中推送,删除和弹出元素的功能.我有一个添加函数来从堆栈中添加两个元素.

现在,手头有这些功能,如何解析简单的程序"1 2 +"才能返回[3]？我希望这个例子看起来像这样:

forthInterpreter "1 2 +"
[3]

任何帮助将非常感激.如果您有任何澄清问题,请告诉我.谢谢.

Answer 1

你拥有的每个命令都是一个函数Stack -> Stack.这使得解释命令变得容易.我使用a [Int]作为类型Stack,在列表顶部的堆栈顶部有数字.

interpretCommand :: String -> [Int] -> [Int]
interpretCommand "+" = lift2 (+)
interpretCommand "-" = lift2 (-)
interpretCommand "*" = lift2 (*)
interpretCommand "/" = lift2 div
interpretCommand "MOD" = lift2 mod
interpretCommand number = \zs -> read number : zs

其中lift2将2参数函数提升到列表的前2个元素上的函数.这些参数x和y进行交换,因为来回似乎有约定,第一个参数压入堆栈是第一个参数的功能和堆栈顶部的参数的第二个参数的功能.

lift2 :: (a -> a -> a) -> [a] -> [a]
lift2 f (x:y:zs) = f y x:zs
lift2 f _ = error "not enough data on the stack"

为了解释多个命令,我们将它们分开words,在空白处拆分字符串,解释每个命令,并将它们组合在一起.

composition :: [a -> a] -> a -> a
composition = foldl (flip (.)) id

interpretCommands :: String -> [Int] -> [Int]
interpretCommands = composition . map interpretCommand . words

然后我们可以通过调用interpretCommands并传递初始(空)堆栈来解释一串命令.以下是两个例子.

main = do
    print $ interpretCommands "1 2 +" []
    print $ interpretCommands "1 2 + 4 - 3" []
    print $ interpretCommands "10 5 / 3" []
    print $ interpretCommands "13 7 MOD 2 / 4 *" []

输出是

[3]
[3,-1]
[3,2]
[12]

请注意,[3,-1]它的顺序与您建议的顺序相反,因为3它位于堆栈顶部,因此位于列表的开头.(这是您在评论中预测的行为fourthadd.)