用 Haskell 编写 Haskell 解释器

Question

一个经典的编程练习是用 Lisp/Scheme 编写一个 Lisp/Scheme 解释器。可以利用完整语言的力量来为该语言的子集生成解释器。

Haskell 有类似的练习吗？我想使用 Haskell 作为引擎来实现 Haskell 的一个子集。当然啦 能 已经完成了，但是有没有在线资源可以查看？

---

这是背景故事。

我正在探索使用 Haskell 作为语言来探索一些概念的想法 离散结构 我正在教的课程。这个学期我已经决定 米兰达, ，一种较小的语言，激发了 Haskell 的灵感。Miranda 完成了我希望它完成的大约 90%，但 Haskell 完成了大约 2000%。:)

所以我的想法是创建一种语言，它具有我想要的 Haskell 特性，并且不允许其他所有特性。随着学生的进步，一旦他们掌握了基础知识，我就可以有选择地“打开”各种功能。

教学“语言水平”已成功用于教学 爪哇 和 方案. 。通过限制他们可以做的事情，你可以防止他们在掌握你试图教授的语法和概念时搬起石头砸自己的脚。您还可以提供更好的错误消息。

Answer 1

我喜欢你的目标，但这是一项艰巨的任务。一些提示：

• 我曾在 GHC 上工作过，你不需要任何部分的源代码。 拥抱 是一个更简单、更清晰的实现，但不幸的是它是用 C 语言编写的。

• 这只是拼图的一小部分，但马克·琼斯写了一篇漂亮的论文，名为 在 Haskell 中输入 Haskell 这将是您前端的一个很好的起点。

祝你好运！通过课堂上的支持证据来确定 Haskell 的语言水平，将对社区大有裨益，而且绝对是一个可发布的结果！

Answer 2

有一个完整的 Haskell 解析器： http://hackage.haskell.org/package/haskell-src-exts

一旦你解析了它，删除或禁止某些事情就很容易了。我为 tryhaskell.org 这样做是为了禁止导入语句、支持顶级定义等。

只需解析模块：

parseModule :: String -> ParseResult Module

然后你就有了一个模块的 AST：

Module SrcLoc ModuleName [ModulePragma] (Maybe WarningText) (Maybe [ExportSpec]) [ImportDecl] [Decl]    

Decl 类型是广泛的： http://hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html#t%3ADecl

您需要做的就是定义一个白名单——其中包含可用的声明、导入、符号、语法，然后遍历 AST 并在您不希望他们知道的任何内容上抛出“解析错误”。您可以使用附加到 AST 中每个节点的 SrcLoc 值：

data SrcLoc = SrcLoc
     { srcFilename :: String
     , srcLine :: Int
     , srcColumn :: Int
     }

无需重新实现 Haskell。如果你想提供更友好的编译错误，只需解析代码，过滤它，将其发送到编译器，然后解析编译器输出。如果它是“无法将预期类型 a 与推断的匹配” a -> b“那么你就知道函数的参数可能太少了。

除非你真的想花时间从头开始实现 Haskell 或搞乱 Hugs 的内部结构，或者一些愚蠢的实现，否则我认为你应该过滤传递给 GHC 的内容。这样，如果您的学生想要使用他们的代码库并将其带到下一步并编写一些真正成熟的 Haskell 代码，那么过渡是透明的。

Answer 3

你想从头开始构建你的解释？与实施，如演算或口齿不清的变体更容易的函数式语言开始。对于后者有一个相当不错的维基称为写自己计划在48小时内给予凉爽务实引入分析和解释技术。

手工解释哈斯克尔会更加复杂，因为你必须处理高度复杂的功能，如类型类，一个非常强大的类型系统（类型推断！）和懒惰的评价（还原技术）。

所以，你应该定义哈斯克尔的相当小的子集一起工作，然后也许通过扩展一步的计划，例如步开始。

增加：

请注意在Haskell，你可以完全访问口译API（至少在GHC），其包括与课程口译解析器，编译器。

要使用的封装是暗示（Language.Haskell。*）。我很不幸地没有看见网上的教程在此，也试过了，由自己，但它看起来很有希望。

Answer 4

创建一种语言，它具有我想要的 Haskell 特性，并且不允许其他所有特性。随着学生的进步，一旦他们掌握了基础知识，我就可以有选择地“打开”各种功能。

我建议用一个更简单（涉及更少的工作）的解决方案来解决这个问题。不要创建一个可以关闭功能的 Haskell 实现，而是用一个程序包装 Haskell 编译器，该程序首先检查代码是否使用您不允许的任何功能，然后使用现成的编译器来编译它。

那将类似于 HLint （也是它的反面）：

HLint（以前的博士。Haskell）阅读 Haskell 程序并提出更改建议，希望使它们更易于阅读。HLint 还可以轻松禁用不需要的建议，并添加您自己的自定义建议。

• 实施您自己的 HLint“建议”，不要使用您不允许的功能
• 禁用所有标准 HLint 建议。
• 让你的包装器运行修改后的 HLint 作为第一步
• 将 HLint 建议视为错误。也就是说，如果 HLint “抱怨”，那么程序不会进入编译阶段

Answer 5

Baskell是教学实施方式中， http://hackage.haskell.org/package/baskell

您可以通过选择而已，也就是说，类型系统来实现启动。这是我们所复杂，如方案的解释， http://hackage.haskell.org/package/thih

Answer 6

在EHC系列的编译器可能是最好的选择。它的积极发展，似乎正是你想要的东西 - 在Haskell最终'98一系列小的λ结石编译器/解释

但你也可以看看皮尔斯的类型和编程语言的，或氦解释制定的各种语言（一个残缺的Haskell用于学生的 http://en.wikipedia.org/wiki/Helium_（Haskell中））。

Answer 7

如果您正在寻找易于实现的 Haskell 子集，您可以取消类型类和类型检查。如果没有类型类，您就不需要类型推断来评估 Haskell 代码。

我写了一个 自编译Haskell子集编译器 参加 Code Golf 挑战。它在输入上获取 Haskell 子集代码并在输出上生成 C 代码。很抱歉，没有更具可读性的版本可用；我在使其自编译的过程中手动解除了嵌套定义。

对于有兴趣为 Haskell 的子集实现解释器的学生，我建议从以下功能开始：

• 懒惰评价。如果解释器使用 Haskell，您可能不需要为此执行任何操作。

• 具有模式匹配参数和保护的函数定义。只关心变量、cons、nil 和 _ 模式。

• 简单的表达式语法：

  • 整数文字

  • 字符文字

  • [] （零）

  • 函数应用（左结合）

  • 中缀 : （缺点，右结合）

  • 插入语

  • 变量名

  • 函数名称

更具体地说，编写一个可以运行此命令的解释器：

-- tail :: [a] -> [a]
tail (_:xs) = xs

-- append :: [a] -> [a] -> [a]
append []     ys = ys
append (x:xs) ys = x : append xs ys

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = []

-- showList :: (a -> String) -> [a] -> String
showList _    []     = '[' : ']' : []
showList show (x:xs) = '[' : append (show x) (showItems show xs)

-- showItems :: (a -> String) -> [a] -> String
showItems show []     = ']' : []
showItems show (x:xs) = ',' : append (show x) (showItems show xs)

-- fibs :: [Int]
fibs = 0 : 1 : zipWith add fibs (tail fibs)

-- main :: String
main = showList showInt (take 40 fibs)

类型检查是 Haskell 的一个重要特性。然而，从无到有类型检查 Haskell 编译器是非常困难的。如果您首先为上述内容编写一个解释器，那么向其添加类型检查应该不会那么令人畏惧。

Answer 8

您可能看快乐（哈斯克尔一类yacc解析器），其中有一个Haskell解析器。

Answer 9

这可能是一个好主意 - 做一个在Haskell的NetLogo的微小版本。 这里是微小的解释器。

Answer 10

看是否氦将使一个更好的基础，以建立在比标准的Haskell。

Answer 11

UHC / EHC是一系列编译器启用/禁用的各种特征的Haskell的。    http://www.cs.uu.nl/wiki/Ehc/WebHome# What_is_UHC_And_EHC

Answer 12

我已经告诉伊德里斯有一个相当紧凑的分析器，不知道它是否真的适合改造的，但它是写在Haskell。

Answer 13

安德烈·鲍尔的编程语言动物园有一个小的实现的纯粹函数式编程语言有点厚颜无耻名为“minihaskell”。它是约700线OCaml的，所以很容易消化。

该网站还包含ML-风格，Prolog的风格和面向对象的编程语言版本的玩具。

Answer 14

你不觉得它会更容易采取的GHC源并去掉你不想要的东西，那将是比从头开始写自己的Haskell解释？一般来说，应该有一个很多较少的努力涉及的除去特征，而不是创建/增加功能。

GHC是写在Haskell反正，所以在技术上与您写在Haskell Haskell的解释的问题保持。

这可能不会太硬，使静态链接整个事情，然后只分发您的自定义GHCI，使学生无法加载其他Haskell的源代码模块。至于会是多少工作需要，以防止它们加载其他Haskell的目标文件，我不知道。您可能需要禁用FFI也一样，如果你有一帮骗子在你的类：）

Answer 15

之所以有如此多的 LISP 解释器，是因为 LISP 基本上是 JSON 的前身：一种简单的数据编码格式。这使得前端部分非常容易处理。相比之下，Haskell，尤其是语言扩展，并不是最容易解析的语言。这些是一些听起来很难正确理解的语法结构：

• 具有可配置优先级、关联性和固定性的运算符，
• 嵌套评论
• 布局规则
• 模式语法
• do- 块和脱糖为单子代码

除了操作符之外，所有这些问题都可以由学生在完成编译器构建课程后解决，但这会将注意力从 Haskell 的实际工作原理上转移开。除此之外，您可能不想直接实现 Haskell 的所有语法结构，而是实现传递来摆脱它们。这将我们带到了问题的字面核心，完全是双关语。

我的建议是实施类型检查和解释器 Core 而不是完整的 Haskell。这两项任务本身就已经相当复杂了。这种语言虽然仍然是一种强类型函数语言，但在优化和代码生成方面处理起来要简单得多。然而，它仍然独立于底层机器。因此，GHC 使用它作为中间语言，并将 Haskell 的大多数语法结构翻译成它。

此外，您不应该回避使用 GHC（或其他编译器）的前端。我不认为这是作弊，因为自定义 LISP 使用主机 LISP 系统的解析器（至少在引导期间）。打扫干净 Core 片段并将其与原始代码一起呈现给学生，应该可以让您概述前端的功能，以及为什么最好不要重新实现它。

以下是一些文档的链接 Core 如 GHC 中所用：

• 系统FC：平等约束和强制
• GHC/作为图书馆
• 这 Core 类型