在Haskell中编写一个Haskell解释器

一个经典的编程练习是在Lisp / Scheme中编写一个Lisp / Scheme解释器。 全语言的力量可以用来为语言的一个子集产生一个解释器。

Haskell有类似的练习吗? 我想用Haskell作为引擎来实现一个Haskell的子集。 当然可以 ,但是有没有在线资源可供查看?


这是背后的故事。

我正在探索使用Haskell作为一种语言的想法来探索我正在教授的离散结构课程中的一些概念。 在这个学期里,我已经解决了米兰达 ,一个较小的语言,启发了哈斯克尔。 米兰达做了大概90%的工作,但是哈斯克尔做了大约2000%的工作。 🙂

所以我的想法是创build一个语言,具有我想要的Haskell的特征,并且不允许其他任何东西。 随着学生的进步,我可以select性地“开启”各种function,一旦他们掌握了基础知识。

教学“语言水平”已被成功地用来教授Java和Scheme 。 通过限制他们可以做的事情,可以防止他们在掌握你正在教的语法和概念的同时,在脚下自己开枪。 而且你可以提供更好的错误信息。

我爱你的目标,但这是一个很大的工作。 几个提示:

  • 我已经在GHC上工作了,你不需要任何部分的来源。 拥抱是一个更简单,更干净的实现,但不幸的是它在C.

  • 这是拼图的一小部分,但Mark Jones 在Haskell写了一个叫做Typing Haskell的漂亮论文这将是你前端的一个很好的起点。

祝你好运! 为Haskell确定语言级别,并附上来自课堂的证据,将会对社区有很大的好处,而且肯定是一个可发表的结果!

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

一旦你parsing了它,剥离或者禁止某些事情是容易的。 我为tryhaskell.org做了这个,禁止导入语句,支持顶层定义等等。

只是parsing模块:

 parseModule :: String -> ParseResult Module 

然后你有一个模块的AST:

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

Decltypes非常广泛: http : //hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html#t%3ADecl

所有你需要做的是定义一个白名单 – 什么声明,导入,符号,语法是可用的,然后走AST,并抛出一个“parsing错误”,你不想让他们知道的任何东西。 您可以使用附加到AST中每个节点的SrcLoc值:

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

没有必要重新实现Haskell。 如果你想提供更友好的编译错误,只需parsing代码,过滤它,发送给编译器,并parsing编译器的输出。 如果它是“无法匹配预期的typesa反对推断a -> b ”,那么你知道这可能是一个函数的参数太less。

除非你真的真的想从头开始实施Haskell或者混淆Hugs的内幕,或者一些愚蠢的实现,否则我认为你应该过滤传递给GHC的东西。 这样一来,如果你的学生想要把他们的代码基础带到下一步,写一些真正完全成熟的Haskell代码,那么过渡是透明的。

你想从头开始build立你的翻译? 开始实施一个更简单的函数式语言,如lambda微积分或lisp变体。 对于后者来说, 在48小时内有一个非常好的wikibook 写自己的计划,给parsing和解释技术一个冷静和务实的介绍。

手工解释Haskell将会复杂得多,因为你必须处理types类,一个非常强大的types系统(type-in​​ference!)和懒惰评估(简化技术)等高度复杂的function。

所以你应该定义一个相当小的Haskell子集来处理,然后开始扩展Scheme-step。

加成:

请注意,在Haskell中,您可以完全访问解释器API(至less在GHC下),包括parsing器,编译器和口译员。

要使用的包是提示(Language.Haskell。*) 。 我遗憾的是既没有在网上find这方面的教程,也没有自己尝试过,但看起来相当有前途。

创build一个具有我想要的Haskellfunction的语言,并禁止其他所有function。 随着学生的进步,我可以select性地“开启”各种function,一旦他们掌握了基础知识。

我build议一个更简单的(如less工作)解决这个问题。 代替在可以closuresfunction的情况下创build一个Haskell实现,用Haskell编译器包装一个程序,首先检查代码是否不使用任何不允许使用的特性,然后使用现成的编译器进行编译。

这和HLint类似(也是相反的):

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

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

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

你可以从select刚刚实现的types系统开始。 这与Scheme的解释器一样复杂, http://hackage.haskell.org/package/thih

如果你正在寻找一个容易实现的Haskell的子集,你可以避免使用types类和types检查。 没有types的类,你不需要types推断来评估Haskell代码。

我为Code Golf挑战编写了一个自编译的Haskell子集编译器 。 它inputHaskell子集代码并在输出上生成C代码。 我很抱歉没有更可读的版本可用; 我在自编的过程中手工提出了嵌套的定义。

对于有兴趣为Haskell的一个子集实现解释器的学生,我build议从以下特性开始:

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

  • 具有模式匹配参数和警卫的函数定义。 只担心variables,缺点,零和_模式。

  • 简单expression式语法:

    • 整数文字

    • 字符文字

    • [] (无)

    • function应用(左联)

    • 中缀:缺点,右联)

    • 插入语

    • variables名称

    • 函数名称

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

 -- 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) = fab : 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) 

types检查是Haskell的一个重要特性。 但是,从无到有,Haskell编译器的types检查是非常困难的。 如果你从头开始编写一个解释器,那么增加types检查应该不那么令人生畏。

EHC系列编译器可能是最好的select:它是积极开发的,看起来正是你想要的 – 一系列小型lambda calculi编译器/解释器在Haskell '98中达到高潮。

但是你也可以看看皮尔斯的types和编程语言中开发的各种语言,或氦解释器(一个残疾的Haskell打算为学生http://en.wikipedia.org/wiki/Helium_(Haskell); )。

你可能会看到有一个Haskellparsing器的Happy (一个类似于Haskell的yaccparsing器)。

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

看看氦气是否会比标准的哈斯克尔build立更好的基础。

Uhc / Ehc是一系列编译器,用于启用/禁用各种Haskellfunction。 http://www.cs.uu.nl/wiki/Ehc/WebHome#What_is_UHC_And_EHC

Andrej Bauer的编程语言动物园有一个纯粹的函数式编程语言的小实现,这个语言稍微有点儿叫做“minihaskell”。 这是约700行的OCaml,所以很容易消化。

该网站还包含ML风格,Prolog风格和OO编程语言的玩具版本。

难道你不觉得拿GHC源代码去掉你不想要的东西会比从头开始编写自己的Haskell解释器更容易吗? 一般来说,与创build/添加function相比, 删除function的工作量要less很多

GHC是用Haskell编写的,所以在技术上与Haskell编写的Haskell解释器的问题保持一致。

将整个事情静态链接起来可能不会太困难,然后只分发您定制的GHCi,这样学生就无法加载其他Haskell源代码模块。 至于需要多less工作来阻止他们加载其他Haskell对象文件,我不知道。 如果你的class里有一群作弊者,你可能也想closuresFFI

我被告知Idris有一个相当紧凑的parsing器,不知道它是否真的适合修改,但它是用Haskell编写的。