在Haskell中编写一个Haskell解释器

Question

一个经典的编程练习是在Lisp/Scheme中编写一个Lisp/Scheme解释器.可以利用完整语言的强大功能为该语言的子集生成解释器.

Haskell有类似的练习吗？我想使用Haskell作为引擎来实现Haskell的子集.当然可以做到,但有没有可供查看的在线资源？

---

这是背景故事.

我正在探索使用Haskell作为一种语言来探索我正在教授的离散结构课程中的一些概念的想法.在这个学期,我已经选择了Miranda,这是一种激发Haskell的小语言.米兰达做了我想做的事情的90%左右,但哈斯克尔做了大约2000%.:)

所以我的想法是创建一种具有Haskell功能的语言,我希望并禁止其他所有功能.随着学生的进步,我可以在掌握了基础知识后有选择地"开启"各种功能.

教学"语言水平"已成功用于教授Java和Scheme.通过限制他们可以做的事情,你可以防止他们在掌握你想要教授的语法和概念的同时在脚中射击.并且您可以提供更好的错误消息.

Answer 1

我喜欢你的目标,但这是一项伟大的工作.一些提示:

• 我一直致力于GHC,你不需要任何部分资源. 拥抱是一个更简单,更清洁的实现,但不幸的是它在C中.

• 这是谜题的一小部分,但马克琼斯在Haskell写了一篇名为Typing 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

你想从头开始构建你的翻译吗？首先实现一个更简单的函数语言,如lambda演算或lisp变体.对于后者,有一个非常好的wikibook,在48小时内称为自己编写一个方案,为解析和解释技术提供了一个很酷和实用的介绍.

手动解释Haskell将会复杂得多,因为你必须处理高度复杂的特性,如类型类,一个非常强大的类型系统(类型推理!)和惰性评估(简化技术).

所以你应该定义一个很小的Haskell子集,然后开始逐步扩展Scheme-example.

加成:

请注意,在Haskell中,您可以完全访问解释器API(至少在GHC下),包括解析器,编译器和解释器.

要使用的包是提示(Language.Haskell.*).遗憾的是,我没有找到关于此的在线教程,也没有自己试过,但看起来很有希望.

Answer 4

创建一种具有我想要的Haskell功能的语言,并禁止其他所有功能.随着学生的进步,我可以在掌握了基础知识后有选择地"开启"各种功能.

我建议这个问题的解决方案更简单(如涉及的工作量少).您可以使用程序首先检查代码是否使用您不允许的任何功能,然后使用现成的编译器对其进行编译,而不是创建可以关闭功能的Haskell实现.

这与HLint类似(也有相反的情况):

HLint(以前称为Haskell博士)读取Haskell程序并建议改变,希望它们更容易阅读.HLint还可以轻松禁用不需要的建议,并添加自己的自定义建议.

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

Answer 5

Baskell是一个教学实现,http: //hackage.haskell.org/package/baskell

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

Answer 6

EHC系列编译器可能是最好的选择:它是积极开发的,似乎正是你想要的 - 一系列小型lambda演算编译器/解释器最终在Haskell '98中出现.

但是你也可以看看在皮尔斯的类型和编程语言中开发的各种语言,或者氦解释器(用于学生的残缺Haskell http://en.wikipedia.org/wiki/Helium_(Haskell)).

Answer 7

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

我为Code Golf挑战编写了一个自编译的Haskell子集编译器.它在输入上获取Haskell子集代码并在输出上生成C代码.对不起,没有更易读的版本; 在进行自编译的过程中,我手动提取了嵌套定义.

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

• 懒惰的评价.如果解释器在Haskell中,您可能不需要为此做任何事情.

• 具有模式匹配参数和保护的函数定义.只担心变量,缺点,零和_模式.

• 简单表达式语法:

  • 整数文字

  • 字符文字

  • [] (零)

  • 功能应用(左关联)

  • 中缀:(缺点,右联想)

  • 插入语

  • 变量名称

  • 功能名称

更具体地说,编写一个可以运行它的解释器:

-- 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编译器是非常困难的.如果你开始为上面写一个解释器,添加类型检查应该不那么令人生畏.