分享 Egison: 非线性模式匹配的 Lisp 方言

luikore · 2015年02月05日 · 最后由 chanshunli 回复于 2015年02月06日 · 3347 次阅读

感谢 @clongbupt 介绍, 认识了 Egison (号称新编程范式, 东大还开了一门 Egison 的课...)

关于 egison 里的一些符号:

  • {} 是 list
  • [] 是 tuple
  • <> 是 pattern macro
  • $x 是声明 match variable x
  • ,x 是引用 match variable x 的值

说明下首页那个列举孪生素数的例子:

(match-all primes (list integer)
    [<join _ <cons $p <cons ,(+ p 2) _>>>
     [p (+ p 2)]])

primes 是个所有素数的无穷列表, 由于 Egison 偷懒用 Haskell 实现, 支持无穷列表没什么障碍... 看看它的前 10 项

(take 10 primes)
;=> {2 3 5 7 11 13 17 19 23 29}

这段 match-all 代码把素数列表转换成 List Integer 作为匹配的输入, 穷举所有符合 <join _ <cons $p <cons ,(+ p 2) _>>>p

consjoin (我觉得叫 concat 好一点...) 是构造 list 的基本函数 (ruby 的 each_conscons 也是来源于 lisp):

(cons 1 (cons 2 (cons 3 {})))
;=> {1 2 3}

用在 pattern 中是解析构 list 的作用. 另外

  • _ 是个哑元, 匹配任何东西
  • $p 将任意匹配结果赋值给 match variable p
  • ,(+ p 2) 求值 p + 2 然后匹配 (注意前面那个逗号... 写模式语言的语法不容易...)

最后对每个匹配 p 输出 [p (+ p 2)]

翻译成 ruby 就是

Prime.each_cons(2).lazy.select{|p, q| q == p + 2}.take(10).to_a

match-all 是这个模式匹配的核心, 基本语法是:

match-all-expr ::= '(' match-all tgt-expr matcher-expr match-clause ')'
match-clause ::= '[' pattern expr ']'

基本 matcher 有: list, set, multiset (现在 set matcher 还有 bug 的样子, 不能去重), array (未实现) 模式构造器有: cons, join, snoc (逆序的 cons...), nioj (逆序的 join) 模式运算: | (或), & (与), ^ (非)

matcher + pattern 就决定了它是如何生成序列来搜索的, 有多少个 match variable 就套多少层, 一个 1000 大小的 list 用 20 个 match variable 说不定就爆炸了...


我觉得像极了个 prolog... 不过写法更像代码执行的顺序, 而且不是 prolog 那样显式指定 sequence, 可以自定义 matcher, match variable 遵循 lexical scoping. 对比代码:

Prolog 版 https://gist.github.com/GRGSIBERIA/c61e05f3fbb4332bf81e

Egison 版 (并列出所有武斗魔法少女霹雳 Q 娃系列的主角) https://gist.github.com/egisatoshi/97453be10d37287bec9c


现在还有了一个 ruby gem, https://github.com/egison/egison-ruby 写法和 egison 略有不同

2 楼 已删除

#1 楼 @saiga 我的意思是模式语言里的 joinconcat 一样, 和 cons 无关

#2 楼 @luikore 原来是吐槽 join 啊...

我还以为什么非线形是指比如矩阵里面匹配一个子矩阵。结果就这种破玩意儿?

#4 楼 @bhuztez 矩阵还不是线性代数? ... 起名字要能唬住人...

匿名 #7 2015年02月06日

:plus1:

需要 登录 后方可回复, 如果你还没有账号请 注册新账号