什么是组合子逻辑?一般来说组合子逻辑是指一类函数式编程语言的编程模式,它将具有同一功能接口的不同逻辑功能(算子)组合为新的、更复杂的逻辑,同时保留同样的功能接口,使接口具有外在的一致性。这是函数式编程中的一个基本范式。在面向对象的设计模式中,也有一些类似的设计思想。
不少函数式编程语言的文本分析工具是用组合子实现的,例如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 老师积极提问,直接回帖提问即可。
高手问答第 286 期 —— 用 Java 和 Scala 实现微型 Lisp 解释器
@hoverload @htoooth @pyboy58
恭喜以上三位网友分别获得《微型 Lisp 解释器的构造与实现》书籍一套。
请于7月12日前登陆账号, 私信 @小白兔爱吃大灰狼 告知快递信息(格式:姓名+电话+地址)
引用来自“贺小皮蛋”的评论
老师能先说下 微型 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。祝读者朋友们从这样一个微型项目出发,可以在将来超越这个小小的练习项目,体会到高度抽象的工具设计带来的生产力提升。
老师能先说下 微型 Lisp 解释器 是干什么的吗 未知领域了
@刘鑫MarsLiu 1.Lisp解释器 解决了什么疼点问题,帮助用户提高了哪些指标?
2. Parsec解释器 ,lisp解释器, 和jvm虚拟机之间的关系和联系?
3.学习组合子逻辑要注意什么? 这个组合子逻辑相当于Java里什么?
@刘鑫MarsLiu 组合子逻辑要求明确的,不是所有的需求的能转换成组合子逻辑,这个时候怎么判断呢?是用组合子还是用别的技术呢?
引用来自“htoooth”的评论
@刘鑫MarsLiu 组合子逻辑要求明确的,不是所有的需求的能转换成组合子逻辑,这个时候怎么判断呢?是用组合子还是用别的技术呢?
任何一个工具都有它的适用范围和局限,Parsec的强项是基于可回滚的状态定义解析规则。
确实有很多场合并不适用,或者并不需要组合子。它是一个有用的工具,但不是万能的。
例如我现在在编写一个基于概率模型的HTML解释器,就没有围绕 parsec 设计(或许在
非关键的部分会用到一点),而是基于 Scala 的概率编程库 Figaro。
引用来自“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 和 正则表达式之间的一类解析工具。
@刘鑫MarsLiu 为什么要用Java来实现?