高手问答第 286 期 —— 用 Java 和 Scala 实现微型 Lisp 解释器

OSC哒哒 发布于 06/27 16:38
阅读 5K+
收藏 3

开源之夏第三届火热来袭,高校学生参与赢万元奖金!>>>

什么是组合子逻辑?一般来说组合子逻辑是指一类函数式编程语言的编程模式,它将具有同一功能接口的不同逻辑功能(算子)组合为新的、更复杂的逻辑,同时保留同样的功能接口,使接口具有外在的一致性。这是函数式编程中的一个基本范式。在面向对象的设计模式中,也有一些类似的设计思想。

不少函数式编程语言的文本分析工具是用组合子实现的,例如Haskell的Parsec和Scala的Parser.Combinators库。这是因为组合子很适合表达抽象模式,例如重复、间隔、顺序依赖等。组合子的这种特性使其可应用于各种各样的序列分析,包括非线性序列。

OSCHINA 本期高手问答6  28 日 - 7  4 日)我们邀请到畅销书《微型Lisp解释器的构造与实现》的作者 @刘鑫MarsLiu 老师和大家一起探讨“用Java和Scala实现微型Lisp解释器”的话题,包括:

  • 学习组合子逻辑要注意什么?
  • 实现这样一个解释器的难点在哪里?
  • 用组合子实现解释器的优势是什么?
  • 移植的这些解释器应用在了哪些项目?


有其他相关的问题,也欢迎提问。

嘉宾介绍:

刘鑫,资深程序员、架构师,2000年毕业于兰州大学数学系,从事软件开发工作21年,参与过电子商务、政务、网游、互联网服务、移动应用等多个领域的项目开发。近十年来,致力于将Haskell的Parsec解释器移植到Go、Swfit、Rust、Javascript、Python、Scala、Java等编程语言中,主要成果包括基于Scala 2.x的Jaskell Core和基于Java 8的Jaskell Java8。这些成果均已应用于实际软件开发。

为了鼓励踊跃提问,我们会在问答结束后从提问者中抽取幸运会员赠予畅销书《微型Lisp解释器的构造与实现》一书。

天猫有售:https://detail.tmall.com/item.htm?id=676914642112

京东购书:https://item.jd.com/10054541441323.html

OSChina 高手问答一贯的风格,不欢迎任何与主题无关的讨论和喷子。

下面欢迎大家向 @刘鑫MarsLiu 老师积极提问,直接回帖提问即可。

加载中
0
OSC哒哒
OSC哒哒

高手问答第 286 期 —— 用 Java 和 Scala 实现微型 Lisp 解释器 

@hoverload  @htoooth @pyboy58

恭喜以上三位网友分别获得《微型 Lisp 解释器的构造与实现》书籍一套

请于7月12日前登陆账号, 私信  @小白兔爱吃大灰狼   告知快递信息(格式:姓名+电话+地址)

1
刘鑫MarsLiu
刘鑫MarsLiu

引用来自“贺小皮蛋”的评论

老师能先说下 微型 Lisp 解释器  是干什么的吗 未知领域了

这个问题我们分几个层面讨论哈。Lisp 本身是一门历史悠久的编程语言,它的特点是极简的形式。几乎所有的代码都是所谓的S表达式,即形如

(+ x (* 6 6) 5 4)

这样的前缀表达式。这个极简的形式带来一个好处就是,实现一个最简单的 Lisp 解释器需要的代码量很低,很适合用来编写教材,例如本书书名致敬的名著《计算机程序的构造与实现》,和本书的原型,著名的Haskell教材《Write Yourself a scheme in 48 hours》。

本书选用 Lisp 作为解释器示例,还有一个原因是,这个解释器设计的 Go 语言版本,曾经用在我的业务系统中。这个 S 表达式解释器内核,极大的弥补了 Go 语言编写应用业务时的不足。因为在这个项目上得到了好处,后来我为 scala 和 java 实现 parsec 组合子的时候,就编写了对应的解释器作为测试案例。

大型的 Lisp 语言实现,可能是非常复杂的 runtime 和编译器组成的生态,例如 Common Lisp 和 JVM 上最成功的 LISP 实现 Clojure 。但是,它也可以是像我的 Gisp2、Jisp、Sisp这样的微型解释器,小到可以内嵌到一个异步任务中,或者在宿主代码中直接操作它的 AST。祝读者朋友们从这样一个微型项目出发,可以在将来超越这个小小的练习项目,体会到高度抽象的工具设计带来的生产力提升。

0
贺小皮蛋
贺小皮蛋

老师能先说下 微型 Lisp 解释器  是干什么的吗 未知领域了

刘鑫MarsLiu
刘鑫MarsLiu
这个问题我们分几个层面讨论哈。Lisp 本身是一门历史悠久的编程语言,它的特点是极简的形式。几乎所有的代码都是所谓的S表达式,即形如 (+ x (* 6 6) 5 4) 这样的前缀表达式。这个极简的形式带来一个好处就是,实现一个最简单的 Lisp 解释器需要的代码量很低,很适合用来编写教材,例如本书书名致敬的名著《计算机程序的构造与实现》,和本书的原型,著名的Haskell教材《Write Y
大漠真人
大漠真人
炫技用的
0
pyboy58
pyboy58

@刘鑫MarsLiu  1.Lisp解释器 解决了什么疼点问题,帮助用户提高了哪些指标?

2. Parsec解释器 ,lisp解释器, 和jvm虚拟机之间的关系和联系? 

3.学习组合子逻辑要注意什么?  这个组合子逻辑相当于Java里什么?

LZSkyline1225
LZSkyline1225
对于问题1,Lisp语言本身擅长做符号计算。如果从实用性角度考虑,用现有的Lisp实现(如SBCL或ChezScheme)效果更好,好的实现性能基本超过Java,而且提供一些激进的语法特性,甚至扩展语言自身。大部分人眼里,程序和数据、算法不同,处于特殊地位,基本不会去编写操作程序的程序,而学习解释器,可以在观念上打破程序与数据的界限,让思维更放得开。而这本书就可以帮助读者在一定程序了解语言解释器
0
htoooth
htoooth

@刘鑫MarsLiu 组合子逻辑要求明确的,不是所有的需求的能转换成组合子逻辑,这个时候怎么判断呢?是用组合子还是用别的技术呢?

0
刘鑫MarsLiu
刘鑫MarsLiu

引用来自“htoooth”的评论

@刘鑫MarsLiu 组合子逻辑要求明确的,不是所有的需求的能转换成组合子逻辑,这个时候怎么判断呢?是用组合子还是用别的技术呢?

任何一个工具都有它的适用范围和局限,Parsec的强项是基于可回滚的状态定义解析规则。

确实有很多场合并不适用,或者并不需要组合子。它是一个有用的工具,但不是万能的。

例如我现在在编写一个基于概率模型的HTML解释器,就没有围绕 parsec 设计(或许在

非关键的部分会用到一点),而是基于 Scala 的概率编程库 Figaro。

0
刘鑫MarsLiu
刘鑫MarsLiu

引用来自“pyboy58”的评论

@刘鑫MarsLiu  1.Lisp解释器 解决了什么疼点问题,帮助用户提高了哪些指标?

2. Parsec解释器 ,lisp解释器, 和jvm虚拟机之间的关系和联系? 

3.学习组合子逻辑要注意什么?  这个组合子逻辑相当于Java里什么?

Haskell 的 Parsec 库是一个文本处理库,Perl6的第一个实现 pugs 就用它开发。我在实现 Java 和 Scala 的 版本时,特意预留了更高的抽象设计,一方面让它可以能够更广泛的适用于任意类型的可回滚信息流,另一方面让Jaskell和 Scala 的类型系统尽可能的结合起来。Jaskell-Java8 则是一个完全使用 Java 8环境开发的实现,用于 Java 项目。无论适用 scala 2.11~2.13 的 jaskell-core  ,还是适用 scala 3 的 jaskell-dotty ,或者 jaskell-java8 ,它们本质上仍然是 Java 和 Scala 库,可以在 JVM 项目中使用。至于 JISP 和SISP,可以看作是 jaskell 系列的示范库。它们很小,定位于演示组合子库功能,和有限应用于一些项目,简化代码。

组合子的使用并不算复杂,它其实是两部分组成,一个是包装信息流的状态类型,一个是各种组合子。它可以看作是复杂度、功能、使用代价都介于 lex/yacc 和 正则表达式之间的一类解析工具。

0
我的ID是jmjoy
我的ID是jmjoy

@刘鑫MarsLiu 为什么要用Java来实现?

刘鑫MarsLiu
刘鑫MarsLiu
我那个时候正好有一个Java项目需要Parsec功能,就写了一个Java8版本。既然写了parsec,也就顺手写了一个解释器。
我的ID是jmjoy
我的ID是jmjoy
回复 @pyboy58 : Lisp本身就不主流,不如用舒服点的语言来写。
pyboy58
pyboy58
大部分公司的业务系统还是java的比较多些,要主流兼容吧
0
hoverload
hoverload
听说很多学Lisp的人都掉进了编译原理的坑里,想问问老师,书中Lisp解释器的实现是不是也类似实现编译器,要做词法、语法、语义分析和代码优化呢
刘鑫MarsLiu
刘鑫MarsLiu
这本书没有那么深,只涉及了解释器相关的东西,而且是最简单的那种实现,可以作为编译原理的预习。 我写过一个解释器,先用组合子做词法分析,然后再将生成的token流导入组合子定义的语法分析程序。不过这本书里是最简单的直接从文本构造AST,然后用一个基于字典的环境对象来执行它。
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部