用Haskell编写Haskell解释器

我喜欢你的目标,但这是一项艰巨的任务。几点提示:

• Hugs 是一个更简单、更干净的实现,但不幸的是它是用C语言实现的。

• 这只是拼图的一小部分,但马克·琼斯写了一篇漂亮的论文,名为 Typing Haskell in Haskell 这将是一个伟大的起点,为您的前端。

祝你好运通过课堂上的支持性证据,确定Haskell的语言水平,将对社区产生巨大的好处,并且肯定是一个可发布的结果!

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

parseModule :: String -> ParseResult Module

然后,您有一个模块的AST:

Module SrcLoc ModuleName [ModulePragma] (Maybe WarningText) (Maybe [ExportSpec]) [ImportDecl] [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匹配 a -> b “那么你就知道函数的参数可能太少了。

除非你真的想花时间从头开始实现Haskell,或者搞乱Hugs的内部结构,或者一些愚蠢的实现,否则我认为你应该过滤传递给GHC的内容。这样,如果您的学生希望获得他们的代码库并进入下一步,编写一些真正成熟的Haskell代码,那么转换是透明的。

Write yourself a Scheme in 48 hours 对语法分析和解释技术进行冷静而实用的介绍。

因此,您应该定义Haskell的一个相当小的子集来使用,然后可以一步一步地扩展Scheme示例。

补充:

要使用的包是 hint (Language.Haskell.*)

创建一种完全具有Haskell特性的语言,我喜欢它,但不允许其他任何东西。随着学生的进步,一旦他们掌握了基础知识,我可以有选择地“打开”各种功能。

这将类似于 HLint

HLint(原名Haskell博士)阅读Haskell程序,并提出修改建议,希望能使其更易于阅读。HLint还可以轻松地禁用不需要的建议,并添加您自己的自定义建议。

• 实施您自己的HLint“建议”,不要使用您不允许的功能
• 禁用所有标准HLint建议。
• 将HLint建议视为错误。也就是说,如果HLint“抱怨”,则程序不会进入编译阶段

http://hackage.haskell.org/package/baskell

您可以从选择要实现的系统类型开始。这和Scheme的解释器一样复杂, http://hackage.haskell.org/package/thih

EHC系列编译器可能是最好的选择:它是积极开发的,似乎正是您想要的——一系列小型lambda calculi编译器/解释器,最终在Haskell'98中达到顶峰。

类型和编程语言 ,或氦翻译(一个残废的哈斯克尔,专为学生设计的) http://en.wikipedia.org/wiki/Helium_(Haskell) ).

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

我写了一封信 self-compiling Haskell subset compiler

对于有兴趣为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编译器是非常困难的。如果您开始为上面的内容编写一个解释器,那么向其中添加类型检查应该不会那么困难。

你可以看看 Happy (Haskell中类似yacc的解析器)具有Haskell解析器。

This 可能是个好主意-在Haskell中制作一个小小的NetLogo版本。 Here 这是一个小小的翻译。

看看是否 helium

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

我听说了 Idris 有一个相当紧凑的解析器,不确定它是否真的适合修改,但它是用Haskell编写的。

安德烈·鲍尔氏 Programming Language Zoo 有一个纯函数式编程语言的小实现,有点冒失地命名为“minihaskell”。它大约有700行OCaml,所以很容易消化。

你不觉得这样更容易接受吗 the GHC sources 去掉你不想要的东西,而不是从头开始编写自己的Haskell解释器?一般来说,应该有一个 大量 减少工作投入 移除 功能,而不是创建/添加功能。

不管怎么说,GHC是用Haskell编写的,所以从技术上讲,这就是用Haskell编写的Haskell解释器的问题。

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

• 具有可配置优先级、关联性和固定性的运算符,
• 嵌套注释
• 布局规则
• 模式语法
• do -分块和去糖化为一元代码

每一个问题,也许除了操作符,都可以由学生在他们的编译器构造课程结束后解决,但这会让人们把注意力从Haskell的实际工作方式上移开。除此之外,您可能不希望直接实现Haskell的所有语法构造,而是实现传递来消除它们。这就把我们带到了这个问题的字面核心,即双关语。

我的建议是实施类型检查和翻译 Core 而不是完全的哈斯克尔。这两项任务本身已经相当复杂了。 这种语言虽然仍然是一种强类型函数式语言,但在优化和代码生成方面处理起来并不复杂。 因此,GHC使用它作为中介语言,并将Haskell的大多数语法结构翻译成它。

此外,您不应该回避使用GHC(或其他编译器)的前端。 我不认为这是作弊,因为自定义LISP使用主机LISP系统的解析器(至少在引导过程中)。清理 果心 片段并将其与原始代码一起呈现给学生,应该允许您概述前端的功能,以及为什么不重新实现它更可取。

这里有一些链接指向 果心 在GHC中使用:

• System FC: equality constraints and coercions
• GHC/As a library
• The Core type